tree 0.4.1

An ordered map and set based on a binary search 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
109
110
111
112
113
114
115
116
117
118

extern crate quickcheck;

use self::quickcheck::{Arbitrary, Gen, Rng, TestResult, quickcheck};
use super::{Link, Node};
use Map;

/// An operation on a `Map`.
#[derive(Clone, Debug)]
enum Op<K> where K: Clone + Ord {
    /// Insert a key into the map.
    Insert(K),
    /// Remove the key at index `n % map.len()` from the map.
    Remove(usize),
    /// Remove the maximum key.
    RemoveMax,
    /// Remove the minimum key.
    RemoveMin,
    /// Insert a key into the map using the entry API.
    EntryInsert(K),
    /// Remove the key at index `n % map.len()` from the map using the entry API.
    EntryRemove(usize),
}

impl<K> Arbitrary for Op<K> where K: Arbitrary + Ord {
    fn arbitrary<G: Gen>(gen: &mut G) -> Self {
        match gen.gen_range(0, 6) {
            0 => Op::Insert(K::arbitrary(gen)),
            1 => Op::Remove(usize::arbitrary(gen)),
            2 => Op::RemoveMax,
            3 => Op::RemoveMin,
            4 => Op::EntryInsert(K::arbitrary(gen)),
            _ => Op::EntryRemove(usize::arbitrary(gen)),
        }
    }

    fn shrink(&self) -> Box<Iterator<Item=Self>> {
        match *self {
            Op::Insert(ref key) => Box::new(key.shrink().map(Op::Insert)),
            Op::Remove(index) => Box::new(index.shrink().map(Op::Remove)),
            Op::RemoveMax | Op::RemoveMin => Box::new(None.into_iter()),
            Op::EntryInsert(ref key) => Box::new(key.shrink().map(Op::EntryInsert)),
            Op::EntryRemove(index) => Box::new(index.shrink().map(Op::EntryRemove)),
        }
    }
}

impl<K> Op<K> where K: Clone + Ord {
    /// Perform the operation on the given map.
    fn exec(self, map: &mut Map<K, ()>) {
        match self {
            Op::Insert(key) => { map.insert(key, ()); }
            Op::Remove(index) => if !map.is_empty() {
                let key = map.iter().nth(index % map.len()).unwrap().0.clone();
                map.remove(&key);
            },
            Op::RemoveMax => { map.remove_max(); }
            Op::RemoveMin => { map.remove_min(); }
            Op::EntryInsert(key) => { map.entry(key).or_insert(()); }
            Op::EntryRemove(index) => if !map.is_empty() {
                use map::Entry;

                let key = map.iter().nth(index % map.len()).unwrap().0.clone();

                match map.entry(key) {
                    Entry::Occupied(e) => { e.remove(); }
                    Entry::Vacant(_) => panic!("expected an occupied entry"),
                }
            },
        }
    }
}

// Adapted from https://github.com/Gankro/collect-rs/tree/map.rs
fn assert_andersson_tree<K, V>(map: &Map<K, V>) where K: Ord {
    fn check_left<K, V>(link: &Link<K, V>, parent: &Node<K, V>) where K: Ord {
        match *link {
            None => assert_eq!(parent.level, 1),
            Some(ref node) => {
                assert!(node.key < parent.key);
                assert_eq!(node.level, parent.level - 1);
                check_left(&node.left, node);
                check_right(&node.right, node, false);
            }
        }
    }

    fn check_right<K, V>(link: &Link<K, V>, parent: &Node<K, V>, parent_red: bool) where K: Ord {
        match *link {
            None => assert_eq!(parent.level, 1),
            Some(ref node) => {
                assert!(node.key > parent.key);
                let red = node.level == parent.level;
                if parent_red { assert!(!red); }
                assert!(red || node.level == parent.level - 1);
                check_left(&node.left, node);
                check_right(&node.right, node, red);
            }
        }
    }

    if let Some(ref node) = *map.root() {
        check_left(&node.left, node);
        check_right(&node.right, node, false);
    }
}

#[test]
#[allow(trivial_casts)]
fn test_andersson() {
    fn check(ops: Vec<Op<u32>>) -> TestResult {
        let mut map = Map::new();
        for op in ops { op.exec(&mut map); }
        assert_andersson_tree(&map);
        TestResult::passed()
    }

    quickcheck(check as fn(Vec<Op<u32>>) -> TestResult);
}