Data Structures

/**
 * Comparer interface for heap ordering
 */
interface IComparer<T> {
  /** Minimum value for the type */
  min: T;
  /** Comparison function returning negative, zero, or positive values */
  compare(a: T, b: T): number;
}

/**
 * Built-in number comparer for numeric heaps
 */
const NumberComparer: IComparer<number>;

/**
 * Heap node interface for direct heap manipulation
 */
interface IHeapNode<T> {
  /** The stored value */
  value: T;
  /** Internal heap position (managed by heap) */
  position: number;
}

/**
 * Ordered heap data structure with customizable comparison
 * Maintains heap property where parent <= children (min-heap by default)
 */
class Heap<T> {
  /**
   * Creates a new heap with required comparer
   * @param comp - Comparer for heap ordering (required parameter)
   */
  constructor(comp: IComparer<T>);
  
  /**
   * Gets and removes the minimum element from the heap
   * @returns The minimum element value
   */
  get(): T;
  
  /**
   * Gets the minimum element without removing it
   * @returns The heap node containing the minimum element
   */
  peek(): IHeapNode<T>;
  
  /**
   * Adds a new value to the heap
   * @param value - Value to add
   * @returns The heap node that was created
   */
  add(value: T): IHeapNode<T>;
  
  /**
   * Updates the position of a node after its value has changed
   * @param node - The heap node to update
   */
  update(node: IHeapNode<T>): void;
  
  /**
   * Removes a specific node from the heap
   * @param node - The heap node to remove
   */
  remove(node: IHeapNode<T>): void;
  
  /**
   * Gets the number of elements in the heap
   * @returns The number of elements in the heap
   */
  count(): number;
}

import { Heap, NumberComparer } from "@fluidframework/common-utils";

// Basic numeric heap (min-heap)
const numberHeap = new Heap<number>(NumberComparer);
numberHeap.add(5);
numberHeap.add(2);
numberHeap.add(8);
numberHeap.add(1);

console.log(numberHeap.peek().value); // 1 (minimum)
console.log(numberHeap.get());  // 1 (removes and returns minimum)
console.log(numberHeap.get());  // 2 (next minimum)

// Custom comparer for max-heap
const maxComparer = {
  min: Number.NEGATIVE_INFINITY,
  compare: (a: number, b: number) => b - a // Reverse comparison for max-heap
};

const maxHeap = new Heap<number>(maxComparer);
maxHeap.add(5);
maxHeap.add(2);
maxHeap.add(8);
console.log(maxHeap.peek().value); // 8 (maximum in max-heap)

// Object heap with custom comparison
interface Task {
  id: string;
  priority: number;
  description: string;
}

const taskComparer: IComparer<Task> = {
  min: { id: "", priority: Number.NEGATIVE_INFINITY, description: "" },
  compare: (a, b) => a.priority - b.priority // Lower number = higher priority
};

const taskQueue = new Heap<Task>(taskComparer);

taskQueue.add({ id: "1", priority: 3, description: "Low priority task" });
taskQueue.add({ id: "2", priority: 1, description: "High priority task" });
taskQueue.add({ id: "3", priority: 2, description: "Medium priority task" });

// Process tasks in priority order
while (taskQueue.count() > 0) {
  const nextTask = taskQueue.get();
  console.log(`Processing: ${nextTask.description}`);
}

// Using heap nodes for updates
const urgentTask = { id: "4", priority: 5, description: "Initially low priority" };
const taskNode = taskQueue.add(urgentTask);

// Later, update priority
urgentTask.priority = 0; // Make it highest priority
taskQueue.update(taskNode); // Heap reorders accordingly

/**
 * Range interface representing a span with primary and secondary coordinates
 */
interface IRange {
  /** Primary range start position */
  primary: number;
  /** Secondary range start position */  
  secondary: number;
  /** Length of the range */
  length: number;
}

/**
 * Serializable snapshot of range tracker state
 */
interface IRangeTrackerSnapshot {
  /** Array of tracked ranges */
  ranges: IRange[];
  /** Last primary position */
  lastPrimary: number;
  /** Last secondary position */
  lastSecondary: number;
}

/**
 * Tracks 1:N relation between two ranges
 * Used by Fluid Framework deli for branch mapping and coordinate transformation
 */
class RangeTracker {
  /**
   * Creates a new RangeTracker
   */
  constructor();
  
  /**
   * Adds a new range mapping
   * @param primaryStart - Start position in primary coordinate space
   * @param primaryEnd - End position in primary coordinate space  
   * @param secondaryStart - Start position in secondary coordinate space
   */
  add(primaryStart: number, primaryEnd: number, secondaryStart: number): void;
  
  /**
   * Gets range information for a primary position
   * @param primaryPosition - Position in primary coordinate space
   * @param primaryEnd - Optional end position for range queries
   * @returns Range information or undefined if not found
   */
  get(primaryPosition: number, primaryEnd?: number): IRange | undefined;
  
  /**
   * Updates the base positions for relative calculations
   * @param primaryBase - New primary base position
   * @param secondaryBase - New secondary base position  
   */
  updateBase(primaryBase: number, secondaryBase: number): void;
  
