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    // CONSTRUCTORS
 20    // --------------------------------------------------------------------------------------------
 21
 22    /// Returns a new [InOrderIndex] instantiated from the provided value.
 23    pub fn new(idx: NonZeroUsize) -> InOrderIndex {
 24        InOrderIndex { idx: idx.get() }
 25    }
 26
 27    /// Return a new [InOrderIndex] instantiated from the specified leaf position.
 28    ///
 29    /// # Panics:
 30    /// If `leaf` is higher than or equal to `usize::MAX / 2`.
 31    pub fn from_leaf_pos(leaf: usize) -> InOrderIndex {
 32        // Convert the position from 0-indexed to 1-indexed, since the bit manipulation in this
 33        // implementation only works 1-indexed counting.
 34        let pos = leaf + 1;
 35        InOrderIndex { idx: pos * 2 - 1 }
 36    }
 37
 38    // PUBLIC ACCESSORS
 39    // --------------------------------------------------------------------------------------------
 40
 41    /// True if the index is pointing at a leaf.
 42    ///
 43    /// Every odd number represents a leaf.
 44    pub fn is_leaf(&self) -> bool {
 45        self.idx & 1 == 1
 46    }
 47
 48    /// Returns true if this note is a left child of its parent.
 49    pub fn is_left_child(&self) -> bool {
 50        self.parent().left_child() == *self
 51    }
 52
 53    /// Returns the level of the index.
 54    ///
 55    /// Starts at level zero for leaves and increases by one for each parent.
 56    pub fn level(&self) -> u32 {
 57        self.idx.trailing_zeros()
 58    }
 59
 60    /// Returns the index of the left child.
 61    ///
 62    /// # Panics:
 63    /// If the index corresponds to a leaf.
 64    pub fn left_child(&self) -> InOrderIndex {
 65        // The left child is itself a parent, with an index that splits its left/right subtrees. To
 66        // go from the parent index to its left child, it is only necessary to subtract the count
 67        // of elements on the child's right subtree + 1.
 68        let els = 1 << (self.level() - 1);
 69        InOrderIndex { idx: self.idx - els }
 70    }
 71
 72    /// Returns the index of the right child.
 73    ///
 74    /// # Panics:
 75    /// If the index corresponds to a leaf.
 76    pub fn right_child(&self) -> InOrderIndex {
 77        // To compute the index of the parent of the right subtree it is sufficient to add the size
 78        // of its left subtree + 1.
 79        let els = 1 << (self.level() - 1);
 80        InOrderIndex { idx: self.idx + els }
 81    }
 82
 83    /// Returns the index of the parent node.
 84    pub fn parent(&self) -> InOrderIndex {
 85        // If the current index corresponds to a node in a left tree, to go up a level it is
 86        // required to add the number of nodes of the right sibling, analogously if the node is a
 87        // right child, going up requires subtracting the number of nodes in its left subtree.
 88        //
 89        // Both of the above operations can be performed by bitwise manipulation. Below the mask
 90        // sets the number of trailing zeros to be equal the new level of the index, and the bit
 91        // marks the parent.
 92        let target = self.level() + 1;
 93        let bit = 1 << target;
 94        let mask = bit - 1;
 95        let idx = self.idx ^ (self.idx & mask);
 96        InOrderIndex { idx: idx | bit }
 97    }
 98
 99    /// Returns the index of the sibling node.
100    pub fn sibling(&self) -> InOrderIndex {
101        let parent = self.parent();
102        if *self > parent {
103            parent.left_child()
104        } else {
105            parent.right_child()
106        }
107    }
108
109    /// Returns the inner value of this [InOrderIndex].
110    pub fn inner(&self) -> u64 {
111        self.idx as u64
112    }
113}
114
115// CONVERSIONS FROM IN-ORDER INDEX
116// ------------------------------------------------------------------------------------------------
117
118impl From<InOrderIndex> for u64 {
119    fn from(index: InOrderIndex) -> Self {
120        index.idx as u64
121    }
122}
123
124// TESTS
125// ================================================================================================
126
127#[cfg(test)]
128mod test {
129    use proptest::prelude::*;
130
131    use super::InOrderIndex;
132
133    proptest! {
134        #[test]
135        fn proptest_inorder_index_random(count in 1..1000usize) {
136            let left_pos = count * 2;
137            let right_pos = count * 2 + 1;
138
139            let left = InOrderIndex::from_leaf_pos(left_pos);
140            let right = InOrderIndex::from_leaf_pos(right_pos);
141
142            assert!(left.is_leaf());
143            assert!(right.is_leaf());
144            assert_eq!(left.parent(), right.parent());
145            assert_eq!(left.parent().right_child(), right);
146            assert_eq!(left, right.parent().left_child());
147            assert_eq!(left.sibling(), right);
148            assert_eq!(left, right.sibling());
149        }
150    }
151
152    #[test]
153    fn test_inorder_index_basic() {
154        let left = InOrderIndex::from_leaf_pos(0);
155        let right = InOrderIndex::from_leaf_pos(1);
156
157        assert!(left.is_leaf());
158        assert!(right.is_leaf());
159        assert_eq!(left.parent(), right.parent());
160        assert_eq!(left.parent().right_child(), right);
161        assert_eq!(left, right.parent().left_child());
162        assert_eq!(left.sibling(), right);
163        assert_eq!(left, right.sibling());
164    }
165}