crow/col/priority-queue.crow (source)

priority-queue[k, v] record

(has non-public fields)

    Immutable priority queue.

    Elements are key-value pairs. Pairs are sorted by key.
    Popping removes the pair with the lowest key.

    If two pairs have the same key, the second pair added will be popped second.

    priority[k] spec k data, k compare

      new[k, v] (k, v) priority-queue(...a (k, v) tuple2 array) k priority

      to[k, v] (k, v) priority-queue(a (k, v) tuple2 array) k priority

      to[k, v] (k, v) tuple2 array(a (k, v) priority-queue) k priority

      is-empty[k, v] bool(a (k, v) priority-queue) k priority

      True iff a.size == 0.

      size[k, v] nat64(a (k, v) priority-queue) k priority

      Number of pairs in the priority queue.

      This is O(n).

      ~[k, v] (k, v) priority-queue(a (k, v) priority-queue, b (k, v) tuple2) k priority

      Adds a pair to the queue.

      This is O(1), since the work of sorting pairs is actually done in pop.

      pop[k, v] ((k, v) tuple2, (k, v) priority-queue) tuple2?(a (k, v) priority-queue) k priority

      Removes and returns the pair with the lowest key.

      Returns an empty option iff a is empty.

      This is amortized O(log n).

      iterate[k, v] bool(a (k, v) priority-queue, f mut bool((k, v) tuple2)) k priority

      priority-queue-builder[k, v] record mut

      (has non-public fields)

        build[k, v] (k, v) priority-queue(a build-options, f mut void((k, v) priority-queue-builder)) k priority

        ~=[k, v] void(a (k, v) priority-queue-builder, value (k, v) tuple2) k priority

        ~~=[k, v] void(a (k, v) priority-queue-builder, values (k, v) tuple2 array) k priority