diff options
73 files changed, 2462 insertions, 1569 deletions
diff --git a/src/libcollections/bench.rs b/src/libcollections/bench.rs new file mode 100644 index 00000000000..a212f22f899 --- /dev/null +++ b/src/libcollections/bench.rs @@ -0,0 +1,88 @@ +// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use std::prelude::*; +use std::rand; +use std::rand::Rng; +use test::Bencher; + +pub fn insert_rand_n<M>(n: uint, map: &mut M, b: &mut Bencher, + insert: |&mut M, uint|, + remove: |&mut M, uint|) { + // setup + let mut rng = rand::weak_rng(); + + for _ in range(0, n) { + insert(map, rng.gen::<uint>() % n); + } + + // measure + b.iter(|| { + let k = rng.gen::<uint>() % n; + insert(map, k); + remove(map, k); + }) +} + +pub fn insert_seq_n<M>(n: uint, map: &mut M, b: &mut Bencher, + insert: |&mut M, uint|, + remove: |&mut M, uint|) { + // setup + for i in range(0u, n) { + insert(map, i * 2); + } + + // measure + let mut i = 1; + b.iter(|| { + insert(map, i); + remove(map, i); + i = (i + 2) % n; + }) +} + +pub fn find_rand_n<M, T>(n: uint, map: &mut M, b: &mut Bencher, + insert: |&mut M, uint|, + find: |&M, uint| -> T) { + // setup + let mut rng = rand::weak_rng(); + let mut keys = Vec::from_fn(n, |_| rng.gen::<uint>() % n); + + for k in keys.iter() { + insert(map, *k); + } + + rng.shuffle(keys.as_mut_slice()); + + // measure + let mut i = 0; + b.iter(|| { + let t = find(map, keys[i]); + i = (i + 1) % n; + t + }) +} + +pub fn find_seq_n<M, T>(n: uint, map: &mut M, b: &mut Bencher, + insert: |&mut M, uint|, + find: |&M, uint| -> T) { + // setup + for i in range(0u, n) { + insert(map, i); + } + + // measure + let mut i = 0; + b.iter(|| { + let x = find(map, i); + i = (i + 1) % n; + x + }) +} diff --git a/src/libcollections/bitv.rs b/src/libcollections/bitv.rs index 1b12fdcb8dc..26e0c73724c 100644 --- a/src/libcollections/bitv.rs +++ b/src/libcollections/bitv.rs @@ -70,7 +70,6 @@ use core::slice; use core::u32; use std::hash; -use {Mutable, Set, MutableSet, MutableSeq}; use vec::Vec; type MatchWords<'a> = Chain<MaskWords<'a>, Skip<Take<Enumerate<Repeat<u32>>>>>; @@ -755,6 +754,20 @@ impl Bitv { } self.set(insert_pos, elem); } + + /// Return the total number of bits in this vector + #[inline] + pub fn len(&self) -> uint { self.nbits } + + /// Returns true if there are no bits in this vector + #[inline] + pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Clears all bits in this vector. + #[inline] + pub fn clear(&mut self) { + for w in self.storage.iter_mut() { *w = 0u32; } + } } /// Transforms a byte-vector into a `Bitv`. Each byte becomes eight bits, @@ -804,18 +817,6 @@ impl Default for Bitv { fn default() -> Bitv { Bitv::new() } } -impl Collection for Bitv { - #[inline] - fn len(&self) -> uint { self.nbits } -} - -impl Mutable for Bitv { - #[inline] - fn clear(&mut self) { - for w in self.storage.iter_mut() { *w = 0u32; } - } -} - impl FromIterator<bool> for Bitv { fn from_iter<I:Iterator<bool>>(iterator: I) -> Bitv { let mut ret = Bitv::new(); @@ -1466,61 +1467,45 @@ impl BitvSet { pub fn symmetric_difference_with(&mut self, other: &BitvSet) { self.other_op(other, |w1, w2| w1 ^ w2); } -} - -impl fmt::Show for BitvSet { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { - try!(write!(fmt, "{{")); - let mut first = true; - for n in self.iter() { - if !first { - try!(write!(fmt, ", ")); - } - try!(write!(fmt, "{}", n)); - first = false; - } - write!(fmt, "}}") - } -} -impl<S: hash::Writer> hash::Hash<S> for BitvSet { - fn hash(&self, state: &mut S) { - for pos in self.iter() { - pos.hash(state); - } + /// Return the number of set bits in this set. + #[inline] + pub fn len(&self) -> uint { + let &BitvSet(ref bitv) = self; + bitv.storage.iter().fold(0, |acc, &n| acc + n.count_ones()) } -} -impl Collection for BitvSet { + /// Returns whether there are no bits set in this set #[inline] - fn len(&self) -> uint { + pub fn is_empty(&self) -> bool { let &BitvSet(ref bitv) = self; - bitv.storage.iter().fold(0, |acc, &n| acc + n.count_ones()) + bitv.storage.iter().all(|&n| n == 0) } -} -impl Mutable for BitvSet { + /// Clears all bits in this set #[inline] - fn clear(&mut self) { + pub fn clear(&mut self) { let &BitvSet(ref mut bitv) = self; bitv.clear(); } -} -impl Set<uint> for BitvSet { + /// Returns `true` if this set contains the specified integer. #[inline] - fn contains(&self, value: &uint) -> bool { + pub fn contains(&self, value: &uint) -> bool { let &BitvSet(ref bitv) = self; *value < bitv.nbits && bitv.get(*value) } + /// Returns `true` if the set has no elements in common with `other`. + /// This is equivalent to checking for an empty intersection. #[inline] - fn is_disjoint(&self, other: &BitvSet) -> bool { + 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] - fn is_subset(&self, other: &BitvSet) -> bool { + pub fn is_subset(&self, other: &BitvSet) -> bool { let &BitvSet(ref self_bitv) = self; let &BitvSet(ref other_bitv) = other; @@ -1531,14 +1516,15 @@ impl Set<uint> for BitvSet { self_bitv.mask_words(other_bitv.storage.len()).all(|(_, w)| w == 0) } + /// Returns `true` if the set is a superset of another. #[inline] - fn is_superset(&self, other: &BitvSet) -> bool { + pub fn is_superset(&self, other: &BitvSet) -> bool { other.is_subset(self) } -} -impl MutableSet<uint> for BitvSet { - fn insert(&mut self, value: uint) -> bool { + /// Adds a value to the set. Returns `true` if the value was not already + /// present in the set. + pub fn insert(&mut self, value: uint) -> bool { if self.contains(&value) { return false; } @@ -1554,7 +1540,9 @@ impl MutableSet<uint> for BitvSet { return true; } - fn remove(&mut self, value: &uint) -> bool { + /// Removes a value from the set. Returns `true` if the value was + /// present in the set. + pub fn remove(&mut self, value: &uint) -> bool { if !self.contains(value) { return false; } @@ -1564,6 +1552,29 @@ impl MutableSet<uint> for BitvSet { } } +impl fmt::Show for BitvSet { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + try!(write!(fmt, "{{")); + let mut first = true; + for n in self.iter() { + if !first { + try!(write!(fmt, ", ")); + } + try!(write!(fmt, "{}", n)); + first = false; + } + write!(fmt, "}}") + } +} + +impl<S: hash::Writer> hash::Hash<S> for BitvSet { + fn hash(&self, state: &mut S) { + for pos in self.iter() { + pos.hash(state); + } + } +} + /// An iterator for `BitvSet`. pub struct BitPositions<'a> { set: &'a BitvSet, @@ -1643,7 +1654,6 @@ mod tests { use std::rand::Rng; use test::Bencher; - use {Set, Mutable, MutableSet, MutableSeq}; use bitv::{Bitv, BitvSet, from_fn, from_bytes}; use bitv; use vec::Vec; diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs index dc7d935619f..4570d49ba0a 100644 --- a/src/libcollections/btree/map.rs +++ b/src/libcollections/btree/map.rs @@ -23,11 +23,8 @@ use core::default::Default; use core::{iter, fmt, mem}; use core::fmt::Show; -use {Deque, Map, MutableMap, Mutable, MutableSeq}; use ringbuf::RingBuf; - - /// A map based on a B-Tree. /// /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing @@ -145,9 +142,25 @@ impl<K: Ord, V> BTreeMap<K, V> { b: b, } } -} -impl<K: Ord, V> Map<K, V> for BTreeMap<K, V> { + /// Clears the map, removing all values. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// a.insert(1u, "a"); + /// a.clear(); + /// assert!(a.is_empty()); + /// ``` + 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() {}; + } + // 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. @@ -155,7 +168,20 @@ impl<K: Ord, V> Map<K, V> for BTreeMap<K, V> { // the search key. If no such key exists (they're *all* smaller), then just take the last // edge in the node. If we're in a leaf and we don't find our key, then it's not // in the tree. - fn find(&self, key: &K) -> Option<&V> { + + /// Returns a reference to the value corresponding to the key. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1u, "a"); + /// assert_eq!(map.find(&1), Some(&"a")); + /// assert_eq!(map.find(&2), None); + /// ``` + pub fn find(&self, key: &K) -> Option<&V> { let mut cur_node = &self.root; loop { match cur_node.search(key) { @@ -170,11 +196,41 @@ impl<K: Ord, V> Map<K, V> for BTreeMap<K, V> { } } } -} -impl<K: Ord, V> MutableMap<K, V> for BTreeMap<K, V> { + /// Returns true if the map contains a value for the specified key. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1u, "a"); + /// assert_eq!(map.contains_key(&1), true); + /// assert_eq!(map.contains_key(&2), false); + /// ``` + #[inline] + pub fn contains_key(&self, key: &K) -> bool { + self.find(key).is_some() + } + + /// Returns a mutable reference to the value corresponding to the key. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1u, "a"); + /// match map.find_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 - fn find_mut(&mut self, key: &K) -> Option<&mut V> { + pub fn find_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 { @@ -218,7 +274,23 @@ impl<K: Ord, V> MutableMap<K, V> for BTreeMap<K, V> { // 2) While ODS may potentially return the pair we *just* inserted after // the split, we will never do this. Again, this shouldn't effect the analysis. - fn swap(&mut self, key: K, mut value: V) -> Option<V> { + /// Inserts a key-value pair from the map. If the key already had a value + /// present in the map, that value is returned. Otherwise, `None` is returned. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// assert_eq!(map.swap(37u, "a"), None); + /// assert_eq!(map.is_empty(), false); + /// + /// map.insert(37, "b"); + /// assert_eq!(map.swap(37, "c"), Some("b")); + /// assert_eq!(map[37], "c"); + /// ``` + pub fn swap(&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 @@ -266,6 +338,25 @@ impl<K: Ord, V> MutableMap<K, V> for 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 @@ -301,7 +392,20 @@ impl<K: Ord, V> MutableMap<K, V> for 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. - fn pop(&mut self, key: &K) -> Option<V> { + /// Removes a key from the map, returning the value at the key if the key + /// was previously in the map. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut map = BTreeMap::new(); + /// map.insert(1u, "a"); + /// assert_eq!(map.pop(&1), Some("a")); + /// assert_eq!(map.pop(&1), None); + /// ``` + pub fn pop(&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 { @@ -322,6 +426,24 @@ impl<K: Ord, V> MutableMap<K, V> for 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 @@ -331,7 +453,6 @@ mod stack { use core::prelude::*; use super::BTreeMap; use super::super::node::*; - use {MutableMap, MutableSeq}; use vec::Vec; type StackItem<K, V> = (*mut Node<K, V>, uint); @@ -603,20 +724,6 @@ mod stack { } } -impl<K, V> Collection for BTreeMap<K, V> { - fn len(&self) -> uint { - self.length - } -} - -impl<K: Ord, V> Mutable for BTreeMap<K, V> { - 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() {}; - } -} - impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> { fn from_iter<T: Iterator<(K, V)>>(iter: T) -> BTreeMap<K, V> { let mut map = BTreeMap::new(); @@ -950,6 +1057,34 @@ impl<K, V> BTreeMap<K, V> { pub fn values<'a>(&'a self) -> Values<'a, K, V> { self.iter().map(|(_, v)| v) } + + /// Return the number of elements in the map. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// assert_eq!(a.len(), 0); + /// a.insert(1u, "a"); + /// assert_eq!(a.len(), 1); + /// ``` + pub fn len(&self) -> uint { self.length } + + /// Return true if the map contains no elements. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut a = BTreeMap::new(); + /// assert!(a.is_empty()); + /// a.insert(1u, "a"); + /// assert!(!a.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { self.len() == 0 } } impl<K: Ord, V> BTreeMap<K, V> { @@ -993,7 +1128,6 @@ impl<K: Ord, V> BTreeMap<K, V> { mod test { use std::prelude::*; - use {Map, MutableMap}; use super::{BTreeMap, Occupied, Vacant}; #[test] @@ -1199,58 +1333,73 @@ mod bench { use test::{Bencher, black_box}; use super::BTreeMap; - use MutableMap; - use deque::bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n}; + use bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n}; #[bench] pub fn insert_rand_100(b: &mut Bencher) { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); - insert_rand_n(100, &mut m, b); + insert_rand_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } #[bench] pub fn insert_rand_10_000(b: &mut Bencher) { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); - insert_rand_n(10_000, &mut m, b); + insert_rand_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } // Insert seq #[bench] pub fn insert_seq_100(b: &mut Bencher) { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); - insert_seq_n(100, &mut m, b); + insert_seq_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } #[bench] pub fn insert_seq_10_000(b: &mut Bencher) { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); - insert_seq_n(10_000, &mut m, b); + insert_seq_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } // Find rand #[bench] pub fn find_rand_100(b: &mut Bencher) { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); - find_rand_n(100, &mut m, b); + find_rand_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } #[bench] pub fn find_rand_10_000(b: &mut Bencher) { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); - find_rand_n(10_000, &mut m, b); + find_rand_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } // Find seq #[bench] pub fn find_seq_100(b: &mut Bencher) { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); - find_seq_n(100, &mut m, b); + find_seq_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } #[bench] pub fn find_seq_10_000(b: &mut Bencher) { let mut m : BTreeMap<uint,uint> = BTreeMap::new(); - find_seq_n(10_000, &mut m, b); + find_seq_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } fn bench_iter(b: &mut Bencher, size: uint) { diff --git a/src/libcollections/btree/node.rs b/src/libcollections/btree/node.rs index 6b491096e7d..a15d31ba284 100644 --- a/src/libcollections/btree/node.rs +++ b/src/libcollections/btree/node.rs @@ -15,7 +15,6 @@ use core::prelude::*; use core::{slice, mem, ptr}; use core::iter::Zip; -use MutableSeq; use vec; use vec::Vec; diff --git a/src/libcollections/btree/set.rs b/src/libcollections/btree/set.rs index 8958f0ef5be..eac74098758 100644 --- a/src/libcollections/btree/set.rs +++ b/src/libcollections/btree/set.rs @@ -20,8 +20,6 @@ use core::{iter, fmt}; use core::iter::Peekable; use core::fmt::Show; -use {Mutable, Set, MutableSet, MutableMap, Map}; - /// A set based on a B-Tree. /// /// See BTreeMap's documentation for a detailed discussion of this collection's performance @@ -109,30 +107,104 @@ impl<T: Ord> BTreeSet<T> { pub fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> UnionItems<'a, T> { UnionItems{a: self.iter().peekable(), b: other.iter().peekable()} } -} - -impl<T> Collection for BTreeSet<T> { - fn len(&self) -> uint { - self.map.len() - } -} -impl<T: Ord> Mutable for BTreeSet<T> { - fn clear(&mut self) { + /// Return the number of elements in the set + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut v = BTreeSet::new(); + /// assert_eq!(v.len(), 0); + /// v.insert(1i); + /// assert_eq!(v.len(), 1); + /// ``` + pub fn len(&self) -> uint { self.map.len() } + + /// Returns true if the set contains no elements + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut v = BTreeSet::new(); + /// assert!(v.is_empty()); + /// v.insert(1i); + /// assert!(!v.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Clears the set, removing all values. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut v = BTreeSet::new(); + /// v.insert(1i); + /// v.clear(); + /// assert!(v.is_empty()); + /// ``` + pub fn clear(&mut self) { self.map.clear() } -} -impl<T: Ord> Set<T> for BTreeSet<T> { - fn contains(&self, value: &T) -> bool { + /// Returns `true` if the set contains a value. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let set: BTreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); + /// assert_eq!(set.contains(&1), true); + /// assert_eq!(set.contains(&4), false); + /// ``` + pub fn contains(&self, value: &T) -> bool { self.map.find(value).is_some() } - fn is_disjoint(&self, other: &BTreeSet<T>) -> bool { + /// Returns `true` if the set has no elements in common with `other`. + /// This is equivalent to checking for an empty intersection. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let a: BTreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); + /// let mut b: BTreeSet<int> = BTreeSet::new(); + /// + /// assert_eq!(a.is_disjoint(&b), true); + /// b.insert(4); + /// assert_eq!(a.is_disjoint(&b), true); + /// b.insert(1); + /// assert_eq!(a.is_disjoint(&b), false); + /// ``` + pub fn is_disjoint(&self, other: &BTreeSet<T>) -> bool { self.intersection(other).next().is_none() } - fn is_subset(&self, other: &BTreeSet<T>) -> bool { + /// Returns `true` if the set is a subset of another. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let sup: BTreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); + /// let mut set: BTreeSet<int> = BTreeSet::new(); + /// + /// assert_eq!(set.is_subset(&sup), true); + /// set.insert(2); + /// assert_eq!(set.is_subset(&sup), true); + /// set.insert(4); + /// assert_eq!(set.is_subset(&sup), false); + /// ``` + pub fn is_subset(&self, other: &BTreeSet<T>) -> bool { // Stolen from TreeMap let mut x = self.iter(); let mut y = other.iter(); @@ -156,14 +228,63 @@ impl<T: Ord> Set<T> for BTreeSet<T> { } true } -} -impl<T: Ord> MutableSet<T> for BTreeSet<T>{ - fn insert(&mut self, value: T) -> bool { + /// Returns `true` if the set is a superset of another. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let sub: BTreeSet<int> = [1i, 2].iter().map(|&x| x).collect(); + /// let mut set: BTreeSet<int> = BTreeSet::new(); + /// + /// assert_eq!(set.is_superset(&sub), false); + /// + /// set.insert(0); + /// set.insert(1); + /// assert_eq!(set.is_superset(&sub), false); + /// + /// set.insert(2); + /// assert_eq!(set.is_superset(&sub), true); + /// ``` + pub fn is_superset(&self, other: &BTreeSet<T>) -> bool { + other.is_subset(self) + } + + /// Adds a value to the set. Returns `true` if the value was not already + /// present in the set. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut set = BTreeSet::new(); + /// + /// assert_eq!(set.insert(2i), true); + /// assert_eq!(set.insert(2i), false); + /// assert_eq!(set.len(), 1); + /// ``` + pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) } - fn remove(&mut self, value: &T) -> bool { + /// Removes a value from the set. Returns `true` if the value was + /// present in the set. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut set = BTreeSet::new(); + /// + /// set.insert(2i); + /// assert_eq!(set.remove(&2), true); + /// assert_eq!(set.remove(&2), false); + /// ``` + pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value) } } @@ -273,7 +394,6 @@ impl<'a, T: Ord> Iterator<&'a T> for UnionItems<'a, T> { mod test { use std::prelude::*; - use {Set, MutableSet}; use super::BTreeSet; use std::hash; diff --git a/src/libcollections/deque.rs b/src/libcollections/deque.rs deleted file mode 100644 index d7970ed8d60..00000000000 --- a/src/libcollections/deque.rs +++ /dev/null @@ -1,96 +0,0 @@ -// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -//! Container traits for collections. - -#[cfg(test)] -pub mod bench { - use std::prelude::*; - use std::rand; - use std::rand::Rng; - use test::Bencher; - use MutableMap; - - pub fn insert_rand_n<M: MutableMap<uint, uint>>(n: uint, - map: &mut M, - b: &mut Bencher) { - // setup - let mut rng = rand::weak_rng(); - - map.clear(); - for _ in range(0, n) { - map.insert(rng.gen::<uint>() % n, 1); - } - - // measure - b.iter(|| { - let k = rng.gen::<uint>() % n; - map.insert(k, 1); - map.remove(&k); - }) - } - - pub fn insert_seq_n<M: MutableMap<uint, uint>>(n: uint, - map: &mut M, - b: &mut Bencher) { - // setup - map.clear(); - for i in range(0u, n) { - map.insert(i*2, 1); - } - - // measure - let mut i = 1; - b.iter(|| { - map.insert(i, 1); - map.remove(&i); - i = (i + 2) % n; - }) - } - - pub fn find_rand_n<M:MutableMap<uint,uint>>(n: uint, - map: &mut M, - b: &mut Bencher) { - // setup - let mut rng = rand::weak_rng(); - let mut keys = Vec::from_fn(n, |_| rng.gen::<uint>() % n); - - for k in keys.iter() { - map.insert(*k, 1); - } - - rng.shuffle(keys.as_mut_slice()); - - // measure - let mut i = 0; - b.iter(|| { - map.find(&keys[i]); - i = (i + 1) % n; - }) - } - - pub fn find_seq_n<M:MutableMap<uint,uint>>(n: uint, - map: &mut M, - b: &mut Bencher) { - // setup - for i in range(0u, n) { - map.insert(i, 1); - } - - // measure - let mut i = 0; - b.iter(|| { - let x = map.find(&i); - i = (i + 1) % n; - x - }) - } -} - diff --git a/src/libcollections/dlist.rs b/src/libcollections/dlist.rs index 22d487bd3a0..a1e286d1245 100644 --- a/src/libcollections/dlist.rs +++ b/src/libcollections/dlist.rs @@ -31,8 +31,6 @@ use core::mem; use core::ptr; use std::hash::{Writer, Hash}; -use {Mutable, Deque, MutableSeq}; - /// A doubly-linked list. pub struct DList<T> { length: uint, @@ -129,34 +127,6 @@ fn link_with_prev<T>(mut next: Box<Node<T>>, prev: Rawlink<Node<T>>) Some(next) } -impl<T> Collection for DList<T> { - /// Returns `true` if the `DList` is empty. - /// - /// This operation should compute in O(1) time. - #[inline] - fn is_empty(&self) -> bool { - self.list_head.is_none() - } - - /// Returns the length of the `DList`. - /// - /// This operation should compute in O(1) time. - #[inline] - fn len(&self) -> uint { - self.length - } -} - -impl<T> Mutable for DList<T> { - /// Removes all elements from the `DList`. - /// - /// This operation should compute in O(n) time. - #[inline] - fn clear(&mut self) { - *self = DList::new() - } -} - // private methods impl<T> DList<T> { /// Add a Node first in the list @@ -217,60 +187,6 @@ impl<T> DList<T> { } } -impl<T> Deque<T> for DList<T> { - /// Provides a reference to the front element, or `None` if the list is - /// empty. - #[inline] - fn front<'a>(&'a self) -> Option<&'a 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] - fn front_mut<'a>(&'a mut self) -> Option<&'a 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] - fn back<'a>(&'a self) -> Option<&'a 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] - fn back_mut<'a>(&'a mut self) -> Option<&'a 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. - fn push_front(&mut self, elt: T) { - self.push_front_node(box Node::new(elt)) - } - - /// Removes the first element and returns it, or `None` if the list is - /// empty. - /// - /// This operation should compute in O(1) time. - fn pop_front(&mut self) -> Option<T> { - self.pop_front_node().map(|box Node{value, ..}| value) - } -} - -impl<T> MutableSeq<T> for DList<T> { - fn push(&mut self, elt: T) { - self.push_back_node(box Node::new(elt)) - } - fn pop(&mut self) -> Option<T> { - self.pop_back_node().map(|box Node{value, ..}| value) - } -} - impl<T> Default for DList<T> { #[inline] fn default() -> DList<T> { DList::new() } @@ -495,6 +411,107 @@ impl<T> DList<T> { pub fn into_iter(self) -> MoveItems<T> { MoveItems{list: self} } + + /// Returns `true` if the `DList` is empty. + /// + /// This operation should compute in O(1) time. + #[inline] + pub fn is_empty(&self) -> bool { + self.list_head.is_none() + } + + /// Returns the length of the `DList`. + /// + /// This operation should compute in O(1) time. + #[inline] + pub fn len(&self) -> uint { + self.length + } + + /// Removes all elements from the `DList`. + /// + /// This operation should compute in O(n) time. + #[inline] + pub fn clear(&mut self) { + *self = DList::new() + } + + /// Provides a reference to the front element, or `None` if the list is + /// empty. + #[inline] + pub fn front<'a>(&'a self) -> Option<&'a 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> { + 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> { + 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> { + self.list_tail.resolve().map(|tail| &mut tail.value) + } + + /// Adds an element first in the list. + /// + /// This operation should compute in O(1) time. + pub fn push_front(&mut self, elt: T) { + self.push_front_node(box Node::new(elt)) + } + + /// Removes the first element and returns it, or `None` if the list is + /// empty. + /// + /// This operation should compute in O(1) time. + pub fn pop_front(&mut self) -> Option<T> { + self.pop_front_node().map(|box Node{value, ..}| value) + } + + /// Appends an element to the back of a list + /// + /// # Example + /// + /// ```rust + /// use std::collections::DList; + /// + /// let mut d = DList::new(); + /// d.push(1i); + /// d.push(3); + /// assert_eq!(3, *d.back().unwrap()); + /// ``` + pub fn push(&mut self, elt: T) { + self.push_back_node(box Node::new(elt)) + } + + /// Removes the last element from a list and returns it, or `None` if + /// it is empty. + /// + /// # Example + /// + /// ```rust + /// 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)); + /// ``` + pub fn pop(&mut self) -> Option<T> { + self.pop_back_node().map(|box Node{value, ..}| value) + } } impl<T: Ord> DList<T> { @@ -745,7 +762,6 @@ mod tests { use test::Bencher; use test; - use {Deque, MutableSeq}; use super::{DList, Node, ListInsertion}; use vec::Vec; diff --git a/src/libcollections/enum_set.rs b/src/libcollections/enum_set.rs index f282549f6f9..b78c1897b06 100644 --- a/src/libcollections/enum_set.rs +++ b/src/libcollections/enum_set.rs @@ -157,8 +157,6 @@ mod test { use enum_set::{EnumSet, CLike}; - use MutableSeq; - #[deriving(PartialEq, Show)] #[repr(uint)] enum Foo { diff --git a/src/libcollections/hash/sip.rs b/src/libcollections/hash/sip.rs index 1f12065750b..dd105c44ad3 100644 --- a/src/libcollections/hash/sip.rs +++ b/src/libcollections/hash/sip.rs @@ -279,8 +279,6 @@ mod tests { use super::super::{Hash, Writer}; use super::{SipState, hash, hash_with_keys}; - use MutableSeq; - // Hash just the bytes of the slice, without length prefix struct Bytes<'a>(&'a [u8]); diff --git a/src/libcollections/lib.rs b/src/libcollections/lib.rs index 20ad5b6334f..e28bc766480 100644 --- a/src/libcollections/lib.rs +++ b/src/libcollections/lib.rs @@ -37,11 +37,8 @@ extern crate alloc; #[cfg(test)] #[phase(plugin, link)] extern crate std; #[cfg(test)] #[phase(plugin, link)] extern crate log; -use core::prelude::Option; - pub use bitv::{Bitv, BitvSet}; pub use btree::{BTreeMap, BTreeSet}; -pub use core::prelude::Collection; pub use dlist::DList; pub use enum_set::EnumSet; pub use priority_queue::PriorityQueue; @@ -69,457 +66,7 @@ pub mod string; pub mod vec; pub mod hash; -mod deque; - -/// A mutable container type. -pub trait Mutable: Collection { - /// Clears the container, removing all values. - /// - /// # Example - /// - /// ``` - /// let mut v = vec![1i, 2, 3]; - /// v.clear(); - /// assert!(v.is_empty()); - /// ``` - fn clear(&mut self); -} - -/// A key-value store where values may be looked up by their keys. This trait -/// provides basic operations to operate on these stores. -pub trait Map<K, V>: Collection { - /// Returns a reference to the value corresponding to the key. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1i); - /// assert_eq!(map.find(&"a"), Some(&1i)); - /// assert_eq!(map.find(&"b"), None); - /// ``` - fn find<'a>(&'a self, key: &K) -> Option<&'a V>; - - /// Returns true if the map contains a value for the specified key. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1i); - /// assert_eq!(map.contains_key(&"a"), true); - /// assert_eq!(map.contains_key(&"b"), false); - /// ``` - #[inline] - fn contains_key(&self, key: &K) -> bool { - self.find(key).is_some() - } -} - -/// A key-value store (map) where the values can be modified. -pub trait MutableMap<K, V>: Map<K, V> + Mutable { - /// 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("key", 2i), true); - /// assert_eq!(map.insert("key", 9i), false); - /// assert_eq!(map["key"], 9i); - /// ``` - #[inline] - 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(&"key"), false); - /// map.insert("key", 2i); - /// assert_eq!(map.remove(&"key"), true); - /// ``` - #[inline] - fn remove(&mut self, key: &K) -> bool { - self.pop(key).is_some() - } - - /// Inserts a key-value pair into the map. If the key already had a value - /// present in the map, that value is returned. Otherwise, `None` is - /// returned. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// assert_eq!(map.swap("a", 37i), None); - /// assert_eq!(map.is_empty(), false); - /// - /// map.insert("a", 1i); - /// assert_eq!(map.swap("a", 37i), Some(1i)); - /// assert_eq!(map["a"], 37i); - /// ``` - fn swap(&mut self, k: K, v: V) -> Option<V>; - - /// Removes a key from the map, returning the value at the key if the key - /// was previously in the map. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map: HashMap<&str, int> = HashMap::new(); - /// map.insert("a", 1i); - /// assert_eq!(map.pop(&"a"), Some(1i)); - /// assert_eq!(map.pop(&"a"), None); - /// ``` - fn pop(&mut self, k: &K) -> Option<V>; - - /// Returns a mutable reference to the value corresponding to the key. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashMap; - /// - /// let mut map = HashMap::new(); - /// map.insert("a", 1i); - /// match map.find_mut(&"a") { - /// Some(x) => *x = 7i, - /// None => (), - /// } - /// assert_eq!(map["a"], 7i); - /// ``` - fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V>; -} - -/// A group of objects which are each distinct from one another. This -/// trait represents actions which can be performed on sets to iterate over -/// them. -pub trait Set<T>: Collection { - /// Returns `true` if the set contains a value. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let set: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); - /// assert_eq!(set.contains(&1), true); - /// assert_eq!(set.contains(&4), false); - /// ``` - fn contains(&self, value: &T) -> bool; - - /// Returns `true` if the set has no elements in common with `other`. - /// This is equivalent to checking for an empty intersection. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); - /// let mut b: HashSet<int> = HashSet::new(); - /// - /// assert_eq!(a.is_disjoint(&b), true); - /// b.insert(4); - /// assert_eq!(a.is_disjoint(&b), true); - /// b.insert(1); - /// assert_eq!(a.is_disjoint(&b), false); - /// ``` - fn is_disjoint(&self, other: &Self) -> bool; - - /// Returns `true` if the set is a subset of another. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let sup: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); - /// let mut set: HashSet<int> = HashSet::new(); - /// - /// assert_eq!(set.is_subset(&sup), true); - /// set.insert(2); - /// assert_eq!(set.is_subset(&sup), true); - /// set.insert(4); - /// assert_eq!(set.is_subset(&sup), false); - /// ``` - fn is_subset(&self, other: &Self) -> bool; - - /// Returns `true` if the set is a superset of another. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let sub: HashSet<int> = [1i, 2].iter().map(|&x| x).collect(); - /// let mut set: HashSet<int> = HashSet::new(); - /// - /// assert_eq!(set.is_superset(&sub), false); - /// - /// set.insert(0); - /// set.insert(1); - /// assert_eq!(set.is_superset(&sub), false); - /// - /// set.insert(2); - /// assert_eq!(set.is_superset(&sub), true); - /// ``` - fn is_superset(&self, other: &Self) -> bool { - other.is_subset(self) - } - - // FIXME #8154: Add difference, sym. difference, intersection and union iterators -} - -/// A mutable collection of values which are distinct from one another that -/// can be mutated. -pub trait MutableSet<T>: Set<T> + Mutable { - /// Adds a value to the set. Returns `true` if the value was not already - /// present in the set. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut set = HashSet::new(); - /// - /// assert_eq!(set.insert(2i), true); - /// assert_eq!(set.insert(2i), false); - /// assert_eq!(set.len(), 1); - /// ``` - fn insert(&mut self, value: T) -> bool; - - /// Removes a value from the set. Returns `true` if the value was - /// present in the set. - /// - /// # Example - /// - /// ``` - /// use std::collections::HashSet; - /// - /// let mut set = HashSet::new(); - /// - /// set.insert(2i); - /// assert_eq!(set.remove(&2), true); - /// assert_eq!(set.remove(&2), false); - /// ``` - fn remove(&mut self, value: &T) -> bool; -} - -pub trait MutableSeq<T>: Mutable { - /// Appends an element to the back of a collection. - /// - /// # Example - /// - /// ```rust - /// let mut vec = vec!(1i, 2); - /// vec.push(3); - /// assert_eq!(vec, vec!(1, 2, 3)); - /// ``` - fn push(&mut self, t: T); - - /// Removes the last element from a collection and returns it, or `None` if - /// it is empty. - /// - /// # Example - /// - /// ```rust - /// let mut vec = vec!(1i, 2, 3); - /// assert_eq!(vec.pop(), Some(3)); - /// assert_eq!(vec, vec!(1, 2)); - /// ``` - fn pop(&mut self) -> Option<T>; -} - -/// A double-ended sequence that allows querying, insertion and deletion at both -/// ends. -/// -/// # Example -/// -/// With a `Deque` we can simulate a queue efficiently: -/// -/// ``` -/// use std::collections::{RingBuf, Deque}; -/// -/// let mut queue = RingBuf::new(); -/// queue.push(1i); -/// queue.push(2i); -/// queue.push(3i); -/// -/// // Will print 1, 2, 3 -/// while !queue.is_empty() { -/// let x = queue.pop_front().unwrap(); -/// println!("{}", x); -/// } -/// ``` -/// -/// We can also simulate a stack: -/// -/// ``` -/// use std::collections::{RingBuf, Deque}; -/// -/// let mut stack = RingBuf::new(); -/// stack.push_front(1i); -/// stack.push_front(2i); -/// stack.push_front(3i); -/// -/// // Will print 3, 2, 1 -/// while !stack.is_empty() { -/// let x = stack.pop_front().unwrap(); -/// println!("{}", x); -/// } -/// ``` -/// -/// And of course we can mix and match: -/// -/// ``` -/// use std::collections::{DList, Deque}; -/// -/// let mut deque = DList::new(); -/// -/// // Init deque with 1, 2, 3, 4 -/// deque.push_front(2i); -/// deque.push_front(1i); -/// deque.push(3i); -/// deque.push(4i); -/// -/// // Will print (1, 4) and (2, 3) -/// while !deque.is_empty() { -/// let f = deque.pop_front().unwrap(); -/// let b = deque.pop().unwrap(); -/// println!("{}", (f, b)); -/// } -/// ``` -pub trait Deque<T> : MutableSeq<T> { - /// Provides a reference to the front element, or `None` if the sequence is - /// empty. - /// - /// # Example - /// - /// ``` - /// use std::collections::{RingBuf, Deque}; - /// - /// let mut d = RingBuf::new(); - /// assert_eq!(d.front(), None); - /// - /// d.push(1i); - /// d.push(2i); - /// assert_eq!(d.front(), Some(&1i)); - /// ``` - fn front<'a>(&'a self) -> Option<&'a T>; - - /// Provides a mutable reference to the front element, or `None` if the - /// sequence is empty. - /// - /// # Example - /// - /// ``` - /// use std::collections::{RingBuf, Deque}; - /// - /// let mut d = RingBuf::new(); - /// assert_eq!(d.front_mut(), None); - /// - /// d.push(1i); - /// d.push(2i); - /// match d.front_mut() { - /// Some(x) => *x = 9i, - /// None => (), - /// } - /// assert_eq!(d.front(), Some(&9i)); - /// ``` - fn front_mut<'a>(&'a mut self) -> Option<&'a mut T>; - - /// Provides a reference to the back element, or `None` if the sequence is - /// empty. - /// - /// # Example - /// - /// ``` - /// use std::collections::{DList, Deque}; - /// - /// let mut d = DList::new(); - /// assert_eq!(d.back(), None); - /// - /// d.push(1i); - /// d.push(2i); - /// assert_eq!(d.back(), Some(&2i)); - /// ``` - fn back<'a>(&'a self) -> Option<&'a T>; - - /// Provides a mutable reference to the back element, or `None` if the - /// sequence is empty. - /// - /// # Example - /// - /// ``` - /// use std::collections::{DList, Deque}; - /// - /// let mut d = DList::new(); - /// assert_eq!(d.back(), None); - /// - /// d.push(1i); - /// d.push(2i); - /// match d.back_mut() { - /// Some(x) => *x = 9i, - /// None => (), - /// } - /// assert_eq!(d.back(), Some(&9i)); - /// ``` - fn back_mut<'a>(&'a mut self) -> Option<&'a mut T>; - - /// Inserts an element first in the sequence. - /// - /// # Example - /// - /// ``` - /// use std::collections::{DList, Deque}; - /// - /// let mut d = DList::new(); - /// d.push_front(1i); - /// d.push_front(2i); - /// assert_eq!(d.front(), Some(&2i)); - /// ``` - fn push_front(&mut self, elt: T); - - /// Removes the first element and returns it, or `None` if the sequence is - /// empty. - /// - /// # Example - /// - /// ``` - /// use std::collections::{RingBuf, Deque}; - /// - /// let mut d = RingBuf::new(); - /// d.push(1i); - /// d.push(2i); - /// - /// assert_eq!(d.pop_front(), Some(1i)); - /// assert_eq!(d.pop_front(), Some(2i)); - /// assert_eq!(d.pop_front(), None); - /// ``` - fn pop_front(&mut self) -> Option<T>; -} +#[cfg(test)] mod bench; // FIXME(#14344) this shouldn't be necessary #[doc(hidden)] @@ -532,8 +79,4 @@ mod std { pub use core::clone; // deriving(Clone) pub use core::cmp; // deriving(Eq, Ord, etc.) pub use hash; // deriving(Hash) - - pub mod collections { - pub use MutableSeq; - } } diff --git a/src/libcollections/priority_queue.rs b/src/libcollections/priority_queue.rs index 65fd8ce4f54..885b5c99c45 100644 --- a/src/libcollections/priority_queue.rs +++ b/src/libcollections/priority_queue.rs @@ -159,7 +159,6 @@ use core::default::Default; use core::mem::{zeroed, replace, swap}; use core::ptr; -use {Mutable, MutableSeq}; use slice; use vec::Vec; @@ -171,16 +170,6 @@ pub struct PriorityQueue<T> { data: Vec<T>, } -impl<T: Ord> Collection for PriorityQueue<T> { - /// Returns the length of the queue. - fn len(&self) -> uint { self.data.len() } -} - -impl<T: Ord> Mutable for PriorityQueue<T> { - /// Drops all items from the queue. - fn clear(&mut self) { self.data.truncate(0) } -} - impl<T: Ord> Default for PriorityQueue<T> { #[inline] fn default() -> PriorityQueue<T> { PriorityQueue::new() } @@ -504,6 +493,15 @@ impl<T: Ord> PriorityQueue<T> { let len = self.len(); self.siftdown_range(pos, len); } + + /// Returns the length of the queue. + pub fn len(&self) -> uint { self.data.len() } + + /// Returns true if the queue contains no elements + pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Drops all items from the queue. + pub fn clear(&mut self) { self.data.truncate(0) } } /// `PriorityQueue` iterator. @@ -545,7 +543,6 @@ mod tests { use priority_queue::PriorityQueue; use vec::Vec; - use MutableSeq; #[test] fn test_iterator() { diff --git a/src/libcollections/ringbuf.rs b/src/libcollections/ringbuf.rs index 81e4361ec39..3c4c3fce61d 100644 --- a/src/libcollections/ringbuf.rs +++ b/src/libcollections/ringbuf.rs @@ -22,7 +22,6 @@ use core::iter; use core::slice; use std::hash::{Writer, Hash}; -use {Deque, Mutable, MutableSeq}; use vec::Vec; static INITIAL_CAPACITY: uint = 8u; // 2^3 @@ -36,86 +35,6 @@ pub struct RingBuf<T> { elts: Vec<Option<T>> } -impl<T> Collection for RingBuf<T> { - /// Returns the number of elements in the `RingBuf`. - fn len(&self) -> uint { self.nelts } -} - -impl<T> Mutable for RingBuf<T> { - /// Clears the `RingBuf`, removing all values. - fn clear(&mut self) { - for x in self.elts.iter_mut() { *x = None } - self.nelts = 0; - self.lo = 0; - } -} - -impl<T> Deque<T> for RingBuf<T> { - /// Returns a reference to the first element in the `RingBuf`. - fn front<'a>(&'a self) -> Option<&'a T> { - if self.nelts > 0 { Some(&self[0]) } else { None } - } - - /// Returns a mutable reference to the first element in the `RingBuf`. - fn front_mut<'a>(&'a mut self) -> Option<&'a mut T> { - if self.nelts > 0 { Some(&mut self[0]) } else { None } - } - - /// Returns a reference to the last element in the `RingBuf`. - fn back<'a>(&'a self) -> Option<&'a T> { - if self.nelts > 0 { Some(&self[self.nelts - 1]) } else { None } - } - - /// Returns a mutable reference to the last element in the `RingBuf`. - fn back_mut<'a>(&'a mut self) -> Option<&'a mut T> { - let nelts = self.nelts; - if nelts > 0 { Some(&mut self[nelts - 1]) } else { None } - } - - /// Removes and returns the first element in the `RingBuf`, or `None` if it - /// is empty. - fn pop_front(&mut self) -> Option<T> { - let result = self.elts[self.lo].take(); - if result.is_some() { - self.lo = (self.lo + 1u) % self.elts.len(); - self.nelts -= 1u; - } - result - } - - /// Prepends an element to the `RingBuf`. - fn push_front(&mut self, t: T) { - if self.nelts == self.elts.len() { - grow(self.nelts, &mut self.lo, &mut self.elts); - } - if self.lo == 0u { - self.lo = self.elts.len() - 1u; - } else { self.lo -= 1u; } - self.elts[self.lo] = Some(t); - self.nelts += 1u; - } -} - -impl<T> MutableSeq<T> for RingBuf<T> { - fn push(&mut self, t: T) { - if self.nelts == self.elts.len() { - grow(self.nelts, &mut self.lo, &mut self.elts); - } - let hi = self.raw_index(self.nelts); - self.elts[hi] = Some(t); - self.nelts += 1u; - } - fn pop(&mut self) -> Option<T> { - if self.nelts > 0 { - self.nelts -= 1; - let hi = self.raw_index(self.nelts); - self.elts[hi].take() - } else { - None - } - } -} - impl<T> Default for RingBuf<T> { #[inline] fn default() -> RingBuf<T> { RingBuf::new() } @@ -151,7 +70,7 @@ impl<T> RingBuf<T> { /// assert_eq!(buf[1], 7); /// ``` #[deprecated = "use indexing instead: `buf[index] = value`"] - pub fn get_mut<'a>(&'a mut self, i: uint) -> &'a mut T { + pub fn get_mut(&mut self, i: uint) -> &mut T { &mut self[i] } @@ -219,7 +138,7 @@ impl<T> RingBuf<T> { /// let b: &[_] = &[&5, &3, &4]; /// assert_eq!(buf.iter().collect::<Vec<&int>>().as_slice(), b); /// ``` - pub fn iter<'a>(&'a self) -> Items<'a, T> { + pub fn iter(&self) -> Items<T> { Items{index: 0, rindex: self.nelts, lo: self.lo, elts: self.elts.as_slice()} } @@ -240,7 +159,7 @@ impl<T> RingBuf<T> { /// let b: &[_] = &[&mut 3, &mut 1, &mut 2]; /// assert_eq!(buf.iter_mut().collect::<Vec<&mut int>>()[], b); /// ``` - pub fn iter_mut<'a>(&'a mut self) -> MutItems<'a, T> { + 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); @@ -268,6 +187,230 @@ impl<T> RingBuf<T> { } } } + + /// Returns the number of elements in the `RingBuf`. + /// + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let mut v = RingBuf::new(); + /// assert_eq!(v.len(), 0); + /// v.push(1i); + /// assert_eq!(v.len(), 1); + /// ``` + pub fn len(&self) -> uint { self.nelts } + + /// Returns true if the buffer contains no elements + /// + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let mut v = RingBuf::new(); + /// assert!(v.is_empty()); + /// v.push_front(1i); + /// assert!(!v.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Clears the buffer, removing all values. + /// + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let mut v = RingBuf::new(); + /// v.push(1i); + /// v.clear(); + /// assert!(v.is_empty()); + /// ``` + pub fn clear(&mut self) { + for x in self.elts.iter_mut() { *x = None } + self.nelts = 0; + self.lo = 0; + } + + /// Provides a reference to the front element, or `None` if the sequence is + /// empty. + /// + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let mut d = RingBuf::new(); + /// assert_eq!(d.front(), None); + /// + /// d.push(1i); + /// d.push(2i); + /// assert_eq!(d.front(), Some(&1i)); + /// ``` + pub fn front(&self) -> Option<&T> { + if self.nelts > 0 { Some(&self[0]) } else { None } + } + + /// Provides a mutable reference to the front element, or `None` if the + /// sequence is empty. + /// + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let mut d = RingBuf::new(); + /// assert_eq!(d.front_mut(), None); + /// + /// d.push(1i); + /// d.push(2i); + /// match d.front_mut() { + /// Some(x) => *x = 9i, + /// None => (), + /// } + /// assert_eq!(d.front(), Some(&9i)); + /// ``` + pub fn front_mut(&mut self) -> Option<&mut T> { + if self.nelts > 0 { Some(&mut self[0]) } else { None } + } + + /// Provides a reference to the back element, or `None` if the sequence is + /// empty. + /// + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let mut d = RingBuf::new(); + /// assert_eq!(d.back(), None); + /// + /// d.push(1i); + /// d.push(2i); + /// assert_eq!(d.back(), Some(&2i)); + /// ``` + pub fn back(&self) -> Option<&T> { + if self.nelts > 0 { Some(&self[self.nelts - 1]) } else { None } + } + + /// Provides a mutable reference to the back element, or `None` if the + /// sequence is empty. + /// + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let mut d = RingBuf::new(); + /// assert_eq!(d.back(), None); + /// + /// d.push(1i); + /// d.push(2i); + /// match d.back_mut() { + /// Some(x) => *x = 9i, + /// None => (), + /// } + /// assert_eq!(d.back(), Some(&9i)); + /// ``` + pub fn back_mut(&mut self) -> Option<&mut T> { + let nelts = self.nelts; + if nelts > 0 { Some(&mut self[nelts - 1]) } else { None } + } + + /// Removes the first element and returns it, or `None` if the sequence is + /// empty. + /// + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let mut d = RingBuf::new(); + /// d.push(1i); + /// d.push(2i); + /// + /// assert_eq!(d.pop_front(), Some(1i)); + /// assert_eq!(d.pop_front(), Some(2i)); + /// assert_eq!(d.pop_front(), None); + /// ``` + pub fn pop_front(&mut self) -> Option<T> { + let result = self.elts[self.lo].take(); + if result.is_some() { + self.lo = (self.lo + 1u) % self.elts.len(); + self.nelts -= 1u; + } + result + } + + /// Inserts an element first in the sequence. + /// + /// # Example + /// + /// ``` + /// use std::collections::RingBuf; + /// + /// let mut d = RingBuf::new(); + /// d.push_front(1i); + /// d.push_front(2i); + /// assert_eq!(d.front(), Some(&2i)); + /// ``` + pub fn push_front(&mut self, t: T) { + if self.nelts == self.elts.len() { + grow(self.nelts, &mut self.lo, &mut self.elts); + } + if self.lo == 0u { + self.lo = self.elts.len() - 1u; + } else { self.lo -= 1u; } + self.elts[self.lo] = Some(t); + self.nelts += 1u; + } + + /// Appends an element to the back of a buffer + /// + /// # Example + /// + /// ```rust + /// use std::collections::RingBuf; + /// + /// let mut buf = RingBuf::new(); + /// buf.push(1i); + /// buf.push(3); + /// assert_eq!(3, *buf.back().unwrap()); + /// ``` + pub fn push(&mut self, t: T) { + if self.nelts == self.elts.len() { + grow(self.nelts, &mut self.lo, &mut self.elts); + } + let hi = self.raw_index(self.nelts); + self.elts[hi] = Some(t); + self.nelts += 1u; + } + + /// Removes the last element from a buffer and returns it, or `None` if + /// it is empty. + /// + /// # Example + /// + /// ```rust + /// 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)); + /// ``` + pub fn pop(&mut self) -> Option<T> { + if self.nelts > 0 { + self.nelts -= 1; + let hi = self.raw_index(self.nelts); + self.elts[hi].take() + } else { + None + } + } } /// `RingBuf` iterator. @@ -513,7 +656,6 @@ mod tests { use test::Bencher; use test; - use {Deque, Mutable, MutableSeq}; use super::RingBuf; use vec::Vec; diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs index a552e4caa2d..107dc3e5c28 100644 --- a/src/libcollections/slice.rs +++ b/src/libcollections/slice.rs @@ -92,12 +92,11 @@ use core::cmp; use core::kinds::Sized; use core::mem::size_of; use core::mem; -use core::prelude::{Clone, Collection, Greater, Iterator, Less, None, Option}; +use core::prelude::{Clone, Greater, Iterator, Less, None, Option}; use core::prelude::{Ord, Ordering, RawPtr, Some, range}; use core::ptr; use core::iter::{range_step, MultiplicativeIterator}; -use MutableSeq; use vec::Vec; pub use core::slice::{Chunks, AsSlice, ImmutableSlice, ImmutablePartialEqSlice}; @@ -762,7 +761,6 @@ mod tests { use std::rt; use slice::*; - use {Mutable, MutableSeq}; use vec::Vec; fn square(n: uint) -> uint { n * n } @@ -2175,7 +2173,6 @@ mod bench { use test::Bencher; use vec::Vec; - use MutableSeq; #[bench] fn iterator(b: &mut Bencher) { diff --git a/src/libcollections/smallintmap.rs b/src/libcollections/smallintmap.rs index 9e6485103e1..b2e018743da 100644 --- a/src/libcollections/smallintmap.rs +++ b/src/libcollections/smallintmap.rs @@ -21,7 +21,6 @@ use core::iter; use core::iter::{Enumerate, FilterMap}; use core::mem::replace; -use {Mutable, Map, MutableMap, MutableSeq}; use {vec, slice}; use vec::Vec; use hash; @@ -65,90 +64,6 @@ pub struct SmallIntMap<T> { v: Vec<Option<T>>, } -impl<V> Collection for SmallIntMap<V> { - /// Returns the number of elements in the map. - fn len(&self) -> uint { - self.v.iter().filter(|elt| elt.is_some()).count() - } - - /// Returns`true` if there are no elements in the map. - fn is_empty(&self) -> bool { - self.v.iter().all(|elt| elt.is_none()) - } -} - -impl<V> Mutable for SmallIntMap<V> { - /// Clears the map, removing all key-value pairs. - fn clear(&mut self) { self.v.clear() } -} - -impl<V> Map<uint, V> for SmallIntMap<V> { - /// Returns a reference to the value corresponding to the key. - fn find<'a>(&'a self, key: &uint) -> Option<&'a V> { - if *key < self.v.len() { - match self.v[*key] { - Some(ref value) => Some(value), - None => None - } - } else { - None - } - } -} - -impl<V> MutableMap<uint, V> for SmallIntMap<V> { - /// Returns a mutable reference to the value corresponding to the key. - fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut V> { - if *key < self.v.len() { - match *self.v.index_mut(key) { - Some(ref mut value) => Some(value), - None => None - } - } else { - None - } - } - - /// 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. - 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. - fn remove(&mut self, key: &uint) -> bool { - self.pop(key).is_some() - } - - /// Inserts a key-value pair into the map. If the key already had a value - /// present in the map, that value is returned. Otherwise `None` is returned. - fn swap(&mut self, key: uint, value: V) -> Option<V> { - match self.find_mut(&key) { - Some(loc) => { return Some(replace(loc, value)); } - None => () - } - self.insert(key, value); - return None; - } - - /// Removes a key from the map, returning the value at the key if the key - /// was previously in the map. - fn pop(&mut self, key: &uint) -> Option<V> { - if *key >= self.v.len() { - return None; - } - self.v[*key].take() - } -} - impl<V> Default for SmallIntMap<V> { #[inline] fn default() -> SmallIntMap<V> { SmallIntMap::new() } @@ -295,6 +210,204 @@ impl<V> SmallIntMap<V> { v.map(|v| (i, v)) }) } + + /// Return the number of elements in the map. + /// + /// # Example + /// + /// ``` + /// use std::collections::SmallIntMap; + /// + /// let mut a = SmallIntMap::new(); + /// assert_eq!(a.len(), 0); + /// a.insert(1, "a"); + /// assert_eq!(a.len(), 1); + /// ``` + pub fn len(&self) -> uint { + self.v.iter().filter(|elt| elt.is_some()).count() + } + + /// Return true if the map contains no elements. + /// + /// # Example + /// + /// ``` + /// use std::collections::SmallIntMap; + /// + /// let mut a = SmallIntMap::new(); + /// assert!(a.is_empty()); + /// a.insert(1, "a"); + /// assert!(!a.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { + self.v.iter().all(|elt| elt.is_none()) + } + + /// Clears the map, removing all key-value pairs. + /// + /// # Example + /// + /// ``` + /// use std::collections::SmallIntMap; + /// + /// let mut a = SmallIntMap::new(); + /// a.insert(1, "a"); + /// a.clear(); + /// assert!(a.is_empty()); + /// ``` + pub fn clear(&mut self) { self.v.clear() } + + /// Returns a reference to the value corresponding to the key. + /// + /// # Example + /// + /// ``` + /// use std::collections::SmallIntMap; + /// + /// let mut map = SmallIntMap::new(); + /// map.insert(1, "a"); + /// assert_eq!(map.find(&1), Some(&"a")); + /// assert_eq!(map.find(&2), None); + /// ``` + pub fn find<'a>(&'a self, key: &uint) -> Option<&'a V> { + if *key < self.v.len() { + match self.v[*key] { + Some(ref value) => Some(value), + None => None + } + } else { + None + } + } + + /// Returns true if the map contains a value for the specified key. + /// + /// # Example + /// + /// ``` + /// use std::collections::SmallIntMap; + /// + /// let mut map = SmallIntMap::new(); + /// map.insert(1, "a"); + /// assert_eq!(map.contains_key(&1), true); + /// assert_eq!(map.contains_key(&2), false); + /// ``` + #[inline] + pub fn contains_key(&self, key: &uint) -> bool { + self.find(key).is_some() + } + + /// Returns a mutable reference to the value corresponding to the key. + /// + /// # Example + /// + /// ``` + /// use std::collections::SmallIntMap; + /// + /// let mut map = SmallIntMap::new(); + /// map.insert(1, "a"); + /// match map.find_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> { + if *key < self.v.len() { + match *(&mut self.v[*key]) { + Some(ref mut value) => Some(value), + None => None + } + } else { + None + } + } + + /// 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::SmallIntMap; + /// + /// let mut map = SmallIntMap::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::SmallIntMap; + /// + /// let mut map = SmallIntMap::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() + } + + /// Inserts a key-value pair from the map. If the key already had a value + /// present in the map, that value is returned. Otherwise, `None` is returned. + /// + /// # Example + /// + /// ``` + /// use std::collections::SmallIntMap; + /// + /// let mut map = SmallIntMap::new(); + /// assert_eq!(map.swap(37, "a"), None); + /// assert_eq!(map.is_empty(), false); + /// + /// map.insert(37, "b"); + /// assert_eq!(map.swap(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 => () + } + self.insert(key, value); + return None; + } + + /// Removes a key from the map, returning the value at the key if the key + /// was previously in the map. + /// + /// # Example + /// + /// ``` + /// use std::collections::SmallIntMap; + /// + /// let mut map = SmallIntMap::new(); + /// map.insert(1, "a"); + /// assert_eq!(map.pop(&1), Some("a")); + /// assert_eq!(map.pop(&1), None); + /// ``` + pub fn pop(&mut self, key: &uint) -> Option<V> { + if *key >= self.v.len() { + return None; + } + self.v[*key].take() + } } impl<V:Clone> SmallIntMap<V> { @@ -499,7 +612,6 @@ mod test_map { use vec::Vec; use hash; - use {Map, MutableMap, Mutable, MutableSeq}; use super::SmallIntMap; #[test] @@ -869,57 +981,72 @@ mod bench { extern crate test; use self::test::Bencher; use super::SmallIntMap; - use deque::bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n}; + use bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n}; - // Find seq #[bench] pub fn insert_rand_100(b: &mut Bencher) { let mut m : SmallIntMap<uint> = SmallIntMap::new(); - insert_rand_n(100, &mut m, b); + insert_rand_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } #[bench] pub fn insert_rand_10_000(b: &mut Bencher) { let mut m : SmallIntMap<uint> = SmallIntMap::new(); - insert_rand_n(10_000, &mut m, b); + insert_rand_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } // Insert seq #[bench] pub fn insert_seq_100(b: &mut Bencher) { let mut m : SmallIntMap<uint> = SmallIntMap::new(); - insert_seq_n(100, &mut m, b); + insert_seq_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } #[bench] pub fn insert_seq_10_000(b: &mut Bencher) { let mut m : SmallIntMap<uint> = SmallIntMap::new(); - insert_seq_n(10_000, &mut m, b); + insert_seq_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } // Find rand #[bench] pub fn find_rand_100(b: &mut Bencher) { let mut m : SmallIntMap<uint> = SmallIntMap::new(); - find_rand_n(100, &mut m, b); + find_rand_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } #[bench] pub fn find_rand_10_000(b: &mut Bencher) { let mut m : SmallIntMap<uint> = SmallIntMap::new(); - find_rand_n(10_000, &mut m, b); + find_rand_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } // Find seq #[bench] pub fn find_seq_100(b: &mut Bencher) { let mut m : SmallIntMap<uint> = SmallIntMap::new(); - find_seq_n(100, &mut m, b); + find_seq_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } #[bench] pub fn find_seq_10_000(b: &mut Bencher) { let mut m : SmallIntMap<uint> = SmallIntMap::new(); - find_seq_n(10_000, &mut m, b); + find_seq_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } } diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs index 86a640d1aeb..297ba71d252 100644 --- a/src/libcollections/str.rs +++ b/src/libcollections/str.rs @@ -59,12 +59,11 @@ use core::fmt; use core::cmp; use core::iter::AdditiveIterator; use core::kinds::Sized; -use core::prelude::{Char, Clone, Collection, Eq, Equiv, ImmutableSlice}; +use core::prelude::{Char, Clone, Eq, Equiv, ImmutableSlice}; use core::prelude::{Iterator, MutableSlice, None, Option, Ord, Ordering}; use core::prelude::{PartialEq, PartialOrd, Result, AsSlice, Some, Tuple2}; use core::prelude::{range}; -use {Deque, MutableSeq}; use hash; use ringbuf::RingBuf; use string::String; @@ -464,6 +463,14 @@ impl<'a> MaybeOwned<'a> { Owned(_) => false } } + + /// Return the number of bytes in this string. + #[inline] + pub fn len(&self) -> uint { self.as_slice().len() } + + /// Returns true if the string contains no bytes + #[inline] + pub fn is_empty(&self) -> bool { self.len() == 0 } } /// Trait for moving into a `MaybeOwned`. @@ -561,11 +568,6 @@ impl<'a> StrAllocating for MaybeOwned<'a> { } } -impl<'a> Collection for MaybeOwned<'a> { - #[inline] - fn len(&self) -> uint { self.as_slice().len() } -} - impl<'a> Clone for MaybeOwned<'a> { #[inline] fn clone(&self) -> MaybeOwned<'a> { @@ -782,7 +784,6 @@ mod tests { use std::option::{Some, None}; use std::ptr::RawPtr; use std::iter::{Iterator, DoubleEndedIterator}; - use {Collection, MutableSeq}; use super::*; use std::slice::{AsSlice, ImmutableSlice}; @@ -2142,14 +2143,16 @@ mod tests { #[test] fn test_str_container() { - fn sum_len<S: Collection>(v: &[S]) -> uint { + fn sum_len(v: &[&str]) -> uint { v.iter().map(|x| x.len()).sum() } let s = String::from_str("01234"); assert_eq!(5, sum_len(["012", "", "34"])); - assert_eq!(5, sum_len([String::from_str("01"), String::from_str("2"), - String::from_str("34"), String::from_str("")])); + assert_eq!(5, sum_len([String::from_str("01").as_slice(), + String::from_str("2").as_slice(), + String::from_str("34").as_slice(), + String::from_str("").as_slice()])); assert_eq!(5, sum_len([s.as_slice()])); } @@ -2232,7 +2235,8 @@ mod bench { use test::black_box; use super::*; use std::iter::{Iterator, DoubleEndedIterator}; - use std::collections::Collection; + use std::str::StrSlice; + use std::slice::ImmutableSlice; #[bench] fn char_iterator(b: &mut Bencher) { diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs index 507cfbf191c..b3c83ba5559 100644 --- a/src/libcollections/string.rs +++ b/src/libcollections/string.rs @@ -22,7 +22,6 @@ use core::ops; // FIXME: ICE's abound if you import the `Slice` type while importing `Slice` trait use core::raw::Slice as RawSlice; -use {Mutable, MutableSeq}; use hash; use slice::CloneableVector; use str; @@ -626,22 +625,43 @@ impl String { pub unsafe fn as_mut_vec<'a>(&'a mut self) -> &'a mut Vec<u8> { &mut self.vec } -} -#[experimental = "collection traits will probably be removed"] -impl Collection for String { + /// Return the number of bytes in this string. + /// + /// # Example + /// + /// ``` + /// let a = "foo".to_string(); + /// assert_eq!(a.len(), 3); + /// ``` #[inline] #[stable] - fn len(&self) -> uint { - self.vec.len() - } -} + pub fn len(&self) -> uint { self.vec.len() } -#[experimental = "collection traits will probably be removed"] -impl Mutable for String { + /// Returns true if the string contains no bytes + /// + /// # Example + /// + /// ``` + /// let mut v = String::new(); + /// assert!(v.is_empty()); + /// v.push('a'); + /// assert!(!v.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Truncates the string, returning it to 0 length. + /// + /// # Example + /// + /// ``` + /// let mut s = "foo".to_string(); + /// s.clear(); + /// assert!(s.is_empty()); + /// ``` #[inline] #[stable] - fn clear(&mut self) { + pub fn clear(&mut self) { self.vec.clear() } } @@ -830,7 +850,6 @@ mod tests { use std::prelude::*; use test::Bencher; - use {Mutable, MutableSeq}; use str; use str::{Str, StrSlice, Owned}; use super::{as_string, String}; diff --git a/src/libcollections/treemap.rs b/src/libcollections/treemap.rs index ea4d541aab9..7e6efcb3d12 100644 --- a/src/libcollections/treemap.rs +++ b/src/libcollections/treemap.rs @@ -44,7 +44,6 @@ use core::mem::{replace, swap}; use core::ptr; use std::hash::{Writer, Hash}; -use {Mutable, Set, MutableSet, MutableMap, Map, MutableSeq}; use vec::Vec; /// This is implemented as an AA tree, which is a simplified variation of @@ -206,45 +205,6 @@ impl<K: Ord + Show, V: Show> Show for TreeMap<K, V> { } } -impl<K: Ord, V> Collection for TreeMap<K, V> { - fn len(&self) -> uint { self.length } -} - -impl<K: Ord, V> Mutable for TreeMap<K, V> { - fn clear(&mut self) { - self.root = None; - self.length = 0 - } -} - -impl<K: Ord, V> Map<K, V> for TreeMap<K, V> { - // See comments on tree_find_with - #[inline] - fn find<'a>(&'a self, key: &K) -> Option<&'a V> { - tree_find_with(&self.root, |k2| key.cmp(k2)) - } -} - -impl<K: Ord, V> MutableMap<K, V> for TreeMap<K, V> { - // See comments on tree_find_with_mut - #[inline] - fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V> { - tree_find_with_mut(&mut self.root, |x| key.cmp(x)) - } - - fn swap(&mut self, key: K, value: V) -> Option<V> { - let ret = insert(&mut self.root, key, value); - if ret.is_none() { self.length += 1 } - ret - } - - fn pop(&mut self, key: &K) -> Option<V> { - let ret = remove(&mut self.root, key); - if ret.is_some() { self.length -= 1 } - ret - } -} - impl<K: Ord, V> Default for TreeMap<K,V> { #[inline] fn default() -> TreeMap<K, V> { TreeMap::new() } @@ -444,6 +404,184 @@ impl<K: Ord, V> TreeMap<K, V> { remaining: length } } + + /// Return the number of elements in the map. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeMap; + /// + /// let mut a = TreeMap::new(); + /// assert_eq!(a.len(), 0); + /// a.insert(1u, "a"); + /// assert_eq!(a.len(), 1); + /// ``` + pub fn len(&self) -> uint { self.length } + + /// Return true if the map contains no elements. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeMap; + /// + /// let mut a = TreeMap::new(); + /// assert!(a.is_empty()); + /// a.insert(1u, "a"); + /// assert!(!a.is_empty()); + /// ``` + #[inline] + pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Clears the map, removing all values. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeMap; + /// + /// let mut a = TreeMap::new(); + /// a.insert(1u, "a"); + /// a.clear(); + /// assert!(a.is_empty()); + /// ``` + pub fn clear(&mut self) { + self.root = None; + self.length = 0 + } + + /// Returns a reference to the value corresponding to the key. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeMap; + /// + /// let mut map = TreeMap::new(); + /// map.insert(1u, "a"); + /// assert_eq!(map.find(&1), Some(&"a")); + /// assert_eq!(map.find(&2), None); + /// ``` + #[inline] + pub fn find<'a>(&'a self, key: &K) -> Option<&'a V> { + tree_find_with(&self.root, |k2| key.cmp(k2)) + } + + /// Returns true if the map contains a value for the specified key. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeMap; + /// + /// let mut map = TreeMap::new(); + /// map.insert(1u, "a"); + /// assert_eq!(map.contains_key(&1), true); + /// assert_eq!(map.contains_key(&2), false); + /// ``` + #[inline] + pub fn contains_key(&self, key: &K) -> bool { + self.find(key).is_some() + } + + /// Returns a mutable reference to the value corresponding to the key. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeMap; + /// + /// let mut map = TreeMap::new(); + /// map.insert(1u, "a"); + /// match map.find_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> { + 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() + } + + /// Inserts a key-value pair from the map. If the key already had a value + /// present in the map, that value is returned. Otherwise, `None` is returned. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeMap; + /// + /// let mut map = TreeMap::new(); + /// assert_eq!(map.swap(37u, "a"), None); + /// assert_eq!(map.is_empty(), false); + /// + /// map.insert(37, "b"); + /// assert_eq!(map.swap(37, "c"), Some("b")); + /// assert_eq!(map[37], "c"); + /// ``` + pub fn swap(&mut self, key: K, value: V) -> Option<V> { + let ret = insert(&mut self.root, key, value); + if ret.is_none() { self.length += 1 } + ret + } + + /// Removes a key from the map, returning the value at the key if the key + /// was previously in the map. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeMap; + /// + /// let mut map = TreeMap::new(); + /// map.insert(1u, "a"); + /// assert_eq!(map.pop(&1), Some("a")); + /// assert_eq!(map.pop(&1), None); + /// ``` + pub fn pop(&mut self, key: &K) -> Option<V> { + let ret = remove(&mut self.root, key); + if ret.is_some() { self.length -= 1 } + ret + } } impl<K, V> TreeMap<K, V> { @@ -1062,59 +1200,6 @@ impl<T: Ord + Show> Show for TreeSet<T> { } } -impl<T: Ord> Collection for TreeSet<T> { - #[inline] - fn len(&self) -> uint { self.map.len() } -} - -impl<T: Ord> Mutable for TreeSet<T> { - #[inline] - fn clear(&mut self) { self.map.clear() } -} - -impl<T: Ord> Set<T> for TreeSet<T> { - #[inline] - fn contains(&self, value: &T) -> bool { - self.map.contains_key(value) - } - - fn is_disjoint(&self, other: &TreeSet<T>) -> bool { - self.intersection(other).next().is_none() - } - - fn is_subset(&self, other: &TreeSet<T>) -> bool { - let mut x = self.iter(); - let mut y = other.iter(); - let mut a = x.next(); - let mut b = y.next(); - while a.is_some() { - if b.is_none() { - return false; - } - - let a1 = a.unwrap(); - let b1 = b.unwrap(); - - match b1.cmp(a1) { - Less => (), - Greater => return false, - Equal => a = x.next(), - } - - b = y.next(); - } - true - } -} - -impl<T: Ord> MutableSet<T> for TreeSet<T> { - #[inline] - fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) } - - #[inline] - fn remove(&mut self, value: &T) -> bool { self.map.remove(value) } -} - impl<T: Ord> Default for TreeSet<T> { #[inline] fn default() -> TreeSet<T> { TreeSet::new() } @@ -1320,6 +1405,184 @@ impl<T: Ord> TreeSet<T> { pub fn union<'a>(&'a self, other: &'a TreeSet<T>) -> UnionItems<'a, T> { UnionItems{a: self.iter().peekable(), b: other.iter().peekable()} } + + /// Return the number of elements in the set + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// + /// let mut v = TreeSet::new(); + /// assert_eq!(v.len(), 0); + /// v.insert(1i); + /// assert_eq!(v.len(), 1); + /// ``` + #[inline] + pub fn len(&self) -> uint { self.map.len() } + + /// Returns true if the set contains no elements + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// + /// let mut v = TreeSet::new(); + /// assert!(v.is_empty()); + /// v.insert(1i); + /// assert!(!v.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Clears the set, removing all values. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// + /// let mut v = TreeSet::new(); + /// v.insert(1i); + /// v.clear(); + /// assert!(v.is_empty()); + /// ``` + #[inline] + pub fn clear(&mut self) { self.map.clear() } + + /// Returns `true` if the set contains a value. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// + /// let set: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); + /// assert_eq!(set.contains(&1), true); + /// assert_eq!(set.contains(&4), false); + /// ``` + #[inline] + pub fn contains(&self, value: &T) -> bool { + self.map.contains_key(value) + } + + /// Returns `true` if the set has no elements in common with `other`. + /// This is equivalent to checking for an empty intersection. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// + /// let a: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); + /// let mut b: TreeSet<int> = TreeSet::new(); + /// + /// assert_eq!(a.is_disjoint(&b), true); + /// b.insert(4); + /// assert_eq!(a.is_disjoint(&b), true); + /// b.insert(1); + /// assert_eq!(a.is_disjoint(&b), false); + /// ``` + pub fn is_disjoint(&self, other: &TreeSet<T>) -> bool { + self.intersection(other).next().is_none() + } + + /// Returns `true` if the set is a subset of another. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// + /// let sup: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); + /// let mut set: TreeSet<int> = TreeSet::new(); + /// + /// assert_eq!(set.is_subset(&sup), true); + /// set.insert(2); + /// assert_eq!(set.is_subset(&sup), true); + /// set.insert(4); + /// assert_eq!(set.is_subset(&sup), false); + /// ``` + pub fn is_subset(&self, other: &TreeSet<T>) -> bool { + let mut x = self.iter(); + let mut y = other.iter(); + let mut a = x.next(); + let mut b = y.next(); + while a.is_some() { + if b.is_none() { + return false; + } + + let a1 = a.unwrap(); + let b1 = b.unwrap(); + + match b1.cmp(a1) { + Less => (), + Greater => return false, + Equal => a = x.next(), + } + + b = y.next(); + } + true + } + + /// Returns `true` if the set is a superset of another. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// + /// let sub: TreeSet<int> = [1i, 2].iter().map(|&x| x).collect(); + /// let mut set: TreeSet<int> = TreeSet::new(); + /// + /// assert_eq!(set.is_superset(&sub), false); + /// + /// set.insert(0); + /// set.insert(1); + /// assert_eq!(set.is_superset(&sub), false); + /// + /// set.insert(2); + /// assert_eq!(set.is_superset(&sub), true); + /// ``` + pub fn is_superset(&self, other: &TreeSet<T>) -> bool { + other.is_subset(self) + } + + /// Adds a value to the set. Returns `true` if the value was not already + /// present in the set. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut set = BTreeSet::new(); + /// + /// assert_eq!(set.insert(2i), true); + /// assert_eq!(set.insert(2i), false); + /// assert_eq!(set.len(), 1); + /// ``` + #[inline] + pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) } + + /// Removes a value from the set. Returns `true` if the value was + /// present in the set. + /// + /// # Example + /// + /// ``` + /// use std::collections::BTreeSet; + /// + /// let mut set = BTreeSet::new(); + /// + /// set.insert(2i); + /// assert_eq!(set.remove(&2), true); + /// assert_eq!(set.remove(&2), false); + /// ``` + #[inline] + pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value) } } /// A lazy forward iterator over a set. @@ -1676,7 +1939,6 @@ mod test_treemap { use std::rand::Rng; use std::rand; - use {Map, MutableMap, Mutable, MutableSeq}; use super::{TreeMap, TreeNode}; #[test] @@ -2195,59 +2457,73 @@ mod bench { use test::{Bencher, black_box}; use super::TreeMap; - use MutableMap; - use deque::bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n}; + use bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n}; - // Find seq #[bench] pub fn insert_rand_100(b: &mut Bencher) { let mut m : TreeMap<uint,uint> = TreeMap::new(); - insert_rand_n(100, &mut m, b); + insert_rand_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } #[bench] pub fn insert_rand_10_000(b: &mut Bencher) { let mut m : TreeMap<uint,uint> = TreeMap::new(); - insert_rand_n(10_000, &mut m, b); + insert_rand_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } // Insert seq #[bench] pub fn insert_seq_100(b: &mut Bencher) { let mut m : TreeMap<uint,uint> = TreeMap::new(); - insert_seq_n(100, &mut m, b); + insert_seq_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } #[bench] pub fn insert_seq_10_000(b: &mut Bencher) { let mut m : TreeMap<uint,uint> = TreeMap::new(); - insert_seq_n(10_000, &mut m, b); + insert_seq_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.remove(&i); }); } // Find rand #[bench] pub fn find_rand_100(b: &mut Bencher) { let mut m : TreeMap<uint,uint> = TreeMap::new(); - find_rand_n(100, &mut m, b); + find_rand_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } #[bench] pub fn find_rand_10_000(b: &mut Bencher) { let mut m : TreeMap<uint,uint> = TreeMap::new(); - find_rand_n(10_000, &mut m, b); + find_rand_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } // Find seq #[bench] pub fn find_seq_100(b: &mut Bencher) { let mut m : TreeMap<uint,uint> = TreeMap::new(); - find_seq_n(100, &mut m, b); + find_seq_n(100, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } #[bench] pub fn find_seq_10_000(b: &mut Bencher) { let mut m : TreeMap<uint,uint> = TreeMap::new(); - find_seq_n(10_000, &mut m, b); + find_seq_n(10_000, &mut m, b, + |m, i| { m.insert(i, 1); }, + |m, i| { m.find(&i); }); } fn bench_iter(b: &mut Bencher, size: uint) { @@ -2286,7 +2562,6 @@ mod test_set { use std::prelude::*; use std::hash; - use {Set, MutableSet, Mutable, MutableMap, MutableSeq}; use super::{TreeMap, TreeSet}; #[test] diff --git a/src/libcollections/trie.rs b/src/libcollections/trie.rs index 8c18a6488ba..7a8cc5df55a 100644 --- a/src/libcollections/trie.rs +++ b/src/libcollections/trie.rs @@ -29,7 +29,6 @@ use core::uint; use core::iter; use std::hash::{Writer, Hash}; -use {Mutable, Map, MutableMap, Set, MutableSet}; use slice::{Items, MutItems}; use slice; @@ -126,72 +125,6 @@ impl<T: Show> Show for TrieMap<T> { } } -impl<T> Collection for TrieMap<T> { - /// Returns the number of elements in the map. - #[inline] - fn len(&self) -> uint { self.length } -} - -impl<T> Mutable for TrieMap<T> { - /// Clears the map, removing all values. - #[inline] - fn clear(&mut self) { - self.root = TrieNode::new(); - self.length = 0; - } -} - -impl<T> Map<uint, T> for TrieMap<T> { - /// Returns a reference to the value corresponding to the key. - #[inline] - fn find<'a>(&'a self, key: &uint) -> Option<&'a T> { - let mut node: &'a TrieNode<T> = &self.root; - let mut idx = 0; - loop { - match node.children[chunk(*key, idx)] { - Internal(ref x) => node = &**x, - External(stored, ref value) => { - if stored == *key { - return Some(value) - } else { - return None - } - } - Nothing => return None - } - idx += 1; - } - } -} - -impl<T> MutableMap<uint, T> for TrieMap<T> { - /// Returns a mutable reference to the value corresponding to the key. - #[inline] - fn find_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 from the map. If the key already had a value - /// present in the map, that value is returned. Otherwise, `None` is returned. - fn swap(&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); - if ret.is_none() { self.length += 1 } - ret - } - - /// Removes a key from the map, returning the value at the key if the key - /// was previously in the map. - fn pop(&mut self, key: &uint) -> Option<T> { - let ret = remove(&mut self.root.count, - &mut self.root.children[chunk(*key, 0)], - *key, 1); - if ret.is_some() { self.length -= 1 } - ret - } -} - impl<T> Default for TrieMap<T> { #[inline] fn default() -> TrieMap<T> { TrieMap::new() } @@ -294,6 +227,205 @@ impl<T> TrieMap<T> { iter } + + /// Return the number of elements in the map. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieMap; + /// + /// let mut a = TrieMap::new(); + /// assert_eq!(a.len(), 0); + /// a.insert(1, "a"); + /// assert_eq!(a.len(), 1); + /// ``` + #[inline] + pub fn len(&self) -> uint { self.length } + + /// Return true if the map contains no elements. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieMap; + /// + /// let mut a = TrieMap::new(); + /// assert!(a.is_empty()); + /// a.insert(1, "a"); + /// assert!(!a.is_empty()); + /// ``` + #[inline] + pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Clears the map, removing all values. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieMap; + /// + /// let mut a = TrieMap::new(); + /// a.insert(1, "a"); + /// a.clear(); + /// assert!(a.is_empty()); + /// ``` + #[inline] + pub fn clear(&mut self) { + self.root = TrieNode::new(); + self.length = 0; + } + + /// Returns a reference to the value corresponding to the key. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieMap; + /// + /// let mut map = TrieMap::new(); + /// map.insert(1, "a"); + /// assert_eq!(map.find(&1), Some(&"a")); + /// assert_eq!(map.find(&2), None); + /// ``` + #[inline] + pub fn find<'a>(&'a self, key: &uint) -> Option<&'a T> { + let mut node: &'a TrieNode<T> = &self.root; + let mut idx = 0; + loop { + match node.children[chunk(*key, idx)] { + Internal(ref x) => node = &**x, + External(stored, ref value) => { + if stored == *key { + return Some(value) + } else { + return None + } + } + Nothing => return None + } + idx += 1; + } + } + + /// Returns true if the map contains a value for the specified key. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieMap; + /// + /// let mut map = TrieMap::new(); + /// map.insert(1, "a"); + /// assert_eq!(map.contains_key(&1), true); + /// assert_eq!(map.contains_key(&2), false); + /// ``` + #[inline] + pub fn contains_key(&self, key: &uint) -> bool { + self.find(key).is_some() + } + + /// Returns a mutable reference to the value corresponding to the key. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieMap; + /// + /// let mut map = TrieMap::new(); + /// map.insert(1, "a"); + /// match map.find_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> { + 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() + } + + /// Inserts a key-value pair from the map. If the key already had a value + /// present in the map, that value is returned. Otherwise, `None` is returned. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieMap; + /// + /// let mut map = TrieMap::new(); + /// assert_eq!(map.swap(37, "a"), None); + /// assert_eq!(map.is_empty(), false); + /// + /// map.insert(37, "b"); + /// assert_eq!(map.swap(37, "c"), Some("b")); + /// assert_eq!(map[37], "c"); + /// ``` + pub fn swap(&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); + if ret.is_none() { self.length += 1 } + ret + } + + /// Removes a key from the map, returning the value at the key if the key + /// was previously in the map. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieMap; + /// + /// let mut map = TrieMap::new(); + /// map.insert(1, "a"); + /// assert_eq!(map.pop(&1), Some("a")); + /// assert_eq!(map.pop(&1), None); + /// ``` + pub fn pop(&mut self, key: &uint) -> Option<T> { + let ret = remove(&mut self.root.count, + &mut self.root.children[chunk(*key, 0)], + *key, 1); + if ret.is_some() { self.length -= 1 } + ret + } } // FIXME #5846 we want to be able to choose between &x and &mut x @@ -569,52 +701,6 @@ impl Show for TrieSet { } } -impl Collection for TrieSet { - /// Returns the number of elements in the set. - #[inline] - fn len(&self) -> uint { self.map.len() } -} - -impl Mutable for TrieSet { - /// Clears the set, removing all values. - #[inline] - fn clear(&mut self) { self.map.clear() } -} - -impl Set<uint> for TrieSet { - #[inline] - fn contains(&self, value: &uint) -> bool { - self.map.contains_key(value) - } - - #[inline] - fn is_disjoint(&self, other: &TrieSet) -> bool { - self.iter().all(|v| !other.contains(&v)) - } - - #[inline] - fn is_subset(&self, other: &TrieSet) -> bool { - self.iter().all(|v| other.contains(&v)) - } - - #[inline] - fn is_superset(&self, other: &TrieSet) -> bool { - other.is_subset(self) - } -} - -impl MutableSet<uint> for TrieSet { - #[inline] - fn insert(&mut self, value: uint) -> bool { - self.map.insert(value, ()) - } - - #[inline] - fn remove(&mut self, value: &uint) -> bool { - self.map.remove(value) - } -} - impl Default for TrieSet { #[inline] fn default() -> TrieSet { TrieSet::new() } @@ -714,6 +800,171 @@ impl TrieSet { pub fn upper_bound<'a>(&'a self, val: uint) -> SetItems<'a> { SetItems{iter: self.map.upper_bound(val)} } + + /// Return the number of elements in the set + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieSet; + /// + /// let mut v = TrieSet::new(); + /// assert_eq!(v.len(), 0); + /// v.insert(1); + /// assert_eq!(v.len(), 1); + /// ``` + #[inline] + pub fn len(&self) -> uint { self.map.len() } + + /// Returns true if the set contains no elements + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieSet; + /// + /// let mut v = TrieSet::new(); + /// assert!(v.is_empty()); + /// v.insert(1); + /// assert!(!v.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Clears the set, removing all values. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieSet; + /// + /// let mut v = TrieSet::new(); + /// v.insert(1); + /// v.clear(); + /// assert!(v.is_empty()); + /// ``` + #[inline] + pub fn clear(&mut self) { self.map.clear() } + + /// Returns `true` if the set contains a value. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieSet; + /// + /// let set: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); + /// assert_eq!(set.contains(&1), true); + /// assert_eq!(set.contains(&4), false); + /// ``` + #[inline] + pub fn contains(&self, value: &uint) -> bool { + self.map.contains_key(value) + } + + /// Returns `true` if the set has no elements in common with `other`. + /// This is equivalent to checking for an empty intersection. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieSet; + /// + /// let a: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); + /// let mut b: TrieSet = TrieSet::new(); + /// + /// assert_eq!(a.is_disjoint(&b), true); + /// b.insert(4); + /// assert_eq!(a.is_disjoint(&b), true); + /// b.insert(1); + /// assert_eq!(a.is_disjoint(&b), false); + /// ``` + #[inline] + pub fn is_disjoint(&self, other: &TrieSet) -> bool { + self.iter().all(|v| !other.contains(&v)) + } + + /// Returns `true` if the set is a subset of another. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieSet; + /// + /// let sup: TrieSet = [1, 2, 3].iter().map(|&x| x).collect(); + /// let mut set: TrieSet = TrieSet::new(); + /// + /// assert_eq!(set.is_subset(&sup), true); + /// set.insert(2); + /// assert_eq!(set.is_subset(&sup), true); + /// set.insert(4); + /// assert_eq!(set.is_subset(&sup), false); + /// ``` + #[inline] + pub fn is_subset(&self, other: &TrieSet) -> bool { + self.iter().all(|v| other.contains(&v)) + } + + /// Returns `true` if the set is a superset of another. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieSet; + /// + /// let sub: TrieSet = [1, 2].iter().map(|&x| x).collect(); + /// let mut set: TrieSet = TrieSet::new(); + /// + /// assert_eq!(set.is_superset(&sub), false); + /// + /// set.insert(0); + /// set.insert(1); + /// assert_eq!(set.is_superset(&sub), false); + /// + /// set.insert(2); + /// assert_eq!(set.is_superset(&sub), true); + /// ``` + #[inline] + pub fn is_superset(&self, other: &TrieSet) -> bool { + other.is_subset(self) + } + + /// Adds a value to the set. Returns `true` if the value was not already + /// present in the set. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieSet; + /// + /// let mut set = TrieSet::new(); + /// + /// assert_eq!(set.insert(2), true); + /// assert_eq!(set.insert(2), false); + /// assert_eq!(set.len(), 1); + /// ``` + #[inline] + pub fn insert(&mut self, value: uint) -> bool { + self.map.insert(value, ()) + } + + /// Removes a value from the set. Returns `true` if the value was + /// present in the set. + /// + /// # Example + /// + /// ``` + /// use std::collections::TrieSet; + /// + /// let mut set = TrieSet::new(); + /// + /// set.insert(2); + /// assert_eq!(set.remove(&2), true); + /// assert_eq!(set.remove(&2), false); + /// ``` + #[inline] + pub fn remove(&mut self, value: &uint) -> bool { + self.map.remove(value) + } } impl FromIterator<uint> for TrieSet { @@ -1026,7 +1277,6 @@ mod test_map { use std::uint; use std::hash; - use {MutableMap, Map, MutableSeq}; use super::{TrieMap, TrieNode, Internal, External, Nothing}; fn check_integrity<T>(trie: &TrieNode<T>) { @@ -1442,7 +1692,6 @@ mod bench_map { use std::rand::{weak_rng, Rng}; use test::{Bencher, black_box}; - use MutableMap; use super::TrieMap; fn bench_iter(b: &mut Bencher, size: uint) { @@ -1559,7 +1808,6 @@ mod test_set { use std::prelude::*; use std::uint; - use {MutableSet, Set, MutableSeq}; use super::TrieSet; #[test] diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs index b190093bafc..d7ec3836eb2 100644 --- a/src/libcollections/vec.rs +++ b/src/libcollections/vec.rs @@ -27,7 +27,6 @@ use core::ptr; use core::raw::Slice as RawSlice; use core::uint; -use {Mutable, MutableSeq}; use slice::{CloneableVector}; /// An owned, growable vector. @@ -530,15 +529,6 @@ impl<T: Ord> Ord for Vec<T> { } } -#[experimental = "waiting on Collection stability"] -impl<T> Collection for Vec<T> { - #[inline] - #[stable] - fn len(&self) -> uint { - self.len - } -} - // FIXME: #13996: need a way to mark the return value as `noalias` #[inline(never)] unsafe fn alloc_or_realloc<T>(ptr: *mut T, old_size: uint, size: uint) -> *mut T { @@ -969,15 +959,107 @@ impl<T> Vec<T> { self.push(f(i)); } } -} -#[experimental = "waiting on Mutable stability"] -impl<T> Mutable for Vec<T> { + /// Appends an element to the back of a collection. + /// + /// # Failure + /// + /// Fails if the number of elements in the vector overflows a `uint`. + /// + /// # Example + /// + /// ```rust + /// let mut vec = vec!(1i, 2); + /// vec.push(3); + /// assert_eq!(vec, vec!(1, 2, 3)); + /// ``` + #[inline] + #[stable] + pub fn push(&mut self, value: T) { + if mem::size_of::<T>() == 0 { + // zero-size types consume no memory, so we can't rely on the address space running out + self.len = self.len.checked_add(&1).expect("length overflow"); + unsafe { mem::forget(value); } + return + } + if self.len == self.cap { + let old_size = self.cap * mem::size_of::<T>(); + let size = max(old_size, 2 * mem::size_of::<T>()) * 2; + if old_size > size { panic!("capacity overflow") } + unsafe { + self.ptr = alloc_or_realloc(self.ptr, old_size, size); + } + self.cap = max(self.cap, 2) * 2; + } + + unsafe { + let end = (self.ptr as *const T).offset(self.len as int) as *mut T; + ptr::write(&mut *end, value); + self.len += 1; + } + } + + /// Removes the last element from a vector and returns it, or `None` if + /// it is empty. + /// + /// # Example + /// + /// ```rust + /// let mut vec = vec![1i, 2, 3]; + /// assert_eq!(vec.pop(), Some(3)); + /// assert_eq!(vec, vec![1, 2]); + /// ``` #[inline] #[stable] - fn clear(&mut self) { + pub fn pop(&mut self) -> Option<T> { + if self.len == 0 { + None + } else { + unsafe { + self.len -= 1; + Some(ptr::read(self.as_slice().unsafe_get(self.len()))) + } + } + } + + /// Clears the vector, removing all values. + /// + /// # Example + /// + /// ``` + /// let mut v = vec![1i, 2, 3]; + /// v.clear(); + /// assert!(v.is_empty()); + /// ``` + #[inline] + #[stable] + pub fn clear(&mut self) { self.truncate(0) } + + /// Return the number of elements in the vector + /// + /// # Example + /// + /// ``` + /// let a = vec![1i, 2, 3]; + /// assert_eq!(a.len(), 3); + /// ``` + #[inline] + #[stable] + pub fn len(&self) -> uint { self.len } + + /// Returns true if the vector contains no elements + /// + /// # Example + /// + /// ``` + /// let mut v = Vec::new(); + /// assert!(v.is_empty()); + /// v.push(1i); + /// assert!(!v.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { self.len() == 0 } } impl<T: PartialEq> Vec<T> { @@ -1141,61 +1223,6 @@ impl<T:fmt::Show> fmt::Show for Vec<T> { } } -#[experimental = "waiting on MutableSeq stability"] -impl<T> MutableSeq<T> for Vec<T> { - /// Appends an element to the back of a collection. - /// - /// # Failure - /// - /// Fails if the number of elements in the vector overflows a `uint`. - /// - /// # Example - /// - /// ```rust - /// let mut vec = vec!(1i, 2); - /// vec.push(3); - /// assert_eq!(vec, vec!(1, 2, 3)); - /// ``` - #[inline] - #[stable] - fn push(&mut self, value: T) { - if mem::size_of::<T>() == 0 { - // zero-size types consume no memory, so we can't rely on the address space running out - self.len = self.len.checked_add(&1).expect("length overflow"); - unsafe { mem::forget(value); } - return - } - if self.len == self.cap { - let old_size = self.cap * mem::size_of::<T>(); - let size = max(old_size, 2 * mem::size_of::<T>()) * 2; - if old_size > size { panic!("capacity overflow") } - unsafe { - self.ptr = alloc_or_realloc(self.ptr, old_size, size); - } - self.cap = max(self.cap, 2) * 2; - } - - unsafe { - let end = (self.ptr as *const T).offset(self.len as int) as *mut T; - ptr::write(&mut *end, value); - self.len += 1; - } - } - - #[inline] - #[stable] - fn pop(&mut self) -> Option<T> { - if self.len == 0 { - None - } else { - unsafe { - self.len -= 1; - Some(ptr::read(self.as_slice().unsafe_get(self.len()))) - } - } - } -} - /// An iterator that moves out of a vector. pub struct MoveItems<T> { allocation: *mut T, // the block of memory allocated for the vector @@ -1636,8 +1663,6 @@ mod tests { use test::Bencher; use super::{as_vec, unzip, raw, Vec}; - use MutableSeq; - struct DropCounter<'a> { count: &'a mut int } diff --git a/src/libcore/char.rs b/src/libcore/char.rs index 5d9553cbbbd..3b9f8f58a20 100644 --- a/src/libcore/char.rs +++ b/src/libcore/char.rs @@ -18,7 +18,7 @@ use mem::transmute; use option::{None, Option, Some}; use iter::range_step; -use collections::Collection; +use slice::ImmutableSlice; // UTF-8 ranges and tags for encoding characters static TAG_CONT: u8 = 0b1000_0000u8; diff --git a/src/libcore/collections.rs b/src/libcore/collections.rs deleted file mode 100644 index 7d87e03c134..00000000000 --- a/src/libcore/collections.rs +++ /dev/null @@ -1,38 +0,0 @@ -// Copyright 2013 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -//! Traits for generic collections - -/// A trait to represent the abstract idea of a container. The only concrete -/// knowledge known is the number of elements contained within. -pub trait Collection { - /// Return the number of elements in the container - /// - /// # Example - /// - /// ``` - /// let a = [1i, 2, 3]; - /// assert_eq!(a.len(), 3); - /// ``` - fn len(&self) -> uint; - - /// Return true if the container contains no elements - /// - /// # Example - /// - /// ``` - /// let s = String::new(); - /// assert!(s.is_empty()); - /// ``` - #[inline] - fn is_empty(&self) -> bool { - self.len() == 0 - } -} diff --git a/src/libcore/fmt/float.rs b/src/libcore/fmt/float.rs index b8a91a912ba..f51d3948757 100644 --- a/src/libcore/fmt/float.rs +++ b/src/libcore/fmt/float.rs @@ -11,14 +11,12 @@ #![allow(missing_docs)] use char; -use collections::Collection; use fmt; use iter::{range, DoubleEndedIterator}; use num::{Float, FPNaN, FPInfinite, ToPrimitive, Primitive}; use num::{Zero, One, cast}; use result::Ok; -use slice::MutableSlice; -use slice; +use slice::{mod, ImmutableSlice, MutableSlice}; use str::StrSlice; /// A flag that specifies whether to use exponential (scientific) notation. diff --git a/src/libcore/fmt/mod.rs b/src/libcore/fmt/mod.rs index 5000b020985..74b39a7058c 100644 --- a/src/libcore/fmt/mod.rs +++ b/src/libcore/fmt/mod.rs @@ -14,7 +14,6 @@ use any; use cell::{Cell, Ref, RefMut}; -use collections::Collection; use iter::{Iterator, range}; use kinds::{Copy, Sized}; use mem; diff --git a/src/libcore/fmt/num.rs b/src/libcore/fmt/num.rs index 568528f6ae2..190e1ecea59 100644 --- a/src/libcore/fmt/num.rs +++ b/src/libcore/fmt/num.rs @@ -14,11 +14,10 @@ #![allow(unsigned_negation)] -use collections::Collection; use fmt; use iter::DoubleEndedIterator; use num::{Int, cast, zero}; -use slice::{MutableSlice}; +use slice::{ImmutableSlice, MutableSlice}; /// A type that represents a specific radix #[doc(hidden)] diff --git a/src/libcore/lib.rs b/src/libcore/lib.rs index a7be23e53e0..7c5c54c6d8a 100644 --- a/src/libcore/lib.rs +++ b/src/libcore/lib.rs @@ -102,7 +102,6 @@ pub mod ops; pub mod cmp; pub mod clone; pub mod default; -pub mod collections; /* Core types and methods on primitives */ diff --git a/src/libcore/prelude.rs b/src/libcore/prelude.rs index 680f91945d1..64917fb2541 100644 --- a/src/libcore/prelude.rs +++ b/src/libcore/prelude.rs @@ -50,7 +50,6 @@ pub use char::Char; pub use clone::Clone; pub use cmp::{PartialEq, PartialOrd, Eq, Ord}; pub use cmp::{Ordering, Less, Equal, Greater, Equiv}; -pub use collections::Collection; pub use iter::{FromIterator, Extendable}; pub use iter::{Iterator, DoubleEndedIterator, RandomAccessIterator, CloneableIterator}; pub use iter::{OrdIterator, MutableDoubleEndedIterator, ExactSize}; diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs index dd51534d319..317a6e224bc 100644 --- a/src/libcore/slice.rs +++ b/src/libcore/slice.rs @@ -36,7 +36,6 @@ use mem::transmute; use clone::Clone; -use collections::Collection; use cmp::{PartialEq, PartialOrd, Eq, Ord, Ordering, Less, Equal, Greater, Equiv}; use cmp; use default::Default; @@ -234,6 +233,29 @@ pub trait ImmutableSlice<T> for Sized? { /// ``` #[unstable = "waiting on unboxed closures"] fn binary_search(&self, f: |&T| -> Ordering) -> BinarySearchResult; + + /// Return the number of elements in the slice + /// + /// # Example + /// + /// ``` + /// let a = [1i, 2, 3]; + /// assert_eq!(a.len(), 3); + /// ``` + #[experimental = "not triaged yet"] + fn len(&self) -> uint; + + /// Returns true if the slice has a length of 0 + /// + /// # Example + /// + /// ``` + /// let a = [1i, 2, 3]; + /// assert!(!a.is_empty()); + /// ``` + #[inline] + #[experimental = "not triaged yet"] + fn is_empty(&self) -> bool { self.len() == 0 } } #[unstable] @@ -372,6 +394,9 @@ impl<T> ImmutableSlice<T> for [T] { } return NotFound(base); } + + #[inline] + fn len(&self) -> uint { self.repr().len } } @@ -886,24 +911,6 @@ impl<'a,T> AsSlice<T> for &'a [T] { fn as_slice<'a>(&'a self) -> &'a [T] { *self } } -#[experimental = "trait is experimental"] -impl<'a, T> Collection for &'a [T] { - /// Returns the length of a slice. - #[inline] - fn len(&self) -> uint { - self.repr().len - } -} - -#[experimental = "trait is experimental"] -impl<'a, T> Collection for &'a mut [T] { - /// Returns the length of a slice. - #[inline] - fn len(&self) -> uint { - self.repr().len - } -} - #[unstable = "waiting for DST"] impl<'a, T> Default for &'a [T] { fn default() -> &'a [T] { &[] } @@ -1508,7 +1515,6 @@ pub mod raw { /// Operations on `[u8]`. #[experimental = "needs review"] pub mod bytes { - use collections::Collection; use kinds::Sized; use ptr; use slice::{ImmutableSlice, MutableSlice}; diff --git a/src/libcore/str.rs b/src/libcore/str.rs index 86bbef861c4..dd8c7e9660a 100644 --- a/src/libcore/str.rs +++ b/src/libcore/str.rs @@ -22,7 +22,6 @@ use char::Char; use clone::Clone; use cmp; use cmp::{PartialEq, Eq}; -use collections::Collection; use default::Default; use iter::{Map, Iterator}; use iter::{DoubleEndedIterator, ExactSize}; @@ -1057,7 +1056,6 @@ const TAG_CONT_U8: u8 = 0b1000_0000u8; /// Unsafe operations pub mod raw { use mem; - use collections::Collection; use ptr::RawPtr; use raw::Slice; use slice::{ImmutableSlice}; @@ -1121,7 +1119,6 @@ Section: Trait implementations #[allow(missing_docs)] pub mod traits { use cmp::{Ord, Ordering, Less, Equal, Greater, PartialEq, PartialOrd, Equiv, Eq}; - use collections::Collection; use iter::Iterator; use option::{Option, Some}; use ops; @@ -1199,13 +1196,6 @@ impl<'a> Str for &'a str { fn as_slice<'a>(&'a self) -> &'a str { *self } } -impl<'a> Collection for &'a str { - #[inline] - fn len(&self) -> uint { - self.repr().len - } -} - /// Methods for string slices pub trait StrSlice for Sized? { /// Returns true if one string contains another @@ -1827,6 +1817,28 @@ pub trait StrSlice for Sized? { /// Return an iterator of `u16` over the string encoded as UTF-16. fn utf16_units<'a>(&'a self) -> Utf16CodeUnits<'a>; + + /// Return the number of bytes in this string + /// + /// # Example + /// + /// ``` + /// assert_eq!("foo".len(), 3); + /// assert_eq!("ƒoo".len(), 4); + /// ``` + #[experimental = "not triaged yet"] + fn len(&self) -> uint; + + /// Returns true if this slice contains no bytes + /// + /// # Example + /// + /// ``` + /// assert!("".is_empty()); + /// ``` + #[inline] + #[experimental = "not triaged yet"] + fn is_empty(&self) -> bool { self.len() == 0 } } #[inline(never)] @@ -2179,6 +2191,9 @@ impl StrSlice for str { fn utf16_units(&self) -> Utf16CodeUnits { Utf16CodeUnits{ chars: self.chars(), extra: 0} } + + #[inline] + fn len(&self) -> uint { self.repr().len } } impl<'a> Default for &'a str { diff --git a/src/libgraphviz/maybe_owned_vec.rs b/src/libgraphviz/maybe_owned_vec.rs index a4d794d1f99..d465d140751 100644 --- a/src/libgraphviz/maybe_owned_vec.rs +++ b/src/libgraphviz/maybe_owned_vec.rs @@ -8,7 +8,6 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use std::collections::Collection; use std::default::Default; use std::fmt; use std::iter::FromIterator; @@ -62,6 +61,10 @@ impl<'a,T> MaybeOwnedVector<'a,T> { &Borrowed(ref v) => v.iter(), } } + + pub fn len(&self) -> uint { self.as_slice().len() } + + pub fn is_empty(&self) -> bool { self.len() == 0 } } impl<'a, T: PartialEq> PartialEq for MaybeOwnedVector<'a, T> { @@ -145,12 +148,6 @@ impl<'a, T> Default for MaybeOwnedVector<'a, T> { } } -impl<'a, T> Collection for MaybeOwnedVector<'a, T> { - fn len(&self) -> uint { - self.as_slice().len() - } -} - impl<'a> BytesContainer for MaybeOwnedVector<'a, u8> { fn container_as_bytes<'a>(&'a self) -> &'a [u8] { self.as_slice() diff --git a/src/libregex/re.rs b/src/libregex/re.rs index 08d73d3434f..df5bfccd18d 100644 --- a/src/libregex/re.rs +++ b/src/libregex/re.rs @@ -772,14 +772,14 @@ impl<'t> Captures<'t> { let re = Regex::new(r"\$\$").unwrap(); re.replace_all(text.as_slice(), NoExpand("$")) } -} -impl<'t> Collection for Captures<'t> { /// Returns the number of captured groups. #[inline] - fn len(&self) -> uint { - self.locs.len() / 2 - } + pub fn len(&self) -> uint { self.locs.len() / 2 } + + /// Returns if there are no captured groups. + #[inline] + pub fn is_empty(&self) -> bool { self.len() == 0 } } /// An iterator over capture groups for a particular match of a regular diff --git a/src/librlibc/lib.rs b/src/librlibc/lib.rs index ca7ce2a8b71..dd88eb3251b 100644 --- a/src/librlibc/lib.rs +++ b/src/librlibc/lib.rs @@ -108,7 +108,6 @@ pub unsafe extern "C" fn memcmp(s1: *const u8, s2: *const u8, n: uint) -> i32 { #[cfg(test)] mod test { - use core::collections::Collection; use core::str::StrSlice; use core::slice::{MutableSlice, ImmutableSlice}; diff --git a/src/librustc/middle/trans/adt.rs b/src/librustc/middle/trans/adt.rs index 98d02dfb8d7..7dbddd3f5df 100644 --- a/src/librustc/middle/trans/adt.rs +++ b/src/librustc/middle/trans/adt.rs @@ -45,7 +45,6 @@ #![allow(unsigned_negation)] -use std::collections::Map; use std::num::Int; use std::rc::Rc; diff --git a/src/librustc/util/common.rs b/src/librustc/util/common.rs index ed38f6f871d..cf807cb22bc 100644 --- a/src/librustc/util/common.rs +++ b/src/librustc/util/common.rs @@ -184,8 +184,8 @@ pub fn can_reach<S,H:Hasher<S>,T:Eq+Clone+Hash<S>>( /// } /// ``` #[inline(always)] -pub fn memoized<T: Clone, U: Clone, M: MutableMap<T, U>>( - cache: &RefCell<M>, +pub fn memoized<T: Clone + Hash<S> + Eq, U: Clone, S, H: Hasher<S>>( + cache: &RefCell<HashMap<T, U, H>>, arg: T, f: |T| -> U ) -> U { @@ -193,8 +193,8 @@ pub fn memoized<T: Clone, U: Clone, M: MutableMap<T, U>>( } #[inline(always)] -pub fn memoized_with_key<T, K, U: Clone, M: MutableMap<K, U>>( - cache: &RefCell<M>, +pub fn memoized_with_key<T, K: Hash<S> + Eq, U: Clone, S, H: Hasher<S>>( + cache: &RefCell<HashMap<K, U, H>>, arg: T, f: |T| -> U, k: |&T| -> K diff --git a/src/librustrt/at_exit_imp.rs b/src/librustrt/at_exit_imp.rs index c54afb241ae..ce27decb136 100644 --- a/src/librustrt/at_exit_imp.rs +++ b/src/librustrt/at_exit_imp.rs @@ -15,7 +15,6 @@ use core::prelude::*; use alloc::boxed::Box; -use collections::MutableSeq; use collections::vec::Vec; use core::atomic; use core::mem; diff --git a/src/librustrt/c_str.rs b/src/librustrt/c_str.rs index ddb4df4fdc5..676f36e5468 100644 --- a/src/librustrt/c_str.rs +++ b/src/librustrt/c_str.rs @@ -76,7 +76,7 @@ use collections::hash; use core::fmt; use core::kinds::marker; use core::mem; -use core::prelude::{Clone, Collection, Drop, Eq, ImmutableSlice, Iterator}; +use core::prelude::{Clone, Drop, Eq, ImmutableSlice, Iterator}; use core::prelude::{MutableSlice, None, Option, Ordering, PartialEq}; use core::prelude::{PartialOrd, RawPtr, Some, StrSlice, range}; use core::ptr; @@ -259,6 +259,16 @@ impl CString { self.buf } + /// Return the number of bytes in the CString (not including the NUL + /// terminator). + #[inline] + pub fn len(&self) -> uint { + unsafe { libc::strlen(self.buf) as uint } + } + + /// Returns if there are no bytes in this string + #[inline] + pub fn is_empty(&self) -> bool { self.len() == 0 } } impl Drop for CString { @@ -271,14 +281,6 @@ impl Drop for CString { } } -impl Collection for CString { - /// Return the number of bytes in the CString (not including the NUL terminator). - #[inline] - fn len(&self) -> uint { - unsafe { libc::strlen(self.buf) as uint } - } -} - impl fmt::Show for CString { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { String::from_utf8_lossy(self.as_bytes_no_nul()).fmt(f) diff --git a/src/librustrt/local_data.rs b/src/librustrt/local_data.rs index 14275d070f0..796f9af6596 100644 --- a/src/librustrt/local_data.rs +++ b/src/librustrt/local_data.rs @@ -42,7 +42,6 @@ use core::prelude::*; use alloc::heap; use collections::treemap::TreeMap; -use collections::MutableMap; use core::cmp; use core::kinds::marker; use core::mem; @@ -261,8 +260,6 @@ impl<T: 'static> KeyValue<T> { /// assert_eq!(*key.get().unwrap(), 3); /// ``` pub fn get(&'static self) -> Option<Ref<T>> { - use collections::Map; - let map = match unsafe { get_local_map() } { Some(map) => map, None => return None, diff --git a/src/libstd/ascii.rs b/src/libstd/ascii.rs index 31f37a8a1bb..6b64959a843 100644 --- a/src/libstd/ascii.rs +++ b/src/libstd/ascii.rs @@ -14,7 +14,6 @@ #![experimental] -use collections::Collection; use core::kinds::Sized; use fmt; use iter::Iterator; diff --git a/src/libstd/c_vec.rs b/src/libstd/c_vec.rs index bb7de168898..fd605bb2b5c 100644 --- a/src/libstd/c_vec.rs +++ b/src/libstd/c_vec.rs @@ -35,7 +35,6 @@ #![experimental] -use collections::Collection; use kinds::Send; use mem; use ops::Drop; @@ -143,6 +142,12 @@ impl<T> CVec<T> { self.dtor = None; self.base } + + /// Returns the number of items in this vector. + pub fn len(&self) -> uint { self.len } + + /// Returns whether this vector is empty. + pub fn is_empty(&self) -> bool { self.len() == 0 } } impl<T> AsSlice<T> for CVec<T> { @@ -154,10 +159,6 @@ impl<T> AsSlice<T> for CVec<T> { } } -impl<T> Collection for CVec<T> { - fn len(&self) -> uint { self.len } -} - #[cfg(test)] mod tests { use prelude::*; diff --git a/src/libstd/collections/hashmap/map.rs b/src/libstd/collections/hashmap/map.rs index 881ffd21d71..596e483c2f6 100644 --- a/src/libstd/collections/hashmap/map.rs +++ b/src/libstd/collections/hashmap/map.rs @@ -12,7 +12,6 @@ use clone::Clone; use cmp::{max, Eq, Equiv, PartialEq}; -use collections::{Collection, Mutable, MutableSet, Map, MutableMap}; use default::Default; use fmt::{mod, Show}; use hash::{Hash, Hasher, RandomSipHasher}; @@ -471,86 +470,6 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { } } -impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Collection for HashMap<K, V, H> { - /// Return the number of elements in the map. - fn len(&self) -> uint { self.table.size() } -} - -impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Mutable for HashMap<K, V, H> { - /// Clear the map, removing all key-value pairs. Keeps the allocated memory - /// for reuse. - 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. - self.resize_policy.reserve(self.table.size()); - - let cap = self.table.capacity(); - let mut buckets = Bucket::first(&mut self.table); - - while buckets.index() != cap { - buckets = match buckets.peek() { - Empty(b) => b.next(), - Full(full) => { - let (b, _, _) = full.take(); - b.next() - } - }; - } - } -} - -impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Map<K, V> for HashMap<K, V, H> { - fn find<'a>(&'a self, k: &K) -> Option<&'a V> { - self.search(k).map(|bucket| { - let (_, v) = bucket.into_refs(); - v - }) - } - - fn contains_key(&self, k: &K) -> bool { - self.search(k).is_some() - } -} - -impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> MutableMap<K, V> for HashMap<K, V, H> { - fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> { - match self.search_mut(k) { - Some(bucket) => { - let (_, v) = bucket.into_mut_refs(); - Some(v) - } - _ => None - } - } - - fn swap(&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); - - let mut retval = None; - self.insert_or_replace_with(hash, k, v, |_, val_ref, val| { - retval = Some(replace(val_ref, val)); - }); - retval - } - - - fn pop(&mut self, k: &K) -> Option<V> { - if self.table.size() == 0 { - return None - } - - let potential_new_size = self.table.size() - 1; - self.make_some_room(potential_new_size); - - self.search_mut(k).map(|bucket| { - let (_k, val) = pop_internal(bucket); - val - }) - } -} - impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> { /// Create an empty HashMap. /// @@ -1064,6 +983,219 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { let hash = self.make_hash(&key); search_entry_hashed(&mut self.table, hash, key) } + + /// Return the number of elements in the map. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut a = HashMap::new(); + /// assert_eq!(a.len(), 0); + /// a.insert(1u, "a"); + /// assert_eq!(a.len(), 1); + /// ``` + pub fn len(&self) -> uint { self.table.size() } + + /// Return true if the map contains no elements. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut a = HashMap::new(); + /// assert!(a.is_empty()); + /// a.insert(1u, "a"); + /// assert!(!a.is_empty()); + /// ``` + #[inline] + pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Clears the map, removing all key-value pairs. Keeps the allocated memory + /// for reuse. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut a = HashMap::new(); + /// a.insert(1u, "a"); + /// a.clear(); + /// assert!(a.is_empty()); + /// ``` + 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. + self.resize_policy.reserve(self.table.size()); + + let cap = self.table.capacity(); + let mut buckets = Bucket::first(&mut self.table); + + while buckets.index() != cap { + buckets = match buckets.peek() { + Empty(b) => b.next(), + Full(full) => { + let (b, _, _) = full.take(); + b.next() + } + }; + } + } + + /// Returns a reference to the value corresponding to the key. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut map = HashMap::new(); + /// map.insert(1u, "a"); + /// assert_eq!(map.find(&1), Some(&"a")); + /// assert_eq!(map.find(&2), None); + /// ``` + pub fn find<'a>(&'a self, k: &K) -> Option<&'a V> { + self.search(k).map(|bucket| { + let (_, v) = bucket.into_refs(); + v + }) + } + + /// Returns true if the map contains a value for the specified key. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut map = HashMap::new(); + /// map.insert(1u, "a"); + /// assert_eq!(map.contains_key(&1), true); + /// assert_eq!(map.contains_key(&2), false); + /// ``` + pub fn contains_key(&self, k: &K) -> bool { + self.search(k).is_some() + } + + /// Returns a mutable reference to the value corresponding to the key. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut map = HashMap::new(); + /// map.insert(1u, "a"); + /// match map.find_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> { + match self.search_mut(k) { + Some(bucket) => { + let (_, v) = bucket.into_mut_refs(); + Some(v) + } + _ => None + } + } + + /// 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() + } + + /// Inserts a key-value pair from the map. If the key already had a value + /// present in the map, that value is returned. Otherwise, `None` is returned. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut map = HashMap::new(); + /// assert_eq!(map.swap(37u, "a"), None); + /// assert_eq!(map.is_empty(), false); + /// + /// map.insert(37, "b"); + /// assert_eq!(map.swap(37, "c"), Some("b")); + /// assert_eq!(map[37], "c"); + /// ``` + pub fn swap(&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); + + let mut retval = None; + self.insert_or_replace_with(hash, k, v, |_, val_ref, val| { + retval = Some(replace(val_ref, val)); + }); + retval + } + + /// Removes a key from the map, returning the value at the key if the key + /// was previously in the map. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashMap; + /// + /// let mut map = HashMap::new(); + /// map.insert(1u, "a"); + /// assert_eq!(map.pop(&1), Some("a")); + /// assert_eq!(map.pop(&1), None); + /// ``` + pub fn pop(&mut self, k: &K) -> Option<V> { + if self.table.size() == 0 { + return None + } + + let potential_new_size = self.table.size() - 1; + self.make_some_room(potential_new_size); + + self.search_mut(k).map(|bucket| { + let (_k, val) = pop_internal(bucket); + val + }) + } } fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K) diff --git a/src/libstd/collections/hashmap/set.rs b/src/libstd/collections/hashmap/set.rs index e4016c70320..69f3812425f 100644 --- a/src/libstd/collections/hashmap/set.rs +++ b/src/libstd/collections/hashmap/set.rs @@ -12,7 +12,6 @@ use clone::Clone; use cmp::{Eq, Equiv, PartialEq}; -use collections::{Collection, Mutable, Set, MutableSet, Map, MutableMap}; use core::kinds::Sized; use default::Default; use fmt::Show; @@ -376,44 +375,170 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> { -> Chain<SetItems<'a, T>, SetAlgebraItems<'a, T, H>> { self.iter().chain(other.difference(self)) } -} -impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> { - fn eq(&self, other: &HashSet<T, H>) -> bool { - if self.len() != other.len() { return false; } - - self.iter().all(|key| other.contains(key)) - } -} - -impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {} + /// Return the number of elements in the set + /// + /// # Example + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let mut v = HashSet::new(); + /// assert_eq!(v.len(), 0); + /// v.insert(1u); + /// assert_eq!(v.len(), 1); + /// ``` + pub fn len(&self) -> uint { self.map.len() } -impl<T: Eq + Hash<S>, S, H: Hasher<S>> Collection for HashSet<T, H> { - fn len(&self) -> uint { self.map.len() } -} + /// Returns true if the set contains no elements + /// + /// # Example + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let mut v = HashSet::new(); + /// assert!(v.is_empty()); + /// v.insert(1u); + /// assert!(!v.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { self.map.len() == 0 } -impl<T: Eq + Hash<S>, S, H: Hasher<S>> Mutable for HashSet<T, H> { - fn clear(&mut self) { self.map.clear() } -} + /// Clears the set, removing all values. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let mut v = HashSet::new(); + /// v.insert(1u); + /// v.clear(); + /// assert!(v.is_empty()); + /// ``` + pub fn clear(&mut self) { self.map.clear() } -impl<T: Eq + Hash<S>, S, H: Hasher<S>> Set<T> for HashSet<T, H> { - fn contains(&self, value: &T) -> bool { self.map.contains_key(value) } + /// Returns `true` if the set contains a value. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let set: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect(); + /// assert_eq!(set.contains(&1), true); + /// assert_eq!(set.contains(&4), false); + /// ``` + pub fn contains(&self, value: &T) -> bool { self.map.contains_key(value) } - fn is_disjoint(&self, other: &HashSet<T, H>) -> bool { + /// Returns `true` if the set has no elements in common with `other`. + /// This is equivalent to checking for an empty intersection. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let a: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect(); + /// let mut b: HashSet<uint> = HashSet::new(); + /// + /// assert_eq!(a.is_disjoint(&b), true); + /// b.insert(4); + /// assert_eq!(a.is_disjoint(&b), true); + /// b.insert(1); + /// assert_eq!(a.is_disjoint(&b), false); + /// ``` + pub fn is_disjoint(&self, other: &HashSet<T, H>) -> bool { self.iter().all(|v| !other.contains(v)) } - fn is_subset(&self, other: &HashSet<T, H>) -> bool { + /// Returns `true` if the set is a subset of another. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let sup: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect(); + /// let mut set: HashSet<uint> = HashSet::new(); + /// + /// assert_eq!(set.is_subset(&sup), true); + /// set.insert(2); + /// assert_eq!(set.is_subset(&sup), true); + /// set.insert(4); + /// assert_eq!(set.is_subset(&sup), false); + /// ``` + pub fn is_subset(&self, other: &HashSet<T, H>) -> bool { self.iter().all(|v| other.contains(v)) } + + /// Returns `true` if the set is a superset of another. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let sub: HashSet<uint> = [1, 2].iter().map(|&x| x).collect(); + /// let mut set: HashSet<uint> = HashSet::new(); + /// + /// assert_eq!(set.is_superset(&sub), false); + /// + /// set.insert(0); + /// set.insert(1); + /// assert_eq!(set.is_superset(&sub), false); + /// + /// set.insert(2); + /// assert_eq!(set.is_superset(&sub), true); + /// ``` + #[inline] + pub fn is_superset(&self, other: &HashSet<T, H>) -> bool { + other.is_subset(self) + } + + /// Adds a value to the set. Returns `true` if the value was not already + /// present in the set. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let mut set = HashSet::new(); + /// + /// assert_eq!(set.insert(2u), true); + /// assert_eq!(set.insert(2), false); + /// assert_eq!(set.len(), 1); + /// ``` + pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) } + + /// Removes a value from the set. Returns `true` if the value was + /// present in the set. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let mut set = HashSet::new(); + /// + /// set.insert(2u); + /// assert_eq!(set.remove(&2), true); + /// assert_eq!(set.remove(&2), false); + /// ``` + pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value) } } -impl<T: Eq + Hash<S>, S, H: Hasher<S>> MutableSet<T> for HashSet<T, H> { - fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) } +impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> { + fn eq(&self, other: &HashSet<T, H>) -> bool { + if self.len() != other.len() { return false; } - fn remove(&mut self, value: &T) -> bool { self.map.remove(value) } + self.iter().all(|key| other.contains(key)) + } } +impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {} + impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { try!(write!(f, "{{")); @@ -471,7 +596,6 @@ mod test_set { use super::HashSet; use slice::ImmutablePartialEqSlice; - use collections::Collection; #[test] fn test_disjoint() { diff --git a/src/libstd/collections/lru_cache.rs b/src/libstd/collections/lru_cache.rs index 5408e50f2bd..93e649f9355 100644 --- a/src/libstd/collections/lru_cache.rs +++ b/src/libstd/collections/lru_cache.rs @@ -38,7 +38,7 @@ //! ``` use cmp::{PartialEq, Eq}; -use collections::{HashMap, Collection, Mutable, MutableMap}; +use collections::HashMap; use fmt; use hash::Hash; use iter::{range, Iterator}; @@ -288,6 +288,15 @@ impl<K: Hash + Eq, V> LruCache<K, V> { (*(*node).next).prev = node; } } + + /// Return the number of key-value pairs in the cache. + pub fn len(&self) -> uint { self.map.len() } + + /// Returns whether the cache is currently empty. + pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Clear the cache of all key-value pairs. + pub fn clear(&mut self) { self.map.clear(); } } impl<A: fmt::Show + Hash + Eq, B: fmt::Show> fmt::Show for LruCache<A, B> { @@ -311,20 +320,6 @@ impl<A: fmt::Show + Hash + Eq, B: fmt::Show> fmt::Show for LruCache<A, B> { } } -impl<K: Hash + Eq, V> Collection for LruCache<K, V> { - /// Return the number of key-value pairs in the cache. - fn len(&self) -> uint { - self.map.len() - } -} - -impl<K: Hash + Eq, V> Mutable for LruCache<K, V> { - /// Clear the cache of all key-value pairs. - fn clear(&mut self) { - self.map.clear(); - } -} - #[unsafe_destructor] impl<K, V> Drop for LruCache<K, V> { fn drop(&mut self) { diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs index c227aa65b48..be9e22ee9d1 100644 --- a/src/libstd/collections/mod.rs +++ b/src/libstd/collections/mod.rs @@ -328,8 +328,6 @@ #![experimental] -pub use core_collections::{Collection, Mutable, Map, MutableMap}; -pub use core_collections::{Set, MutableSet, Deque, MutableSeq}; pub use core_collections::{Bitv, BitvSet, BTreeMap, BTreeSet, DList, EnumSet}; pub use core_collections::{PriorityQueue, RingBuf, SmallIntMap}; pub use core_collections::{TreeMap, TreeSet, TrieMap, TrieSet}; diff --git a/src/libstd/dynamic_lib.rs b/src/libstd/dynamic_lib.rs index ec6eef07c95..4c133fc7397 100644 --- a/src/libstd/dynamic_lib.rs +++ b/src/libstd/dynamic_lib.rs @@ -20,7 +20,6 @@ A simple wrapper over the platform's dynamic library facilities #![allow(missing_docs)] use clone::Clone; -use collections::MutableSeq; use c_str::ToCStr; use iter::Iterator; use mem; @@ -280,7 +279,6 @@ pub mod dl { #[cfg(target_os = "windows")] pub mod dl { use c_str::ToCStr; - use collections::MutableSeq; use iter::Iterator; use libc; use os; diff --git a/src/libstd/io/buffered.rs b/src/libstd/io/buffered.rs index a01787c286b..49c688da31c 100644 --- a/src/libstd/io/buffered.rs +++ b/src/libstd/io/buffered.rs @@ -13,7 +13,6 @@ //! Buffering wrappers for I/O traits use cmp; -use collections::Collection; use io::{Reader, Writer, Stream, Buffer, DEFAULT_BUF_SIZE, IoResult}; use iter::ExactSize; use ops::Drop; diff --git a/src/libstd/io/comm_adapters.rs b/src/libstd/io/comm_adapters.rs index 91f3f38f89d..c925208c3ee 100644 --- a/src/libstd/io/comm_adapters.rs +++ b/src/libstd/io/comm_adapters.rs @@ -10,7 +10,6 @@ use clone::Clone; use cmp; -use collections::Collection; use comm::{Sender, Receiver}; use io; use option::{None, Some}; diff --git a/src/libstd/io/extensions.rs b/src/libstd/io/extensions.rs index 06ed183e936..6d0b8ebc3d9 100644 --- a/src/libstd/io/extensions.rs +++ b/src/libstd/io/extensions.rs @@ -15,7 +15,6 @@ // FIXME: Not sure how this should be structured // FIXME: Iteration should probably be considered separately -use collections::{Collection, MutableSeq}; use io::{IoError, IoResult, Reader}; use io; use iter::Iterator; @@ -502,7 +501,6 @@ mod test { mod bench { extern crate test; - use collections::Collection; use prelude::*; use self::test::Bencher; diff --git a/src/libstd/io/fs.rs b/src/libstd/io/fs.rs index f193ce8cffa..c8524676a6d 100644 --- a/src/libstd/io/fs.rs +++ b/src/libstd/io/fs.rs @@ -54,7 +54,6 @@ fs::unlink(&path); use c_str::ToCStr; use clone::Clone; -use collections::{Collection, MutableSeq}; use io::standard_error; use io::{FilePermission, Write, UnstableFileStat, Open, FileAccess, FileMode}; use io::{IoResult, IoError, FileStat, SeekStyle, Seek, Writer, Reader}; diff --git a/src/libstd/io/mem.rs b/src/libstd/io/mem.rs index 2f6dd7e4795..60104365817 100644 --- a/src/libstd/io/mem.rs +++ b/src/libstd/io/mem.rs @@ -13,13 +13,11 @@ //! Readers and Writers for in-memory buffers use cmp::min; -use collections::Collection; use option::None; use result::{Err, Ok}; use io; use io::{Reader, Writer, Seek, Buffer, IoError, SeekStyle, IoResult}; -use slice; -use slice::AsSlice; +use slice::{mod, AsSlice, ImmutableSlice}; use vec::Vec; const BUF_CAPACITY: uint = 128; diff --git a/src/libstd/io/mod.rs b/src/libstd/io/mod.rs index 6d6c0c0dd75..c6f237ff1da 100644 --- a/src/libstd/io/mod.rs +++ b/src/libstd/io/mod.rs @@ -222,7 +222,6 @@ responding to errors that may occur while attempting to read the numbers. #![deny(unused_must_use)] use char::Char; -use collections::Collection; use default::Default; use fmt; use int; diff --git a/src/libstd/io/net/ip.rs b/src/libstd/io/net/ip.rs index e93af744699..f4f3be13f66 100644 --- a/src/libstd/io/net/ip.rs +++ b/src/libstd/io/net/ip.rs @@ -15,13 +15,12 @@ #![allow(missing_docs)] -use collections::Collection; use fmt; use from_str::FromStr; use iter::Iterator; use option::{Option, None, Some}; use str::StrSlice; -use slice::{MutableCloneableSlice, MutableSlice}; +use slice::{MutableCloneableSlice, MutableSlice, ImmutableSlice}; pub type Port = u16; diff --git a/src/libstd/num/strconv.rs b/src/libstd/num/strconv.rs index 3b17f0bc79f..30ecf2284df 100644 --- a/src/libstd/num/strconv.rs +++ b/src/libstd/num/strconv.rs @@ -14,7 +14,6 @@ use char; use clone::Clone; -use collections::{Collection, MutableSeq}; use num::{NumCast, Zero, One, cast, Int}; use num::{Float, FPNaN, FPInfinite, ToPrimitive}; use num; diff --git a/src/libstd/os.rs b/src/libstd/os.rs index d4e6251cebe..5b3c872d2b7 100644 --- a/src/libstd/os.rs +++ b/src/libstd/os.rs @@ -32,7 +32,6 @@ #![allow(non_snake_case)] use clone::Clone; -use collections::{Collection, MutableSeq}; use fmt; use io::{IoResult, IoError}; use iter::Iterator; diff --git a/src/libstd/path/mod.rs b/src/libstd/path/mod.rs index 6a122990246..62105c0d90e 100644 --- a/src/libstd/path/mod.rs +++ b/src/libstd/path/mod.rs @@ -67,7 +67,6 @@ println!("path exists: {}", path.exists()); #![experimental] -use collections::{Collection, MutableSeq}; use c_str::CString; use clone::Clone; use fmt; diff --git a/src/libstd/path/posix.rs b/src/libstd/path/posix.rs index 0d7a467b313..596dbfc7e63 100644 --- a/src/libstd/path/posix.rs +++ b/src/libstd/path/posix.rs @@ -13,7 +13,6 @@ use c_str::{CString, ToCStr}; use clone::Clone; use cmp::{PartialEq, Eq, PartialOrd, Ord, Ordering}; -use collections::{Collection, MutableSeq}; use from_str::FromStr; use hash; use io::Writer; diff --git a/src/libstd/path/windows.rs b/src/libstd/path/windows.rs index 1ddc027a07e..de85748da5e 100644 --- a/src/libstd/path/windows.rs +++ b/src/libstd/path/windows.rs @@ -16,7 +16,6 @@ use ascii::AsciiCast; use c_str::{CString, ToCStr}; use clone::Clone; use cmp::{PartialEq, Eq, PartialOrd, Ord, Ordering}; -use collections::{Collection, MutableSeq}; use from_str::FromStr; use hash; use io::Writer; diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs index 48be404b0d0..b2ff29c0f7e 100644 --- a/src/libstd/prelude.rs +++ b/src/libstd/prelude.rs @@ -65,8 +65,6 @@ #[doc(no_inline)] pub use clone::Clone; #[doc(no_inline)] pub use cmp::{PartialEq, PartialOrd, Eq, Ord}; #[doc(no_inline)] pub use cmp::{Ordering, Less, Equal, Greater, Equiv}; -#[doc(no_inline)] pub use collections::{Collection, Mutable, Map, MutableMap, MutableSeq}; -#[doc(no_inline)] pub use collections::{Set, MutableSet}; #[doc(no_inline)] pub use iter::{FromIterator, Extendable, ExactSize}; #[doc(no_inline)] pub use iter::{Iterator, DoubleEndedIterator}; #[doc(no_inline)] pub use iter::{RandomAccessIterator, CloneableIterator}; diff --git a/src/libstd/rand/os.rs b/src/libstd/rand/os.rs index bf5bdc8a308..b7b08581230 100644 --- a/src/libstd/rand/os.rs +++ b/src/libstd/rand/os.rs @@ -62,7 +62,6 @@ mod imp { mod imp { extern crate libc; - use collections::Collection; use io::{IoResult}; use kinds::marker; use mem; @@ -70,7 +69,7 @@ mod imp { use rand::Rng; use result::{Ok}; use self::libc::{c_int, size_t}; - use slice::MutableSlice; + use slice::{ImmutableSlice, MutableSlice}; /// A random number generator that retrieves randomness straight from /// the operating system. Platform sources: @@ -130,7 +129,6 @@ mod imp { mod imp { extern crate libc; - use core_collections::Collection; use io::{IoResult, IoError}; use mem; use ops::Drop; @@ -139,7 +137,7 @@ mod imp { use result::{Ok, Err}; use self::libc::{DWORD, BYTE, LPCSTR, BOOL}; use self::libc::types::os::arch::extra::{LONG_PTR}; - use slice::MutableSlice; + use slice::{ImmutableSlice, MutableSlice}; type HCRYPTPROV = LONG_PTR; diff --git a/src/libstd/rand/reader.rs b/src/libstd/rand/reader.rs index 4f220531237..c1bb6970f71 100644 --- a/src/libstd/rand/reader.rs +++ b/src/libstd/rand/reader.rs @@ -10,10 +10,10 @@ //! A wrapper around any Reader to treat it as an RNG. -use collections::Collection; use io::Reader; use rand::Rng; use result::{Ok, Err}; +use slice::ImmutableSlice; /// An RNG that reads random bytes straight from a `Reader`. This will /// work best with an infinite reader, but this is not required. diff --git a/src/libstd/rt/backtrace.rs b/src/libstd/rt/backtrace.rs index 5bd39277275..5d7aa0509c5 100644 --- a/src/libstd/rt/backtrace.rs +++ b/src/libstd/rt/backtrace.rs @@ -12,7 +12,6 @@ #![allow(non_camel_case_types)] -use collections::Collection; use from_str::from_str; use io::{IoResult, Writer}; use iter::Iterator; @@ -390,7 +389,6 @@ mod imp { #[cfg(not(any(target_os = "macos", target_os = "ios")))] fn print(w: &mut Writer, idx: int, addr: *mut libc::c_void) -> IoResult<()> { - use collections::Collection; use iter::Iterator; use os; use path::GenericPath; @@ -659,7 +657,6 @@ mod imp { #[allow(dead_code, non_snake_case)] mod imp { use c_str::CString; - use core_collections::Collection; use intrinsics; use io::{IoResult, Writer}; use libc; diff --git a/src/libsync/deque.rs b/src/libsync/deque.rs index 31889a36dd7..11b8b974dcf 100644 --- a/src/libsync/deque.rs +++ b/src/libsync/deque.rs @@ -55,7 +55,7 @@ use core::prelude::*; use alloc::arc::Arc; use alloc::heap::{allocate, deallocate}; use alloc::boxed::Box; -use collections::{Vec, MutableSeq}; +use collections::Vec; use core::kinds::marker; use core::mem::{forget, min_align_of, size_of, transmute}; use core::ptr; diff --git a/src/libsync/raw.rs b/src/libsync/raw.rs index 1410091b924..facf204983b 100644 --- a/src/libsync/raw.rs +++ b/src/libsync/raw.rs @@ -22,7 +22,7 @@ use core::finally::Finally; use core::kinds::marker; use core::mem; use core::cell::UnsafeCell; -use collections::{Vec, MutableSeq}; +use collections::Vec; use mutex; use comm::{Receiver, Sender, channel}; diff --git a/src/libsyntax/owned_slice.rs b/src/libsyntax/owned_slice.rs index 4f09b34557c..f622e2d6112 100644 --- a/src/libsyntax/owned_slice.rs +++ b/src/libsyntax/owned_slice.rs @@ -112,6 +112,10 @@ impl<T> OwnedSlice<T> { pub fn map<U>(&self, f: |&T| -> U) -> OwnedSlice<U> { self.iter().map(f).collect() } + + pub fn len(&self) -> uint { self.len } + + pub fn is_empty(&self) -> bool { self.len == 0 } } impl<T> Default for OwnedSlice<T> { @@ -140,10 +144,6 @@ impl<T: PartialEq> PartialEq for OwnedSlice<T> { impl<T: Eq> Eq for OwnedSlice<T> {} -impl<T> Collection for OwnedSlice<T> { - fn len(&self) -> uint { self.len } -} - impl<T> FromIterator<T> for OwnedSlice<T> { fn from_iter<I: Iterator<T>>(mut iter: I) -> OwnedSlice<T> { OwnedSlice::from_vec(iter.collect()) diff --git a/src/libsyntax/util/small_vector.rs b/src/libsyntax/util/small_vector.rs index 422c2d5c75b..56ee6c7b915 100644 --- a/src/libsyntax/util/small_vector.rs +++ b/src/libsyntax/util/small_vector.rs @@ -25,16 +25,6 @@ enum SmallVectorRepr<T> { Many(Vec<T>), } -impl<T> Collection for SmallVector<T> { - fn len(&self) -> uint { - match self.repr { - Zero => 0, - One(..) => 1, - Many(ref vals) => vals.len() - } - } -} - impl<T> FromIterator<T> for SmallVector<T> { fn from_iter<I: Iterator<T>>(iter: I) -> SmallVector<T> { let mut v = SmallVector::zero(); @@ -131,6 +121,16 @@ impl<T> SmallVector<T> { }; MoveItems { repr: repr } } + + pub fn len(&self) -> uint { + match self.repr { + Zero => 0, + One(..) => 1, + Many(ref vals) => vals.len() + } + } + + pub fn is_empty(&self) -> bool { self.len() == 0 } } pub struct MoveItems<T> { diff --git a/src/libunicode/u_str.rs b/src/libunicode/u_str.rs index e4148440252..4bad631798f 100644 --- a/src/libunicode/u_str.rs +++ b/src/libunicode/u_str.rs @@ -19,7 +19,7 @@ use core::clone::Clone; use core::cmp; -use core::collections::Collection; +use core::slice::ImmutableSlice; use core::iter::{Filter, AdditiveIterator, Iterator, DoubleEndedIterator}; use core::kinds::Sized; use core::option::{Option, None, Some}; diff --git a/src/test/bench/core-map.rs b/src/test/bench/core-map.rs index f68ace395aa..3933a33446d 100644 --- a/src/test/bench/core-map.rs +++ b/src/test/bench/core-map.rs @@ -22,7 +22,29 @@ fn timed(label: &str, f: ||) { println!(" {}: {}", label, end - start); } -fn ascending<M: MutableMap<uint, uint>>(map: &mut M, n_keys: uint) { +trait MutableMap { + fn insert(&mut self, k: uint, v: uint); + fn remove(&mut self, k: &uint) -> bool; + fn find(&self, k: &uint) -> Option<&uint>; +} + +impl MutableMap for TreeMap<uint, uint> { + fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); } + fn remove(&mut self, k: &uint) -> bool { self.remove(k) } + fn find(&self, k: &uint) -> Option<&uint> { self.find(k) } +} +impl MutableMap for HashMap<uint, uint> { + fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); } + fn remove(&mut self, k: &uint) -> bool { self.remove(k) } + fn find(&self, k: &uint) -> Option<&uint> { self.find(k) } +} +impl MutableMap for TrieMap<uint> { + fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); } + fn remove(&mut self, k: &uint) -> bool { self.remove(k) } + fn find(&self, k: &uint) -> Option<&uint> { self.find(k) } +} + +fn ascending<M: MutableMap>(map: &mut M, n_keys: uint) { println!(" Ascending integers:"); timed("insert", || { @@ -44,7 +66,7 @@ fn ascending<M: MutableMap<uint, uint>>(map: &mut M, n_keys: uint) { }); } -fn descending<M: MutableMap<uint, uint>>(map: &mut M, n_keys: uint) { +fn descending<M: MutableMap>(map: &mut M, n_keys: uint) { println!(" Descending integers:"); timed("insert", || { @@ -66,7 +88,7 @@ fn descending<M: MutableMap<uint, uint>>(map: &mut M, n_keys: uint) { }); } -fn vector<M: MutableMap<uint, uint>>(map: &mut M, n_keys: uint, dist: &[uint]) { +fn vector<M: MutableMap>(map: &mut M, n_keys: uint, dist: &[uint]) { timed("insert", || { for i in range(0u, n_keys) { map.insert(dist[i], i + 1); diff --git a/src/test/bench/core-set.rs b/src/test/bench/core-set.rs index 7f85bc1d700..4833467922b 100644 --- a/src/test/bench/core-set.rs +++ b/src/test/bench/core-set.rs @@ -16,6 +16,7 @@ extern crate time; use std::collections::bitv::BitvSet; use std::collections::TreeSet; +use std::hash::Hash; use std::collections::HashSet; use std::os; use std::uint; @@ -37,6 +38,28 @@ fn timed(result: &mut f64, op: ||) { *result = (end - start); } +trait MutableSet<T> { + fn insert(&mut self, k: T); + fn remove(&mut self, k: &T) -> bool; + fn contains(&self, k: &T) -> bool; +} + +impl<T: Hash + Eq> MutableSet<T> for HashSet<T> { + fn insert(&mut self, k: T) { self.insert(k); } + fn remove(&mut self, k: &T) -> bool { self.remove(k) } + fn contains(&self, k: &T) -> bool { self.contains(k) } +} +impl<T: Ord> MutableSet<T> for TreeSet<T> { + fn insert(&mut self, k: T) { self.insert(k); } + fn remove(&mut self, k: &T) -> bool { self.remove(k) } + fn contains(&self, k: &T) -> bool { self.contains(k) } +} +impl MutableSet<uint> for BitvSet { + fn insert(&mut self, k: uint) { self.insert(k); } + fn remove(&mut self, k: &uint) -> bool { self.remove(k) } + fn contains(&self, k: &uint) -> bool { self.contains(k) } +} + impl Results { pub fn bench_int<T:MutableSet<uint>, R: rand::Rng>( diff --git a/src/test/compile-fail/issue-16562.rs b/src/test/compile-fail/issue-16562.rs index 2207e10add4..3c784c3b770 100644 --- a/src/test/compile-fail/issue-16562.rs +++ b/src/test/compile-fail/issue-16562.rs @@ -15,6 +15,8 @@ struct Col<D, C> { col: C, } +trait Collection { fn len(&self) -> uint; } + impl<T, M: MatrixShape> Collection for Col<M, uint> { //~^ ERROR unable to infer enough type information fn len(&self) -> uint { diff --git a/src/test/compile-fail/issue-16747.rs b/src/test/compile-fail/issue-16747.rs index 012dc01ca97..134f58951ba 100644 --- a/src/test/compile-fail/issue-16747.rs +++ b/src/test/compile-fail/issue-16747.rs @@ -12,6 +12,8 @@ trait ListItem<'a> { fn list_name() -> &'a str; } +trait Collection { fn len(&self) -> uint; } + struct List<'a, T: ListItem<'a>> { //~^ ERROR the parameter type `T` may not live long enough; consider adding an explicit lifetime bo //~^^ NOTE ...so that the reference type `&'a [T]` does not outlive the data it points at diff --git a/src/test/compile-fail/map-types.rs b/src/test/compile-fail/map-types.rs index 6f032c5b1f0..b1116a4cca6 100644 --- a/src/test/compile-fail/map-types.rs +++ b/src/test/compile-fail/map-types.rs @@ -12,11 +12,15 @@ extern crate collections; use std::collections::HashMap; +trait Map<K, V> {} + +impl<K, V> Map<K, V> for HashMap<K, V> {} + // Test that trait types printed in error msgs include the type arguments. fn main() { let x: Box<HashMap<int, int>> = box HashMap::new(); let x: Box<Map<int, int>> = x; let y: Box<Map<uint, int>> = box x; - //~^ ERROR the trait `collections::Map<uint, int>` is not implemented + //~^ ERROR the trait `Map<uint, int>` is not implemented } diff --git a/src/test/run-pass/class-impl-very-parameterized-trait.rs b/src/test/run-pass/class-impl-very-parameterized-trait.rs index aab06c0339b..b5892c3f123 100644 --- a/src/test/run-pass/class-impl-very-parameterized-trait.rs +++ b/src/test/run-pass/class-impl-very-parameterized-trait.rs @@ -46,18 +46,9 @@ impl<T> cat<T> { return false; } } -} - -impl<T> Collection for cat<T> { fn len(&self) -> uint { self.meows as uint } fn is_empty(&self) -> bool { self.meows == 0 } -} - -impl<T> Mutable for cat<T> { fn clear(&mut self) {} -} - -impl<T> Map<int, T> for cat<T> { fn contains_key(&self, k: &int) -> bool { *k <= self.meows } fn find(&self, k: &int) -> Option<&T> { @@ -67,9 +58,6 @@ impl<T> Map<int, T> for cat<T> { None } } -} - -impl<T> MutableMap<int, T> for cat<T> { fn insert(&mut self, k: int, _: T) -> bool { self.meows += k; true diff --git a/src/test/run-pass/issue-2383.rs b/src/test/run-pass/issue-2383.rs index 9a00868cc12..39995db5a2f 100644 --- a/src/test/run-pass/issue-2383.rs +++ b/src/test/run-pass/issue-2383.rs @@ -11,7 +11,6 @@ extern crate collections; use std::collections::RingBuf; -use std::collections::Deque; pub fn main() { let mut q = RingBuf::new(); diff --git a/src/test/run-pass/send_str_hashmap.rs b/src/test/run-pass/send_str_hashmap.rs index 163cf194a3c..1edce811bcb 100644 --- a/src/test/run-pass/send_str_hashmap.rs +++ b/src/test/run-pass/send_str_hashmap.rs @@ -10,7 +10,6 @@ extern crate collections; -use std::collections::{Map, MutableMap}; use std::str::{SendStr, Owned, Slice}; use std::collections::HashMap; use std::option::Some; diff --git a/src/test/run-pass/send_str_treemap.rs b/src/test/run-pass/send_str_treemap.rs index c6b872efa03..f73ab8f52d7 100644 --- a/src/test/run-pass/send_str_treemap.rs +++ b/src/test/run-pass/send_str_treemap.rs @@ -10,7 +10,6 @@ extern crate collections; -use std::collections::{ Map, MutableMap}; use std::str::{SendStr, Owned, Slice}; use std::to_string::ToString; use self::collections::TreeMap; |