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
146
147
148

use super::*;
use bitstring::BitString;
use std::option::Option;

#[derive(Clone, Copy, PartialEq, Eq)]
enum Direction {
	Down,
	Left,
	Right,
	Up,
}
use self::Direction::*;

/// Iterate over tree
pub struct IterFull<'a, S: BitString + 'a> {
	stack: Vec<(Direction, &'a Node<S>)>,
	depth: usize,
}

impl<'a, S: BitString + Clone> IterFull<'a, S> {
	/// new iterator
	pub fn new(tree: &'a RadixSet<S>) -> Self {
		match tree.root() {
			None => IterFull {
				stack: Vec::new(),
				depth: 0,
			},
			Some(node) => IterFull {
				stack: vec![(Down, node)],
				depth: 0,
			},
		}
	}
}

impl<'a, S: BitString + Clone> Iterator for IterFull<'a, S> {
	type Item = (S, bool);

	fn next(&mut self) -> Option<Self::Item> {
		if self.stack.is_empty() {
			if self.depth == 0 {
				// empty tree and first call
				self.depth = !0;
				return Some((S::null(), false));
			} else {
				return None;
			}
		}

		// go up in tree from last visited node
		while Up == self.stack[self.stack.len() - 1].0 {
			if 0 == self.depth {
				// all done
				debug_assert_eq!(1, self.stack.len());
				self.stack.clear();
				self.depth = !0;
				return None;
			}

			if self.stack.len() > 1 {
				// next node up the tree must be an inner node, and
				// covers the first bit of both branches
				let up_len = self.stack[self.stack.len() - 2].1.key().len();
				if self.depth - 1 == up_len {
					// done walking up this branch
					self.stack.pop();
					self.depth = up_len;
					debug_assert!(!self.stack.is_empty());
					// stack cannot be empty yet!
					continue;
				}
			}

			// still walking up current branch
			let key = self.stack[self.stack.len() - 1].1.key();
			self.depth -= 1;
			if key.get(self.depth) {
				// already walked that side when going Down
			} else {
				let mut key = key.clone();
				key.clip(self.depth + 1);
				key.flip(self.depth);
				return Some((key, false));
			}
		}

		loop {
			let top = self.stack.len() - 1;
			let (dir, node) = self.stack[top];

			debug_assert!(!self.stack.is_empty());
			// go down in tree to next node
			match dir {
				Down => loop {
					let key = node.key();
					// next node up the tree must be an inner node, and
					// covers the first bit of both branches
					let key_len = key.len();
					if self.depth == key_len {
						// done walking down this branch
						self.stack[top].0 = Left;
						break;
					}

					debug_assert!(self.depth < key_len);

					// still walking down current branch
					if key.get(self.depth) {
						let mut key = key.clone();
						key.flip(self.depth);
						self.depth += 1;
						key.clip(self.depth);
						return Some((key, false));
					} else {
						// will walk that side when going Up
						self.depth += 1;
					}
				},
				Left => {
					debug_assert_eq!(self.depth, node.key().len());
					match *node {
						Node::InnerNode(ref inner) => {
							self.stack[top].0 = Right;
							self.stack.push((Down, inner.left()));
							self.depth += 1;
						},
						Node::Leaf(ref leaf) => {
							self.stack[top].0 = Up;
							return Some((leaf.key.clone(), true));
						},
					}
				},
				Right => {
					debug_assert_eq!(self.depth, node.key().len());
					match *node {
						Node::InnerNode(ref inner) => {
							self.stack[top].0 = Up;
							self.stack.push((Down, inner.right()));
							self.depth += 1;
						},
						Node::Leaf(_) => unreachable!(),
					}
				},
				Up => unreachable!(),
			}
		}
	}
}