System Design #15: Design a Spreadsheet / Data Grid

interface VirtualGrid {
  // Viewport
  scrollTop: number;
  scrollLeft: number;
  viewportWidth: number;
  viewportHeight: number;
  
  // Dimensions
  rowHeights: number[];       // Variable heights per row
  columnWidths: number[];     // Variable widths per column
  
  // Computed visible range
  visibleRows: { start: number; end: number };
  visibleColumns: { start: number; end: number };
  
  // Overscan (render a few extra rows/cols for smooth scrolling)
  overscanRows: number;       // Default: 3
  overscanColumns: number;    // Default: 2
}

function getVisibleRange(
  scrollOffset: number,
  viewportSize: number,
  sizes: number[],
  overscan: number
): { start: number; end: number } {
  let accumulated = 0;
  let start = 0;
  let end = 0;
  
  // Find first visible item
  for (let i = 0; i < sizes.length; i++) {
    if (accumulated + sizes[i] > scrollOffset) {
      start = Math.max(0, i - overscan);
      break;
    }
    accumulated += sizes[i];
  }
  
  // Find last visible item
  accumulated = 0;
  for (let i = start; i < sizes.length; i++) {
    accumulated += sizes[i];
    if (accumulated > scrollOffset + viewportSize) {
      end = Math.min(sizes.length - 1, i + overscan);
      break;
    }
  }
  
  return { start, end: end || sizes.length - 1 };
}

DataGrid
├── GridHeader                    // Sticky column headers
│   ├── ColumnHeader[]            // Sortable, resizable
│   └── ColumnResizeHandle[]
├── GridBody                      // Virtualized content area
│   ├── RowNumberColumn           // Sticky row numbers (1, 2, 3...)
│   └── VirtualCells              // Only rendered cells
│       └── Cell                  // Individual cell
│           ├── CellDisplay       // Read-only view
│           └── CellEditor        // Active editing input
├── SelectionOverlay              // Blue selection rectangle(s)
├── ScrollbarX / ScrollbarY       // Custom scrollbars
├── FormulaBar                    // Shows active cell formula
└── StatusBar                     // "SUM: 42, AVG: 7, COUNT: 6"

// Don't store 100K × 50 cells in memory — most are empty!
// Use sparse storage: only store cells that have values

type CellKey = string; // "A1", "B2", etc. or "r0c0", "r1c1"

interface CellData {
  value: any;                    // Raw value (number, string, boolean)
  formula?: string;              // "=SUM(A1:A10)"
  displayValue?: string;         // Computed/formatted display text
  format?: CellFormat;
  style?: CellStyle;
}

interface CellFormat {
  type: 'text' | 'number' | 'date' | 'currency' | 'percentage';
  pattern?: string;              // "#,##0.00", "MM/dd/yyyy"
  locale?: string;
}

interface CellStyle {
  bold?: boolean;
  italic?: boolean;
  textColor?: string;
  bgColor?: string;
  alignment?: 'left' | 'center' | 'right';
}

// Sparse data store
class SpreadsheetData {
  private cells = new Map<CellKey, CellData>();
  
  getCell(row: number, col: number): CellData | null {
    return this.cells.get(`r${row}c${col}`) || null;
  }
  
  setCell(row: number, col: number, data: CellData): void {
    const key = `r${row}c${col}`;
    if (data.value === null && !data.formula && !data.style) {
      this.cells.delete(key); // Remove empty cells
    } else {
      this.cells.set(key, data);
    }
  }
  
  getCellCount(): number {
    return this.cells.size; // Only non-empty cells
  }
}

interface SelectionState {
  activeCell: CellRef;           // Current "focused" cell
  ranges: CellRange[];           // Selected ranges (can be multiple with Ctrl)
  isEditing: boolean;            // Cell editor is active
  editValue: string;             // Current editor content
  selectionMode: 'idle' | 'selecting' | 'extending';
}

interface CellRef {
  row: number;
  col: number;
}

interface CellRange {
  start: CellRef;
  end: CellRef;
}

