History 관리 최적화

// ✅ 좋음: Operation 기반 history
interface HistoryEntry {
  operations: Operation[];
  inverseOperations: Operation[]; // 사전 계산된 리버스 Operation
  beforeSelection: Selection;
  afterSelection: Selection;
  // Model snapshot 없음!
}

class HistoryManager {
  #undoStack: HistoryEntry[] = [];
  #redoStack: HistoryEntry[] = [];
  #model: DocumentModel; // 단일 현재 model
  
  record(operations: Operation[]) {
    const beforeSelection = this.#model.getSelection();
    
    // Operation 적용
    operations.forEach(op => this.#model.apply(op));
    
    const afterSelection = this.#model.getSelection();
    
    // 리버스 Operation 계산
    const inverseOperations = operations
      .slice()
      .reverse()
      .map(op => this.#getInverseOperation(op));
    
    this.#undoStack.push({
      operations,
      inverseOperations,
      beforeSelection,
      afterSelection
    });
    
    this.#redoStack = []; // 새 액션에서 redo 지우기
  }
  
  undo(): boolean {
    if (this.#undoStack.length === 0) {
      return false;
    }
    
    const entry = this.#undoStack.pop()!;
    
    // 리버스 Operation 적용 (역순으로)
    for (let i = entry.inverseOperations.length - 1; i >= 0; i--) {
      this.#model.apply(entry.inverseOperations[i]);
    }
    
    this.#model.setSelection(entry.beforeSelection);
    
    // redo 스택으로 이동
    this.#redoStack.push(entry);
    return true;
  }
  
  redo(): boolean {
    if (this.#redoStack.length === 0) {
      return false;
    }
    
    const entry = this.#redoStack.pop()!;
    
    // Operation 재적용
    entry.operations.forEach(op => {
      this.#model.apply(op);
    });
    
    this.#model.setSelection(entry.afterSelection);
    
    // undo 스택으로 이동
    this.#undoStack.push(entry);
    return true;
  }
  
  #getInverseOperation(op: Operation): Operation {
    switch (op.type) {
      case 'insertText':
        return {
          type: 'deleteText',
          path: op.path,
          length: op.text.length,
          deletedContent: op.text // redo를 위해 저장
        };
      
      case 'deleteText':
        return {
          type: 'insertText',
          path: op.path,
          text: op.deletedContent || ''
        };
      
      case 'insertNode':
        return {
          type: 'deleteNode',
          path: op.path,
          deletedNode: op.node // redo를 위해 저장
        };
      
      case 'deleteNode':
        return {
          type: 'insertNode',
          path: op.path,
          node: op.deletedNode
        };
      
      case 'applyFormat':
        return {
          type: 'removeFormat',
          path: op.path,
          length: op.length,
          format: op.format,
          previousValue: this.#model.getFormatAt(op.path, op.format)
        };
      
      case 'removeFormat':
        return {
          type: 'applyFormat',
          path: op.path,
          length: op.length,
          format: op.format,
          value: op.previousValue
        };
      
      default:
        throw new Error(`알 수 없는 operation: ${op.type}`);
    }
  }
}

// 메모리 사용량: O(history_size × operation_size)
// 각각 약 10개 operation이 있는 50개 history entry = 약 수 KB
// vs 전체 snapshot의 50MB+!

// 예제: 사용자가 "Hello World" 입력
// 전체 snapshot 접근법:
// - beforeModel: ~1MB (전체 문서)
// - afterModel: ~1MB (전체 문서)
// 총: entry당 ~2MB

// Operation 기반 접근법:
const entry = {
  operations: [
    { type: 'insertText', path: [0, 5], text: 'H' },
    { type: 'insertText', path: [0, 6], text: 'e' },
    { type: 'insertText', path: [0, 7], text: 'l' },
    { type: 'insertText', path: [0, 8], text: 'l' },
    { type: 'insertText', path: [0, 9], text: 'o' },
    { type: 'insertText', path: [0, 10], text: ' ' },
    { type: 'insertText', path: [0, 11], text: 'W' },
    { type: 'insertText', path: [0, 12], text: 'o' },
    { type: 'insertText', path: [0, 13], text: 'r' },
    { type: 'insertText', path: [0, 14], text: 'l' },
    { type: 'insertText', path: [0, 15], text: 'd' }
  ],
  inverseOperations: [/* 11개 리버스 Operation */]
};
// 총: ~수백 바이트 vs 2MB!

