1--- Strict ordering evidence. `less` must be irreflexive and transitive, with
2--- consistent equivalence classes, for the duration of a sort.
3public ordered: type = concept (item: type)
4 --- Return true exactly when left precedes right under the strict weak
5 --- ordering.
6 less: (left: item, right: item) -> (yes: bool)
7end ordered
8
9-- The library supplies the ordering of every integer scalar, and core/text
10-- that of utf8. One register, no override [1280]: another ordering for one
11-- of these goes on a distinct wrapper.
12less_u8: (left: u8, right: u8) -> (yes: bool) =
13 yes = left < right
14end less_u8
15less_u16: (left: u16, right: u16) -> (yes: bool) =
16 yes = left < right
17end less_u16
18less_u32: (left: u32, right: u32) -> (yes: bool) =
19 yes = left < right
20end less_u32
21less_u64: (left: u64, right: u64) -> (yes: bool) =
22 yes = left < right
23end less_u64
24less_usize: (left: usize, right: usize) -> (yes: bool) =
25 yes = left < right
26end less_usize
27less_i8: (left: i8, right: i8) -> (yes: bool) =
28 yes = left < right
29end less_i8
30less_i16: (left: i16, right: i16) -> (yes: bool) =
31 yes = left < right
32end less_i16
33less_i32: (left: i32, right: i32) -> (yes: bool) =
34 yes = left < right
35end less_i32
36less_i64: (left: i64, right: i64) -> (yes: bool) =
37 yes = left < right
38end less_i64
39less_isize: (left: isize, right: isize) -> (yes: bool) =
40 yes = left < right
41end less_isize
42u8 is ordered (less: less_u8)
43u16 is ordered (less: less_u16)
44u32 is ordered (less: less_u32)
45u64 is ordered (less: less_u64)
46usize is ordered (less: less_usize)
47i8 is ordered (less: less_i8)
48i16 is ordered (less: less_i16)
49i32 is ordered (less: less_i32)
50i64 is ordered (less: less_i64)
51isize is ordered (less: less_isize)
52
53-- Restore the max-heap property in values[0..<count] below root.
54-- A parent has a child exactly when at < count / 2, so the child-index
55-- arithmetic cannot overflow even for a maximum-length view.
56sift_down: (item: type is ordered, values: []mut item,
57 root: usize, count: usize) -> none =
58 mut at := root
59 while at < count / 2 do
60 mut child: usize = at * 2 + 1
61 if child + 1 < count and item.less(values[child], values[child + 1]) then
62 inc child
63 end if
64 if not item.less(values[at], values[child]) then
65 return
66 end if
67 saved: item = values[at]
68 values[at] = values[child]
69 values[child] = saved
70 at = child
71 end while
72end sift_down
73
74--- Sort an initialized mutable slice in place using heapsort. Requires
75--- consistent `ordered` evidence; uses constant auxiliary storage, no
76--- allocation and O(n log n) comparisons. Equal items need not retain their
77--- order.
78---
79--- In-place heapsort for initialized views. Worst-case O(n log n)
80--- comparisons, constant auxiliary storage and bounded call depth.
81--- The caller supplies a strict ordering; stability is not promised.
82public sort: (item: type is ordered, values: []mut item) -> none =
83 count: usize = lenof values
84 mut start: usize = count / 2
85 while start > 0 do
86 dec start
87 sift_down(values, start, count)
88 end while
89 mut remaining := count
90 zero: usize = 0
91 while remaining > 1 do
92 dec remaining
93 saved: item = values[zero]
94 values[zero] = values[remaining]
95 values[remaining] = saved
96 sift_down(values, zero, remaining)
97 end while
98end sort
99
100--- Sort in place using selection sort. Performs n(n-1)/2 comparisons and at
101--- most n-1 swaps, with no allocation. Useful for tiny or expensive-to-swap
102--- items; it is not stable.
103---
104--- Selection sort for tiny or swap-expensive views. Exactly n(n-1)/2
105--- comparisons, at most n-1 swaps, constant storage and bounded call depth.
106public sort_selection: (item: type is ordered, values: []mut item) -> none =
107 mut at: usize = 0
108 while at < lenof values do
109 mut least := at
110 mut next := at + 1
111 while next < lenof values do
112 if item.less(values[next], values[least]) then
113 least = next
114 end if
115 inc next
116 end while
117 if least <> at then
118 saved: item = values[at]
119 values[at] = values[least]
120 values[least] = saved
121 end if
122 inc at
123 end while
124end sort_selection