src/binary_tree_array.rs

   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 }