// 메모리 절약: 99.9%+ 감소

class HybridHistoryManager {
  #undoStack: HistoryEntry[] = [];
  #checkpoints: Map<number, DocumentModel> = new Map();
  #checkpointInterval = 20; // 20개 entry마다 snapshot 생성
  
  record(operations: Operation[]) {
    const entryIndex = this.#undoStack.length;
    
    // 주기적으로 checkpoint 생성
    if (entryIndex % this.#checkpointInterval === 0) {
      this.#checkpoints.set(entryIndex, this.#model.clone());
    }
    
    // Operation 저장 (전체 model 아님)
    const entry: HistoryEntry = {
      operations,
      inverseOperations: this.#computeInverses(operations),
      checkpointIndex: entryIndex,
      // ...
    };
    
    this.#undoStack.push(entry);
  }
  
  undo(): boolean {
    if (this.#undoStack.length === 0) {
      return false;
    }
    
    const entry = this.#undoStack.pop()!;
    
    // 가까운 checkpoint 확인
    const nearestCheckpoint = this.#findNearestCheckpoint(entry.checkpointIndex);
    
    if (nearestCheckpoint && this.#shouldUseCheckpoint(entry, nearestCheckpoint)) {
      // Checkpoint에서 복원하고 operation 재생
      this.#restoreFromCheckpoint(nearestCheckpoint, entry);
    } else {
      // 리버스 Operation 사용 (일반적인 경우)
      this.#applyInverseOperations(entry.inverseOperations);
    }
    
    return true;
  }
  
  #shouldUseCheckpoint(entry: HistoryEntry, checkpoint: number): boolean {
    // 많은 operation을 undo해야 하는 경우 checkpoint 사용
    const distance = entry.checkpointIndex - checkpoint;
    return distance > 10; // Checkpoint 사용 임계값
  }
  
  #restoreFromCheckpoint(checkpointIndex: number, targetEntry: HistoryEntry) {
    const checkpoint = this.#checkpoints.get(checkpointIndex)!;
    this.#model = checkpoint.clone();
    
    // Checkpoint에서 target까지 operation 재생
    const entries = this.#undoStack.slice(checkpointIndex, targetEntry.checkpointIndex);
    entries.forEach(e => {
      e.operations.forEach(op => this.#model.apply(op));
    });
  }
}

// Checkpoint 전략: 전략적 지점에 snapshot 저장
class CheckpointManager {
  #checkpoints: Map<number, DocumentModel> = new Map();
  #maxCheckpoints = 5; // Checkpoint 수 제한
  
  createCheckpoint(index: number, model: DocumentModel) {
    // 제한에 도달하면 가장 오래된 checkpoint 제거
    if (this.#checkpoints.size >= this.#maxCheckpoints) {
      const oldest = Math.min(...this.#checkpoints.keys());
      this.#checkpoints.delete(oldest);
    }
    
    this.#checkpoints.set(index, model.clone());
  }
  
  getNearestCheckpoint(targetIndex: number): [number, DocumentModel] | null {
    let nearest: [number, DocumentModel] | null = null;
    let minDistance = Infinity;
    
    for (const [index, model] of this.#checkpoints) {
      if (index <= targetIndex) {
        const distance = targetIndex - index;
        if (distance < minDistance) {
          minDistance = distance;
          nearest = [index, model];
        }
      }
    }
    
    return nearest;
  }
  
  // 오래된 checkpoint 정리
  cleanup(beforeIndex: number) {
    for (const index of this.#checkpoints.keys()) {
      if (index < beforeIndex) {
        this.#checkpoints.delete(index);
      }
    }
  }
}