Method indexOf

packages/db/src/SortedMap.ts:36–83

* Finds the index where a key-value pair should be inserted to maintain sort order. * Uses binary search to find the correct position based on the value (if comparator provided), * with key-based tie-breaking for deterministic ordering when values compare as equal. * If no comparator is pro

(key: TKey, value: TValue)

   * @returns The index where the key should be inserted
   */
  private indexOf(key: TKey, value: TValue): number {
    let left = 0
    let right = this.sortedKeys.length

    // Fast path: no comparator means sort by key only
    if (!this.comparator) {
      while (left < right) {
        const mid = Math.floor((left + right) / 2)
        const midKey = this.sortedKeys[mid]!
        const keyComparison = compareKeys(key, midKey)
        if (keyComparison < 0) {
          right = mid
        } else if (keyComparison > 0) {
          left = mid + 1
        } else {
          return mid
        }
      }
      return left
    }

    // With comparator: sort by value first, then key as tie-breaker
    while (left < right) {
      const mid = Math.floor((left + right) / 2)
      const midKey = this.sortedKeys[mid]!
      const midValue = this.map.get(midKey)!
      const valueComparison = this.comparator(value, midValue)

      if (valueComparison < 0) {
        right = mid
      } else if (valueComparison > 0) {
        left = mid + 1
      } else {
        // Values are equal, use key as tie-breaker for deterministic ordering
        const keyComparison = compareKeys(key, midKey)
        if (keyComparison < 0) {
          right = mid
        } else if (keyComparison > 0) {
          left = mid + 1
        } else {
          // Same key (shouldn't happen during insert, but handle for lookups)
          return mid
        }
      }
    }

    return left
  }

  /**
   * Sets a key-value pair in the map and maintains sort order