1//! Index for nodes of a binary tree based on an in-order tree walk.
  2//!
  3//! In-order walks have the parent node index split its left and right subtrees. All the left
  4//! children have indexes lower than the parent, meanwhile all the right subtree higher indexes.
  5//! This property makes it is easy to compute changes to the index by adding or subtracting the
  6//! leaves count.
  7use core::num::NonZeroUsize;
  8
  9// IN-ORDER INDEX
 10// ================================================================================================
 11
 12/// Index of nodes in a perfectly balanced binary tree based on an in-order tree walk.
 13#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
 14pub struct InOrderIndex {
 15    idx: usize,
 16}
 17
 18impl InOrderIndex {
 19    /// Constructor for a new [InOrderIndex].
 20    pub fn new(idx: NonZeroUsize) -> InOrderIndex {
 21        InOrderIndex { idx: idx.get() }
 22    }
 23
 24    /// Constructs an index from a leaf position.
 25    ///
 26    /// Panics:
 27    ///
 28    /// If `leaf` is higher than or equal to `usize::MAX / 2`.
 29    pub fn from_leaf_pos(leaf: usize) -> InOrderIndex {
 30        // Convert the position from 0-indexed to 1-indexed, since the bit manipulation in this
 31        // implementation only works 1-indexed counting.
 32        let pos = leaf + 1;
 33        InOrderIndex { idx: pos * 2 - 1 }
 34    }
 35
 36    /// True if the index is pointing at a leaf.
 37    ///
 38    /// Every odd number represents a leaf.
 39    pub fn is_leaf(&self) -> bool {
 40        self.idx & 1 == 1
 41    }
 42
 43    /// Returns the level of the index.
 44    ///
 45    /// Starts at level zero for leaves and increases by one for each parent.
 46    pub fn level(&self) -> u32 {
 47        self.idx.trailing_zeros()
 48    }
 49
 50    /// Returns the index of the left child.
 51    ///
 52    /// Panics:
 53    ///
 54    /// If the index corresponds to a leaf.
 55    pub fn left_child(&self) -> InOrderIndex {
 56        // The left child is itself a parent, with an index that splits its left/right subtrees. To
 57        // go from the parent index to its left child, it is only necessary to subtract the count
 58        // of elements on the child's right subtree + 1.
 59        let els = 1 << (self.level() - 1);
 60        InOrderIndex { idx: self.idx - els }
 61    }
 62
 63    /// Returns the index of the right child.
 64    ///
 65    /// Panics:
 66    ///
 67    /// If the index corresponds to a leaf.
 68    pub fn right_child(&self) -> InOrderIndex {
 69        // To compute the index of the parent of the right subtree it is sufficient to add the size
 70        // of its left subtree + 1.
 71        let els = 1 << (self.level() - 1);
 72        InOrderIndex { idx: self.idx + els }
 73    }
 74
 75    /// Returns the index of the parent node.
 76    pub fn parent(&self) -> InOrderIndex {
 77        // If the current index corresponds to a node in a left tree, to go up a level it is
 78        // required to add the number of nodes of the right sibling, analogously if the node is a
 79        // right child, going up requires subtracting the number of nodes in its left subtree.
 80        //
 81        // Both of the above operations can be performed by bitwise manipulation. Below the mask
 82        // sets the number of trailing zeros to be equal the new level of the index, and the bit
 83        // marks the parent.
 84        let target = self.level() + 1;
 85        let bit = 1 << target;
 86        let mask = bit - 1;
 87        let idx = self.idx ^ (self.idx & mask);
 88        InOrderIndex { idx: idx | bit }
 89    }
 90
 91    /// Returns the index of the sibling node.
 92    pub fn sibling(&self) -> InOrderIndex {
 93        let parent = self.parent();
 94        if *self > parent {
 95            parent.left_child()
 96        } else {
 97            parent.right_child()
 98        }
 99    }
100}
101
102// CONVERSIONS FROM IN-ORDER INDEX
103// ------------------------------------------------------------------------------------------------
104
105impl From<InOrderIndex> for u64 {
106    fn from(index: InOrderIndex) -> Self {
107        index.idx as u64
108    }
109}
110
111// TESTS
112// ================================================================================================
113
114#[cfg(test)]
115mod test {
116    use super::InOrderIndex;
117    use proptest::prelude::*;
118
119    proptest! {
120        #[test]
121        fn proptest_inorder_index_random(count in 1..1000usize) {
122            let left_pos = count * 2;
123            let right_pos = count * 2 + 1;
124
125            let left = InOrderIndex::from_leaf_pos(left_pos);
126            let right = InOrderIndex::from_leaf_pos(right_pos);
127
128            assert!(left.is_leaf());
129            assert!(right.is_leaf());
130            assert_eq!(left.parent(), right.parent());
131            assert_eq!(left.parent().right_child(), right);
132            assert_eq!(left, right.parent().left_child());
133            assert_eq!(left.sibling(), right);
134            assert_eq!(left, right.sibling());
135        }
136    }
137
138    #[test]
139    fn test_inorder_index_basic() {
140        let left = InOrderIndex::from_leaf_pos(0);
141        let right = InOrderIndex::from_leaf_pos(1);
142
143        assert!(left.is_leaf());
144        assert!(right.is_leaf());
145        assert_eq!(left.parent(), right.parent());
146        assert_eq!(left.parent().right_child(), right);
147        assert_eq!(left, right.parent().left_child());
148        assert_eq!(left.sibling(), right);
149        assert_eq!(left, right.sibling());
150    }
151}