]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | // This implementation is largely based on the high-level description and analysis of B-Trees | |
12 | // found in *Open Data Structures* (ODS). Although our implementation does not use any of | |
13 | // the source found in ODS, if one wishes to review the high-level design of this structure, it | |
14 | // can be freely downloaded at http://opendatastructures.org/. Its contents are as of this | |
15 | // writing (August 2014) freely licensed under the following Creative Commons Attribution | |
16 | // License: [CC BY 2.5 CA](http://creativecommons.org/licenses/by/2.5/ca/). | |
17 | ||
85aaf69f | 18 | use self::Entry::*; |
1a4d82fc JJ |
19 | |
20 | use core::prelude::*; | |
21 | ||
1a4d82fc | 22 | use core::cmp::Ordering; |
85aaf69f | 23 | use core::fmt::Debug; |
1a4d82fc | 24 | use core::hash::{Hash, Hasher}; |
9346a6ac | 25 | use core::iter::{Map, FromIterator}; |
c34b1796 AL |
26 | use core::ops::Index; |
27 | use core::{iter, fmt, mem, usize}; | |
85aaf69f | 28 | use Bound::{self, Included, Excluded, Unbounded}; |
1a4d82fc | 29 | |
85aaf69f SL |
30 | use borrow::Borrow; |
31 | use vec_deque::VecDeque; | |
1a4d82fc JJ |
32 | |
33 | use self::Continuation::{Continue, Finished}; | |
34 | use self::StackOp::*; | |
35 | use super::node::ForceResult::{Leaf, Internal}; | |
36 | use super::node::TraversalItem::{self, Elem, Edge}; | |
37 | use super::node::{Traversal, MutTraversal, MoveTraversal}; | |
38 | use super::node::{self, Node, Found, GoDown}; | |
39 | ||
1a4d82fc JJ |
40 | /// A map based on a B-Tree. |
41 | /// | |
42 | /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing | |
43 | /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal | |
44 | /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of | |
45 | /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this | |
46 | /// is done is *very* inefficient for modern computer architectures. In particular, every element | |
47 | /// is stored in its own individually heap-allocated node. This means that every single insertion | |
48 | /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these | |
49 | /// are both notably expensive things to do in practice, we are forced to at very least reconsider | |
50 | /// the BST strategy. | |
51 | /// | |
52 | /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing | |
53 | /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in | |
54 | /// searches. However, this does mean that searches will have to do *more* comparisons on average. | |
55 | /// The precise number of comparisons depends on the node search strategy used. For optimal cache | |
56 | /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search | |
57 | /// the node using binary search. As a compromise, one could also perform a linear search | |
58 | /// that initially only checks every i<sup>th</sup> element for some choice of i. | |
59 | /// | |
60 | /// Currently, our implementation simply performs naive linear search. This provides excellent | |
61 | /// performance on *small* nodes of elements which are cheap to compare. However in the future we | |
62 | /// would like to further explore choosing the optimal search strategy based on the choice of B, | |
63 | /// and possibly other factors. Using linear search, searching for a random element is expected | |
64 | /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice, | |
85aaf69f | 65 | /// however, performance is excellent. |
c34b1796 AL |
66 | /// |
67 | /// It is a logic error for a key to be modified in such a way that the key's ordering relative to | |
68 | /// any other key, as determined by the `Ord` trait, changes while it is in the map. This is | |
69 | /// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code. | |
1a4d82fc | 70 | #[derive(Clone)] |
85aaf69f | 71 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
72 | pub struct BTreeMap<K, V> { |
73 | root: Node<K, V>, | |
85aaf69f SL |
74 | length: usize, |
75 | depth: usize, | |
76 | b: usize, | |
1a4d82fc JJ |
77 | } |
78 | ||
79 | /// An abstract base over-which all other BTree iterators are built. | |
c34b1796 | 80 | #[derive(Clone)] |
1a4d82fc | 81 | struct AbsIter<T> { |
85aaf69f SL |
82 | traversals: VecDeque<T>, |
83 | size: usize, | |
1a4d82fc JJ |
84 | } |
85 | ||
86 | /// An iterator over a BTreeMap's entries. | |
85aaf69f | 87 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
88 | pub struct Iter<'a, K: 'a, V: 'a> { |
89 | inner: AbsIter<Traversal<'a, K, V>> | |
90 | } | |
91 | ||
92 | /// A mutable iterator over a BTreeMap's entries. | |
85aaf69f | 93 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
94 | pub struct IterMut<'a, K: 'a, V: 'a> { |
95 | inner: AbsIter<MutTraversal<'a, K, V>> | |
96 | } | |
97 | ||
98 | /// An owning iterator over a BTreeMap's entries. | |
85aaf69f | 99 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
100 | pub struct IntoIter<K, V> { |
101 | inner: AbsIter<MoveTraversal<K, V>> | |
102 | } | |
103 | ||
104 | /// An iterator over a BTreeMap's keys. | |
85aaf69f | 105 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 106 | pub struct Keys<'a, K: 'a, V: 'a> { |
85aaf69f | 107 | inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K> |
1a4d82fc JJ |
108 | } |
109 | ||
110 | /// An iterator over a BTreeMap's values. | |
85aaf69f | 111 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 112 | pub struct Values<'a, K: 'a, V: 'a> { |
85aaf69f SL |
113 | inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V> |
114 | } | |
115 | ||
116 | /// An iterator over a sub-range of BTreeMap's entries. | |
117 | pub struct Range<'a, K: 'a, V: 'a> { | |
118 | inner: AbsIter<Traversal<'a, K, V>> | |
119 | } | |
120 | ||
121 | /// A mutable iterator over a sub-range of BTreeMap's entries. | |
122 | pub struct RangeMut<'a, K: 'a, V: 'a> { | |
123 | inner: AbsIter<MutTraversal<'a, K, V>> | |
1a4d82fc JJ |
124 | } |
125 | ||
126 | /// A view into a single entry in a map, which may either be vacant or occupied. | |
c34b1796 | 127 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
128 | pub enum Entry<'a, K:'a, V:'a> { |
129 | /// A vacant Entry | |
c34b1796 | 130 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 131 | Vacant(VacantEntry<'a, K, V>), |
c34b1796 | 132 | |
1a4d82fc | 133 | /// An occupied Entry |
c34b1796 | 134 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
135 | Occupied(OccupiedEntry<'a, K, V>), |
136 | } | |
137 | ||
138 | /// A vacant Entry. | |
c34b1796 | 139 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
140 | pub struct VacantEntry<'a, K:'a, V:'a> { |
141 | key: K, | |
142 | stack: stack::SearchStack<'a, K, V, node::handle::Edge, node::handle::Leaf>, | |
143 | } | |
144 | ||
145 | /// An occupied Entry. | |
c34b1796 | 146 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
147 | pub struct OccupiedEntry<'a, K:'a, V:'a> { |
148 | stack: stack::SearchStack<'a, K, V, node::handle::KV, node::handle::LeafOrInternal>, | |
149 | } | |
150 | ||
151 | impl<K: Ord, V> BTreeMap<K, V> { | |
152 | /// Makes a new empty BTreeMap with a reasonable choice for B. | |
85aaf69f | 153 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
154 | pub fn new() -> BTreeMap<K, V> { |
155 | //FIXME(Gankro): Tune this as a function of size_of<K/V>? | |
156 | BTreeMap::with_b(6) | |
157 | } | |
158 | ||
159 | /// Makes a new empty BTreeMap with the given B. | |
160 | /// | |
161 | /// B cannot be less than 2. | |
85aaf69f | 162 | pub fn with_b(b: usize) -> BTreeMap<K, V> { |
1a4d82fc JJ |
163 | assert!(b > 1, "B must be greater than 1"); |
164 | BTreeMap { | |
165 | length: 0, | |
166 | depth: 1, | |
167 | root: Node::make_leaf_root(b), | |
168 | b: b, | |
169 | } | |
170 | } | |
171 | ||
172 | /// Clears the map, removing all values. | |
173 | /// | |
174 | /// # Examples | |
175 | /// | |
176 | /// ``` | |
177 | /// use std::collections::BTreeMap; | |
178 | /// | |
179 | /// let mut a = BTreeMap::new(); | |
85aaf69f | 180 | /// a.insert(1, "a"); |
1a4d82fc JJ |
181 | /// a.clear(); |
182 | /// assert!(a.is_empty()); | |
183 | /// ``` | |
85aaf69f | 184 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
185 | pub fn clear(&mut self) { |
186 | let b = self.b; | |
187 | // avoid recursive destructors by manually traversing the tree | |
85aaf69f | 188 | for _ in mem::replace(self, BTreeMap::with_b(b)) {}; |
1a4d82fc JJ |
189 | } |
190 | ||
191 | // Searching in a B-Tree is pretty straightforward. | |
192 | // | |
193 | // Start at the root. Try to find the key in the current node. If we find it, return it. | |
194 | // If it's not in there, follow the edge *before* the smallest key larger than | |
195 | // the search key. If no such key exists (they're *all* smaller), then just take the last | |
196 | // edge in the node. If we're in a leaf and we don't find our key, then it's not | |
197 | // in the tree. | |
198 | ||
199 | /// Returns a reference to the value corresponding to the key. | |
200 | /// | |
201 | /// The key may be any borrowed form of the map's key type, but the ordering | |
202 | /// on the borrowed form *must* match the ordering on the key type. | |
203 | /// | |
204 | /// # Examples | |
205 | /// | |
206 | /// ``` | |
207 | /// use std::collections::BTreeMap; | |
208 | /// | |
209 | /// let mut map = BTreeMap::new(); | |
85aaf69f | 210 | /// map.insert(1, "a"); |
1a4d82fc JJ |
211 | /// assert_eq!(map.get(&1), Some(&"a")); |
212 | /// assert_eq!(map.get(&2), None); | |
213 | /// ``` | |
85aaf69f SL |
214 | #[stable(feature = "rust1", since = "1.0.0")] |
215 | pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord { | |
1a4d82fc JJ |
216 | let mut cur_node = &self.root; |
217 | loop { | |
218 | match Node::search(cur_node, key) { | |
219 | Found(handle) => return Some(handle.into_kv().1), | |
220 | GoDown(handle) => match handle.force() { | |
221 | Leaf(_) => return None, | |
222 | Internal(internal_handle) => { | |
223 | cur_node = internal_handle.into_edge(); | |
224 | continue; | |
225 | } | |
226 | } | |
227 | } | |
228 | } | |
229 | } | |
230 | ||
231 | /// Returns true if the map contains a value for the specified key. | |
232 | /// | |
233 | /// The key may be any borrowed form of the map's key type, but the ordering | |
234 | /// on the borrowed form *must* match the ordering on the key type. | |
235 | /// | |
236 | /// # Examples | |
237 | /// | |
238 | /// ``` | |
239 | /// use std::collections::BTreeMap; | |
240 | /// | |
241 | /// let mut map = BTreeMap::new(); | |
85aaf69f | 242 | /// map.insert(1, "a"); |
1a4d82fc JJ |
243 | /// assert_eq!(map.contains_key(&1), true); |
244 | /// assert_eq!(map.contains_key(&2), false); | |
245 | /// ``` | |
85aaf69f SL |
246 | #[stable(feature = "rust1", since = "1.0.0")] |
247 | pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord { | |
1a4d82fc JJ |
248 | self.get(key).is_some() |
249 | } | |
250 | ||
251 | /// Returns a mutable reference to the value corresponding to the key. | |
252 | /// | |
253 | /// The key may be any borrowed form of the map's key type, but the ordering | |
254 | /// on the borrowed form *must* match the ordering on the key type. | |
255 | /// | |
256 | /// # Examples | |
257 | /// | |
258 | /// ``` | |
259 | /// use std::collections::BTreeMap; | |
260 | /// | |
261 | /// let mut map = BTreeMap::new(); | |
85aaf69f | 262 | /// map.insert(1, "a"); |
9346a6ac AL |
263 | /// if let Some(x) = map.get_mut(&1) { |
264 | /// *x = "b"; | |
1a4d82fc | 265 | /// } |
c34b1796 | 266 | /// assert_eq!(map[&1], "b"); |
1a4d82fc JJ |
267 | /// ``` |
268 | // See `get` for implementation notes, this is basically a copy-paste with mut's added | |
85aaf69f SL |
269 | #[stable(feature = "rust1", since = "1.0.0")] |
270 | pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord { | |
1a4d82fc JJ |
271 | // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration |
272 | let mut temp_node = &mut self.root; | |
273 | loop { | |
274 | let cur_node = temp_node; | |
275 | match Node::search(cur_node, key) { | |
276 | Found(handle) => return Some(handle.into_kv_mut().1), | |
277 | GoDown(handle) => match handle.force() { | |
278 | Leaf(_) => return None, | |
279 | Internal(internal_handle) => { | |
280 | temp_node = internal_handle.into_edge_mut(); | |
281 | continue; | |
282 | } | |
283 | } | |
284 | } | |
285 | } | |
286 | } | |
287 | ||
288 | // Insertion in a B-Tree is a bit complicated. | |
289 | // | |
290 | // First we do the same kind of search described in `find`. But we need to maintain a stack of | |
291 | // all the nodes/edges in our search path. If we find a match for the key we're trying to | |
292 | // insert, just swap the vals and return the old ones. However, when we bottom out in a leaf, | |
293 | // we attempt to insert our key-value pair at the same location we would want to follow another | |
294 | // edge. | |
295 | // | |
296 | // If the node has room, then this is done in the obvious way by shifting elements. However, | |
297 | // if the node itself is full, we split node into two, and give its median key-value | |
298 | // pair to its parent to insert the new node with. Of course, the parent may also be | |
299 | // full, and insertion can propagate until we reach the root. If we reach the root, and | |
300 | // it is *also* full, then we split the root and place the two nodes under a newly made root. | |
301 | // | |
302 | // Note that we subtly deviate from Open Data Structures in our implementation of split. | |
303 | // ODS describes inserting into the node *regardless* of its capacity, and then | |
304 | // splitting *afterwards* if it happens to be overfull. However, this is inefficient. | |
305 | // Instead, we split beforehand, and then insert the key-value pair into the appropriate | |
306 | // result node. This has two consequences: | |
307 | // | |
308 | // 1) While ODS produces a left node of size B-1, and a right node of size B, | |
309 | // we may potentially reverse this. However, this shouldn't effect the analysis. | |
310 | // | |
311 | // 2) While ODS may potentially return the pair we *just* inserted after | |
312 | // the split, we will never do this. Again, this shouldn't effect the analysis. | |
313 | ||
9346a6ac | 314 | /// Inserts a key-value pair into the map. If the key already had a value |
1a4d82fc JJ |
315 | /// present in the map, that value is returned. Otherwise, `None` is returned. |
316 | /// | |
317 | /// # Examples | |
318 | /// | |
319 | /// ``` | |
320 | /// use std::collections::BTreeMap; | |
321 | /// | |
322 | /// let mut map = BTreeMap::new(); | |
85aaf69f | 323 | /// assert_eq!(map.insert(37, "a"), None); |
1a4d82fc JJ |
324 | /// assert_eq!(map.is_empty(), false); |
325 | /// | |
326 | /// map.insert(37, "b"); | |
327 | /// assert_eq!(map.insert(37, "c"), Some("b")); | |
c34b1796 | 328 | /// assert_eq!(map[&37], "c"); |
1a4d82fc | 329 | /// ``` |
85aaf69f | 330 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
331 | pub fn insert(&mut self, mut key: K, mut value: V) -> Option<V> { |
332 | // This is a stack of rawptrs to nodes paired with indices, respectively | |
333 | // representing the nodes and edges of our search path. We have to store rawptrs | |
334 | // because as far as Rust is concerned, we can mutate aliased data with such a | |
335 | // stack. It is of course correct, but what it doesn't know is that we will only | |
336 | // be popping and using these ptrs one at a time in child-to-parent order. The alternative | |
337 | // to doing this is to take the Nodes from their parents. This actually makes | |
338 | // borrowck *really* happy and everything is pretty smooth. However, this creates | |
339 | // *tons* of pointless writes, and requires us to always walk all the way back to | |
340 | // the root after an insertion, even if we only needed to change a leaf. Therefore, | |
341 | // we accept this potential unsafety and complexity in the name of performance. | |
342 | // | |
343 | // Regardless, the actual dangerous logic is completely abstracted away from BTreeMap | |
344 | // by the stack module. All it can do is immutably read nodes, and ask the search stack | |
345 | // to proceed down some edge by index. This makes the search logic we'll be reusing in a | |
346 | // few different methods much neater, and of course drastically improves safety. | |
347 | let mut stack = stack::PartialSearchStack::new(self); | |
348 | ||
349 | loop { | |
350 | let result = stack.with(move |pusher, node| { | |
351 | // Same basic logic as found in `find`, but with PartialSearchStack mediating the | |
352 | // actual nodes for us | |
c34b1796 | 353 | match Node::search(node, &key) { |
1a4d82fc JJ |
354 | Found(mut handle) => { |
355 | // Perfect match, swap the values and return the old one | |
356 | mem::swap(handle.val_mut(), &mut value); | |
357 | Finished(Some(value)) | |
358 | }, | |
359 | GoDown(handle) => { | |
360 | // We need to keep searching, try to get the search stack | |
361 | // to go down further | |
362 | match handle.force() { | |
363 | Leaf(leaf_handle) => { | |
364 | // We've reached a leaf, perform the insertion here | |
365 | pusher.seal(leaf_handle).insert(key, value); | |
366 | Finished(None) | |
367 | } | |
368 | Internal(internal_handle) => { | |
369 | // We've found the subtree to insert this key/value pair in, | |
370 | // keep searching | |
371 | Continue((pusher.push(internal_handle), key, value)) | |
372 | } | |
373 | } | |
374 | } | |
375 | } | |
376 | }); | |
377 | match result { | |
c34b1796 | 378 | Finished(ret) => return ret, |
1a4d82fc JJ |
379 | Continue((new_stack, renewed_key, renewed_val)) => { |
380 | stack = new_stack; | |
381 | key = renewed_key; | |
382 | value = renewed_val; | |
383 | } | |
384 | } | |
385 | } | |
386 | } | |
387 | ||
388 | // Deletion is the most complicated operation for a B-Tree. | |
389 | // | |
390 | // First we do the same kind of search described in | |
391 | // `find`. But we need to maintain a stack of all the nodes/edges in our search path. | |
392 | // If we don't find the key, then we just return `None` and do nothing. If we do find the | |
393 | // key, we perform two operations: remove the item, and then possibly handle underflow. | |
394 | // | |
395 | // # removing the item | |
396 | // If the node is a leaf, we just remove the item, and shift | |
397 | // any items after it back to fill the hole. | |
398 | // | |
399 | // If the node is an internal node, we *swap* the item with the smallest item in | |
400 | // in its right subtree (which must reside in a leaf), and then revert to the leaf | |
401 | // case | |
402 | // | |
403 | // # handling underflow | |
404 | // After removing an item, there may be too few items in the node. We want nodes | |
405 | // to be mostly full for efficiency, although we make an exception for the root, which | |
406 | // may have as few as one item. If this is the case, we may first try to steal | |
407 | // an item from our left or right neighbour. | |
408 | // | |
409 | // To steal from the left (right) neighbour, | |
410 | // we take the largest (smallest) item and child from it. We then swap the taken item | |
411 | // with the item in their mutual parent that separates them, and then insert the | |
412 | // parent's item and the taken child into the first (last) index of the underflowed node. | |
413 | // | |
414 | // However, stealing has the possibility of underflowing our neighbour. If this is the | |
415 | // case, we instead *merge* with our neighbour. This of course reduces the number of | |
416 | // children in the parent. Therefore, we also steal the item that separates the now | |
417 | // merged nodes, and insert it into the merged node. | |
418 | // | |
419 | // Merging may cause the parent to underflow. If this is the case, then we must repeat | |
420 | // the underflow handling process on the parent. If merging merges the last two children | |
421 | // of the root, then we replace the root with the merged node. | |
422 | ||
423 | /// Removes a key from the map, returning the value at the key if the key | |
424 | /// was previously in the map. | |
425 | /// | |
426 | /// The key may be any borrowed form of the map's key type, but the ordering | |
427 | /// on the borrowed form *must* match the ordering on the key type. | |
428 | /// | |
429 | /// # Examples | |
430 | /// | |
431 | /// ``` | |
432 | /// use std::collections::BTreeMap; | |
433 | /// | |
434 | /// let mut map = BTreeMap::new(); | |
85aaf69f | 435 | /// map.insert(1, "a"); |
1a4d82fc JJ |
436 | /// assert_eq!(map.remove(&1), Some("a")); |
437 | /// assert_eq!(map.remove(&1), None); | |
438 | /// ``` | |
85aaf69f SL |
439 | #[stable(feature = "rust1", since = "1.0.0")] |
440 | pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord { | |
1a4d82fc JJ |
441 | // See `swap` for a more thorough description of the stuff going on in here |
442 | let mut stack = stack::PartialSearchStack::new(self); | |
443 | loop { | |
444 | let result = stack.with(move |pusher, node| { | |
c34b1796 | 445 | match Node::search(node, key) { |
1a4d82fc JJ |
446 | Found(handle) => { |
447 | // Perfect match. Terminate the stack here, and remove the entry | |
448 | Finished(Some(pusher.seal(handle).remove())) | |
449 | }, | |
450 | GoDown(handle) => { | |
451 | // We need to keep searching, try to go down the next edge | |
452 | match handle.force() { | |
453 | // We're at a leaf; the key isn't in here | |
454 | Leaf(_) => Finished(None), | |
455 | Internal(internal_handle) => Continue(pusher.push(internal_handle)) | |
456 | } | |
457 | } | |
458 | } | |
459 | }); | |
460 | match result { | |
461 | Finished(ret) => return ret, | |
462 | Continue(new_stack) => stack = new_stack | |
463 | } | |
464 | } | |
465 | } | |
466 | } | |
467 | ||
85aaf69f SL |
468 | #[stable(feature = "rust1", since = "1.0.0")] |
469 | impl<K, V> IntoIterator for BTreeMap<K, V> { | |
470 | type Item = (K, V); | |
471 | type IntoIter = IntoIter<K, V>; | |
472 | ||
9346a6ac AL |
473 | /// Gets an owning iterator over the entries of the map. |
474 | /// | |
475 | /// # Examples | |
476 | /// | |
477 | /// ``` | |
478 | /// use std::collections::BTreeMap; | |
479 | /// | |
480 | /// let mut map = BTreeMap::new(); | |
481 | /// map.insert(1, "a"); | |
482 | /// map.insert(2, "b"); | |
483 | /// map.insert(3, "c"); | |
484 | /// | |
485 | /// for (key, value) in map.into_iter() { | |
486 | /// println!("{}: {}", key, value); | |
487 | /// } | |
488 | /// ``` | |
85aaf69f | 489 | fn into_iter(self) -> IntoIter<K, V> { |
9346a6ac AL |
490 | let len = self.len(); |
491 | let mut lca = VecDeque::new(); | |
492 | lca.push_back(Traverse::traverse(self.root)); | |
493 | IntoIter { | |
494 | inner: AbsIter { | |
495 | traversals: lca, | |
496 | size: len, | |
497 | } | |
498 | } | |
85aaf69f SL |
499 | } |
500 | } | |
501 | ||
502 | #[stable(feature = "rust1", since = "1.0.0")] | |
503 | impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> { | |
504 | type Item = (&'a K, &'a V); | |
505 | type IntoIter = Iter<'a, K, V>; | |
506 | ||
507 | fn into_iter(self) -> Iter<'a, K, V> { | |
508 | self.iter() | |
509 | } | |
510 | } | |
511 | ||
512 | #[stable(feature = "rust1", since = "1.0.0")] | |
513 | impl<'a, K, V> IntoIterator for &'a mut BTreeMap<K, V> { | |
514 | type Item = (&'a K, &'a mut V); | |
515 | type IntoIter = IterMut<'a, K, V>; | |
516 | ||
517 | fn into_iter(mut self) -> IterMut<'a, K, V> { | |
518 | self.iter_mut() | |
519 | } | |
520 | } | |
521 | ||
1a4d82fc JJ |
522 | /// A helper enum useful for deciding whether to continue a loop since we can't |
523 | /// return from a closure | |
524 | enum Continuation<A, B> { | |
525 | Continue(A), | |
526 | Finished(B) | |
527 | } | |
528 | ||
529 | /// The stack module provides a safe interface for constructing and manipulating a stack of ptrs | |
530 | /// to nodes. By using this module much better safety guarantees can be made, and more search | |
531 | /// boilerplate gets cut out. | |
532 | mod stack { | |
533 | use core::prelude::*; | |
534 | use core::marker; | |
535 | use core::mem; | |
536 | use core::ops::{Deref, DerefMut}; | |
537 | use super::BTreeMap; | |
538 | use super::super::node::{self, Node, Fit, Split, Internal, Leaf}; | |
539 | use super::super::node::handle; | |
540 | use vec::Vec; | |
541 | ||
85aaf69f SL |
542 | struct InvariantLifetime<'id>( |
543 | marker::PhantomData<::core::cell::Cell<&'id ()>>); | |
544 | ||
545 | impl<'id> InvariantLifetime<'id> { | |
546 | fn new() -> InvariantLifetime<'id> { | |
547 | InvariantLifetime(marker::PhantomData) | |
548 | } | |
549 | } | |
550 | ||
1a4d82fc JJ |
551 | /// A generic mutable reference, identical to `&mut` except for the fact that its lifetime |
552 | /// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef` | |
553 | /// with the exact requested lifetime can be used. This is in contrast to normal references, | |
554 | /// where `&'static` can be used in any function expecting any lifetime reference. | |
555 | pub struct IdRef<'id, T: 'id> { | |
556 | inner: &'id mut T, | |
85aaf69f | 557 | _marker: InvariantLifetime<'id>, |
1a4d82fc JJ |
558 | } |
559 | ||
560 | impl<'id, T> Deref for IdRef<'id, T> { | |
561 | type Target = T; | |
562 | ||
563 | fn deref(&self) -> &T { | |
564 | &*self.inner | |
565 | } | |
566 | } | |
567 | ||
568 | impl<'id, T> DerefMut for IdRef<'id, T> { | |
569 | fn deref_mut(&mut self) -> &mut T { | |
570 | &mut *self.inner | |
571 | } | |
572 | } | |
573 | ||
574 | type StackItem<K, V> = node::Handle<*mut Node<K, V>, handle::Edge, handle::Internal>; | |
575 | type Stack<K, V> = Vec<StackItem<K, V>>; | |
576 | ||
577 | /// A `PartialSearchStack` handles the construction of a search stack. | |
578 | pub struct PartialSearchStack<'a, K:'a, V:'a> { | |
579 | map: &'a mut BTreeMap<K, V>, | |
580 | stack: Stack<K, V>, | |
581 | next: *mut Node<K, V>, | |
582 | } | |
583 | ||
584 | /// A `SearchStack` represents a full path to an element or an edge of interest. It provides | |
585 | /// methods depending on the type of what the path points to for removing an element, inserting | |
586 | /// a new element, and manipulating to element at the top of the stack. | |
587 | pub struct SearchStack<'a, K:'a, V:'a, Type, NodeType> { | |
588 | map: &'a mut BTreeMap<K, V>, | |
589 | stack: Stack<K, V>, | |
590 | top: node::Handle<*mut Node<K, V>, Type, NodeType>, | |
591 | } | |
592 | ||
593 | /// A `PartialSearchStack` that doesn't hold a a reference to the next node, and is just | |
594 | /// just waiting for a `Handle` to that next node to be pushed. See `PartialSearchStack::with` | |
595 | /// for more details. | |
596 | pub struct Pusher<'id, 'a, K:'a, V:'a> { | |
597 | map: &'a mut BTreeMap<K, V>, | |
598 | stack: Stack<K, V>, | |
85aaf69f | 599 | _marker: InvariantLifetime<'id>, |
1a4d82fc JJ |
600 | } |
601 | ||
602 | impl<'a, K, V> PartialSearchStack<'a, K, V> { | |
603 | /// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the | |
604 | /// root of the tree. | |
605 | pub fn new(map: &'a mut BTreeMap<K, V>) -> PartialSearchStack<'a, K, V> { | |
606 | let depth = map.depth; | |
607 | ||
608 | PartialSearchStack { | |
609 | next: &mut map.root as *mut _, | |
610 | map: map, | |
611 | stack: Vec::with_capacity(depth), | |
612 | } | |
613 | } | |
614 | ||
615 | /// Breaks up the stack into a `Pusher` and the next `Node`, allowing the given closure | |
616 | /// to interact with, search, and finally push the `Node` onto the stack. The passed in | |
617 | /// closure must be polymorphic on the `'id` lifetime parameter, as this statically | |
618 | /// ensures that only `Handle`s from the correct `Node` can be pushed. | |
619 | /// | |
620 | /// The reason this works is that the `Pusher` has an `'id` parameter, and will only accept | |
621 | /// handles with the same `'id`. The closure could only get references with that lifetime | |
622 | /// through its arguments or through some other `IdRef` that it has lying around. However, | |
623 | /// no other `IdRef` could possibly work - because the `'id` is held in an invariant | |
624 | /// parameter, it would need to have precisely the correct lifetime, which would mean that | |
625 | /// at least one of the calls to `with` wouldn't be properly polymorphic, wanting a | |
626 | /// specific lifetime instead of the one that `with` chooses to give it. | |
627 | /// | |
628 | /// See also Haskell's `ST` monad, which uses a similar trick. | |
629 | pub fn with<T, F: for<'id> FnOnce(Pusher<'id, 'a, K, V>, | |
630 | IdRef<'id, Node<K, V>>) -> T>(self, closure: F) -> T { | |
631 | let pusher = Pusher { | |
632 | map: self.map, | |
633 | stack: self.stack, | |
85aaf69f | 634 | _marker: InvariantLifetime::new(), |
1a4d82fc JJ |
635 | }; |
636 | let node = IdRef { | |
637 | inner: unsafe { &mut *self.next }, | |
85aaf69f | 638 | _marker: InvariantLifetime::new(), |
1a4d82fc JJ |
639 | }; |
640 | ||
641 | closure(pusher, node) | |
642 | } | |
643 | } | |
644 | ||
645 | impl<'id, 'a, K, V> Pusher<'id, 'a, K, V> { | |
646 | /// Pushes the requested child of the stack's current top on top of the stack. If the child | |
647 | /// exists, then a new PartialSearchStack is yielded. Otherwise, a VacantSearchStack is | |
648 | /// yielded. | |
649 | pub fn push(mut self, mut edge: node::Handle<IdRef<'id, Node<K, V>>, | |
650 | handle::Edge, | |
651 | handle::Internal>) | |
652 | -> PartialSearchStack<'a, K, V> { | |
653 | self.stack.push(edge.as_raw()); | |
654 | PartialSearchStack { | |
655 | map: self.map, | |
656 | stack: self.stack, | |
657 | next: edge.edge_mut() as *mut _, | |
658 | } | |
659 | } | |
660 | ||
661 | /// Converts the PartialSearchStack into a SearchStack. | |
662 | pub fn seal<Type, NodeType> | |
663 | (self, mut handle: node::Handle<IdRef<'id, Node<K, V>>, Type, NodeType>) | |
664 | -> SearchStack<'a, K, V, Type, NodeType> { | |
665 | SearchStack { | |
666 | map: self.map, | |
667 | stack: self.stack, | |
668 | top: handle.as_raw(), | |
669 | } | |
670 | } | |
671 | } | |
672 | ||
673 | impl<'a, K, V, NodeType> SearchStack<'a, K, V, handle::KV, NodeType> { | |
674 | /// Gets a reference to the value the stack points to. | |
675 | pub fn peek(&self) -> &V { | |
676 | unsafe { self.top.from_raw().into_kv().1 } | |
677 | } | |
678 | ||
679 | /// Gets a mutable reference to the value the stack points to. | |
680 | pub fn peek_mut(&mut self) -> &mut V { | |
681 | unsafe { self.top.from_raw_mut().into_kv_mut().1 } | |
682 | } | |
683 | ||
684 | /// Converts the stack into a mutable reference to the value it points to, with a lifetime | |
685 | /// tied to the original tree. | |
686 | pub fn into_top(mut self) -> &'a mut V { | |
687 | unsafe { | |
62682a34 | 688 | &mut *(self.top.from_raw_mut().val_mut() as *mut V) |
1a4d82fc JJ |
689 | } |
690 | } | |
691 | } | |
692 | ||
693 | impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::Leaf> { | |
694 | /// Removes the key and value in the top element of the stack, then handles underflows as | |
695 | /// described in BTree's pop function. | |
696 | fn remove_leaf(mut self) -> V { | |
697 | self.map.length -= 1; | |
698 | ||
699 | // Remove the key-value pair from the leaf that this search stack points to. | |
700 | // Then, note if the leaf is underfull, and promptly forget the leaf and its ptr | |
701 | // to avoid ownership issues. | |
702 | let (value, mut underflow) = unsafe { | |
703 | let (_, value) = self.top.from_raw_mut().remove_as_leaf(); | |
704 | let underflow = self.top.from_raw().node().is_underfull(); | |
705 | (value, underflow) | |
706 | }; | |
707 | ||
708 | loop { | |
709 | match self.stack.pop() { | |
710 | None => { | |
711 | // We've reached the root, so no matter what, we're done. We manually | |
712 | // access the root via the tree itself to avoid creating any dangling | |
713 | // pointers. | |
9346a6ac | 714 | if self.map.root.is_empty() && !self.map.root.is_leaf() { |
1a4d82fc JJ |
715 | // We've emptied out the root, so make its only child the new root. |
716 | // If it's a leaf, we just let it become empty. | |
717 | self.map.depth -= 1; | |
718 | self.map.root.hoist_lone_child(); | |
719 | } | |
720 | return value; | |
721 | } | |
722 | Some(mut handle) => { | |
723 | if underflow { | |
724 | // Underflow! Handle it! | |
725 | unsafe { | |
726 | handle.from_raw_mut().handle_underflow(); | |
727 | underflow = handle.from_raw().node().is_underfull(); | |
728 | } | |
729 | } else { | |
730 | // All done! | |
731 | return value; | |
732 | } | |
733 | } | |
734 | } | |
735 | } | |
736 | } | |
737 | } | |
738 | ||
739 | impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::LeafOrInternal> { | |
740 | /// Removes the key and value in the top element of the stack, then handles underflows as | |
741 | /// described in BTree's pop function. | |
742 | pub fn remove(self) -> V { | |
743 | // Ensure that the search stack goes to a leaf. This is necessary to perform deletion | |
744 | // in a BTree. Note that this may put the tree in an inconsistent state (further | |
745 | // described in into_leaf's comments), but this is immediately fixed by the | |
746 | // removing the value we want to remove | |
747 | self.into_leaf().remove_leaf() | |
748 | } | |
749 | ||
750 | /// Subroutine for removal. Takes a search stack for a key that might terminate at an | |
751 | /// internal node, and mutates the tree and search stack to *make* it a search stack | |
752 | /// for that same key that *does* terminates at a leaf. If the mutation occurs, then this | |
753 | /// leaves the tree in an inconsistent state that must be repaired by the caller by | |
754 | /// removing the entry in question. Specifically the key-value pair and its successor will | |
755 | /// become swapped. | |
756 | fn into_leaf(mut self) -> SearchStack<'a, K, V, handle::KV, handle::Leaf> { | |
757 | unsafe { | |
758 | let mut top_raw = self.top; | |
759 | let mut top = top_raw.from_raw_mut(); | |
760 | ||
761 | let key_ptr = top.key_mut() as *mut _; | |
762 | let val_ptr = top.val_mut() as *mut _; | |
763 | ||
764 | // Try to go into the right subtree of the found key to find its successor | |
765 | match top.force() { | |
766 | Leaf(mut leaf_handle) => { | |
767 | // We're a proper leaf stack, nothing to do | |
768 | return SearchStack { | |
769 | map: self.map, | |
770 | stack: self.stack, | |
771 | top: leaf_handle.as_raw() | |
772 | } | |
773 | } | |
774 | Internal(mut internal_handle) => { | |
775 | let mut right_handle = internal_handle.right_edge(); | |
776 | ||
777 | //We're not a proper leaf stack, let's get to work. | |
778 | self.stack.push(right_handle.as_raw()); | |
779 | ||
780 | let mut temp_node = right_handle.edge_mut(); | |
781 | loop { | |
782 | // Walk into the smallest subtree of this node | |
783 | let node = temp_node; | |
784 | ||
785 | match node.kv_handle(0).force() { | |
786 | Leaf(mut handle) => { | |
787 | // This node is a leaf, do the swap and return | |
788 | mem::swap(handle.key_mut(), &mut *key_ptr); | |
789 | mem::swap(handle.val_mut(), &mut *val_ptr); | |
790 | return SearchStack { | |
791 | map: self.map, | |
792 | stack: self.stack, | |
793 | top: handle.as_raw() | |
794 | } | |
795 | }, | |
796 | Internal(kv_handle) => { | |
797 | // This node is internal, go deeper | |
798 | let mut handle = kv_handle.into_left_edge(); | |
799 | self.stack.push(handle.as_raw()); | |
800 | temp_node = handle.into_edge_mut(); | |
801 | } | |
802 | } | |
803 | } | |
804 | } | |
805 | } | |
806 | } | |
807 | } | |
808 | } | |
809 | ||
810 | impl<'a, K, V> SearchStack<'a, K, V, handle::Edge, handle::Leaf> { | |
811 | /// Inserts the key and value into the top element in the stack, and if that node has to | |
812 | /// split recursively inserts the split contents into the next element stack until | |
813 | /// splits stop. | |
814 | /// | |
815 | /// Assumes that the stack represents a search path from the root to a leaf. | |
816 | /// | |
817 | /// An &mut V is returned to the inserted value, for callers that want a reference to this. | |
818 | pub fn insert(mut self, key: K, val: V) -> &'a mut V { | |
819 | unsafe { | |
820 | self.map.length += 1; | |
821 | ||
822 | // Insert the key and value into the leaf at the top of the stack | |
823 | let (mut insertion, inserted_ptr) = self.top.from_raw_mut() | |
824 | .insert_as_leaf(key, val); | |
825 | ||
826 | loop { | |
827 | match insertion { | |
828 | Fit => { | |
829 | // The last insertion went off without a hitch, no splits! We can stop | |
830 | // inserting now. | |
831 | return &mut *inserted_ptr; | |
832 | } | |
833 | Split(key, val, right) => match self.stack.pop() { | |
834 | // The last insertion triggered a split, so get the next element on the | |
835 | // stack to recursively insert the split node into. | |
836 | None => { | |
837 | // The stack was empty; we've split the root, and need to make a | |
838 | // a new one. This is done in-place because we can't move the | |
839 | // root out of a reference to the tree. | |
840 | Node::make_internal_root(&mut self.map.root, self.map.b, | |
841 | key, val, right); | |
842 | ||
843 | self.map.depth += 1; | |
844 | return &mut *inserted_ptr; | |
845 | } | |
846 | Some(mut handle) => { | |
847 | // The stack wasn't empty, do the insertion and recurse | |
848 | insertion = handle.from_raw_mut() | |
849 | .insert_as_internal(key, val, right); | |
850 | continue; | |
851 | } | |
852 | } | |
853 | } | |
854 | } | |
855 | } | |
856 | } | |
857 | } | |
858 | } | |
859 | ||
85aaf69f | 860 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 861 | impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> { |
85aaf69f | 862 | fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> { |
1a4d82fc JJ |
863 | let mut map = BTreeMap::new(); |
864 | map.extend(iter); | |
865 | map | |
866 | } | |
867 | } | |
868 | ||
85aaf69f | 869 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
870 | impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> { |
871 | #[inline] | |
85aaf69f | 872 | fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) { |
1a4d82fc JJ |
873 | for (k, v) in iter { |
874 | self.insert(k, v); | |
875 | } | |
876 | } | |
877 | } | |
878 | ||
62682a34 SL |
879 | #[stable(feature = "extend_ref", since = "1.2.0")] |
880 | impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> { | |
881 | fn extend<I: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: I) { | |
882 | self.extend(iter.into_iter().map(|(&key, &value)| (key, value))); | |
883 | } | |
884 | } | |
885 | ||
85aaf69f SL |
886 | #[stable(feature = "rust1", since = "1.0.0")] |
887 | impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> { | |
888 | fn hash<H: Hasher>(&self, state: &mut H) { | |
889 | for elt in self { | |
1a4d82fc JJ |
890 | elt.hash(state); |
891 | } | |
892 | } | |
893 | } | |
894 | ||
85aaf69f | 895 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 896 | impl<K: Ord, V> Default for BTreeMap<K, V> { |
85aaf69f | 897 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
898 | fn default() -> BTreeMap<K, V> { |
899 | BTreeMap::new() | |
900 | } | |
901 | } | |
902 | ||
85aaf69f | 903 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
904 | impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> { |
905 | fn eq(&self, other: &BTreeMap<K, V>) -> bool { | |
906 | self.len() == other.len() && | |
62682a34 | 907 | self.iter().zip(other).all(|(a, b)| a == b) |
1a4d82fc JJ |
908 | } |
909 | } | |
910 | ||
85aaf69f | 911 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
912 | impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {} |
913 | ||
85aaf69f | 914 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
915 | impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> { |
916 | #[inline] | |
917 | fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> { | |
918 | iter::order::partial_cmp(self.iter(), other.iter()) | |
919 | } | |
920 | } | |
921 | ||
85aaf69f | 922 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
923 | impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> { |
924 | #[inline] | |
925 | fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering { | |
926 | iter::order::cmp(self.iter(), other.iter()) | |
927 | } | |
928 | } | |
929 | ||
85aaf69f SL |
930 | #[stable(feature = "rust1", since = "1.0.0")] |
931 | impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> { | |
1a4d82fc | 932 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
62682a34 | 933 | f.debug_map().entries(self.iter()).finish() |
1a4d82fc JJ |
934 | } |
935 | } | |
936 | ||
85aaf69f | 937 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 938 | impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V> |
85aaf69f | 939 | where K: Borrow<Q>, Q: Ord |
1a4d82fc JJ |
940 | { |
941 | type Output = V; | |
942 | ||
c34b1796 | 943 | #[inline] |
1a4d82fc JJ |
944 | fn index(&self, key: &Q) -> &V { |
945 | self.get(key).expect("no entry found for key") | |
946 | } | |
947 | } | |
948 | ||
1a4d82fc JJ |
949 | /// Genericises over how to get the correct type of iterator from the correct type |
950 | /// of Node ownership. | |
951 | trait Traverse<N> { | |
952 | fn traverse(node: N) -> Self; | |
953 | } | |
954 | ||
955 | impl<'a, K, V> Traverse<&'a Node<K, V>> for Traversal<'a, K, V> { | |
956 | fn traverse(node: &'a Node<K, V>) -> Traversal<'a, K, V> { | |
957 | node.iter() | |
958 | } | |
959 | } | |
960 | ||
961 | impl<'a, K, V> Traverse<&'a mut Node<K, V>> for MutTraversal<'a, K, V> { | |
962 | fn traverse(node: &'a mut Node<K, V>) -> MutTraversal<'a, K, V> { | |
963 | node.iter_mut() | |
964 | } | |
965 | } | |
966 | ||
967 | impl<K, V> Traverse<Node<K, V>> for MoveTraversal<K, V> { | |
968 | fn traverse(node: Node<K, V>) -> MoveTraversal<K, V> { | |
969 | node.into_iter() | |
970 | } | |
971 | } | |
972 | ||
973 | /// Represents an operation to perform inside the following iterator methods. | |
85aaf69f SL |
974 | /// This is necessary to use in `next` because we want to modify `self.traversals` inside |
975 | /// a match that borrows it. Similarly in `next_back`. Instead, we use this enum to note | |
976 | /// what we want to do, and do it after the match. | |
1a4d82fc JJ |
977 | enum StackOp<T> { |
978 | Push(T), | |
979 | Pop, | |
980 | } | |
1a4d82fc JJ |
981 | impl<K, V, E, T> Iterator for AbsIter<T> where |
982 | T: DoubleEndedIterator<Item=TraversalItem<K, V, E>> + Traverse<E>, | |
983 | { | |
984 | type Item = (K, V); | |
985 | ||
85aaf69f SL |
986 | // Our iterator represents a queue of all ancestors of elements we have |
987 | // yet to yield, from smallest to largest. Note that the design of these | |
988 | // iterators permits an *arbitrary* initial pair of min and max, making | |
989 | // these arbitrary sub-range iterators. | |
1a4d82fc JJ |
990 | fn next(&mut self) -> Option<(K, V)> { |
991 | loop { | |
85aaf69f SL |
992 | // We want the smallest element, so try to get the back of the queue |
993 | let op = match self.traversals.back_mut() { | |
994 | None => return None, | |
995 | // The queue wasn't empty, so continue along the node in its head | |
1a4d82fc | 996 | Some(iter) => match iter.next() { |
85aaf69f | 997 | // The head is empty, so Pop it off and continue the process |
1a4d82fc | 998 | None => Pop, |
85aaf69f | 999 | // The head yielded an edge, so make that the new head |
1a4d82fc | 1000 | Some(Edge(next)) => Push(Traverse::traverse(next)), |
85aaf69f SL |
1001 | // The head yielded an entry, so yield that |
1002 | Some(Elem(kv)) => { | |
1a4d82fc | 1003 | self.size -= 1; |
85aaf69f | 1004 | return Some(kv) |
1a4d82fc JJ |
1005 | } |
1006 | } | |
1007 | }; | |
1008 | ||
85aaf69f | 1009 | // Handle any operation as necessary, without a conflicting borrow of the queue |
1a4d82fc | 1010 | match op { |
85aaf69f SL |
1011 | Push(item) => { self.traversals.push_back(item); }, |
1012 | Pop => { self.traversals.pop_back(); }, | |
1a4d82fc JJ |
1013 | } |
1014 | } | |
1015 | } | |
1016 | ||
85aaf69f | 1017 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1018 | (self.size, Some(self.size)) |
1019 | } | |
1020 | } | |
1021 | ||
1022 | impl<K, V, E, T> DoubleEndedIterator for AbsIter<T> where | |
1023 | T: DoubleEndedIterator<Item=TraversalItem<K, V, E>> + Traverse<E>, | |
1024 | { | |
1025 | // next_back is totally symmetric to next | |
85aaf69f | 1026 | #[inline] |
1a4d82fc JJ |
1027 | fn next_back(&mut self) -> Option<(K, V)> { |
1028 | loop { | |
85aaf69f SL |
1029 | let op = match self.traversals.front_mut() { |
1030 | None => return None, | |
1a4d82fc JJ |
1031 | Some(iter) => match iter.next_back() { |
1032 | None => Pop, | |
1033 | Some(Edge(next)) => Push(Traverse::traverse(next)), | |
85aaf69f | 1034 | Some(Elem(kv)) => { |
1a4d82fc | 1035 | self.size -= 1; |
85aaf69f | 1036 | return Some(kv) |
1a4d82fc JJ |
1037 | } |
1038 | } | |
1039 | }; | |
1040 | ||
1041 | match op { | |
85aaf69f SL |
1042 | Push(item) => { self.traversals.push_front(item); }, |
1043 | Pop => { self.traversals.pop_front(); } | |
1a4d82fc JJ |
1044 | } |
1045 | } | |
1046 | } | |
1047 | } | |
1048 | ||
c34b1796 AL |
1049 | impl<'a, K, V> Clone for Iter<'a, K, V> { |
1050 | fn clone(&self) -> Iter<'a, K, V> { Iter { inner: self.inner.clone() } } | |
1051 | } | |
85aaf69f | 1052 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1053 | impl<'a, K, V> Iterator for Iter<'a, K, V> { |
1054 | type Item = (&'a K, &'a V); | |
1055 | ||
1056 | fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() } | |
85aaf69f | 1057 | fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } |
1a4d82fc | 1058 | } |
85aaf69f | 1059 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1060 | impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> { |
1061 | fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next_back() } | |
1062 | } | |
85aaf69f | 1063 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1064 | impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {} |
1065 | ||
85aaf69f | 1066 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1067 | impl<'a, K, V> Iterator for IterMut<'a, K, V> { |
1068 | type Item = (&'a K, &'a mut V); | |
1069 | ||
1070 | fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() } | |
85aaf69f | 1071 | fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } |
1a4d82fc | 1072 | } |
85aaf69f | 1073 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1074 | impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> { |
1075 | fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next_back() } | |
1076 | } | |
85aaf69f | 1077 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1078 | impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {} |
1079 | ||
85aaf69f | 1080 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1081 | impl<K, V> Iterator for IntoIter<K, V> { |
1082 | type Item = (K, V); | |
1083 | ||
1084 | fn next(&mut self) -> Option<(K, V)> { self.inner.next() } | |
85aaf69f | 1085 | fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } |
1a4d82fc | 1086 | } |
85aaf69f | 1087 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1088 | impl<K, V> DoubleEndedIterator for IntoIter<K, V> { |
1089 | fn next_back(&mut self) -> Option<(K, V)> { self.inner.next_back() } | |
1090 | } | |
85aaf69f | 1091 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1092 | impl<K, V> ExactSizeIterator for IntoIter<K, V> {} |
1093 | ||
c34b1796 AL |
1094 | impl<'a, K, V> Clone for Keys<'a, K, V> { |
1095 | fn clone(&self) -> Keys<'a, K, V> { Keys { inner: self.inner.clone() } } | |
1096 | } | |
85aaf69f | 1097 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1098 | impl<'a, K, V> Iterator for Keys<'a, K, V> { |
1099 | type Item = &'a K; | |
1100 | ||
1101 | fn next(&mut self) -> Option<(&'a K)> { self.inner.next() } | |
85aaf69f | 1102 | fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } |
1a4d82fc | 1103 | } |
85aaf69f | 1104 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1105 | impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> { |
1106 | fn next_back(&mut self) -> Option<(&'a K)> { self.inner.next_back() } | |
1107 | } | |
85aaf69f | 1108 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1109 | impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {} |
1110 | ||
1111 | ||
c34b1796 AL |
1112 | impl<'a, K, V> Clone for Values<'a, K, V> { |
1113 | fn clone(&self) -> Values<'a, K, V> { Values { inner: self.inner.clone() } } | |
1114 | } | |
85aaf69f | 1115 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1116 | impl<'a, K, V> Iterator for Values<'a, K, V> { |
1117 | type Item = &'a V; | |
1118 | ||
1119 | fn next(&mut self) -> Option<(&'a V)> { self.inner.next() } | |
85aaf69f | 1120 | fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } |
1a4d82fc | 1121 | } |
85aaf69f | 1122 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1123 | impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> { |
1124 | fn next_back(&mut self) -> Option<(&'a V)> { self.inner.next_back() } | |
1125 | } | |
85aaf69f | 1126 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1127 | impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {} |
1128 | ||
c34b1796 AL |
1129 | impl<'a, K, V> Clone for Range<'a, K, V> { |
1130 | fn clone(&self) -> Range<'a, K, V> { Range { inner: self.inner.clone() } } | |
1131 | } | |
85aaf69f SL |
1132 | impl<'a, K, V> Iterator for Range<'a, K, V> { |
1133 | type Item = (&'a K, &'a V); | |
1134 | ||
1135 | fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() } | |
1136 | } | |
1137 | impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> { | |
1138 | fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next_back() } | |
1139 | } | |
1140 | ||
1141 | impl<'a, K, V> Iterator for RangeMut<'a, K, V> { | |
1142 | type Item = (&'a K, &'a mut V); | |
1143 | ||
1144 | fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() } | |
1145 | } | |
1146 | impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> { | |
1147 | fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next_back() } | |
1148 | } | |
1149 | ||
1a4d82fc | 1150 | impl<'a, K: Ord, V> Entry<'a, K, V> { |
62682a34 | 1151 | #[unstable(feature = "entry", |
c34b1796 AL |
1152 | reason = "will soon be replaced by or_insert")] |
1153 | #[deprecated(since = "1.0", | |
1154 | reason = "replaced with more ergonomic `or_insert` and `or_insert_with`")] | |
1a4d82fc JJ |
1155 | /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant |
1156 | pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, K, V>> { | |
1157 | match self { | |
1158 | Occupied(entry) => Ok(entry.into_mut()), | |
1159 | Vacant(entry) => Err(entry), | |
1160 | } | |
1161 | } | |
c34b1796 AL |
1162 | |
1163 | #[stable(feature = "rust1", since = "1.0.0")] | |
1164 | /// Ensures a value is in the entry by inserting the default if empty, and returns | |
1165 | /// a mutable reference to the value in the entry. | |
1166 | pub fn or_insert(self, default: V) -> &'a mut V { | |
1167 | match self { | |
1168 | Occupied(entry) => entry.into_mut(), | |
1169 | Vacant(entry) => entry.insert(default), | |
1170 | } | |
1171 | } | |
1172 | ||
1173 | #[stable(feature = "rust1", since = "1.0.0")] | |
1174 | /// Ensures a value is in the entry by inserting the result of the default function if empty, | |
1175 | /// and returns a mutable reference to the value in the entry. | |
1176 | pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V { | |
1177 | match self { | |
1178 | Occupied(entry) => entry.into_mut(), | |
1179 | Vacant(entry) => entry.insert(default()), | |
1180 | } | |
1181 | } | |
1a4d82fc JJ |
1182 | } |
1183 | ||
1184 | impl<'a, K: Ord, V> VacantEntry<'a, K, V> { | |
1185 | /// Sets the value of the entry with the VacantEntry's key, | |
1186 | /// and returns a mutable reference to it. | |
85aaf69f | 1187 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1188 | pub fn insert(self, value: V) -> &'a mut V { |
1189 | self.stack.insert(self.key, value) | |
1190 | } | |
1191 | } | |
1192 | ||
1193 | impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> { | |
1194 | /// Gets a reference to the value in the entry. | |
85aaf69f | 1195 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1196 | pub fn get(&self) -> &V { |
1197 | self.stack.peek() | |
1198 | } | |
1199 | ||
1200 | /// Gets a mutable reference to the value in the entry. | |
85aaf69f | 1201 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1202 | pub fn get_mut(&mut self) -> &mut V { |
1203 | self.stack.peek_mut() | |
1204 | } | |
1205 | ||
1206 | /// Converts the entry into a mutable reference to its value. | |
85aaf69f | 1207 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1208 | pub fn into_mut(self) -> &'a mut V { |
1209 | self.stack.into_top() | |
1210 | } | |
1211 | ||
1212 | /// Sets the value of the entry with the OccupiedEntry's key, | |
1213 | /// and returns the entry's old value. | |
85aaf69f | 1214 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1215 | pub fn insert(&mut self, mut value: V) -> V { |
1216 | mem::swap(self.stack.peek_mut(), &mut value); | |
1217 | value | |
1218 | } | |
1219 | ||
1220 | /// Takes the value of the entry out of the map, and returns it. | |
85aaf69f | 1221 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1222 | pub fn remove(self) -> V { |
1223 | self.stack.remove() | |
1224 | } | |
1225 | } | |
1226 | ||
1227 | impl<K, V> BTreeMap<K, V> { | |
1228 | /// Gets an iterator over the entries of the map. | |
1229 | /// | |
c34b1796 | 1230 | /// # Examples |
1a4d82fc JJ |
1231 | /// |
1232 | /// ``` | |
1233 | /// use std::collections::BTreeMap; | |
1234 | /// | |
1235 | /// let mut map = BTreeMap::new(); | |
85aaf69f SL |
1236 | /// map.insert(1, "a"); |
1237 | /// map.insert(2, "b"); | |
1238 | /// map.insert(3, "c"); | |
1a4d82fc JJ |
1239 | /// |
1240 | /// for (key, value) in map.iter() { | |
1241 | /// println!("{}: {}", key, value); | |
1242 | /// } | |
1243 | /// | |
1244 | /// let (first_key, first_value) = map.iter().next().unwrap(); | |
85aaf69f | 1245 | /// assert_eq!((*first_key, *first_value), (1, "a")); |
1a4d82fc | 1246 | /// ``` |
85aaf69f | 1247 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1248 | pub fn iter(&self) -> Iter<K, V> { |
1249 | let len = self.len(); | |
85aaf69f SL |
1250 | // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases. |
1251 | let mut lca = VecDeque::new(); | |
1252 | lca.push_back(Traverse::traverse(&self.root)); | |
1a4d82fc JJ |
1253 | Iter { |
1254 | inner: AbsIter { | |
85aaf69f | 1255 | traversals: lca, |
1a4d82fc JJ |
1256 | size: len, |
1257 | } | |
1258 | } | |
1259 | } | |
1260 | ||
1261 | /// Gets a mutable iterator over the entries of the map. | |
1262 | /// | |
1263 | /// # Examples | |
1264 | /// | |
1265 | /// ``` | |
1266 | /// use std::collections::BTreeMap; | |
1267 | /// | |
1268 | /// let mut map = BTreeMap::new(); | |
85aaf69f SL |
1269 | /// map.insert("a", 1); |
1270 | /// map.insert("b", 2); | |
1271 | /// map.insert("c", 3); | |
1a4d82fc JJ |
1272 | /// |
1273 | /// // add 10 to the value if the key isn't "a" | |
1274 | /// for (key, value) in map.iter_mut() { | |
1275 | /// if key != &"a" { | |
1276 | /// *value += 10; | |
1277 | /// } | |
1278 | /// } | |
1279 | /// ``` | |
85aaf69f | 1280 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1281 | pub fn iter_mut(&mut self) -> IterMut<K, V> { |
1282 | let len = self.len(); | |
85aaf69f SL |
1283 | let mut lca = VecDeque::new(); |
1284 | lca.push_back(Traverse::traverse(&mut self.root)); | |
1a4d82fc JJ |
1285 | IterMut { |
1286 | inner: AbsIter { | |
85aaf69f | 1287 | traversals: lca, |
1a4d82fc JJ |
1288 | size: len, |
1289 | } | |
1290 | } | |
1291 | } | |
1292 | ||
1a4d82fc JJ |
1293 | /// Gets an iterator over the keys of the map. |
1294 | /// | |
1295 | /// # Examples | |
1296 | /// | |
1297 | /// ``` | |
1298 | /// use std::collections::BTreeMap; | |
1299 | /// | |
1300 | /// let mut a = BTreeMap::new(); | |
85aaf69f SL |
1301 | /// a.insert(1, "a"); |
1302 | /// a.insert(2, "b"); | |
1a4d82fc | 1303 | /// |
62682a34 | 1304 | /// let keys: Vec<_> = a.keys().cloned().collect(); |
c34b1796 | 1305 | /// assert_eq!(keys, [1, 2]); |
1a4d82fc | 1306 | /// ``` |
85aaf69f | 1307 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1308 | pub fn keys<'a>(&'a self) -> Keys<'a, K, V> { |
1309 | fn first<A, B>((a, _): (A, B)) -> A { a } | |
1310 | let first: fn((&'a K, &'a V)) -> &'a K = first; // coerce to fn pointer | |
1311 | ||
1312 | Keys { inner: self.iter().map(first) } | |
1313 | } | |
1314 | ||
1315 | /// Gets an iterator over the values of the map. | |
1316 | /// | |
1317 | /// # Examples | |
1318 | /// | |
1319 | /// ``` | |
1320 | /// use std::collections::BTreeMap; | |
1321 | /// | |
1322 | /// let mut a = BTreeMap::new(); | |
85aaf69f SL |
1323 | /// a.insert(1, "a"); |
1324 | /// a.insert(2, "b"); | |
1a4d82fc JJ |
1325 | /// |
1326 | /// let values: Vec<&str> = a.values().cloned().collect(); | |
c34b1796 | 1327 | /// assert_eq!(values, ["a", "b"]); |
1a4d82fc | 1328 | /// ``` |
85aaf69f | 1329 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1330 | pub fn values<'a>(&'a self) -> Values<'a, K, V> { |
1331 | fn second<A, B>((_, b): (A, B)) -> B { b } | |
1332 | let second: fn((&'a K, &'a V)) -> &'a V = second; // coerce to fn pointer | |
1333 | ||
1334 | Values { inner: self.iter().map(second) } | |
1335 | } | |
1336 | ||
9346a6ac | 1337 | /// Returns the number of elements in the map. |
1a4d82fc JJ |
1338 | /// |
1339 | /// # Examples | |
1340 | /// | |
1341 | /// ``` | |
1342 | /// use std::collections::BTreeMap; | |
1343 | /// | |
1344 | /// let mut a = BTreeMap::new(); | |
1345 | /// assert_eq!(a.len(), 0); | |
85aaf69f | 1346 | /// a.insert(1, "a"); |
1a4d82fc JJ |
1347 | /// assert_eq!(a.len(), 1); |
1348 | /// ``` | |
85aaf69f SL |
1349 | #[stable(feature = "rust1", since = "1.0.0")] |
1350 | pub fn len(&self) -> usize { self.length } | |
1a4d82fc | 1351 | |
9346a6ac | 1352 | /// Returns true if the map contains no elements. |
1a4d82fc JJ |
1353 | /// |
1354 | /// # Examples | |
1355 | /// | |
1356 | /// ``` | |
1357 | /// use std::collections::BTreeMap; | |
1358 | /// | |
1359 | /// let mut a = BTreeMap::new(); | |
1360 | /// assert!(a.is_empty()); | |
85aaf69f | 1361 | /// a.insert(1, "a"); |
1a4d82fc JJ |
1362 | /// assert!(!a.is_empty()); |
1363 | /// ``` | |
85aaf69f | 1364 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1365 | pub fn is_empty(&self) -> bool { self.len() == 0 } |
1366 | } | |
1367 | ||
85aaf69f SL |
1368 | macro_rules! range_impl { |
1369 | ($root:expr, $min:expr, $max:expr, $as_slices_internal:ident, $iter:ident, $Range:ident, | |
1370 | $edges:ident, [$($mutability:ident)*]) => ( | |
1371 | { | |
1372 | // A deque that encodes two search paths containing (left-to-right): | |
1373 | // a series of truncated-from-the-left iterators, the LCA's doubly-truncated iterator, | |
1374 | // and a series of truncated-from-the-right iterators. | |
1375 | let mut traversals = VecDeque::new(); | |
1376 | let (root, min, max) = ($root, $min, $max); | |
1377 | ||
1378 | let mut leftmost = None; | |
1379 | let mut rightmost = None; | |
1380 | ||
1381 | match (&min, &max) { | |
1382 | (&Unbounded, &Unbounded) => { | |
1383 | traversals.push_back(Traverse::traverse(root)) | |
1384 | } | |
1385 | (&Unbounded, &Included(_)) | (&Unbounded, &Excluded(_)) => { | |
1386 | rightmost = Some(root); | |
1387 | } | |
1388 | (&Included(_), &Unbounded) | (&Excluded(_), &Unbounded) => { | |
1389 | leftmost = Some(root); | |
1390 | } | |
1391 | (&Included(min_key), &Included(max_key)) | |
1392 | | (&Included(min_key), &Excluded(max_key)) | |
1393 | | (&Excluded(min_key), &Included(max_key)) | |
1394 | | (&Excluded(min_key), &Excluded(max_key)) => { | |
1395 | // lca represents the Lowest Common Ancestor, above which we never | |
1396 | // walk, since everything else is outside the range to iterate. | |
1397 | // ___________________ | |
1398 | // |__0_|_80_|_85_|_90_| (root) | |
1399 | // | | | | | | |
1400 | // | | |
1401 | // v | |
1402 | // ___________________ | |
1403 | // |__5_|_15_|_30_|_73_| | |
1404 | // | | | | | | |
1405 | // | | |
1406 | // v | |
1407 | // ___________________ | |
1408 | // |_33_|_58_|_63_|_68_| lca for the range [41, 65] | |
1409 | // | |\___|___/| | iterator at traversals[2] | |
1410 | // | | | |
1411 | // | v | |
1412 | // v rightmost | |
1413 | // leftmost | |
1414 | let mut is_leaf = root.is_leaf(); | |
1415 | let mut lca = root.$as_slices_internal(); | |
1416 | loop { | |
1417 | let slice = lca.slice_from(min_key).slice_to(max_key); | |
1418 | if let [ref $($mutability)* edge] = slice.edges { | |
1419 | // Follow the only edge that leads the node that covers the range. | |
1420 | is_leaf = edge.is_leaf(); | |
1421 | lca = edge.$as_slices_internal(); | |
1422 | } else { | |
1423 | let mut iter = slice.$iter(); | |
1424 | if is_leaf { | |
1425 | leftmost = None; | |
1426 | rightmost = None; | |
1427 | } else { | |
1428 | // Only change the state of nodes with edges. | |
1429 | leftmost = iter.next_edge_item(); | |
1430 | rightmost = iter.next_edge_item_back(); | |
1431 | } | |
1432 | traversals.push_back(iter); | |
1433 | break; | |
1434 | } | |
1435 | } | |
1436 | } | |
1437 | } | |
1438 | // Keep narrowing the range by going down. | |
1439 | // ___________________ | |
1440 | // |_38_|_43_|_48_|_53_| | |
1441 | // | |____|____|____/ iterator at traversals[1] | |
1442 | // | | |
1443 | // v | |
1444 | // ___________________ | |
1445 | // |_39_|_40_|_41_|_42_| (leaf, the last leftmost) | |
1446 | // \_________| iterator at traversals[0] | |
1447 | match min { | |
1448 | Included(key) | Excluded(key) => | |
1449 | while let Some(left) = leftmost { | |
1450 | let is_leaf = left.is_leaf(); | |
1451 | let mut iter = left.$as_slices_internal().slice_from(key).$iter(); | |
1452 | leftmost = if is_leaf { | |
1453 | None | |
1454 | } else { | |
1455 | // Only change the state of nodes with edges. | |
1456 | iter.next_edge_item() | |
1457 | }; | |
1458 | traversals.push_back(iter); | |
1459 | }, | |
1460 | _ => {} | |
1461 | } | |
1462 | // If the leftmost iterator starts with an element, then it was an exact match. | |
1463 | if let (Excluded(_), Some(leftmost_iter)) = (min, traversals.back_mut()) { | |
1464 | // Drop this excluded element. `next_kv_item` has no effect when | |
1465 | // the next item is an edge. | |
1466 | leftmost_iter.next_kv_item(); | |
1467 | } | |
1468 | ||
1469 | // The code for the right side is similar. | |
1470 | match max { | |
1471 | Included(key) | Excluded(key) => | |
1472 | while let Some(right) = rightmost { | |
1473 | let is_leaf = right.is_leaf(); | |
1474 | let mut iter = right.$as_slices_internal().slice_to(key).$iter(); | |
1475 | rightmost = if is_leaf { | |
1476 | None | |
1477 | } else { | |
1478 | iter.next_edge_item_back() | |
1479 | }; | |
1480 | traversals.push_front(iter); | |
1481 | }, | |
1482 | _ => {} | |
1483 | } | |
1484 | if let (Excluded(_), Some(rightmost_iter)) = (max, traversals.front_mut()) { | |
1485 | rightmost_iter.next_kv_item_back(); | |
1486 | } | |
1487 | ||
1488 | $Range { | |
1489 | inner: AbsIter { | |
1490 | traversals: traversals, | |
c34b1796 | 1491 | size: usize::MAX, // unused |
85aaf69f SL |
1492 | } |
1493 | } | |
1494 | } | |
1495 | ) | |
1496 | } | |
1497 | ||
1a4d82fc | 1498 | impl<K: Ord, V> BTreeMap<K, V> { |
85aaf69f SL |
1499 | /// Constructs a double-ended iterator over a sub-range of elements in the map, starting |
1500 | /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative | |
1501 | /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity". | |
1502 | /// Thus range(Unbounded, Unbounded) will yield the whole collection. | |
1503 | /// | |
1504 | /// # Examples | |
1505 | /// | |
1506 | /// ``` | |
c1a9b12d SL |
1507 | /// #![feature(btree_range, collections_bound)] |
1508 | /// | |
85aaf69f SL |
1509 | /// use std::collections::BTreeMap; |
1510 | /// use std::collections::Bound::{Included, Unbounded}; | |
1511 | /// | |
1512 | /// let mut map = BTreeMap::new(); | |
1513 | /// map.insert(3, "a"); | |
1514 | /// map.insert(5, "b"); | |
1515 | /// map.insert(8, "c"); | |
1516 | /// for (&key, &value) in map.range(Included(&4), Included(&8)) { | |
1517 | /// println!("{}: {}", key, value); | |
1518 | /// } | |
1519 | /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next()); | |
1520 | /// ``` | |
62682a34 | 1521 | #[unstable(feature = "btree_range", |
85aaf69f SL |
1522 | reason = "matches collection reform specification, waiting for dust to settle")] |
1523 | pub fn range<'a>(&'a self, min: Bound<&K>, max: Bound<&K>) -> Range<'a, K, V> { | |
1524 | range_impl!(&self.root, min, max, as_slices_internal, iter, Range, edges, []) | |
1525 | } | |
1526 | ||
1527 | /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting | |
1528 | /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative | |
1529 | /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity". | |
1530 | /// Thus range(Unbounded, Unbounded) will yield the whole collection. | |
1531 | /// | |
1532 | /// # Examples | |
1533 | /// | |
1534 | /// ``` | |
c1a9b12d SL |
1535 | /// #![feature(btree_range, collections_bound)] |
1536 | /// | |
85aaf69f SL |
1537 | /// use std::collections::BTreeMap; |
1538 | /// use std::collections::Bound::{Included, Excluded}; | |
1539 | /// | |
1540 | /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter() | |
1541 | /// .map(|&s| (s, 0)) | |
1542 | /// .collect(); | |
1543 | /// for (_, balance) in map.range_mut(Included(&"B"), Excluded(&"Cheryl")) { | |
1544 | /// *balance += 100; | |
1545 | /// } | |
62682a34 | 1546 | /// for (name, balance) in &map { |
85aaf69f SL |
1547 | /// println!("{} => {}", name, balance); |
1548 | /// } | |
1549 | /// ``` | |
62682a34 | 1550 | #[unstable(feature = "btree_range", |
85aaf69f SL |
1551 | reason = "matches collection reform specification, waiting for dust to settle")] |
1552 | pub fn range_mut<'a>(&'a mut self, min: Bound<&K>, max: Bound<&K>) -> RangeMut<'a, K, V> { | |
1553 | range_impl!(&mut self.root, min, max, as_slices_internal_mut, iter_mut, RangeMut, | |
1554 | edges_mut, [mut]) | |
1555 | } | |
1556 | ||
1a4d82fc JJ |
1557 | /// Gets the given key's corresponding entry in the map for in-place manipulation. |
1558 | /// | |
1559 | /// # Examples | |
1560 | /// | |
1561 | /// ``` | |
1562 | /// use std::collections::BTreeMap; | |
1a4d82fc | 1563 | /// |
85aaf69f | 1564 | /// let mut count: BTreeMap<&str, usize> = BTreeMap::new(); |
1a4d82fc JJ |
1565 | /// |
1566 | /// // count the number of occurrences of letters in the vec | |
c34b1796 AL |
1567 | /// for x in vec!["a","b","a","c","a","b"] { |
1568 | /// *count.entry(x).or_insert(0) += 1; | |
1a4d82fc JJ |
1569 | /// } |
1570 | /// | |
85aaf69f | 1571 | /// assert_eq!(count["a"], 3); |
1a4d82fc | 1572 | /// ``` |
85aaf69f SL |
1573 | #[stable(feature = "rust1", since = "1.0.0")] |
1574 | pub fn entry(&mut self, mut key: K) -> Entry<K, V> { | |
1a4d82fc JJ |
1575 | // same basic logic of `swap` and `pop`, blended together |
1576 | let mut stack = stack::PartialSearchStack::new(self); | |
1577 | loop { | |
1578 | let result = stack.with(move |pusher, node| { | |
c34b1796 | 1579 | match Node::search(node, &key) { |
1a4d82fc JJ |
1580 | Found(handle) => { |
1581 | // Perfect match | |
1582 | Finished(Occupied(OccupiedEntry { | |
1583 | stack: pusher.seal(handle) | |
1584 | })) | |
1585 | }, | |
1586 | GoDown(handle) => { | |
1587 | match handle.force() { | |
1588 | Leaf(leaf_handle) => { | |
1589 | Finished(Vacant(VacantEntry { | |
1590 | stack: pusher.seal(leaf_handle), | |
1591 | key: key, | |
1592 | })) | |
1593 | }, | |
1594 | Internal(internal_handle) => { | |
1595 | Continue(( | |
1596 | pusher.push(internal_handle), | |
1597 | key | |
1598 | )) | |
1599 | } | |
1600 | } | |
1601 | } | |
1602 | } | |
1603 | }); | |
1604 | match result { | |
1605 | Finished(finished) => return finished, | |
1606 | Continue((new_stack, renewed_key)) => { | |
1607 | stack = new_stack; | |
1608 | key = renewed_key; | |
1609 | } | |
1610 | } | |
1611 | } | |
1612 | } | |
1613 | } |