function selectionReducer(state: SelectionState, action: SelectionAction): SelectionState {
  switch (action.type) {
    case 'CLICK_CELL':
      return {
        ...state,
        activeCell: action.cell,
        ranges: [{ start: action.cell, end: action.cell }],
        isEditing: false,
      };
      
    case 'SHIFT_CLICK_CELL':
      // Extend current selection
      const lastRange = state.ranges[state.ranges.length - 1];
      return {
        ...state,
        ranges: [
          ...state.ranges.slice(0, -1),
          { start: lastRange.start, end: action.cell },
        ],
      };
      
    case 'CTRL_CLICK_CELL':
      // Add new selection range
      return {
        ...state,
        activeCell: action.cell,
        ranges: [...state.ranges, { start: action.cell, end: action.cell }],
      };
      
    case 'DOUBLE_CLICK_CELL':
      return {
        ...state,
        activeCell: action.cell,
        isEditing: true,
        editValue: getCellDisplayValue(action.cell),
      };
      
    case 'ARROW_KEY':
      if (state.isEditing) return state; // Don't navigate while editing
      const next = moveCell(state.activeCell, action.direction);
      return {
        ...state,
        activeCell: next,
        ranges: [{ start: next, end: next }],
      };
      
    case 'ENTER':
      if (state.isEditing) {
        // Confirm edit and move down
        commitEdit(state.activeCell, state.editValue);
        const below = { row: state.activeCell.row + 1, col: state.activeCell.col };
        return { ...state, isEditing: false, activeCell: below, ranges: [{ start: below, end: below }] };
      }
      // Start editing
      return { ...state, isEditing: true, editValue: '' };
      
    case 'TAB':
      // Move right (or to next row start)
      const nextTab = state.activeCell.col < maxCol
        ? { row: state.activeCell.row, col: state.activeCell.col + 1 }
        : { row: state.activeCell.row + 1, col: 0 };
      return { ...state, activeCell: nextTab, ranges: [{ start: nextTab, end: nextTab }], isEditing: false };
      
    case 'ESCAPE':
      return { ...state, isEditing: false };
  }
}

const Cell = memo(function Cell({
  row, col, data, isActive, isSelected, isEditing, onEdit
}: CellProps) {
  const cellRef = useRef<HTMLDivElement>(null);
  
  if (isEditing) {
    return (
      <input
        autoFocus
        className="absolute inset-0 border-2 border-primary z-10 px-1 outline-none"
        defaultValue={data?.formula || data?.value || ''}
        onBlur={(e) => onEdit(e.target.value)}
        onKeyDown={handleEditKeyDown}
      />
    );
  }
  
  return (
    <div
      ref={cellRef}
      role="gridcell"
      aria-colindex={col + 1}
      aria-selected={isSelected}
      tabIndex={isActive ? 0 : -1}
      className={cn(
        "px-1 py-0.5 border-r border-b border-border text-xs truncate",
        isActive && "ring-2 ring-primary ring-inset",
        isSelected && !isActive && "bg-primary/10",
        data?.style?.bold && "font-bold",
      )}
      style={{
        textAlign: data?.style?.alignment || 'left',
        color: data?.style?.textColor,
        backgroundColor: data?.style?.bgColor,
      }}
    >
      {data?.displayValue ?? data?.value ?? ''}
    </div>
  );
});

async function handleCopy(selection: CellRange[], data: SpreadsheetData) {
  const { start, end } = normalizeRange(selection[0]);
  
  // Build tab-separated text (Excel-compatible)
  const rows: string[] = [];
  for (let r = start.row; r <= end.row; r++) {
    const cols: string[] = [];
    for (let c = start.col; c <= end.col; c++) {
      const cell = data.getCell(r, c);
      cols.push(cell?.value?.toString() || '');
    }
    rows.push(cols.join('\t'));
  }
  
  const text = rows.join('\n');
  
  // Also write HTML for rich paste
  const html = buildHtmlTable(selection, data);
  
  await navigator.clipboard.write([
    new ClipboardItem({
      'text/plain': new Blob([text], { type: 'text/plain' }),
      'text/html': new Blob([html], { type: 'text/html' }),
    }),
  ]);
}

