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

use std::slice;
use std::iter::{Map, FilterMap};

use Trie;

// MY EYES.
type Child<K, V> = Box<Trie<K, V>>;
type RawChildIter<'a, K, V> = slice::Iter<'a, Option<Child<K, V>>>;
type ChildMapFn<'a, K, V> = fn(&'a Option<Child<K, V>>) -> Option<&'a Child<K, V>>;
type ChildIter<'a, K, V> = FilterMap<RawChildIter<'a, K, V>, ChildMapFn<'a, K, V>>;

/// Iterator over the keys and values of a Trie.
pub struct Iter<'a, K: 'a, V: 'a> {
    root: &'a Trie<K, V>,
    root_visited: bool,
    stack: Vec<ChildIter<'a, K, V>>
}

impl<'a, K, V> Iter<'a, K, V> {
    pub fn new(root: &Trie<K, V>) -> Iter<K, V> {
        Iter {
            root: root,
            root_visited: false,
            stack: vec![]
        }
    }
}

/// Iterator over the keys of a Trie.
pub struct Keys<'a, K: 'a, V: 'a> {
    inner: Map<Iter<'a, K, V>, KeyMapFn<'a, K, V>>
}

type KeyMapFn<'a, K, V> = fn((&'a K, &'a V)) -> &'a K;

impl<'a, K, V> Keys<'a, K, V> {
    pub fn new(iter: Iter<'a, K, V>) -> Keys<'a, K, V> {
        fn first<'b, K, V>((k, _): (&'b K, &'b V)) -> &'b K { k }
        Keys { inner: iter.map(first) }
    }
}

impl<'a, K, V> Iterator for Keys<'a, K, V> {
    type Item = &'a K;

    fn next(&mut self) -> Option<&'a K> {
        self.inner.next()
    }
}

/// Iterator over the values of a Trie.
pub struct Values<'a, K: 'a, V: 'a> {
    inner: Map<Iter<'a, K, V>, ValueMapFn<'a, K, V>>
}

type ValueMapFn<'a, K, V> = fn((&'a K, &'a V)) -> &'a V;

impl<'a, K, V> Values<'a, K, V> {
    pub fn new(iter: Iter<'a, K, V>) -> Values<'a, K, V> {
        fn second<'b, K, V>((_, v): (&'b K, &'b V)) -> &'b V { v }
        Values { inner: iter.map(second) }
    }
}

impl<'a, K, V> Iterator for Values<'a, K, V> {
    type Item = &'a V;

    fn next(&mut self) -> Option<&'a V> {
        self.inner.next()
    }
}

impl<K, V> Trie<K, V> {
    /// Helper function to get all the non-empty children of a node.
    fn child_iter<'a>(&'a self) -> ChildIter<'a, K, V> {
        fn id<'b, K, V>(x: &'b Option<Child<K, V>>) -> Option<&'b Child<K, V>> {
            x.as_ref()
        }

        self.children.iter().filter_map(id)
    }

    /// Get the key and value of a node as a pair.
    fn kv_as_pair<'a>(&'a self) -> Option<(&'a K, &'a V)> {
        self.key_value.as_ref().map(|kv| (&kv.key, &kv.value))
    }
}

enum IterAction<'a, K: 'a, V: 'a> {
    Push(&'a Trie<K, V>),
    Pop
}

impl<'a, K, V> Iterator for Iter<'a, K, V> {
    type Item = (&'a K, &'a V);

    fn next(&mut self) -> Option<Self::Item> {
        use self::IterAction::*;

        // Visit each node as it is reached from its parent (with special root handling).
        if !self.root_visited {
            self.root_visited = true;
            self.stack.push(self.root.child_iter());
            if let Some(kv) = self.root.kv_as_pair() {
                return Some(kv);
            }
        }

        loop {
            let action = match self.stack.last_mut() {
                Some(stack_top) => {
                    match stack_top.next() {
                        Some(child) => Push(&child),
                        None => Pop
                    }
                }
                None => return None
            };

            match action {
                Push(trie) => {
                    self.stack.push(trie.child_iter());
                    if let Some(kv) = trie.kv_as_pair() {
                        return Some(kv);
                    }
                }
                Pop => { self.stack.pop(); }
            }
        }
    }
}