gavl 0.1.5

A fast implementation for a map and a set using an AVL tree
Documentation 
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

use std::{
    marker::PhantomData,
};

use super::{
    super::{
        structs::{
            Side,
        },
        Map,
        MapLink,
    },
};

/// # Dependant on feature unchecked_mut
/// Returns a mutable reference to both the key and the content, it is dangerous to modify the key
/// since the tree wont autobalance.
/// 
/// For this reason you should make sure that  for each `Key1 > Key0` the transformation applied to 
/// the key `t(Key1) > t(Key0)` can be granted.
pub struct IterMutUnchecked<'a, KeyType:Ord, ContentType> (
    IterMutUncheckedEnum<'a, KeyType, ContentType>
);

enum IterMutUncheckedEnum<'a, KeyType:Ord, ContentType> {
    NewIter(&'a mut Map<KeyType, ContentType>),
    Iter{
        current: MapLink<KeyType, ContentType>,
        phantom0: PhantomData<&'a mut KeyType>,
        phantom1: PhantomData<&'a mut ContentType>,
    }
}

impl<'a, KeyType:Ord, ContentType> IterMutUnchecked<'a, KeyType, ContentType> {
    pub(crate) fn new(map:&'a mut Map<KeyType, ContentType>) -> Self {
        IterMutUnchecked(
            IterMutUncheckedEnum::NewIter(map)
        )
    }
}


impl<'a, KeyType:Ord, ContentType> Iterator for IterMutUnchecked<'a, KeyType, ContentType> {
    type Item = (&'a mut KeyType, &'a mut ContentType);
    
    fn next(&mut self) -> Option<Self::Item> {
        match &mut self.0 {
            IterMutUncheckedEnum::NewIter(map) => {
                let mut pivot = match map.head {
                    Some(head) => head,
                    None => {return None;}
                };
                loop {
                    let pivot_mut = unsafe{pivot.as_mut()};
                    match pivot_mut.son[Side::Left] {
                        None => {
                            *self = IterMutUnchecked(IterMutUncheckedEnum::Iter{current:pivot, phantom0:PhantomData, phantom1:PhantomData});
                            
                            return Some((&mut pivot_mut.key, &mut pivot_mut.content));
                        },
                        Some(new_pivot) => {
                            pivot = new_pivot;
                        }
                    }
                }
            },
            IterMutUncheckedEnum::Iter{
                ref mut current,
                ..
            } => {
                let pivot_or_nothing = Map::next_node(*current);
                match pivot_or_nothing {
                    None => None,
                    Some(mut pivot) => {
                        let pivot_mut = unsafe{pivot.as_mut()};
                        *current = pivot;
                        Some((&mut pivot_mut.key, &mut pivot_mut.content))
                    }
                }
            },
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use crate::test::*;
    
    #[test]
    fn test() {
        let mut avl = Map::<u64,u64>::new();
        for number in 4+0..4+7 {
            avl.add(number, 0).unwrap();
        }
        println!("{:#?}", &avl);
        let iter_level = avl.iter_ref_mut_unchecked();//.enumerate();
        for elem in iter_level {
            print_type_of(&elem);
            println!("{:?}", &elem);
            *elem.0 += 8;
            *elem.1 += 1;
            println!("{:?}", &elem);
        }
        println!("{:#?}", &avl);
    }
}