async function handlePaste(activeCell: CellRef, data: SpreadsheetData) {
  const clipText = await navigator.clipboard.readText();
  const rows = clipText.split('\n').map(row => row.split('\t'));
  
  const commands: EditCommand[] = [];
  rows.forEach((cols, ri) => {
    cols.forEach((value, ci) => {
      commands.push({
        type: 'SET_CELL',
        row: activeCell.row + ri,
        col: activeCell.col + ci,
        value: parseValue(value),
      });
    });
  });
  
  executeCommands(commands); // Batch for undo
}

class FormulaEngine {
  private depGraph = new Map<string, Set<string>>(); // cell → cells that depend on it
  
  evaluate(formula: string, data: SpreadsheetData): any {
    // Parse: "=SUM(A1:A10)" → { fn: "SUM", args: [Range("A1", "A10")] }
    const parsed = parseFormula(formula);
    
    switch (parsed.fn) {
      case 'SUM':
        return this.resolveRange(parsed.args[0], data)
          .reduce((sum, v) => sum + (Number(v) || 0), 0);
      case 'AVERAGE':
        const values = this.resolveRange(parsed.args[0], data).filter(v => v !== null);
        return values.reduce((s, v) => s + Number(v), 0) / values.length;
      case 'IF':
        const condition = this.evaluateExpression(parsed.args[0], data);
        return condition ? parsed.args[1] : parsed.args[2];
      case 'COUNT':
        return this.resolveRange(parsed.args[0], data).filter(v => v !== null).length;
    }
  }
  
  // When A1 changes, recalculate all cells that reference A1
  onCellChange(cellKey: string, data: SpreadsheetData) {
    const dependents = this.depGraph.get(cellKey) || new Set();
    for (const dep of dependents) {
      const cell = data.getCell(...parseCellKey(dep));
      if (cell?.formula) {
        cell.displayValue = String(this.evaluate(cell.formula, data));
        // Recursive: this cell changing may trigger other recalcs
        this.onCellChange(dep, data);
      }
    }
  }
}

interface EditCommand {
  execute(data: SpreadsheetData): void;
  undo(data: SpreadsheetData): void;
  description: string;
}

class UndoManager {
  private undoStack: EditCommand[] = [];
  private redoStack: EditCommand[] = [];
  
  execute(command: EditCommand, data: SpreadsheetData) {
    command.execute(data);
    this.undoStack.push(command);
    this.redoStack = []; // Clear redo on new action
  }
  
  undo(data: SpreadsheetData) {
    const command = this.undoStack.pop();
    if (!command) return;
    command.undo(data);
    this.redoStack.push(command);
  }
  
  redo(data: SpreadsheetData) {
    const command = this.redoStack.pop();
    if (!command) return;
    command.execute(data);
    this.undoStack.push(command);
  }
}

// Example command
class SetCellCommand implements EditCommand {
  private prevData: CellData | null;
  
  constructor(
    private row: number,
    private col: number,
    private newData: CellData,
  ) {}
  
  execute(data: SpreadsheetData) {
    this.prevData = data.getCell(this.row, this.col);
    data.setCell(this.row, this.col, this.newData);
  }
  
  undo(data: SpreadsheetData) {
    if (this.prevData) {
      data.setCell(this.row, this.col, this.prevData);
    } else {
      data.setCell(this.row, this.col, { value: null });
    }
  }
  
  get description() { return `Edit cell R${this.row}C${this.col}`; }
}

function useColumnResize(
  colIndex: number,
  onResize: (col: number, width: number) => void
) {
  const handleMouseDown = (e: React.MouseEvent) => {
    e.preventDefault();
    const startX = e.clientX;
    const startWidth = columnWidths[colIndex];
    
    const handleMouseMove = (e: MouseEvent) => {
      requestAnimationFrame(() => {
        const delta = e.clientX - startX;
        const newWidth = Math.max(40, startWidth + delta);
        onResize(colIndex, newWidth);
      });
    };
    
    const handleMouseUp = () => {
      document.removeEventListener('mousemove', handleMouseMove);
      document.removeEventListener('mouseup', handleMouseUp);
    };
    
    document.addEventListener('mousemove', handleMouseMove);
    document.addEventListener('mouseup', handleMouseUp);
  };
  
  return handleMouseDown;
}