  /**
   * Serializes the current state for persistence
   * @returns Serializable snapshot of current state
   */
  serialize(): IRangeTrackerSnapshot;
  
  /**
   * Restores state from a serialized snapshot
   * @param snapshot - Previously serialized snapshot
   */
  deserialize(snapshot: IRangeTrackerSnapshot): void;
}

import { RangeTracker } from "@fluidframework/common-utils";

// Document coordinate mapping
const coordMapper = new RangeTracker();

// Map document sections to display coordinates
// Document chars 0-100 map to display pixels 0-500
coordMapper.add(0, 100, 0);

// Document chars 100-200 map to display pixels 600-1100 (with gap)
coordMapper.add(100, 200, 600);

// Find display coordinates for document position
const range1 = coordMapper.get(50); // Document position 50
console.log(range1?.secondary); // Display coordinate for doc position 50

const range2 = coordMapper.get(150); // Document position 150  
console.log(range2?.secondary); // Display coordinate for doc position 150

// Branch mapping in collaborative editing
class BranchMapper {
  private tracker = new RangeTracker();
  
  addEdit(localStart: number, localEnd: number, remoteStart: number): void {
    this.tracker.add(localStart, localEnd, remoteStart);
  }
  
  mapToRemote(localPosition: number): number | undefined {
    const range = this.tracker.get(localPosition);
    if (!range) return undefined;
    
    const offset = localPosition - range.primary;
    return range.secondary + offset;
  }
  
  save(): string {
    return JSON.stringify(this.tracker.serialize());
  }
  
  load(serialized: string): void {
    const snapshot = JSON.parse(serialized);
    this.tracker.deserialize(snapshot);
  }
}

// Time series data mapping
const timeMapper = new RangeTracker();

// Map time ranges to data indices
// Hours 0-24 (day 1) map to data indices 0-1440 (minute-level data)
timeMapper.add(0, 24, 0);

// Hours 24-48 (day 2) map to data indices 1440-2880
timeMapper.add(24, 48, 1440);

// Find data index for specific time
const dataRange = timeMapper.get(36); // Hour 36 (day 2, hour 12)
if (dataRange) {
  const hourOffset = 36 - dataRange.primary;
  const dataIndex = dataRange.secondary + (hourOffset * 60); // Convert to minutes
  console.log(`Hour 36 maps to data index: ${dataIndex}`);
}

// Viewport mapping with dynamic updates
class ViewportMapper {
  private tracker = new RangeTracker();
  
  addViewport(contentStart: number, contentEnd: number, viewStart: number): void {
    this.tracker.add(contentStart, contentEnd, viewStart);
  }
  
  scrollTo(newContentBase: number, newViewBase: number): void {
    this.tracker.updateBase(newContentBase, newViewBase);
  }
  
  getViewPosition(contentPosition: number): number | undefined {
    const range = this.tracker.get(contentPosition);
    if (!range) return undefined;
    
    return range.secondary + (contentPosition - range.primary);
  }
}

import { Heap } from "@fluidframework/common-utils";

// Event scheduling system
interface ScheduledEvent {
  id: string;
  timestamp: number;
  callback: () => void;
  data?: any;
}

class EventScheduler {
  private eventHeap = new Heap<ScheduledEvent>({
    min: { id: "", timestamp: 0, callback: () => {} },
    compare: (a, b) => a.timestamp - b.timestamp
  });
  
  schedule(event: ScheduledEvent): void {
    this.eventHeap.add(event);
  }
  
  processNext(): ScheduledEvent | null {
    if (this.eventHeap.isEmpty) return null;
    
    const nextEvent = this.eventHeap.get();
    if (nextEvent.timestamp <= Date.now()) {
      nextEvent.callback();
      return nextEvent;
    }
    
    // Put it back if not ready
    this.eventHeap.add(nextEvent);
    return null;
  }
  
  getNextTimestamp(): number | null {
    if (this.eventHeap.isEmpty) return null;
    return this.eventHeap.peek().timestamp;
  }
}

// Usage
const scheduler = new EventScheduler();

scheduler.schedule({
  id: "reminder",
  timestamp: Date.now() + 5000, // 5 seconds from now
  callback: () => console.log("Reminder fired!"),
  data: { message: "Don't forget the meeting" }
});

import { RangeTracker } from "@fluidframework/common-utils";

// Multi-layer coordinate system
class MultiLayerMapper {
  private layers: Map<string, RangeTracker> = new Map();
  
  addLayer(layerId: string): void {
    this.layers.set(layerId, new RangeTracker());
  }
  
  mapRange(layerId: string, sourceStart: number, sourceEnd: number, targetStart: number): void {
    const tracker = this.layers.get(layerId);
    if (tracker) {
      tracker.add(sourceStart, sourceEnd, targetStart);
    }
  }
  
  // Map position through multiple layers
  mapThroughLayers(position: number, layerOrder: string[]): number {
    let currentPosition = position;
    
    for (const layerId of layerOrder) {
      const tracker = this.layers.get(layerId);
      if (tracker) {
        const range = tracker.get(currentPosition);
        if (range) {
          const offset = currentPosition - range.primary;
          currentPosition = range.secondary + offset;
        }
      }
    }
    
    return currentPosition;
  }
}