Range Sets

/**
 * A range set stores a collection of ranges with associated values.
 * The ranges are non-overlapping and stored in sorted order.
 */
class RangeSet<T extends RangeValue> {
  /** Create a range set from an array of ranges */
  static of<T extends RangeValue>(ranges: readonly Range<T>[] | Range<T>, sort?: boolean): RangeSet<T>;
  
  /** An empty range set */
  static empty: RangeSet<any>;
  
  /** The number of ranges in this set */
  readonly size: number;
  
  /** Whether this range set is empty */
  readonly empty: boolean;
  
  /** Create a new range set by updating this one */
  update(updateSpec: RangeSetUpdateSpec<T>): RangeSet<T>;
  
  /** Map this range set through a set of changes */
  map(changes: ChangeDesc): RangeSet<T>;
  
  /** Iterate over ranges that overlap with the given range */
  between(from: number, to: number, f: (from: number, to: number, value: T) => void | false): void;
  
  /** Get an iterator for this range set */
  iter(from?: number): RangeCursor<T>;
  
  /** Compare this range set with another */
  compare(other: RangeSet<T>, textDiff?: ChangeDesc, comparator?: RangeComparator<T>, oldLen?: number): void;
}

interface RangeSetUpdateSpec<T extends RangeValue> {
  /** Ranges to add */
  add?: readonly Range<T>[];
  
  /** Ranges to remove (by filtering) */
  filter?: (from: number, to: number, value: T) => boolean;
  
  /** Ranges of text to filter out entirely */
  filterFrom?: number;
  
  /** End of range to filter out */
  filterTo?: number;
}

import { RangeSet, RangeValue, Range } from "@codemirror/state";

// Define a custom range value
class HighlightValue extends RangeValue {
  constructor(public color: string) {
    super();
  }
  
  eq(other: RangeValue) {
    return other instanceof HighlightValue && other.color === this.color;
  }
}

// Create ranges
const yellowHighlight = new HighlightValue("yellow");
const blueHighlight = new HighlightValue("blue");

const ranges = [
  yellowHighlight.range(5, 10),
  blueHighlight.range(15, 20),
  yellowHighlight.range(25, 30)
];

// Create range set
const rangeSet = RangeSet.of(ranges);

console.log(rangeSet.size); // 3
console.log(rangeSet.empty); // false

// Iterate over ranges in a specific area
rangeSet.between(8, 18, (from, to, value) => {
  console.log(`Range ${from}-${to}: ${value.color}`);
  // Output: "Range 8-10: yellow" and "Range 15-18: blue"
});

/**
 * Each range is associated with a value, which must inherit from this class.
 */
abstract class RangeValue {
  /** Compare this value with another value */
  eq(other: RangeValue): boolean;
  
  /** The bias value at the start of the range */
  startSide: number;
  
  /** The bias value at the end of the range */
  endSide: number;
  
  /** The mode with which the location of the range should be mapped when from and to are the same */
  mapMode: MapMode;
  
  /** Determines whether this value marks a point range */
  point: boolean;
  
  /** Create a Range with this value */
  range(from: number, to?: number): Range<this>;
}

// Custom range value for bookmarks
class BookmarkValue extends RangeValue {
  constructor(public id: string, public label: string) {
    super();
    this.point = true; // This is a point decoration
    this.startSide = 1; // Appears after other content at same position
  }
  
  eq(other: RangeValue) {
    return other instanceof BookmarkValue && 
           other.id === this.id && 
           other.label === this.label;
  }
}

// Custom range value for error highlighting
class ErrorValue extends RangeValue {
  constructor(public message: string, public severity: "error" | "warning") {
    super();
    this.startSide = -1; // Appears before other content
    this.endSide = 1;    // Ends after other content
  }
  
  eq(other: RangeValue) {
    return other instanceof ErrorValue && 
           other.message === this.message && 
           other.severity === this.severity;
  }
}

// Create and use custom ranges
const bookmark = new BookmarkValue("bm1", "Important Note");
const error = new ErrorValue("Syntax error", "error");

const bookmarkRange = bookmark.range(15);     // Point range at position 15
const errorRange = error.range(20, 25);       // Range from 20 to 25

/**
 * A range associates a value with a range of positions.
 */
class Range<T extends RangeValue> {
  /** The range's start position */
  readonly from: number;
  
  /** Its end position */
  readonly to: number;
  
  /** The value associated with this range */
  readonly value: T;
  
  /** @internal - Create a range (use RangeValue.range() instead) */
  static create<T extends RangeValue>(from: number, to: number, value: T): Range<T>;
}

/**
 * Update a range set by adding, removing, or filtering ranges
 * @param updateSpec Specification of what to change
 */
update(updateSpec: RangeSetUpdateSpec<T>): RangeSet<T>;

/**
 * Map this range set through a set of changes, updating all positions
 * @param changes The changes to map through
 */
map(changes: ChangeDesc): RangeSet<T>;

/**
 * Iterate over ranges that overlap with the given range
 * @param from Start position
 * @param to End position  
 * @param f Callback for each overlapping range
 */
between(from: number, to: number, f: (from: number, to: number, value: T) => void | false): void;

const rangeSet = RangeSet.of([
  new HighlightValue("yellow").range(5, 10),
  new HighlightValue("blue").range(15, 20)
]);

// Add new ranges
const updated = rangeSet.update({
  add: [new HighlightValue("red").range(25, 30)]
});

