tobogganSe connecter

louise

The Louise language: compiler, runtime, std, tooling

Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.

1615 lignes · 35551 octetsBrut · Historique
1/// Immutable arrays: O(1) length and indexing (ADR 0014).
2///
3/// let a = array.from_list([1, 2, 3])
4/// array.get(a, 1) // Some(2)
5/// let b = array.set(a, 1, 20) // `a` is unchanged
6/// array.to_list(array.push(b, 4)) // [1, 20, 3, 4]
7///
8/// An array is a value: `set` and `push` return a new array. When the
9/// array they get is unique (no other reference to it remains, as with
10/// `array.push(acc, x)` in a loop), they change it in place instead of
11/// copying it, so building an array with `push` is linear. `==`, `<`,
12/// `show`, `debug` and `hash` work on arrays, so types holding arrays can
13/// derive them.
14
15import std/int
16import std/string
17
18@builtin
19pub type Array<a>
20
21/// The empty array.
22pub fn empty :: -> Array<a>
23{
24 with_capacity 0
25}
26
27/// An empty array with room for `n` elements: pushing that many does not
28/// reallocate it.
29@extern c "tl_array_with_capacity"
30pub fn with_capacity :: n: Int -> Array<a>
31
32@extern c "tl_array_from_list"
33pub fn from_list :: items: List<a> -> Array<a>
34
35@extern c "tl_array_to_list"
36pub fn to_list :: a: Array<a> -> List<a>
37
38/// The number of elements.
39@extern c "tl_array_length"
40pub fn length :: a: Array<a> -> Int
41
42/// The element at `index`, if it is in range.
43@extern c "tl_array_get"
44pub fn get :: a: Array<a> index: Int -> Option<a>
45
46/// `a` with `value` at `index`, which must be in range (panics otherwise).
47/// In place when `a` is unique.
48@extern c "tl_array_set" owned
49pub fn set :: a: Array<a> index: Int value: a -> Array<a>
50
51/// `a` with `value` appended. In place when `a` is unique (it grows by
52/// doubling).
53@extern c "tl_array_push" owned
54pub fn push :: a: Array<a> value: a -> Array<a>
55
56/// The elements from `start` up to `end` (excluded). Both are clamped to
57/// `0..length(a)`; the result is empty when `end <= start`.
58@extern c "tl_array_slice"
59pub fn slice :: a: Array<a> start: Int end: Int -> Array<a>
60
61/// The element at `index`, which the caller keeps in range (panics
62/// otherwise).
63@extern c "tl_array_at"
64fn at :: a: Array<a> index: Int -> a
65
66/// `a` in ascending order. Stable: elements that compare `Eq` keep their
67/// original relative order. See [`sort_by`].
68pub fn sort :: a: Array<a> -> Array<a> where Ord<a>
69{
70 sort_by a fn x y { compare x y }
71}
72
73/// `a` ordered by `compare` (`Lt` means "comes first"). Stable, as `sort`
74/// is.
75///
76/// A driftsort-style stable sort (Bergdoll and Peters, 2024; Rust's
77/// `slice::sort`), over the array's own storage:
78///
79/// - Existing ascending and strictly descending runs are detected, and
80/// descending ones reversed in place, so sorted and reversed inputs cost
81/// O(n) comparisons.
82/// - An unsorted stretch of up to `sqrt(n)` is left alone until its first
83/// merge, and sorted then by a stable quicksort: median-of-roughly-
84/// `sqrt(n)` pivot selection, and a partition through the scratch array
85/// that splits off the elements equal to a repeated pivot (pdqsort-style,
86/// for O(n log k) expected comparisons on k distinct values). Past
87/// `2 * log2(n)` bad partitions it falls back to a merge sort, keeping
88/// the worst case O(n log n).
89/// - Sorted runs merge in powersort order (Munro and Wild, 2018) through
90/// a scratch array, galloping (exponential, then binary, search) while
91/// one side keeps winning.
92///
93/// The scratch is `n` elements up to a million (8 MB of words, so one
94/// quicksort can take the whole input — driftsort's full-buffer policy),
95/// `n / 2` past it. O(log n) stack. Sorted in place when `a` is unique;
96/// a shared `a` is copied once, by the first update, as with [`set`].
97pub fn sort_by :: a: Array<a> compare: fn(a, a) -> Order / <e> -> Array<a> / <e>
98{
99 let n = length a
100 if n <= insertion_max ()
101 {
102 insertion_sort a 0 n compare
103 }
104 else
105 {
106 driftsort a 0 n False compare
107 }
108}
109
110/// Combine the elements from the first to the last: `f(f(acc, a0), a1)`...
111pub fn fold :: a: Array<a> acc: b f: fn(b, a) -> b / <e> -> b / <e>
112{
113 fold_from a 0 acc f
114}
115
116fn fold_from :: a: Array<a> i: Int acc: b f: fn(b, a) -> b / <e> -> b / <e>
117{
118 if i < length a
119 {
120 fold_from a (i + 1) (f acc (at a i)) f
121 }
122 else
123 {
124 acc
125 }
126}
127
128/// `f` applied to each element, from the first to the last.
129pub fn map :: a: Array<a> f: fn(a) -> b / <e> -> Array<b> / <e>
130{
131 map_into a 0 (with_capacity (length a)) f
132}
133
134fn map_into ::
135 a: Array<a>
136 i: Int
137 out: Array<b>
138 f: fn(a) -> b / <e>
139 -> Array<b> / <e>
140{
141 if i < length a
142 {
143 map_into a (i + 1) (push out (f (at a i))) f
144 }
145 else
146 {
147 out
148 }
149}
150
151// ---- sorting --------------------------------------------------------------
152
153/// `sort_by` is a plain insertion sort up to here (driftsort's
154/// `MAX_LEN_ALWAYS_INSERTION_SORT`).
155fn insertion_max :: -> Int
156{
157 20
158}
159
160/// The quicksort's base case: ranges of at most this many elements are
161/// insertion sorted (driftsort's `SMALL_SORT_GENERAL_THRESHOLD`).
162fn small_sort_len :: -> Int
163{
164 32
165}
166
167/// One side of a merge must win this many steps in a row before the merge
168/// gallops (timsort's `MIN_GALLOP`).
169fn gallop_min :: -> Int
170{
171 7
172}
173
174fn min_int :: x: Int y: Int -> Int
175{
176 if x < y
177 {
178 x
179 }
180 else
181 {
182 y
183 }
184}
185
186fn max_int :: x: Int y: Int -> Int
187{
188 if x > y
189 {
190 x
191 }
192 else
193 {
194 y
195 }
196}
197
198/// `floor(log2(n))` for `n >= 1`.
199fn ilog2 :: n: Int -> Int
200{
201 int.bit_length (int.or n 1) - 1
202}
203
204/// Approximately `sqrt(n)`: `2^(ceil(log2(n)) / 2)`, improved by one
205/// Newton step (driftsort's `sqrt_approx`).
206fn sqrt_approx :: n: Int -> Int
207{
208 let shift = int.bit_length (int.or n 1) / 2
209 (int.shift_left 1 shift + int.shift_right n shift) / 2
210}
211
212/// The length under which a detected run counts as sorted (driftsort's
213/// `min_good_run_len`): about `sqrt(n)` — long enough that merging with
214/// one pays, short enough that quicksorting an unsorted one is cheap.
215fn min_good_run_len :: n: Int -> Int
216{
217 if n <= 4096
218 {
219 // Below 64 * 64, `sqrt` would break the detection of fully or nearly
220 // sorted inputs.
221 min_int (n - n / 2) 64
222 }
223 else
224 {
225 sqrt_approx n
226 }
227}
228
229/// `ceil(2^62 / n)`: positions rescaled into fixed-point fractions of the
230/// whole array, for [`merge_tree_depth`]. (2^62 is one past the largest
231/// small-int literal; the products land past 2^62 and promote to big
232/// integers, which is correct and rare enough not to matter.)
233fn merge_tree_scale :: n: Int -> Int
234{
235 (4611686018427387903 + 1 + n - 1) / n
236}
237
238/// The depth the node merging the runs meeting at `mid` wants in the merge
239/// tree (`left` and `right` are the runs' other ends): the leading zeros
240/// of the XOR of the scaled midpoints (powersort; Munro and Wild, 2018).
241fn merge_tree_depth :: left: Int mid: Int right: Int scale: Int -> Int
242{
243 64 - int.bit_length (int.xor (scale * (left + mid)) (scale * (mid + right)))
244}
245
246/// Whether `compare x y` is `Lt`.
247fn less :: compare: fn(a, a) -> Order / <e> x: a y: a -> Bool / <e>
248{
249 match compare x y { Lt -> True, _ -> False }
250}
251
252/// Insertion sort of `a[lo..hi]`: stable, and the fastest thing there is
253/// for the few elements it is given.
254fn insertion_sort ::
255 a: Array<a>
256 lo: Int
257 hi: Int
258 compare: fn(a, a) -> Order / <e>
259 -> Array<a> / <e>
260{
261 insertion_from a (lo + 1) lo hi compare
262}
263
264fn insertion_from ::
265 a: Array<a>
266 i: Int
267 lo: Int
268 hi: Int
269 compare: fn(a, a) -> Order / <e>
270 -> Array<a> / <e>
271{
272 if i >= hi
273 {
274 a
275 }
276 else
277 {
278 let x = at a i
279 let (a, j) = shift_right a i lo x compare
280 insertion_from (set a j x) (i + 1) lo hi compare
281 }
282}
283
284/// The elements of `a[lo..j)` greater than `x` shifted one slot right, and
285/// the slot `x` belongs in. Strictly-greater keeps equals in their
286/// original order (stability).
287fn shift_right ::
288 a: Array<a>
289 j: Int
290 lo: Int
291 x: a
292 compare: fn(a, a) -> Order / <e>
293 -> (Array<a>, Int) / <e>
294{
295 if j > lo && less compare x (at a (j - 1))
296 {
297 shift_right (set a j (at a (j - 1))) (j - 1) lo x compare
298 }
299 else
300 {
301 (a, j)
302 }
303}
304
305/// `a[lo..hi)` reversed, in place.
306fn reverse_range :: a: Array<a> lo: Int hi: Int -> Array<a>
307{
308 reverse_to a lo (hi - 1)
309}
310
311fn reverse_to :: a: Array<a> i: Int j: Int -> Array<a>
312{
313 if i < j
314 {
315 let x = at a i
316 let a = set a i (at a j)
317 reverse_to (set a j x) (i + 1) (j - 1)
318 }
319 else
320 {
321 a
322 }
323}
324
325/// The length of the sorted run starting at `lo`, and whether it is
326/// strictly descending (strictly, so reversing it cannot swap equal
327/// elements).
328fn find_run ::
329 a: Array<a>
330 lo: Int
331 hi: Int
332 compare: fn(a, a) -> Order / <e>
333 -> (Int, Bool) / <e>
334{
335 if hi - lo < 2
336 {
337 (hi - lo, False)
338 }
339 else if less compare (at a (lo + 1)) (at a lo)
340 {
341 (scan_down a (lo + 2) hi compare - lo, True)
342 }
343 else
344 {
345 (scan_up a (lo + 2) hi compare - lo, False)
346 }
347}
348
349/// The end of the ascending run `a[lo..]` continues: the first `i` with
350/// `a[i] < a[i - 1]`, or `hi`.
351fn scan_up ::
352 a: Array<a>
353 i: Int
354 hi: Int
355 compare: fn(a, a) -> Order / <e>
356 -> Int / <e>
357{
358 if i < hi && !(less compare (at a i) (at a (i - 1)))
359 {
360 scan_up a (i + 1) hi compare
361 }
362 else
363 {
364 i
365 }
366}
367
368/// The end of the strictly descending run `a[lo..]` continues: the first
369/// `i` with `a[i] >= a[i - 1]`, or `hi`.
370fn scan_down ::
371 a: Array<a>
372 i: Int
373 hi: Int
374 compare: fn(a, a) -> Order / <e>
375 -> Int / <e>
376{
377 if i < hi && less compare (at a i) (at a (i - 1))
378 {
379 scan_down a (i + 1) hi compare
380 }
381 else
382 {
383 i
384 }
385}
386
387/// `scratch` grown to `cap` copies of `x`: the sort writes `scratch` at
388/// arbitrary indices, and `set` needs them in range. The copies are
389/// overwritten or dropped with `scratch`.
390fn prefill :: scratch: Array<a> cap: Int x: a -> Array<a>
391{
392 if length scratch >= cap
393 {
394 scratch
395 }
396 else
397 {
398 prefill (push scratch x) cap x
399 }
400}
401
402/// Driftsort over `a[lo..hi)`: runs created left to right, merged in
403/// powersort order; unsorted runs quicksorted lazily at their first
404/// physical merge, or at the end. `eager` sorts every made run at once
405/// (the quicksort's depth-limit fallback, a O(n log n) merge sort).
406fn driftsort ::
407 a: Array<a>
408 lo: Int
409 hi: Int
410 eager: Bool
411 compare: fn(a, a) -> Order / <e>
412 -> Array<a> / <e>
413{
414 let n = hi - lo
415 // The scratch: big enough that one quicksort can take the whole input
416 // for small n (driftsort's 8 MB full-buffer policy: values are words),
417 // half the input past it.
418 let cap = max_int (n - n / 2) (min_int n 1000000)
419 let scratch = prefill (with_capacity cap) cap (at a lo)
420 let (a, _) =
421 drift_loop
422 a
423 scratch
424 lo
425 hi
426 lo
427 0
428 True
429 []
430 (merge_tree_scale n)
431 (min_good_run_len n)
432 eager
433 compare
434 a
435}
436
437/// The scan: `a[lo..scan)` is the runs merged so far and the pending run
438/// (`prev_len`, `prev_sorted`), `stack` the runs before it with their
439/// desired merge depths.
440fn drift_loop ::
441 a: Array<a>
442 scratch: Array<a>
443 lo: Int
444 hi: Int
445 scan: Int
446 prev_len: Int
447 prev_sorted: Bool
448 stack: List<(Int, Bool, Int)>
449 scale: Int
450 min_run: Int
451 eager: Bool
452 compare: fn(a, a) -> Order / <e>
453 -> (Array<a>, Array<a>) / <e>
454{
455 if scan < hi
456 {
457 let (run_len, run_sorted, a) = create_run a scan hi min_run eager compare
458 let depth =
459 merge_tree_depth
460 (scan - prev_len - lo)
461 (scan - lo)
462 (scan - lo + run_len)
463 scale
464 let (a, scratch, prev_len, prev_sorted, stack) =
465 collapse a scratch scan prev_len prev_sorted stack depth compare
466 drift_loop
467 a
468 scratch
469 lo
470 hi
471 (scan + run_len)
472 run_len
473 run_sorted
474 [(prev_len, prev_sorted, depth), ..stack]
475 scale
476 min_run
477 eager
478 compare
479 }
480 else
481 {
482 // A final dummy run with desired depth 0 collapses the whole stack.
483 let (a, scratch, prev_len, prev_sorted, _) =
484 collapse a scratch scan prev_len prev_sorted stack 0 compare
485 if prev_sorted
486 {
487 (a, scratch)
488 }
489 else
490 {
491 stable_quicksort a scratch lo hi compare
492 }
493 }
494}
495
496/// Merge the stack's top run into the pending run while its desired depth
497/// is at least the upcoming node's (`desired`): those merges want to sit
498/// deeper in the merge tree.
499fn collapse ::
500 a: Array<a>
501 scratch: Array<a>
502 scan: Int
503 prev_len: Int
504 prev_sorted: Bool
505 stack: List<(Int, Bool, Int)>
506 desired: Int
507 compare: fn(a, a) -> Order / <e>
508 -> (Array<a>, Array<a>, Int, Bool, List<(Int, Bool, Int)>) / <e>
509{
510 match stack
511 { [ (top_len, top_sorted, top_depth)
512 , ..rest
513 ] if rest != [] && top_depth >= desired ->
514 {
515 let (a, scratch, len, sorted) =
516 logical_merge
517 a
518 scratch
519 (scan - top_len - prev_len)
520 top_len
521 top_sorted
522 prev_len
523 prev_sorted
524 compare
525 collapse a scratch scan len sorted rest desired compare
526 }
527 , _ -> (a, scratch, prev_len, prev_sorted, stack)
528 }
529}
530
531/// The merger of the adjacent runs at `start` (lengths `l_len` and
532/// `r_len`). Two unsorted runs that fit in `scratch` together become one
533/// bigger unsorted run without a comparison (lazy); anything else is
534/// quicksorted as needed and physically merged.
535fn logical_merge ::
536 a: Array<a>
537 scratch: Array<a>
538 start: Int
539 l_len: Int
540 l_sorted: Bool
541 r_len: Int
542 r_sorted: Bool
543 compare: fn(a, a) -> Order / <e>
544 -> (Array<a>, Array<a>, Int, Bool) / <e>
545{
546 let total = l_len + r_len
547 if total <= length scratch && !l_sorted && !r_sorted
548 {
549 (a, scratch, total, False)
550 }
551 else
552 {
553 let (a, scratch) = if l_sorted
554 {
555 (a, scratch)
556 }
557 else
558 {
559 stable_quicksort a scratch start (start + l_len) compare
560 }
561 let (a, scratch) = if r_sorted
562 {
563 (a, scratch)
564 }
565 else
566 {
567 stable_quicksort a scratch (start + l_len) (start + total) compare
568 }
569 let (a, scratch) =
570 merge_runs a scratch start (start + l_len) (start + total) compare
571 (a, scratch, total, True)
572 }
573}
574
575/// The run starting at `lo`: its length, whether it is sorted, and the
576/// array (a descending run is reversed in place). An existing run of at
577/// least `min_run` is kept; anything shorter is an unsorted run of up to
578/// `min_run` (eager: insertion sorted at once).
579fn create_run ::
580 a: Array<a>
581 lo: Int
582 hi: Int
583 min_run: Int
584 eager: Bool
585 compare: fn(a, a) -> Order / <e>
586 -> (Int, Bool, Array<a>) / <e>
587{
588 if hi - lo >= min_run
589 {
590 let (run_len, descending) = find_run a lo hi compare
591 if run_len >= min_run
592 {
593 if descending
594 {
595 (run_len, True, reverse_range a lo (lo + run_len))
596 }
597 else
598 {
599 (run_len, True, a)
600 }
601 }
602 else
603 {
604 made_run a lo hi min_run eager compare
605 }
606 }
607 else
608 {
609 made_run a lo hi min_run eager compare
610 }
611}
612
613fn made_run ::
614 a: Array<a>
615 lo: Int
616 hi: Int
617 min_run: Int
618 eager: Bool
619 compare: fn(a, a) -> Order / <e>
620 -> (Int, Bool, Array<a>) / <e>
621{
622 if eager
623 {
624 let run_end = min_int (lo + small_sort_len ()) hi
625 (run_end - lo, True, insertion_sort a lo run_end compare)
626 }
627 else
628 {
629 (min_int min_run (hi - lo), False, a)
630 }
631}
632
633/// Quicksort of `a[lo..hi)` with the depth limit `2 * log2(n)`.
634fn stable_quicksort ::
635 a: Array<a>
636 scratch: Array<a>
637 lo: Int
638 hi: Int
639 compare: fn(a, a) -> Order / <e>
640 -> (Array<a>, Array<a>) / <e>
641{
642 quicksort a scratch lo hi (2 * ilog2 (hi - lo)) None compare
643}
644
645/// Stable quicksort of `a[lo..hi)` through `scratch`: partition around a
646/// sampled pivot, recurse on the right, loop on the left. `ancestor` is
647/// the pivot of the partition this range is the right side of, if any: a
648/// pivot equal to it instead splits off the elements equal to the pivot
649/// (pdqsort's low-cardinality trick), which needs no recursion. Past the
650/// depth limit: a merge sort.
651fn quicksort ::
652 a: Array<a>
653 scratch: Array<a>
654 lo: Int
655 hi: Int
656 limit: Int
657 ancestor: Option<a>
658 compare: fn(a, a) -> Order / <e>
659 -> (Array<a>, Array<a>) / <e>
660{
661 let n = hi - lo
662 if n <= small_sort_len ()
663 {
664 (insertion_sort a lo hi compare, scratch)
665 }
666 else if limit <= 0
667 {
668 drift_loop
669 a
670 scratch
671 lo
672 hi
673 lo
674 0
675 True
676 []
677 (merge_tree_scale n)
678 (min_good_run_len n)
679 True
680 compare
681 }
682 else
683 {
684 let pivot_pos = choose_pivot a lo hi compare
685 let pivot = at a pivot_pos
686 let repeated = match ancestor
687 { Some(ancestor_pivot) -> !(less compare ancestor_pivot pivot)
688 , None -> False
689 }
690 if repeated
691 {
692 let (a, scratch, eq_len) =
693 partition a scratch lo hi pivot_pos True compare
694 quicksort a scratch (lo + eq_len) hi (limit - 1) None compare
695 }
696 else
697 {
698 let (a, scratch, left_len) =
699 partition a scratch lo hi pivot_pos False compare
700 if left_len == 0
701 {
702 // The pivot is the range's minimum: split off its equals.
703 let (a, scratch, eq_len) =
704 partition a scratch lo hi pivot_pos True compare
705 quicksort a scratch (lo + eq_len) hi (limit - 1) None compare
706 }
707 else
708 {
709 let (a, scratch) =
710 quicksort
711 a
712 scratch
713 (lo + left_len)
714 hi
715 (limit - 1)
716 (Some(pivot))
717 compare
718 quicksort a scratch lo (lo + left_len) (limit - 1) ancestor compare
719 }
720 }
721 }
722}
723
724/// The pivot's index in `a[lo..hi)`: the median of three samples, each the
725/// recursive pseudo-median of its third for ranges of 64 or more —
726/// approximating the median of `sqrt(n)` samples (glidesort).
727fn choose_pivot ::
728 a: Array<a>
729 lo: Int
730 hi: Int
731 compare: fn(a, a) -> Order / <e>
732 -> Int / <e>
733{
734 let n = hi - lo
735 let n8 = n / 8
736 if n < 64
737 {
738 median3 a lo (lo + n8 * 4) (lo + n8 * 7) compare
739 }
740 else
741 {
742 median3_rec a lo (lo + n8 * 4) (lo + n8 * 7) n8 compare
743 }
744}
745
746fn median3_rec ::
747 a: Array<a>
748 x: Int
749 y: Int
750 z: Int
751 n: Int
752 compare: fn(a, a) -> Order / <e>
753 -> Int / <e>
754{
755 if n * 8 >= 64
756 {
757 let n8 = n / 8
758 let x = median3_rec a x (x + n8 * 4) (x + n8 * 7) n8 compare
759 let y = median3_rec a y (y + n8 * 4) (y + n8 * 7) n8 compare
760 let z = median3_rec a z (z + n8 * 4) (z + n8 * 7) n8 compare
761 median3 a x y z compare
762 }
763 else
764 {
765 median3 a x y z compare
766 }
767}
768
769/// The index of the median of `a[x]`, `a[y]`, `a[z]`.
770fn median3 ::
771 a: Array<a>
772 x: Int
773 y: Int
774 z: Int
775 compare: fn(a, a) -> Order / <e>
776 -> Int / <e>
777{
778 let xy = less compare (at a x) (at a y)
779 let xz = less compare (at a x) (at a z)
780 if xy == xz
781 {
782 // `a[x]` is the smallest or the largest: the median is `a[y]` or
783 // `a[z]`, whichever is closer to it.
784 let yz = less compare (at a y) (at a z)
785 if yz != xy
786 {
787 z
788 }
789 else
790 {
791 y
792 }
793 }
794 else
795 {
796 x
797 }
798}
799
800/// Stable partition of `a[lo..hi)` around the pivot `a[pivot_pos]` through
801/// `scratch`, returning the left side's length. In less mode the left side
802/// is the elements `<` the pivot and the pivot joins the right; in equal
803/// mode the left side is the elements `<=` the pivot, the pivot included
804/// (called when the pivot is a known minimum or a repeated one, so that
805/// side is exactly its equals). Both sides keep their original order: the
806/// right is written into `scratch` backwards and the copy back reverses it
807/// again.
808fn partition ::
809 a: Array<a>
810 scratch: Array<a>
811 lo: Int
812 hi: Int
813 pivot_pos: Int
814 equal_mode: Bool
815 compare: fn(a, a) -> Order / <e>
816 -> (Array<a>, Array<a>, Int) / <e>
817{
818 let pivot = at a pivot_pos
819 let (scratch, left, right) =
820 partition_scan
821 a
822 scratch
823 lo
824 hi
825 pivot_pos
826 pivot
827 equal_mode
828 0
829 (hi - lo)
830 compare
831 let a = copy_forward a scratch 0 left lo
832 let a = copy_reversed a scratch right (hi - lo) (lo + left)
833 (a, scratch, left)
834}
835
836/// The scan of [`partition`]: `left` is the next slot on `scratch`'s left
837/// side, `right` one past the next slot on its right side (filled
838/// backwards from `hi - lo`): both relative to `lo`, so any subslice fits
839/// in `scratch`.
840fn partition_scan ::
841 a: Array<a>
842 scratch: Array<a>
843 i: Int
844 hi: Int
845 pivot_pos: Int
846 pivot: a
847 equal_mode: Bool
848 left: Int
849 right: Int
850 compare: fn(a, a) -> Order / <e>
851 -> (Array<a>, Int, Int) / <e>
852{
853 if i >= hi
854 {
855 (scratch, left, right)
856 }
857 else
858 {
859 // The pivot is placed, not compared (a comparison of it with itself
860 // could lie), at its scan turn: it stays among its equals where it
861 // was.
862 if i == pivot_pos
863 {
864 if equal_mode
865 {
866 partition_scan
867 a
868 (set scratch left pivot)
869 (i + 1)
870 hi
871 pivot_pos
872 pivot
873 equal_mode
874 (left + 1)
875 right
876 compare
877 }
878 else
879 {
880 partition_scan
881 a
882 (set scratch (right - 1) pivot)
883 (i + 1)
884 hi
885 pivot_pos
886 pivot
887 equal_mode
888 left
889 (right - 1)
890 compare
891 }
892 }
893 else
894 {
895 let x = at a i
896 let goes_left = if equal_mode
897 {
898 !(less compare pivot x)
899 }
900 else
901 {
902 less compare x pivot
903 }
904 if goes_left
905 {
906 partition_scan
907 a
908 (set scratch left x)
909 (i + 1)
910 hi
911 pivot_pos
912 pivot
913 equal_mode
914 (left + 1)
915 right
916 compare
917 }
918 else
919 {
920 partition_scan
921 a
922 (set scratch (right - 1) x)
923 (i + 1)
924 hi
925 pivot_pos
926 pivot
927 equal_mode
928 left
929 (right - 1)
930 compare
931 }
932 }
933 }
934}
935
936/// `src[from..to)` copied into `dst` at `out`.
937fn copy_forward ::
938 dst: Array<a>
939 src: Array<a>
940 from: Int
941 to: Int
942 out: Int
943 -> Array<a>
944{
945 if from >= to
946 {
947 dst
948 }
949 else
950 {
951 copy_forward (set dst out (at src from)) src (from + 1) to (out + 1)
952 }
953}
954
955/// `src[from..to)` copied into `dst` at `out`, reversed (`dst` gets
956/// `src[to - 1]`, then `src[to - 2]`, ...): how [`partition`]'s
957/// backwards-written right side comes back in its original order.
958fn copy_reversed ::
959 dst: Array<a>
960 src: Array<a>
961 from: Int
962 to: Int
963 out: Int
964 -> Array<a>
965{
966 if to <= from
967 {
968 dst
969 }
970 else
971 {
972 copy_reversed (set dst out (at src (to - 1))) src from (to - 1) (out + 1)
973 }
974}
975
976/// `a[from..to)` moved forwards to start at `out`. The target must be
977/// before the source. (One array parameter: passing `a` as both `dst` and
978/// `src` of `copy_forward` would share it, and `set` would copy.)
979fn move_forward :: a: Array<a> from: Int to: Int out: Int -> Array<a>
980{
981 if from >= to
982 {
983 a
984 }
985 else
986 {
987 move_forward (set a out (at a from)) (from + 1) to (out + 1)
988 }
989}
990
991/// `a[from..to)` moved backwards to end at `out` (included). The target
992/// must be past the source. (One array parameter: passing `a` as both
993/// `dst` and `src` of `copy_down` would share it, and `set` would copy.)
994fn move_down :: a: Array<a> from: Int to: Int out: Int -> Array<a>
995{
996 if to <= from
997 {
998 a
999 }
1000 else
1001 {
1002 move_down (set a out (at a (to - 1))) from (to - 1) (out - 1)
1003 }
1004}
1005
1006/// `src[from..to)` copied into `dst` backwards, ending at `out`
1007/// (included). Safe with `dst == src` when the target is past the source.
1008fn copy_down ::
1009 dst: Array<a>
1010 src: Array<a>
1011 from: Int
1012 to: Int
1013 out: Int
1014 -> Array<a>
1015{
1016 if to <= from
1017 {
1018 dst
1019 }
1020 else
1021 {
1022 copy_down (set dst out (at src (to - 1))) src from (to - 1) (out - 1)
1023 }
1024}
1025
1026/// The merger of the sorted runs `a[lo..mid)` and `a[mid..hi)`, through
1027/// `scratch`.
1028fn merge_runs ::
1029 a: Array<a>
1030 scratch: Array<a>
1031 lo: Int
1032 mid: Int
1033 hi: Int
1034 compare: fn(a, a) -> Order / <e>
1035 -> (Array<a>, Array<a>) / <e>
1036{
1037 let left_len = mid - lo
1038 let right_len = hi - mid
1039 if left_len == 0 || right_len == 0
1040 {
1041 (a, scratch)
1042 }
1043 else if !(less compare (at a mid) (at a (mid - 1)))
1044 {
1045 // Already in order across the boundary.
1046 (a, scratch)
1047 }
1048 else if left_len <= right_len
1049 {
1050 let scratch = fill_scratch a scratch lo 0 left_len
1051 merge_up_pair a scratch lo 0 left_len mid hi 0 (gallop_min ()) compare
1052 }
1053 else
1054 {
1055 let scratch = fill_scratch a scratch mid 0 right_len
1056 merge_down_pair
1057 a
1058 scratch
1059 (hi - 1)
1060 (mid - 1)
1061 lo
1062 (right_len - 1)
1063 0
1064 (gallop_min ())
1065 compare
1066 }
1067}
1068
1069/// `a[from..from + len)` copied over `scratch[0..len)`.
1070fn fill_scratch ::
1071 a: Array<a>
1072 scratch: Array<a>
1073 from: Int
1074 k: Int
1075 len: Int
1076 -> Array<a>
1077{
1078 if k >= len
1079 {
1080 scratch
1081 }
1082 else
1083 {
1084 fill_scratch a (set scratch k (at a (from + k))) from (k + 1) len
1085 }
1086}
1087
1088/// An up-merge's pairwise half: `scratch[0..left_len)` (the left run) and
1089/// `a[j..hi)` (the right) merged into `a[out..]`. Equal elements take the
1090/// left's (stability). `streak` counts one side's consecutive wins
1091/// (positive: the left's); past `min_gallop` of them the merge gallops.
1092fn merge_up_pair ::
1093 a: Array<a>
1094 scratch: Array<a>
1095 out: Int
1096 i: Int
1097 left_len: Int
1098 j: Int
1099 hi: Int
1100 streak: Int
1101 min_gallop: Int
1102 compare: fn(a, a) -> Order / <e>
1103 -> (Array<a>, Array<a>) / <e>
1104{
1105 if i >= left_len
1106 {
1107 // The left run is spent; the right's rest is in place.
1108 (a, scratch)
1109 }
1110 else if j >= hi
1111 {
1112 (copy_forward a scratch i left_len out, scratch)
1113 }
1114 else if less compare (at a j) (at scratch i)
1115 {
1116 let a = set a out (at a j)
1117 let streak = if streak < 0 { streak - 1 } else { 0 - 1 }
1118 if 0 - streak >= min_gallop
1119 {
1120 merge_up_gallop
1121 a
1122 scratch
1123 (out + 1)
1124 i
1125 left_len
1126 (j + 1)
1127 hi
1128 min_gallop
1129 compare
1130 }
1131 else
1132 {
1133 merge_up_pair
1134 a
1135 scratch
1136 (out + 1)
1137 i
1138 left_len
1139 (j + 1)
1140 hi
1141 streak
1142 min_gallop
1143 compare
1144 }
1145 }
1146 else
1147 {
1148 let a = set a out (at scratch i)
1149 let streak = if streak > 0 { streak + 1 } else { 1 }
1150 if streak >= min_gallop
1151 {
1152 merge_up_gallop
1153 a
1154 scratch
1155 (out + 1)
1156 (i + 1)
1157 left_len
1158 j
1159 hi
1160 min_gallop
1161 compare
1162 }
1163 else
1164 {
1165 merge_up_pair
1166 a
1167 scratch
1168 (out + 1)
1169 (i + 1)
1170 left_len
1171 j
1172 hi
1173 streak
1174 min_gallop
1175 compare
1176 }
1177 }
1178}
1179
1180/// An up-merge's galloping half: the losing side's next stretch is found
1181/// by exponential, then binary, search and copied without per-element
1182/// comparisons, until both stretches come up short (then back to
1183/// [`merge_up_pair`], with a raised `min_gallop`). Alternates: the left
1184/// run's elements `<=` the right's head, then the right run's elements
1185/// `<` the left's head (timsort's `merge_lo`; the strict/non-strict
1186/// split is what keeps equal elements in their original order).
1187fn merge_up_gallop ::
1188 a: Array<a>
1189 scratch: Array<a>
1190 out: Int
1191 i: Int
1192 left_len: Int
1193 j: Int
1194 hi: Int
1195 min_gallop: Int
1196 compare: fn(a, a) -> Order / <e>
1197 -> (Array<a>, Array<a>) / <e>
1198{
1199 if i >= left_len
1200 {
1201 (a, scratch)
1202 }
1203 else if j >= hi
1204 {
1205 (copy_forward a scratch i left_len out, scratch)
1206 }
1207 else
1208 {
1209 // The left run's elements `<= a[j]` come first (stability).
1210 let count = gallop_right scratch (at a j) i (left_len - i) compare
1211 let a = copy_forward a scratch i (i + count) out
1212 let i = i + count
1213 let out = out + count
1214 if i >= left_len
1215 {
1216 (a, scratch)
1217 }
1218 else
1219 {
1220 let a = set a out (at a j)
1221 let j = j + 1
1222 let out = out + 1
1223 if j >= hi
1224 {
1225 (copy_forward a scratch i left_len out, scratch)
1226 }
1227 else
1228 {
1229 // The right run's elements `< scratch[i]` come first.
1230 let count2 = gallop_left a (at scratch i) j (hi - j) compare
1231 let a = move_forward a j (j + count2) out
1232 let j = j + count2
1233 let out = out + count2
1234 if j >= hi
1235 {
1236 (copy_forward a scratch i left_len out, scratch)
1237 }
1238 else
1239 {
1240 let a = set a out (at scratch i)
1241 let i = i + 1
1242 let out = out + 1
1243 let min_gallop = if min_gallop > 1 { min_gallop - 1 } else { 1 }
1244 if count < gallop_min () && count2 < gallop_min ()
1245 {
1246 merge_up_pair
1247 a
1248 scratch
1249 out
1250 i
1251 left_len
1252 j
1253 hi
1254 0
1255 (min_gallop + 2)
1256 compare
1257 }
1258 else
1259 {
1260 merge_up_gallop a scratch out i left_len j hi min_gallop compare
1261 }
1262 }
1263 }
1264 }
1265 }
1266}
1267
1268/// A down-merge's pairwise half: `a[lo..=i]` (the left run) and
1269/// `scratch[0..=j]` (the right) merged into `a[..=out]`, from the back.
1270/// Equal elements take the right's (stability, from the back).
1271fn merge_down_pair ::
1272 a: Array<a>
1273 scratch: Array<a>
1274 out: Int
1275 i: Int
1276 lo: Int
1277 j: Int
1278 streak: Int
1279 min_gallop: Int
1280 compare: fn(a, a) -> Order / <e>
1281 -> (Array<a>, Array<a>) / <e>
1282{
1283 if j < 0
1284 {
1285 // The right run is spent; the left's rest is in place.
1286 (a, scratch)
1287 }
1288 else if i < lo
1289 {
1290 (copy_forward a scratch 0 (j + 1) lo, scratch)
1291 }
1292 else if less compare (at scratch j) (at a i)
1293 {
1294 let a = set a out (at a i)
1295 let streak = if streak < 0 { streak - 1 } else { 0 - 1 }
1296 if False
1297 {
1298 merge_down_gallop a scratch (out - 1) (i - 1) lo j min_gallop compare
1299 }
1300 else
1301 {
1302 merge_down_pair a scratch (out - 1) (i - 1) lo j streak min_gallop compare
1303 }
1304 }
1305 else
1306 {
1307 let a = set a out (at scratch j)
1308 let streak = if streak > 0 { streak + 1 } else { 1 }
1309 if False
1310 {
1311 merge_down_gallop a scratch (out - 1) i lo (j - 1) min_gallop compare
1312 }
1313 else
1314 {
1315 merge_down_pair a scratch (out - 1) i lo (j - 1) streak min_gallop compare
1316 }
1317 }
1318}
1319
1320/// A down-merge's galloping half (see [`merge_up_gallop`]).
1321fn merge_down_gallop ::
1322 a: Array<a>
1323 scratch: Array<a>
1324 out: Int
1325 i: Int
1326 lo: Int
1327 j: Int
1328 min_gallop: Int
1329 compare: fn(a, a) -> Order / <e>
1330 -> (Array<a>, Array<a>) / <e>
1331{
1332 if j < 0
1333 {
1334 (a, scratch)
1335 }
1336 else if i < lo
1337 {
1338 (copy_forward a scratch 0 (j + 1) lo, scratch)
1339 }
1340 else
1341 {
1342 // The left run's elements `> scratch[j]` go to the back.
1343 let count = gallop_right a (at scratch j) lo (i - lo + 1) compare
1344 let bulk = i - lo + 1 - count
1345 let a = move_down a (lo + count) (i + 1) out
1346 let i = i - bulk
1347 let out = out - bulk
1348 if i < lo
1349 {
1350 (copy_forward a scratch 0 (j + 1) lo, scratch)
1351 }
1352 else
1353 {
1354 let a = set a out (at scratch j)
1355 let j = j - 1
1356 let out = out - 1
1357 if j < 0
1358 {
1359 (a, scratch)
1360 }
1361 else
1362 {
1363 // The right run's elements `>= a[i]` go to the back.
1364 let count2 = gallop_left scratch (at a i) 0 (j + 1) compare
1365 let bulk2 = j + 1 - count2
1366 let a = copy_down a scratch count2 (j + 1) out
1367 let j = j - bulk2
1368 let out = out - bulk2
1369 if j < 0
1370 {
1371 (a, scratch)
1372 }
1373 else
1374 {
1375 let a = set a out (at a i)
1376 let i = i - 1
1377 let out = out - 1
1378 let min_gallop = if min_gallop > 1 { min_gallop - 1 } else { 1 }
1379 if count < gallop_min () && count2 < gallop_min ()
1380 {
1381 merge_down_pair a scratch out i lo j 0 (min_gallop + 2) compare
1382 }
1383 else
1384 {
1385 merge_down_gallop a scratch out i lo j min_gallop compare
1386 }
1387 }
1388 }
1389 }
1390 }
1391}
1392
1393/// How many of `arr[base..base + n)` are `<= key`: the upper bound, so
1394/// equal elements sort before `key`. Exponential search, then binary.
1395fn gallop_right ::
1396 arr: Array<a>
1397 key: a
1398 base: Int
1399 n: Int
1400 compare: fn(a, a) -> Order / <e>
1401 -> Int / <e>
1402{
1403 if n <= 0 || less compare key (at arr base)
1404 {
1405 0
1406 }
1407 else
1408 {
1409 let (lo, hi) = gallop_right_probe arr key base n 0 1 compare
1410 gallop_right_finish arr key base lo hi compare
1411 }
1412}
1413
1414/// The probe range for [`gallop_right`]: `arr[base + lo] <= key`, and
1415/// `probe` past the answer or past the end.
1416fn gallop_right_probe ::
1417 arr: Array<a>
1418 key: a
1419 base: Int
1420 n: Int
1421 lo: Int
1422 ofs: Int
1423 compare: fn(a, a) -> Order / <e>
1424 -> (Int, Int) / <e>
1425{
1426 let probe = lo + ofs
1427 if probe < n && !(less compare key (at arr (base + probe)))
1428 {
1429 gallop_right_probe arr key base n probe (ofs * 2) compare
1430 }
1431 else
1432 {
1433 (lo, min_int probe (n - 1))
1434 }
1435}
1436
1437/// The binary search: the last index in `[lo, hi]` with
1438/// `arr[base + ..] <= key`, plus one.
1439fn gallop_right_finish ::
1440 arr: Array<a>
1441 key: a
1442 base: Int
1443 lo: Int
1444 hi: Int
1445 compare: fn(a, a) -> Order / <e>
1446 -> Int / <e>
1447{
1448 if lo >= hi
1449 {
1450 lo + 1
1451 }
1452 else
1453 {
1454 let mid = (lo + hi + 1) / 2
1455 if less compare key (at arr (base + mid))
1456 {
1457 gallop_right_finish arr key base lo (mid - 1) compare
1458 }
1459 else
1460 {
1461 gallop_right_finish arr key base mid hi compare
1462 }
1463 }
1464}
1465
1466/// How many of `arr[base..base + n)` are `< key`: the lower bound, so
1467/// equal elements sort after `key`. Exponential search, then binary.
1468fn gallop_left ::
1469 arr: Array<a>
1470 key: a
1471 base: Int
1472 n: Int
1473 compare: fn(a, a) -> Order / <e>
1474 -> Int / <e>
1475{
1476 if n <= 0 || !(less compare (at arr base) key)
1477 {
1478 0
1479 }
1480 else
1481 {
1482 let (lo, hi) = gallop_left_probe arr key base n 0 1 compare
1483 gallop_left_finish arr key base lo hi compare
1484 }
1485}
1486
1487/// The probe range for [`gallop_left`]: `arr[base + lo] < key`, and
1488/// `probe` past the answer or past the end.
1489fn gallop_left_probe ::
1490 arr: Array<a>
1491 key: a
1492 base: Int
1493 n: Int
1494 lo: Int
1495 ofs: Int
1496 compare: fn(a, a) -> Order / <e>
1497 -> (Int, Int) / <e>
1498{
1499 let probe = lo + ofs
1500 if probe < n && less compare (at arr (base + probe)) key
1501 {
1502 gallop_left_probe arr key base n probe (ofs * 2) compare
1503 }
1504 else
1505 {
1506 (lo, min_int probe (n - 1))
1507 }
1508}
1509
1510/// The binary search: the last index in `[lo, hi]` with
1511/// `arr[base + ..] < key`, plus one.
1512fn gallop_left_finish ::
1513 arr: Array<a>
1514 key: a
1515 base: Int
1516 lo: Int
1517 hi: Int
1518 compare: fn(a, a) -> Order / <e>
1519 -> Int / <e>
1520{
1521 if lo >= hi
1522 {
1523 lo + 1
1524 }
1525 else
1526 {
1527 let mid = (lo + hi + 1) / 2
1528 if less compare (at arr (base + mid)) key
1529 {
1530 gallop_left_finish arr key base mid hi compare
1531 }
1532 else
1533 {
1534 gallop_left_finish arr key base lo (mid - 1) compare
1535 }
1536 }
1537}
1538
1539impl Eq<Array<a>> where Eq<a>
1540{
1541 fn eq :: x y
1542 {
1543 length x == length y && equal_from x y 0
1544 }
1545}
1546
1547fn equal_from :: x y i
1548{
1549 if i < length x
1550 {
1551 at x i == at y i && equal_from x y (i + 1)
1552 }
1553 else
1554 {
1555 True
1556 }
1557}
1558
1559/// Lexicographic, as for lists: a prefix is smaller.
1560impl Ord<Array<a>> where Ord<a>
1561{
1562 fn compare :: x y
1563 {
1564 compare_from x y 0
1565 }
1566}
1567
1568fn compare_from :: x y i
1569{
1570 if i >= length x
1571 {
1572 if i >= length y
1573 {
1574 Eq
1575 }
1576 else
1577 {
1578 Lt
1579 }
1580 }
1581 else if i >= length y
1582 {
1583 Gt
1584 }
1585 else
1586 {
1587 match compare (at x i) (at y i)
1588 { Eq -> compare_from x y (i + 1), other -> other }
1589 }
1590}
1591
1592/// `[1, 2, 3]`, as for lists.
1593impl Show<Array<a>> where Show<a>
1594{
1595 fn show :: x
1596 {
1597 "[" <> string.join (to_list (map x (show _))) ", " <> "]"
1598 }
1599}
1600
1601impl Debug<Array<a>> where Debug<a>
1602{
1603 fn debug :: x
1604 {
1605 "[" <> string.join (to_list (map x (debug _))) ", " <> "]"
1606 }
1607}
1608
1609impl Hash<Array<a>> where Hash<a>
1610{
1611 fn hash :: x
1612 {
1613 fold x 7 fn acc v { hash_combine acc (hash v) }
1614 }
1615}