/// Immutable arrays: O(1) length and indexing (ADR 0014).
///
/// let a = array.from_list([1, 2, 3])
/// array.get(a, 1) // Some(2)
/// let b = array.set(a, 1, 20) // `a` is unchanged
/// array.to_list(array.push(b, 4)) // [1, 20, 3, 4]
///
/// An array is a value: `set` and `push` return a new array. When the
/// array they get is unique (no other reference to it remains, as with
/// `array.push(acc, x)` in a loop), they change it in place instead of
/// copying it, so building an array with `push` is linear. `==`, `<`,
/// `show`, `debug` and `hash` work on arrays, so types holding arrays can
/// derive them.
import std/int
import std/string
@builtin
pub type Array
/// The empty array.
pub fn empty :: -> Array
{
with_capacity 0
}
/// An empty array with room for `n` elements: pushing that many does not
/// reallocate it.
@extern c "tl_array_with_capacity"
pub fn with_capacity :: n: Int -> Array
@extern c "tl_array_from_list"
pub fn from_list :: items: List -> Array
@extern c "tl_array_to_list"
pub fn to_list :: a: Array -> List
/// The number of elements.
@extern c "tl_array_length"
pub fn length :: a: Array -> Int
/// The element at `index`, if it is in range.
@extern c "tl_array_get"
pub fn get :: a: Array index: Int -> Option
/// `a` with `value` at `index`, which must be in range (panics otherwise).
/// In place when `a` is unique.
@extern c "tl_array_set" owned
pub fn set :: a: Array index: Int value: a -> Array
/// `a` with `value` appended. In place when `a` is unique (it grows by
/// doubling).
@extern c "tl_array_push" owned
pub fn push :: a: Array value: a -> Array
/// The elements from `start` up to `end` (excluded). Both are clamped to
/// `0..length(a)`; the result is empty when `end <= start`.
@extern c "tl_array_slice"
pub fn slice :: a: Array start: Int end: Int -> Array
/// The element at `index`, which the caller keeps in range (panics
/// otherwise).
@extern c "tl_array_at"
fn at :: a: Array index: Int -> a
/// `a` in ascending order. Stable: elements that compare `Eq` keep their
/// original relative order. See [`sort_by`].
pub fn sort :: a: Array -> Array where Ord
{
sort_by a fn x y { compare x y }
}
/// `a` ordered by `compare` (`Lt` means "comes first"). Stable, as `sort`
/// is.
///
/// A driftsort-style stable sort (Bergdoll and Peters, 2024; Rust's
/// `slice::sort`), over the array's own storage:
///
/// - Existing ascending and strictly descending runs are detected, and
/// descending ones reversed in place, so sorted and reversed inputs cost
/// O(n) comparisons.
/// - An unsorted stretch of up to `sqrt(n)` is left alone until its first
/// merge, and sorted then by a stable quicksort: median-of-roughly-
/// `sqrt(n)` pivot selection, and a partition through the scratch array
/// that splits off the elements equal to a repeated pivot (pdqsort-style,
/// for O(n log k) expected comparisons on k distinct values). Past
/// `2 * log2(n)` bad partitions it falls back to a merge sort, keeping
/// the worst case O(n log n).
/// - Sorted runs merge in powersort order (Munro and Wild, 2018) through
/// a scratch array, galloping (exponential, then binary, search) while
/// one side keeps winning.
///
/// The scratch is `n` elements up to a million (8 MB of words, so one
/// quicksort can take the whole input — driftsort's full-buffer policy),
/// `n / 2` past it. O(log n) stack. Sorted in place when `a` is unique;
/// a shared `a` is copied once, by the first update, as with [`set`].
pub fn sort_by :: a: Array compare: fn(a, a) -> Order / -> Array /
{
let n = length a
if n <= insertion_max ()
{
insertion_sort a 0 n compare
}
else
{
driftsort a 0 n False compare
}
}
/// Combine the elements from the first to the last: `f(f(acc, a0), a1)`...
pub fn fold :: a: Array acc: b f: fn(b, a) -> b / -> b /
{
fold_from a 0 acc f
}
fn fold_from :: a: Array i: Int acc: b f: fn(b, a) -> b / -> b /
{
if i < length a
{
fold_from a (i + 1) (f acc (at a i)) f
}
else
{
acc
}
}
/// `f` applied to each element, from the first to the last.
pub fn map :: a: Array f: fn(a) -> b / -> Array /
{
map_into a 0 (with_capacity (length a)) f
}
fn map_into ::
a: Array
i: Int
out: Array
f: fn(a) -> b /
-> Array /
{
if i < length a
{
map_into a (i + 1) (push out (f (at a i))) f
}
else
{
out
}
}
// ---- sorting --------------------------------------------------------------
/// `sort_by` is a plain insertion sort up to here (driftsort's
/// `MAX_LEN_ALWAYS_INSERTION_SORT`).
fn insertion_max :: -> Int
{
20
}
/// The quicksort's base case: ranges of at most this many elements are
/// insertion sorted (driftsort's `SMALL_SORT_GENERAL_THRESHOLD`).
fn small_sort_len :: -> Int
{
32
}
/// One side of a merge must win this many steps in a row before the merge
/// gallops (timsort's `MIN_GALLOP`).
fn gallop_min :: -> Int
{
7
}
fn min_int :: x: Int y: Int -> Int
{
if x < y
{
x
}
else
{
y
}
}
fn max_int :: x: Int y: Int -> Int
{
if x > y
{
x
}
else
{
y
}
}
/// `floor(log2(n))` for `n >= 1`.
fn ilog2 :: n: Int -> Int
{
int.bit_length (int.or n 1) - 1
}
/// Approximately `sqrt(n)`: `2^(ceil(log2(n)) / 2)`, improved by one
/// Newton step (driftsort's `sqrt_approx`).
fn sqrt_approx :: n: Int -> Int
{
let shift = int.bit_length (int.or n 1) / 2
(int.shift_left 1 shift + int.shift_right n shift) / 2
}
/// The length under which a detected run counts as sorted (driftsort's
/// `min_good_run_len`): about `sqrt(n)` — long enough that merging with
/// one pays, short enough that quicksorting an unsorted one is cheap.
fn min_good_run_len :: n: Int -> Int
{
if n <= 4096
{
// Below 64 * 64, `sqrt` would break the detection of fully or nearly
// sorted inputs.
min_int (n - n / 2) 64
}
else
{
sqrt_approx n
}
}
/// `ceil(2^62 / n)`: positions rescaled into fixed-point fractions of the
/// whole array, for [`merge_tree_depth`]. (2^62 is one past the largest
/// small-int literal; the products land past 2^62 and promote to big
/// integers, which is correct and rare enough not to matter.)
fn merge_tree_scale :: n: Int -> Int
{
(4611686018427387903 + 1 + n - 1) / n
}
/// The depth the node merging the runs meeting at `mid` wants in the merge
/// tree (`left` and `right` are the runs' other ends): the leading zeros
/// of the XOR of the scaled midpoints (powersort; Munro and Wild, 2018).
fn merge_tree_depth :: left: Int mid: Int right: Int scale: Int -> Int
{
64 - int.bit_length (int.xor (scale * (left + mid)) (scale * (mid + right)))
}
/// Whether `compare x y` is `Lt`.
fn less :: compare: fn(a, a) -> Order / x: a y: a -> Bool /
{
match compare x y { Lt -> True, _ -> False }
}
/// Insertion sort of `a[lo..hi]`: stable, and the fastest thing there is
/// for the few elements it is given.
fn insertion_sort ::
a: Array
lo: Int
hi: Int
compare: fn(a, a) -> Order /
-> Array /
{
insertion_from a (lo + 1) lo hi compare
}
fn insertion_from ::
a: Array
i: Int
lo: Int
hi: Int
compare: fn(a, a) -> Order /
-> Array /
{
if i >= hi
{
a
}
else
{
let x = at a i
let (a, j) = shift_right a i lo x compare
insertion_from (set a j x) (i + 1) lo hi compare
}
}
/// The elements of `a[lo..j)` greater than `x` shifted one slot right, and
/// the slot `x` belongs in. Strictly-greater keeps equals in their
/// original order (stability).
fn shift_right ::
a: Array
j: Int
lo: Int
x: a
compare: fn(a, a) -> Order /
-> (Array, Int) /
{
if j > lo && less compare x (at a (j - 1))
{
shift_right (set a j (at a (j - 1))) (j - 1) lo x compare
}
else
{
(a, j)
}
}
/// `a[lo..hi)` reversed, in place.
fn reverse_range :: a: Array lo: Int hi: Int -> Array
{
reverse_to a lo (hi - 1)
}
fn reverse_to :: a: Array i: Int j: Int -> Array
{
if i < j
{
let x = at a i
let a = set a i (at a j)
reverse_to (set a j x) (i + 1) (j - 1)
}
else
{
a
}
}
/// The length of the sorted run starting at `lo`, and whether it is
/// strictly descending (strictly, so reversing it cannot swap equal
/// elements).
fn find_run ::
a: Array
lo: Int
hi: Int
compare: fn(a, a) -> Order /
-> (Int, Bool) /
{
if hi - lo < 2
{
(hi - lo, False)
}
else if less compare (at a (lo + 1)) (at a lo)
{
(scan_down a (lo + 2) hi compare - lo, True)
}
else
{
(scan_up a (lo + 2) hi compare - lo, False)
}
}
/// The end of the ascending run `a[lo..]` continues: the first `i` with
/// `a[i] < a[i - 1]`, or `hi`.
fn scan_up ::
a: Array
i: Int
hi: Int
compare: fn(a, a) -> Order /
-> Int /
{
if i < hi && !(less compare (at a i) (at a (i - 1)))
{
scan_up a (i + 1) hi compare
}
else
{
i
}
}
/// The end of the strictly descending run `a[lo..]` continues: the first
/// `i` with `a[i] >= a[i - 1]`, or `hi`.
fn scan_down ::
a: Array
i: Int
hi: Int
compare: fn(a, a) -> Order /
-> Int /
{
if i < hi && less compare (at a i) (at a (i - 1))
{
scan_down a (i + 1) hi compare
}
else
{
i
}
}
/// `scratch` grown to `cap` copies of `x`: the sort writes `scratch` at
/// arbitrary indices, and `set` needs them in range. The copies are
/// overwritten or dropped with `scratch`.
fn prefill :: scratch: Array cap: Int x: a -> Array
{
if length scratch >= cap
{
scratch
}
else
{
prefill (push scratch x) cap x
}
}
/// Driftsort over `a[lo..hi)`: runs created left to right, merged in
/// powersort order; unsorted runs quicksorted lazily at their first
/// physical merge, or at the end. `eager` sorts every made run at once
/// (the quicksort's depth-limit fallback, a O(n log n) merge sort).
fn driftsort ::
a: Array
lo: Int
hi: Int
eager: Bool
compare: fn(a, a) -> Order /
-> Array /
{
let n = hi - lo
// The scratch: big enough that one quicksort can take the whole input
// for small n (driftsort's 8 MB full-buffer policy: values are words),
// half the input past it.
let cap = max_int (n - n / 2) (min_int n 1000000)
let scratch = prefill (with_capacity cap) cap (at a lo)
let (a, _) =
drift_loop
a
scratch
lo
hi
lo
0
True
[]
(merge_tree_scale n)
(min_good_run_len n)
eager
compare
a
}
/// The scan: `a[lo..scan)` is the runs merged so far and the pending run
/// (`prev_len`, `prev_sorted`), `stack` the runs before it with their
/// desired merge depths.
fn drift_loop ::
a: Array
scratch: Array
lo: Int
hi: Int
scan: Int
prev_len: Int
prev_sorted: Bool
stack: List<(Int, Bool, Int)>
scale: Int
min_run: Int
eager: Bool
compare: fn(a, a) -> Order /
-> (Array, Array) /
{
if scan < hi
{
let (run_len, run_sorted, a) = create_run a scan hi min_run eager compare
let depth =
merge_tree_depth
(scan - prev_len - lo)
(scan - lo)
(scan - lo + run_len)
scale
let (a, scratch, prev_len, prev_sorted, stack) =
collapse a scratch scan prev_len prev_sorted stack depth compare
drift_loop
a
scratch
lo
hi
(scan + run_len)
run_len
run_sorted
[(prev_len, prev_sorted, depth), ..stack]
scale
min_run
eager
compare
}
else
{
// A final dummy run with desired depth 0 collapses the whole stack.
let (a, scratch, prev_len, prev_sorted, _) =
collapse a scratch scan prev_len prev_sorted stack 0 compare
if prev_sorted
{
(a, scratch)
}
else
{
stable_quicksort a scratch lo hi compare
}
}
}
/// Merge the stack's top run into the pending run while its desired depth
/// is at least the upcoming node's (`desired`): those merges want to sit
/// deeper in the merge tree.
fn collapse ::
a: Array
scratch: Array
scan: Int
prev_len: Int
prev_sorted: Bool
stack: List<(Int, Bool, Int)>
desired: Int
compare: fn(a, a) -> Order /
-> (Array, Array, Int, Bool, List<(Int, Bool, Int)>) /
{
match stack
{ [ (top_len, top_sorted, top_depth)
, ..rest
] if rest != [] && top_depth >= desired ->
{
let (a, scratch, len, sorted) =
logical_merge
a
scratch
(scan - top_len - prev_len)
top_len
top_sorted
prev_len
prev_sorted
compare
collapse a scratch scan len sorted rest desired compare
}
, _ -> (a, scratch, prev_len, prev_sorted, stack)
}
}
/// The merger of the adjacent runs at `start` (lengths `l_len` and
/// `r_len`). Two unsorted runs that fit in `scratch` together become one
/// bigger unsorted run without a comparison (lazy); anything else is
/// quicksorted as needed and physically merged.
fn logical_merge ::
a: Array
scratch: Array
start: Int
l_len: Int
l_sorted: Bool
r_len: Int
r_sorted: Bool
compare: fn(a, a) -> Order /
-> (Array, Array, Int, Bool) /
{
let total = l_len + r_len
if total <= length scratch && !l_sorted && !r_sorted
{
(a, scratch, total, False)
}
else
{
let (a, scratch) = if l_sorted
{
(a, scratch)
}
else
{
stable_quicksort a scratch start (start + l_len) compare
}
let (a, scratch) = if r_sorted
{
(a, scratch)
}
else
{
stable_quicksort a scratch (start + l_len) (start + total) compare
}
let (a, scratch) =
merge_runs a scratch start (start + l_len) (start + total) compare
(a, scratch, total, True)
}
}
/// The run starting at `lo`: its length, whether it is sorted, and the
/// array (a descending run is reversed in place). An existing run of at
/// least `min_run` is kept; anything shorter is an unsorted run of up to
/// `min_run` (eager: insertion sorted at once).
fn create_run ::
a: Array
lo: Int
hi: Int
min_run: Int
eager: Bool
compare: fn(a, a) -> Order /
-> (Int, Bool, Array) /
{
if hi - lo >= min_run
{
let (run_len, descending) = find_run a lo hi compare
if run_len >= min_run
{
if descending
{
(run_len, True, reverse_range a lo (lo + run_len))
}
else
{
(run_len, True, a)
}
}
else
{
made_run a lo hi min_run eager compare
}
}
else
{
made_run a lo hi min_run eager compare
}
}
fn made_run ::
a: Array
lo: Int
hi: Int
min_run: Int
eager: Bool
compare: fn(a, a) -> Order /
-> (Int, Bool, Array) /
{
if eager
{
let run_end = min_int (lo + small_sort_len ()) hi
(run_end - lo, True, insertion_sort a lo run_end compare)
}
else
{
(min_int min_run (hi - lo), False, a)
}
}
/// Quicksort of `a[lo..hi)` with the depth limit `2 * log2(n)`.
fn stable_quicksort ::
a: Array
scratch: Array
lo: Int
hi: Int
compare: fn(a, a) -> Order /
-> (Array, Array) /
{
quicksort a scratch lo hi (2 * ilog2 (hi - lo)) None compare
}
/// Stable quicksort of `a[lo..hi)` through `scratch`: partition around a
/// sampled pivot, recurse on the right, loop on the left. `ancestor` is
/// the pivot of the partition this range is the right side of, if any: a
/// pivot equal to it instead splits off the elements equal to the pivot
/// (pdqsort's low-cardinality trick), which needs no recursion. Past the
/// depth limit: a merge sort.
fn quicksort ::
a: Array
scratch: Array
lo: Int
hi: Int
limit: Int
ancestor: Option
compare: fn(a, a) -> Order /
-> (Array, Array) /
{
let n = hi - lo
if n <= small_sort_len ()
{
(insertion_sort a lo hi compare, scratch)
}
else if limit <= 0
{
drift_loop
a
scratch
lo
hi
lo
0
True
[]
(merge_tree_scale n)
(min_good_run_len n)
True
compare
}
else
{
let pivot_pos = choose_pivot a lo hi compare
let pivot = at a pivot_pos
let repeated = match ancestor
{ Some(ancestor_pivot) -> !(less compare ancestor_pivot pivot)
, None -> False
}
if repeated
{
let (a, scratch, eq_len) =
partition a scratch lo hi pivot_pos True compare
quicksort a scratch (lo + eq_len) hi (limit - 1) None compare
}
else
{
let (a, scratch, left_len) =
partition a scratch lo hi pivot_pos False compare
if left_len == 0
{
// The pivot is the range's minimum: split off its equals.
let (a, scratch, eq_len) =
partition a scratch lo hi pivot_pos True compare
quicksort a scratch (lo + eq_len) hi (limit - 1) None compare
}
else
{
let (a, scratch) =
quicksort
a
scratch
(lo + left_len)
hi
(limit - 1)
(Some(pivot))
compare
quicksort a scratch lo (lo + left_len) (limit - 1) ancestor compare
}
}
}
}
/// The pivot's index in `a[lo..hi)`: the median of three samples, each the
/// recursive pseudo-median of its third for ranges of 64 or more —
/// approximating the median of `sqrt(n)` samples (glidesort).
fn choose_pivot ::
a: Array
lo: Int
hi: Int
compare: fn(a, a) -> Order /
-> Int /
{
let n = hi - lo
let n8 = n / 8
if n < 64
{
median3 a lo (lo + n8 * 4) (lo + n8 * 7) compare
}
else
{
median3_rec a lo (lo + n8 * 4) (lo + n8 * 7) n8 compare
}
}
fn median3_rec ::
a: Array
x: Int
y: Int
z: Int
n: Int
compare: fn(a, a) -> Order /
-> Int /
{
if n * 8 >= 64
{
let n8 = n / 8
let x = median3_rec a x (x + n8 * 4) (x + n8 * 7) n8 compare
let y = median3_rec a y (y + n8 * 4) (y + n8 * 7) n8 compare
let z = median3_rec a z (z + n8 * 4) (z + n8 * 7) n8 compare
median3 a x y z compare
}
else
{
median3 a x y z compare
}
}
/// The index of the median of `a[x]`, `a[y]`, `a[z]`.
fn median3 ::
a: Array
x: Int
y: Int
z: Int
compare: fn(a, a) -> Order /
-> Int /
{
let xy = less compare (at a x) (at a y)
let xz = less compare (at a x) (at a z)
if xy == xz
{
// `a[x]` is the smallest or the largest: the median is `a[y]` or
// `a[z]`, whichever is closer to it.
let yz = less compare (at a y) (at a z)
if yz != xy
{
z
}
else
{
y
}
}
else
{
x
}
}
/// Stable partition of `a[lo..hi)` around the pivot `a[pivot_pos]` through
/// `scratch`, returning the left side's length. In less mode the left side
/// is the elements `<` the pivot and the pivot joins the right; in equal
/// mode the left side is the elements `<=` the pivot, the pivot included
/// (called when the pivot is a known minimum or a repeated one, so that
/// side is exactly its equals). Both sides keep their original order: the
/// right is written into `scratch` backwards and the copy back reverses it
/// again.
fn partition ::
a: Array
scratch: Array
lo: Int
hi: Int
pivot_pos: Int
equal_mode: Bool
compare: fn(a, a) -> Order /
-> (Array, Array, Int) /
{
let pivot = at a pivot_pos
let (scratch, left, right) =
partition_scan
a
scratch
lo
hi
pivot_pos
pivot
equal_mode
0
(hi - lo)
compare
let a = copy_forward a scratch 0 left lo
let a = copy_reversed a scratch right (hi - lo) (lo + left)
(a, scratch, left)
}
/// The scan of [`partition`]: `left` is the next slot on `scratch`'s left
/// side, `right` one past the next slot on its right side (filled
/// backwards from `hi - lo`): both relative to `lo`, so any subslice fits
/// in `scratch`.
fn partition_scan ::
a: Array
scratch: Array
i: Int
hi: Int
pivot_pos: Int
pivot: a
equal_mode: Bool
left: Int
right: Int
compare: fn(a, a) -> Order /
-> (Array, Int, Int) /
{
if i >= hi
{
(scratch, left, right)
}
else
{
// The pivot is placed, not compared (a comparison of it with itself
// could lie), at its scan turn: it stays among its equals where it
// was.
if i == pivot_pos
{
if equal_mode
{
partition_scan
a
(set scratch left pivot)
(i + 1)
hi
pivot_pos
pivot
equal_mode
(left + 1)
right
compare
}
else
{
partition_scan
a
(set scratch (right - 1) pivot)
(i + 1)
hi
pivot_pos
pivot
equal_mode
left
(right - 1)
compare
}
}
else
{
let x = at a i
let goes_left = if equal_mode
{
!(less compare pivot x)
}
else
{
less compare x pivot
}
if goes_left
{
partition_scan
a
(set scratch left x)
(i + 1)
hi
pivot_pos
pivot
equal_mode
(left + 1)
right
compare
}
else
{
partition_scan
a
(set scratch (right - 1) x)
(i + 1)
hi
pivot_pos
pivot
equal_mode
left
(right - 1)
compare
}
}
}
}
/// `src[from..to)` copied into `dst` at `out`.
fn copy_forward ::
dst: Array
src: Array
from: Int
to: Int
out: Int
-> Array
{
if from >= to
{
dst
}
else
{
copy_forward (set dst out (at src from)) src (from + 1) to (out + 1)
}
}
/// `src[from..to)` copied into `dst` at `out`, reversed (`dst` gets
/// `src[to - 1]`, then `src[to - 2]`, ...): how [`partition`]'s
/// backwards-written right side comes back in its original order.
fn copy_reversed ::
dst: Array
src: Array
from: Int
to: Int
out: Int
-> Array
{
if to <= from
{
dst
}
else
{
copy_reversed (set dst out (at src (to - 1))) src from (to - 1) (out + 1)
}
}
/// `a[from..to)` moved forwards to start at `out`. The target must be
/// before the source. (One array parameter: passing `a` as both `dst` and
/// `src` of `copy_forward` would share it, and `set` would copy.)
fn move_forward :: a: Array from: Int to: Int out: Int -> Array
{
if from >= to
{
a
}
else
{
move_forward (set a out (at a from)) (from + 1) to (out + 1)
}
}
/// `a[from..to)` moved backwards to end at `out` (included). The target
/// must be past the source. (One array parameter: passing `a` as both
/// `dst` and `src` of `copy_down` would share it, and `set` would copy.)
fn move_down :: a: Array from: Int to: Int out: Int -> Array
{
if to <= from
{
a
}
else
{
move_down (set a out (at a (to - 1))) from (to - 1) (out - 1)
}
}
/// `src[from..to)` copied into `dst` backwards, ending at `out`
/// (included). Safe with `dst == src` when the target is past the source.
fn copy_down ::
dst: Array
src: Array
from: Int
to: Int
out: Int
-> Array
{
if to <= from
{
dst
}
else
{
copy_down (set dst out (at src (to - 1))) src from (to - 1) (out - 1)
}
}
/// The merger of the sorted runs `a[lo..mid)` and `a[mid..hi)`, through
/// `scratch`.
fn merge_runs ::
a: Array
scratch: Array
lo: Int
mid: Int
hi: Int
compare: fn(a, a) -> Order /
-> (Array, Array) /
{
let left_len = mid - lo
let right_len = hi - mid
if left_len == 0 || right_len == 0
{
(a, scratch)
}
else if !(less compare (at a mid) (at a (mid - 1)))
{
// Already in order across the boundary.
(a, scratch)
}
else if left_len <= right_len
{
let scratch = fill_scratch a scratch lo 0 left_len
merge_up_pair a scratch lo 0 left_len mid hi 0 (gallop_min ()) compare
}
else
{
let scratch = fill_scratch a scratch mid 0 right_len
merge_down_pair
a
scratch
(hi - 1)
(mid - 1)
lo
(right_len - 1)
0
(gallop_min ())
compare
}
}
/// `a[from..from + len)` copied over `scratch[0..len)`.
fn fill_scratch ::
a: Array
scratch: Array
from: Int
k: Int
len: Int
-> Array
{
if k >= len
{
scratch
}
else
{
fill_scratch a (set scratch k (at a (from + k))) from (k + 1) len
}
}
/// An up-merge's pairwise half: `scratch[0..left_len)` (the left run) and
/// `a[j..hi)` (the right) merged into `a[out..]`. Equal elements take the
/// left's (stability). `streak` counts one side's consecutive wins
/// (positive: the left's); past `min_gallop` of them the merge gallops.
fn merge_up_pair ::
a: Array
scratch: Array
out: Int
i: Int
left_len: Int
j: Int
hi: Int
streak: Int
min_gallop: Int
compare: fn(a, a) -> Order /
-> (Array, Array) /
{
if i >= left_len
{
// The left run is spent; the right's rest is in place.
(a, scratch)
}
else if j >= hi
{
(copy_forward a scratch i left_len out, scratch)
}
else if less compare (at a j) (at scratch i)
{
let a = set a out (at a j)
let streak = if streak < 0 { streak - 1 } else { 0 - 1 }
if 0 - streak >= min_gallop
{
merge_up_gallop
a
scratch
(out + 1)
i
left_len
(j + 1)
hi
min_gallop
compare
}
else
{
merge_up_pair
a
scratch
(out + 1)
i
left_len
(j + 1)
hi
streak
min_gallop
compare
}
}
else
{
let a = set a out (at scratch i)
let streak = if streak > 0 { streak + 1 } else { 1 }
if streak >= min_gallop
{
merge_up_gallop
a
scratch
(out + 1)
(i + 1)
left_len
j
hi
min_gallop
compare
}
else
{
merge_up_pair
a
scratch
(out + 1)
(i + 1)
left_len
j
hi
streak
min_gallop
compare
}
}
}
/// An up-merge's galloping half: the losing side's next stretch is found
/// by exponential, then binary, search and copied without per-element
/// comparisons, until both stretches come up short (then back to
/// [`merge_up_pair`], with a raised `min_gallop`). Alternates: the left
/// run's elements `<=` the right's head, then the right run's elements
/// `<` the left's head (timsort's `merge_lo`; the strict/non-strict
/// split is what keeps equal elements in their original order).
fn merge_up_gallop ::
a: Array
scratch: Array
out: Int
i: Int
left_len: Int
j: Int
hi: Int
min_gallop: Int
compare: fn(a, a) -> Order /
-> (Array, Array) /
{
if i >= left_len
{
(a, scratch)
}
else if j >= hi
{
(copy_forward a scratch i left_len out, scratch)
}
else
{
// The left run's elements `<= a[j]` come first (stability).
let count = gallop_right scratch (at a j) i (left_len - i) compare
let a = copy_forward a scratch i (i + count) out
let i = i + count
let out = out + count
if i >= left_len
{
(a, scratch)
}
else
{
let a = set a out (at a j)
let j = j + 1
let out = out + 1
if j >= hi
{
(copy_forward a scratch i left_len out, scratch)
}
else
{
// The right run's elements `< scratch[i]` come first.
let count2 = gallop_left a (at scratch i) j (hi - j) compare
let a = move_forward a j (j + count2) out
let j = j + count2
let out = out + count2
if j >= hi
{
(copy_forward a scratch i left_len out, scratch)
}
else
{
let a = set a out (at scratch i)
let i = i + 1
let out = out + 1
let min_gallop = if min_gallop > 1 { min_gallop - 1 } else { 1 }
if count < gallop_min () && count2 < gallop_min ()
{
merge_up_pair
a
scratch
out
i
left_len
j
hi
0
(min_gallop + 2)
compare
}
else
{
merge_up_gallop a scratch out i left_len j hi min_gallop compare
}
}
}
}
}
}
/// A down-merge's pairwise half: `a[lo..=i]` (the left run) and
/// `scratch[0..=j]` (the right) merged into `a[..=out]`, from the back.
/// Equal elements take the right's (stability, from the back).
fn merge_down_pair ::
a: Array
scratch: Array
out: Int
i: Int
lo: Int
j: Int
streak: Int
min_gallop: Int
compare: fn(a, a) -> Order /
-> (Array, Array) /
{
if j < 0
{
// The right run is spent; the left's rest is in place.
(a, scratch)
}
else if i < lo
{
(copy_forward a scratch 0 (j + 1) lo, scratch)
}
else if less compare (at scratch j) (at a i)
{
let a = set a out (at a i)
let streak = if streak < 0 { streak - 1 } else { 0 - 1 }
if False
{
merge_down_gallop a scratch (out - 1) (i - 1) lo j min_gallop compare
}
else
{
merge_down_pair a scratch (out - 1) (i - 1) lo j streak min_gallop compare
}
}
else
{
let a = set a out (at scratch j)
let streak = if streak > 0 { streak + 1 } else { 1 }
if False
{
merge_down_gallop a scratch (out - 1) i lo (j - 1) min_gallop compare
}
else
{
merge_down_pair a scratch (out - 1) i lo (j - 1) streak min_gallop compare
}
}
}
/// A down-merge's galloping half (see [`merge_up_gallop`]).
fn merge_down_gallop ::
a: Array
scratch: Array
out: Int
i: Int
lo: Int
j: Int
min_gallop: Int
compare: fn(a, a) -> Order /
-> (Array, Array) /
{
if j < 0
{
(a, scratch)
}
else if i < lo
{
(copy_forward a scratch 0 (j + 1) lo, scratch)
}
else
{
// The left run's elements `> scratch[j]` go to the back.
let count = gallop_right a (at scratch j) lo (i - lo + 1) compare
let bulk = i - lo + 1 - count
let a = move_down a (lo + count) (i + 1) out
let i = i - bulk
let out = out - bulk
if i < lo
{
(copy_forward a scratch 0 (j + 1) lo, scratch)
}
else
{
let a = set a out (at scratch j)
let j = j - 1
let out = out - 1
if j < 0
{
(a, scratch)
}
else
{
// The right run's elements `>= a[i]` go to the back.
let count2 = gallop_left scratch (at a i) 0 (j + 1) compare
let bulk2 = j + 1 - count2
let a = copy_down a scratch count2 (j + 1) out
let j = j - bulk2
let out = out - bulk2
if j < 0
{
(a, scratch)
}
else
{
let a = set a out (at a i)
let i = i - 1
let out = out - 1
let min_gallop = if min_gallop > 1 { min_gallop - 1 } else { 1 }
if count < gallop_min () && count2 < gallop_min ()
{
merge_down_pair a scratch out i lo j 0 (min_gallop + 2) compare
}
else
{
merge_down_gallop a scratch out i lo j min_gallop compare
}
}
}
}
}
}
/// How many of `arr[base..base + n)` are `<= key`: the upper bound, so
/// equal elements sort before `key`. Exponential search, then binary.
fn gallop_right ::
arr: Array
key: a
base: Int
n: Int
compare: fn(a, a) -> Order /
-> Int /
{
if n <= 0 || less compare key (at arr base)
{
0
}
else
{
let (lo, hi) = gallop_right_probe arr key base n 0 1 compare
gallop_right_finish arr key base lo hi compare
}
}
/// The probe range for [`gallop_right`]: `arr[base + lo] <= key`, and
/// `probe` past the answer or past the end.
fn gallop_right_probe ::
arr: Array
key: a
base: Int
n: Int
lo: Int
ofs: Int
compare: fn(a, a) -> Order /
-> (Int, Int) /
{
let probe = lo + ofs
if probe < n && !(less compare key (at arr (base + probe)))
{
gallop_right_probe arr key base n probe (ofs * 2) compare
}
else
{
(lo, min_int probe (n - 1))
}
}
/// The binary search: the last index in `[lo, hi]` with
/// `arr[base + ..] <= key`, plus one.
fn gallop_right_finish ::
arr: Array
key: a
base: Int
lo: Int
hi: Int
compare: fn(a, a) -> Order /
-> Int /
{
if lo >= hi
{
lo + 1
}
else
{
let mid = (lo + hi + 1) / 2
if less compare key (at arr (base + mid))
{
gallop_right_finish arr key base lo (mid - 1) compare
}
else
{
gallop_right_finish arr key base mid hi compare
}
}
}
/// How many of `arr[base..base + n)` are `< key`: the lower bound, so
/// equal elements sort after `key`. Exponential search, then binary.
fn gallop_left ::
arr: Array
key: a
base: Int
n: Int
compare: fn(a, a) -> Order /
-> Int /
{
if n <= 0 || !(less compare (at arr base) key)
{
0
}
else
{
let (lo, hi) = gallop_left_probe arr key base n 0 1 compare
gallop_left_finish arr key base lo hi compare
}
}
/// The probe range for [`gallop_left`]: `arr[base + lo] < key`, and
/// `probe` past the answer or past the end.
fn gallop_left_probe ::
arr: Array
key: a
base: Int
n: Int
lo: Int
ofs: Int
compare: fn(a, a) -> Order /
-> (Int, Int) /
{
let probe = lo + ofs
if probe < n && less compare (at arr (base + probe)) key
{
gallop_left_probe arr key base n probe (ofs * 2) compare
}
else
{
(lo, min_int probe (n - 1))
}
}
/// The binary search: the last index in `[lo, hi]` with
/// `arr[base + ..] < key`, plus one.
fn gallop_left_finish ::
arr: Array
key: a
base: Int
lo: Int
hi: Int
compare: fn(a, a) -> Order /
-> Int /
{
if lo >= hi
{
lo + 1
}
else
{
let mid = (lo + hi + 1) / 2
if less compare (at arr (base + mid)) key
{
gallop_left_finish arr key base mid hi compare
}
else
{
gallop_left_finish arr key base lo (mid - 1) compare
}
}
}
impl Eq> where Eq
{
fn eq :: x y
{
length x == length y && equal_from x y 0
}
}
fn equal_from :: x y i
{
if i < length x
{
at x i == at y i && equal_from x y (i + 1)
}
else
{
True
}
}
/// Lexicographic, as for lists: a prefix is smaller.
impl Ord> where Ord
{
fn compare :: x y
{
compare_from x y 0
}
}
fn compare_from :: x y i
{
if i >= length x
{
if i >= length y
{
Eq
}
else
{
Lt
}
}
else if i >= length y
{
Gt
}
else
{
match compare (at x i) (at y i)
{ Eq -> compare_from x y (i + 1), other -> other }
}
}
/// `[1, 2, 3]`, as for lists.
impl Show> where Show
{
fn show :: x
{
"[" <> string.join (to_list (map x (show _))) ", " <> "]"
}
}
impl Debug> where Debug
{
fn debug :: x
{
"[" <> string.join (to_list (map x (debug _))) ", " <> "]"
}
}
impl Hash> where Hash
{
fn hash :: x
{
fold x 7 fn acc v { hash_combine acc (hash v) }
}
}