// Filter ranges
const filtered = rangeSet.update({
  filter: (from, to, value) => value.color !== "blue" // Remove blue highlights
});

// Filter by position
const positionFiltered = rangeSet.update({
  filterFrom: 12,
  filterTo: 18 // Remove ranges that overlap with positions 12-18
});

// Map through changes
const changes = ChangeSet.of([{from: 3, insert: "NEW "}], 50);
const mapped = rangeSet.map(changes);
// All range positions are adjusted for the insertion

/**
 * Get an iterator for this range set
 * @param from Starting position (optional)
 */
iter(from?: number): RangeCursor<T>;

/**
 * Range cursor for iterating over ranges
 */
interface RangeCursor<T extends RangeValue> {
  /** Move to the next range */
  next(): void;
  
  /** The current range's start position */
  from: number;
  
  /** The current range's end position */
  to: number;
  
  /** The current range's value */
  value: T;
  
  /** Whether the iterator is at the end */
  done: boolean;
}

const rangeSet = RangeSet.of([
  new HighlightValue("yellow").range(5, 10),
  new HighlightValue("blue").range(15, 20),
  new HighlightValue("green").range(25, 30)
]);

// Iterate over all ranges
const cursor = rangeSet.iter();
while (!cursor.done) {
  console.log(`Range: ${cursor.from}-${cursor.to}, color: ${cursor.value.color}`);
  cursor.next();
}

// Iterate starting from a specific position
const partialCursor = rangeSet.iter(12);
while (!partialCursor.done) {
  console.log(`Range from pos 12: ${partialCursor.from}-${partialCursor.to}`);
  partialCursor.next();
}

// Collect ranges in an area
const rangesInArea: Range<HighlightValue>[] = [];
rangeSet.between(8, 22, (from, to, value) => {
  rangesInArea.push(value.range(from, to));
});

/**
 * Builder for efficiently constructing range sets
 */
class RangeSetBuilder<T extends RangeValue> {
  /** Create a new builder */
  constructor();
  
  /** Add a range to the builder */
  add(from: number, to: number, value: T): void;
  
  /** Add a point range to the builder */
  addPoint(pos: number, value: T): void;
  
  /** Finish building and return the range set */
  finish(): RangeSet<T>;
}

// Build a large range set efficiently
const builder = new RangeSetBuilder<HighlightValue>();

// Add many ranges (must be added in sorted order)
for (let i = 0; i < 100; i++) {
  const start = i * 10;
  const end = start + 5;
  const color = i % 2 === 0 ? "yellow" : "blue";
  builder.add(start, end, new HighlightValue(color));
}

// Add some point decorations
builder.addPoint(250, new BookmarkValue("bookmark1", "Important"));
builder.addPoint(300, new BookmarkValue("bookmark2", "Note"));

const rangeSet = builder.finish();
console.log(rangeSet.size); // 102 (100 highlights + 2 bookmarks)

/**
 * Collection of methods used when comparing range sets
 */
interface RangeComparator<T extends RangeValue> {
  /** Called for ranges that have different values in old vs new sets */
  compareRange(from: number, to: number, activeA: T[], activeB: T[]): void;
  
  /** Called for point ranges that changed */
  comparePoint(from: number, to: number, pointA: T | null, pointB: T | null): void;
  
  /** Called when range boundaries change */
  boundChange?(pos: number): void;
}

/**
 * Compare this range set with another
 * @param other The range set to compare with
 * @param textDiff Changes to map through (optional)
 * @param comparator Object to receive comparison events
 * @param oldLen Length of old document (when using textDiff)
 */
compare(other: RangeSet<T>, textDiff?: ChangeDesc, comparator?: RangeComparator<T>, oldLen?: number): void;

const oldRangeSet = RangeSet.of([
  new HighlightValue("yellow").range(5, 10),
  new HighlightValue("blue").range(15, 20)
]);

const newRangeSet = RangeSet.of([
  new HighlightValue("yellow").range(5, 10),    // Same
  new HighlightValue("red").range(15, 20),      // Changed color
  new HighlightValue("green").range(25, 30)     // New
]);

const comparator: RangeComparator<HighlightValue> = {
  compareRange(from, to, activeA, activeB) {
    console.log(`Range ${from}-${to} changed:`);
    console.log("  Old:", activeA.map(v => v.color));
    console.log("  New:", activeB.map(v => v.color));
  },
  
  comparePoint(from, to, pointA, pointB) {
    console.log(`Point at ${from} changed from ${pointA?.color} to ${pointB?.color}`);
  }
};

oldRangeSet.compare(newRangeSet, undefined, comparator);
// Will report the change from blue to red at position 15-20
// and the addition of green at 25-30

/**
 * Methods used when iterating over the spans created by a set of ranges
 */
interface SpanIterator<T extends RangeValue> {
  /** Called for any ranges not covered by point decorations */
  span(from: number, to: number, active: readonly T[], openStart: number): void;
  
  /** Called when going over a point decoration */
  point(from: number, to: number, value: T, active: readonly T[], openStart: number, index: number): void;
}

/**
 * Update specification for range sets
 */
interface RangeSetUpdateSpec<T extends RangeValue> {
  add?: readonly Range<T>[];
  filter?: (from: number, to: number, value: T) => boolean;
  filterFrom?: number;
  filterTo?: number;
}

/**
 * Cursor for iterating over ranges
 */
interface RangeCursor<T extends RangeValue> {
  next(): void;
  from: number;
  to: number;
  value: T;
  done: boolean;
}