Sorted and priority list factories

lists.js

/**
 * @param {any[]} items
 * @param {any} item
 * @param {{ (a: any, b: any) => number }} compare
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
function binarySearch (items, item, compare, low = 0, high = items.length) {
  if (high <= low) {
    return compare(item, items[low]) > 0 ? (low + 1) : low
  }

  const mid = Math.floor((low + high) / 2)

  if (compare(item, items[mid]) === 0) {
    return mid + 1
  }

  if (compare(item, items[mid]) > 0) {
    return binarySearch(items, item, compare, mid + 1, high)
  } else {
    return binarySearch(items, item, compare, low, mid - 1)
  }
}

const defaultCompare = (a, b) => {
  return a > b ? 1 : (a < b ? -1 : 0)
}

/**
 * @param {Object} [options]
 * @param {{ (a: any, b: any) => number }} [options.compare] Comparison function
 */
export function SortedList ({ compare = defaultCompare } = {}) {
  const items = []

  return {
    get size () {
      return items.length
    },
    /** @param {number} index */
    at (index) {
      if (index >= 0 && index < items.length) {
        return items[index]
      } else {
        throw new Error('IndexOutOfBounds')
      }
    },
    add (item) {
      if (items.length === 0) {
        items.push(item)
      } else {
        const k = binarySearch(items, item, compare)
        items.splice(k, 0, item)
      }

      return this
    },
    toArray () {
      return items.slice()
    }
  }
}

export function PriorityList () {
  const list = SortedList({
    compare (a, b) { return b.priority - a.priority }
  })

  list.addFirst = function (value) {
    this.add(value, { priority: Infinity })
    return this
  }

  list.addLast = function (value) {
    this.add(value, { priority: -Infinity })
    return this
  }

  const at = list.at
  list.at = function (index) {
    return at.call(this, index).value
  }

  const add = list.add
  /**
   * @param {any} value
   * @param {Object} [options]
   * @param {number} [options.priority]
   */
  list.add = function (value, { priority = 0 } = {}) {
    add.call(this, { value, priority })
    return this
  }

  const toArray = list.toArray
  list.toArray = function () {
    return toArray.call(this).map(item => item.value)
  }

  return list
}