]>
Commit | Line | Data |
---|---|---|
1 | //! Helpers to generate a binary search tree stored in an array from a | |
2 | //! sorted array. | |
3 | //! | |
4 | //! Specifically, for any given sorted array 'input' permute the | |
5 | //! array so that the following rule holds: | |
6 | //! | |
7 | //! For each array item with index i, the item at 2i+1 is smaller and | |
8 | //! the item 2i+2 is larger. | |
9 | //! | |
10 | //! This structure permits efficient (meaning: O(log(n)) binary | |
11 | //! searches: start with item i=0 (i.e. the root of the BST), compare | |
12 | //! the value with the searched item, if smaller proceed at item | |
13 | //! 2i+1, if larger proceed at item 2i+2, and repeat, until either | |
14 | //! the item is found, or the indexes grow beyond the array size, | |
15 | //! which means the entry does not exist. | |
16 | //! | |
17 | //! Effectively this implements bisection, but instead of jumping | |
18 | //! around wildly in the array during a single search we only search | |
19 | //! with strictly monotonically increasing indexes. | |
20 | //! | |
21 | //! Algorithm is from casync (camakebst.c), simplified and optimized | |
22 | //! for rust. Permutation function originally by L. Bressel, 2017. We | |
23 | //! pass permutation info to user provided callback, which actually | |
24 | //! implements the data copy. | |
25 | //! | |
26 | //! The Wikipedia Artikel for [Binary | |
27 | //! Heap](https://en.wikipedia.org/wiki/Binary_heap) gives a short | |
28 | //! intro howto store binary trees using an array. | |
29 | ||
30 | #![deny(missing_docs)] | |
31 | ||
32 | use std::cmp::Ordering; | |
33 | ||
34 | #[allow(clippy::many_single_char_names)] | |
35 | fn copy_inner<F: FnMut(usize, usize)>( | |
36 | copy_func: &mut F, | |
37 | // we work on input array input[o..o+n] | |
38 | n: usize, | |
39 | o: usize, | |
40 | e: usize, | |
41 | i: usize, | |
42 | ) { | |
43 | let p = 1 << e; | |
44 | ||
45 | let t = p + (p >> 1) - 1; | |
46 | ||
47 | let m = if n > t { | |
48 | // |...........p.............t....n........(2p)| | |
49 | p - 1 | |
50 | } else { | |
51 | // |...........p.....n.......t.............(2p)| | |
52 | p - 1 - (t - n) | |
53 | }; | |
54 | ||
55 | (copy_func)(o + m, i); | |
56 | ||
57 | if m > 0 { | |
58 | copy_inner(copy_func, m, o, e - 1, i * 2 + 1); | |
59 | } | |
60 | ||
61 | if (m + 1) < n { | |
62 | copy_inner(copy_func, n - m - 1, o + m + 1, e - 1, i * 2 + 2); | |
63 | } | |
64 | } | |
65 | ||
66 | /// This function calls the provided `copy_func()` with the permutaion information required to | |
67 | /// build a binary search tree array. | |
68 | /// | |
69 | /// ``` | |
70 | /// # use pxar::binary_tree_array; | |
71 | /// # let mut i = 0; | |
72 | /// # const EXPECTED: &[(usize, usize)] = &[(3, 0), (1, 1), (0, 3), (2, 4), (4, 2)]; | |
73 | /// binary_tree_array::copy(5, |src, dest| { | |
74 | /// # assert_eq!((src, dest), EXPECTED[i]); | |
75 | /// # i += 1; | |
76 | /// println!("Copy {} to {}", src, dest); | |
77 | /// }); | |
78 | /// ``` | |
79 | /// | |
80 | /// This will produce the folowing output: | |
81 | /// | |
82 | /// ```no-compile | |
83 | /// Copy 3 to 0 | |
84 | /// Copy 1 to 1 | |
85 | /// Copy 0 to 3 | |
86 | /// Copy 2 to 4 | |
87 | /// Copy 4 to 2 | |
88 | /// ``` | |
89 | /// | |
90 | /// So this generates the following permuation: `[3,1,4,0,2]`. | |
91 | pub fn copy<F>(n: usize, mut copy_func: F) | |
92 | where | |
93 | F: FnMut(usize, usize), | |
94 | { | |
95 | if n == 0 { | |
96 | return; | |
97 | }; | |
98 | ||
99 | let e = (64 - n.leading_zeros() - 1) as usize; // fast log2(n) | |
100 | ||
101 | copy_inner(&mut copy_func, n, 0, e, 0); | |
102 | } | |
103 | ||
104 | /// This function searches for the index where the comparison by the provided | |
105 | /// `compare()` function returns `Ordering::Equal`. | |
106 | /// The order of the comparison matters (noncommutative) and should be search | |
107 | /// value compared to value at given index as shown in the examples. | |
108 | /// The parameter `skip` defines the number of matches to ignore while | |
109 | /// searching before returning the index in order to lookup duplicate entries in | |
110 | /// the tree. | |
111 | /// | |
112 | /// ``` | |
113 | /// # use pxar::binary_tree_array; | |
114 | /// let mut vals = vec![0,1,2,2,2,3,4,5,6,6,7,8,8,8]; | |
115 | /// | |
116 | /// let clone = vals.clone(); | |
117 | /// binary_tree_array::copy(vals.len(), |s, d| { | |
118 | /// vals[d] = clone[s]; | |
119 | /// }); | |
120 | /// let should_be = vec![5,2,8,1,3,6,8,0,2,2,4,6,7,8]; | |
121 | /// assert_eq!(vals, should_be); | |
122 | /// | |
123 | /// let find = 8; | |
124 | /// let skip = 0; | |
125 | /// let idx = binary_tree_array::search_by(&vals, 0, skip, |el| find.cmp(el)); | |
126 | /// assert_eq!(idx, Some(2)); | |
127 | /// | |
128 | /// let find = 8; | |
129 | /// let skip = 1; | |
130 | /// let idx = binary_tree_array::search_by(&vals, 2, skip, |el| find.cmp(el)); | |
131 | /// assert_eq!(idx, Some(6)); | |
132 | /// | |
133 | /// let find = 8; | |
134 | /// let skip = 1; | |
135 | /// let idx = binary_tree_array::search_by(&vals, 6, skip, |el| find.cmp(el)); | |
136 | /// assert_eq!(idx, Some(13)); | |
137 | /// | |
138 | /// let find = 5; | |
139 | /// let skip = 1; | |
140 | /// let idx = binary_tree_array::search_by(&vals, 0, skip, |el| find.cmp(el)); | |
141 | /// assert!(idx.is_none()); | |
142 | /// | |
143 | /// let find = 5; | |
144 | /// let skip = 0; | |
145 | /// // if start index is equal to the array length, `None` is returned. | |
146 | /// let idx = binary_tree_array::search_by(&vals, vals.len(), skip, |el| find.cmp(el)); | |
147 | /// assert!(idx.is_none()); | |
148 | /// | |
149 | /// // if start index is larger than length, `None` is returned. | |
150 | /// let idx = binary_tree_array::search_by(&vals, vals.len() + 1, skip, |el| find.cmp(el)); | |
151 | /// assert!(idx.is_none()); | |
152 | /// ``` | |
153 | pub fn search_by<F, T>(tree: &[T], start: usize, skip: usize, f: F) -> Option<usize> | |
154 | where | |
155 | F: Copy + Fn(&T) -> Ordering, | |
156 | { | |
157 | let mut i = start; | |
158 | ||
159 | while i < tree.len() { | |
160 | match f(&tree[i]) { | |
161 | Ordering::Less => i = 2 * i + 1, | |
162 | Ordering::Greater => i = 2 * i + 2, | |
163 | Ordering::Equal if skip == 0 => return Some(i), | |
164 | Ordering::Equal => { | |
165 | i = 2 * i + 1; | |
166 | return search_by(tree, i, skip - 1, f) | |
167 | .or_else(move || search_by(tree, i + 1, skip - 1, f)); | |
168 | } | |
169 | } | |
170 | } | |
171 | ||
172 | None | |
173 | } | |
174 | ||
175 | #[test] | |
176 | fn test_binary_search_tree() { | |
177 | fn run_test(len: usize) -> Vec<usize> { | |
178 | const MARKER: usize = 0xfffffff; | |
179 | let mut output = vec![]; | |
180 | for _i in 0..len { | |
181 | output.push(MARKER); | |
182 | } | |
183 | copy(len, |s, d| { | |
184 | assert!(output[d] == MARKER); | |
185 | output[d] = s; | |
186 | }); | |
187 | if len < 32 { | |
188 | println!("GOT:{}:{:?}", len, output); | |
189 | } | |
190 | for i in 0..len { | |
191 | assert!(output[i] != MARKER); | |
192 | } | |
193 | output | |
194 | } | |
195 | ||
196 | assert!(run_test(0).len() == 0); | |
197 | assert!(run_test(1) == [0]); | |
198 | assert!(run_test(2) == [1, 0]); | |
199 | assert!(run_test(3) == [1, 0, 2]); | |
200 | assert!(run_test(4) == [2, 1, 3, 0]); | |
201 | assert!(run_test(5) == [3, 1, 4, 0, 2]); | |
202 | assert!(run_test(6) == [3, 1, 5, 0, 2, 4]); | |
203 | assert!(run_test(7) == [3, 1, 5, 0, 2, 4, 6]); | |
204 | assert!(run_test(8) == [4, 2, 6, 1, 3, 5, 7, 0]); | |
205 | assert!(run_test(9) == [5, 3, 7, 1, 4, 6, 8, 0, 2]); | |
206 | assert!(run_test(10) == [6, 3, 8, 1, 5, 7, 9, 0, 2, 4]); | |
207 | assert!(run_test(11) == [7, 3, 9, 1, 5, 8, 10, 0, 2, 4, 6]); | |
208 | assert!(run_test(12) == [7, 3, 10, 1, 5, 9, 11, 0, 2, 4, 6, 8]); | |
209 | assert!(run_test(13) == [7, 3, 11, 1, 5, 9, 12, 0, 2, 4, 6, 8, 10]); | |
210 | assert!(run_test(14) == [7, 3, 11, 1, 5, 9, 13, 0, 2, 4, 6, 8, 10, 12]); | |
211 | assert!(run_test(15) == [7, 3, 11, 1, 5, 9, 13, 0, 2, 4, 6, 8, 10, 12, 14]); | |
212 | assert!(run_test(16) == [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15, 0]); | |
213 | assert!(run_test(17) == [9, 5, 13, 3, 7, 11, 15, 1, 4, 6, 8, 10, 12, 14, 16, 0, 2]); | |
214 | ||
215 | for len in 18..1000 { | |
216 | run_test(len); | |
217 | } | |
218 | } |