1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

pub trait HeapIndex {
    fn parent(self) -> Self;
    fn grandparent(self) -> Self;

    fn child1(self) -> Self;
    fn child2(self) -> Self;

    fn grandchild1(self) -> Self;
    fn grandchild2(self) -> Self;
    fn grandchild3(self) -> Self;
    fn grandchild4(self) -> Self;

    fn has_parent(self) -> bool;
    fn has_grandparent(self) -> bool;
    fn is_min_level(self) -> bool;
}

impl HeapIndex for usize {
    fn parent(self) -> Self { (self - 1) / 2 }
    fn grandparent(self) -> Self { self.parent().parent() }

    fn child1(self) -> Self { 2 * self + 1 }
    fn child2(self) -> Self { 2 * self + 2 }

    fn grandchild1(self) -> Self { self.child1().child1() }
    fn grandchild2(self) -> Self { self.child1().child2() }
    fn grandchild3(self) -> Self { self.child2().child1() }
    fn grandchild4(self) -> Self { self.child2().child2() }

    fn has_parent(self) -> bool {
        self > 0
    }

    fn has_grandparent(self) -> bool {
        self > 2
    }

    fn is_min_level(self) -> bool {
        (self + 1).leading_zeros() & 1 == 1
    }
}

//                       0
//           1                        2
//      3         4             5           6
//    7   8     9   10       11   12     13   14

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn t_parent() {
        assert_eq!(0, 1.parent());
        assert_eq!(0, 2.parent());
        assert_eq!(1, 3.parent());
        assert_eq!(1, 4.parent());
        assert_eq!(2, 5.parent());
        assert_eq!(2, 6.parent());
        assert_eq!(5, 11.parent());
    }

    #[test]
    fn t_child1() {
        assert_eq!(1, 0.child1());
        assert_eq!(3, 1.child1());
        assert_eq!(7, 3.child1());
        assert_eq!(13, 6.child1());
    }

    #[test]
    fn t_child2() {
        assert_eq!(2, 0.child2());
        assert_eq!(4, 1.child2());
        assert_eq!(8, 3.child2());
        assert_eq!(14, 6.child2());
    }

    #[test]
    fn t_grandchild1() {
        assert_eq!(3, 0.grandchild1());
        assert_eq!(7, 1.grandchild1());
        assert_eq!(11, 2.grandchild1());
    }

    #[test]
    fn t_grandchild2() {
        assert_eq!(4, 0.grandchild2());
        assert_eq!(8, 1.grandchild2());
        assert_eq!(12, 2.grandchild2());
    }

    #[test]
    fn t_grandchild3() {
        assert_eq!(5, 0.grandchild3());
        assert_eq!(9, 1.grandchild3());
        assert_eq!(13, 2.grandchild3());
    }

    #[test]
    fn t_grandchild4() {
        assert_eq!(6, 0.grandchild4());
        assert_eq!(10, 1.grandchild4());
        assert_eq!(14, 2.grandchild4());
    }

    #[test]
    fn t_has_parent() {
        assert!(! 0.has_parent());
        assert!(1.has_parent());
        assert!(2.has_parent());
        assert!(3.has_parent());
    }

    #[test]
    fn t_has_grandparent() {
        assert!(! 0.has_grandparent());
        assert!(! 1.has_grandparent());
        assert!(! 2.has_grandparent());
        assert!(3.has_grandparent());
        assert!(4.has_grandparent());
        assert!(5.has_grandparent());
        assert!(6.has_grandparent());
    }

    #[test]
    fn t_is_min_level() {
        assert!(0.is_min_level());
        assert!(!1.is_min_level());
        assert!(!2.is_min_level());
        assert!(3.is_min_level());
        assert!(4.is_min_level());
        assert!(5.is_min_level());
        assert!(6.is_min_level());
        assert!(!7.is_min_level());
        assert!(!8.is_min_level());
        assert!(!9.is_min_level());
        assert!(!10.is_min_level());
        assert!(!11.is_min_level());
        assert!(!12.is_min_level());
        assert!(!13.is_min_level());
        assert!(!14.is_min_level());
        assert!(15.is_min_level());
    }
}