diff options
| -rw-r--r-- | src/libcollections/binary_heap.rs | 50 | ||||
| -rw-r--r-- | src/libcollections/bit.rs | 28 | ||||
| -rw-r--r-- | src/libcollections/btree/map.rs | 176 | ||||
| -rw-r--r-- | src/libcollections/btree/set.rs | 25 | ||||
| -rw-r--r-- | src/libcollections/dlist.rs | 147 | ||||
| -rw-r--r-- | src/libcollections/enum_set.rs | 192 | ||||
| -rw-r--r-- | src/libcollections/ring_buf.rs | 328 | ||||
| -rw-r--r-- | src/libcollections/slice.rs | 6 | ||||
| -rw-r--r-- | src/libcollections/str.rs | 8 | ||||
| -rw-r--r-- | src/libcollections/string.rs | 58 | ||||
| -rw-r--r-- | src/libcollections/tree/map.rs | 315 | ||||
| -rw-r--r-- | src/libcollections/tree/set.rs | 24 | ||||
| -rw-r--r-- | src/libcollections/trie/map.rs | 208 | ||||
| -rw-r--r-- | src/libcollections/trie/set.rs | 21 | ||||
| -rw-r--r-- | src/libcollections/vec.rs | 151 | ||||
| -rw-r--r-- | src/libcollections/vec_map.rs | 266 | ||||
| -rw-r--r-- | src/libstd/collections/hash/bench.rs | 10 | ||||
| -rw-r--r-- | src/libstd/collections/hash/map.rs | 253 | ||||
| -rw-r--r-- | src/libstd/collections/hash/set.rs | 30 | ||||
| -rw-r--r-- | src/libstd/collections/lru_cache.rs | 150 | ||||
| -rw-r--r-- | src/libstd/collections/mod.rs | 2 |
21 files changed, 1386 insertions, 1062 deletions
diff --git a/src/libcollections/binary_heap.rs b/src/libcollections/binary_heap.rs index 8481111ae91..c9d60077449 100644 --- a/src/libcollections/binary_heap.rs +++ b/src/libcollections/binary_heap.rs @@ -162,6 +162,8 @@ use core::ptr; use slice; use vec::Vec; +// FIXME(conventions): implement into_iter + /// A priority queue implemented with a binary heap. /// /// This will be a max-heap. @@ -184,6 +186,7 @@ impl<T: Ord> BinaryHeap<T> { /// use std::collections::BinaryHeap; /// let pq: BinaryHeap<uint> = BinaryHeap::new(); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> BinaryHeap<T> { BinaryHeap{data: vec!(),} } /// Creates an empty `BinaryHeap` with a specific capacity. @@ -197,6 +200,7 @@ impl<T: Ord> BinaryHeap<T> { /// use std::collections::BinaryHeap; /// let pq: BinaryHeap<uint> = BinaryHeap::with_capacity(10u); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn with_capacity(capacity: uint) -> BinaryHeap<T> { BinaryHeap { data: Vec::with_capacity(capacity) } } @@ -234,6 +238,7 @@ impl<T: Ord> BinaryHeap<T> { /// println!("{}", x); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter<'a>(&'a self) -> Items<'a, T> { Items { iter: self.data.iter() } } @@ -268,10 +273,19 @@ impl<T: Ord> BinaryHeap<T> { /// let pq: BinaryHeap<uint> = BinaryHeap::with_capacity(100u); /// assert!(pq.capacity() >= 100u); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn capacity(&self) -> uint { self.data.capacity() } - /// Reserves capacity for exactly `n` elements in the `BinaryHeap`. - /// Do nothing if the capacity is already sufficient. + /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the + /// given `BinaryHeap`. Does nothing if the capacity is already sufficient. + /// + /// Note that the allocator may give the collection more space than it requests. Therefore + /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future + /// insertions are expected. + /// + /// # Panics + /// + /// Panics if the new capacity overflows `uint`. /// /// # Example /// @@ -280,12 +294,17 @@ impl<T: Ord> BinaryHeap<T> { /// /// let mut pq: BinaryHeap<uint> = BinaryHeap::new(); /// pq.reserve_exact(100u); - /// assert!(pq.capacity() == 100u); + /// assert!(pq.capacity() >= 100u); /// ``` - pub fn reserve_exact(&mut self, n: uint) { self.data.reserve_exact(n) } + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn reserve_exact(&mut self, additional: uint) { self.data.reserve_exact(additional) } - /// Reserves capacity for at least `n` elements in the `BinaryHeap`. - /// Do nothing if the capacity is already sufficient. + /// Reserves capacity for at least `additional` more elements to be inserted in the + /// `BinaryHeap`. The collection may reserve more space to avoid frequent reallocations. + /// + /// # Panics + /// + /// Panics if the new capacity overflows `uint`. /// /// # Example /// @@ -296,8 +315,15 @@ impl<T: Ord> BinaryHeap<T> { /// pq.reserve(100u); /// assert!(pq.capacity() >= 100u); /// ``` - pub fn reserve(&mut self, n: uint) { - self.data.reserve(n) + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn reserve(&mut self, additional: uint) { + self.data.reserve(additional) + } + + /// Discards as much additional capacity as possible. + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn shrink_to_fit(&mut self) { + self.data.shrink_to_fit() } /// Removes the greatest item from a queue and returns it, or `None` if it @@ -314,6 +340,7 @@ impl<T: Ord> BinaryHeap<T> { /// assert_eq!(pq.pop(), Some(1i)); /// assert_eq!(pq.pop(), None); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn pop(&mut self) -> Option<T> { match self.data.pop() { None => { None } @@ -342,6 +369,7 @@ impl<T: Ord> BinaryHeap<T> { /// assert_eq!(pq.len(), 3); /// assert_eq!(pq.top(), Some(&5i)); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn push(&mut self, item: T) { self.data.push(item); let new_len = self.len() - 1; @@ -495,12 +523,15 @@ impl<T: Ord> BinaryHeap<T> { } /// Returns the length of the queue. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.data.len() } /// Returns true if the queue contains no elements + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.len() == 0 } /// Drops all items from the queue. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { self.data.truncate(0) } } @@ -528,8 +559,7 @@ impl<T: Ord> Extendable<T> for BinaryHeap<T> { fn extend<Iter: Iterator<T>>(&mut self, mut iter: Iter) { let (lower, _) = iter.size_hint(); - let len = self.capacity(); - self.reserve(len + lower); + self.reserve(lower); for elem in iter { self.push(elem); diff --git a/src/libcollections/bit.rs b/src/libcollections/bit.rs index b7085c96aed..833cfc04c55 100644 --- a/src/libcollections/bit.rs +++ b/src/libcollections/bit.rs @@ -75,6 +75,8 @@ use std::hash; use vec::Vec; +// FIXME(conventions): look, we just need to refactor this whole thing. Inside and out. + type MatchWords<'a> = Chain<MaskWords<'a>, Skip<Take<Enumerate<Repeat<u32>>>>>; // Take two BitV's, and return iterators of their words, where the shorter one // has been padded with 0's @@ -216,6 +218,7 @@ impl Bitv { /// use std::collections::Bitv; /// let mut bv = Bitv::new(); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> Bitv { Bitv { storage: Vec::new(), nbits: 0 } } @@ -613,6 +616,7 @@ impl Bitv { /// bv.truncate(2); /// assert!(bv.eq_vec([false, true])); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn truncate(&mut self, len: uint) { if len < self.len() { self.nbits = len; @@ -760,14 +764,17 @@ impl Bitv { /// Return the total number of bits in this vector #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.nbits } /// Returns true if there are no bits in this vector #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.len() == 0 } /// Clears all bits in this vector. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { for w in self.storage.iter_mut() { *w = 0u32; } } @@ -849,8 +856,7 @@ impl Clone for Bitv { #[inline] fn clone_from(&mut self, source: &Bitv) { self.nbits = source.nbits; - self.storage.reserve(source.storage.len()); - for (i, w) in self.storage.iter_mut().enumerate() { *w = source.storage[i]; } + self.storage.clone_from(&source.storage); } } @@ -1052,6 +1058,7 @@ impl BitvSet { /// let mut s = BitvSet::new(); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> BitvSet { BitvSet(Bitv::new()) } @@ -1067,6 +1074,7 @@ impl BitvSet { /// assert!(s.capacity() >= 100); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn with_capacity(nbits: uint) -> BitvSet { let bitv = Bitv::with_capacity(nbits, false); BitvSet::from_bitv(bitv) @@ -1106,6 +1114,7 @@ impl BitvSet { /// assert!(s.capacity() >= 100); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn capacity(&self) -> uint { let &BitvSet(ref bitv) = self; bitv.capacity() @@ -1212,6 +1221,7 @@ impl BitvSet { /// println!("new capacity: {}", s.capacity()); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn shrink_to_fit(&mut self) { let &BitvSet(ref mut bitv) = self; // Obtain original length @@ -1240,6 +1250,7 @@ impl BitvSet { /// } /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter<'a>(&'a self) -> BitPositions<'a> { BitPositions {set: self, next_idx: 0u} } @@ -1262,6 +1273,7 @@ impl BitvSet { /// } /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn union<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> { TwoBitPositions { set: self, @@ -1290,6 +1302,7 @@ impl BitvSet { /// } /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Take<TwoBitPositions<'a>> { let min = cmp::min(self.capacity(), other.capacity()); TwoBitPositions { @@ -1326,6 +1339,7 @@ impl BitvSet { /// } /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> { TwoBitPositions { set: self, @@ -1355,6 +1369,7 @@ impl BitvSet { /// } /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> { TwoBitPositions { set: self, @@ -1473,6 +1488,7 @@ impl BitvSet { /// Return the number of set bits in this set. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { let &BitvSet(ref bitv) = self; bitv.storage.iter().fold(0, |acc, &n| acc + n.count_ones()) @@ -1480,6 +1496,7 @@ impl BitvSet { /// Returns whether there are no bits set in this set #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { let &BitvSet(ref bitv) = self; bitv.storage.iter().all(|&n| n == 0) @@ -1487,6 +1504,7 @@ impl BitvSet { /// Clears all bits in this set #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { let &BitvSet(ref mut bitv) = self; bitv.clear(); @@ -1494,6 +1512,7 @@ impl BitvSet { /// Returns `true` if this set contains the specified integer. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn contains(&self, value: &uint) -> bool { let &BitvSet(ref bitv) = self; *value < bitv.nbits && bitv.get(*value) @@ -1502,12 +1521,14 @@ impl BitvSet { /// Returns `true` if the set has no elements in common with `other`. /// This is equivalent to checking for an empty intersection. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_disjoint(&self, other: &BitvSet) -> bool { self.intersection(other).next().is_none() } /// Returns `true` if the set is a subset of another. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_subset(&self, other: &BitvSet) -> bool { let &BitvSet(ref self_bitv) = self; let &BitvSet(ref other_bitv) = other; @@ -1521,12 +1542,14 @@ impl BitvSet { /// Returns `true` if the set is a superset of another. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_superset(&self, other: &BitvSet) -> bool { other.is_subset(self) } /// Adds a value to the set. Returns `true` if the value was not already /// present in the set. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn insert(&mut self, value: uint) -> bool { if self.contains(&value) { return false; @@ -1545,6 +1568,7 @@ impl BitvSet { /// Removes a value from the set. Returns `true` if the value was /// present in the set. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn remove(&mut self, value: &uint) -> bool { if !self.contains(value) { return false; diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs index e3dfabfa295..9b644115f30 100644 --- a/src/libcollections/btree/map.rs +++ b/src/libcollections/btree/map.rs @@ -25,6 +25,8 @@ use core::fmt::Show; use ring_buf::RingBuf; +// FIXME(conventions): implement bounded iterators + /// A map based on a B-Tree. /// /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing @@ -125,6 +127,7 @@ pub struct OccupiedEntry<'a, K:'a, V:'a> { impl<K: Ord, V> BTreeMap<K, V> { /// Makes a new empty BTreeMap with a reasonable choice for B. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> BTreeMap<K, V> { //FIXME(Gankro): Tune this as a function of size_of<K/V>? BTreeMap::with_b(6) @@ -155,12 +158,19 @@ impl<K: Ord, V> BTreeMap<K, V> { /// a.clear(); /// assert!(a.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { let b = self.b; // avoid recursive destructors by manually traversing the tree for _ in mem::replace(self, BTreeMap::with_b(b)).into_iter() {}; } + /// Deprecated: renamed to `get`. + #[deprecated = "renamed to `get`"] + pub fn find(&self, key: &K) -> Option<&V> { + self.get(key) + } + // Searching in a B-Tree is pretty straightforward. // // Start at the root. Try to find the key in the current node. If we find it, return it. @@ -178,10 +188,11 @@ impl<K: Ord, V> BTreeMap<K, V> { /// /// let mut map = BTreeMap::new(); /// map.insert(1u, "a"); - /// assert_eq!(map.find(&1), Some(&"a")); - /// assert_eq!(map.find(&2), None); + /// assert_eq!(map.get(&1), Some(&"a")); + /// assert_eq!(map.get(&2), None); /// ``` - pub fn find(&self, key: &K) -> Option<&V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get(&self, key: &K) -> Option<&V> { let mut cur_node = &self.root; loop { match cur_node.search(key) { @@ -209,9 +220,15 @@ impl<K: Ord, V> BTreeMap<K, V> { /// assert_eq!(map.contains_key(&1), true); /// assert_eq!(map.contains_key(&2), false); /// ``` - #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn contains_key(&self, key: &K) -> bool { - self.find(key).is_some() + self.get(key).is_some() + } + + /// Deprecated: renamed to `get_mut`. + #[deprecated = "renamed to `get_mut`"] + pub fn find_mut(&mut self, key: &K) -> Option<&mut V> { + self.get_mut(key) } /// Returns a mutable reference to the value corresponding to the key. @@ -223,14 +240,15 @@ impl<K: Ord, V> BTreeMap<K, V> { /// /// let mut map = BTreeMap::new(); /// map.insert(1u, "a"); - /// match map.find_mut(&1) { + /// match map.get_mut(&1) { /// Some(x) => *x = "b", /// None => (), /// } /// assert_eq!(map[1], "b"); /// ``` - // See `find` for implementation notes, this is basically a copy-paste with mut's added - pub fn find_mut(&mut self, key: &K) -> Option<&mut V> { + // See `get` for implementation notes, this is basically a copy-paste with mut's added + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get_mut(&mut self, key: &K) -> Option<&mut V> { // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration let mut temp_node = &mut self.root; loop { @@ -248,6 +266,12 @@ impl<K: Ord, V> BTreeMap<K, V> { } } + /// Deprecated: renamed to `insert`. + #[deprecated = "renamed to `insert`"] + pub fn swap(&mut self, key: K, value: V) -> Option<V> { + self.insert(key, value) + } + // Insertion in a B-Tree is a bit complicated. // // First we do the same kind of search described in `find`. But we need to maintain a stack of @@ -283,14 +307,15 @@ impl<K: Ord, V> BTreeMap<K, V> { /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); - /// assert_eq!(map.swap(37u, "a"), None); + /// assert_eq!(map.insert(37u, "a"), None); /// assert_eq!(map.is_empty(), false); /// /// map.insert(37, "b"); - /// assert_eq!(map.swap(37, "c"), Some("b")); + /// assert_eq!(map.insert(37, "c"), Some("b")); /// assert_eq!(map[37], "c"); /// ``` - pub fn swap(&mut self, key: K, mut value: V) -> Option<V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn insert(&mut self, key: K, mut value: V) -> Option<V> { // This is a stack of rawptrs to nodes paired with indices, respectively // representing the nodes and edges of our search path. We have to store rawptrs // because as far as Rust is concerned, we can mutate aliased data with such a @@ -338,25 +363,6 @@ impl<K: Ord, V> BTreeMap<K, V> { } } - /// Inserts a key-value pair into the map. An existing value for a - /// key is replaced by the new value. Returns `true` if the key did - /// not already exist in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::BTreeMap; - /// - /// let mut map = BTreeMap::new(); - /// assert_eq!(map.insert(2u, "value"), true); - /// assert_eq!(map.insert(2, "value2"), false); - /// assert_eq!(map[2], "value2"); - /// ``` - #[inline] - pub fn insert(&mut self, key: K, value: V) -> bool { - self.swap(key, value).is_none() - } - // Deletion is the most complicated operation for a B-Tree. // // First we do the same kind of search described in @@ -392,6 +398,12 @@ impl<K: Ord, V> BTreeMap<K, V> { // the underflow handling process on the parent. If merging merges the last two children // of the root, then we replace the root with the merged node. + /// Deprecated: renamed to `remove`. + #[deprecated = "renamed to `remove`"] + pub fn pop(&mut self, key: &K) -> Option<V> { + self.remove(key) + } + /// Removes a key from the map, returning the value at the key if the key /// was previously in the map. /// @@ -402,10 +414,11 @@ impl<K: Ord, V> BTreeMap<K, V> { /// /// let mut map = BTreeMap::new(); /// map.insert(1u, "a"); - /// assert_eq!(map.pop(&1), Some("a")); - /// assert_eq!(map.pop(&1), None); + /// assert_eq!(map.remove(&1), Some("a")); + /// assert_eq!(map.remove(&1), None); /// ``` - pub fn pop(&mut self, key: &K) -> Option<V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn remove(&mut self, key: &K) -> Option<V> { // See `swap` for a more thorough description of the stuff going on in here let mut stack = stack::PartialSearchStack::new(self); loop { @@ -426,24 +439,6 @@ impl<K: Ord, V> BTreeMap<K, V> { } } } - - /// Removes a key-value pair from the map. Returns `true` if the key - /// was present in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::BTreeMap; - /// - /// let mut map = BTreeMap::new(); - /// assert_eq!(map.remove(&1u), false); - /// map.insert(1, "a"); - /// assert_eq!(map.remove(&1), true); - /// ``` - #[inline] - pub fn remove(&mut self, key: &K) -> bool { - self.pop(key).is_some() - } } /// The stack module provides a safe interface for constructing and manipulating a stack of ptrs @@ -793,13 +788,13 @@ impl<K: Show, V: Show> Show for BTreeMap<K, V> { impl<K: Ord, V> Index<K, V> for BTreeMap<K, V> { fn index(&self, key: &K) -> &V { - self.find(key).expect("no entry found for key") + self.get(key).expect("no entry found for key") } } impl<K: Ord, V> IndexMut<K, V> for BTreeMap<K, V> { fn index_mut(&mut self, key: &K) -> &mut V { - self.find_mut(key).expect("no entry found for key") + self.get_mut(key).expect("no entry found for key") } } @@ -891,8 +886,8 @@ impl<K, V, E, T: Traverse<E> + DoubleEndedIterator<TraversalItem<K, V, E>>> // Handle any operation on the left stack as necessary match op { - Push(item) => { self.left.push(item); }, - Pop => { self.left.pop(); }, + Push(item) => { self.left.push_back(item); }, + Pop => { self.left.pop_back(); }, } } } @@ -933,8 +928,8 @@ impl<K, V, E, T: Traverse<E> + DoubleEndedIterator<TraversalItem<K, V, E>>> }; match op { - Push(item) => { self.right.push(item); }, - Pop => { self.right.pop(); } + Push(item) => { self.right.push_back(item); }, + Pop => { self.right.pop_back(); } } } } @@ -1010,6 +1005,7 @@ impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> { impl<K, V> BTreeMap<K, V> { /// Gets an iterator over the entries of the map. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter<'a>(&'a self) -> Entries<'a, K, V> { let len = self.len(); Entries { @@ -1023,6 +1019,7 @@ impl<K, V> BTreeMap<K, V> { } /// Gets a mutable iterator over the entries of the map. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter_mut<'a>(&'a mut self) -> MutEntries<'a, K, V> { let len = self.len(); MutEntries { @@ -1036,6 +1033,7 @@ impl<K, V> BTreeMap<K, V> { } /// Gets an owning iterator over the entries of the map. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn into_iter(self) -> MoveEntries<K, V> { let len = self.len(); MoveEntries { @@ -1049,11 +1047,13 @@ impl<K, V> BTreeMap<K, V> { } /// Gets an iterator over the keys of the map. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn keys<'a>(&'a self) -> Keys<'a, K, V> { self.iter().map(|(k, _)| k) } /// Gets an iterator over the values of the map. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn values<'a>(&'a self) -> Values<'a, K, V> { self.iter().map(|(_, v)| v) } @@ -1070,6 +1070,7 @@ impl<K, V> BTreeMap<K, V> { /// a.insert(1u, "a"); /// assert_eq!(a.len(), 1); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.length } /// Return true if the map contains no elements. @@ -1084,6 +1085,7 @@ impl<K, V> BTreeMap<K, V> { /// a.insert(1u, "a"); /// assert!(!a.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.len() == 0 } } @@ -1137,40 +1139,40 @@ mod test { assert_eq!(map.len(), 0); for i in range(0, size) { - assert_eq!(map.swap(i, 10*i), None); + assert_eq!(map.insert(i, 10*i), None); assert_eq!(map.len(), i + 1); } for i in range(0, size) { - assert_eq!(map.find(&i).unwrap(), &(i*10)); + assert_eq!(map.get(&i).unwrap(), &(i*10)); } for i in range(size, size*2) { - assert_eq!(map.find(&i), None); + assert_eq!(map.get(&i), None); } for i in range(0, size) { - assert_eq!(map.swap(i, 100*i), Some(10*i)); + assert_eq!(map.insert(i, 100*i), Some(10*i)); assert_eq!(map.len(), size); } for i in range(0, size) { - assert_eq!(map.find(&i).unwrap(), &(i*100)); + assert_eq!(map.get(&i).unwrap(), &(i*100)); } for i in range(0, size/2) { - assert_eq!(map.pop(&(i*2)), Some(i*200)); + assert_eq!(map.remove(&(i*2)), Some(i*200)); assert_eq!(map.len(), size - i - 1); } for i in range(0, size/2) { - assert_eq!(map.find(&(2*i)), None); - assert_eq!(map.find(&(2*i+1)).unwrap(), &(i*200 + 100)); + assert_eq!(map.get(&(2*i)), None); + assert_eq!(map.get(&(2*i+1)).unwrap(), &(i*200 + 100)); } for i in range(0, size/2) { - assert_eq!(map.pop(&(2*i)), None); - assert_eq!(map.pop(&(2*i+1)), Some(i*200 + 100)); + assert_eq!(map.remove(&(2*i)), None); + assert_eq!(map.remove(&(2*i+1)), Some(i*200 + 100)); assert_eq!(map.len(), size/2 - i - 1); } } @@ -1178,17 +1180,17 @@ mod test { #[test] fn test_basic_small() { let mut map = BTreeMap::new(); - assert_eq!(map.pop(&1), None); - assert_eq!(map.find(&1), None); - assert_eq!(map.swap(1u, 1u), None); - assert_eq!(map.find(&1), Some(&1)); - assert_eq!(map.swap(1, 2), Some(1)); - assert_eq!(map.find(&1), Some(&2)); - assert_eq!(map.swap(2, 4), None); - assert_eq!(map.find(&2), Some(&4)); - assert_eq!(map.pop(&1), Some(2)); - assert_eq!(map.pop(&2), Some(4)); - assert_eq!(map.pop(&1), None); + assert_eq!(map.remove(&1), None); + assert_eq!(map.get(&1), None); + assert_eq!(map.insert(1u, 1u), None); + assert_eq!(map.get(&1), Some(&1)); + assert_eq!(map.insert(1, 2), Some(1)); + assert_eq!(map.get(&1), Some(&2)); + assert_eq!(map.insert(2, 4), None); + assert_eq!(map.get(&2), Some(&4)); + assert_eq!(map.remove(&1), Some(2)); + assert_eq!(map.remove(&2), Some(4)); + assert_eq!(map.remove(&1), None); } #[test] @@ -1283,7 +1285,7 @@ mod test { assert_eq!(view.set(100), 10); } } - assert_eq!(map.find(&1).unwrap(), &100); + assert_eq!(map.get(&1).unwrap(), &100); assert_eq!(map.len(), 6); @@ -1295,7 +1297,7 @@ mod test { *v *= 10; } } - assert_eq!(map.find(&2).unwrap(), &200); + assert_eq!(map.get(&2).unwrap(), &200); assert_eq!(map.len(), 6); // Existing key (take) @@ -1305,7 +1307,7 @@ mod test { assert_eq!(view.take(), 30); } } - assert_eq!(map.find(&3), None); + assert_eq!(map.get(&3), None); assert_eq!(map.len(), 5); @@ -1316,7 +1318,7 @@ mod test { assert_eq!(*view.set(1000), 1000); } } - assert_eq!(map.find(&10).unwrap(), &1000); + assert_eq!(map.get(&10).unwrap(), &1000); assert_eq!(map.len(), 6); } } @@ -1374,7 +1376,7 @@ mod bench { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); find_rand_n(100, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } #[bench] @@ -1382,7 +1384,7 @@ mod bench { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); find_rand_n(10_000, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } // Find seq @@ -1391,7 +1393,7 @@ mod bench { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); find_seq_n(100, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } #[bench] @@ -1399,7 +1401,7 @@ mod bench { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); find_seq_n(10_000, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } fn bench_iter(b: &mut Bencher, size: uint) { @@ -1407,7 +1409,7 @@ mod bench { let mut rng = weak_rng(); for _ in range(0, size) { - map.swap(rng.gen(), rng.gen()); + map.insert(rng.gen(), rng.gen()); } b.iter(|| { diff --git a/src/libcollections/btree/set.rs b/src/libcollections/btree/set.rs index 27752207b97..f6a3de11d13 100644 --- a/src/libcollections/btree/set.rs +++ b/src/libcollections/btree/set.rs @@ -20,6 +20,9 @@ use core::{iter, fmt}; use core::iter::Peekable; use core::fmt::Show; +// FIXME(conventions): implement bounded iterators +// FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub + /// A set based on a B-Tree. /// /// See BTreeMap's documentation for a detailed discussion of this collection's performance @@ -61,6 +64,7 @@ pub struct UnionItems<'a, T:'a> { impl<T: Ord> BTreeSet<T> { /// Makes a new BTreeSet with a reasonable choice of B. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> BTreeSet<T> { BTreeSet { map: BTreeMap::new() } } @@ -75,11 +79,13 @@ impl<T: Ord> BTreeSet<T> { impl<T> BTreeSet<T> { /// Gets an iterator over the BTreeSet's contents. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter<'a>(&'a self) -> Items<'a, T> { self.map.keys() } /// Gets an iterator for moving out the BtreeSet's contents. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn into_iter(self) -> MoveItems<T> { self.map.into_iter().map(|(k, _)| k) } @@ -87,23 +93,27 @@ impl<T> BTreeSet<T> { impl<T: Ord> BTreeSet<T> { /// Visits the values representing the difference, in ascending order. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> DifferenceItems<'a, T> { DifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()} } /// Visits the values representing the symmetric difference, in ascending order. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn symmetric_difference<'a>(&'a self, other: &'a BTreeSet<T>) -> SymDifferenceItems<'a, T> { SymDifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()} } /// Visits the values representing the intersection, in ascending order. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> IntersectionItems<'a, T> { IntersectionItems{a: self.iter().peekable(), b: other.iter().peekable()} } /// Visits the values representing the union, in ascending order. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> UnionItems<'a, T> { UnionItems{a: self.iter().peekable(), b: other.iter().peekable()} } @@ -120,6 +130,7 @@ impl<T: Ord> BTreeSet<T> { /// v.insert(1i); /// assert_eq!(v.len(), 1); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.map.len() } /// Returns true if the set contains no elements @@ -134,6 +145,7 @@ impl<T: Ord> BTreeSet<T> { /// v.insert(1i); /// assert!(!v.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.len() == 0 } /// Clears the set, removing all values. @@ -148,6 +160,7 @@ impl<T: Ord> BTreeSet<T> { /// v.clear(); /// assert!(v.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { self.map.clear() } @@ -163,8 +176,9 @@ impl<T: Ord> BTreeSet<T> { /// assert_eq!(set.contains(&1), true); /// assert_eq!(set.contains(&4), false); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn contains(&self, value: &T) -> bool { - self.map.find(value).is_some() + self.map.contains_key(value) } /// Returns `true` if the set has no elements in common with `other`. @@ -184,6 +198,7 @@ impl<T: Ord> BTreeSet<T> { /// b.insert(1); /// assert_eq!(a.is_disjoint(&b), false); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_disjoint(&self, other: &BTreeSet<T>) -> bool { self.intersection(other).next().is_none() } @@ -204,6 +219,7 @@ impl<T: Ord> BTreeSet<T> { /// set.insert(4); /// assert_eq!(set.is_subset(&sup), false); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_subset(&self, other: &BTreeSet<T>) -> bool { // Stolen from TreeMap let mut x = self.iter(); @@ -248,6 +264,7 @@ impl<T: Ord> BTreeSet<T> { /// set.insert(2); /// assert_eq!(set.is_superset(&sub), true); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_superset(&self, other: &BTreeSet<T>) -> bool { other.is_subset(self) } @@ -266,8 +283,9 @@ impl<T: Ord> BTreeSet<T> { /// assert_eq!(set.insert(2i), false); /// assert_eq!(set.len(), 1); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn insert(&mut self, value: T) -> bool { - self.map.insert(value, ()) + self.map.insert(value, ()).is_none() } /// Removes a value from the set. Returns `true` if the value was @@ -284,8 +302,9 @@ impl<T: Ord> BTreeSet<T> { /// assert_eq!(set.remove(&2), true); /// assert_eq!(set.remove(&2), false); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn remove(&mut self, value: &T) -> bool { - self.map.remove(value) + self.map.remove(value).is_some() } } diff --git a/src/libcollections/dlist.rs b/src/libcollections/dlist.rs index a1e286d1245..9d9955141df 100644 --- a/src/libcollections/dlist.rs +++ b/src/libcollections/dlist.rs @@ -195,6 +195,7 @@ impl<T> Default for DList<T> { impl<T> DList<T> { /// Creates an empty `DList`. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> DList<T> { DList{list_head: None, list_tail: Rawlink::none(), length: 0} } @@ -209,9 +210,9 @@ impl<T> DList<T> { /// use std::collections::DList; /// /// let mut dl = DList::new(); - /// dl.push(1i); - /// dl.push(2); - /// dl.push(3); + /// dl.push_back(1i); + /// dl.push_back(2); + /// dl.push_back(3); /// /// dl.rotate_forward(); /// @@ -236,9 +237,9 @@ impl<T> DList<T> { /// use std::collections::DList; /// /// let mut dl = DList::new(); - /// dl.push(1i); - /// dl.push(2); - /// dl.push(3); + /// dl.push_back(1i); + /// dl.push_back(2); + /// dl.push_back(3); /// /// dl.rotate_backward(); /// @@ -264,10 +265,10 @@ impl<T> DList<T> { /// /// let mut a = DList::new(); /// let mut b = DList::new(); - /// a.push(1i); - /// a.push(2); - /// b.push(3i); - /// b.push(4); + /// a.push_back(1i); + /// a.push_back(2); + /// b.push_back(3i); + /// b.push_back(4); /// /// a.append(b); /// @@ -305,10 +306,10 @@ impl<T> DList<T> { /// /// let mut a = DList::new(); /// let mut b = DList::new(); - /// a.push(1i); - /// a.push(2); - /// b.push(3i); - /// b.push(4); + /// a.push_back(1i); + /// a.push_back(2); + /// b.push_back(3i); + /// b.push_back(4); /// /// a.prepend(b); /// @@ -333,10 +334,10 @@ impl<T> DList<T> { /// use std::collections::DList; /// /// let mut a: DList<int> = DList::new(); - /// a.push(2i); - /// a.push(4); - /// a.push(7); - /// a.push(8); + /// a.push_back(2i); + /// a.push_back(4); + /// a.push_back(7); + /// a.push_back(8); /// /// // insert 11 before the first odd number in the list /// a.insert_when(11, |&e, _| e % 2 == 1); @@ -387,12 +388,14 @@ impl<T> DList<T> { /// Provides a forward iterator. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter<'a>(&'a self) -> Items<'a, T> { Items{nelem: self.len(), head: &self.list_head, tail: self.list_tail} } /// Provides a forward iterator with mutable references. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter_mut<'a>(&'a mut self) -> MutItems<'a, T> { let head_raw = match self.list_head { Some(ref mut h) => Rawlink::some(&mut **h), @@ -408,6 +411,7 @@ impl<T> DList<T> { /// Consumes the list into an iterator yielding elements by value. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn into_iter(self) -> MoveItems<T> { MoveItems{list: self} } @@ -416,6 +420,7 @@ impl<T> DList<T> { /// /// This operation should compute in O(1) time. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.list_head.is_none() } @@ -424,6 +429,7 @@ impl<T> DList<T> { /// /// This operation should compute in O(1) time. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.length } @@ -432,6 +438,7 @@ impl<T> DList<T> { /// /// This operation should compute in O(n) time. #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { *self = DList::new() } @@ -439,34 +446,39 @@ impl<T> DList<T> { /// Provides a reference to the front element, or `None` if the list is /// empty. #[inline] - pub fn front<'a>(&'a self) -> Option<&'a T> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn front(&self) -> Option<&T> { self.list_head.as_ref().map(|head| &head.value) } /// Provides a mutable reference to the front element, or `None` if the list /// is empty. #[inline] - pub fn front_mut<'a>(&'a mut self) -> Option<&'a mut T> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn front_mut(&mut self) -> Option<&mut T> { self.list_head.as_mut().map(|head| &mut head.value) } /// Provides a reference to the back element, or `None` if the list is /// empty. #[inline] - pub fn back<'a>(&'a self) -> Option<&'a T> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn back(&self) -> Option<&T> { self.list_tail.resolve_immut().as_ref().map(|tail| &tail.value) } /// Provides a mutable reference to the back element, or `None` if the list /// is empty. #[inline] - pub fn back_mut<'a>(&'a mut self) -> Option<&'a mut T> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn back_mut(&mut self) -> Option<&mut T> { self.list_tail.resolve().map(|tail| &mut tail.value) } /// Adds an element first in the list. /// /// This operation should compute in O(1) time. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn push_front(&mut self, elt: T) { self.push_front_node(box Node::new(elt)) } @@ -475,10 +487,17 @@ impl<T> DList<T> { /// empty. /// /// This operation should compute in O(1) time. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn pop_front(&mut self) -> Option<T> { self.pop_front_node().map(|box Node{value, ..}| value) } + /// Deprecated: Renamed to `push_back`. + #[deprecated = "Renamed to `push_back`"] + pub fn push(&mut self, elt: T) { + self.push_back(elt) + } + /// Appends an element to the back of a list /// /// # Example @@ -487,14 +506,21 @@ impl<T> DList<T> { /// use std::collections::DList; /// /// let mut d = DList::new(); - /// d.push(1i); - /// d.push(3); + /// d.push_back(1i); + /// d.push_back(3); /// assert_eq!(3, *d.back().unwrap()); /// ``` - pub fn push(&mut self, elt: T) { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn push_back(&mut self, elt: T) { self.push_back_node(box Node::new(elt)) } + /// Deprecated: Renamed to `pop_back`. + #[deprecated = "Renamed to `pop_back`"] + pub fn pop(&mut self) -> Option<T> { + self.pop_back() + } + /// Removes the last element from a list and returns it, or `None` if /// it is empty. /// @@ -504,12 +530,13 @@ impl<T> DList<T> { /// use std::collections::DList; /// /// let mut d = DList::new(); - /// assert_eq!(d.pop(), None); - /// d.push(1i); - /// d.push(3); - /// assert_eq!(d.pop(), Some(3)); + /// assert_eq!(d.pop_back(), None); + /// d.push_back(1i); + /// d.push_back(3); + /// assert_eq!(d.pop_back(), Some(3)); /// ``` - pub fn pop(&mut self) -> Option<T> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn pop_back(&mut self) -> Option<T> { self.pop_back_node().map(|box Node{value, ..}| value) } } @@ -682,7 +709,7 @@ impl<A> Iterator<A> for MoveItems<A> { impl<A> DoubleEndedIterator<A> for MoveItems<A> { #[inline] - fn next_back(&mut self) -> Option<A> { self.list.pop() } + fn next_back(&mut self) -> Option<A> { self.list.pop_back() } } impl<A> FromIterator<A> for DList<A> { @@ -695,7 +722,7 @@ impl<A> FromIterator<A> for DList<A> { impl<A> Extendable<A> for DList<A> { fn extend<T: Iterator<A>>(&mut self, mut iterator: T) { - for elt in iterator { self.push(elt); } + for elt in iterator { self.push_back(elt); } } } @@ -801,21 +828,21 @@ mod tests { fn test_basic() { let mut m: DList<Box<int>> = DList::new(); assert_eq!(m.pop_front(), None); - assert_eq!(m.pop(), None); + assert_eq!(m.pop_back(), None); assert_eq!(m.pop_front(), None); m.push_front(box 1); assert_eq!(m.pop_front(), Some(box 1)); - m.push(box 2); - m.push(box 3); + m.push_back(box 2); + m.push_back(box 3); assert_eq!(m.len(), 2); assert_eq!(m.pop_front(), Some(box 2)); assert_eq!(m.pop_front(), Some(box 3)); assert_eq!(m.len(), 0); assert_eq!(m.pop_front(), None); - m.push(box 1); - m.push(box 3); - m.push(box 5); - m.push(box 7); + m.push_back(box 1); + m.push_back(box 3); + m.push_back(box 5); + m.push_back(box 7); assert_eq!(m.pop_front(), Some(box 1)); let mut n = DList::new(); @@ -853,19 +880,19 @@ mod tests { { let mut m = DList::new(); let mut n = DList::new(); - n.push(2i); + n.push_back(2i); m.append(n); assert_eq!(m.len(), 1); - assert_eq!(m.pop(), Some(2)); + assert_eq!(m.pop_back(), Some(2)); check_links(&m); } { let mut m = DList::new(); let n = DList::new(); - m.push(2i); + m.push_back(2i); m.append(n); assert_eq!(m.len(), 1); - assert_eq!(m.pop(), Some(2)); + assert_eq!(m.pop_back(), Some(2)); check_links(&m); } @@ -887,10 +914,10 @@ mod tests { { let mut m = DList::new(); let mut n = DList::new(); - n.push(2i); + n.push_back(2i); m.prepend(n); assert_eq!(m.len(), 1); - assert_eq!(m.pop(), Some(2)); + assert_eq!(m.pop_back(), Some(2)); check_links(&m); } @@ -948,9 +975,9 @@ mod tests { #[test] fn test_iterator_clone() { let mut n = DList::new(); - n.push(2i); - n.push(3); - n.push(4); + n.push_back(2i); + n.push_back(3); + n.push_back(4); let mut it = n.iter(); it.next(); let mut jt = it.clone(); @@ -1005,7 +1032,7 @@ mod tests { let mut n = DList::new(); assert!(n.iter_mut().next().is_none()); n.push_front(4i); - n.push(5); + n.push_back(5); let mut it = n.iter_mut(); assert_eq!(it.size_hint(), (2, Some(2))); assert!(it.next().is_some()); @@ -1079,8 +1106,8 @@ mod tests { assert_eq!(n.pop_front(), Some(1)); let mut m = DList::new(); - m.push(2i); - m.push(4); + m.push_back(2i); + m.push_back(4); m.insert_ordered(3); check_links(&m); assert_eq!(vec![2,3,4], m.into_iter().collect::<Vec<int>>()); @@ -1117,7 +1144,7 @@ mod tests { assert!(n == m); n.push_front(1); assert!(n != m); - m.push(1); + m.push_back(1); assert!(n == m); let n = list_from([2i,3,4]); @@ -1132,9 +1159,9 @@ mod tests { assert!(hash::hash(&x) == hash::hash(&y)); - x.push(1i); - x.push(2); - x.push(3); + x.push_back(1i); + x.push_back(2); + x.push_back(3); y.push_front(3i); y.push_front(2); @@ -1214,7 +1241,7 @@ mod tests { let r: u8 = rand::random(); match r % 6 { 0 => { - m.pop(); + m.pop_back(); v.pop(); } 1 => { @@ -1226,7 +1253,7 @@ mod tests { v.insert(0, -i); } 3 | 5 | _ => { - m.push(i); + m.push_back(i); v.push(i); } } @@ -1262,7 +1289,7 @@ mod tests { fn bench_push_back(b: &mut test::Bencher) { let mut m: DList<int> = DList::new(); b.iter(|| { - m.push(0); + m.push_back(0); }) } @@ -1270,8 +1297,8 @@ mod tests { fn bench_push_back_pop_back(b: &mut test::Bencher) { let mut m: DList<int> = DList::new(); b.iter(|| { - m.push(0); - m.pop(); + m.push_back(0); + m.pop_back(); }) } diff --git a/src/libcollections/enum_set.rs b/src/libcollections/enum_set.rs index bcae4fe68c9..454d4f1ca87 100644 --- a/src/libcollections/enum_set.rs +++ b/src/libcollections/enum_set.rs @@ -16,6 +16,10 @@ use core::prelude::*; use core::fmt; +// FIXME(conventions): implement BitXor +// FIXME(contentions): implement union family of methods? (general design may be wrong here) +// FIXME(conventions): implement len + #[deriving(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] /// A specialized `Set` implementation to use enum types. pub struct EnumSet<E> { @@ -47,34 +51,56 @@ pub trait CLike { fn from_uint(uint) -> Self; } -fn bit<E:CLike>(e: E) -> uint { +fn bit<E:CLike>(e: &E) -> uint { 1 << e.to_uint() } impl<E:CLike> EnumSet<E> { - /// Returns an empty `EnumSet`. + /// Deprecated: Renamed to `new`. + #[deprecated = "Renamed to `new`"] pub fn empty() -> EnumSet<E> { + EnumSet::new() + } + + /// Returns an empty `EnumSet`. + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn new() -> EnumSet<E> { EnumSet {bits: 0} } /// Returns true if the `EnumSet` is empty. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.bits == 0 } + pub fn clear(&mut self) { + self.bits = 0; + } + /// Returns `true` if the `EnumSet` contains any enum of the given `EnumSet`. + /// Deprecated: Use `is_disjoint`. + #[deprecated = "Use `is_disjoint`"] pub fn intersects(&self, e: EnumSet<E>) -> bool { - (self.bits & e.bits) != 0 + !self.is_disjoint(&e) } - /// Returns the intersection of both `EnumSets`. - pub fn intersection(&self, e: EnumSet<E>) -> EnumSet<E> { - EnumSet {bits: self.bits & e.bits} + /// Returns `false` if the `EnumSet` contains any enum of the given `EnumSet`. + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn is_disjoint(&self, other: &EnumSet<E>) -> bool { + (self.bits & other.bits) == 0 } - /// Returns `true` if a given `EnumSet` is included in an `EnumSet`. - pub fn contains(&self, e: EnumSet<E>) -> bool { - (self.bits & e.bits) == e.bits + /// Returns `true` if a given `EnumSet` is included in this `EnumSet`. + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn is_superset(&self, other: &EnumSet<E>) -> bool { + (self.bits & other.bits) == other.bits + } + + /// Returns `true` if this `EnumSet` is included in the given `EnumSet`. + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn is_subset(&self, other: &EnumSet<E>) -> bool { + other.is_subset(self) } /// Returns the union of both `EnumSets`. @@ -82,17 +108,47 @@ impl<E:CLike> EnumSet<E> { EnumSet {bits: self.bits | e.bits} } - /// Adds an enum to an `EnumSet`. + /// Returns the intersection of both `EnumSets`. + pub fn intersection(&self, e: EnumSet<E>) -> EnumSet<E> { + EnumSet {bits: self.bits & e.bits} + } + + /// Deprecated: Use `insert`. + #[deprecated = "Use `insert`"] pub fn add(&mut self, e: E) { - self.bits |= bit(e); + self.insert(e); } - /// Returns `true` if an `EnumSet` contains a given enum. + /// Adds an enum to the `EnumSet`, and returns `true` if it wasn't there before + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn insert(&mut self, e: E) -> bool { + let result = !self.contains(&e); + self.bits |= bit(&e); + result + } + + /// Removes an enum from the EnumSet + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn remove(&mut self, e: &E) -> bool { + let result = self.contains(e); + self.bits &= !bit(e); + result + } + + /// Deprecated: use `contains`. + #[deprecated = "use `contains"] pub fn contains_elem(&self, e: E) -> bool { + self.contains(&e) + } + + /// Returns `true` if an `EnumSet` contains a given enum. + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn contains(&self, e: &E) -> bool { (self.bits & bit(e)) != 0 } /// Returns an iterator over an `EnumSet`. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter(&self) -> Items<E> { Items::new(self.bits) } @@ -174,18 +230,18 @@ mod test { } #[test] - fn test_empty() { - let e: EnumSet<Foo> = EnumSet::empty(); + fn test_new() { + let e: EnumSet<Foo> = EnumSet::new(); assert!(e.is_empty()); } #[test] fn test_show() { - let mut e = EnumSet::empty(); + let mut e = EnumSet::new(); assert_eq!("{}", e.to_string().as_slice()); - e.add(A); + e.insert(A); assert_eq!("{A}", e.to_string().as_slice()); - e.add(C); + e.insert(C); assert_eq!("{A, C}", e.to_string().as_slice()); } @@ -194,75 +250,75 @@ mod test { #[test] fn test_two_empties_do_not_intersect() { - let e1: EnumSet<Foo> = EnumSet::empty(); - let e2: EnumSet<Foo> = EnumSet::empty(); - assert!(!e1.intersects(e2)); + let e1: EnumSet<Foo> = EnumSet::new(); + let e2: EnumSet<Foo> = EnumSet::new(); + assert!(e1.is_disjoint(&e2)); } #[test] fn test_empty_does_not_intersect_with_full() { - let e1: EnumSet<Foo> = EnumSet::empty(); + let e1: EnumSet<Foo> = EnumSet::new(); - let mut e2: EnumSet<Foo> = EnumSet::empty(); - e2.add(A); - e2.add(B); - e2.add(C); + let mut e2: EnumSet<Foo> = EnumSet::new(); + e2.insert(A); + e2.insert(B); + e2.insert(C); - assert!(!e1.intersects(e2)); + assert!(e1.is_disjoint(&e2)); } #[test] fn test_disjoint_intersects() { - let mut e1: EnumSet<Foo> = EnumSet::empty(); - e1.add(A); + let mut e1: EnumSet<Foo> = EnumSet::new(); + e1.insert(A); - let mut e2: EnumSet<Foo> = EnumSet::empty(); - e2.add(B); + let mut e2: EnumSet<Foo> = EnumSet::new(); + e2.insert(B); - assert!(!e1.intersects(e2)); + assert!(e1.is_disjoint(&e2)); } #[test] fn test_overlapping_intersects() { - let mut e1: EnumSet<Foo> = EnumSet::empty(); - e1.add(A); + let mut e1: EnumSet<Foo> = EnumSet::new(); + e1.insert(A); - let mut e2: EnumSet<Foo> = EnumSet::empty(); - e2.add(A); - e2.add(B); + let mut e2: EnumSet<Foo> = EnumSet::new(); + e2.insert(A); + e2.insert(B); - assert!(e1.intersects(e2)); + assert!(!e1.is_disjoint(&e2)); } /////////////////////////////////////////////////////////////////////////// // contains and contains_elem #[test] - fn test_contains() { - let mut e1: EnumSet<Foo> = EnumSet::empty(); - e1.add(A); + fn test_superset() { + let mut e1: EnumSet<Foo> = EnumSet::new(); + e1.insert(A); - let mut e2: EnumSet<Foo> = EnumSet::empty(); - e2.add(A); - e2.add(B); + let mut e2: EnumSet<Foo> = EnumSet::new(); + e2.insert(A); + e2.insert(B); - assert!(!e1.contains(e2)); - assert!(e2.contains(e1)); + assert!(!e1.is_superset(&e2)); + assert!(e2.is_superset(&e1)); } #[test] - fn test_contains_elem() { - let mut e1: EnumSet<Foo> = EnumSet::empty(); - e1.add(A); - assert!(e1.contains_elem(A)); - assert!(!e1.contains_elem(B)); - assert!(!e1.contains_elem(C)); - - e1.add(A); - e1.add(B); - assert!(e1.contains_elem(A)); - assert!(e1.contains_elem(B)); - assert!(!e1.contains_elem(C)); + fn test_contains() { + let mut e1: EnumSet<Foo> = EnumSet::new(); + e1.insert(A); + assert!(e1.contains(&A)); + assert!(!e1.contains(&B)); + assert!(!e1.contains(&C)); + + e1.insert(A); + e1.insert(B); + assert!(e1.contains(&A)); + assert!(e1.contains(&B)); + assert!(!e1.contains(&C)); } /////////////////////////////////////////////////////////////////////////// @@ -270,24 +326,24 @@ mod test { #[test] fn test_iterator() { - let mut e1: EnumSet<Foo> = EnumSet::empty(); + let mut e1: EnumSet<Foo> = EnumSet::new(); let elems: Vec<Foo> = e1.iter().collect(); assert!(elems.is_empty()) - e1.add(A); + e1.insert(A); let elems = e1.iter().collect(); assert_eq!(vec![A], elems) - e1.add(C); + e1.insert(C); let elems = e1.iter().collect(); assert_eq!(vec![A,C], elems) - e1.add(C); + e1.insert(C); let elems = e1.iter().collect(); assert_eq!(vec![A,C], elems) - e1.add(B); + e1.insert(B); let elems = e1.iter().collect(); assert_eq!(vec![A,B,C], elems) } @@ -297,13 +353,13 @@ mod test { #[test] fn test_operators() { - let mut e1: EnumSet<Foo> = EnumSet::empty(); - e1.add(A); - e1.add(C); + let mut e1: EnumSet<Foo> = EnumSet::new(); + e1.insert(A); + e1.insert(C); - let mut e2: EnumSet<Foo> = EnumSet::empty(); - e2.add(B); - e2.add(C); + let mut e2: EnumSet<Foo> = EnumSet::new(); + e2.insert(B); + e2.insert(C); let e_union = e1 | e2; let elems = e_union.iter().collect(); diff --git a/src/libcollections/ring_buf.rs b/src/libcollections/ring_buf.rs index 3c4c3fce61d..549ebb14b3e 100644 --- a/src/libcollections/ring_buf.rs +++ b/src/libcollections/ring_buf.rs @@ -27,6 +27,11 @@ use vec::Vec; static INITIAL_CAPACITY: uint = 8u; // 2^3 static MINIMUM_CAPACITY: uint = 2u; +// FIXME(conventions): implement shrink_to_fit. Awkward with the current design, but it should +// be scrapped anyway. Defer to rewrite? +// FIXME(conventions): implement into_iter + + /// `RingBuf` is a circular buffer that implements `Deque`. #[deriving(Clone)] pub struct RingBuf<T> { @@ -42,11 +47,13 @@ impl<T> Default for RingBuf<T> { impl<T> RingBuf<T> { /// Creates an empty `RingBuf`. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> RingBuf<T> { RingBuf::with_capacity(INITIAL_CAPACITY) } /// Creates an empty `RingBuf` with space for at least `n` elements. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn with_capacity(n: uint) -> RingBuf<T> { RingBuf{nelts: 0, lo: 0, elts: Vec::from_fn(cmp::max(MINIMUM_CAPACITY, n), |_| None)} @@ -54,24 +61,51 @@ impl<T> RingBuf<T> { /// Retrieves an element in the `RingBuf` by index. /// - /// Fails if there is no element with the given index. + /// # Example + /// + /// ```rust + /// use std::collections::RingBuf; + /// + /// let mut buf = RingBuf::new(); + /// buf.push_back(3i); + /// buf.push_back(4); + /// buf.push_back(5); + /// assert_eq!(buf.get(1).unwrap(), &4); + /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get(&self, i: uint) -> Option<&T> { + match self.elts.get(i) { + None => None, + Some(opt) => opt.as_ref(), + } + } + + /// Retrieves an element in the `RingBuf` mutably by index. /// /// # Example /// /// ```rust - /// # #![allow(deprecated)] /// use std::collections::RingBuf; /// /// let mut buf = RingBuf::new(); - /// buf.push(3i); - /// buf.push(4); - /// buf.push(5); - /// *buf.get_mut(1) = 7; + /// buf.push_back(3i); + /// buf.push_back(4); + /// buf.push_back(5); + /// match buf.get_mut(1) { + /// None => {} + /// Some(elem) => { + /// *elem = 7; + /// } + /// } + /// /// assert_eq!(buf[1], 7); /// ``` - #[deprecated = "use indexing instead: `buf[index] = value`"] - pub fn get_mut(&mut self, i: uint) -> &mut T { - &mut self[i] + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get_mut(&mut self, i: uint) -> Option<&mut T> { + match self.elts.get_mut(i) { + None => None, + Some(opt) => opt.as_mut(), + } } /// Swaps elements at indices `i` and `j`. @@ -86,9 +120,9 @@ impl<T> RingBuf<T> { /// use std::collections::RingBuf; /// /// let mut buf = RingBuf::new(); - /// buf.push(3i); - /// buf.push(4); - /// buf.push(5); + /// buf.push_back(3i); + /// buf.push_back(4); + /// buf.push_back(5); /// buf.swap(0, 2); /// assert_eq!(buf[0], 5); /// assert_eq!(buf[2], 3); @@ -107,21 +141,70 @@ impl<T> RingBuf<T> { raw_index(self.lo, self.elts.len(), idx) } - /// Reserves capacity for exactly `n` elements in the given `RingBuf`, - /// doing nothing if `self`'s capacity is already equal to or greater - /// than the requested capacity. - pub fn reserve_exact(&mut self, n: uint) { - self.elts.reserve_exact(n); + /// Returns the number of elements the `RingBuf` can hold without + /// reallocating. + /// + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let buf: RingBuf<int> = RingBuf::with_capacity(10); + /// assert_eq!(buf.capacity(), 10); + /// ``` + #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn capacity(&self) -> uint { + // FXIME(Gankro): not the actual usable capacity if you use reserve/reserve_exact + self.elts.capacity() } - /// Reserves capacity for at least `n` elements in the given `RingBuf`, - /// over-allocating in case the caller needs to reserve additional - /// space. + /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the + /// given `RingBuf`. Does nothing if the capacity is already sufficient. + /// + /// Note that the allocator may give the collection more space than it requests. Therefore + /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future + /// insertions are expected. + /// + /// # Panics + /// + /// Panics if the new capacity overflows `uint`. /// - /// Do nothing if `self`'s capacity is already equal to or greater - /// than the requested capacity. - pub fn reserve(&mut self, n: uint) { - self.elts.reserve(n); + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let mut buf: RingBuf<int> = vec![1].into_iter().collect(); + /// buf.reserve_exact(10); + /// assert!(buf.capacity() >= 11); + /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn reserve_exact(&mut self, additional: uint) { + // FIXME(Gankro): this is just wrong. The ringbuf won't actually use this space + self.elts.reserve_exact(additional); + } + + /// Reserves capacity for at least `additional` more elements to be inserted in the given + /// `Ringbuf`. The collection may reserve more space to avoid frequent reallocations. + /// + /// # Panics + /// + /// Panics if the new capacity overflows `uint`. + /// + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let mut buf: RingBuf<int> = vec![1].into_iter().collect(); + /// buf.reserve(10); + /// assert!(buf.capacity() >= 11); + /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn reserve(&mut self, additional: uint) { + // FIXME(Gankro): this is just wrong. The ringbuf won't actually use this space + self.elts.reserve(additional); } /// Returns a front-to-back iterator. @@ -132,12 +215,13 @@ impl<T> RingBuf<T> { /// use std::collections::RingBuf; /// /// let mut buf = RingBuf::new(); - /// buf.push(5i); - /// buf.push(3); - /// buf.push(4); + /// buf.push_back(5i); + /// buf.push_back(3); + /// buf.push_back(4); /// let b: &[_] = &[&5, &3, &4]; /// assert_eq!(buf.iter().collect::<Vec<&int>>().as_slice(), b); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter(&self) -> Items<T> { Items{index: 0, rindex: self.nelts, lo: self.lo, elts: self.elts.as_slice()} } @@ -150,15 +234,16 @@ impl<T> RingBuf<T> { /// use std::collections::RingBuf; /// /// let mut buf = RingBuf::new(); - /// buf.push(5i); - /// buf.push(3); - /// buf.push(4); + /// buf.push_back(5i); + /// buf.push_back(3); + /// buf.push_back(4); /// for num in buf.iter_mut() { /// *num = *num - 2; /// } /// let b: &[_] = &[&mut 3, &mut 1, &mut 2]; /// assert_eq!(buf.iter_mut().collect::<Vec<&mut int>>()[], b); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter_mut(&mut self) -> MutItems<T> { let start_index = raw_index(self.lo, self.elts.len(), 0); let end_index = raw_index(self.lo, self.elts.len(), self.nelts); @@ -197,9 +282,10 @@ impl<T> RingBuf<T> { /// /// let mut v = RingBuf::new(); /// assert_eq!(v.len(), 0); - /// v.push(1i); + /// v.push_back(1i); /// assert_eq!(v.len(), 1); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.nelts } /// Returns true if the buffer contains no elements @@ -214,6 +300,7 @@ impl<T> RingBuf<T> { /// v.push_front(1i); /// assert!(!v.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.len() == 0 } /// Clears the buffer, removing all values. @@ -224,10 +311,11 @@ impl<T> RingBuf<T> { /// use std::collections::RingBuf; /// /// let mut v = RingBuf::new(); - /// v.push(1i); + /// v.push_back(1i); /// v.clear(); /// assert!(v.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { for x in self.elts.iter_mut() { *x = None } self.nelts = 0; @@ -245,10 +333,11 @@ impl<T> RingBuf<T> { /// let mut d = RingBuf::new(); /// assert_eq!(d.front(), None); /// - /// d.push(1i); - /// d.push(2i); + /// d.push_back(1i); + /// d.push_back(2i); /// assert_eq!(d.front(), Some(&1i)); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn front(&self) -> Option<&T> { if self.nelts > 0 { Some(&self[0]) } else { None } } @@ -264,14 +353,15 @@ impl<T> RingBuf<T> { /// let mut d = RingBuf::new(); /// assert_eq!(d.front_mut(), None); /// - /// d.push(1i); - /// d.push(2i); + /// d.push_back(1i); + /// d.push_back(2i); /// match d.front_mut() { /// Some(x) => *x = 9i, /// None => (), /// } /// assert_eq!(d.front(), Some(&9i)); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn front_mut(&mut self) -> Option<&mut T> { if self.nelts > 0 { Some(&mut self[0]) } else { None } } @@ -287,10 +377,11 @@ impl<T> RingBuf<T> { /// let mut d = RingBuf::new(); /// assert_eq!(d.back(), None); /// - /// d.push(1i); - /// d.push(2i); + /// d.push_back(1i); + /// d.push_back(2i); /// assert_eq!(d.back(), Some(&2i)); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn back(&self) -> Option<&T> { if self.nelts > 0 { Some(&self[self.nelts - 1]) } else { None } } @@ -306,14 +397,15 @@ impl<T> RingBuf<T> { /// let mut d = RingBuf::new(); /// assert_eq!(d.back(), None); /// - /// d.push(1i); - /// d.push(2i); + /// d.push_back(1i); + /// d.push_back(2i); /// match d.back_mut() { /// Some(x) => *x = 9i, /// None => (), /// } /// assert_eq!(d.back(), Some(&9i)); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn back_mut(&mut self) -> Option<&mut T> { let nelts = self.nelts; if nelts > 0 { Some(&mut self[nelts - 1]) } else { None } @@ -328,13 +420,14 @@ impl<T> RingBuf<T> { /// use std::collections::RingBuf; /// /// let mut d = RingBuf::new(); - /// d.push(1i); - /// d.push(2i); + /// d.push_back(1i); + /// d.push_back(2i); /// /// assert_eq!(d.pop_front(), Some(1i)); /// assert_eq!(d.pop_front(), Some(2i)); /// assert_eq!(d.pop_front(), None); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn pop_front(&mut self) -> Option<T> { let result = self.elts[self.lo].take(); if result.is_some() { @@ -356,6 +449,7 @@ impl<T> RingBuf<T> { /// d.push_front(2i); /// assert_eq!(d.front(), Some(&2i)); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn push_front(&mut self, t: T) { if self.nelts == self.elts.len() { grow(self.nelts, &mut self.lo, &mut self.elts); @@ -367,6 +461,12 @@ impl<T> RingBuf<T> { self.nelts += 1u; } + /// Deprecated: Renamed to `push_back`. + #[deprecated = "Renamed to `push_back`"] + pub fn push(&mut self, t: T) { + self.push_back(t) + } + /// Appends an element to the back of a buffer /// /// # Example @@ -375,11 +475,12 @@ impl<T> RingBuf<T> { /// use std::collections::RingBuf; /// /// let mut buf = RingBuf::new(); - /// buf.push(1i); - /// buf.push(3); + /// buf.push_back(1i); + /// buf.push_back(3); /// assert_eq!(3, *buf.back().unwrap()); /// ``` - pub fn push(&mut self, t: T) { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn push_back(&mut self, t: T) { if self.nelts == self.elts.len() { grow(self.nelts, &mut self.lo, &mut self.elts); } @@ -388,6 +489,12 @@ impl<T> RingBuf<T> { self.nelts += 1u; } + /// Deprecated: Renamed to `pop_back`. + #[deprecated = "Renamed to `pop_back`"] + pub fn pop(&mut self) -> Option<T> { + self.pop_back() + } + /// Removes the last element from a buffer and returns it, or `None` if /// it is empty. /// @@ -397,12 +504,13 @@ impl<T> RingBuf<T> { /// use std::collections::RingBuf; /// /// let mut buf = RingBuf::new(); - /// assert_eq!(buf.pop(), None); - /// buf.push(1i); - /// buf.push(3); - /// assert_eq!(buf.pop(), Some(3)); + /// assert_eq!(buf.pop_back(), None); + /// buf.push_back(1i); + /// buf.push_back(3); + /// assert_eq!(buf.pop_back(), Some(3)); /// ``` - pub fn pop(&mut self) -> Option<T> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn pop_back(&mut self) -> Option<T> { if self.nelts > 0 { self.nelts -= 1; let hi = self.raw_index(self.nelts); @@ -523,7 +631,7 @@ impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {} fn grow<T>(nelts: uint, loptr: &mut uint, elts: &mut Vec<Option<T>>) { assert_eq!(nelts, elts.len()); let lo = *loptr; - elts.reserve(nelts * 2); + elts.reserve_exact(nelts); let newlen = elts.capacity(); /* fill with None */ @@ -630,7 +738,7 @@ impl<A> FromIterator<A> for RingBuf<A> { impl<A> Extendable<A> for RingBuf<A> { fn extend<T: Iterator<A>>(&mut self, mut iterator: T) { for elt in iterator { - self.push(elt); + self.push_back(elt); } } } @@ -666,9 +774,9 @@ mod tests { assert_eq!(d.len(), 0u); d.push_front(17i); d.push_front(42i); - d.push(137); + d.push_back(137); assert_eq!(d.len(), 3u); - d.push(137); + d.push_back(137); assert_eq!(d.len(), 4u); debug!("{}", d.front()); assert_eq!(*d.front().unwrap(), 42); @@ -677,21 +785,21 @@ mod tests { let mut i = d.pop_front(); debug!("{}", i); assert_eq!(i, Some(42)); - i = d.pop(); + i = d.pop_back(); debug!("{}", i); assert_eq!(i, Some(137)); - i = d.pop(); + i = d.pop_back(); debug!("{}", i); assert_eq!(i, Some(137)); - i = d.pop(); + i = d.pop_back(); debug!("{}", i); assert_eq!(i, Some(17)); assert_eq!(d.len(), 0u); - d.push(3); + d.push_back(3); assert_eq!(d.len(), 1u); d.push_front(2); assert_eq!(d.len(), 2u); - d.push(4); + d.push_back(4); assert_eq!(d.len(), 3u); d.push_front(1); assert_eq!(d.len(), 4u); @@ -711,22 +819,22 @@ mod tests { assert_eq!(deq.len(), 0); deq.push_front(a.clone()); deq.push_front(b.clone()); - deq.push(c.clone()); + deq.push_back(c.clone()); assert_eq!(deq.len(), 3); - deq.push(d.clone()); + deq.push_back(d.clone()); assert_eq!(deq.len(), 4); assert_eq!((*deq.front().unwrap()).clone(), b.clone()); assert_eq!((*deq.back().unwrap()).clone(), d.clone()); assert_eq!(deq.pop_front().unwrap(), b.clone()); - assert_eq!(deq.pop().unwrap(), d.clone()); - assert_eq!(deq.pop().unwrap(), c.clone()); - assert_eq!(deq.pop().unwrap(), a.clone()); + assert_eq!(deq.pop_back().unwrap(), d.clone()); + assert_eq!(deq.pop_back().unwrap(), c.clone()); + assert_eq!(deq.pop_back().unwrap(), a.clone()); assert_eq!(deq.len(), 0); - deq.push(c.clone()); + deq.push_back(c.clone()); assert_eq!(deq.len(), 1); deq.push_front(b.clone()); assert_eq!(deq.len(), 2); - deq.push(d.clone()); + deq.push_back(d.clone()); assert_eq!(deq.len(), 3); deq.push_front(a.clone()); assert_eq!(deq.len(), 4); @@ -750,7 +858,7 @@ mod tests { let mut deq = RingBuf::new(); for i in range(0u, 66) { - deq.push(i); + deq.push_back(i); } for i in range(0u, 66) { @@ -788,7 +896,7 @@ mod tests { fn bench_push_back(b: &mut test::Bencher) { let mut deq = RingBuf::new(); b.iter(|| { - deq.push(0i); + deq.push_back(0i); }) } @@ -861,17 +969,17 @@ mod tests { #[test] fn test_with_capacity() { let mut d = RingBuf::with_capacity(0); - d.push(1i); + d.push_back(1i); assert_eq!(d.len(), 1); let mut d = RingBuf::with_capacity(50); - d.push(1i); + d.push_back(1i); assert_eq!(d.len(), 1); } #[test] fn test_with_capacity_non_power_two() { let mut d3 = RingBuf::with_capacity(3); - d3.push(1i); + d3.push_back(1i); // X = None, | = lo // [|1, X, X] @@ -880,20 +988,20 @@ mod tests { assert_eq!(d3.front(), None); // [X, |3, X] - d3.push(3); + d3.push_back(3); // [X, |3, 6] - d3.push(6); + d3.push_back(6); // [X, X, |6] assert_eq!(d3.pop_front(), Some(3)); // Pushing the lo past half way point to trigger // the 'B' scenario for growth // [9, X, |6] - d3.push(9); + d3.push_back(9); // [9, 12, |6] - d3.push(12); + d3.push_back(12); - d3.push(15); + d3.push_back(15); // There used to be a bug here about how the // RingBuf made growth assumptions about the // underlying Vec which didn't hold and lead @@ -912,25 +1020,25 @@ mod tests { #[test] fn test_reserve_exact() { let mut d = RingBuf::new(); - d.push(0u64); + d.push_back(0u64); d.reserve_exact(50); - assert_eq!(d.elts.capacity(), 50); + assert!(d.capacity() >= 51); let mut d = RingBuf::new(); - d.push(0u32); + d.push_back(0u32); d.reserve_exact(50); - assert_eq!(d.elts.capacity(), 50); + assert!(d.capacity() >= 51); } #[test] fn test_reserve() { let mut d = RingBuf::new(); - d.push(0u64); + d.push_back(0u64); d.reserve(50); - assert_eq!(d.elts.capacity(), 64); + assert!(d.capacity() >= 64); let mut d = RingBuf::new(); - d.push(0u32); + d.push_back(0u32); d.reserve(50); - assert_eq!(d.elts.capacity(), 64); + assert!(d.capacity() >= 64); } #[test] @@ -948,7 +1056,7 @@ mod tests { assert_eq!(d.iter().size_hint(), (0, Some(0))); for i in range(0i, 5) { - d.push(i); + d.push_back(i); } { let b: &[_] = &[&0,&1,&2,&3,&4]; @@ -979,7 +1087,7 @@ mod tests { assert_eq!(d.iter().rev().next(), None); for i in range(0i, 5) { - d.push(i); + d.push_back(i); } { let b: &[_] = &[&4,&3,&2,&1,&0]; @@ -998,11 +1106,11 @@ mod tests { let mut d = RingBuf::with_capacity(3); assert!(d.iter_mut().rev().next().is_none()); - d.push(1i); - d.push(2); - d.push(3); + d.push_back(1i); + d.push_back(2); + d.push_back(3); assert_eq!(d.pop_front(), Some(1)); - d.push(4); + d.push_back(4); assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<int>>(), vec!(4, 3, 2)); @@ -1075,13 +1183,13 @@ mod tests { let mut d = RingBuf::new(); d.push_front(17i); d.push_front(42); - d.push(137); - d.push(137); + d.push_back(137); + d.push_back(137); assert_eq!(d.len(), 4u); let mut e = d.clone(); assert_eq!(e.len(), 4u); while !d.is_empty() { - assert_eq!(d.pop(), e.pop()); + assert_eq!(d.pop_back(), e.pop_back()); } assert_eq!(d.len(), 0u); assert_eq!(e.len(), 0u); @@ -1094,15 +1202,15 @@ mod tests { d.push_front(137i); d.push_front(17); d.push_front(42); - d.push(137); + d.push_back(137); let mut e = RingBuf::with_capacity(0); - e.push(42); - e.push(17); - e.push(137); - e.push(137); + e.push_back(42); + e.push_back(17); + e.push_back(137); + e.push_back(137); assert!(&e == &d); - e.pop(); - e.push(0); + e.pop_back(); + e.push_back(0); assert!(e != d); e.clear(); assert!(e == RingBuf::new()); @@ -1113,15 +1221,15 @@ mod tests { let mut x = RingBuf::new(); let mut y = RingBuf::new(); - x.push(1i); - x.push(2); - x.push(3); + x.push_back(1i); + x.push_back(2); + x.push_back(3); - y.push(0i); - y.push(1i); + y.push_back(0i); + y.push_back(1i); y.pop_front(); - y.push(2); - y.push(3); + y.push_back(2); + y.push_back(3); assert!(hash::hash(&x) == hash::hash(&y)); } @@ -1130,9 +1238,9 @@ mod tests { fn test_ord() { let x = RingBuf::new(); let mut y = RingBuf::new(); - y.push(1i); - y.push(2); - y.push(3); + y.push_back(1i); + y.push_back(2); + y.push_back(3); assert!(x < y); assert!(y > x); assert!(x <= x); diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs index e4af5795e1c..13703d6fe95 100644 --- a/src/libcollections/slice.rs +++ b/src/libcollections/slice.rs @@ -1523,10 +1523,10 @@ mod tests { fn test_capacity() { let mut v = vec![0u64]; v.reserve_exact(10u); - assert_eq!(v.capacity(), 10u); + assert!(v.capacity() >= 11u); let mut v = vec![0u32]; v.reserve_exact(10u); - assert_eq!(v.capacity(), 10u); + assert!(v.capacity() >= 11u); } #[test] @@ -2318,7 +2318,7 @@ mod bench { v.set_len(1024); } for i in range(0u, 1024) { - *v.get_mut(i) = 0; + v[i] = 0; } }); } diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs index cdca0d10eed..bed14e933bf 100644 --- a/src/libcollections/str.rs +++ b/src/libcollections/str.rs @@ -76,6 +76,8 @@ pub use core::str::{truncate_utf16_at_nul, utf8_char_width, CharRange}; pub use core::str::{Str, StrSlice}; pub use unicode::str::{UnicodeStrSlice, Words, Graphemes, GraphemeIndices}; +// FIXME(conventions): ensure bit/char conventions are followed by str's API + /* Section: Creating a string */ @@ -308,7 +310,7 @@ impl<'a> Iterator<char> for Recompositions<'a> { self.composee = Some(ch); return Some(k); } - self.buffer.push(ch); + self.buffer.push_back(ch); self.last_ccc = Some(ch_class); } } @@ -322,7 +324,7 @@ impl<'a> Iterator<char> for Recompositions<'a> { self.state = Purging; return Some(k); } - self.buffer.push(ch); + self.buffer.push_back(ch); self.last_ccc = Some(ch_class); continue; } @@ -332,7 +334,7 @@ impl<'a> Iterator<char> for Recompositions<'a> { continue; } None => { - self.buffer.push(ch); + self.buffer.push_back(ch); self.last_ccc = Some(ch_class); } } diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs index b3c83ba5559..ff9bd039a7d 100644 --- a/src/libcollections/string.rs +++ b/src/libcollections/string.rs @@ -330,8 +330,8 @@ impl String { let mut buf = String::new(); buf.push(ch); - let size = buf.len() * length; - buf.reserve(size); + let size = buf.len() * (length - 1); + buf.reserve_exact(size); for _ in range(1, length) { buf.push(ch) } @@ -379,27 +379,23 @@ impl String { /// assert!(s.capacity() >= 10); /// ``` #[inline] - #[unstable = "just implemented, needs to prove itself"] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn capacity(&self) -> uint { self.vec.capacity() } - /// Reserves capacity for at least `extra` additional bytes in this string buffer. - /// - /// # Example - /// - /// ``` - /// let mut s = String::with_capacity(10); - /// let before = s.capacity(); - /// s.reserve_additional(100); - /// assert!(s.capacity() - before >= 100); - /// ``` - #[inline] + /// Deprecated: Renamed to `reserve`. + #[deprecated = "Renamed to `reserve`"] pub fn reserve_additional(&mut self, extra: uint) { - self.vec.reserve_additional(extra) + self.vec.reserve(extra) } - /// Reserves capacity for at least `capacity` bytes in this string buffer. + /// Reserves capacity for at least `additional` more bytes to be inserted in the given + /// `String`. The collection may reserve more space to avoid frequent reallocations. + /// + /// # Panics + /// + /// Panics if the new capacity overflows `uint`. /// /// # Example /// @@ -409,22 +405,33 @@ impl String { /// assert!(s.capacity() >= 10); /// ``` #[inline] - pub fn reserve(&mut self, capacity: uint) { - self.vec.reserve(capacity) + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn reserve(&mut self, additional: uint) { + self.vec.reserve(additional) } - /// Reserves capacity for exactly `capacity` bytes in this string buffer. + /// Reserves the minimum capacity for exactly `additional` more bytes to be inserted in the + /// given `String`. Does nothing if the capacity is already sufficient. + /// + /// Note that the allocator may give the collection more space than it requests. Therefore + /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future + /// insertions are expected. + /// + /// # Panics + /// + /// Panics if the new capacity overflows `uint`. /// /// # Example /// /// ``` /// let mut s = String::new(); - /// s.reserve_exact(10); - /// assert_eq!(s.capacity(), 10); + /// s.reserve(10); + /// assert!(s.capacity() >= 10); /// ``` #[inline] - pub fn reserve_exact(&mut self, capacity: uint) { - self.vec.reserve_exact(capacity) + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn reserve_exact(&mut self, additional: uint) { + self.vec.reserve_exact(additional) } /// Shrinks the capacity of this string buffer to match its length. @@ -439,6 +446,7 @@ impl String { /// assert_eq!(s.capacity(), 3); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn shrink_to_fit(&mut self) { self.vec.shrink_to_fit() } @@ -459,7 +467,7 @@ impl String { pub fn push(&mut self, ch: char) { let cur_len = self.len(); // This may use up to 4 bytes. - self.vec.reserve_additional(4); + self.vec.reserve(4); unsafe { // Attempt to not use an intermediate buffer by just pushing bytes @@ -590,7 +598,7 @@ impl String { let len = self.len(); assert!(idx <= len); assert!(self.as_slice().is_char_boundary(idx)); - self.vec.reserve_additional(4); + self.vec.reserve(4); let mut bits = [0, ..4]; let amt = ch.encode_utf8(bits).unwrap(); diff --git a/src/libcollections/tree/map.rs b/src/libcollections/tree/map.rs index 8e24eabfccf..ea1c37d036a 100644 --- a/src/libcollections/tree/map.rs +++ b/src/libcollections/tree/map.rs @@ -21,6 +21,9 @@ use std::hash::{Writer, Hash}; use vec::Vec; +// FIXME(conventions): implement bounded iterators +// FIXME(conventions): replace rev_iter(_mut) by making iter(_mut) DoubleEnded + /// This is implemented as an AA tree, which is a simplified variation of /// a red-black tree where red (horizontal) nodes can only be added /// as a right child. The time complexity is the same, and re-balancing @@ -60,7 +63,7 @@ use vec::Vec; /// } /// /// for key in range(0, 4) { -/// match map.find(&key) { +/// match map.get(&key) { /// Some(val) => println!("{} has a value: {}", key, val), /// None => println!("{} not in map", key), /// } @@ -188,14 +191,14 @@ impl<K: Ord, V> Default for TreeMap<K,V> { impl<K: Ord, V> Index<K, V> for TreeMap<K, V> { #[inline] fn index<'a>(&'a self, i: &K) -> &'a V { - self.find(i).expect("no entry found for key") + self.get(i).expect("no entry found for key") } } impl<K: Ord, V> IndexMut<K, V> for TreeMap<K, V> { #[inline] fn index_mut<'a>(&'a mut self, i: &K) -> &'a mut V { - self.find_mut(i).expect("no entry found for key") + self.get_mut(i).expect("no entry found for key") } } @@ -208,6 +211,7 @@ impl<K: Ord, V> TreeMap<K, V> { /// use std::collections::TreeMap; /// let mut map: TreeMap<&str, int> = TreeMap::new(); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} } /// Gets a lazy iterator over the keys in the map, in ascending order. @@ -226,6 +230,7 @@ impl<K: Ord, V> TreeMap<K, V> { /// println!("{}", x); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn keys<'a>(&'a self) -> Keys<'a, K, V> { self.iter().map(|(k, _v)| k) } @@ -247,6 +252,7 @@ impl<K: Ord, V> TreeMap<K, V> { /// println!("{}", x); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn values<'a>(&'a self) -> Values<'a, K, V> { self.iter().map(|(_k, v)| v) } @@ -267,6 +273,7 @@ impl<K: Ord, V> TreeMap<K, V> { /// println!("{}: {}", key, value); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter<'a>(&'a self) -> Entries<'a, K, V> { Entries { stack: vec!(), @@ -314,10 +321,11 @@ impl<K: Ord, V> TreeMap<K, V> { /// if key == &"b" { break } /// } /// - /// assert_eq!(map.find(&"a"), Some(&11)); - /// assert_eq!(map.find(&"b"), Some(&12)); - /// assert_eq!(map.find(&"c"), Some(&3)); + /// assert_eq!(map.get(&"a"), Some(&11)); + /// assert_eq!(map.get(&"b"), Some(&12)); + /// assert_eq!(map.get(&"c"), Some(&3)); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter_mut<'a>(&'a mut self) -> MutEntries<'a, K, V> { MutEntries { stack: vec!(), @@ -345,15 +353,15 @@ impl<K: Ord, V> TreeMap<K, V> { /// if key == &"b" { break } /// } /// - /// assert_eq!(map.find(&"a"), Some(&1)); - /// assert_eq!(map.find(&"b"), Some(&12)); - /// assert_eq!(map.find(&"c"), Some(&13)); + /// assert_eq!(map.get(&"a"), Some(&1)); + /// assert_eq!(map.get(&"b"), Some(&12)); + /// assert_eq!(map.get(&"c"), Some(&13)); /// ``` pub fn rev_iter_mut<'a>(&'a mut self) -> RevMutEntries<'a, K, V> { RevMutEntries{iter: self.iter_mut()} } - /// Gets a lazy iterator that consumes the TreeMap. + /// Gets a lazy iterator that consumes the treemap. /// /// # Example /// @@ -368,6 +376,7 @@ impl<K: Ord, V> TreeMap<K, V> { /// let vec: Vec<(&str, int)> = map.into_iter().collect(); /// assert_eq!(vec, vec![("a", 1), ("b", 2), ("c", 3)]); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn into_iter(self) -> MoveEntries<K, V> { let TreeMap { root, length } = self; let stk = match root { @@ -392,6 +401,7 @@ impl<K: Ord, V> TreeMap<K, V> { /// a.insert(1u, "a"); /// assert_eq!(a.len(), 1); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.length } /// Return true if the map contains no elements. @@ -406,6 +416,7 @@ impl<K: Ord, V> TreeMap<K, V> { /// a.insert(1u, "a"); /// assert!(!a.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] #[inline] pub fn is_empty(&self) -> bool { self.len() == 0 } @@ -421,11 +432,18 @@ impl<K: Ord, V> TreeMap<K, V> { /// a.clear(); /// assert!(a.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { self.root = None; self.length = 0 } + /// Deprecated: Renamed to `get`. + #[deprecated = "Renamed to `get`"] + pub fn find(&self, key: &K) -> Option<&V> { + self.get(key) + } + /// Returns a reference to the value corresponding to the key. /// /// # Example @@ -435,11 +453,12 @@ impl<K: Ord, V> TreeMap<K, V> { /// /// let mut map = TreeMap::new(); /// map.insert(1u, "a"); - /// assert_eq!(map.find(&1), Some(&"a")); - /// assert_eq!(map.find(&2), None); + /// assert_eq!(map.get(&1), Some(&"a")); + /// assert_eq!(map.get(&2), None); /// ``` #[inline] - pub fn find<'a>(&'a self, key: &K) -> Option<&'a V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get(&self, key: &K) -> Option<&V> { tree_find_with(&self.root, |k2| key.cmp(k2)) } @@ -456,8 +475,15 @@ impl<K: Ord, V> TreeMap<K, V> { /// assert_eq!(map.contains_key(&2), false); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn contains_key(&self, key: &K) -> bool { - self.find(key).is_some() + self.get(key).is_some() + } + + /// Deprecated: Renamed to `get_mut`. + #[deprecated = "Renamed to `get_mut`"] + pub fn find_mut(&mut self, key: &K) -> Option<&mut V> { + self.get_mut(key) } /// Returns a mutable reference to the value corresponding to the key. @@ -469,52 +495,22 @@ impl<K: Ord, V> TreeMap<K, V> { /// /// let mut map = TreeMap::new(); /// map.insert(1u, "a"); - /// match map.find_mut(&1) { + /// match map.get_mut(&1) { /// Some(x) => *x = "b", /// None => (), /// } /// assert_eq!(map[1], "b"); /// ``` #[inline] - pub fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get_mut(&mut self, key: &K) -> Option<&mut V> { tree_find_with_mut(&mut self.root, |x| key.cmp(x)) } - /// Inserts a key-value pair into the map. An existing value for a - /// key is replaced by the new value. Returns `true` if the key did - /// not already exist in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::TreeMap; - /// - /// let mut map = TreeMap::new(); - /// assert_eq!(map.insert(2u, "value"), true); - /// assert_eq!(map.insert(2, "value2"), false); - /// assert_eq!(map[2], "value2"); - /// ``` - #[inline] - pub fn insert(&mut self, key: K, value: V) -> bool { - self.swap(key, value).is_none() - } - - /// Removes a key-value pair from the map. Returns `true` if the key - /// was present in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::TreeMap; - /// - /// let mut map = TreeMap::new(); - /// assert_eq!(map.remove(&1u), false); - /// map.insert(1, "a"); - /// assert_eq!(map.remove(&1), true); - /// ``` - #[inline] - pub fn remove(&mut self, key: &K) -> bool { - self.pop(key).is_some() + /// Deprecated: Renamed to `insert`. + #[deprecated = "Renamed to `insert`"] + pub fn swap(&mut self, key: K, value: V) -> Option<V> { + self.insert(key, value) } /// Inserts a key-value pair from the map. If the key already had a value @@ -526,19 +522,26 @@ impl<K: Ord, V> TreeMap<K, V> { /// use std::collections::TreeMap; /// /// let mut map = TreeMap::new(); - /// assert_eq!(map.swap(37u, "a"), None); + /// assert_eq!(map.insert(37u, "a"), None); /// assert_eq!(map.is_empty(), false); /// /// map.insert(37, "b"); - /// assert_eq!(map.swap(37, "c"), Some("b")); + /// assert_eq!(map.insert(37, "c"), Some("b")); /// assert_eq!(map[37], "c"); /// ``` - pub fn swap(&mut self, key: K, value: V) -> Option<V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn insert(&mut self, key: K, value: V) -> Option<V> { let ret = insert(&mut self.root, key, value); if ret.is_none() { self.length += 1 } ret } + /// Deprecated: Renamed to `remove`. + #[deprecated = "Renamed to `remove`"] + pub fn pop(&mut self, key: &K) -> Option<V> { + self.remove(key) + } + /// Removes a key from the map, returning the value at the key if the key /// was previously in the map. /// @@ -549,10 +552,11 @@ impl<K: Ord, V> TreeMap<K, V> { /// /// let mut map = TreeMap::new(); /// map.insert(1u, "a"); - /// assert_eq!(map.pop(&1), Some("a")); - /// assert_eq!(map.pop(&1), None); + /// assert_eq!(map.remove(&1), Some("a")); + /// assert_eq!(map.remove(&1), None); /// ``` - pub fn pop(&mut self, key: &K) -> Option<V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn remove(&mut self, key: &K) -> Option<V> { let ret = remove(&mut self.root, key); if ret.is_some() { self.length -= 1 } ret @@ -567,7 +571,7 @@ impl<K, V> TreeMap<K, V> { /// # Example /// /// ``` - /// use std::collections::TreeMap; + /// use collections::tree_map::TreeMap; /// /// fn get_headers() -> TreeMap<String, String> { /// let mut result = TreeMap::new(); @@ -585,7 +589,7 @@ impl<K, V> TreeMap<K, V> { /// assert_eq!((*ua.unwrap()).as_slice(), "Curl-Rust/0.1"); /// ``` #[inline] - pub fn find_with<'a>(&'a self, f:|&K| -> Ordering) -> Option<&'a V> { + pub fn find_with(&self, f:|&K| -> Ordering) -> Option<&V> { tree_find_with(&self.root, f) } @@ -596,9 +600,7 @@ impl<K, V> TreeMap<K, V> { /// # Example /// /// ``` - /// use std::collections::TreeMap; - /// - /// let mut t = TreeMap::new(); + /// let mut t = collections::tree_map::TreeMap::new(); /// t.insert("Content-Type", "application/xml"); /// t.insert("User-Agent", "Curl-Rust/0.1"); /// @@ -608,7 +610,7 @@ impl<K, V> TreeMap<K, V> { /// None => panic!(), /// } /// - /// assert_eq!(t.find(&"User-Agent"), Some(&new_ua)); + /// assert_eq!(t.get(&"User-Agent"), Some(&new_ua)); /// ``` #[inline] pub fn find_with_mut<'a>(&'a mut self, f:|&K| -> Ordering) -> Option<&'a mut V> { @@ -742,10 +744,10 @@ impl<K: Ord, V> TreeMap<K, V> { /// *value = "changed"; /// } /// - /// assert_eq!(map.find(&2), Some(&"a")); - /// assert_eq!(map.find(&4), Some(&"changed")); - /// assert_eq!(map.find(&6), Some(&"changed")); - /// assert_eq!(map.find(&8), Some(&"changed")); + /// assert_eq!(map.get(&2), Some(&"a")); + /// assert_eq!(map.get(&4), Some(&"changed")); + /// assert_eq!(map.get(&6), Some(&"changed")); + /// assert_eq!(map.get(&8), Some(&"changed")); /// ``` pub fn lower_bound_mut<'a>(&'a mut self, k: &K) -> MutEntries<'a, K, V> { bound_setup!(self.iter_mut_for_traversal(), k, true) @@ -776,10 +778,10 @@ impl<K: Ord, V> TreeMap<K, V> { /// *value = "changed"; /// } /// - /// assert_eq!(map.find(&2), Some(&"a")); - /// assert_eq!(map.find(&4), Some(&"b")); - /// assert_eq!(map.find(&6), Some(&"changed")); - /// assert_eq!(map.find(&8), Some(&"changed")); + /// assert_eq!(map.get(&2), Some(&"a")); + /// assert_eq!(map.get(&4), Some(&"b")); + /// assert_eq!(map.get(&6), Some(&"changed")); + /// assert_eq!(map.get(&8), Some(&"changed")); /// ``` pub fn upper_bound_mut<'a>(&'a mut self, k: &K) -> MutEntries<'a, K, V> { bound_setup!(self.iter_mut_for_traversal(), k, false) @@ -1287,16 +1289,16 @@ mod test_treemap { #[test] fn find_empty() { let m: TreeMap<int,int> = TreeMap::new(); - assert!(m.find(&5) == None); + assert!(m.get(&5) == None); } #[test] fn find_not_found() { let mut m = TreeMap::new(); - assert!(m.insert(1i, 2i)); - assert!(m.insert(5i, 3i)); - assert!(m.insert(9i, 3i)); - assert_eq!(m.find(&2), None); + assert!(m.insert(1i, 2i).is_none()); + assert!(m.insert(5i, 3i).is_none()); + assert!(m.insert(9i, 3i).is_none()); + assert_eq!(m.get(&2), None); } #[test] @@ -1308,41 +1310,42 @@ mod test_treemap { #[test] fn find_with_not_found() { let mut m = TreeMap::new(); - assert!(m.insert("test1", 2i)); - assert!(m.insert("test2", 3i)); - assert!(m.insert("test3", 3i)); + assert!(m.insert("test1", 2i).is_none()); + assert!(m.insert("test2", 3i).is_none()); + assert!(m.insert("test3", 3i).is_none()); assert_eq!(m.find_with(|&k| "test4".cmp(k)), None); } #[test] fn find_with_found() { let mut m = TreeMap::new(); - assert!(m.insert("test1", 2i)); - assert!(m.insert("test2", 3i)); - assert!(m.insert("test3", 4i)); + assert!(m.insert("test1", 2i).is_none()); + assert!(m.insert("test2", 3i).is_none()); + assert!(m.insert("test3", 4i).is_none()); assert_eq!(m.find_with(|&k| "test2".cmp(k)), Some(&3i)); } #[test] fn test_find_mut() { let mut m = TreeMap::new(); - assert!(m.insert(1i, 12i)); - assert!(m.insert(2, 8)); - assert!(m.insert(5, 14)); + assert!(m.insert(1i, 12i).is_none()); + assert!(m.insert(2, 8).is_none()); + assert!(m.insert(5, 14).is_none()); let new = 100; - match m.find_mut(&5) { + match m.get_mut(&5) { None => panic!(), Some(x) => *x = new } - assert_eq!(m.find(&5), Some(&new)); + assert_eq!(m.get(&5), Some(&new)); } #[test] fn test_find_with_mut() { let mut m = TreeMap::new(); - assert!(m.insert("t1", 12i)); - assert!(m.insert("t2", 8)); - assert!(m.insert("t5", 14)); + assert!(m.insert("t1", 12i).is_none()); + assert!(m.insert("t2", 8).is_none()); + assert!(m.insert("t5", 14).is_none()); let new = 100; + match m.find_with_mut(|&k| "t5".cmp(k)) { None => panic!(), Some(x) => *x = new } @@ -1352,23 +1355,23 @@ mod test_treemap { #[test] fn insert_replace() { let mut m = TreeMap::new(); - assert!(m.insert(5i, 2i)); - assert!(m.insert(2, 9)); - assert!(!m.insert(2, 11)); - assert_eq!(m.find(&2).unwrap(), &11); + assert!(m.insert(5i, 2i).is_none()); + assert!(m.insert(2, 9).is_none()); + assert!(!m.insert(2, 11).is_none()); + assert_eq!(m.get(&2).unwrap(), &11); } #[test] fn test_clear() { let mut m = TreeMap::new(); m.clear(); - assert!(m.insert(5i, 11i)); - assert!(m.insert(12, -3)); - assert!(m.insert(19, 2)); + assert!(m.insert(5i, 11i).is_none()); + assert!(m.insert(12, -3).is_none()); + assert!(m.insert(19, 2).is_none()); m.clear(); - assert!(m.find(&5).is_none()); - assert!(m.find(&12).is_none()); - assert!(m.find(&19).is_none()); + assert!(m.get(&5).is_none()); + assert!(m.get(&12).is_none()); + assert!(m.get(&19).is_none()); assert!(m.is_empty()); } @@ -1384,8 +1387,8 @@ mod test_treemap { m.insert(k1.clone(), v1.clone()); m.insert(k2.clone(), v2.clone()); - assert_eq!(m.find(&k2), Some(&v2)); - assert_eq!(m.find(&k1), Some(&v1)); + assert_eq!(m.get(&k2), Some(&v2)); + assert_eq!(m.get(&k1), Some(&v1)); } fn check_equal<K: PartialEq + Ord, V: PartialEq>(ctrl: &[(K, V)], @@ -1393,7 +1396,7 @@ mod test_treemap { assert_eq!(ctrl.is_empty(), map.is_empty()); for x in ctrl.iter() { let &(ref k, ref v) = x; - assert!(map.find(k).unwrap() == v) + assert!(map.get(k).unwrap() == v) } for (map_k, map_v) in map.iter() { let mut found = false; @@ -1455,7 +1458,7 @@ mod test_treemap { let mut ctrl = vec![]; check_equal(ctrl.as_slice(), &map); - assert!(map.find(&5).is_none()); + assert!(map.get(&5).is_none()); let seed: &[_] = &[42]; let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed); @@ -1465,7 +1468,7 @@ mod test_treemap { let k = rng.gen(); let v = rng.gen(); if !ctrl.iter().any(|x| x == &(k, v)) { - assert!(map.insert(k, v)); + assert!(map.insert(k, v).is_none()); ctrl.push((k, v)); check_structure(&map); check_equal(ctrl.as_slice(), &map); @@ -1475,7 +1478,7 @@ mod test_treemap { for _ in range(0u, 30) { let r = rng.gen_range(0, ctrl.len()); let (key, _) = ctrl.remove(r).unwrap(); - assert!(map.remove(&key)); + assert!(map.remove(&key).is_some()); check_structure(&map); check_equal(ctrl.as_slice(), &map); } @@ -1485,19 +1488,19 @@ mod test_treemap { #[test] fn test_len() { let mut m = TreeMap::new(); - assert!(m.insert(3i, 6i)); + assert!(m.insert(3i, 6i).is_none()); assert_eq!(m.len(), 1); - assert!(m.insert(0, 0)); + assert!(m.insert(0, 0).is_none()); assert_eq!(m.len(), 2); - assert!(m.insert(4, 8)); + assert!(m.insert(4, 8).is_none()); assert_eq!(m.len(), 3); - assert!(m.remove(&3)); + assert!(m.remove(&3).is_some()); assert_eq!(m.len(), 2); - assert!(!m.remove(&5)); + assert!(!m.remove(&5).is_some()); assert_eq!(m.len(), 2); - assert!(m.insert(2, 4)); + assert!(m.insert(2, 4).is_none()); assert_eq!(m.len(), 3); - assert!(m.insert(1, 2)); + assert!(m.insert(1, 2).is_none()); assert_eq!(m.len(), 4); } @@ -1505,11 +1508,11 @@ mod test_treemap { fn test_iterator() { let mut m = TreeMap::new(); - assert!(m.insert(3i, 6i)); - assert!(m.insert(0, 0)); - assert!(m.insert(4, 8)); - assert!(m.insert(2, 4)); - assert!(m.insert(1, 2)); + assert!(m.insert(3i, 6i).is_none()); + assert!(m.insert(0, 0).is_none()); + assert!(m.insert(4, 8).is_none()); + assert!(m.insert(2, 4).is_none()); + assert!(m.insert(1, 2).is_none()); let mut n = 0; for (k, v) in m.iter() { @@ -1524,7 +1527,7 @@ mod test_treemap { fn test_interval_iteration() { let mut m = TreeMap::new(); for i in range(1i, 100i) { - assert!(m.insert(i * 2, i * 4)); + assert!(m.insert(i * 2, i * 4).is_none()); } for i in range(1i, 198i) { @@ -1548,11 +1551,11 @@ mod test_treemap { fn test_rev_iter() { let mut m = TreeMap::new(); - assert!(m.insert(3i, 6i)); - assert!(m.insert(0, 0)); - assert!(m.insert(4, 8)); - assert!(m.insert(2, 4)); - assert!(m.insert(1, 2)); + assert!(m.insert(3i, 6i).is_none()); + assert!(m.insert(0, 0).is_none()); + assert!(m.insert(4, 8).is_none()); + assert!(m.insert(2, 4).is_none()); + assert!(m.insert(1, 2).is_none()); let mut n = 4; for (k, v) in m.rev_iter() { @@ -1566,7 +1569,7 @@ mod test_treemap { fn test_mut_iter() { let mut m = TreeMap::new(); for i in range(0u, 10) { - assert!(m.insert(i, 100 * i)); + assert!(m.insert(i, 100 * i).is_none()); } for (i, (&k, v)) in m.iter_mut().enumerate() { @@ -1581,7 +1584,7 @@ mod test_treemap { fn test_mut_rev_iter() { let mut m = TreeMap::new(); for i in range(0u, 10) { - assert!(m.insert(i, 100 * i)); + assert!(m.insert(i, 100 * i).is_none()); } for (i, (&k, v)) in m.rev_iter_mut().enumerate() { @@ -1598,8 +1601,8 @@ mod test_treemap { let mut m_lower = TreeMap::new(); let mut m_upper = TreeMap::new(); for i in range(1i, 100i) { - assert!(m_lower.insert(i * 2, i * 4)); - assert!(m_upper.insert(i * 2, i * 4)); + assert!(m_lower.insert(i * 2, i * 4).is_none()); + assert!(m_upper.insert(i * 2, i * 4).is_none()); } for i in range(1i, 199) { @@ -1653,15 +1656,15 @@ mod test_treemap { let mut b = TreeMap::new(); assert!(a == b); - assert!(a.insert(0i, 5i)); + assert!(a.insert(0i, 5i).is_none()); assert!(a != b); - assert!(b.insert(0, 4)); + assert!(b.insert(0, 4).is_none()); assert!(a != b); - assert!(a.insert(5, 19)); + assert!(a.insert(5, 19).is_none()); assert!(a != b); - assert!(!b.insert(0, 5)); + assert!(!b.insert(0, 5).is_none()); assert!(a != b); - assert!(b.insert(5, 19)); + assert!(b.insert(5, 19).is_none()); assert!(a == b); } @@ -1671,15 +1674,15 @@ mod test_treemap { let mut b = TreeMap::new(); assert!(!(a < b) && !(b < a)); - assert!(b.insert(0i, 5i)); + assert!(b.insert(0i, 5i).is_none()); assert!(a < b); - assert!(a.insert(0, 7)); + assert!(a.insert(0, 7).is_none()); assert!(!(a < b) && b < a); - assert!(b.insert(-2, 0)); + assert!(b.insert(-2, 0).is_none()); assert!(b < a); - assert!(a.insert(-5, 2)); + assert!(a.insert(-5, 2).is_none()); assert!(a < b); - assert!(a.insert(6, 2)); + assert!(a.insert(6, 2).is_none()); assert!(a < b && !(b < a)); } @@ -1689,10 +1692,10 @@ mod test_treemap { let mut b = TreeMap::new(); assert!(a <= b && a >= b); - assert!(a.insert(1i, 1i)); + assert!(a.insert(1i, 1i).is_none()); assert!(a > b && a >= b); assert!(b < a && b <= a); - assert!(b.insert(2, 2)); + assert!(b.insert(2, 2).is_none()); assert!(b > a && b >= a); assert!(a < b && a <= b); } @@ -1720,11 +1723,11 @@ mod test_treemap { let (x4, y4) = (29, 5); let (x5, y5) = (103, 3); - assert!(m.insert(x1, y1)); - assert!(m.insert(x2, y2)); - assert!(m.insert(x3, y3)); - assert!(m.insert(x4, y4)); - assert!(m.insert(x5, y5)); + assert!(m.insert(x1, y1).is_none()); + assert!(m.insert(x2, y2).is_none()); + assert!(m.insert(x3, y3).is_none()); + assert!(m.insert(x4, y4).is_none()); + assert!(m.insert(x5, y5).is_none()); let m = m; let mut a = m.iter(); @@ -1765,7 +1768,7 @@ mod test_treemap { let map: TreeMap<int, int> = xs.iter().map(|&x| x).collect(); for &(k, v) in xs.iter() { - assert_eq!(map.find(&k), Some(&v)); + assert_eq!(map.get(&k), Some(&v)); } } @@ -1795,17 +1798,17 @@ mod test_treemap { #[test] fn test_swap() { let mut m = TreeMap::new(); - assert_eq!(m.swap(1u, 2i), None); - assert_eq!(m.swap(1u, 3i), Some(2)); - assert_eq!(m.swap(1u, 4i), Some(3)); + assert_eq!(m.insert(1u, 2i), None); + assert_eq!(m.insert(1u, 3i), Some(2)); + assert_eq!(m.insert(1u, 4i), Some(3)); } #[test] fn test_pop() { let mut m = TreeMap::new(); m.insert(1u, 2i); - assert_eq!(m.pop(&1), Some(2)); - assert_eq!(m.pop(&1), None); + assert_eq!(m.remove(&1), Some(2)); + assert_eq!(m.remove(&1), None); } } @@ -1857,7 +1860,7 @@ mod bench { let mut m : TreeMap<uint,uint> = TreeMap::new(); find_rand_n(100, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } #[bench] @@ -1865,7 +1868,7 @@ mod bench { let mut m : TreeMap<uint,uint> = TreeMap::new(); find_rand_n(10_000, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } // Find seq @@ -1874,7 +1877,7 @@ mod bench { let mut m : TreeMap<uint,uint> = TreeMap::new(); find_seq_n(100, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } #[bench] @@ -1882,7 +1885,7 @@ mod bench { let mut m : TreeMap<uint,uint> = TreeMap::new(); find_seq_n(10_000, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } fn bench_iter(b: &mut Bencher, size: uint) { @@ -1890,7 +1893,7 @@ mod bench { let mut rng = weak_rng(); for _ in range(0, size) { - map.swap(rng.gen(), rng.gen()); + map.insert(rng.gen(), rng.gen()); } b.iter(|| { diff --git a/src/libcollections/tree/set.rs b/src/libcollections/tree/set.rs index d24a8234b20..22307a5d376 100644 --- a/src/libcollections/tree/set.rs +++ b/src/libcollections/tree/set.rs @@ -19,6 +19,10 @@ use std::hash::{Writer, Hash}; use tree_map::{TreeMap, Entries, RevEntries, MoveEntries}; +// FIXME(conventions): implement bounded iterators +// FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub +// FIXME(conventions): replace rev_iter(_mut) by making iter(_mut) DoubleEnded + /// An implementation of the `Set` trait on top of the `TreeMap` container. The /// only requirement is that the type of the elements contained ascribes to the /// `Ord` trait. @@ -145,6 +149,7 @@ impl<T: Ord> TreeSet<T> { /// let mut set: TreeSet<int> = TreeSet::new(); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> TreeSet<T> { TreeSet{map: TreeMap::new()} } /// Gets a lazy iterator over the values in the set, in ascending order. @@ -161,6 +166,7 @@ impl<T: Ord> TreeSet<T> { /// } /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter<'a>(&'a self) -> SetItems<'a, T> { SetItems{iter: self.map.iter()} } @@ -197,6 +203,7 @@ impl<T: Ord> TreeSet<T> { /// assert_eq!(v, vec![1, 2, 3, 4, 5]); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn into_iter(self) -> MoveSetItems<T> { self.map.into_iter().map(|(value, _)| value) } @@ -261,6 +268,7 @@ impl<T: Ord> TreeSet<T> { /// let diff: TreeSet<int> = b.difference(&a).map(|&x| x).collect(); /// assert_eq!(diff, [4, 5].iter().map(|&x| x).collect()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn difference<'a>(&'a self, other: &'a TreeSet<T>) -> DifferenceItems<'a, T> { DifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()} } @@ -286,6 +294,7 @@ impl<T: Ord> TreeSet<T> { /// assert_eq!(diff1, diff2); /// assert_eq!(diff1, [1, 2, 4, 5].iter().map(|&x| x).collect()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn symmetric_difference<'a>(&'a self, other: &'a TreeSet<T>) -> SymDifferenceItems<'a, T> { SymDifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()} @@ -309,6 +318,7 @@ impl<T: Ord> TreeSet<T> { /// let diff: TreeSet<int> = a.intersection(&b).map(|&x| x).collect(); /// assert_eq!(diff, [2, 3].iter().map(|&x| x).collect()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn intersection<'a>(&'a self, other: &'a TreeSet<T>) -> IntersectionItems<'a, T> { IntersectionItems{a: self.iter().peekable(), b: other.iter().peekable()} @@ -332,6 +342,7 @@ impl<T: Ord> TreeSet<T> { /// let diff: TreeSet<int> = a.union(&b).map(|&x| x).collect(); /// assert_eq!(diff, [1, 2, 3, 4, 5].iter().map(|&x| x).collect()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn union<'a>(&'a self, other: &'a TreeSet<T>) -> UnionItems<'a, T> { UnionItems{a: self.iter().peekable(), b: other.iter().peekable()} } @@ -349,6 +360,7 @@ impl<T: Ord> TreeSet<T> { /// assert_eq!(v.len(), 1); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.map.len() } /// Returns true if the set contains no elements @@ -363,6 +375,7 @@ impl<T: Ord> TreeSet<T> { /// v.insert(1i); /// assert!(!v.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.len() == 0 } /// Clears the set, removing all values. @@ -378,6 +391,7 @@ impl<T: Ord> TreeSet<T> { /// assert!(v.is_empty()); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { self.map.clear() } /// Returns `true` if the set contains a value. @@ -392,6 +406,7 @@ impl<T: Ord> TreeSet<T> { /// assert_eq!(set.contains(&4), false); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn contains(&self, value: &T) -> bool { self.map.contains_key(value) } @@ -413,6 +428,7 @@ impl<T: Ord> TreeSet<T> { /// b.insert(1); /// assert_eq!(a.is_disjoint(&b), false); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_disjoint(&self, other: &TreeSet<T>) -> bool { self.intersection(other).next().is_none() } @@ -433,6 +449,7 @@ impl<T: Ord> TreeSet<T> { /// set.insert(4); /// assert_eq!(set.is_subset(&sup), false); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_subset(&self, other: &TreeSet<T>) -> bool { let mut x = self.iter(); let mut y = other.iter(); @@ -476,6 +493,7 @@ impl<T: Ord> TreeSet<T> { /// set.insert(2); /// assert_eq!(set.is_superset(&sub), true); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_superset(&self, other: &TreeSet<T>) -> bool { other.is_subset(self) } @@ -495,7 +513,8 @@ impl<T: Ord> TreeSet<T> { /// assert_eq!(set.len(), 1); /// ``` #[inline] - pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) } + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() } /// Removes a value from the set. Returns `true` if the value was /// present in the set. @@ -512,7 +531,8 @@ impl<T: Ord> TreeSet<T> { /// assert_eq!(set.remove(&2), false); /// ``` #[inline] - pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value) } + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value).is_some() } } /// A lazy forward iterator over a set. diff --git a/src/libcollections/trie/map.rs b/src/libcollections/trie/map.rs index 27486de6f19..d604e176a67 100644 --- a/src/libcollections/trie/map.rs +++ b/src/libcollections/trie/map.rs @@ -32,6 +32,10 @@ use std::hash::{Writer, Hash}; use slice::{Items, MutItems}; use slice; +// FIXME(conventions): implement bounded iterators +// FIXME(conventions): implement into_iter +// FIXME(conventions): replace each_reverse by making iter DoubleEnded + // FIXME: #5244: need to manually update the TrieNode constructor const SHIFT: uint = 4; const SIZE: uint = 1 << SHIFT; @@ -59,14 +63,14 @@ enum Child<T> { /// map.insert(1, "Martin"); /// /// assert_eq!(map.len(), 3); -/// assert_eq!(map.find(&1), Some(&"Martin")); +/// assert_eq!(map.get(&1), Some(&"Martin")); /// /// if !map.contains_key(&90) { /// println!("Nobody is keyed 90"); /// } /// /// // Update a key -/// match map.find_mut(&1) { +/// match map.get_mut(&1) { /// Some(value) => *value = "Olga", /// None => (), /// } @@ -140,6 +144,7 @@ impl<T> TrieMap<T> { /// let mut map: TrieMap<&str> = TrieMap::new(); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> TrieMap<T> { TrieMap{root: TrieNode::new(), length: 0} } @@ -169,12 +174,14 @@ impl<T> TrieMap<T> { /// Gets an iterator visiting all keys in ascending order by the keys. /// The iterator's element type is `uint`. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn keys<'r>(&'r self) -> Keys<'r, T> { self.iter().map(|(k, _v)| k) } /// Gets an iterator visiting all values in ascending order by the keys. /// The iterator's element type is `&'r T`. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn values<'r>(&'r self) -> Values<'r, T> { self.iter().map(|(_k, v)| v) } @@ -191,6 +198,7 @@ impl<T> TrieMap<T> { /// println!("{}: {}", key, value); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter<'a>(&'a self) -> Entries<'a, T> { let mut iter = unsafe {Entries::new()}; iter.stack[0] = self.root.children.iter(); @@ -214,10 +222,11 @@ impl<T> TrieMap<T> { /// *value = -(key as int); /// } /// - /// assert_eq!(map.find(&1), Some(&-1)); - /// assert_eq!(map.find(&2), Some(&-2)); - /// assert_eq!(map.find(&3), Some(&-3)); + /// assert_eq!(map.get(&1), Some(&-1)); + /// assert_eq!(map.get(&2), Some(&-2)); + /// assert_eq!(map.get(&3), Some(&-3)); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter_mut<'a>(&'a mut self) -> MutEntries<'a, T> { let mut iter = unsafe {MutEntries::new()}; iter.stack[0] = self.root.children.iter_mut(); @@ -241,6 +250,7 @@ impl<T> TrieMap<T> { /// assert_eq!(a.len(), 1); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.length } /// Return true if the map contains no elements. @@ -256,6 +266,7 @@ impl<T> TrieMap<T> { /// assert!(!a.is_empty()); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.len() == 0 } /// Clears the map, removing all values. @@ -271,11 +282,18 @@ impl<T> TrieMap<T> { /// assert!(a.is_empty()); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { self.root = TrieNode::new(); self.length = 0; } + /// Deprecated: renamed to `get`. + #[deprecated = "renamed to `get`"] + pub fn find(&self, key: &uint) -> Option<&T> { + self.get(key) + } + /// Returns a reference to the value corresponding to the key. /// /// # Example @@ -285,12 +303,13 @@ impl<T> TrieMap<T> { /// /// let mut map = TrieMap::new(); /// map.insert(1, "a"); - /// assert_eq!(map.find(&1), Some(&"a")); - /// assert_eq!(map.find(&2), None); + /// assert_eq!(map.get(&1), Some(&"a")); + /// assert_eq!(map.get(&2), None); /// ``` #[inline] - pub fn find<'a>(&'a self, key: &uint) -> Option<&'a T> { - let mut node: &'a TrieNode<T> = &self.root; + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get(&self, key: &uint) -> Option<&T> { + let mut node = &self.root; let mut idx = 0; loop { match node.children[chunk(*key, idx)] { @@ -321,8 +340,15 @@ impl<T> TrieMap<T> { /// assert_eq!(map.contains_key(&2), false); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn contains_key(&self, key: &uint) -> bool { - self.find(key).is_some() + self.get(key).is_some() + } + + /// Deprecated: renamed to `get_mut`. + #[deprecated = "renamed to `get_mut`"] + pub fn find_mut(&mut self, key: &uint) -> Option<&mut T> { + self.get_mut(key) } /// Returns a mutable reference to the value corresponding to the key. @@ -334,52 +360,22 @@ impl<T> TrieMap<T> { /// /// let mut map = TrieMap::new(); /// map.insert(1, "a"); - /// match map.find_mut(&1) { + /// match map.get_mut(&1) { /// Some(x) => *x = "b", /// None => (), /// } /// assert_eq!(map[1], "b"); /// ``` #[inline] - pub fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> { find_mut(&mut self.root.children[chunk(*key, 0)], *key, 1) } - /// Inserts a key-value pair into the map. An existing value for a - /// key is replaced by the new value. Returns `true` if the key did - /// not already exist in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::TrieMap; - /// - /// let mut map = TrieMap::new(); - /// assert_eq!(map.insert(2, "value"), true); - /// assert_eq!(map.insert(2, "value2"), false); - /// assert_eq!(map[2], "value2"); - /// ``` - #[inline] - pub fn insert(&mut self, key: uint, value: T) -> bool { - self.swap(key, value).is_none() - } - - /// Removes a key-value pair from the map. Returns `true` if the key - /// was present in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::TrieMap; - /// - /// let mut map = TrieMap::new(); - /// assert_eq!(map.remove(&1), false); - /// map.insert(1, "a"); - /// assert_eq!(map.remove(&1), true); - /// ``` - #[inline] - pub fn remove(&mut self, key: &uint) -> bool { - self.pop(key).is_some() + /// Deprecated: Renamed to `insert`. + #[deprecated = "Renamed to `insert`"] + pub fn swap(&mut self, key: uint, value: T) -> Option<T> { + self.insert(key, value) } /// Inserts a key-value pair from the map. If the key already had a value @@ -391,14 +387,15 @@ impl<T> TrieMap<T> { /// use std::collections::TrieMap; /// /// let mut map = TrieMap::new(); - /// assert_eq!(map.swap(37, "a"), None); + /// assert_eq!(map.insert(37, "a"), None); /// assert_eq!(map.is_empty(), false); /// /// map.insert(37, "b"); - /// assert_eq!(map.swap(37, "c"), Some("b")); + /// assert_eq!(map.insert(37, "c"), Some("b")); /// assert_eq!(map[37], "c"); /// ``` - pub fn swap(&mut self, key: uint, value: T) -> Option<T> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn insert(&mut self, key: uint, value: T) -> Option<T> { let ret = insert(&mut self.root.count, &mut self.root.children[chunk(key, 0)], key, value, 1); @@ -406,6 +403,12 @@ impl<T> TrieMap<T> { ret } + /// Deprecated: Renamed to `remove`. + #[deprecated = "Renamed to `remove`"] + pub fn pop(&mut self, key: &uint) -> Option<T> { + self.remove(key) + } + /// Removes a key from the map, returning the value at the key if the key /// was previously in the map. /// @@ -416,10 +419,11 @@ impl<T> TrieMap<T> { /// /// let mut map = TrieMap::new(); /// map.insert(1, "a"); - /// assert_eq!(map.pop(&1), Some("a")); - /// assert_eq!(map.pop(&1), None); + /// assert_eq!(map.remove(&1), Some("a")); + /// assert_eq!(map.remove(&1), None); /// ``` - pub fn pop(&mut self, key: &uint) -> Option<T> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn remove(&mut self, key: &uint) -> Option<T> { let ret = remove(&mut self.root.count, &mut self.root.children[chunk(*key, 0)], *key, 1); @@ -582,9 +586,9 @@ impl<T> TrieMap<T> { /// *value = "changed"; /// } /// - /// assert_eq!(map.find(&2), Some(&"a")); - /// assert_eq!(map.find(&4), Some(&"changed")); - /// assert_eq!(map.find(&6), Some(&"changed")); + /// assert_eq!(map.get(&2), Some(&"a")); + /// assert_eq!(map.get(&4), Some(&"changed")); + /// assert_eq!(map.get(&6), Some(&"changed")); /// ``` pub fn lower_bound_mut<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> { self.bound_mut(key, false) @@ -607,9 +611,9 @@ impl<T> TrieMap<T> { /// *value = "changed"; /// } /// - /// assert_eq!(map.find(&2), Some(&"a")); - /// assert_eq!(map.find(&4), Some(&"b")); - /// assert_eq!(map.find(&6), Some(&"changed")); + /// assert_eq!(map.get(&2), Some(&"a")); + /// assert_eq!(map.get(&4), Some(&"b")); + /// assert_eq!(map.get(&6), Some(&"changed")); /// ``` pub fn upper_bound_mut<'a>(&'a mut self, key: uint) -> MutEntries<'a, T> { self.bound_mut(key, true) @@ -643,14 +647,14 @@ impl<S: Writer, T: Hash<S>> Hash<S> for TrieMap<T> { impl<T> Index<uint, T> for TrieMap<T> { #[inline] fn index<'a>(&'a self, i: &uint) -> &'a T { - self.find(i).expect("key not present") + self.get(i).expect("key not present") } } impl<T> IndexMut<uint, T> for TrieMap<T> { #[inline] fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut T { - self.find_mut(i).expect("key not present") + self.get_mut(i).expect("key not present") } } @@ -957,24 +961,24 @@ mod test { #[test] fn test_find_mut() { let mut m = TrieMap::new(); - assert!(m.insert(1u, 12i)); - assert!(m.insert(2u, 8i)); - assert!(m.insert(5u, 14i)); + assert!(m.insert(1u, 12i).is_none()); + assert!(m.insert(2u, 8i).is_none()); + assert!(m.insert(5u, 14i).is_none()); let new = 100; - match m.find_mut(&5) { + match m.get_mut(&5) { None => panic!(), Some(x) => *x = new } - assert_eq!(m.find(&5), Some(&new)); + assert_eq!(m.get(&5), Some(&new)); } #[test] fn test_find_mut_missing() { let mut m = TrieMap::new(); - assert!(m.find_mut(&0).is_none()); - assert!(m.insert(1u, 12i)); - assert!(m.find_mut(&0).is_none()); - assert!(m.insert(2, 8)); - assert!(m.find_mut(&0).is_none()); + assert!(m.get_mut(&0).is_none()); + assert!(m.insert(1u, 12i).is_none()); + assert!(m.get_mut(&0).is_none()); + assert!(m.insert(2, 8).is_none()); + assert!(m.get_mut(&0).is_none()); } #[test] @@ -983,32 +987,32 @@ mod test { let n = 300u; for x in range_step(1u, n, 2) { - assert!(trie.insert(x, x + 1)); + assert!(trie.insert(x, x + 1).is_none()); assert!(trie.contains_key(&x)); check_integrity(&trie.root); } for x in range_step(0u, n, 2) { assert!(!trie.contains_key(&x)); - assert!(trie.insert(x, x + 1)); + assert!(trie.insert(x, x + 1).is_none()); check_integrity(&trie.root); } for x in range(0u, n) { assert!(trie.contains_key(&x)); - assert!(!trie.insert(x, x + 1)); + assert!(!trie.insert(x, x + 1).is_none()); check_integrity(&trie.root); } for x in range_step(1u, n, 2) { - assert!(trie.remove(&x)); + assert!(trie.remove(&x).is_some()); assert!(!trie.contains_key(&x)); check_integrity(&trie.root); } for x in range_step(0u, n, 2) { assert!(trie.contains_key(&x)); - assert!(!trie.insert(x, x + 1)); + assert!(!trie.insert(x, x + 1).is_none()); check_integrity(&trie.root); } } @@ -1017,11 +1021,11 @@ mod test { fn test_each_reverse() { let mut m = TrieMap::new(); - assert!(m.insert(3, 6)); - assert!(m.insert(0, 0)); - assert!(m.insert(4, 8)); - assert!(m.insert(2, 4)); - assert!(m.insert(1, 2)); + assert!(m.insert(3, 6).is_none()); + assert!(m.insert(0, 0).is_none()); + assert!(m.insert(4, 8).is_none()); + assert!(m.insert(2, 4).is_none()); + assert!(m.insert(1, 2).is_none()); let mut n = 4; m.each_reverse(|k, v| { @@ -1054,19 +1058,19 @@ mod test { } #[test] - fn test_swap() { + fn test_insert() { let mut m = TrieMap::new(); - assert_eq!(m.swap(1u, 2i), None); - assert_eq!(m.swap(1u, 3i), Some(2)); - assert_eq!(m.swap(1u, 4i), Some(3)); + assert_eq!(m.insert(1u, 2i), None); + assert_eq!(m.insert(1u, 3i), Some(2)); + assert_eq!(m.insert(1u, 4i), Some(3)); } #[test] - fn test_pop() { + fn test_remove() { let mut m = TrieMap::new(); m.insert(1u, 2i); - assert_eq!(m.pop(&1), Some(2)); - assert_eq!(m.pop(&1), None); + assert_eq!(m.remove(&1), Some(2)); + assert_eq!(m.remove(&1), None); } #[test] @@ -1076,7 +1080,7 @@ mod test { let map: TrieMap<int> = xs.iter().map(|&x| x).collect(); for &(k, v) in xs.iter() { - assert_eq!(map.find(&k), Some(&v)); + assert_eq!(map.get(&k), Some(&v)); } } @@ -1243,15 +1247,15 @@ mod test { let mut b = TrieMap::new(); assert!(a == b); - assert!(a.insert(0, 5i)); + assert!(a.insert(0, 5i).is_none()); assert!(a != b); - assert!(b.insert(0, 4i)); + assert!(b.insert(0, 4i).is_none()); assert!(a != b); - assert!(a.insert(5, 19)); + assert!(a.insert(5, 19).is_none()); assert!(a != b); - assert!(!b.insert(0, 5)); + assert!(!b.insert(0, 5).is_none()); assert!(a != b); - assert!(b.insert(5, 19)); + assert!(b.insert(5, 19).is_none()); assert!(a == b); } @@ -1261,15 +1265,15 @@ mod test { let mut b = TrieMap::new(); assert!(!(a < b) && !(b < a)); - assert!(b.insert(2u, 5i)); + assert!(b.insert(2u, 5i).is_none()); assert!(a < b); - assert!(a.insert(2, 7)); + assert!(a.insert(2, 7).is_none()); assert!(!(a < b) && b < a); - assert!(b.insert(1, 0)); + assert!(b.insert(1, 0).is_none()); assert!(b < a); - assert!(a.insert(0, 6)); + assert!(a.insert(0, 6).is_none()); assert!(a < b); - assert!(a.insert(6, 2)); + assert!(a.insert(6, 2).is_none()); assert!(a < b && !(b < a)); } @@ -1279,10 +1283,10 @@ mod test { let mut b = TrieMap::new(); assert!(a <= b && a >= b); - assert!(a.insert(1u, 1i)); + assert!(a.insert(1u, 1i).is_none()); assert!(a > b && a >= b); assert!(b < a && b <= a); - assert!(b.insert(2, 2)); + assert!(b.insert(2, 2).is_none()); assert!(b > a && b >= a); assert!(a < b && a <= b); } @@ -1355,7 +1359,7 @@ mod bench { let mut rng = weak_rng(); for _ in range(0, size) { - map.swap(rng.gen(), rng.gen()); + map.insert(rng.gen(), rng.gen()); } b.iter(|| { diff --git a/src/libcollections/trie/set.rs b/src/libcollections/trie/set.rs index ddddd279b04..dd5a81fe96e 100644 --- a/src/libcollections/trie/set.rs +++ b/src/libcollections/trie/set.rs @@ -8,6 +8,12 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. +// FIXME(conventions): implement bounded iterators +// FIXME(conventions): implement union family of fns +// FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub +// FIXME(conventions): replace each_reverse by making iter DoubleEnded +// FIXME(conventions): implement iter_mut and into_iter + use core::prelude::*; use core::default::Default; @@ -79,6 +85,7 @@ impl TrieSet { /// let mut set = TrieSet::new(); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> TrieSet { TrieSet{map: TrieMap::new()} } @@ -126,6 +133,7 @@ impl TrieSet { /// } /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter<'a>(&'a self) -> SetItems<'a> { SetItems{iter: self.map.iter()} } @@ -177,6 +185,7 @@ impl TrieSet { /// assert_eq!(v.len(), 1); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.map.len() } /// Returns true if the set contains no elements @@ -191,6 +200,7 @@ impl TrieSet { /// v.insert(1); /// assert!(!v.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.len() == 0 } /// Clears the set, removing all values. @@ -206,6 +216,7 @@ impl TrieSet { /// assert!(v.is_empty()); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { self.map.clear() } /// Returns `true` if the set contains a value. @@ -220,6 +231,7 @@ impl TrieSet { /// assert_eq!(set.contains(&4), false); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn contains(&self, value: &uint) -> bool { self.map.contains_key(value) } @@ -242,6 +254,7 @@ impl TrieSet { /// assert_eq!(a.is_disjoint(&b), false); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_disjoint(&self, other: &TrieSet) -> bool { self.iter().all(|v| !other.contains(&v)) } @@ -263,6 +276,7 @@ impl TrieSet { /// assert_eq!(set.is_subset(&sup), false); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_subset(&self, other: &TrieSet) -> bool { self.iter().all(|v| other.contains(&v)) } @@ -287,6 +301,7 @@ impl TrieSet { /// assert_eq!(set.is_superset(&sub), true); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_superset(&self, other: &TrieSet) -> bool { other.is_subset(self) } @@ -306,8 +321,9 @@ impl TrieSet { /// assert_eq!(set.len(), 1); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn insert(&mut self, value: uint) -> bool { - self.map.insert(value, ()) + self.map.insert(value, ()).is_none() } /// Removes a value from the set. Returns `true` if the value was @@ -325,8 +341,9 @@ impl TrieSet { /// assert_eq!(set.remove(&2), false); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn remove(&mut self, value: &uint) -> bool { - self.map.remove(value) + self.map.remove(value).is_some() } } diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs index 4b6921ed0c0..707084d9c70 100644 --- a/src/libcollections/vec.rs +++ b/src/libcollections/vec.rs @@ -312,7 +312,7 @@ impl<T: Clone> Vec<T> { #[inline] #[experimental] pub fn push_all(&mut self, other: &[T]) { - self.reserve_additional(other.len()); + self.reserve(other.len()); for i in range(0, other.len()) { let len = self.len(); @@ -342,7 +342,7 @@ impl<T: Clone> Vec<T> { /// ``` #[stable] pub fn grow(&mut self, n: uint, value: T) { - self.reserve_additional(n); + self.reserve(n); let mut i: uint = 0u; while i < n { @@ -489,7 +489,7 @@ impl<T> Extendable<T> for Vec<T> { #[inline] fn extend<I: Iterator<T>>(&mut self, mut iterator: I) { let (lower, _) = iterator.size_hint(); - self.reserve_additional(lower); + self.reserve(lower); for element in iterator { self.push(element) } @@ -578,74 +578,70 @@ impl<T> Vec<T> { self.cap } - /// Reserves capacity for at least `n` additional elements in the given - /// vector. - /// - /// # Failure - /// - /// Fails if the new capacity overflows `uint`. - /// - /// # Example - /// - /// ``` - /// let mut vec: Vec<int> = vec![1i]; - /// vec.reserve_additional(10); - /// assert!(vec.capacity() >= 11); - /// ``` + /// Deprecated: Renamed to `reserve`. + #[deprecated = "Renamed to `reserve`"] pub fn reserve_additional(&mut self, extra: uint) { - if self.cap - self.len < extra { - match self.len.checked_add(&extra) { - None => panic!("Vec::reserve_additional: `uint` overflow"), - Some(new_cap) => self.reserve(new_cap) - } - } + self.reserve(extra) } - /// Reserves capacity for at least `n` elements in the given vector. + /// Reserves capacity for at least `additional` more elements to be inserted in the given + /// `Vec`. The collection may reserve more space to avoid frequent reallocations. /// - /// This function will over-allocate in order to amortize the allocation - /// costs in scenarios where the caller may need to repeatedly reserve - /// additional space. + /// # Panics /// - /// If the capacity for `self` is already equal to or greater than the - /// requested capacity, then no action is taken. + /// Panics if the new capacity overflows `uint`. /// /// # Example /// /// ``` - /// let mut vec = vec![1i, 2, 3]; + /// let mut vec: Vec<int> = vec![1]; /// vec.reserve(10); - /// assert!(vec.capacity() >= 10); + /// assert!(vec.capacity() >= 11); /// ``` - pub fn reserve(&mut self, capacity: uint) { - if capacity > self.cap { - self.reserve_exact(num::next_power_of_two(capacity)) + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn reserve(&mut self, additional: uint) { + if self.cap - self.len < additional { + match self.len.checked_add(&additional) { + None => panic!("Vec::reserve: `uint` overflow"), + // if the checked_add + Some(new_cap) => { + let amort_cap = num::next_power_of_two(new_cap); + // next_power_of_two will overflow to exactly 0 for really big capacities + if amort_cap == 0 { + self.grow_capacity(new_cap); + } else { + self.grow_capacity(amort_cap); + } + } + } } } - /// Reserves capacity for exactly `capacity` elements in the given vector. + /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the + /// given `Vec`. Does nothing if the capacity is already sufficient. /// - /// If the capacity for `self` is already equal to or greater than the - /// requested capacity, then no action is taken. + /// Note that the allocator may give the collection more space than it requests. Therefore + /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future + /// insertions are expected. + /// + /// # Panics + /// + /// Panics if the new capacity overflows `uint`. /// /// # Example /// /// ``` - /// let mut vec: Vec<int> = Vec::with_capacity(10); - /// vec.reserve_exact(11); - /// assert_eq!(vec.capacity(), 11); + /// let mut vec: Vec<int> = vec![1]; + /// vec.reserve_exact(10); + /// assert!(vec.capacity() >= 11); /// ``` - pub fn reserve_exact(&mut self, capacity: uint) { - if mem::size_of::<T>() == 0 { return } - - if capacity > self.cap { - let size = capacity.checked_mul(&mem::size_of::<T>()) - .expect("capacity overflow"); - unsafe { - self.ptr = alloc_or_realloc(self.ptr, self.cap * mem::size_of::<T>(), size); - if self.ptr.is_null() { ::alloc::oom() } + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn reserve_exact(&mut self, additional: uint) { + if self.cap - self.len < additional { + match self.len.checked_add(&additional) { + None => panic!("Vec::reserve: `uint` overflow"), + Some(new_cap) => self.grow_capacity(new_cap) } - self.cap = capacity; } } @@ -663,6 +659,7 @@ impl<T> Vec<T> { /// assert!(vec.capacity() >= 3); /// ``` #[stable] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn shrink_to_fit(&mut self) { if mem::size_of::<T>() == 0 { return } @@ -713,7 +710,7 @@ impl<T> Vec<T> { /// vec.truncate(2); /// assert_eq!(vec, vec![1, 2]); /// ``` - #[unstable = "waiting on panic semantics"] + #[unstable = "matches collection reform specification; waiting on panic semantics"] pub fn truncate(&mut self, len: uint) { unsafe { // drop any extra elements @@ -761,6 +758,7 @@ impl<T> Vec<T> { /// } /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn into_iter(self) -> MoveItems<T> { unsafe { let ptr = self.ptr; @@ -796,26 +794,6 @@ impl<T> Vec<T> { self.len = len; } - /// Returns a mutable reference to the value at index `index`. - /// - /// # Failure - /// - /// Fails if `index` is out of bounds - /// - /// # Example - /// - /// ``` - /// # #![allow(deprecated)] - /// let mut vec = vec![1i, 2, 3]; - /// *vec.get_mut(1) = 4; - /// assert_eq!(vec, vec![1i, 4, 3]); - /// ``` - #[inline] - #[deprecated = "use `foo[index] = bar` instead"] - pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut T { - &mut self.as_mut_slice()[index] - } - /// Removes an element from anywhere in the vector and return it, replacing /// it with the last element. This does not preserve ordering, but is O(1). /// @@ -868,7 +846,7 @@ impl<T> Vec<T> { let len = self.len(); assert!(index <= len); // space for the new element - self.reserve(len + 1); + self.reserve(1); unsafe { // infallible // The spot to put the new value @@ -970,7 +948,7 @@ impl<T> Vec<T> { /// ``` #[unstable = "this function may be renamed or change to unboxed closures"] pub fn grow_fn(&mut self, n: uint, f: |uint| -> T) { - self.reserve_additional(n); + self.reserve(n); for i in range(0u, n) { self.push(f(i)); } @@ -1076,7 +1054,26 @@ impl<T> Vec<T> { /// v.push(1i); /// assert!(!v.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Reserves capacity for exactly `capacity` elements in the given vector. + /// + /// If the capacity for `self` is already equal to or greater than the + /// requested capacity, then no action is taken. + fn grow_capacity(&mut self, capacity: uint) { + if mem::size_of::<T>() == 0 { return } + + if capacity > self.cap { + let size = capacity.checked_mul(&mem::size_of::<T>()) + .expect("capacity overflow"); + unsafe { + self.ptr = alloc_or_realloc(self.ptr, self.cap * mem::size_of::<T>(), size); + if self.ptr.is_null() { ::alloc::oom() } + } + self.cap = capacity; + } + } } impl<T: PartialEq> Vec<T> { @@ -1742,11 +1739,11 @@ mod tests { } #[test] - fn test_reserve_additional() { + fn test_reserve() { let mut v = Vec::new(); assert_eq!(v.capacity(), 0); - v.reserve_additional(2); + v.reserve(2); assert!(v.capacity() >= 2); for i in range(0i, 16) { @@ -1754,12 +1751,12 @@ mod tests { } assert!(v.capacity() >= 16); - v.reserve_additional(16); + v.reserve(16); assert!(v.capacity() >= 32); v.push(16); - v.reserve_additional(16); + v.reserve(16); assert!(v.capacity() >= 33) } diff --git a/src/libcollections/vec_map.rs b/src/libcollections/vec_map.rs index c0bc785126c..38a345272b0 100644 --- a/src/libcollections/vec_map.rs +++ b/src/libcollections/vec_map.rs @@ -26,6 +26,8 @@ use vec::Vec; use hash; use hash::Hash; +// FIXME(conventions): capacity management??? + /// A map optimized for small integer keys. /// /// # Example @@ -42,14 +44,14 @@ use hash::Hash; /// println!("The end is near!"); /// } /// -/// assert_eq!(months.find(&1), Some(&"Jan")); +/// assert_eq!(months.get(&1), Some(&"Jan")); /// -/// match months.find_mut(&3) { +/// match months.get_mut(&3) { /// Some(value) => *value = "Venus", /// None => (), /// } /// -/// assert_eq!(months.find(&3), Some(&"Venus")); +/// assert_eq!(months.get(&3), Some(&"Venus")); /// /// // Print out all months /// for (key, value) in months.iter() { @@ -77,10 +79,7 @@ impl<V:Clone> Clone for VecMap<V> { #[inline] fn clone_from(&mut self, source: &VecMap<V>) { - self.v.reserve(source.v.len()); - for (i, w) in self.v.iter_mut().enumerate() { - *w = source.v[i].clone(); - } + self.v.clone_from(&source.v); } } @@ -99,6 +98,7 @@ impl<V> VecMap<V> { /// use std::collections::VecMap; /// let mut map: VecMap<&str> = VecMap::new(); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> VecMap<V> { VecMap{v: vec!()} } /// Creates an empty `VecMap` with space for at least `capacity` @@ -110,18 +110,21 @@ impl<V> VecMap<V> { /// use std::collections::VecMap; /// let mut map: VecMap<&str> = VecMap::with_capacity(10); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn with_capacity(capacity: uint) -> VecMap<V> { VecMap { v: Vec::with_capacity(capacity) } } /// Returns an iterator visiting all keys in ascending order by the keys. /// The iterator's element type is `uint`. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn keys<'r>(&'r self) -> Keys<'r, V> { self.iter().map(|(k, _v)| k) } /// Returns an iterator visiting all values in ascending order by the keys. /// The iterator's element type is `&'r V`. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn values<'r>(&'r self) -> Values<'r, V> { self.iter().map(|(_k, v)| v) } @@ -144,6 +147,7 @@ impl<V> VecMap<V> { /// println!("{}: {}", key, value); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter<'r>(&'r self) -> Entries<'r, V> { Entries { front: 0, @@ -174,6 +178,7 @@ impl<V> VecMap<V> { /// assert_eq!(value, &"x"); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter_mut<'r>(&'r mut self) -> MutEntries<'r, V> { MutEntries { front: 0, @@ -201,6 +206,7 @@ impl<V> VecMap<V> { /// /// assert_eq!(vec, vec![(1, "a"), (2, "b"), (3, "c")]); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn into_iter(&mut self) -> FilterMap<(uint, Option<V>), (uint, V), Enumerate<vec::MoveItems<Option<V>>>> @@ -223,6 +229,7 @@ impl<V> VecMap<V> { /// a.insert(1, "a"); /// assert_eq!(a.len(), 1); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.v.iter().filter(|elt| elt.is_some()).count() } @@ -239,6 +246,7 @@ impl<V> VecMap<V> { /// a.insert(1, "a"); /// assert!(!a.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.v.iter().all(|elt| elt.is_none()) } @@ -255,8 +263,15 @@ impl<V> VecMap<V> { /// a.clear(); /// assert!(a.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { self.v.clear() } + /// Deprecated: Renamed to `get`. + #[deprecated = "Renamed to `get`"] + pub fn find(&self, key: &uint) -> Option<&V> { + self.get(key) + } + /// Returns a reference to the value corresponding to the key. /// /// # Example @@ -266,10 +281,11 @@ impl<V> VecMap<V> { /// /// let mut map = VecMap::new(); /// map.insert(1, "a"); - /// assert_eq!(map.find(&1), Some(&"a")); - /// assert_eq!(map.find(&2), None); + /// assert_eq!(map.get(&1), Some(&"a")); + /// assert_eq!(map.get(&2), None); /// ``` - pub fn find<'a>(&'a self, key: &uint) -> Option<&'a V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get(&self, key: &uint) -> Option<&V> { if *key < self.v.len() { match self.v[*key] { Some(ref value) => Some(value), @@ -293,8 +309,15 @@ impl<V> VecMap<V> { /// assert_eq!(map.contains_key(&2), false); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn contains_key(&self, key: &uint) -> bool { - self.find(key).is_some() + self.get(key).is_some() + } + + /// Deprecated: Renamed to `get_mut`. + #[deprecated = "Renamed to `get_mut`"] + pub fn find_mut(&mut self, key: &uint) -> Option<&mut V> { + self.get_mut(key) } /// Returns a mutable reference to the value corresponding to the key. @@ -306,13 +329,14 @@ impl<V> VecMap<V> { /// /// let mut map = VecMap::new(); /// map.insert(1, "a"); - /// match map.find_mut(&1) { + /// match map.get_mut(&1) { /// Some(x) => *x = "b", /// None => (), /// } /// assert_eq!(map[1], "b"); /// ``` - pub fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get_mut(&mut self, key: &uint) -> Option<&mut V> { if *key < self.v.len() { match *(&mut self.v[*key]) { Some(ref mut value) => Some(value), @@ -323,45 +347,10 @@ impl<V> VecMap<V> { } } - /// Inserts a key-value pair into the map. An existing value for a - /// key is replaced by the new value. Returns `true` if the key did - /// not already exist in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::VecMap; - /// - /// let mut map = VecMap::new(); - /// assert_eq!(map.insert(2, "value"), true); - /// assert_eq!(map.insert(2, "value2"), false); - /// assert_eq!(map[2], "value2"); - /// ``` - pub fn insert(&mut self, key: uint, value: V) -> bool { - let exists = self.contains_key(&key); - let len = self.v.len(); - if len <= key { - self.v.grow_fn(key - len + 1, |_| None); - } - self.v[key] = Some(value); - !exists - } - - /// Removes a key-value pair from the map. Returns `true` if the key - /// was present in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::VecMap; - /// - /// let mut map = VecMap::new(); - /// assert_eq!(map.remove(&1), false); - /// map.insert(1, "a"); - /// assert_eq!(map.remove(&1), true); - /// ``` - pub fn remove(&mut self, key: &uint) -> bool { - self.pop(key).is_some() + /// Deprecated: Renamed to `insert`. + #[deprecated = "Renamed to `insert`"] + pub fn swap(&mut self, key: uint, value: V) -> Option<V> { + self.insert(key, value) } /// Inserts a key-value pair from the map. If the key already had a value @@ -373,20 +362,26 @@ impl<V> VecMap<V> { /// use std::collections::VecMap; /// /// let mut map = VecMap::new(); - /// assert_eq!(map.swap(37, "a"), None); + /// assert_eq!(map.insert(37, "a"), None); /// assert_eq!(map.is_empty(), false); /// /// map.insert(37, "b"); - /// assert_eq!(map.swap(37, "c"), Some("b")); + /// assert_eq!(map.insert(37, "c"), Some("b")); /// assert_eq!(map[37], "c"); /// ``` - pub fn swap(&mut self, key: uint, value: V) -> Option<V> { - match self.find_mut(&key) { - Some(loc) => { return Some(replace(loc, value)); } - None => () + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn insert(&mut self, key: uint, value: V) -> Option<V> { + let len = self.v.len(); + if len <= key { + self.v.grow_fn(key - len + 1, |_| None); } - self.insert(key, value); - return None; + replace(&mut self.v[key], Some(value)) + } + + /// Deprecated: Renamed to `remove`. + #[deprecated = "Renamed to `remove`"] + pub fn pop(&mut self, key: &uint) -> Option<V> { + self.remove(key) } /// Removes a key from the map, returning the value at the key if the key @@ -399,10 +394,11 @@ impl<V> VecMap<V> { /// /// let mut map = VecMap::new(); /// map.insert(1, "a"); - /// assert_eq!(map.pop(&1), Some("a")); - /// assert_eq!(map.pop(&1), None); + /// assert_eq!(map.remove(&1), Some("a")); + /// assert_eq!(map.remove(&1), None); /// ``` - pub fn pop(&mut self, key: &uint) -> Option<V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn remove(&mut self, key: &uint) -> Option<V> { if *key >= self.v.len() { return None; } @@ -460,11 +456,11 @@ impl<V:Clone> VecMap<V> { val: V, ff: |uint, V, V| -> V) -> bool { - let new_val = match self.find(&key) { + let new_val = match self.get(&key) { None => val, Some(orig) => ff(key, (*orig).clone(), val) }; - self.insert(key, new_val) + self.insert(key, new_val).is_none() } } @@ -514,14 +510,14 @@ impl<V> Extendable<(uint, V)> for VecMap<V> { impl<V> Index<uint, V> for VecMap<V> { #[inline] fn index<'a>(&'a self, i: &uint) -> &'a V { - self.find(i).expect("key not present") + self.get(i).expect("key not present") } } impl<V> IndexMut<uint, V> for VecMap<V> { #[inline] fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut V { - self.find_mut(i).expect("key not present") + self.get_mut(i).expect("key not present") } } @@ -615,16 +611,16 @@ mod test_map { use super::VecMap; #[test] - fn test_find_mut() { + fn test_get_mut() { let mut m = VecMap::new(); - assert!(m.insert(1, 12i)); - assert!(m.insert(2, 8)); - assert!(m.insert(5, 14)); + assert!(m.insert(1, 12i).is_none()); + assert!(m.insert(2, 8).is_none()); + assert!(m.insert(5, 14).is_none()); let new = 100; - match m.find_mut(&5) { + match m.get_mut(&5) { None => panic!(), Some(x) => *x = new } - assert_eq!(m.find(&5), Some(&new)); + assert_eq!(m.get(&5), Some(&new)); } #[test] @@ -632,13 +628,13 @@ mod test_map { let mut map = VecMap::new(); assert_eq!(map.len(), 0); assert!(map.is_empty()); - assert!(map.insert(5, 20i)); + assert!(map.insert(5, 20i).is_none()); assert_eq!(map.len(), 1); assert!(!map.is_empty()); - assert!(map.insert(11, 12)); + assert!(map.insert(11, 12).is_none()); assert_eq!(map.len(), 2); assert!(!map.is_empty()); - assert!(map.insert(14, 22)); + assert!(map.insert(14, 22).is_none()); assert_eq!(map.len(), 3); assert!(!map.is_empty()); } @@ -646,14 +642,14 @@ mod test_map { #[test] fn test_clear() { let mut map = VecMap::new(); - assert!(map.insert(5, 20i)); - assert!(map.insert(11, 12)); - assert!(map.insert(14, 22)); + assert!(map.insert(5, 20i).is_none()); + assert!(map.insert(11, 12).is_none()); + assert!(map.insert(14, 22).is_none()); map.clear(); assert!(map.is_empty()); - assert!(map.find(&5).is_none()); - assert!(map.find(&11).is_none()); - assert!(map.find(&14).is_none()); + assert!(map.get(&5).is_none()); + assert!(map.get(&11).is_none()); + assert!(map.get(&14).is_none()); } #[test] @@ -678,28 +674,28 @@ mod test_map { map.update_with_key(3, 2, add_more_to_count); // check the total counts - assert_eq!(map.find(&3).unwrap(), &10); - assert_eq!(map.find(&5).unwrap(), &3); - assert_eq!(map.find(&9).unwrap(), &1); + assert_eq!(map.get(&3).unwrap(), &10); + assert_eq!(map.get(&5).unwrap(), &3); + assert_eq!(map.get(&9).unwrap(), &1); // sadly, no sevens were counted - assert!(map.find(&7).is_none()); + assert!(map.get(&7).is_none()); } #[test] - fn test_swap() { + fn test_insert() { let mut m = VecMap::new(); - assert_eq!(m.swap(1, 2i), None); - assert_eq!(m.swap(1, 3i), Some(2)); - assert_eq!(m.swap(1, 4i), Some(3)); + assert_eq!(m.insert(1, 2i), None); + assert_eq!(m.insert(1, 3i), Some(2)); + assert_eq!(m.insert(1, 4i), Some(3)); } #[test] - fn test_pop() { + fn test_remove() { let mut m = VecMap::new(); m.insert(1, 2i); - assert_eq!(m.pop(&1), Some(2)); - assert_eq!(m.pop(&1), None); + assert_eq!(m.remove(&1), Some(2)); + assert_eq!(m.remove(&1), None); } #[test] @@ -732,11 +728,11 @@ mod test_map { fn test_iterator() { let mut m = VecMap::new(); - assert!(m.insert(0, 1i)); - assert!(m.insert(1, 2)); - assert!(m.insert(3, 5)); - assert!(m.insert(6, 10)); - assert!(m.insert(10, 11)); + assert!(m.insert(0, 1i).is_none()); + assert!(m.insert(1, 2).is_none()); + assert!(m.insert(3, 5).is_none()); + assert!(m.insert(6, 10).is_none()); + assert!(m.insert(10, 11).is_none()); let mut it = m.iter(); assert_eq!(it.size_hint(), (0, Some(11))); @@ -757,11 +753,11 @@ mod test_map { fn test_iterator_size_hints() { let mut m = VecMap::new(); - assert!(m.insert(0, 1i)); - assert!(m.insert(1, 2)); - assert!(m.insert(3, 5)); - assert!(m.insert(6, 10)); - assert!(m.insert(10, 11)); + assert!(m.insert(0, 1i).is_none()); + assert!(m.insert(1, 2).is_none()); + assert!(m.insert(3, 5).is_none()); + assert!(m.insert(6, 10).is_none()); + assert!(m.insert(10, 11).is_none()); assert_eq!(m.iter().size_hint(), (0, Some(11))); assert_eq!(m.iter().rev().size_hint(), (0, Some(11))); @@ -773,11 +769,11 @@ mod test_map { fn test_mut_iterator() { let mut m = VecMap::new(); - assert!(m.insert(0, 1i)); - assert!(m.insert(1, 2)); - assert!(m.insert(3, 5)); - assert!(m.insert(6, 10)); - assert!(m.insert(10, 11)); + assert!(m.insert(0, 1i).is_none()); + assert!(m.insert(1, 2).is_none()); + assert!(m.insert(3, 5).is_none()); + assert!(m.insert(6, 10).is_none()); + assert!(m.insert(10, 11).is_none()); for (k, v) in m.iter_mut() { *v += k as int; @@ -796,11 +792,11 @@ mod test_map { fn test_rev_iterator() { let mut m = VecMap::new(); - assert!(m.insert(0, 1i)); - assert!(m.insert(1, 2)); - assert!(m.insert(3, 5)); - assert!(m.insert(6, 10)); - assert!(m.insert(10, 11)); + assert!(m.insert(0, 1i).is_none()); + assert!(m.insert(1, 2).is_none()); + assert!(m.insert(3, 5).is_none()); + assert!(m.insert(6, 10).is_none()); + assert!(m.insert(10, 11).is_none()); let mut it = m.iter().rev(); assert_eq!(it.next().unwrap(), (10, &11)); @@ -815,11 +811,11 @@ mod test_map { fn test_mut_rev_iterator() { let mut m = VecMap::new(); - assert!(m.insert(0, 1i)); - assert!(m.insert(1, 2)); - assert!(m.insert(3, 5)); - assert!(m.insert(6, 10)); - assert!(m.insert(10, 11)); + assert!(m.insert(0, 1i).is_none()); + assert!(m.insert(1, 2).is_none()); + assert!(m.insert(3, 5).is_none()); + assert!(m.insert(6, 10).is_none()); + assert!(m.insert(10, 11).is_none()); for (k, v) in m.iter_mut().rev() { *v += k as int; @@ -880,15 +876,15 @@ mod test_map { let mut b = VecMap::new(); assert!(a == b); - assert!(a.insert(0, 5i)); + assert!(a.insert(0, 5i).is_none()); assert!(a != b); - assert!(b.insert(0, 4i)); + assert!(b.insert(0, 4i).is_none()); assert!(a != b); - assert!(a.insert(5, 19)); + assert!(a.insert(5, 19).is_none()); assert!(a != b); - assert!(!b.insert(0, 5)); + assert!(!b.insert(0, 5).is_none()); assert!(a != b); - assert!(b.insert(5, 19)); + assert!(b.insert(5, 19).is_none()); assert!(a == b); } @@ -898,15 +894,15 @@ mod test_map { let mut b = VecMap::new(); assert!(!(a < b) && !(b < a)); - assert!(b.insert(2u, 5i)); + assert!(b.insert(2u, 5i).is_none()); assert!(a < b); - assert!(a.insert(2, 7)); + assert!(a.insert(2, 7).is_none()); assert!(!(a < b) && b < a); - assert!(b.insert(1, 0)); + assert!(b.insert(1, 0).is_none()); assert!(b < a); - assert!(a.insert(0, 6)); + assert!(a.insert(0, 6).is_none()); assert!(a < b); - assert!(a.insert(6, 2)); + assert!(a.insert(6, 2).is_none()); assert!(a < b && !(b < a)); } @@ -916,10 +912,10 @@ mod test_map { let mut b = VecMap::new(); assert!(a <= b && a >= b); - assert!(a.insert(1u, 1i)); + assert!(a.insert(1u, 1i).is_none()); assert!(a > b && a >= b); assert!(b < a && b <= a); - assert!(b.insert(2, 2)); + assert!(b.insert(2, 2).is_none()); assert!(b > a && b >= a); assert!(a < b && a <= b); } @@ -948,7 +944,7 @@ mod test_map { let map: VecMap<char> = xs.iter().map(|&x| x).collect(); for &(k, v) in xs.iter() { - assert_eq!(map.find(&k), Some(&v)); + assert_eq!(map.get(&k), Some(&v)); } } @@ -1022,7 +1018,7 @@ mod bench { let mut m : VecMap<uint> = VecMap::new(); find_rand_n(100, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } #[bench] @@ -1030,7 +1026,7 @@ mod bench { let mut m : VecMap<uint> = VecMap::new(); find_rand_n(10_000, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } // Find seq @@ -1039,7 +1035,7 @@ mod bench { let mut m : VecMap<uint> = VecMap::new(); find_seq_n(100, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } #[bench] @@ -1047,6 +1043,6 @@ mod bench { let mut m : VecMap<uint> = VecMap::new(); find_seq_n(10_000, &mut m, b, |m, i| { m.insert(i, 1); }, - |m, i| { m.find(&i); }); + |m, i| { m.get(&i); }); } } diff --git a/src/libstd/collections/hash/bench.rs b/src/libstd/collections/hash/bench.rs index 62b93336a34..87aebb24f98 100644 --- a/src/libstd/collections/hash/bench.rs +++ b/src/libstd/collections/hash/bench.rs @@ -102,14 +102,14 @@ fn hashmap_as_queue(b: &mut Bencher) { let mut k = 1i; b.iter(|| { - m.pop(&k); + m.remove(&k); m.insert(k + 1000, k + 1000); k += 1; }); } #[bench] -fn find_pop_insert(b: &mut Bencher) { +fn get_remove_insert(b: &mut Bencher) { use super::map::HashMap; let mut m = HashMap::new(); @@ -121,9 +121,9 @@ fn find_pop_insert(b: &mut Bencher) { let mut k = 1i; b.iter(|| { - m.find(&(k + 400)); - m.find(&(k + 2000)); - m.pop(&k); + m.get(&(k + 400)); + m.get(&(k + 2000)); + m.remove(&k); m.insert(k + 1000, k + 1000); k += 1; }) diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs index 596e483c2f6..7ff332c295c 100644 --- a/src/libstd/collections/hash/map.rs +++ b/src/libstd/collections/hash/map.rs @@ -36,6 +36,9 @@ use super::table::{ SafeHash }; +// FIXME(conventions): update capacity management to match other collections (no auto-shrink) +// FIXME(conventions): axe find_copy/get_copy in favour of Option.cloned (also implement that) + const INITIAL_LOG2_CAP: uint = 5; pub const INITIAL_CAPACITY: uint = 1 << INITIAL_LOG2_CAP; // 2^5 @@ -233,7 +236,7 @@ impl DefaultResizePolicy { /// // look up the values associated with some keys. /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"]; /// for book in to_find.iter() { -/// match book_reviews.find(book) { +/// match book_reviews.get(book) { /// Some(review) => println!("{}: {}", *book, *review), /// None => println!("{} is unreviewed.", *book) /// } @@ -480,6 +483,7 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> { /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> HashMap<K, V, RandomSipHasher> { let hasher = RandomSipHasher::new(); HashMap::with_hasher(hasher) @@ -494,6 +498,7 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> { /// let mut map: HashMap<&str, int> = HashMap::with_capacity(10); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn with_capacity(capacity: uint) -> HashMap<K, V, RandomSipHasher> { let hasher = RandomSipHasher::new(); HashMap::with_capacity_and_hasher(capacity, hasher) @@ -741,38 +746,6 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { } } - /// Retrieves a mutable value for the given key. - /// See [`find_mut`](../trait.MutableMap.html#tymethod.find_mut) for a non-panicking - /// alternative. - /// - /// # Failure - /// - /// Fails if the key is not present. - /// - /// # Example - /// - /// ``` - /// # #![allow(deprecated)] - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1i); - /// { - /// // val will freeze map to prevent usage during its lifetime - /// let val = map.get_mut(&"a"); - /// *val = 40; - /// } - /// assert_eq!(map["a"], 40); - /// - /// // A more direct way could be: - /// *map.get_mut(&"a") = -2; - /// assert_eq!(map["a"], -2); - /// ``` - #[deprecated = "use indexing instead: `&mut map[key]`"] - pub fn get_mut<'a>(&'a mut self, k: &K) -> &'a mut V { - &mut self[*k] - } - /// Return true if the map contains a value for the specified key, /// using equivalence. /// @@ -875,6 +848,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// println!("{}", key); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn keys(&self) -> Keys<K, V> { self.iter().map(|(k, _v)| k) } @@ -896,6 +870,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// println!("{}", key); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn values(&self) -> Values<K, V> { self.iter().map(|(_k, v)| v) } @@ -917,6 +892,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// println!("key: {} val: {}", key, val); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter(&self) -> Entries<K, V> { Entries { inner: self.table.iter() } } @@ -944,6 +920,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// println!("key: {} val: {}", key, val); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter_mut(&mut self) -> MutEntries<K, V> { MutEntries { inner: self.table.iter_mut() } } @@ -965,6 +942,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// // Not possible with .iter() /// let vec: Vec<(&str, int)> = map.into_iter().collect(); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn into_iter(self) -> MoveEntries<K, V> { MoveEntries { inner: self.table.into_iter().map(|(_, k, v)| (k, v)) @@ -996,6 +974,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// a.insert(1u, "a"); /// assert_eq!(a.len(), 1); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.table.size() } /// Return true if the map contains no elements. @@ -1011,6 +990,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// assert!(!a.is_empty()); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.len() == 0 } /// Clears the map, removing all key-value pairs. Keeps the allocated memory @@ -1026,6 +1006,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// a.clear(); /// assert!(a.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { // Prevent reallocations from happening from now on. Makes it possible // for the map to be reused but has a downside: reserves permanently. @@ -1045,6 +1026,12 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { } } + /// Deprecated: Renamed to `get`. + #[deprecated = "Renamed to `get`"] + pub fn find(&self, k: &K) -> Option<&V> { + self.get(k) + } + /// Returns a reference to the value corresponding to the key. /// /// # Example @@ -1054,10 +1041,11 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// /// let mut map = HashMap::new(); /// map.insert(1u, "a"); - /// assert_eq!(map.find(&1), Some(&"a")); - /// assert_eq!(map.find(&2), None); + /// assert_eq!(map.get(&1), Some(&"a")); + /// assert_eq!(map.get(&2), None); /// ``` - pub fn find<'a>(&'a self, k: &K) -> Option<&'a V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get(&self, k: &K) -> Option<&V> { self.search(k).map(|bucket| { let (_, v) = bucket.into_refs(); v @@ -1076,10 +1064,17 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// assert_eq!(map.contains_key(&1), true); /// assert_eq!(map.contains_key(&2), false); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn contains_key(&self, k: &K) -> bool { self.search(k).is_some() } + /// Deprecated: Renamed to `get_mut`. + #[deprecated = "Renamed to `get_mut`"] + pub fn find_mut(&mut self, k: &K) -> Option<&mut V> { + self.get_mut(k) + } + /// Returns a mutable reference to the value corresponding to the key. /// /// # Example @@ -1089,13 +1084,14 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// /// let mut map = HashMap::new(); /// map.insert(1u, "a"); - /// match map.find_mut(&1) { + /// match map.get_mut(&1) { /// Some(x) => *x = "b", /// None => (), /// } /// assert_eq!(map[1], "b"); /// ``` - pub fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get_mut(&mut self, k: &K) -> Option<&mut V> { match self.search_mut(k) { Some(bucket) => { let (_, v) = bucket.into_mut_refs(); @@ -1105,41 +1101,10 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { } } - /// Inserts a key-value pair into the map. An existing value for a - /// key is replaced by the new value. Returns `true` if the key did - /// not already exist in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// assert_eq!(map.insert(2u, "value"), true); - /// assert_eq!(map.insert(2, "value2"), false); - /// assert_eq!(map[2], "value2"); - /// ``` - #[inline] - pub fn insert(&mut self, key: K, value: V) -> bool { - self.swap(key, value).is_none() - } - - /// Removes a key-value pair from the map. Returns `true` if the key - /// was present in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// assert_eq!(map.remove(&1u), false); - /// map.insert(1, "a"); - /// assert_eq!(map.remove(&1), true); - /// ``` - #[inline] - pub fn remove(&mut self, key: &K) -> bool { - self.pop(key).is_some() + /// Deprecated: Renamed to `insert`. + #[deprecated = "Renamed to `insert`"] + pub fn swap(&mut self, k: K, v: V) -> Option<V> { + self.insert(k, v) } /// Inserts a key-value pair from the map. If the key already had a value @@ -1151,14 +1116,15 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// use std::collections::HashMap; /// /// let mut map = HashMap::new(); - /// assert_eq!(map.swap(37u, "a"), None); + /// assert_eq!(map.insert(37u, "a"), None); /// assert_eq!(map.is_empty(), false); /// /// map.insert(37, "b"); - /// assert_eq!(map.swap(37, "c"), Some("b")); + /// assert_eq!(map.insert(37, "c"), Some("b")); /// assert_eq!(map[37], "c"); /// ``` - pub fn swap(&mut self, k: K, v: V) -> Option<V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn insert(&mut self, k: K, v: V) -> Option<V> { let hash = self.make_hash(&k); let potential_new_size = self.table.size() + 1; self.make_some_room(potential_new_size); @@ -1170,6 +1136,12 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { retval } + /// Deprecated: Renamed to `remove`. + #[deprecated = "Renamed to `remove`"] + pub fn pop(&mut self, k: &K) -> Option<V> { + self.remove(k) + } + /// Removes a key from the map, returning the value at the key if the key /// was previously in the map. /// @@ -1180,10 +1152,11 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// /// let mut map = HashMap::new(); /// map.insert(1u, "a"); - /// assert_eq!(map.pop(&1), Some("a")); - /// assert_eq!(map.pop(&1), None); + /// assert_eq!(map.remove(&1), Some("a")); + /// assert_eq!(map.remove(&1), None); /// ``` - pub fn pop(&mut self, k: &K) -> Option<V> { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn remove(&mut self, k: &K) -> Option<V> { if self.table.size() == 0 { return None } @@ -1260,7 +1233,7 @@ impl<K: Eq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> { /// let s: String = map.find_copy(&1).unwrap(); /// ``` pub fn find_copy(&self, k: &K) -> Option<V> { - self.find(k).map(|v| (*v).clone()) + self.get(k).map(|v| (*v).clone()) } /// Return a copy of the value corresponding to the key. @@ -1288,7 +1261,7 @@ impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V, if self.len() != other.len() { return false; } self.iter().all(|(key, value)| - other.find(key).map_or(false, |v| *value == *v) + other.get(key).map_or(false, |v| *value == *v) ) } } @@ -1317,14 +1290,14 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H> impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Index<K, V> for HashMap<K, V, H> { #[inline] fn index<'a>(&'a self, index: &K) -> &'a V { - self.find(index).expect("no entry found for key") + self.get(index).expect("no entry found for key") } } impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> IndexMut<K, V> for HashMap<K, V, H> { #[inline] fn index_mut<'a>(&'a mut self, index: &K) -> &'a mut V { - match self.find_mut(index) { + match self.get_mut(index) { Some(v) => v, None => panic!("no entry found for key") } @@ -1514,7 +1487,7 @@ mod test_map { fn test_create_capacity_zero() { let mut m = HashMap::with_capacity(0); - assert!(m.insert(1i, 1i)); + assert!(m.insert(1i, 1i).is_none()); assert!(m.contains_key(&1)); assert!(!m.contains_key(&0)); @@ -1524,12 +1497,12 @@ mod test_map { fn test_insert() { let mut m = HashMap::new(); assert_eq!(m.len(), 0); - assert!(m.insert(1i, 2i)); + assert!(m.insert(1i, 2i).is_none()); assert_eq!(m.len(), 1); - assert!(m.insert(2i, 4i)); + assert!(m.insert(2i, 4i).is_none()); assert_eq!(m.len(), 2); - assert_eq!(*m.find(&1).unwrap(), 2); - assert_eq!(*m.find(&2).unwrap(), 4); + assert_eq!(*m.get(&1).unwrap(), 2); + assert_eq!(*m.get(&2).unwrap(), 4); } local_data_key!(drop_vector: RefCell<Vec<int>>) @@ -1588,7 +1561,7 @@ mod test_map { for i in range(0u, 50) { let k = Dropable::new(i); - let v = m.pop(&k); + let v = m.remove(&k); assert!(v.is_some()); @@ -1679,7 +1652,7 @@ mod test_map { #[test] fn test_empty_pop() { let mut m: HashMap<int, bool> = HashMap::new(); - assert_eq!(m.pop(&0), None); + assert_eq!(m.remove(&0), None); } #[test] @@ -1692,15 +1665,15 @@ mod test_map { assert!(m.is_empty()); for i in range_inclusive(1i, 1000) { - assert!(m.insert(i, i)); + assert!(m.insert(i, i).is_none()); for j in range_inclusive(1, i) { - let r = m.find(&j); + let r = m.get(&j); assert_eq!(r, Some(&j)); } for j in range_inclusive(i+1, 1000) { - let r = m.find(&j); + let r = m.get(&j); assert_eq!(r, None); } } @@ -1711,7 +1684,7 @@ mod test_map { // remove forwards for i in range_inclusive(1i, 1000) { - assert!(m.remove(&i)); + assert!(m.remove(&i).is_some()); for j in range_inclusive(1, i) { assert!(!m.contains_key(&j)); @@ -1727,12 +1700,12 @@ mod test_map { } for i in range_inclusive(1i, 1000) { - assert!(m.insert(i, i)); + assert!(m.insert(i, i).is_none()); } // remove backwards for i in range_step_inclusive(1000i, 1, -1) { - assert!(m.remove(&i)); + assert!(m.remove(&i).is_some()); for j in range_inclusive(i, 1000) { assert!(!m.contains_key(&j)); @@ -1748,59 +1721,59 @@ mod test_map { #[test] fn test_find_mut() { let mut m = HashMap::new(); - assert!(m.insert(1i, 12i)); - assert!(m.insert(2i, 8i)); - assert!(m.insert(5i, 14i)); + assert!(m.insert(1i, 12i).is_none()); + assert!(m.insert(2i, 8i).is_none()); + assert!(m.insert(5i, 14i).is_none()); let new = 100; - match m.find_mut(&5) { + match m.get_mut(&5) { None => panic!(), Some(x) => *x = new } - assert_eq!(m.find(&5), Some(&new)); + assert_eq!(m.get(&5), Some(&new)); } #[test] fn test_insert_overwrite() { let mut m = HashMap::new(); - assert!(m.insert(1i, 2i)); - assert_eq!(*m.find(&1).unwrap(), 2); - assert!(!m.insert(1i, 3i)); - assert_eq!(*m.find(&1).unwrap(), 3); + assert!(m.insert(1i, 2i).is_none()); + assert_eq!(*m.get(&1).unwrap(), 2); + assert!(!m.insert(1i, 3i).is_none()); + assert_eq!(*m.get(&1).unwrap(), 3); } #[test] fn test_insert_conflicts() { let mut m = HashMap::with_capacity(4); - assert!(m.insert(1i, 2i)); - assert!(m.insert(5i, 3i)); - assert!(m.insert(9i, 4i)); - assert_eq!(*m.find(&9).unwrap(), 4); - assert_eq!(*m.find(&5).unwrap(), 3); - assert_eq!(*m.find(&1).unwrap(), 2); + assert!(m.insert(1i, 2i).is_none()); + assert!(m.insert(5i, 3i).is_none()); + assert!(m.insert(9i, 4i).is_none()); + assert_eq!(*m.get(&9).unwrap(), 4); + assert_eq!(*m.get(&5).unwrap(), 3); + assert_eq!(*m.get(&1).unwrap(), 2); } #[test] fn test_conflict_remove() { let mut m = HashMap::with_capacity(4); - assert!(m.insert(1i, 2i)); - assert_eq!(*m.find(&1).unwrap(), 2); - assert!(m.insert(5, 3)); - assert_eq!(*m.find(&1).unwrap(), 2); - assert_eq!(*m.find(&5).unwrap(), 3); - assert!(m.insert(9, 4)); - assert_eq!(*m.find(&1).unwrap(), 2); - assert_eq!(*m.find(&5).unwrap(), 3); - assert_eq!(*m.find(&9).unwrap(), 4); - assert!(m.remove(&1)); - assert_eq!(*m.find(&9).unwrap(), 4); - assert_eq!(*m.find(&5).unwrap(), 3); + assert!(m.insert(1i, 2i).is_none()); + assert_eq!(*m.get(&1).unwrap(), 2); + assert!(m.insert(5, 3).is_none()); + assert_eq!(*m.get(&1).unwrap(), 2); + assert_eq!(*m.get(&5).unwrap(), 3); + assert!(m.insert(9, 4).is_none()); + assert_eq!(*m.get(&1).unwrap(), 2); + assert_eq!(*m.get(&5).unwrap(), 3); + assert_eq!(*m.get(&9).unwrap(), 4); + assert!(m.remove(&1).is_some()); + assert_eq!(*m.get(&9).unwrap(), 4); + assert_eq!(*m.get(&5).unwrap(), 3); } #[test] fn test_is_empty() { let mut m = HashMap::with_capacity(4); - assert!(m.insert(1i, 2i)); + assert!(m.insert(1i, 2i).is_none()); assert!(!m.is_empty()); - assert!(m.remove(&1)); + assert!(m.remove(&1).is_some()); assert!(m.is_empty()); } @@ -1808,8 +1781,8 @@ mod test_map { fn test_pop() { let mut m = HashMap::new(); m.insert(1i, 2i); - assert_eq!(m.pop(&1), Some(2)); - assert_eq!(m.pop(&1), None); + assert_eq!(m.remove(&1), Some(2)); + assert_eq!(m.remove(&1), None); } #[test] @@ -1822,18 +1795,10 @@ mod test_map { } #[test] - fn test_swap() { - let mut m = HashMap::new(); - assert_eq!(m.swap(1i, 2i), None); - assert_eq!(m.swap(1i, 3i), Some(2)); - assert_eq!(m.swap(1i, 4i), Some(3)); - } - - #[test] fn test_iterate() { let mut m = HashMap::with_capacity(4); for i in range(0u, 32) { - assert!(m.insert(i, i*2)); + assert!(m.insert(i, i*2).is_none()); } assert_eq!(m.len(), 32); @@ -1871,9 +1836,9 @@ mod test_map { #[test] fn test_find() { let mut m = HashMap::new(); - assert!(m.find(&1i).is_none()); + assert!(m.get(&1i).is_none()); m.insert(1i, 2i); - match m.find(&1) { + match m.get(&1) { None => panic!(), Some(v) => assert_eq!(*v, 2) } @@ -1882,7 +1847,7 @@ mod test_map { #[test] fn test_find_copy() { let mut m = HashMap::new(); - assert!(m.find(&1i).is_none()); + assert!(m.get(&1i).is_none()); for i in range(1i, 10000) { m.insert(i, i + 7); @@ -2026,7 +1991,7 @@ mod test_map { let map: HashMap<int, int> = xs.iter().map(|&x| x).collect(); for &(k, v) in xs.iter() { - assert_eq!(map.find(&k), Some(&v)); + assert_eq!(map.get(&k), Some(&v)); } } @@ -2093,7 +2058,7 @@ mod test_map { assert_eq!(view.set(100), 10); } } - assert_eq!(map.find(&1).unwrap(), &100); + assert_eq!(map.get(&1).unwrap(), &100); assert_eq!(map.len(), 6); @@ -2106,7 +2071,7 @@ mod test_map { *v = new_v; } } - assert_eq!(map.find(&2).unwrap(), &200); + assert_eq!(map.get(&2).unwrap(), &200); assert_eq!(map.len(), 6); // Existing key (take) @@ -2116,7 +2081,7 @@ mod test_map { assert_eq!(view.take(), 30); } } - assert_eq!(map.find(&3), None); + assert_eq!(map.get(&3), None); assert_eq!(map.len(), 5); @@ -2127,7 +2092,7 @@ mod test_map { assert_eq!(*view.set(1000), 1000); } } - assert_eq!(map.find(&10).unwrap(), &1000); + assert_eq!(map.get(&10).unwrap(), &1000); assert_eq!(map.len(), 6); } } diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs index 688036d22dd..45574deec41 100644 --- a/src/libstd/collections/hash/set.rs +++ b/src/libstd/collections/hash/set.rs @@ -23,6 +23,9 @@ use result::{Ok, Err}; use super::map::{HashMap, Entries, MoveEntries, INITIAL_CAPACITY}; +// FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub +// FIXME(conventions): update capacity management to match other collections (no auto-shrink) + // Future Optimization (FIXME!) // ============================= @@ -103,6 +106,7 @@ impl<T: Hash + Eq> HashSet<T, RandomSipHasher> { /// let mut set: HashSet<int> = HashSet::new(); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new() -> HashSet<T, RandomSipHasher> { HashSet::with_capacity(INITIAL_CAPACITY) } @@ -117,6 +121,7 @@ impl<T: Hash + Eq> HashSet<T, RandomSipHasher> { /// let mut set: HashSet<int> = HashSet::with_capacity(10); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn with_capacity(capacity: uint) -> HashSet<T, RandomSipHasher> { HashSet { map: HashMap::with_capacity(capacity) } } @@ -240,16 +245,11 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// println!("{}", x); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn iter<'a>(&'a self) -> SetItems<'a, T> { self.map.keys() } - /// Deprecated: use `into_iter`. - #[deprecated = "use into_iter"] - pub fn move_iter(self) -> SetMoveItems<T> { - self.into_iter() - } - /// Creates a consuming iterator, that is, one that moves each value out /// of the set in arbitrary order. The set cannot be used after calling /// this. @@ -270,6 +270,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// println!("{}", x); /// } /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn into_iter(self) -> SetMoveItems<T> { self.map.into_iter().map(|(k, _)| k) } @@ -296,6 +297,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// let diff: HashSet<int> = b.difference(&a).map(|&x| x).collect(); /// assert_eq!(diff, [4i].iter().map(|&x| x).collect()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn difference<'a>(&'a self, other: &'a HashSet<T, H>) -> SetAlgebraItems<'a, T, H> { Repeat::new(other).zip(self.iter()) .filter_map(|(other, elt)| { @@ -323,6 +325,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// assert_eq!(diff1, diff2); /// assert_eq!(diff1, [1i, 4].iter().map(|&x| x).collect()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, H>) -> Chain<SetAlgebraItems<'a, T, H>, SetAlgebraItems<'a, T, H>> { self.difference(other).chain(other.difference(self)) @@ -345,6 +348,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// let diff: HashSet<int> = a.intersection(&b).map(|&x| x).collect(); /// assert_eq!(diff, [2i, 3].iter().map(|&x| x).collect()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn intersection<'a>(&'a self, other: &'a HashSet<T, H>) -> SetAlgebraItems<'a, T, H> { Repeat::new(other).zip(self.iter()) @@ -370,6 +374,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// let diff: HashSet<int> = a.union(&b).map(|&x| x).collect(); /// assert_eq!(diff, [1i, 2, 3, 4].iter().map(|&x| x).collect()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn union<'a>(&'a self, other: &'a HashSet<T, H>) -> Chain<SetItems<'a, T>, SetAlgebraItems<'a, T, H>> { self.iter().chain(other.difference(self)) @@ -387,6 +392,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// v.insert(1u); /// assert_eq!(v.len(), 1); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.map.len() } /// Returns true if the set contains no elements @@ -401,6 +407,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// v.insert(1u); /// assert!(!v.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.map.len() == 0 } /// Clears the set, removing all values. @@ -415,6 +422,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// v.clear(); /// assert!(v.is_empty()); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { self.map.clear() } /// Returns `true` if the set contains a value. @@ -428,6 +436,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// assert_eq!(set.contains(&1), true); /// assert_eq!(set.contains(&4), false); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn contains(&self, value: &T) -> bool { self.map.contains_key(value) } /// Returns `true` if the set has no elements in common with `other`. @@ -447,6 +456,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// b.insert(1); /// assert_eq!(a.is_disjoint(&b), false); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_disjoint(&self, other: &HashSet<T, H>) -> bool { self.iter().all(|v| !other.contains(v)) } @@ -467,6 +477,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// set.insert(4); /// assert_eq!(set.is_subset(&sup), false); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_subset(&self, other: &HashSet<T, H>) -> bool { self.iter().all(|v| other.contains(v)) } @@ -491,6 +502,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// assert_eq!(set.is_superset(&sub), true); /// ``` #[inline] + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_superset(&self, other: &HashSet<T, H>) -> bool { other.is_subset(self) } @@ -509,7 +521,8 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// assert_eq!(set.insert(2), false); /// assert_eq!(set.len(), 1); /// ``` - pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) } + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() } /// Removes a value from the set. Returns `true` if the value was /// present in the set. @@ -525,7 +538,8 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { /// assert_eq!(set.remove(&2), true); /// assert_eq!(set.remove(&2), false); /// ``` - pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value) } + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value).is_some() } } impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> { diff --git a/src/libstd/collections/lru_cache.rs b/src/libstd/collections/lru_cache.rs index 93e649f9355..aab0924e7e4 100644 --- a/src/libstd/collections/lru_cache.rs +++ b/src/libstd/collections/lru_cache.rs @@ -20,20 +20,20 @@ //! use std::collections::LruCache; //! //! let mut cache: LruCache<int, int> = LruCache::new(2); -//! cache.put(1, 10); -//! cache.put(2, 20); -//! cache.put(3, 30); +//! cache.insert(1, 10); +//! cache.insert(2, 20); +//! cache.insert(3, 30); //! assert!(cache.get(&1).is_none()); //! assert_eq!(*cache.get(&2).unwrap(), 20); //! assert_eq!(*cache.get(&3).unwrap(), 30); //! -//! cache.put(2, 22); +//! cache.insert(2, 22); //! assert_eq!(*cache.get(&2).unwrap(), 22); //! -//! cache.put(6, 60); +//! cache.insert(6, 60); //! assert!(cache.get(&3).is_none()); //! -//! cache.change_capacity(1); +//! cache.set_capacity(1); //! assert!(cache.get(&2).is_none()); //! ``` @@ -49,6 +49,9 @@ use boxed::Box; use ptr; use result::{Ok, Err}; +// FIXME(conventions): implement iterators? +// FIXME(conventions): implement indexing? + struct KeyRef<K> { k: *const K } struct LruEntry<K, V> { @@ -99,6 +102,7 @@ impl<K: Hash + Eq, V> LruCache<K, V> { /// use std::collections::LruCache; /// let mut cache: LruCache<int, &str> = LruCache::new(10); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn new(capacity: uint) -> LruCache<K, V> { let cache = LruCache { map: HashMap::new(), @@ -112,7 +116,14 @@ impl<K: Hash + Eq, V> LruCache<K, V> { return cache; } - /// Put a key-value pair into cache. + /// Deprecated: Replaced with `insert`. + #[deprecated = "Replaced with `insert`"] + pub fn put(&mut self, k: K, v: V) { + self.insert(k, v); + } + + /// Inserts a key-value pair into the cache. If the key already existed, the old value is + /// returned. /// /// # Example /// @@ -120,22 +131,23 @@ impl<K: Hash + Eq, V> LruCache<K, V> { /// use std::collections::LruCache; /// let mut cache = LruCache::new(2); /// - /// cache.put(1i, "a"); - /// cache.put(2, "b"); + /// cache.insert(1i, "a"); + /// cache.insert(2, "b"); /// assert_eq!(cache.get(&1), Some(&"a")); /// assert_eq!(cache.get(&2), Some(&"b")); /// ``` - pub fn put(&mut self, k: K, v: V) { - let (node_ptr, node_opt) = match self.map.find_mut(&KeyRef{k: &k}) { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn insert(&mut self, k: K, v: V) -> Option<V> { + let (node_ptr, node_opt, old_val) = match self.map.get_mut(&KeyRef{k: &k}) { Some(node) => { - node.value = v; + let old_val = mem::replace(&mut node.value, v); let node_ptr: *mut LruEntry<K, V> = &mut **node; - (node_ptr, None) + (node_ptr, None, Some(old_val)) } None => { let mut node = box LruEntry::new(k, v); let node_ptr: *mut LruEntry<K, V> = &mut *node; - (node_ptr, Some(node)) + (node_ptr, Some(node), None) } }; match node_opt { @@ -146,13 +158,14 @@ impl<K: Hash + Eq, V> LruCache<K, V> { } Some(node) => { let keyref = unsafe { &(*node_ptr).key }; - self.map.swap(KeyRef{k: keyref}, node); + self.map.insert(KeyRef{k: keyref}, node); self.attach(node_ptr); if self.len() > self.capacity() { self.remove_lru(); } } } + old_val } /// Return a value corresponding to the key in the cache. @@ -163,16 +176,17 @@ impl<K: Hash + Eq, V> LruCache<K, V> { /// use std::collections::LruCache; /// let mut cache = LruCache::new(2); /// - /// cache.put(1i, "a"); - /// cache.put(2, "b"); - /// cache.put(2, "c"); - /// cache.put(3, "d"); + /// cache.insert(1i, "a"); + /// cache.insert(2, "b"); + /// cache.insert(2, "c"); + /// cache.insert(3, "d"); /// /// assert_eq!(cache.get(&1), None); /// assert_eq!(cache.get(&2), Some(&"c")); /// ``` - pub fn get<'a>(&'a mut self, k: &K) -> Option<&'a V> { - let (value, node_ptr_opt) = match self.map.find_mut(&KeyRef{k: k}) { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn get(&mut self, k: &K) -> Option<&V> { + let (value, node_ptr_opt) = match self.map.get_mut(&KeyRef{k: k}) { None => (None, None), Some(node) => { let node_ptr: *mut LruEntry<K, V> = &mut **node; @@ -189,6 +203,12 @@ impl<K: Hash + Eq, V> LruCache<K, V> { return value; } + /// Deprecated: Renamed to `remove`. + #[deprecated = "Renamed to `remove`"] + pub fn pop(&mut self, k: &K) -> Option<V> { + self.remove(k) + } + /// Remove and return a value corresponding to the key from the cache. /// /// # Example @@ -197,15 +217,16 @@ impl<K: Hash + Eq, V> LruCache<K, V> { /// use std::collections::LruCache; /// let mut cache = LruCache::new(2); /// - /// cache.put(2i, "a"); + /// cache.insert(2i, "a"); /// - /// assert_eq!(cache.pop(&1), None); - /// assert_eq!(cache.pop(&2), Some("a")); - /// assert_eq!(cache.pop(&2), None); + /// assert_eq!(cache.remove(&1), None); + /// assert_eq!(cache.remove(&2), Some("a")); + /// assert_eq!(cache.remove(&2), None); /// assert_eq!(cache.len(), 0); /// ``` - pub fn pop(&mut self, k: &K) -> Option<V> { - match self.map.pop(&KeyRef{k: k}) { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn remove(&mut self, k: &K) -> Option<V> { + match self.map.remove(&KeyRef{k: k}) { None => None, Some(lru_entry) => Some(lru_entry.value) } @@ -220,10 +241,17 @@ impl<K: Hash + Eq, V> LruCache<K, V> { /// let mut cache: LruCache<int, &str> = LruCache::new(2); /// assert_eq!(cache.capacity(), 2); /// ``` + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn capacity(&self) -> uint { self.max_size } + /// Deprecated: Renamed to `set_capacity`. + #[deprecated = "Renamed to `set_capacity`"] + pub fn change_capacity(&mut self, capacity: uint) { + self.set_capacity(capacity) + } + /// Change the number of key-value pairs the cache can hold. Remove /// least-recently-used key-value pairs if necessary. /// @@ -233,29 +261,30 @@ impl<K: Hash + Eq, V> LruCache<K, V> { /// use std::collections::LruCache; /// let mut cache = LruCache::new(2); /// - /// cache.put(1i, "a"); - /// cache.put(2, "b"); - /// cache.put(3, "c"); + /// cache.insert(1i, "a"); + /// cache.insert(2, "b"); + /// cache.insert(3, "c"); /// /// assert_eq!(cache.get(&1), None); /// assert_eq!(cache.get(&2), Some(&"b")); /// assert_eq!(cache.get(&3), Some(&"c")); /// - /// cache.change_capacity(3); - /// cache.put(1i, "a"); - /// cache.put(2, "b"); + /// cache.set_capacity(3); + /// cache.insert(1i, "a"); + /// cache.insert(2, "b"); /// /// assert_eq!(cache.get(&1), Some(&"a")); /// assert_eq!(cache.get(&2), Some(&"b")); /// assert_eq!(cache.get(&3), Some(&"c")); /// - /// cache.change_capacity(1); + /// cache.set_capacity(1); /// /// assert_eq!(cache.get(&1), None); /// assert_eq!(cache.get(&2), None); /// assert_eq!(cache.get(&3), Some(&"c")); /// ``` - pub fn change_capacity(&mut self, capacity: uint) { + #[unstable = "matches collection reform specification, waiting for dust to settle"] + pub fn set_capacity(&mut self, capacity: uint) { for _ in range(capacity, self.len()) { self.remove_lru(); } @@ -267,7 +296,7 @@ impl<K: Hash + Eq, V> LruCache<K, V> { if self.len() > 0 { let lru = unsafe { (*self.head).prev }; self.detach(lru); - self.map.pop(&KeyRef{k: unsafe { &(*lru).key }}); + self.map.remove(&KeyRef{k: unsafe { &(*lru).key }}); } } @@ -290,12 +319,15 @@ impl<K: Hash + Eq, V> LruCache<K, V> { } /// Return the number of key-value pairs in the cache. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn len(&self) -> uint { self.map.len() } /// Returns whether the cache is currently empty. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn is_empty(&self) -> bool { self.len() == 0 } /// Clear the cache of all key-value pairs. + #[unstable = "matches collection reform specification, waiting for dust to settle"] pub fn clear(&mut self) { self.map.clear(); } } @@ -347,8 +379,8 @@ mod tests { #[test] fn test_put_and_get() { let mut cache: LruCache<int, int> = LruCache::new(2); - cache.put(1, 10); - cache.put(2, 20); + cache.insert(1, 10); + cache.insert(2, 20); assert_opt_eq(cache.get(&1), 10); assert_opt_eq(cache.get(&2), 20); assert_eq!(cache.len(), 2); @@ -357,8 +389,8 @@ mod tests { #[test] fn test_put_update() { let mut cache: LruCache<String, Vec<u8>> = LruCache::new(1); - cache.put("1".to_string(), vec![10, 10]); - cache.put("1".to_string(), vec![10, 19]); + cache.insert("1".to_string(), vec![10, 10]); + cache.insert("1".to_string(), vec![10, 19]); assert_opt_eq(cache.get(&"1".to_string()), vec![10, 19]); assert_eq!(cache.len(), 1); } @@ -366,22 +398,22 @@ mod tests { #[test] fn test_expire_lru() { let mut cache: LruCache<String, String> = LruCache::new(2); - cache.put("foo1".to_string(), "bar1".to_string()); - cache.put("foo2".to_string(), "bar2".to_string()); - cache.put("foo3".to_string(), "bar3".to_string()); + cache.insert("foo1".to_string(), "bar1".to_string()); + cache.insert("foo2".to_string(), "bar2".to_string()); + cache.insert("foo3".to_string(), "bar3".to_string()); assert!(cache.get(&"foo1".to_string()).is_none()); - cache.put("foo2".to_string(), "bar2update".to_string()); - cache.put("foo4".to_string(), "bar4".to_string()); + cache.insert("foo2".to_string(), "bar2update".to_string()); + cache.insert("foo4".to_string(), "bar4".to_string()); assert!(cache.get(&"foo3".to_string()).is_none()); } #[test] fn test_pop() { let mut cache: LruCache<int, int> = LruCache::new(2); - cache.put(1, 10); - cache.put(2, 20); + cache.insert(1, 10); + cache.insert(2, 20); assert_eq!(cache.len(), 2); - let opt1 = cache.pop(&1); + let opt1 = cache.remove(&1); assert!(opt1.is_some()); assert_eq!(opt1.unwrap(), 10); assert!(cache.get(&1).is_none()); @@ -392,9 +424,9 @@ mod tests { fn test_change_capacity() { let mut cache: LruCache<int, int> = LruCache::new(2); assert_eq!(cache.capacity(), 2); - cache.put(1, 10); - cache.put(2, 20); - cache.change_capacity(1); + cache.insert(1, 10); + cache.insert(2, 20); + cache.set_capacity(1); assert!(cache.get(&1).is_none()); assert_eq!(cache.capacity(), 1); } @@ -402,25 +434,25 @@ mod tests { #[test] fn test_to_string() { let mut cache: LruCache<int, int> = LruCache::new(3); - cache.put(1, 10); - cache.put(2, 20); - cache.put(3, 30); + cache.insert(1, 10); + cache.insert(2, 20); + cache.insert(3, 30); assert_eq!(cache.to_string(), "{3: 30, 2: 20, 1: 10}".to_string()); - cache.put(2, 22); + cache.insert(2, 22); assert_eq!(cache.to_string(), "{2: 22, 3: 30, 1: 10}".to_string()); - cache.put(6, 60); + cache.insert(6, 60); assert_eq!(cache.to_string(), "{6: 60, 2: 22, 3: 30}".to_string()); cache.get(&3); assert_eq!(cache.to_string(), "{3: 30, 6: 60, 2: 22}".to_string()); - cache.change_capacity(2); + cache.set_capacity(2); assert_eq!(cache.to_string(), "{3: 30, 6: 60}".to_string()); } #[test] fn test_clear() { let mut cache: LruCache<int, int> = LruCache::new(2); - cache.put(1, 10); - cache.put(2, 20); + cache.insert(1, 10); + cache.insert(2, 20); cache.clear(); assert!(cache.get(&1).is_none()); assert!(cache.get(&2).is_none()); diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs index 13486d4b8f8..3419a3d98a1 100644 --- a/src/libstd/collections/mod.rs +++ b/src/libstd/collections/mod.rs @@ -278,7 +278,7 @@ //! } //! } //! -//! assert_eq!(count.find(&'s'), Some(&8)); +//! assert_eq!(count.get(&'s'), Some(&8)); //! //! println!("Number of occurences of each character"); //! for (char, count) in count.iter() { |