diff options
Diffstat (limited to 'src/libcollections')
| -rw-r--r-- | src/libcollections/binary_heap.rs | 7 | ||||
| -rw-r--r-- | src/libcollections/bit.rs | 1078 | ||||
| -rw-r--r-- | src/libcollections/borrow.rs | 316 | ||||
| -rw-r--r-- | src/libcollections/borrow_stage0.rs | 313 | ||||
| -rw-r--r-- | src/libcollections/btree/map.rs | 57 | ||||
| -rw-r--r-- | src/libcollections/btree/node.rs | 93 | ||||
| -rw-r--r-- | src/libcollections/btree/set.rs | 10 | ||||
| -rw-r--r-- | src/libcollections/enum_set.rs | 32 | ||||
| -rw-r--r-- | src/libcollections/lib.rs | 54 | ||||
| -rw-r--r-- | src/libcollections/linked_list.rs (renamed from src/libcollections/dlist.rs) | 257 | ||||
| -rw-r--r-- | src/libcollections/slice.rs | 31 | ||||
| -rw-r--r-- | src/libcollections/str.rs | 113 | ||||
| -rw-r--r-- | src/libcollections/string.rs | 70 | ||||
| -rw-r--r-- | src/libcollections/vec.rs | 106 | ||||
| -rw-r--r-- | src/libcollections/vec_deque.rs (renamed from src/libcollections/ring_buf.rs) | 446 | ||||
| -rw-r--r-- | src/libcollections/vec_map.rs | 25 |
16 files changed, 1915 insertions, 1093 deletions
diff --git a/src/libcollections/binary_heap.rs b/src/libcollections/binary_heap.rs index 6196d94b5a6..9f549fd7237 100644 --- a/src/libcollections/binary_heap.rs +++ b/src/libcollections/binary_heap.rs @@ -650,8 +650,8 @@ impl<'a, T: 'a> ExactSizeIterator for Drain<'a, T> {} #[stable(feature = "rust1", since = "1.0.0")] impl<T: Ord> FromIterator<T> for BinaryHeap<T> { - fn from_iter<Iter: Iterator<Item=T>>(iter: Iter) -> BinaryHeap<T> { - BinaryHeap::from_vec(iter.collect()) + fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> BinaryHeap<T> { + BinaryHeap::from_vec(iter.into_iter().collect()) } } @@ -677,7 +677,8 @@ impl<'a, T> IntoIterator for &'a BinaryHeap<T> where T: Ord { #[stable(feature = "rust1", since = "1.0.0")] impl<T: Ord> Extend<T> for BinaryHeap<T> { - fn extend<Iter: Iterator<Item=T>>(&mut self, iter: Iter) { + fn extend<I: IntoIterator<Item=T>>(&mut self, iterable: I) { + let iter = iterable.into_iter(); let (lower, _) = iter.size_hint(); self.reserve(lower); diff --git a/src/libcollections/bit.rs b/src/libcollections/bit.rs index 0b762788b20..11c576eab15 100644 --- a/src/libcollections/bit.rs +++ b/src/libcollections/bit.rs @@ -8,13 +8,13 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -// FIXME(Gankro): Bitv and BitvSet are very tightly coupled. Ideally (for -// maintenance), they should be in separate files/modules, with BitvSet only -// using Bitv's public API. This will be hard for performance though, because -// `Bitv` will not want to leak its internal representation while its internal +// FIXME(Gankro): BitVec and BitSet are very tightly coupled. Ideally (for +// maintenance), they should be in separate files/modules, with BitSet only +// using BitVec's public API. This will be hard for performance though, because +// `BitVec` will not want to leak its internal representation while its internal // representation as `u32`s must be assumed for best performance. -// FIXME(tbu-): `Bitv`'s methods shouldn't be `union`, `intersection`, but +// FIXME(tbu-): `BitVec`'s methods shouldn't be `union`, `intersection`, but // rather `or` and `and`. // (1) Be careful, most things can overflow here because the amount of bits in @@ -25,8 +25,8 @@ // methods rely on it (for *CORRECTNESS*). // (3) Make sure that the unused bits in the last word are zeroed out, again // other methods rely on it for *CORRECTNESS*. -// (4) `BitvSet` is tightly coupled with `Bitv`, so any changes you make in -// `Bitv` will need to be reflected in `BitvSet`. +// (4) `BitSet` is tightly coupled with `BitVec`, so any changes you make in +// `BitVec` will need to be reflected in `BitSet`. //! Collections implemented with bit vectors. //! @@ -38,17 +38,17 @@ //! [sieve]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes //! //! ``` -//! use std::collections::{BitvSet, Bitv}; +//! use std::collections::{BitSet, BitVec}; //! use std::num::Float; //! use std::iter; //! //! let max_prime = 10000; //! -//! // Store the primes as a BitvSet +//! // Store the primes as a BitSet //! let primes = { //! // Assume all numbers are prime to begin, and then we //! // cross off non-primes progressively -//! let mut bv = Bitv::from_elem(max_prime, true); +//! let mut bv = BitVec::from_elem(max_prime, true); //! //! // Neither 0 nor 1 are prime //! bv.set(0, false); @@ -62,7 +62,7 @@ //! for j in iter::range_step(i * i, max_prime, i) { bv.set(j, false) } //! } //! } -//! BitvSet::from_bitv(bv) +//! BitSet::from_bit_vec(bv) //! }; //! //! // Simple primality tests below our max bound @@ -75,7 +75,7 @@ //! } //! println!(""); //! -//! // We can manipulate the internal Bitv +//! // We can manipulate the internal BitVec //! let num_primes = primes.get_ref().iter().filter(|x| *x).count(); //! println!("There are {} primes below {}", num_primes, max_prime); //! ``` @@ -94,7 +94,7 @@ use core::num::Int; use core::ops::Index; use core::slice; use core::{u8, u32, usize}; -use bitv_set; //so meta +use bit_set; //so meta use Vec; @@ -112,7 +112,7 @@ fn reverse_bits(byte: u8) -> u8 { // Take two BitV's, and return iterators of their words, where the shorter one // has been padded with 0's -fn match_words <'a,'b>(a: &'a Bitv, b: &'b Bitv) -> (MatchWords<'a>, MatchWords<'b>) { +fn match_words <'a,'b>(a: &'a BitVec, b: &'b BitVec) -> (MatchWords<'a>, MatchWords<'b>) { let a_len = a.storage.len(); let b_len = b.storage.len(); @@ -134,9 +134,9 @@ static FALSE: bool = false; /// # Examples /// /// ```rust -/// use std::collections::Bitv; +/// use std::collections::BitVec; /// -/// let mut bv = Bitv::from_elem(10, false); +/// let mut bv = BitVec::from_elem(10, false); /// /// // insert all primes less than 10 /// bv.set(2, true); @@ -158,7 +158,7 @@ static FALSE: bool = false; /// ``` #[unstable(feature = "collections", reason = "RFC 509")] -pub struct Bitv { +pub struct BitVec { /// Internal representation of the bit vector storage: Vec<u32>, /// The number of valid bits in the internal representation @@ -166,7 +166,7 @@ pub struct Bitv { } // FIXME(Gankro): NopeNopeNopeNopeNope (wait for IndexGet to be a thing) -impl Index<usize> for Bitv { +impl Index<usize> for BitVec { type Output = bool; #[inline] @@ -202,12 +202,12 @@ fn mask_for_bits(bits: usize) -> u32 { !0u32 >> (u32::BITS - bits % u32::BITS) % u32::BITS } -impl Bitv { +impl BitVec { /// Applies the given operation to the blocks of self and other, and sets /// self to be the result. This relies on the caller not to corrupt the /// last word. #[inline] - fn process<F>(&mut self, other: &Bitv, mut op: F) -> bool where F: FnMut(u32, u32) -> u32 { + fn process<F>(&mut self, other: &BitVec, mut op: F) -> bool where F: FnMut(u32, u32) -> u32 { assert_eq!(self.len(), other.len()); // This could theoretically be a `debug_assert!`. assert_eq!(self.storage.len(), other.storage.len()); @@ -235,7 +235,7 @@ impl Bitv { } /// An operation might screw up the unused bits in the last block of the - /// `Bitv`. As per (3), it's assumed to be all 0s. This method fixes it up. + /// `BitVec`. As per (3), it's assumed to be all 0s. This method fixes it up. fn fix_last_block(&mut self) { let extra_bits = self.len() % u32::BITS; if extra_bits > 0 { @@ -245,44 +245,44 @@ impl Bitv { } } - /// Creates an empty `Bitv`. + /// Creates an empty `BitVec`. /// /// # Examples /// /// ``` - /// use std::collections::Bitv; - /// let mut bv = Bitv::new(); + /// use std::collections::BitVec; + /// let mut bv = BitVec::new(); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn new() -> Bitv { - Bitv { storage: Vec::new(), nbits: 0 } + pub fn new() -> BitVec { + BitVec { storage: Vec::new(), nbits: 0 } } - /// Creates a `Bitv` that holds `nbits` elements, setting each element + /// Creates a `BitVec` that holds `nbits` elements, setting each element /// to `bit`. /// /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::from_elem(10, false); + /// let mut bv = BitVec::from_elem(10, false); /// assert_eq!(bv.len(), 10); /// for x in bv.iter() { /// assert_eq!(x, false); /// } /// ``` - pub fn from_elem(nbits: usize, bit: bool) -> Bitv { + pub fn from_elem(nbits: usize, bit: bool) -> BitVec { let nblocks = blocks_for_bits(nbits); - let mut bitv = Bitv { + let mut bit_vec = BitVec { storage: repeat(if bit { !0u32 } else { 0u32 }).take(nblocks).collect(), nbits: nbits }; - bitv.fix_last_block(); - bitv + bit_vec.fix_last_block(); + bit_vec } - /// Constructs a new, empty `Bitv` with the specified capacity. + /// Constructs a new, empty `BitVec` with the specified capacity. /// /// The bitvector will be able to hold at least `capacity` bits without /// reallocating. If `capacity` is 0, it will not allocate. @@ -290,38 +290,38 @@ impl Bitv { /// It is important to note that this function does not specify the /// *length* of the returned bitvector, but only the *capacity*. #[stable(feature = "rust1", since = "1.0.0")] - pub fn with_capacity(nbits: usize) -> Bitv { - Bitv { + pub fn with_capacity(nbits: usize) -> BitVec { + BitVec { storage: Vec::with_capacity(blocks_for_bits(nbits)), nbits: 0, } } - /// Transforms a byte-vector into a `Bitv`. Each byte becomes eight bits, + /// Transforms a byte-vector into a `BitVec`. Each byte becomes eight bits, /// with the most significant bits of each byte coming first. Each /// bit becomes `true` if equal to 1 or `false` if equal to 0. /// /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let bv = Bitv::from_bytes(&[0b10100000, 0b00010010]); + /// let bv = BitVec::from_bytes(&[0b10100000, 0b00010010]); /// assert!(bv.eq_vec(&[true, false, true, false, /// false, false, false, false, /// false, false, false, true, /// false, false, true, false])); /// ``` - pub fn from_bytes(bytes: &[u8]) -> Bitv { + pub fn from_bytes(bytes: &[u8]) -> BitVec { let len = bytes.len().checked_mul(u8::BITS).expect("capacity overflow"); - let mut bitv = Bitv::with_capacity(len); + let mut bit_vec = BitVec::with_capacity(len); let complete_words = bytes.len() / 4; let extra_bytes = bytes.len() % 4; - bitv.nbits = len; + bit_vec.nbits = len; for i in 0..complete_words { - bitv.storage.push( + bit_vec.storage.push( ((reverse_bits(bytes[i * 4 + 0]) as u32) << 0) | ((reverse_bits(bytes[i * 4 + 1]) as u32) << 8) | ((reverse_bits(bytes[i * 4 + 2]) as u32) << 16) | @@ -334,29 +334,29 @@ impl Bitv { for (i, &byte) in bytes[complete_words*4..].iter().enumerate() { last_word |= (reverse_bits(byte) as u32) << (i * 8); } - bitv.storage.push(last_word); + bit_vec.storage.push(last_word); } - bitv + bit_vec } - /// Creates a `Bitv` of the specified length where the value at each index + /// Creates a `BitVec` of the specified length where the value at each index /// is `f(index)`. /// /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let bv = Bitv::from_fn(5, |i| { i % 2 == 0 }); + /// let bv = BitVec::from_fn(5, |i| { i % 2 == 0 }); /// assert!(bv.eq_vec(&[true, false, true, false, true])); /// ``` - pub fn from_fn<F>(len: usize, mut f: F) -> Bitv where F: FnMut(usize) -> bool { - let mut bitv = Bitv::from_elem(len, false); + pub fn from_fn<F>(len: usize, mut f: F) -> BitVec where F: FnMut(usize) -> bool { + let mut bit_vec = BitVec::from_elem(len, false); for i in 0..len { - bitv.set(i, f(i)); + bit_vec.set(i, f(i)); } - bitv + bit_vec } /// Retrieves the value at index `i`, or `None` if the index is out of bounds. @@ -364,9 +364,9 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let bv = Bitv::from_bytes(&[0b01100000]); + /// let bv = BitVec::from_bytes(&[0b01100000]); /// assert_eq!(bv.get(0), Some(false)); /// assert_eq!(bv.get(1), Some(true)); /// assert_eq!(bv.get(100), None); @@ -396,9 +396,9 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::from_elem(5, false); + /// let mut bv = BitVec::from_elem(5, false); /// bv.set(3, true); /// assert_eq!(bv[3], true); /// ``` @@ -420,14 +420,14 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// /// let before = 0b01100000; /// let after = 0b11111111; /// - /// let mut bv = Bitv::from_bytes(&[before]); + /// let mut bv = BitVec::from_bytes(&[before]); /// bv.set_all(); - /// assert_eq!(bv, Bitv::from_bytes(&[after])); + /// assert_eq!(bv, BitVec::from_bytes(&[after])); /// ``` #[inline] pub fn set_all(&mut self) { @@ -440,14 +440,14 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// /// let before = 0b01100000; /// let after = 0b10011111; /// - /// let mut bv = Bitv::from_bytes(&[before]); + /// let mut bv = BitVec::from_bytes(&[before]); /// bv.negate(); - /// assert_eq!(bv, Bitv::from_bytes(&[after])); + /// assert_eq!(bv, BitVec::from_bytes(&[after])); /// ``` #[inline] pub fn negate(&mut self) { @@ -468,20 +468,20 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// /// let a = 0b01100100; /// let b = 0b01011010; /// let res = 0b01111110; /// - /// let mut a = Bitv::from_bytes(&[a]); - /// let b = Bitv::from_bytes(&[b]); + /// let mut a = BitVec::from_bytes(&[a]); + /// let b = BitVec::from_bytes(&[b]); /// /// assert!(a.union(&b)); - /// assert_eq!(a, Bitv::from_bytes(&[res])); + /// assert_eq!(a, BitVec::from_bytes(&[res])); /// ``` #[inline] - pub fn union(&mut self, other: &Bitv) -> bool { + pub fn union(&mut self, other: &BitVec) -> bool { self.process(other, |w1, w2| w1 | w2) } @@ -498,20 +498,20 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// /// let a = 0b01100100; /// let b = 0b01011010; /// let res = 0b01000000; /// - /// let mut a = Bitv::from_bytes(&[a]); - /// let b = Bitv::from_bytes(&[b]); + /// let mut a = BitVec::from_bytes(&[a]); + /// let b = BitVec::from_bytes(&[b]); /// /// assert!(a.intersect(&b)); - /// assert_eq!(a, Bitv::from_bytes(&[res])); + /// assert_eq!(a, BitVec::from_bytes(&[res])); /// ``` #[inline] - pub fn intersect(&mut self, other: &Bitv) -> bool { + pub fn intersect(&mut self, other: &BitVec) -> bool { self.process(other, |w1, w2| w1 & w2) } @@ -528,27 +528,27 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// /// let a = 0b01100100; /// let b = 0b01011010; /// let a_b = 0b00100100; // a - b /// let b_a = 0b00011010; // b - a /// - /// let mut bva = Bitv::from_bytes(&[a]); - /// let bvb = Bitv::from_bytes(&[b]); + /// let mut bva = BitVec::from_bytes(&[a]); + /// let bvb = BitVec::from_bytes(&[b]); /// /// assert!(bva.difference(&bvb)); - /// assert_eq!(bva, Bitv::from_bytes(&[a_b])); + /// assert_eq!(bva, BitVec::from_bytes(&[a_b])); /// - /// let bva = Bitv::from_bytes(&[a]); - /// let mut bvb = Bitv::from_bytes(&[b]); + /// let bva = BitVec::from_bytes(&[a]); + /// let mut bvb = BitVec::from_bytes(&[b]); /// /// assert!(bvb.difference(&bva)); - /// assert_eq!(bvb, Bitv::from_bytes(&[b_a])); + /// assert_eq!(bvb, BitVec::from_bytes(&[b_a])); /// ``` #[inline] - pub fn difference(&mut self, other: &Bitv) -> bool { + pub fn difference(&mut self, other: &BitVec) -> bool { self.process(other, |w1, w2| w1 & !w2) } @@ -557,9 +557,9 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::from_elem(5, true); + /// let mut bv = BitVec::from_elem(5, true); /// assert_eq!(bv.all(), true); /// /// bv.set(1, false); @@ -581,15 +581,15 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let bv = Bitv::from_bytes(&[0b01110100, 0b10010010]); + /// let bv = BitVec::from_bytes(&[0b01110100, 0b10010010]); /// assert_eq!(bv.iter().filter(|x| *x).count(), 7); /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn iter(&self) -> Iter { - Iter { bitv: self, next_idx: 0, end_idx: self.nbits } + Iter { bit_vec: self, next_idx: 0, end_idx: self.nbits } } /// Returns `true` if all bits are 0. @@ -597,9 +597,9 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::from_elem(10, false); + /// let mut bv = BitVec::from_elem(10, false); /// assert_eq!(bv.none(), true); /// /// bv.set(3, true); @@ -614,9 +614,9 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::from_elem(10, false); + /// let mut bv = BitVec::from_elem(10, false); /// assert_eq!(bv.any(), false); /// /// bv.set(3, true); @@ -628,33 +628,33 @@ impl Bitv { } /// Organises the bits into bytes, such that the first bit in the - /// `Bitv` becomes the high-order bit of the first byte. If the - /// size of the `Bitv` is not a multiple of eight then trailing bits + /// `BitVec` becomes the high-order bit of the first byte. If the + /// size of the `BitVec` is not a multiple of eight then trailing bits /// will be filled-in with `false`. /// /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::from_elem(3, true); + /// let mut bv = BitVec::from_elem(3, true); /// bv.set(1, false); /// /// assert_eq!(bv.to_bytes(), vec!(0b10100000)); /// - /// let mut bv = Bitv::from_elem(9, false); + /// let mut bv = BitVec::from_elem(9, false); /// bv.set(2, true); /// bv.set(8, true); /// /// assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000)); /// ``` pub fn to_bytes(&self) -> Vec<u8> { - fn bit(bitv: &Bitv, byte: usize, bit: usize) -> u8 { + fn bit(bit_vec: &BitVec, byte: usize, bit: usize) -> u8 { let offset = byte * 8 + bit; - if offset >= bitv.nbits { + if offset >= bit_vec.nbits { 0 } else { - (bitv[offset] as u8) << (7 - bit) + (bit_vec[offset] as u8) << (7 - bit) } } @@ -672,19 +672,19 @@ impl Bitv { ).collect() } - /// Compares a `Bitv` to a slice of `bool`s. - /// Both the `Bitv` and slice must have the same length. + /// Compares a `BitVec` to a slice of `bool`s. + /// Both the `BitVec` and slice must have the same length. /// /// # Panics /// - /// Panics if the `Bitv` and slice are of different length. + /// Panics if the `BitVec` and slice are of different length. /// /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let bv = Bitv::from_bytes(&[0b10100000]); + /// let bv = BitVec::from_bytes(&[0b10100000]); /// /// assert!(bv.eq_vec(&[true, false, true, false, /// false, false, false, false])); @@ -694,7 +694,7 @@ impl Bitv { iter::order::eq(self.iter(), v.iter().cloned()) } - /// Shortens a `Bitv`, dropping excess elements. + /// Shortens a `BitVec`, dropping excess elements. /// /// If `len` is greater than the vector's current length, this has no /// effect. @@ -702,9 +702,9 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::from_bytes(&[0b01001011]); + /// let mut bv = BitVec::from_bytes(&[0b01001011]); /// bv.truncate(2); /// assert!(bv.eq_vec(&[false, true])); /// ``` @@ -719,7 +719,7 @@ impl Bitv { } /// Reserves capacity for at least `additional` more bits to be inserted in the given - /// `Bitv`. The collection may reserve more space to avoid frequent reallocations. + /// `BitVec`. The collection may reserve more space to avoid frequent reallocations. /// /// # Panics /// @@ -728,9 +728,9 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::from_elem(3, false); + /// let mut bv = BitVec::from_elem(3, false); /// bv.reserve(10); /// assert_eq!(bv.len(), 3); /// assert!(bv.capacity() >= 13); @@ -745,7 +745,7 @@ impl Bitv { } /// Reserves the minimum capacity for exactly `additional` more bits to be inserted in the - /// given `Bitv`. Does nothing if the capacity is already sufficient. + /// given `BitVec`. Does nothing if the capacity is already sufficient. /// /// Note that the allocator may give the collection more space than it requests. Therefore /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future @@ -758,9 +758,9 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::from_elem(3, false); + /// let mut bv = BitVec::from_elem(3, false); /// bv.reserve(10); /// assert_eq!(bv.len(), 3); /// assert!(bv.capacity() >= 13); @@ -780,9 +780,9 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::new(); + /// let mut bv = BitVec::new(); /// bv.reserve(10); /// assert!(bv.capacity() >= 10); /// ``` @@ -792,7 +792,7 @@ impl Bitv { self.storage.capacity().checked_mul(u32::BITS).unwrap_or(usize::MAX) } - /// Grows the `Bitv` in-place, adding `n` copies of `value` to the `Bitv`. + /// Grows the `BitVec` in-place, adding `n` copies of `value` to the `BitVec`. /// /// # Panics /// @@ -801,9 +801,9 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::from_bytes(&[0b01001011]); + /// let mut bv = BitVec::from_bytes(&[0b01001011]); /// bv.grow(2, true); /// assert_eq!(bv.len(), 10); /// assert_eq!(bv.to_bytes(), vec!(0b01001011, 0b11000000)); @@ -846,14 +846,14 @@ impl Bitv { self.fix_last_block(); } - /// Removes the last bit from the Bitv, and returns it. Returns None if the Bitv is empty. + /// Removes the last bit from the BitVec, and returns it. Returns None if the BitVec is empty. /// /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::from_bytes(&[0b01001001]); + /// let mut bv = BitVec::from_bytes(&[0b01001001]); /// assert_eq!(bv.pop(), Some(true)); /// assert_eq!(bv.pop(), Some(false)); /// assert_eq!(bv.len(), 6); @@ -881,9 +881,9 @@ impl Bitv { /// # Examples /// /// ``` - /// use std::collections::Bitv; + /// use std::collections::BitVec; /// - /// let mut bv = Bitv::new(); + /// let mut bv = BitVec::new(); /// bv.push(true); /// bv.push(false); /// assert!(bv.eq_vec(&[true, false])); @@ -917,24 +917,25 @@ impl Bitv { } #[stable(feature = "rust1", since = "1.0.0")] -impl Default for Bitv { +impl Default for BitVec { #[inline] - fn default() -> Bitv { Bitv::new() } + fn default() -> BitVec { BitVec::new() } } #[stable(feature = "rust1", since = "1.0.0")] -impl FromIterator<bool> for Bitv { - fn from_iter<I:Iterator<Item=bool>>(iterator: I) -> Bitv { - let mut ret = Bitv::new(); - ret.extend(iterator); +impl FromIterator<bool> for BitVec { + fn from_iter<I: IntoIterator<Item=bool>>(iter: I) -> BitVec { + let mut ret = BitVec::new(); + ret.extend(iter); ret } } #[stable(feature = "rust1", since = "1.0.0")] -impl Extend<bool> for Bitv { +impl Extend<bool> for BitVec { #[inline] - fn extend<I: Iterator<Item=bool>>(&mut self, iterator: I) { + fn extend<I: IntoIterator<Item=bool>>(&mut self, iterable: I) { + let iterator = iterable.into_iter(); let (min, _) = iterator.size_hint(); self.reserve(min); for element in iterator { @@ -944,37 +945,37 @@ impl Extend<bool> for Bitv { } #[stable(feature = "rust1", since = "1.0.0")] -impl Clone for Bitv { +impl Clone for BitVec { #[inline] - fn clone(&self) -> Bitv { - Bitv { storage: self.storage.clone(), nbits: self.nbits } + fn clone(&self) -> BitVec { + BitVec { storage: self.storage.clone(), nbits: self.nbits } } #[inline] - fn clone_from(&mut self, source: &Bitv) { + fn clone_from(&mut self, source: &BitVec) { self.nbits = source.nbits; self.storage.clone_from(&source.storage); } } #[stable(feature = "rust1", since = "1.0.0")] -impl PartialOrd for Bitv { +impl PartialOrd for BitVec { #[inline] - fn partial_cmp(&self, other: &Bitv) -> Option<Ordering> { + fn partial_cmp(&self, other: &BitVec) -> Option<Ordering> { iter::order::partial_cmp(self.iter(), other.iter()) } } #[stable(feature = "rust1", since = "1.0.0")] -impl Ord for Bitv { +impl Ord for BitVec { #[inline] - fn cmp(&self, other: &Bitv) -> Ordering { + fn cmp(&self, other: &BitVec) -> Ordering { iter::order::cmp(self.iter(), other.iter()) } } #[stable(feature = "rust1", since = "1.0.0")] -impl fmt::Debug for Bitv { +impl fmt::Debug for BitVec { fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { for bit in self { try!(write!(fmt, "{}", if bit { 1u32 } else { 0u32 })); @@ -984,7 +985,8 @@ impl fmt::Debug for Bitv { } #[stable(feature = "rust1", since = "1.0.0")] -impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for Bitv { +#[cfg(stage0)] +impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for BitVec { fn hash(&self, state: &mut S) { self.nbits.hash(state); for elem in self.blocks() { @@ -992,11 +994,21 @@ impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for Bitv { } } } +#[stable(feature = "rust1", since = "1.0.0")] +#[cfg(not(stage0))] +impl hash::Hash for BitVec { + fn hash<H: hash::Hasher>(&self, state: &mut H) { + self.nbits.hash(state); + for elem in self.blocks() { + elem.hash(state); + } + } +} #[stable(feature = "rust1", since = "1.0.0")] -impl cmp::PartialEq for Bitv { +impl cmp::PartialEq for BitVec { #[inline] - fn eq(&self, other: &Bitv) -> bool { + fn eq(&self, other: &BitVec) -> bool { if self.nbits != other.nbits { return false; } @@ -1005,13 +1017,13 @@ impl cmp::PartialEq for Bitv { } #[stable(feature = "rust1", since = "1.0.0")] -impl cmp::Eq for Bitv {} +impl cmp::Eq for BitVec {} -/// An iterator for `Bitv`. +/// An iterator for `BitVec`. #[stable(feature = "rust1", since = "1.0.0")] #[derive(Clone)] pub struct Iter<'a> { - bitv: &'a Bitv, + bit_vec: &'a BitVec, next_idx: usize, end_idx: usize, } @@ -1025,7 +1037,7 @@ impl<'a> Iterator for Iter<'a> { if self.next_idx != self.end_idx { let idx = self.next_idx; self.next_idx += 1; - Some(self.bitv[idx]) + Some(self.bit_vec[idx]) } else { None } @@ -1043,7 +1055,7 @@ impl<'a> DoubleEndedIterator for Iter<'a> { fn next_back(&mut self) -> Option<bool> { if self.next_idx != self.end_idx { self.end_idx -= 1; - Some(self.bitv[self.end_idx]) + Some(self.bit_vec[self.end_idx]) } else { None } @@ -1065,13 +1077,13 @@ impl<'a> RandomAccessIterator for Iter<'a> { if index >= self.indexable() { None } else { - Some(self.bitv[index]) + Some(self.bit_vec[index]) } } } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a> IntoIterator for &'a Bitv { +impl<'a> IntoIterator for &'a BitVec { type Item = bool; type IntoIter = Iter<'a>; @@ -1090,10 +1102,10 @@ impl<'a> IntoIterator for &'a Bitv { /// # Examples /// /// ``` -/// use std::collections::{BitvSet, Bitv}; +/// use std::collections::{BitSet, BitVec}; /// /// // It's a regular set -/// let mut s = BitvSet::new(); +/// let mut s = BitSet::new(); /// s.insert(0); /// s.insert(3); /// s.insert(7); @@ -1104,8 +1116,8 @@ impl<'a> IntoIterator for &'a Bitv { /// println!("There is no 7"); /// } /// -/// // Can initialize from a `Bitv` -/// let other = BitvSet::from_bitv(Bitv::from_bytes(&[0b11010000])); +/// // Can initialize from a `BitVec` +/// let other = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11010000])); /// /// s.union_with(&other); /// @@ -1114,115 +1126,115 @@ impl<'a> IntoIterator for &'a Bitv { /// println!("{}", x); /// } /// -/// // Can convert back to a `Bitv` -/// let bv: Bitv = s.into_bitv(); +/// // Can convert back to a `BitVec` +/// let bv: BitVec = s.into_bit_vec(); /// assert!(bv[3]); /// ``` #[derive(Clone)] #[unstable(feature = "collections", reason = "RFC 509")] -pub struct BitvSet { - bitv: Bitv, +pub struct BitSet { + bit_vec: BitVec, } #[stable(feature = "rust1", since = "1.0.0")] -impl Default for BitvSet { +impl Default for BitSet { #[inline] - fn default() -> BitvSet { BitvSet::new() } + fn default() -> BitSet { BitSet::new() } } #[stable(feature = "rust1", since = "1.0.0")] -impl FromIterator<usize> for BitvSet { - fn from_iter<I:Iterator<Item=usize>>(iterator: I) -> BitvSet { - let mut ret = BitvSet::new(); - ret.extend(iterator); +impl FromIterator<usize> for BitSet { + fn from_iter<I: IntoIterator<Item=usize>>(iter: I) -> BitSet { + let mut ret = BitSet::new(); + ret.extend(iter); ret } } #[stable(feature = "rust1", since = "1.0.0")] -impl Extend<usize> for BitvSet { +impl Extend<usize> for BitSet { #[inline] - fn extend<I: Iterator<Item=usize>>(&mut self, iterator: I) { - for i in iterator { + fn extend<I: IntoIterator<Item=usize>>(&mut self, iter: I) { + for i in iter { self.insert(i); } } } #[stable(feature = "rust1", since = "1.0.0")] -impl PartialOrd for BitvSet { +impl PartialOrd for BitSet { #[inline] - fn partial_cmp(&self, other: &BitvSet) -> Option<Ordering> { + fn partial_cmp(&self, other: &BitSet) -> Option<Ordering> { let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref()); iter::order::partial_cmp(a_iter, b_iter) } } #[stable(feature = "rust1", since = "1.0.0")] -impl Ord for BitvSet { +impl Ord for BitSet { #[inline] - fn cmp(&self, other: &BitvSet) -> Ordering { + fn cmp(&self, other: &BitSet) -> Ordering { let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref()); iter::order::cmp(a_iter, b_iter) } } #[stable(feature = "rust1", since = "1.0.0")] -impl cmp::PartialEq for BitvSet { +impl cmp::PartialEq for BitSet { #[inline] - fn eq(&self, other: &BitvSet) -> bool { + fn eq(&self, other: &BitSet) -> bool { let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref()); iter::order::eq(a_iter, b_iter) } } #[stable(feature = "rust1", since = "1.0.0")] -impl cmp::Eq for BitvSet {} +impl cmp::Eq for BitSet {} -impl BitvSet { - /// Creates a new empty `BitvSet`. +impl BitSet { + /// Creates a new empty `BitSet`. /// /// # Examples /// /// ``` - /// use std::collections::BitvSet; + /// use std::collections::BitSet; /// - /// let mut s = BitvSet::new(); + /// let mut s = BitSet::new(); /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn new() -> BitvSet { - BitvSet { bitv: Bitv::new() } + pub fn new() -> BitSet { + BitSet { bit_vec: BitVec::new() } } - /// Creates a new `BitvSet` with initially no contents, able to + /// Creates a new `BitSet` with initially no contents, able to /// hold `nbits` elements without resizing. /// /// # Examples /// /// ``` - /// use std::collections::BitvSet; + /// use std::collections::BitSet; /// - /// let mut s = BitvSet::with_capacity(100); + /// let mut s = BitSet::with_capacity(100); /// assert!(s.capacity() >= 100); /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn with_capacity(nbits: usize) -> BitvSet { - let bitv = Bitv::from_elem(nbits, false); - BitvSet::from_bitv(bitv) + pub fn with_capacity(nbits: usize) -> BitSet { + let bit_vec = BitVec::from_elem(nbits, false); + BitSet::from_bit_vec(bit_vec) } - /// Creates a new `BitvSet` from the given bit vector. + /// Creates a new `BitSet` from the given bit vector. /// /// # Examples /// /// ``` - /// use std::collections::{Bitv, BitvSet}; + /// use std::collections::{BitVec, BitSet}; /// - /// let bv = Bitv::from_bytes(&[0b01100000]); - /// let s = BitvSet::from_bitv(bv); + /// let bv = BitVec::from_bytes(&[0b01100000]); + /// let s = BitSet::from_bit_vec(bv); /// /// // Print 1, 2 in arbitrary order /// for x in s.iter() { @@ -1230,8 +1242,16 @@ impl BitvSet { /// } /// ``` #[inline] - pub fn from_bitv(bitv: Bitv) -> BitvSet { - BitvSet { bitv: bitv } + pub fn from_bit_vec(bit_vec: BitVec) -> BitSet { + BitSet { bit_vec: bit_vec } + } + + /// Deprecated: use `from_bit_vec`. + #[inline] + #[deprecated(since = "1.0.0", reason = "renamed to from_bit_vec")] + #[unstable(feature = "collections")] + pub fn from_bitv(bit_vec: BitVec) -> BitSet { + BitSet { bit_vec: bit_vec } } /// Returns the capacity in bits for this bit vector. Inserting any @@ -1240,19 +1260,19 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::BitvSet; + /// use std::collections::BitSet; /// - /// let mut s = BitvSet::with_capacity(100); + /// let mut s = BitSet::with_capacity(100); /// assert!(s.capacity() >= 100); /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn capacity(&self) -> usize { - self.bitv.capacity() + self.bit_vec.capacity() } - /// Reserves capacity for the given `BitvSet` to contain `len` distinct elements. In the case - /// of `BitvSet` this means reallocations will not occur as long as all inserted elements + /// Reserves capacity for the given `BitSet` to contain `len` distinct elements. In the case + /// of `BitSet` this means reallocations will not occur as long as all inserted elements /// are less than `len`. /// /// The collection may reserve more space to avoid frequent reallocations. @@ -1261,22 +1281,22 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::BitvSet; + /// use std::collections::BitSet; /// - /// let mut s = BitvSet::new(); + /// let mut s = BitSet::new(); /// s.reserve_len(10); /// assert!(s.capacity() >= 10); /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn reserve_len(&mut self, len: usize) { - let cur_len = self.bitv.len(); + let cur_len = self.bit_vec.len(); if len >= cur_len { - self.bitv.reserve(len - cur_len); + self.bit_vec.reserve(len - cur_len); } } - /// Reserves the minimum capacity for the given `BitvSet` to contain `len` distinct elements. - /// In the case of `BitvSet` this means reallocations will not occur as long as all inserted + /// Reserves the minimum capacity for the given `BitSet` to contain `len` distinct elements. + /// In the case of `BitSet` this means reallocations will not occur as long as all inserted /// elements are less than `len`. /// /// Note that the allocator may give the collection more space than it requests. Therefore @@ -1287,17 +1307,17 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::BitvSet; + /// use std::collections::BitSet; /// - /// let mut s = BitvSet::new(); + /// let mut s = BitSet::new(); /// s.reserve_len_exact(10); /// assert!(s.capacity() >= 10); /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn reserve_len_exact(&mut self, len: usize) { - let cur_len = self.bitv.len(); + let cur_len = self.bit_vec.len(); if len >= cur_len { - self.bitv.reserve_exact(len - cur_len); + self.bit_vec.reserve_exact(len - cur_len); } } @@ -1307,19 +1327,19 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::BitvSet; + /// use std::collections::BitSet; /// - /// let mut s = BitvSet::new(); + /// let mut s = BitSet::new(); /// s.insert(0); /// s.insert(3); /// - /// let bv = s.into_bitv(); + /// let bv = s.into_bit_vec(); /// assert!(bv[0]); /// assert!(bv[3]); /// ``` #[inline] - pub fn into_bitv(self) -> Bitv { - self.bitv + pub fn into_bit_vec(self) -> BitVec { + self.bit_vec } /// Returns a reference to the underlying bit vector. @@ -1327,44 +1347,44 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::BitvSet; + /// use std::collections::BitSet; /// - /// let mut s = BitvSet::new(); + /// let mut s = BitSet::new(); /// s.insert(0); /// /// let bv = s.get_ref(); /// assert_eq!(bv[0], true); /// ``` #[inline] - pub fn get_ref(&self) -> &Bitv { - &self.bitv + pub fn get_ref(&self) -> &BitVec { + &self.bit_vec } #[inline] - fn other_op<F>(&mut self, other: &BitvSet, mut f: F) where F: FnMut(u32, u32) -> u32 { - // Unwrap Bitvs - let self_bitv = &mut self.bitv; - let other_bitv = &other.bitv; + fn other_op<F>(&mut self, other: &BitSet, mut f: F) where F: FnMut(u32, u32) -> u32 { + // Unwrap BitVecs + let self_bit_vec = &mut self.bit_vec; + let other_bit_vec = &other.bit_vec; - let self_len = self_bitv.len(); - let other_len = other_bitv.len(); + let self_len = self_bit_vec.len(); + let other_len = other_bit_vec.len(); // Expand the vector if necessary if self_len < other_len { - self_bitv.grow(other_len - self_len, false); + self_bit_vec.grow(other_len - self_len, false); } // virtually pad other with 0's for equal lengths let other_words = { - let (_, result) = match_words(self_bitv, other_bitv); + let (_, result) = match_words(self_bit_vec, other_bit_vec); result }; // Apply values found in other for (i, w) in other_words { - let old = self_bitv.storage[i]; + let old = self_bit_vec.storage[i]; let new = f(old, w); - self_bitv.storage[i] = new; + self_bit_vec.storage[i] = new; } } @@ -1373,9 +1393,9 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::BitvSet; + /// use std::collections::BitSet; /// - /// let mut s = BitvSet::new(); + /// let mut s = BitSet::new(); /// s.insert(32183231); /// s.remove(&32183231); /// @@ -1389,25 +1409,25 @@ impl BitvSet { #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn shrink_to_fit(&mut self) { - let bitv = &mut self.bitv; + let bit_vec = &mut self.bit_vec; // Obtain original length - let old_len = bitv.storage.len(); + let old_len = bit_vec.storage.len(); // Obtain coarse trailing zero length - let n = bitv.storage.iter().rev().take_while(|&&n| n == 0).count(); + let n = bit_vec.storage.iter().rev().take_while(|&&n| n == 0).count(); // Truncate let trunc_len = cmp::max(old_len - n, 1); - bitv.storage.truncate(trunc_len); - bitv.nbits = trunc_len * u32::BITS; + bit_vec.storage.truncate(trunc_len); + bit_vec.nbits = trunc_len * u32::BITS; } - /// Iterator over each u32 stored in the `BitvSet`. + /// Iterator over each u32 stored in the `BitSet`. /// /// # Examples /// /// ``` - /// use std::collections::{Bitv, BitvSet}; + /// use std::collections::{BitVec, BitSet}; /// - /// let s = BitvSet::from_bitv(Bitv::from_bytes(&[0b01001010])); + /// let s = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01001010])); /// /// // Print 1, 4, 6 in arbitrary order /// for x in s.iter() { @@ -1416,7 +1436,7 @@ impl BitvSet { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn iter(&self) -> bitv_set::Iter { + pub fn iter(&self) -> bit_set::Iter { SetIter {set: self, next_idx: 0} } @@ -1426,10 +1446,10 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::{Bitv, BitvSet}; + /// use std::collections::{BitVec, BitSet}; /// - /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000])); - /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000])); + /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); + /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); /// /// // Print 0, 1, 2, 4 in arbitrary order /// for x in a.union(&b) { @@ -1438,7 +1458,7 @@ impl BitvSet { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn union<'a>(&'a self, other: &'a BitvSet) -> Union<'a> { + pub fn union<'a>(&'a self, other: &'a BitSet) -> Union<'a> { fn or(w1: u32, w2: u32) -> u32 { w1 | w2 } Union(TwoBitPositions { @@ -1456,10 +1476,10 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::{Bitv, BitvSet}; + /// use std::collections::{BitVec, BitSet}; /// - /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000])); - /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000])); + /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); + /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); /// /// // Print 2 /// for x in a.intersection(&b) { @@ -1468,9 +1488,9 @@ impl BitvSet { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Intersection<'a> { + pub fn intersection<'a>(&'a self, other: &'a BitSet) -> Intersection<'a> { fn bitand(w1: u32, w2: u32) -> u32 { w1 & w2 } - let min = cmp::min(self.bitv.len(), other.bitv.len()); + let min = cmp::min(self.bit_vec.len(), other.bit_vec.len()); Intersection(TwoBitPositions { set: self, other: other, @@ -1486,10 +1506,10 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::{BitvSet, Bitv}; + /// use std::collections::{BitSet, BitVec}; /// - /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000])); - /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000])); + /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); + /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); /// /// // Print 1, 4 in arbitrary order /// for x in a.difference(&b) { @@ -1505,7 +1525,7 @@ impl BitvSet { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn difference<'a>(&'a self, other: &'a BitvSet) -> Difference<'a> { + pub fn difference<'a>(&'a self, other: &'a BitSet) -> Difference<'a> { fn diff(w1: u32, w2: u32) -> u32 { w1 & !w2 } Difference(TwoBitPositions { @@ -1524,10 +1544,10 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::{BitvSet, Bitv}; + /// use std::collections::{BitSet, BitVec}; /// - /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000])); - /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000])); + /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); + /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); /// /// // Print 0, 1, 4 in arbitrary order /// for x in a.symmetric_difference(&b) { @@ -1536,7 +1556,7 @@ impl BitvSet { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> SymmetricDifference<'a> { + pub fn symmetric_difference<'a>(&'a self, other: &'a BitSet) -> SymmetricDifference<'a> { fn bitxor(w1: u32, w2: u32) -> u32 { w1 ^ w2 } SymmetricDifference(TwoBitPositions { @@ -1553,21 +1573,21 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::{BitvSet, Bitv}; + /// use std::collections::{BitSet, BitVec}; /// /// let a = 0b01101000; /// let b = 0b10100000; /// let res = 0b11101000; /// - /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a])); - /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b])); - /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res])); + /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a])); + /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b])); + /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res])); /// /// a.union_with(&b); /// assert_eq!(a, res); /// ``` #[inline] - pub fn union_with(&mut self, other: &BitvSet) { + pub fn union_with(&mut self, other: &BitSet) { self.other_op(other, |w1, w2| w1 | w2); } @@ -1576,21 +1596,21 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::{BitvSet, Bitv}; + /// use std::collections::{BitSet, BitVec}; /// /// let a = 0b01101000; /// let b = 0b10100000; /// let res = 0b00100000; /// - /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a])); - /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b])); - /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res])); + /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a])); + /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b])); + /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res])); /// /// a.intersect_with(&b); /// assert_eq!(a, res); /// ``` #[inline] - pub fn intersect_with(&mut self, other: &BitvSet) { + pub fn intersect_with(&mut self, other: &BitSet) { self.other_op(other, |w1, w2| w1 & w2); } @@ -1600,29 +1620,29 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::{BitvSet, Bitv}; + /// use std::collections::{BitSet, BitVec}; /// /// let a = 0b01101000; /// let b = 0b10100000; /// let a_b = 0b01001000; // a - b /// let b_a = 0b10000000; // b - a /// - /// let mut bva = BitvSet::from_bitv(Bitv::from_bytes(&[a])); - /// let bvb = BitvSet::from_bitv(Bitv::from_bytes(&[b])); - /// let bva_b = BitvSet::from_bitv(Bitv::from_bytes(&[a_b])); - /// let bvb_a = BitvSet::from_bitv(Bitv::from_bytes(&[b_a])); + /// let mut bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a])); + /// let bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b])); + /// let bva_b = BitSet::from_bit_vec(BitVec::from_bytes(&[a_b])); + /// let bvb_a = BitSet::from_bit_vec(BitVec::from_bytes(&[b_a])); /// /// bva.difference_with(&bvb); /// assert_eq!(bva, bva_b); /// - /// let bva = BitvSet::from_bitv(Bitv::from_bytes(&[a])); - /// let mut bvb = BitvSet::from_bitv(Bitv::from_bytes(&[b])); + /// let bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a])); + /// let mut bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b])); /// /// bvb.difference_with(&bva); /// assert_eq!(bvb, bvb_a); /// ``` #[inline] - pub fn difference_with(&mut self, other: &BitvSet) { + pub fn difference_with(&mut self, other: &BitSet) { self.other_op(other, |w1, w2| w1 & !w2); } @@ -1632,21 +1652,21 @@ impl BitvSet { /// # Examples /// /// ``` - /// use std::collections::{BitvSet, Bitv}; + /// use std::collections::{BitSet, BitVec}; /// /// let a = 0b01101000; /// let b = 0b10100000; /// let res = 0b11001000; /// - /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a])); - /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b])); - /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res])); + /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a])); + /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b])); + /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res])); /// /// a.symmetric_difference_with(&b); /// assert_eq!(a, res); /// ``` #[inline] - pub fn symmetric_difference_with(&mut self, other: &BitvSet) { + pub fn symmetric_difference_with(&mut self, other: &BitSet) { self.other_op(other, |w1, w2| w1 ^ w2); } @@ -1654,57 +1674,57 @@ impl BitvSet { #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn len(&self) -> usize { - self.bitv.blocks().fold(0, |acc, n| acc + n.count_ones()) + self.bit_vec.blocks().fold(0, |acc, n| acc + n.count_ones()) } /// Returns whether there are no bits set in this set #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn is_empty(&self) -> bool { - self.bitv.none() + self.bit_vec.none() } /// Clears all bits in this set #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn clear(&mut self) { - self.bitv.clear(); + self.bit_vec.clear(); } /// Returns `true` if this set contains the specified integer. #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn contains(&self, value: &usize) -> bool { - let bitv = &self.bitv; - *value < bitv.nbits && bitv[*value] + let bit_vec = &self.bit_vec; + *value < bit_vec.nbits && bit_vec[*value] } /// Returns `true` if the set has no elements in common with `other`. /// This is equivalent to checking for an empty intersection. #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_disjoint(&self, other: &BitvSet) -> bool { + pub fn is_disjoint(&self, other: &BitSet) -> bool { self.intersection(other).next().is_none() } /// Returns `true` if the set is a subset of another. #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_subset(&self, other: &BitvSet) -> bool { - let self_bitv = &self.bitv; - let other_bitv = &other.bitv; - let other_blocks = blocks_for_bits(other_bitv.len()); + pub fn is_subset(&self, other: &BitSet) -> bool { + let self_bit_vec = &self.bit_vec; + let other_bit_vec = &other.bit_vec; + let other_blocks = blocks_for_bits(other_bit_vec.len()); // Check that `self` intersect `other` is self - self_bitv.blocks().zip(other_bitv.blocks()).all(|(w1, w2)| w1 & w2 == w1) && + self_bit_vec.blocks().zip(other_bit_vec.blocks()).all(|(w1, w2)| w1 & w2 == w1) && // Make sure if `self` has any more blocks than `other`, they're all 0 - self_bitv.blocks().skip(other_blocks).all(|w| w == 0) + self_bit_vec.blocks().skip(other_blocks).all(|w| w == 0) } /// Returns `true` if the set is a superset of another. #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_superset(&self, other: &BitvSet) -> bool { + pub fn is_superset(&self, other: &BitSet) -> bool { other.is_subset(self) } @@ -1717,12 +1737,12 @@ impl BitvSet { } // Ensure we have enough space to hold the new element - let len = self.bitv.len(); + let len = self.bit_vec.len(); if value >= len { - self.bitv.grow(value - len + 1, false) + self.bit_vec.grow(value - len + 1, false) } - self.bitv.set(value, true); + self.bit_vec.set(value, true); return true; } @@ -1734,16 +1754,16 @@ impl BitvSet { return false; } - self.bitv.set(*value, false); + self.bit_vec.set(*value, false); return true; } } #[stable(feature = "rust1", since = "1.0.0")] -impl fmt::Debug for BitvSet { +impl fmt::Debug for BitSet { fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { - try!(write!(fmt, "BitvSet {{")); + try!(write!(fmt, "BitSet {{")); let mut first = true; for n in self { if !first { @@ -1756,27 +1776,37 @@ impl fmt::Debug for BitvSet { } } -impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for BitvSet { +#[cfg(stage0)] +impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for BitSet { fn hash(&self, state: &mut S) { for pos in self { pos.hash(state); } } } +#[stable(feature = "rust1", since = "1.0.0")] +#[cfg(not(stage0))] +impl hash::Hash for BitSet { + fn hash<H: hash::Hasher>(&self, state: &mut H) { + for pos in self { + pos.hash(state); + } + } +} -/// An iterator for `BitvSet`. +/// An iterator for `BitSet`. #[derive(Clone)] #[stable(feature = "rust1", since = "1.0.0")] pub struct SetIter<'a> { - set: &'a BitvSet, + set: &'a BitSet, next_idx: usize } -/// An iterator combining two `BitvSet` iterators. +/// An iterator combining two `BitSet` iterators. #[derive(Clone)] struct TwoBitPositions<'a> { - set: &'a BitvSet, - other: &'a BitvSet, + set: &'a BitSet, + other: &'a BitSet, merge: fn(u32, u32) -> u32, current_word: u32, next_idx: usize @@ -1796,7 +1826,7 @@ impl<'a> Iterator for SetIter<'a> { type Item = usize; fn next(&mut self) -> Option<usize> { - while self.next_idx < self.set.bitv.len() { + while self.next_idx < self.set.bit_vec.len() { let idx = self.next_idx; self.next_idx += 1; @@ -1810,7 +1840,7 @@ impl<'a> Iterator for SetIter<'a> { #[inline] fn size_hint(&self) -> (usize, Option<usize>) { - (0, Some(self.set.bitv.len() - self.next_idx)) + (0, Some(self.set.bit_vec.len() - self.next_idx)) } } @@ -1819,20 +1849,20 @@ impl<'a> Iterator for TwoBitPositions<'a> { type Item = usize; fn next(&mut self) -> Option<usize> { - while self.next_idx < self.set.bitv.len() || - self.next_idx < self.other.bitv.len() { + while self.next_idx < self.set.bit_vec.len() || + self.next_idx < self.other.bit_vec.len() { let bit_idx = self.next_idx % u32::BITS; if bit_idx == 0 { - let s_bitv = &self.set.bitv; - let o_bitv = &self.other.bitv; + let s_bit_vec = &self.set.bit_vec; + let o_bit_vec = &self.other.bit_vec; // Merging the two words is a bit of an awkward dance since - // one Bitv might be longer than the other + // one BitVec might be longer than the other let word_idx = self.next_idx / u32::BITS; - let w1 = if word_idx < s_bitv.storage.len() { - s_bitv.storage[word_idx] + let w1 = if word_idx < s_bit_vec.storage.len() { + s_bit_vec.storage[word_idx] } else { 0 }; - let w2 = if word_idx < o_bitv.storage.len() { - o_bitv.storage[word_idx] + let w2 = if word_idx < o_bit_vec.storage.len() { + o_bit_vec.storage[word_idx] } else { 0 }; self.current_word = (self.merge)(w1, w2); } @@ -1847,7 +1877,7 @@ impl<'a> Iterator for TwoBitPositions<'a> { #[inline] fn size_hint(&self) -> (usize, Option<usize>) { - let cap = cmp::max(self.set.bitv.len(), self.other.bitv.len()); + let cap = cmp::max(self.set.bit_vec.len(), self.other.bit_vec.len()); (0, Some(cap - self.next_idx)) } } @@ -1885,7 +1915,7 @@ impl<'a> Iterator for SymmetricDifference<'a> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a> IntoIterator for &'a BitvSet { +impl<'a> IntoIterator for &'a BitSet { type Item = usize; type IntoIter = SetIter<'a>; @@ -1899,20 +1929,20 @@ mod tests { use prelude::*; use core::u32; - use super::Bitv; + use super::BitVec; #[test] fn test_to_str() { - let zerolen = Bitv::new(); + let zerolen = BitVec::new(); assert_eq!(format!("{:?}", zerolen), ""); - let eightbits = Bitv::from_elem(8, false); + let eightbits = BitVec::from_elem(8, false); assert_eq!(format!("{:?}", eightbits), "00000000") } #[test] fn test_0_elements() { - let act = Bitv::new(); + let act = BitVec::new(); let exp = Vec::new(); assert!(act.eq_vec(&exp)); assert!(act.none() && act.all()); @@ -1920,17 +1950,17 @@ mod tests { #[test] fn test_1_element() { - let mut act = Bitv::from_elem(1, false); + let mut act = BitVec::from_elem(1, false); assert!(act.eq_vec(&[false])); assert!(act.none() && !act.all()); - act = Bitv::from_elem(1, true); + act = BitVec::from_elem(1, true); assert!(act.eq_vec(&[true])); assert!(!act.none() && act.all()); } #[test] fn test_2_elements() { - let mut b = Bitv::from_elem(2, false); + let mut b = BitVec::from_elem(2, false); b.set(0, true); b.set(1, false); assert_eq!(format!("{:?}", b), "10"); @@ -1942,18 +1972,18 @@ mod tests { let mut act; // all 0 - act = Bitv::from_elem(10, false); + act = BitVec::from_elem(10, false); assert!((act.eq_vec( &[false, false, false, false, false, false, false, false, false, false]))); assert!(act.none() && !act.all()); // all 1 - act = Bitv::from_elem(10, true); + act = BitVec::from_elem(10, true); assert!((act.eq_vec(&[true, true, true, true, true, true, true, true, true, true]))); assert!(!act.none() && act.all()); // mixed - act = Bitv::from_elem(10, false); + act = BitVec::from_elem(10, false); act.set(0, true); act.set(1, true); act.set(2, true); @@ -1963,7 +1993,7 @@ mod tests { assert!(!act.none() && !act.all()); // mixed - act = Bitv::from_elem(10, false); + act = BitVec::from_elem(10, false); act.set(5, true); act.set(6, true); act.set(7, true); @@ -1973,7 +2003,7 @@ mod tests { assert!(!act.none() && !act.all()); // mixed - act = Bitv::from_elem(10, false); + act = BitVec::from_elem(10, false); act.set(0, true); act.set(3, true); act.set(6, true); @@ -1987,7 +2017,7 @@ mod tests { let mut act; // all 0 - act = Bitv::from_elem(31, false); + act = BitVec::from_elem(31, false); assert!(act.eq_vec( &[false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, @@ -1995,7 +2025,7 @@ mod tests { assert!(act.none() && !act.all()); // all 1 - act = Bitv::from_elem(31, true); + act = BitVec::from_elem(31, true); assert!(act.eq_vec( &[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, @@ -2003,7 +2033,7 @@ mod tests { assert!(!act.none() && act.all()); // mixed - act = Bitv::from_elem(31, false); + act = BitVec::from_elem(31, false); act.set(0, true); act.set(1, true); act.set(2, true); @@ -2019,7 +2049,7 @@ mod tests { assert!(!act.none() && !act.all()); // mixed - act = Bitv::from_elem(31, false); + act = BitVec::from_elem(31, false); act.set(16, true); act.set(17, true); act.set(18, true); @@ -2035,7 +2065,7 @@ mod tests { assert!(!act.none() && !act.all()); // mixed - act = Bitv::from_elem(31, false); + act = BitVec::from_elem(31, false); act.set(24, true); act.set(25, true); act.set(26, true); @@ -2050,7 +2080,7 @@ mod tests { assert!(!act.none() && !act.all()); // mixed - act = Bitv::from_elem(31, false); + act = BitVec::from_elem(31, false); act.set(3, true); act.set(17, true); act.set(30, true); @@ -2066,7 +2096,7 @@ mod tests { let mut act; // all 0 - act = Bitv::from_elem(32, false); + act = BitVec::from_elem(32, false); assert!(act.eq_vec( &[false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, @@ -2074,7 +2104,7 @@ mod tests { assert!(act.none() && !act.all()); // all 1 - act = Bitv::from_elem(32, true); + act = BitVec::from_elem(32, true); assert!(act.eq_vec( &[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, @@ -2082,7 +2112,7 @@ mod tests { assert!(!act.none() && act.all()); // mixed - act = Bitv::from_elem(32, false); + act = BitVec::from_elem(32, false); act.set(0, true); act.set(1, true); act.set(2, true); @@ -2098,7 +2128,7 @@ mod tests { assert!(!act.none() && !act.all()); // mixed - act = Bitv::from_elem(32, false); + act = BitVec::from_elem(32, false); act.set(16, true); act.set(17, true); act.set(18, true); @@ -2114,7 +2144,7 @@ mod tests { assert!(!act.none() && !act.all()); // mixed - act = Bitv::from_elem(32, false); + act = BitVec::from_elem(32, false); act.set(24, true); act.set(25, true); act.set(26, true); @@ -2130,7 +2160,7 @@ mod tests { assert!(!act.none() && !act.all()); // mixed - act = Bitv::from_elem(32, false); + act = BitVec::from_elem(32, false); act.set(3, true); act.set(17, true); act.set(30, true); @@ -2147,7 +2177,7 @@ mod tests { let mut act; // all 0 - act = Bitv::from_elem(33, false); + act = BitVec::from_elem(33, false); assert!(act.eq_vec( &[false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, @@ -2155,7 +2185,7 @@ mod tests { assert!(act.none() && !act.all()); // all 1 - act = Bitv::from_elem(33, true); + act = BitVec::from_elem(33, true); assert!(act.eq_vec( &[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, @@ -2163,7 +2193,7 @@ mod tests { assert!(!act.none() && act.all()); // mixed - act = Bitv::from_elem(33, false); + act = BitVec::from_elem(33, false); act.set(0, true); act.set(1, true); act.set(2, true); @@ -2179,7 +2209,7 @@ mod tests { assert!(!act.none() && !act.all()); // mixed - act = Bitv::from_elem(33, false); + act = BitVec::from_elem(33, false); act.set(16, true); act.set(17, true); act.set(18, true); @@ -2195,7 +2225,7 @@ mod tests { assert!(!act.none() && !act.all()); // mixed - act = Bitv::from_elem(33, false); + act = BitVec::from_elem(33, false); act.set(24, true); act.set(25, true); act.set(26, true); @@ -2211,7 +2241,7 @@ mod tests { assert!(!act.none() && !act.all()); // mixed - act = Bitv::from_elem(33, false); + act = BitVec::from_elem(33, false); act.set(3, true); act.set(17, true); act.set(30, true); @@ -2226,24 +2256,24 @@ mod tests { #[test] fn test_equal_differing_sizes() { - let v0 = Bitv::from_elem(10, false); - let v1 = Bitv::from_elem(11, false); + let v0 = BitVec::from_elem(10, false); + let v1 = BitVec::from_elem(11, false); assert!(v0 != v1); } #[test] fn test_equal_greatly_differing_sizes() { - let v0 = Bitv::from_elem(10, false); - let v1 = Bitv::from_elem(110, false); + let v0 = BitVec::from_elem(10, false); + let v1 = BitVec::from_elem(110, false); assert!(v0 != v1); } #[test] fn test_equal_sneaky_small() { - let mut a = Bitv::from_elem(1, false); + let mut a = BitVec::from_elem(1, false); a.set(0, true); - let mut b = Bitv::from_elem(1, true); + let mut b = BitVec::from_elem(1, true); b.set(0, true); assert_eq!(a, b); @@ -2251,12 +2281,12 @@ mod tests { #[test] fn test_equal_sneaky_big() { - let mut a = Bitv::from_elem(100, false); + let mut a = BitVec::from_elem(100, false); for i in 0..100 { a.set(i, true); } - let mut b = Bitv::from_elem(100, true); + let mut b = BitVec::from_elem(100, true); for i in 0..100 { b.set(i, true); } @@ -2266,18 +2296,18 @@ mod tests { #[test] fn test_from_bytes() { - let bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111]); + let bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]); let str = concat!("10110110", "00000000", "11111111"); - assert_eq!(format!("{:?}", bitv), str); + assert_eq!(format!("{:?}", bit_vec), str); } #[test] fn test_to_bytes() { - let mut bv = Bitv::from_elem(3, true); + let mut bv = BitVec::from_elem(3, true); bv.set(1, false); assert_eq!(bv.to_bytes(), vec!(0b10100000)); - let mut bv = Bitv::from_elem(9, false); + let mut bv = BitVec::from_elem(9, false); bv.set(2, true); bv.set(8, true); assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000)); @@ -2286,32 +2316,32 @@ mod tests { #[test] fn test_from_bools() { let bools = vec![true, false, true, true]; - let bitv: Bitv = bools.iter().map(|n| *n).collect(); - assert_eq!(format!("{:?}", bitv), "1011"); + let bit_vec: BitVec = bools.iter().map(|n| *n).collect(); + assert_eq!(format!("{:?}", bit_vec), "1011"); } #[test] fn test_to_bools() { let bools = vec![false, false, true, false, false, true, true, false]; - assert_eq!(Bitv::from_bytes(&[0b00100110]).iter().collect::<Vec<bool>>(), bools); + assert_eq!(BitVec::from_bytes(&[0b00100110]).iter().collect::<Vec<bool>>(), bools); } #[test] - fn test_bitv_iterator() { + fn test_bit_vec_iterator() { let bools = vec![true, false, true, true]; - let bitv: Bitv = bools.iter().map(|n| *n).collect(); + let bit_vec: BitVec = bools.iter().map(|n| *n).collect(); - assert_eq!(bitv.iter().collect::<Vec<bool>>(), bools); + assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), bools); let long: Vec<_> = (0i32..10000).map(|i| i % 2 == 0).collect(); - let bitv: Bitv = long.iter().map(|n| *n).collect(); - assert_eq!(bitv.iter().collect::<Vec<bool>>(), long) + let bit_vec: BitVec = long.iter().map(|n| *n).collect(); + assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), long) } #[test] fn test_small_difference() { - let mut b1 = Bitv::from_elem(3, false); - let mut b2 = Bitv::from_elem(3, false); + let mut b1 = BitVec::from_elem(3, false); + let mut b2 = BitVec::from_elem(3, false); b1.set(0, true); b1.set(1, true); b2.set(1, true); @@ -2324,8 +2354,8 @@ mod tests { #[test] fn test_big_difference() { - let mut b1 = Bitv::from_elem(100, false); - let mut b2 = Bitv::from_elem(100, false); + let mut b1 = BitVec::from_elem(100, false); + let mut b2 = BitVec::from_elem(100, false); b1.set(0, true); b1.set(40, true); b2.set(40, true); @@ -2338,7 +2368,7 @@ mod tests { #[test] fn test_small_clear() { - let mut b = Bitv::from_elem(14, true); + let mut b = BitVec::from_elem(14, true); assert!(!b.none() && b.all()); b.clear(); assert!(b.none() && !b.all()); @@ -2346,16 +2376,16 @@ mod tests { #[test] fn test_big_clear() { - let mut b = Bitv::from_elem(140, true); + let mut b = BitVec::from_elem(140, true); assert!(!b.none() && b.all()); b.clear(); assert!(b.none() && !b.all()); } #[test] - fn test_bitv_lt() { - let mut a = Bitv::from_elem(5, false); - let mut b = Bitv::from_elem(5, false); + fn test_bit_vec_lt() { + let mut a = BitVec::from_elem(5, false); + let mut b = BitVec::from_elem(5, false); assert!(!(a < b) && !(b < a)); b.set(2, true); @@ -2370,8 +2400,8 @@ mod tests { #[test] fn test_ord() { - let mut a = Bitv::from_elem(5, false); - let mut b = Bitv::from_elem(5, false); + let mut a = BitVec::from_elem(5, false); + let mut b = BitVec::from_elem(5, false); assert!(a <= b && a >= b); a.set(1, true); @@ -2385,26 +2415,26 @@ mod tests { #[test] - fn test_small_bitv_tests() { - let v = Bitv::from_bytes(&[0]); + fn test_small_bit_vec_tests() { + let v = BitVec::from_bytes(&[0]); assert!(!v.all()); assert!(!v.any()); assert!(v.none()); - let v = Bitv::from_bytes(&[0b00010100]); + let v = BitVec::from_bytes(&[0b00010100]); assert!(!v.all()); assert!(v.any()); assert!(!v.none()); - let v = Bitv::from_bytes(&[0xFF]); + let v = BitVec::from_bytes(&[0xFF]); assert!(v.all()); assert!(v.any()); assert!(!v.none()); } #[test] - fn test_big_bitv_tests() { - let v = Bitv::from_bytes(&[ // 88 bits + fn test_big_bit_vec_tests() { + let v = BitVec::from_bytes(&[ // 88 bits 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]); @@ -2412,7 +2442,7 @@ mod tests { assert!(!v.any()); assert!(v.none()); - let v = Bitv::from_bytes(&[ // 88 bits + let v = BitVec::from_bytes(&[ // 88 bits 0, 0, 0b00010100, 0, 0, 0, 0, 0b00110100, 0, 0, 0]); @@ -2420,7 +2450,7 @@ mod tests { assert!(v.any()); assert!(!v.none()); - let v = Bitv::from_bytes(&[ // 88 bits + let v = BitVec::from_bytes(&[ // 88 bits 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF]); @@ -2430,8 +2460,8 @@ mod tests { } #[test] - fn test_bitv_push_pop() { - let mut s = Bitv::from_elem(5 * u32::BITS - 2, false); + fn test_bit_vec_push_pop() { + let mut s = BitVec::from_elem(5 * u32::BITS - 2, false); assert_eq!(s.len(), 5 * u32::BITS - 2); assert_eq!(s[5 * u32::BITS - 3], false); s.push(true); @@ -2453,29 +2483,29 @@ mod tests { } #[test] - fn test_bitv_truncate() { - let mut s = Bitv::from_elem(5 * u32::BITS, true); + fn test_bit_vec_truncate() { + let mut s = BitVec::from_elem(5 * u32::BITS, true); - assert_eq!(s, Bitv::from_elem(5 * u32::BITS, true)); + assert_eq!(s, BitVec::from_elem(5 * u32::BITS, true)); assert_eq!(s.len(), 5 * u32::BITS); s.truncate(4 * u32::BITS); - assert_eq!(s, Bitv::from_elem(4 * u32::BITS, true)); + assert_eq!(s, BitVec::from_elem(4 * u32::BITS, true)); assert_eq!(s.len(), 4 * u32::BITS); // Truncating to a size > s.len() should be a noop s.truncate(5 * u32::BITS); - assert_eq!(s, Bitv::from_elem(4 * u32::BITS, true)); + assert_eq!(s, BitVec::from_elem(4 * u32::BITS, true)); assert_eq!(s.len(), 4 * u32::BITS); s.truncate(3 * u32::BITS - 10); - assert_eq!(s, Bitv::from_elem(3 * u32::BITS - 10, true)); + assert_eq!(s, BitVec::from_elem(3 * u32::BITS - 10, true)); assert_eq!(s.len(), 3 * u32::BITS - 10); s.truncate(0); - assert_eq!(s, Bitv::from_elem(0, true)); + assert_eq!(s, BitVec::from_elem(0, true)); assert_eq!(s.len(), 0); } #[test] - fn test_bitv_reserve() { - let mut s = Bitv::from_elem(5 * u32::BITS, true); + fn test_bit_vec_reserve() { + let mut s = BitVec::from_elem(5 * u32::BITS, true); // Check capacity assert!(s.capacity() >= 5 * u32::BITS); s.reserve(2 * u32::BITS); @@ -2498,25 +2528,25 @@ mod tests { } #[test] - fn test_bitv_grow() { - let mut bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010]); - bitv.grow(32, true); - assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010, + fn test_bit_vec_grow() { + let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010]); + bit_vec.grow(32, true); + assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010, 0xFF, 0xFF, 0xFF, 0xFF])); - bitv.grow(64, false); - assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010, + bit_vec.grow(64, false); + assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010, 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0])); - bitv.grow(16, true); - assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010, + bit_vec.grow(16, true); + assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010, 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF])); } #[test] - fn test_bitv_extend() { - let mut bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111]); - let ext = Bitv::from_bytes(&[0b01001001, 0b10010010, 0b10111101]); - bitv.extend(ext.iter()); - assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111, + fn test_bit_vec_extend() { + let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]); + let ext = BitVec::from_bytes(&[0b01001001, 0b10010010, 0b10111101]); + bit_vec.extend(ext.iter()); + assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111, 0b01001001, 0b10010010, 0b10111101])); } } @@ -2525,14 +2555,14 @@ mod tests { #[cfg(test)] -mod bitv_bench { +mod bit_vec_bench { use std::prelude::v1::*; use std::rand; use std::rand::Rng; use std::u32; use test::{Bencher, black_box}; - use super::Bitv; + use super::BitVec; static BENCH_BITS : usize = 1 << 14; @@ -2544,67 +2574,67 @@ mod bitv_bench { #[bench] fn bench_usize_small(b: &mut Bencher) { let mut r = rng(); - let mut bitv = 0 as usize; + let mut bit_vec = 0 as usize; b.iter(|| { for _ in 0..100 { - bitv |= 1 << ((r.next_u32() as usize) % u32::BITS); + bit_vec |= 1 << ((r.next_u32() as usize) % u32::BITS); } - black_box(&bitv); + black_box(&bit_vec); }); } #[bench] - fn bench_bitv_set_big_fixed(b: &mut Bencher) { + fn bench_bit_set_big_fixed(b: &mut Bencher) { let mut r = rng(); - let mut bitv = Bitv::from_elem(BENCH_BITS, false); + let mut bit_vec = BitVec::from_elem(BENCH_BITS, false); b.iter(|| { for _ in 0..100 { - bitv.set((r.next_u32() as usize) % BENCH_BITS, true); + bit_vec.set((r.next_u32() as usize) % BENCH_BITS, true); } - black_box(&bitv); + black_box(&bit_vec); }); } #[bench] - fn bench_bitv_set_big_variable(b: &mut Bencher) { + fn bench_bit_set_big_variable(b: &mut Bencher) { let mut r = rng(); - let mut bitv = Bitv::from_elem(BENCH_BITS, false); + let mut bit_vec = BitVec::from_elem(BENCH_BITS, false); b.iter(|| { for _ in 0..100 { - bitv.set((r.next_u32() as usize) % BENCH_BITS, r.gen()); + bit_vec.set((r.next_u32() as usize) % BENCH_BITS, r.gen()); } - black_box(&bitv); + black_box(&bit_vec); }); } #[bench] - fn bench_bitv_set_small(b: &mut Bencher) { + fn bench_bit_set_small(b: &mut Bencher) { let mut r = rng(); - let mut bitv = Bitv::from_elem(u32::BITS, false); + let mut bit_vec = BitVec::from_elem(u32::BITS, false); b.iter(|| { for _ in 0..100 { - bitv.set((r.next_u32() as usize) % u32::BITS, true); + bit_vec.set((r.next_u32() as usize) % u32::BITS, true); } - black_box(&bitv); + black_box(&bit_vec); }); } #[bench] - fn bench_bitv_big_union(b: &mut Bencher) { - let mut b1 = Bitv::from_elem(BENCH_BITS, false); - let b2 = Bitv::from_elem(BENCH_BITS, false); + fn bench_bit_vec_big_union(b: &mut Bencher) { + let mut b1 = BitVec::from_elem(BENCH_BITS, false); + let b2 = BitVec::from_elem(BENCH_BITS, false); b.iter(|| { b1.union(&b2) }) } #[bench] - fn bench_bitv_small_iter(b: &mut Bencher) { - let bitv = Bitv::from_elem(u32::BITS, false); + fn bench_bit_vec_small_iter(b: &mut Bencher) { + let bit_vec = BitVec::from_elem(u32::BITS, false); b.iter(|| { let mut sum = 0; for _ in 0..10 { - for pres in &bitv { + for pres in &bit_vec { sum += pres as usize; } } @@ -2613,11 +2643,11 @@ mod bitv_bench { } #[bench] - fn bench_bitv_big_iter(b: &mut Bencher) { - let bitv = Bitv::from_elem(BENCH_BITS, false); + fn bench_bit_vec_big_iter(b: &mut Bencher) { + let bit_vec = BitVec::from_elem(BENCH_BITS, false); b.iter(|| { let mut sum = 0; - for pres in &bitv { + for pres in &bit_vec { sum += pres as usize; } sum @@ -2632,27 +2662,27 @@ mod bitv_bench { #[cfg(test)] -mod bitv_set_test { +mod bit_set_test { use prelude::*; use std::iter::range_step; - use super::{Bitv, BitvSet}; + use super::{BitVec, BitSet}; #[test] - fn test_bitv_set_show() { - let mut s = BitvSet::new(); + fn test_bit_set_show() { + let mut s = BitSet::new(); s.insert(1); s.insert(10); s.insert(50); s.insert(2); - assert_eq!("BitvSet {1, 2, 10, 50}", format!("{:?}", s)); + assert_eq!("BitSet {1, 2, 10, 50}", format!("{:?}", s)); } #[test] - fn test_bitv_set_from_usizes() { + fn test_bit_set_from_usizes() { let usizes = vec![0, 2, 2, 3]; - let a: BitvSet = usizes.into_iter().collect(); - let mut b = BitvSet::new(); + let a: BitSet = usizes.into_iter().collect(); + let mut b = BitSet::new(); b.insert(0); b.insert(2); b.insert(3); @@ -2660,14 +2690,14 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_iterator() { + fn test_bit_set_iterator() { let usizes = vec![0, 2, 2, 3]; - let bitv: BitvSet = usizes.into_iter().collect(); + let bit_vec: BitSet = usizes.into_iter().collect(); - let idxs: Vec<_> = bitv.iter().collect(); + let idxs: Vec<_> = bit_vec.iter().collect(); assert_eq!(idxs, vec![0, 2, 3]); - let long: BitvSet = (0..10000).filter(|&n| n % 2 == 0).collect(); + let long: BitSet = (0..10000).filter(|&n| n % 2 == 0).collect(); let real: Vec<_> = range_step(0, 10000, 2).collect(); let idxs: Vec<_> = long.iter().collect(); @@ -2675,12 +2705,12 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_frombitv_init() { + fn test_bit_set_frombit_vec_init() { let bools = [true, false]; let lengths = [10, 64, 100]; for &b in &bools { for &l in &lengths { - let bitset = BitvSet::from_bitv(Bitv::from_elem(l, b)); + let bitset = BitSet::from_bit_vec(BitVec::from_elem(l, b)); assert_eq!(bitset.contains(&1), b); assert_eq!(bitset.contains(&(l-1)), b); assert!(!bitset.contains(&l)); @@ -2689,9 +2719,9 @@ mod bitv_set_test { } #[test] - fn test_bitv_masking() { - let b = Bitv::from_elem(140, true); - let mut bs = BitvSet::from_bitv(b); + fn test_bit_vec_masking() { + let b = BitVec::from_elem(140, true); + let mut bs = BitSet::from_bit_vec(b); assert!(bs.contains(&139)); assert!(!bs.contains(&140)); assert!(bs.insert(150)); @@ -2702,8 +2732,8 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_basic() { - let mut b = BitvSet::new(); + fn test_bit_set_basic() { + let mut b = BitSet::new(); assert!(b.insert(3)); assert!(!b.insert(3)); assert!(b.contains(&3)); @@ -2717,9 +2747,9 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_intersection() { - let mut a = BitvSet::new(); - let mut b = BitvSet::new(); + fn test_bit_set_intersection() { + let mut a = BitSet::new(); + let mut b = BitSet::new(); assert!(a.insert(11)); assert!(a.insert(1)); @@ -2740,9 +2770,9 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_difference() { - let mut a = BitvSet::new(); - let mut b = BitvSet::new(); + fn test_bit_set_difference() { + let mut a = BitSet::new(); + let mut b = BitSet::new(); assert!(a.insert(1)); assert!(a.insert(3)); @@ -2759,9 +2789,9 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_symmetric_difference() { - let mut a = BitvSet::new(); - let mut b = BitvSet::new(); + fn test_bit_set_symmetric_difference() { + let mut a = BitSet::new(); + let mut b = BitSet::new(); assert!(a.insert(1)); assert!(a.insert(3)); @@ -2780,9 +2810,9 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_union() { - let mut a = BitvSet::new(); - let mut b = BitvSet::new(); + fn test_bit_set_union() { + let mut a = BitSet::new(); + let mut b = BitSet::new(); assert!(a.insert(1)); assert!(a.insert(3)); assert!(a.insert(5)); @@ -2805,9 +2835,9 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_subset() { - let mut set1 = BitvSet::new(); - let mut set2 = BitvSet::new(); + fn test_bit_set_subset() { + let mut set1 = BitSet::new(); + let mut set2 = BitSet::new(); assert!(set1.is_subset(&set2)); // {} {} set2.insert(100); @@ -2831,11 +2861,11 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_is_disjoint() { - let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010])); - let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01000000])); - let c = BitvSet::new(); - let d = BitvSet::from_bitv(Bitv::from_bytes(&[0b00110000])); + fn test_bit_set_is_disjoint() { + let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010])); + let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01000000])); + let c = BitSet::new(); + let d = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00110000])); assert!(!a.is_disjoint(&d)); assert!(!d.is_disjoint(&a)); @@ -2849,19 +2879,19 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_union_with() { + fn test_bit_set_union_with() { //a should grow to include larger elements - let mut a = BitvSet::new(); + let mut a = BitSet::new(); a.insert(0); - let mut b = BitvSet::new(); + let mut b = BitSet::new(); b.insert(5); - let expected = BitvSet::from_bitv(Bitv::from_bytes(&[0b10000100])); + let expected = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10000100])); a.union_with(&b); assert_eq!(a, expected); // Standard - let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010])); - let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010])); + let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010])); + let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010])); let c = a.clone(); a.union_with(&b); b.union_with(&c); @@ -2870,10 +2900,10 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_intersect_with() { + fn test_bit_set_intersect_with() { // Explicitly 0'ed bits - let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010])); - let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000])); + let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010])); + let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000])); let c = a.clone(); a.intersect_with(&b); b.intersect_with(&c); @@ -2881,8 +2911,8 @@ mod bitv_set_test { assert!(b.is_empty()); // Uninitialized bits should behave like 0's - let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010])); - let mut b = BitvSet::new(); + let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010])); + let mut b = BitSet::new(); let c = a.clone(); a.intersect_with(&b); b.intersect_with(&c); @@ -2890,8 +2920,8 @@ mod bitv_set_test { assert!(b.is_empty()); // Standard - let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010])); - let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010])); + let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010])); + let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010])); let c = a.clone(); a.intersect_with(&b); b.intersect_with(&c); @@ -2900,22 +2930,22 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_difference_with() { + fn test_bit_set_difference_with() { // Explicitly 0'ed bits - let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000])); - let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010])); + let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000])); + let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010])); a.difference_with(&b); assert!(a.is_empty()); // Uninitialized bits should behave like 0's - let mut a = BitvSet::new(); - let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b11111111])); + let mut a = BitSet::new(); + let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11111111])); a.difference_with(&b); assert!(a.is_empty()); // Standard - let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010])); - let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010])); + let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010])); + let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010])); let c = a.clone(); a.difference_with(&b); b.difference_with(&c); @@ -2924,27 +2954,27 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_symmetric_difference_with() { + fn test_bit_set_symmetric_difference_with() { //a should grow to include larger elements - let mut a = BitvSet::new(); + let mut a = BitSet::new(); a.insert(0); a.insert(1); - let mut b = BitvSet::new(); + let mut b = BitSet::new(); b.insert(1); b.insert(5); - let expected = BitvSet::from_bitv(Bitv::from_bytes(&[0b10000100])); + let expected = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10000100])); a.symmetric_difference_with(&b); assert_eq!(a, expected); - let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010])); - let b = BitvSet::new(); + let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010])); + let b = BitSet::new(); let c = a.clone(); a.symmetric_difference_with(&b); assert_eq!(a, c); // Standard - let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b11100010])); - let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101010])); + let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11100010])); + let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101010])); let c = a.clone(); a.symmetric_difference_with(&b); b.symmetric_difference_with(&c); @@ -2953,10 +2983,10 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_eq() { - let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010])); - let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000])); - let c = BitvSet::new(); + fn test_bit_set_eq() { + let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010])); + let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000])); + let c = BitSet::new(); assert!(a == a); assert!(a != b); @@ -2967,10 +2997,10 @@ mod bitv_set_test { } #[test] - fn test_bitv_set_cmp() { - let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010])); - let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000])); - let c = BitvSet::new(); + fn test_bit_set_cmp() { + let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010])); + let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000])); + let c = BitSet::new(); assert_eq!(a.cmp(&b), Greater); assert_eq!(a.cmp(&c), Greater); @@ -2981,8 +3011,8 @@ mod bitv_set_test { } #[test] - fn test_bitv_remove() { - let mut a = BitvSet::new(); + fn test_bit_vec_remove() { + let mut a = BitSet::new(); assert!(a.insert(1)); assert!(a.remove(&1)); @@ -2996,8 +3026,8 @@ mod bitv_set_test { } #[test] - fn test_bitv_clone() { - let mut a = BitvSet::new(); + fn test_bit_vec_clone() { + let mut a = BitSet::new(); assert!(a.insert(1)); assert!(a.insert(100)); @@ -3020,14 +3050,14 @@ mod bitv_set_test { #[cfg(test)] -mod bitv_set_bench { +mod bit_set_bench { use std::prelude::v1::*; use std::rand; use std::rand::Rng; use std::u32; use test::{Bencher, black_box}; - use super::{Bitv, BitvSet}; + use super::{BitVec, BitSet}; static BENCH_BITS : usize = 1 << 14; @@ -3037,36 +3067,36 @@ mod bitv_set_bench { } #[bench] - fn bench_bitvset_small(b: &mut Bencher) { + fn bench_bit_vecset_small(b: &mut Bencher) { let mut r = rng(); - let mut bitv = BitvSet::new(); + let mut bit_vec = BitSet::new(); b.iter(|| { for _ in 0..100 { - bitv.insert((r.next_u32() as usize) % u32::BITS); + bit_vec.insert((r.next_u32() as usize) % u32::BITS); } - black_box(&bitv); + black_box(&bit_vec); }); } #[bench] - fn bench_bitvset_big(b: &mut Bencher) { + fn bench_bit_vecset_big(b: &mut Bencher) { let mut r = rng(); - let mut bitv = BitvSet::new(); + let mut bit_vec = BitSet::new(); b.iter(|| { for _ in 0..100 { - bitv.insert((r.next_u32() as usize) % BENCH_BITS); + bit_vec.insert((r.next_u32() as usize) % BENCH_BITS); } - black_box(&bitv); + black_box(&bit_vec); }); } #[bench] - fn bench_bitvset_iter(b: &mut Bencher) { - let bitv = BitvSet::from_bitv(Bitv::from_fn(BENCH_BITS, + fn bench_bit_vecset_iter(b: &mut Bencher) { + let bit_vec = BitSet::from_bit_vec(BitVec::from_fn(BENCH_BITS, |idx| {idx % 3 == 0})); b.iter(|| { let mut sum = 0; - for idx in &bitv { + for idx in &bit_vec { sum += idx as usize; } sum diff --git a/src/libcollections/borrow.rs b/src/libcollections/borrow.rs new file mode 100644 index 00000000000..901d7a73b51 --- /dev/null +++ b/src/libcollections/borrow.rs @@ -0,0 +1,316 @@ +// Copyright 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. + +//! A module for working with borrowed data. + +#![stable(feature = "rust1", since = "1.0.0")] + +use core::clone::Clone; +use core::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd}; +use core::hash::{Hash, Hasher}; +use core::marker::Sized; +use core::ops::Deref; +use core::option::Option; + +use fmt; +use alloc::{rc, arc}; + +use self::Cow::*; + +/// A trait for borrowing data. +/// +/// In general, there may be several ways to "borrow" a piece of data. The +/// typical ways of borrowing a type `T` are `&T` (a shared borrow) and `&mut T` +/// (a mutable borrow). But types like `Vec<T>` provide additional kinds of +/// borrows: the borrowed slices `&[T]` and `&mut [T]`. +/// +/// When writing generic code, it is often desirable to abstract over all ways +/// of borrowing data from a given type. That is the role of the `Borrow` +/// trait: if `T: Borrow<U>`, then `&U` can be borrowed from `&T`. A given +/// type can be borrowed as multiple different types. In particular, `Vec<T>: +/// Borrow<Vec<T>>` and `Vec<T>: Borrow<[T]>`. +#[stable(feature = "rust1", since = "1.0.0")] +pub trait Borrow<Borrowed: ?Sized> { + /// Immutably borrow from an owned value. + #[stable(feature = "rust1", since = "1.0.0")] + fn borrow(&self) -> &Borrowed; +} + +/// A trait for mutably borrowing data. +/// +/// Similar to `Borrow`, but for mutable borrows. +#[stable(feature = "rust1", since = "1.0.0")] +pub trait BorrowMut<Borrowed: ?Sized> : Borrow<Borrowed> { + /// Mutably borrow from an owned value. + #[stable(feature = "rust1", since = "1.0.0")] + fn borrow_mut(&mut self) -> &mut Borrowed; +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<T: ?Sized> Borrow<T> for T { + fn borrow(&self) -> &T { self } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<T: ?Sized> BorrowMut<T> for T { + fn borrow_mut(&mut self) -> &mut T { self } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T: ?Sized> Borrow<T> for &'a T { + fn borrow(&self) -> &T { &**self } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T: ?Sized> Borrow<T> for &'a mut T { + fn borrow(&self) -> &T { &**self } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T: ?Sized> BorrowMut<T> for &'a mut T { + fn borrow_mut(&mut self) -> &mut T { &mut **self } +} + +impl<T> Borrow<T> for rc::Rc<T> { + fn borrow(&self) -> &T { &**self } +} + +impl<T> Borrow<T> for arc::Arc<T> { + fn borrow(&self) -> &T { &**self } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> Borrow<B> for Cow<'a, B> where B: ToOwned, <B as ToOwned>::Owned: 'a { + fn borrow(&self) -> &B { + &**self + } +} + +/// A generalization of Clone to borrowed data. +/// +/// Some types make it possible to go from borrowed to owned, usually by +/// implementing the `Clone` trait. But `Clone` works only for going from `&T` +/// to `T`. The `ToOwned` trait generalizes `Clone` to construct owned data +/// from any borrow of a given type. +#[stable(feature = "rust1", since = "1.0.0")] +pub trait ToOwned { + #[stable(feature = "rust1", since = "1.0.0")] + type Owned: Borrow<Self>; + + /// Create owned data from borrowed data, usually by copying. + #[stable(feature = "rust1", since = "1.0.0")] + fn to_owned(&self) -> Self::Owned; +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<T> ToOwned for T where T: Clone { + type Owned = T; + fn to_owned(&self) -> T { self.clone() } +} + +/// A clone-on-write smart pointer. +/// +/// The type `Cow` is a smart pointer providing clone-on-write functionality: it +/// can enclose and provide immutable access to borrowed data, and clone the +/// data lazily when mutation or ownership is required. The type is designed to +/// work with general borrowed data via the `Borrow` trait. +/// +/// `Cow` implements both `Deref`, which means that you can call +/// non-mutating methods directly on the data it encloses. If mutation +/// is desired, `to_mut` will obtain a mutable references to an owned +/// value, cloning if necessary. +/// +/// # Example +/// +/// ```rust +/// use std::borrow::Cow; +/// +/// fn abs_all(input: &mut Cow<[int]>) { +/// for i in 0..input.len() { +/// let v = input[i]; +/// if v < 0 { +/// // clones into a vector the first time (if not already owned) +/// input.to_mut()[i] = -v; +/// } +/// } +/// } +/// ``` +#[stable(feature = "rust1", since = "1.0.0")] +pub enum Cow<'a, B: ?Sized + 'a> where B: ToOwned { + /// Borrowed data. + #[stable(feature = "rust1", since = "1.0.0")] + Borrowed(&'a B), + + /// Owned data. + #[stable(feature = "rust1", since = "1.0.0")] + Owned(<B as ToOwned>::Owned) +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> Clone for Cow<'a, B> where B: ToOwned { + fn clone(&self) -> Cow<'a, B> { + match *self { + Borrowed(b) => Borrowed(b), + Owned(ref o) => { + let b: &B = o.borrow(); + Owned(b.to_owned()) + }, + } + } +} + +impl<'a, B: ?Sized> Cow<'a, B> where B: ToOwned { + /// Acquire a mutable reference to the owned form of the data. + /// + /// Copies the data if it is not already owned. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn to_mut(&mut self) -> &mut <B as ToOwned>::Owned { + match *self { + Borrowed(borrowed) => { + *self = Owned(borrowed.to_owned()); + self.to_mut() + } + Owned(ref mut owned) => owned + } + } + + /// Extract the owned data. + /// + /// Copies the data if it is not already owned. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn into_owned(self) -> <B as ToOwned>::Owned { + match self { + Borrowed(borrowed) => borrowed.to_owned(), + Owned(owned) => owned + } + } + + /// Returns true if this `Cow` wraps a borrowed value + #[deprecated(since = "1.0.0", reason = "match on the enum instead")] + #[unstable(feature = "std_misc")] + pub fn is_borrowed(&self) -> bool { + match *self { + Borrowed(_) => true, + _ => false, + } + } + + /// Returns true if this `Cow` wraps an owned value + #[deprecated(since = "1.0.0", reason = "match on the enum instead")] + #[unstable(feature = "std_misc")] + pub fn is_owned(&self) -> bool { + match *self { + Owned(_) => true, + _ => false, + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> Deref for Cow<'a, B> where B: ToOwned { + type Target = B; + + fn deref(&self) -> &B { + match *self { + Borrowed(borrowed) => borrowed, + Owned(ref owned) => owned.borrow() + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> Eq for Cow<'a, B> where B: Eq + ToOwned {} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> Ord for Cow<'a, B> where B: Ord + ToOwned { + #[inline] + fn cmp(&self, other: &Cow<'a, B>) -> Ordering { + Ord::cmp(&**self, &**other) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, 'b, B: ?Sized, C: ?Sized> PartialEq<Cow<'b, C>> for Cow<'a, B> where + B: PartialEq<C> + ToOwned, C: ToOwned, +{ + #[inline] + fn eq(&self, other: &Cow<'b, C>) -> bool { + PartialEq::eq(&**self, &**other) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> PartialOrd for Cow<'a, B> where B: PartialOrd + ToOwned, +{ + #[inline] + fn partial_cmp(&self, other: &Cow<'a, B>) -> Option<Ordering> { + PartialOrd::partial_cmp(&**self, &**other) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> fmt::Debug for Cow<'a, B> where + B: fmt::Debug + ToOwned, + <B as ToOwned>::Owned: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match *self { + Borrowed(ref b) => fmt::Debug::fmt(b, f), + Owned(ref o) => fmt::Debug::fmt(o, f), + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> fmt::Display for Cow<'a, B> where + B: fmt::Display + ToOwned, + <B as ToOwned>::Owned: fmt::Display, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match *self { + Borrowed(ref b) => fmt::Display::fmt(b, f), + Owned(ref o) => fmt::Display::fmt(o, f), + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +#[cfg(stage0)] +impl<'a, B: ?Sized, S: Hasher> Hash<S> for Cow<'a, B> where B: Hash<S> + ToOwned +{ + #[inline] + fn hash(&self, state: &mut S) { + Hash::hash(&**self, state) + } +} +#[stable(feature = "rust1", since = "1.0.0")] +#[cfg(not(stage0))] +impl<'a, B: ?Sized> Hash for Cow<'a, B> where B: Hash + ToOwned +{ + #[inline] + fn hash<H: Hasher>(&self, state: &mut H) { + Hash::hash(&**self, state) + } +} + +/// Trait for moving into a `Cow` +#[stable(feature = "rust1", since = "1.0.0")] +pub trait IntoCow<'a, B: ?Sized> where B: ToOwned { + /// Moves `self` into `Cow` + #[stable(feature = "rust1", since = "1.0.0")] + fn into_cow(self) -> Cow<'a, B>; +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> IntoCow<'a, B> for Cow<'a, B> where B: ToOwned { + fn into_cow(self) -> Cow<'a, B> { + self + } +} diff --git a/src/libcollections/borrow_stage0.rs b/src/libcollections/borrow_stage0.rs new file mode 100644 index 00000000000..c1d74b16ce6 --- /dev/null +++ b/src/libcollections/borrow_stage0.rs @@ -0,0 +1,313 @@ +// Copyright 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. + +//! A module for working with borrowed data. + +#![stable(feature = "rust1", since = "1.0.0")] + +use core::clone::Clone; +use core::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd}; +use core::hash::{Hash, Hasher}; +use core::marker::Sized; +use core::ops::Deref; +use core::option::Option; + +use fmt; +use alloc::{rc, arc}; + +use self::Cow::*; + +/// A trait for borrowing data. +/// +/// In general, there may be several ways to "borrow" a piece of data. The +/// typical ways of borrowing a type `T` are `&T` (a shared borrow) and `&mut T` +/// (a mutable borrow). But types like `Vec<T>` provide additional kinds of +/// borrows: the borrowed slices `&[T]` and `&mut [T]`. +/// +/// When writing generic code, it is often desirable to abstract over all ways +/// of borrowing data from a given type. That is the role of the `Borrow` +/// trait: if `T: Borrow<U>`, then `&U` can be borrowed from `&T`. A given +/// type can be borrowed as multiple different types. In particular, `Vec<T>: +/// Borrow<Vec<T>>` and `Vec<T>: Borrow<[T]>`. +#[stable(feature = "rust1", since = "1.0.0")] +pub trait Borrow<Borrowed: ?Sized> { + /// Immutably borrow from an owned value. + #[stable(feature = "rust1", since = "1.0.0")] + fn borrow(&self) -> &Borrowed; +} + +/// A trait for mutably borrowing data. +/// +/// Similar to `Borrow`, but for mutable borrows. +#[stable(feature = "rust1", since = "1.0.0")] +pub trait BorrowMut<Borrowed: ?Sized> : Borrow<Borrowed> { + /// Mutably borrow from an owned value. + #[stable(feature = "rust1", since = "1.0.0")] + fn borrow_mut(&mut self) -> &mut Borrowed; +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<T: ?Sized> Borrow<T> for T { + fn borrow(&self) -> &T { self } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<T: ?Sized> BorrowMut<T> for T { + fn borrow_mut(&mut self) -> &mut T { self } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T: ?Sized> Borrow<T> for &'a T { + fn borrow(&self) -> &T { &**self } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T: ?Sized> Borrow<T> for &'a mut T { + fn borrow(&self) -> &T { &**self } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T: ?Sized> BorrowMut<T> for &'a mut T { + fn borrow_mut(&mut self) -> &mut T { &mut **self } +} + +impl<T> Borrow<T> for rc::Rc<T> { + fn borrow(&self) -> &T { &**self } +} + +impl<T> Borrow<T> for arc::Arc<T> { + fn borrow(&self) -> &T { &**self } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> Borrow<B> for Cow<'a, B> where B: ToOwned, <B as ToOwned>::Owned: 'a { + fn borrow(&self) -> &B { + &**self + } +} + +/// A generalization of Clone to borrowed data. +/// +/// Some types make it possible to go from borrowed to owned, usually by +/// implementing the `Clone` trait. But `Clone` works only for going from `&T` +/// to `T`. The `ToOwned` trait generalizes `Clone` to construct owned data +/// from any borrow of a given type. +#[stable(feature = "rust1", since = "1.0.0")] +pub trait ToOwned { + #[stable(feature = "rust1", since = "1.0.0")] + type Owned: Borrow<Self>; + + /// Create owned data from borrowed data, usually by copying. + #[stable(feature = "rust1", since = "1.0.0")] + fn to_owned(&self) -> Self::Owned; +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<T> ToOwned for T where T: Clone { + type Owned = T; + fn to_owned(&self) -> T { self.clone() } +} + +/// A clone-on-write smart pointer. +/// +/// The type `Cow` is a smart pointer providing clone-on-write functionality: it +/// can enclose and provide immutable access to borrowed data, and clone the +/// data lazily when mutation or ownership is required. The type is designed to +/// work with general borrowed data via the `Borrow` trait. +/// +/// `Cow` implements both `Deref`, which means that you can call +/// non-mutating methods directly on the data it encloses. If mutation +/// is desired, `to_mut` will obtain a mutable references to an owned +/// value, cloning if necessary. +/// +/// # Example +/// +/// ```rust +/// use std::borrow::Cow; +/// +/// fn abs_all(input: &mut Cow<[int]>) { +/// for i in 0..input.len() { +/// let v = input[i]; +/// if v < 0 { +/// // clones into a vector the first time (if not already owned) +/// input.to_mut()[i] = -v; +/// } +/// } +/// } +/// ``` +#[stable(feature = "rust1", since = "1.0.0")] +pub enum Cow<'a, B: ?Sized + 'a> where B: ToOwned { + /// Borrowed data. + #[stable(feature = "rust1", since = "1.0.0")] + Borrowed(&'a B), + + /// Owned data. + #[stable(feature = "rust1", since = "1.0.0")] + Owned(<B as ToOwned>::Owned) +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> Clone for Cow<'a, B> where B: ToOwned { + fn clone(&self) -> Cow<'a, B> { + match *self { + Borrowed(b) => Borrowed(b), + Owned(ref o) => { + let b: &B = o.borrow(); + Owned(b.to_owned()) + }, + } + } +} + +impl<'a, B: ?Sized> Cow<'a, B> where B: ToOwned, <B as ToOwned>::Owned: 'a { + /// Acquire a mutable reference to the owned form of the data. + /// + /// Copies the data if it is not already owned. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn to_mut(&mut self) -> &mut <B as ToOwned>::Owned where <B as ToOwned>::Owned: 'a { + match *self { + Borrowed(borrowed) => { + *self = Owned(borrowed.to_owned()); + self.to_mut() + } + Owned(ref mut owned) => owned + } + } + + /// Extract the owned data. + /// + /// Copies the data if it is not already owned. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn into_owned(self) -> <B as ToOwned>::Owned { + match self { + Borrowed(borrowed) => borrowed.to_owned(), + Owned(owned) => owned + } + } + + /// Returns true if this `Cow` wraps a borrowed value + #[deprecated(since = "1.0.0", reason = "match on the enum instead")] + #[unstable(feature = "std_misc")] + pub fn is_borrowed(&self) -> bool { + match *self { + Borrowed(_) => true, + _ => false, + } + } + + /// Returns true if this `Cow` wraps an owned value + #[deprecated(since = "1.0.0", reason = "match on the enum instead")] + #[unstable(feature = "std_misc")] + pub fn is_owned(&self) -> bool { + match *self { + Owned(_) => true, + _ => false, + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> Deref for Cow<'a, B> where + B: ToOwned, <B as ToOwned>::Owned: 'a +{ + type Target = B; + + fn deref(&self) -> &B { + match *self { + Borrowed(borrowed) => borrowed, + Owned(ref owned) => owned.borrow() + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> Eq for Cow<'a, B> where B: Eq + ToOwned, <B as ToOwned>::Owned: 'a {} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> Ord for Cow<'a, B> where + B: Ord + ToOwned, <B as ToOwned>::Owned: 'a +{ + #[inline] + fn cmp(&self, other: &Cow<'a, B>) -> Ordering { + Ord::cmp(&**self, &**other) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, 'b, B: ?Sized, C: ?Sized> PartialEq<Cow<'b, C>> for Cow<'a, B> where + B: PartialEq<C> + ToOwned, C: ToOwned, + <B as ToOwned>::Owned: 'a, <C as ToOwned>::Owned: 'b, +{ + #[inline] + fn eq(&self, other: &Cow<'b, C>) -> bool { + PartialEq::eq(&**self, &**other) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> PartialOrd for Cow<'a, B> where + B: PartialOrd + ToOwned, <B as ToOwned>::Owned: 'a +{ + #[inline] + fn partial_cmp(&self, other: &Cow<'a, B>) -> Option<Ordering> { + PartialOrd::partial_cmp(&**self, &**other) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> fmt::Debug for Cow<'a, B> where + B: fmt::Debug + ToOwned, + <B as ToOwned>::Owned: fmt::Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match *self { + Borrowed(ref b) => fmt::Debug::fmt(b, f), + Owned(ref o) => fmt::Debug::fmt(o, f), + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> fmt::Display for Cow<'a, B> where + B: fmt::Display + ToOwned, + <B as ToOwned>::Owned: fmt::Display, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match *self { + Borrowed(ref b) => fmt::Display::fmt(b, f), + Owned(ref o) => fmt::Display::fmt(o, f), + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized, S: Hasher> Hash<S> for Cow<'a, B> where + B: Hash<S> + ToOwned, <B as ToOwned>::Owned: 'a +{ + #[inline] + fn hash(&self, state: &mut S) { + Hash::hash(&**self, state) + } +} + +/// Trait for moving into a `Cow` +#[stable(feature = "rust1", since = "1.0.0")] +pub trait IntoCow<'a, B: ?Sized> where B: ToOwned { + /// Moves `self` into `Cow` + #[stable(feature = "rust1", since = "1.0.0")] + fn into_cow(self) -> Cow<'a, B>; +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, B: ?Sized> IntoCow<'a, B> for Cow<'a, B> where B: ToOwned { + fn into_cow(self) -> Cow<'a, B> { + self + } +} diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs index 747211e9238..7823f536c7a 100644 --- a/src/libcollections/btree/map.rs +++ b/src/libcollections/btree/map.rs @@ -19,7 +19,6 @@ use self::Entry::*; use core::prelude::*; -use core::borrow::BorrowFrom; use core::cmp::Ordering; use core::default::Default; use core::fmt::Debug; @@ -29,7 +28,8 @@ use core::ops::{Index, IndexMut}; use core::{iter, fmt, mem}; use Bound::{self, Included, Excluded, Unbounded}; -use ring_buf::RingBuf; +use borrow::Borrow; +use vec_deque::VecDeque; use self::Continuation::{Continue, Finished}; use self::StackOp::*; @@ -75,7 +75,7 @@ pub struct BTreeMap<K, V> { /// An abstract base over-which all other BTree iterators are built. struct AbsIter<T> { - traversals: RingBuf<T>, + traversals: VecDeque<T>, size: usize, } @@ -208,7 +208,7 @@ impl<K: Ord, V> BTreeMap<K, V> { /// assert_eq!(map.get(&2), None); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where Q: BorrowFrom<K> + Ord { + pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord { let mut cur_node = &self.root; loop { match Node::search(cur_node, key) { @@ -240,7 +240,7 @@ impl<K: Ord, V> BTreeMap<K, V> { /// assert_eq!(map.contains_key(&2), false); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where Q: BorrowFrom<K> + Ord { + pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord { self.get(key).is_some() } @@ -264,7 +264,7 @@ impl<K: Ord, V> BTreeMap<K, V> { /// ``` // See `get` for implementation notes, this is basically a copy-paste with mut's added #[stable(feature = "rust1", since = "1.0.0")] - pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where Q: BorrowFrom<K> + Ord { + pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord { // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration let mut temp_node = &mut self.root; loop { @@ -434,7 +434,7 @@ impl<K: Ord, V> BTreeMap<K, V> { /// assert_eq!(map.remove(&1), None); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: BorrowFrom<K> + Ord { + pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord { // See `swap` for a more thorough description of the stuff going on in here let mut stack = stack::PartialSearchStack::new(self); loop { @@ -512,13 +512,22 @@ mod stack { use super::super::node::handle; use vec::Vec; + struct InvariantLifetime<'id>( + marker::PhantomData<::core::cell::Cell<&'id ()>>); + + impl<'id> InvariantLifetime<'id> { + fn new() -> InvariantLifetime<'id> { + InvariantLifetime(marker::PhantomData) + } + } + /// A generic mutable reference, identical to `&mut` except for the fact that its lifetime /// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef` /// with the exact requested lifetime can be used. This is in contrast to normal references, /// where `&'static` can be used in any function expecting any lifetime reference. pub struct IdRef<'id, T: 'id> { inner: &'id mut T, - marker: marker::InvariantLifetime<'id> + _marker: InvariantLifetime<'id>, } impl<'id, T> Deref for IdRef<'id, T> { @@ -560,7 +569,7 @@ mod stack { pub struct Pusher<'id, 'a, K:'a, V:'a> { map: &'a mut BTreeMap<K, V>, stack: Stack<K, V>, - marker: marker::InvariantLifetime<'id> + _marker: InvariantLifetime<'id>, } impl<'a, K, V> PartialSearchStack<'a, K, V> { @@ -595,11 +604,11 @@ mod stack { let pusher = Pusher { map: self.map, stack: self.stack, - marker: marker::InvariantLifetime + _marker: InvariantLifetime::new(), }; let node = IdRef { inner: unsafe { &mut *self.next }, - marker: marker::InvariantLifetime + _marker: InvariantLifetime::new(), }; closure(pusher, node) @@ -826,7 +835,7 @@ mod stack { #[stable(feature = "rust1", since = "1.0.0")] impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> { - fn from_iter<T: Iterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> { + fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> { let mut map = BTreeMap::new(); map.extend(iter); map @@ -836,13 +845,14 @@ impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> { #[inline] - fn extend<T: Iterator<Item=(K, V)>>(&mut self, iter: T) { + fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) { for (k, v) in iter { self.insert(k, v); } } } +#[cfg(stage0)] #[stable(feature = "rust1", since = "1.0.0")] impl<S: Hasher, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> { fn hash(&self, state: &mut S) { @@ -851,6 +861,15 @@ impl<S: Hasher, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> { } } } +#[cfg(not(stage0))] +#[stable(feature = "rust1", since = "1.0.0")] +impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> { + fn hash<H: Hasher>(&self, state: &mut H) { + for elt in self { + elt.hash(state); + } + } +} #[stable(feature = "rust1", since = "1.0.0")] impl<K: Ord, V> Default for BTreeMap<K, V> { @@ -903,7 +922,7 @@ impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] impl<K: Ord, Q: ?Sized, V> Index<Q> for BTreeMap<K, V> - where Q: BorrowFrom<K> + Ord + where K: Borrow<Q>, Q: Ord { type Output = V; @@ -914,7 +933,7 @@ impl<K: Ord, Q: ?Sized, V> Index<Q> for BTreeMap<K, V> #[stable(feature = "rust1", since = "1.0.0")] impl<K: Ord, Q: ?Sized, V> IndexMut<Q> for BTreeMap<K, V> - where Q: BorrowFrom<K> + Ord + where K: Borrow<Q>, Q: Ord { fn index_mut(&mut self, key: &Q) -> &mut V { self.get_mut(key).expect("no entry found for key") @@ -1189,7 +1208,7 @@ impl<K, V> BTreeMap<K, V> { pub fn iter(&self) -> Iter<K, V> { let len = self.len(); // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases. - let mut lca = RingBuf::new(); + let mut lca = VecDeque::new(); lca.push_back(Traverse::traverse(&self.root)); Iter { inner: AbsIter { @@ -1221,7 +1240,7 @@ impl<K, V> BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] pub fn iter_mut(&mut self) -> IterMut<K, V> { let len = self.len(); - let mut lca = RingBuf::new(); + let mut lca = VecDeque::new(); lca.push_back(Traverse::traverse(&mut self.root)); IterMut { inner: AbsIter { @@ -1250,7 +1269,7 @@ impl<K, V> BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] pub fn into_iter(self) -> IntoIter<K, V> { let len = self.len(); - let mut lca = RingBuf::new(); + let mut lca = VecDeque::new(); lca.push_back(Traverse::traverse(self.root)); IntoIter { inner: AbsIter { @@ -1342,7 +1361,7 @@ macro_rules! range_impl { // A deque that encodes two search paths containing (left-to-right): // a series of truncated-from-the-left iterators, the LCA's doubly-truncated iterator, // and a series of truncated-from-the-right iterators. - let mut traversals = RingBuf::new(); + let mut traversals = VecDeque::new(); let (root, min, max) = ($root, $min, $max); let mut leftmost = None; diff --git a/src/libcollections/btree/node.rs b/src/libcollections/btree/node.rs index 24523d4dcc9..f0fc12da727 100644 --- a/src/libcollections/btree/node.rs +++ b/src/libcollections/btree/node.rs @@ -18,13 +18,15 @@ pub use self::TraversalItem::*; use core::prelude::*; -use core::borrow::BorrowFrom; use core::cmp::Ordering::{Greater, Less, Equal}; use core::iter::Zip; +use core::marker::PhantomData; use core::ops::{Deref, DerefMut, Index, IndexMut}; use core::ptr::Unique; use core::{slice, mem, ptr, cmp, num, raw}; -use alloc::heap; +use alloc::heap::{self, EMPTY}; + +use borrow::Borrow; /// Represents the result of an Insertion: either the item fit, or the node had to split pub enum InsertionResult<K, V> { @@ -57,8 +59,8 @@ pub struct Node<K, V> { keys: Unique<K>, vals: Unique<V>, - // In leaf nodes, this will be null, and no space will be allocated for edges. - edges: Unique<Node<K, V>>, + // In leaf nodes, this will be None, and no space will be allocated for edges. + edges: Option<Unique<Node<K, V>>>, // At any given time, there will be `_len` keys, `_len` values, and (in an internal node) // `_len + 1` edges. In a leaf node, there will never be any edges. @@ -278,8 +280,11 @@ impl<T> Drop for RawItems<T> { #[unsafe_destructor] impl<K, V> Drop for Node<K, V> { fn drop(&mut self) { - if self.keys.ptr.is_null() { - // We have already cleaned up this node. + if self.keys.is_null() { + // Since we have #[unsafe_no_drop_flag], we have to watch + // out for a null value being stored in self.keys. (Using + // null is technically a violation of the `Unique` + // requirements, though.) return; } @@ -292,7 +297,7 @@ impl<K, V> Drop for Node<K, V> { self.destroy(); } - self.keys.ptr = ptr::null_mut(); + self.keys = unsafe { Unique::new(0 as *mut K) }; } } @@ -308,9 +313,9 @@ impl<K, V> Node<K, V> { let (vals_offset, edges_offset) = calculate_offsets_generic::<K, V>(capacity, false); Node { - keys: Unique(buffer as *mut K), - vals: Unique(buffer.offset(vals_offset as isize) as *mut V), - edges: Unique(buffer.offset(edges_offset as isize) as *mut Node<K, V>), + keys: Unique::new(buffer as *mut K), + vals: Unique::new(buffer.offset(vals_offset as isize) as *mut V), + edges: Some(Unique::new(buffer.offset(edges_offset as isize) as *mut Node<K, V>)), _len: 0, _capacity: capacity, } @@ -326,9 +331,9 @@ impl<K, V> Node<K, V> { let (vals_offset, _) = calculate_offsets_generic::<K, V>(capacity, true); Node { - keys: Unique(buffer as *mut K), - vals: Unique(unsafe { buffer.offset(vals_offset as isize) as *mut V }), - edges: Unique(ptr::null_mut()), + keys: unsafe { Unique::new(buffer as *mut K) }, + vals: unsafe { Unique::new(buffer.offset(vals_offset as isize) as *mut V) }, + edges: None, _len: 0, _capacity: capacity, } @@ -337,18 +342,18 @@ impl<K, V> Node<K, V> { unsafe fn destroy(&mut self) { let (alignment, size) = calculate_allocation_generic::<K, V>(self.capacity(), self.is_leaf()); - heap::deallocate(self.keys.ptr as *mut u8, size, alignment); + heap::deallocate(*self.keys as *mut u8, size, alignment); } #[inline] pub fn as_slices<'a>(&'a self) -> (&'a [K], &'a [V]) { unsafe {( mem::transmute(raw::Slice { - data: self.keys.ptr, + data: *self.keys as *const K, len: self.len() }), mem::transmute(raw::Slice { - data: self.vals.ptr, + data: *self.vals as *const V, len: self.len() }) )} @@ -367,8 +372,12 @@ impl<K, V> Node<K, V> { &[] } else { unsafe { + let data = match self.edges { + None => heap::EMPTY as *const Node<K,V>, + Some(ref p) => **p as *const Node<K,V>, + }; mem::transmute(raw::Slice { - data: self.edges.ptr, + data: data, len: self.len() + 1 }) } @@ -524,7 +533,8 @@ impl<K: Clone, V: Clone> Clone for Node<K, V> { #[derive(Copy)] pub struct Handle<NodeRef, Type, NodeType> { node: NodeRef, - index: usize + index: usize, + marker: PhantomData<(Type, NodeType)>, } pub mod handle { @@ -543,13 +553,13 @@ impl<K: Ord, V> Node<K, V> { /// `Found` will be yielded with the matching index. If it doesn't find an exact match, /// `GoDown` will be yielded with the index of the subtree the key must lie in. pub fn search<Q: ?Sized, NodeRef: Deref<Target=Node<K, V>>>(node: NodeRef, key: &Q) - -> SearchResult<NodeRef> where Q: BorrowFrom<K> + Ord { + -> SearchResult<NodeRef> where K: Borrow<Q>, Q: Ord { // FIXME(Gankro): Tune when to search linear or binary based on B (and maybe K/V). // For the B configured as of this writing (B = 6), binary search was *significantly* // worse for usizes. match node.as_slices_internal().search_linear(key) { - (index, true) => Found(Handle { node: node, index: index }), - (index, false) => GoDown(Handle { node: node, index: index }), + (index, true) => Found(Handle { node: node, index: index, marker: PhantomData }), + (index, false) => GoDown(Handle { node: node, index: index, marker: PhantomData }), } } } @@ -586,7 +596,7 @@ impl <K, V> Node<K, V> { /// If the node has any children pub fn is_leaf(&self) -> bool { - self.edges.ptr.is_null() + self.edges.is_none() } /// if the node has too few elements @@ -618,7 +628,8 @@ impl<K, V, NodeRef, Type, NodeType> Handle<NodeRef, Type, NodeType> where pub fn as_raw(&mut self) -> Handle<*mut Node<K, V>, Type, NodeType> { Handle { node: &mut *self.node as *mut _, - index: self.index + index: self.index, + marker: PhantomData, } } } @@ -630,7 +641,8 @@ impl<K, V, Type, NodeType> Handle<*mut Node<K, V>, Type, NodeType> { pub unsafe fn from_raw<'a>(&'a self) -> Handle<&'a Node<K, V>, Type, NodeType> { Handle { node: &*self.node, - index: self.index + index: self.index, + marker: PhantomData, } } @@ -640,7 +652,8 @@ impl<K, V, Type, NodeType> Handle<*mut Node<K, V>, Type, NodeType> { pub unsafe fn from_raw_mut<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, Type, NodeType> { Handle { node: &mut *self.node, - index: self.index + index: self.index, + marker: PhantomData, } } } @@ -688,12 +701,14 @@ impl<K, V, NodeRef: Deref<Target=Node<K, V>>, Type> Handle<NodeRef, Type, handle if self.node.is_leaf() { Leaf(Handle { node: self.node, - index: self.index + index: self.index, + marker: PhantomData, }) } else { Internal(Handle { node: self.node, - index: self.index + index: self.index, + marker: PhantomData, }) } } @@ -826,7 +841,8 @@ impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::Edge, NodeType> where unsafe fn left_kv<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::KV, NodeType> { Handle { node: &mut *self.node, - index: self.index - 1 + index: self.index - 1, + marker: PhantomData, } } @@ -836,7 +852,8 @@ impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::Edge, NodeType> where unsafe fn right_kv<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::KV, NodeType> { Handle { node: &mut *self.node, - index: self.index + index: self.index, + marker: PhantomData, } } } @@ -876,7 +893,8 @@ impl<'a, K: 'a, V: 'a, NodeType> Handle<&'a mut Node<K, V>, handle::KV, NodeType pub fn into_left_edge(self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> { Handle { node: &mut *self.node, - index: self.index + index: self.index, + marker: PhantomData, } } } @@ -926,7 +944,8 @@ impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::KV, NodeType> where pub fn left_edge<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> { Handle { node: &mut *self.node, - index: self.index + index: self.index, + marker: PhantomData, } } @@ -935,7 +954,8 @@ impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::KV, NodeType> where pub fn right_edge<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> { Handle { node: &mut *self.node, - index: self.index + 1 + index: self.index + 1, + marker: PhantomData, } } } @@ -1044,7 +1064,8 @@ impl<K, V> Node<K, V> { debug_assert!(index < self.len(), "kv_handle index out of bounds"); Handle { node: self, - index: index + index: index, + marker: PhantomData, } } @@ -1064,7 +1085,7 @@ impl<K, V> Node<K, V> { vals: RawItems::from_slice(self.vals()), edges: RawItems::from_slice(self.edges()), - ptr: self.keys.ptr as *mut u8, + ptr: *self.keys as *mut u8, capacity: self.capacity(), is_leaf: self.is_leaf() }, @@ -1491,9 +1512,9 @@ macro_rules! node_slice_impl { impl<'a, K: Ord + 'a, V: 'a> $NodeSlice<'a, K, V> { /// Performs linear search in a slice. Returns a tuple of (index, is_exact_match). fn search_linear<Q: ?Sized>(&self, key: &Q) -> (usize, bool) - where Q: BorrowFrom<K> + Ord { + where K: Borrow<Q>, Q: Ord { for (i, k) in self.keys.iter().enumerate() { - match key.cmp(BorrowFrom::borrow_from(k)) { + match key.cmp(k.borrow()) { Greater => {}, Equal => return (i, true), Less => return (i, false), diff --git a/src/libcollections/btree/set.rs b/src/libcollections/btree/set.rs index 7ef887b70cc..929b2f58043 100644 --- a/src/libcollections/btree/set.rs +++ b/src/libcollections/btree/set.rs @@ -13,7 +13,6 @@ use core::prelude::*; -use core::borrow::BorrowFrom; use core::cmp::Ordering::{self, Less, Greater, Equal}; use core::default::Default; use core::fmt::Debug; @@ -21,6 +20,7 @@ use core::fmt; use core::iter::{Peekable, Map, FromIterator, IntoIterator}; use core::ops::{BitOr, BitAnd, BitXor, Sub}; +use borrow::Borrow; use btree_map::{BTreeMap, Keys}; use Bound; @@ -336,7 +336,7 @@ impl<T: Ord> BTreeSet<T> { /// assert_eq!(set.contains(&4), false); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool where Q: BorrowFrom<T> + Ord { + pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool where T: Borrow<Q>, Q: Ord { self.map.contains_key(value) } @@ -466,14 +466,14 @@ impl<T: Ord> BTreeSet<T> { /// assert_eq!(set.remove(&2), false); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool where Q: BorrowFrom<T> + Ord { + pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool where T: Borrow<Q>, Q: Ord { self.map.remove(value).is_some() } } #[stable(feature = "rust1", since = "1.0.0")] impl<T: Ord> FromIterator<T> for BTreeSet<T> { - fn from_iter<Iter: Iterator<Item=T>>(iter: Iter) -> BTreeSet<T> { + fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> BTreeSet<T> { let mut set = BTreeSet::new(); set.extend(iter); set @@ -503,7 +503,7 @@ impl<'a, T> IntoIterator for &'a BTreeSet<T> { #[stable(feature = "rust1", since = "1.0.0")] impl<T: Ord> Extend<T> for BTreeSet<T> { #[inline] - fn extend<Iter: Iterator<Item=T>>(&mut self, iter: Iter) { + fn extend<Iter: IntoIterator<Item=T>>(&mut self, iter: Iter) { for elem in iter { self.insert(elem); } diff --git a/src/libcollections/enum_set.rs b/src/libcollections/enum_set.rs index d5403ca5d9b..0c957426060 100644 --- a/src/libcollections/enum_set.rs +++ b/src/libcollections/enum_set.rs @@ -14,6 +14,7 @@ //! representation to hold C-like enum variants. use core::prelude::*; +use core::marker; use core::fmt; use core::num::Int; use core::iter::{FromIterator, IntoIterator}; @@ -26,7 +27,8 @@ use core::ops::{Sub, BitOr, BitAnd, BitXor}; pub struct EnumSet<E> { // We must maintain the invariant that no bits are set // for which no variant exists - bits: usize + bits: usize, + marker: marker::PhantomData<E>, } impl<E> Copy for EnumSet<E> {} @@ -86,7 +88,7 @@ impl<E:CLike> EnumSet<E> { #[unstable(feature = "collections", reason = "matches collection reform specification, waiting for dust to settle")] pub fn new() -> EnumSet<E> { - EnumSet {bits: 0} + EnumSet {bits: 0, marker: marker::PhantomData} } /// Returns the number of elements in the given `EnumSet`. @@ -130,12 +132,14 @@ impl<E:CLike> EnumSet<E> { /// Returns the union of both `EnumSets`. pub fn union(&self, e: EnumSet<E>) -> EnumSet<E> { - EnumSet {bits: self.bits | e.bits} + EnumSet {bits: self.bits | e.bits, + marker: marker::PhantomData} } /// Returns the intersection of both `EnumSets`. pub fn intersection(&self, e: EnumSet<E>) -> EnumSet<E> { - EnumSet {bits: self.bits & e.bits} + EnumSet {bits: self.bits & e.bits, + marker: marker::PhantomData} } /// Adds an enum to the `EnumSet`, and returns `true` if it wasn't there before @@ -175,7 +179,7 @@ impl<E:CLike> Sub for EnumSet<E> { type Output = EnumSet<E>; fn sub(self, e: EnumSet<E>) -> EnumSet<E> { - EnumSet {bits: self.bits & !e.bits} + EnumSet {bits: self.bits & !e.bits, marker: marker::PhantomData} } } @@ -183,7 +187,7 @@ impl<E:CLike> BitOr for EnumSet<E> { type Output = EnumSet<E>; fn bitor(self, e: EnumSet<E>) -> EnumSet<E> { - EnumSet {bits: self.bits | e.bits} + EnumSet {bits: self.bits | e.bits, marker: marker::PhantomData} } } @@ -191,7 +195,7 @@ impl<E:CLike> BitAnd for EnumSet<E> { type Output = EnumSet<E>; fn bitand(self, e: EnumSet<E>) -> EnumSet<E> { - EnumSet {bits: self.bits & e.bits} + EnumSet {bits: self.bits & e.bits, marker: marker::PhantomData} } } @@ -199,7 +203,7 @@ impl<E:CLike> BitXor for EnumSet<E> { type Output = EnumSet<E>; fn bitxor(self, e: EnumSet<E>) -> EnumSet<E> { - EnumSet {bits: self.bits ^ e.bits} + EnumSet {bits: self.bits ^ e.bits, marker: marker::PhantomData} } } @@ -207,6 +211,7 @@ impl<E:CLike> BitXor for EnumSet<E> { pub struct Iter<E> { index: usize, bits: usize, + marker: marker::PhantomData<E>, } // FIXME(#19839) Remove in favor of `#[derive(Clone)]` @@ -215,13 +220,14 @@ impl<E> Clone for Iter<E> { Iter { index: self.index, bits: self.bits, + marker: marker::PhantomData, } } } impl<E:CLike> Iter<E> { fn new(bits: usize) -> Iter<E> { - Iter { index: 0, bits: bits } + Iter { index: 0, bits: bits, marker: marker::PhantomData } } } @@ -250,9 +256,9 @@ impl<E:CLike> Iterator for Iter<E> { } impl<E:CLike> FromIterator<E> for EnumSet<E> { - fn from_iter<I:Iterator<Item=E>>(iterator: I) -> EnumSet<E> { + fn from_iter<I: IntoIterator<Item=E>>(iter: I) -> EnumSet<E> { let mut ret = EnumSet::new(); - ret.extend(iterator); + ret.extend(iter); ret } } @@ -268,8 +274,8 @@ impl<'a, E> IntoIterator for &'a EnumSet<E> where E: CLike { } impl<E:CLike> Extend<E> for EnumSet<E> { - fn extend<I: Iterator<Item=E>>(&mut self, iterator: I) { - for element in iterator { + fn extend<I: IntoIterator<Item=E>>(&mut self, iter: I) { + for element in iter { self.insert(element); } } diff --git a/src/libcollections/lib.rs b/src/libcollections/lib.rs index cacbf3bce80..6569ab9c05a 100644 --- a/src/libcollections/lib.rs +++ b/src/libcollections/lib.rs @@ -26,7 +26,6 @@ #![feature(box_syntax)] #![feature(box_patterns)] #![feature(core)] -#![feature(hash)] #![feature(staged_api)] #![feature(unboxed_closures)] #![feature(unicode)] @@ -49,17 +48,33 @@ extern crate alloc; #[cfg(test)] #[macro_use] extern crate log; pub use binary_heap::BinaryHeap; -pub use bitv::Bitv; -pub use bitv_set::BitvSet; +pub use bit_vec::BitVec; +pub use bit_set::BitSet; pub use btree_map::BTreeMap; pub use btree_set::BTreeSet; -pub use dlist::DList; +pub use linked_list::LinkedList; pub use enum_set::EnumSet; -pub use ring_buf::RingBuf; +pub use vec_deque::VecDeque; pub use string::String; pub use vec::Vec; pub use vec_map::VecMap; +#[deprecated(since = "1.0.0", reason = "renamed to vec_deque")] +#[unstable(feature = "collections")] +pub use vec_deque as ring_buf; + +#[deprecated(since = "1.0.0", reason = "renamed to linked_list")] +#[unstable(feature = "collections")] +pub use linked_list as dlist; + +#[deprecated(since = "1.0.0", reason = "renamed to bit_vec")] +#[unstable(feature = "collections")] +pub use bit_vec as bitv; + +#[deprecated(since = "1.0.0", reason = "renamed to bit_set")] +#[unstable(feature = "collections")] +pub use bit_set as bitv_set; + // Needed for the vec! macro pub use alloc::boxed; @@ -71,27 +86,42 @@ mod macros; pub mod binary_heap; mod bit; mod btree; -pub mod dlist; +pub mod linked_list; pub mod enum_set; pub mod fmt; -pub mod ring_buf; +pub mod vec_deque; pub mod slice; pub mod str; pub mod string; pub mod vec; pub mod vec_map; +#[cfg(stage0)] +#[path = "borrow_stage0.rs"] +pub mod borrow; + +#[cfg(not(stage0))] +pub mod borrow; + #[unstable(feature = "collections", reason = "RFC 509")] -pub mod bitv { - pub use bit::{Bitv, Iter}; +pub mod bit_vec { + pub use bit::{BitVec, Iter}; + + #[deprecated(since = "1.0.0", reason = "renamed to BitVec")] + #[unstable(feature = "collections")] + pub use bit::BitVec as Bitv; } #[unstable(feature = "collections", reason = "RFC 509")] -pub mod bitv_set { - pub use bit::{BitvSet, Union, Intersection, Difference, SymmetricDifference}; +pub mod bit_set { + pub use bit::{BitSet, Union, Intersection, Difference, SymmetricDifference}; pub use bit::SetIter as Iter; + + #[deprecated(since = "1.0.0", reason = "renamed to BitSet")] + #[unstable(feature = "collections")] + pub use bit::BitSet as BitvSet; } #[stable(feature = "rust1", since = "1.0.0")] @@ -117,7 +147,6 @@ mod std { #[cfg(test)] mod prelude { // from core. - pub use core::borrow::IntoCow; pub use core::clone::Clone; pub use core::cmp::{PartialEq, Eq, PartialOrd, Ord}; pub use core::cmp::Ordering::{Less, Equal, Greater}; @@ -143,6 +172,7 @@ mod prelude { pub use unicode::char::CharExt; // from collections. + pub use borrow::IntoCow; pub use slice::SliceConcatExt; pub use string::{String, ToString}; pub use vec::Vec; diff --git a/src/libcollections/dlist.rs b/src/libcollections/linked_list.rs index eb1bf93c0aa..c142819a518 100644 --- a/src/libcollections/dlist.rs +++ b/src/libcollections/linked_list.rs @@ -10,13 +10,13 @@ //! A doubly-linked list with owned nodes. //! -//! The `DList` allows pushing and popping elements at either end and is thus +//! The `LinkedList` allows pushing and popping elements at either end and is thus //! efficiently usable as a double-ended queue. -// DList is constructed like a singly-linked list over the field `next`. +// LinkedList is constructed like a singly-linked list over the field `next`. // including the last link being None; each Node owns its `next` field. // -// Backlinks over DList::prev are raw pointers that form a full chain in +// Backlinks over LinkedList::prev are raw pointers that form a full chain in // the reverse direction. #![stable(feature = "rust1", since = "1.0.0")] @@ -27,14 +27,20 @@ use alloc::boxed::Box; use core::cmp::Ordering; use core::default::Default; use core::fmt; -use core::hash::{Writer, Hasher, Hash}; +use core::hash::{Hasher, Hash}; +#[cfg(stage0)] +use core::hash::Writer; use core::iter::{self, FromIterator, IntoIterator}; use core::mem; use core::ptr; +#[deprecated(since = "1.0.0", reason = "renamed to LinkedList")] +#[unstable(feature = "collections")] +pub use LinkedList as DList; + /// A doubly-linked list. #[stable(feature = "rust1", since = "1.0.0")] -pub struct DList<T> { +pub struct LinkedList<T> { length: usize, list_head: Link<T>, list_tail: Rawlink<Node<T>>, @@ -56,7 +62,7 @@ struct Node<T> { value: T, } -/// An iterator over references to the items of a `DList`. +/// An iterator over references to the items of a `LinkedList`. #[stable(feature = "rust1", since = "1.0.0")] pub struct Iter<'a, T:'a> { head: &'a Link<T>, @@ -76,20 +82,20 @@ impl<'a, T> Clone for Iter<'a, T> { } } -/// An iterator over mutable references to the items of a `DList`. +/// An iterator over mutable references to the items of a `LinkedList`. #[stable(feature = "rust1", since = "1.0.0")] pub struct IterMut<'a, T:'a> { - list: &'a mut DList<T>, + list: &'a mut LinkedList<T>, head: Rawlink<Node<T>>, tail: Rawlink<Node<T>>, nelem: usize, } -/// An iterator over mutable references to the items of a `DList`. +/// An iterator over mutable references to the items of a `LinkedList`. #[derive(Clone)] #[stable(feature = "rust1", since = "1.0.0")] pub struct IntoIter<T> { - list: DList<T> + list: LinkedList<T> } /// Rawlink is a type like Option<T> but for holding a raw pointer @@ -147,7 +153,7 @@ fn link_with_prev<T>(mut next: Box<Node<T>>, prev: Rawlink<Node<T>>) } // private methods -impl<T> DList<T> { +impl<T> LinkedList<T> { /// Add a Node first in the list #[inline] fn push_front_node(&mut self, mut new_head: Box<Node<T>>) { @@ -207,18 +213,18 @@ impl<T> DList<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<T> Default for DList<T> { +impl<T> Default for LinkedList<T> { #[inline] #[stable(feature = "rust1", since = "1.0.0")] - fn default() -> DList<T> { DList::new() } + fn default() -> LinkedList<T> { LinkedList::new() } } -impl<T> DList<T> { - /// Creates an empty `DList`. +impl<T> LinkedList<T> { + /// Creates an empty `LinkedList`. #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn new() -> DList<T> { - DList{list_head: None, list_tail: Rawlink::none(), length: 0} + pub fn new() -> LinkedList<T> { + LinkedList{list_head: None, list_tail: Rawlink::none(), length: 0} } /// Moves all elements from `other` to the end of the list. @@ -231,10 +237,10 @@ impl<T> DList<T> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut a = DList::new(); - /// let mut b = DList::new(); + /// let mut a = LinkedList::new(); + /// let mut b = LinkedList::new(); /// a.push_back(1); /// a.push_back(2); /// b.push_back(3); @@ -247,7 +253,7 @@ impl<T> DList<T> { /// } /// println!("{}", b.len()); // prints 0 /// ``` - pub fn append(&mut self, other: &mut DList<T>) { + pub fn append(&mut self, other: &mut LinkedList<T>) { match self.list_tail.resolve() { None => { self.length = other.length; @@ -301,16 +307,16 @@ impl<T> DList<T> { IntoIter{list: self} } - /// Returns `true` if the `DList` is empty. + /// Returns `true` if the `LinkedList` is empty. /// /// This operation should compute in O(1) time. /// /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut dl = DList::new(); + /// let mut dl = LinkedList::new(); /// assert!(dl.is_empty()); /// /// dl.push_front("foo"); @@ -322,16 +328,16 @@ impl<T> DList<T> { self.list_head.is_none() } - /// Returns the length of the `DList`. + /// Returns the length of the `LinkedList`. /// /// This operation should compute in O(1) time. /// /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut dl = DList::new(); + /// let mut dl = LinkedList::new(); /// /// dl.push_front(2); /// assert_eq!(dl.len(), 1); @@ -349,16 +355,16 @@ impl<T> DList<T> { self.length } - /// Removes all elements from the `DList`. + /// Removes all elements from the `LinkedList`. /// /// This operation should compute in O(n) time. /// /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut dl = DList::new(); + /// let mut dl = LinkedList::new(); /// /// dl.push_front(2); /// dl.push_front(1); @@ -373,7 +379,7 @@ impl<T> DList<T> { #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn clear(&mut self) { - *self = DList::new() + *self = LinkedList::new() } /// Provides a reference to the front element, or `None` if the list is @@ -382,9 +388,9 @@ impl<T> DList<T> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut dl = DList::new(); + /// let mut dl = LinkedList::new(); /// assert_eq!(dl.front(), None); /// /// dl.push_front(1); @@ -403,9 +409,9 @@ impl<T> DList<T> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut dl = DList::new(); + /// let mut dl = LinkedList::new(); /// assert_eq!(dl.front(), None); /// /// dl.push_front(1); @@ -430,9 +436,9 @@ impl<T> DList<T> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut dl = DList::new(); + /// let mut dl = LinkedList::new(); /// assert_eq!(dl.back(), None); /// /// dl.push_back(1); @@ -451,9 +457,9 @@ impl<T> DList<T> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut dl = DList::new(); + /// let mut dl = LinkedList::new(); /// assert_eq!(dl.back(), None); /// /// dl.push_back(1); @@ -479,9 +485,9 @@ impl<T> DList<T> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut dl = DList::new(); + /// let mut dl = LinkedList::new(); /// /// dl.push_front(2); /// assert_eq!(dl.front().unwrap(), &2); @@ -503,9 +509,9 @@ impl<T> DList<T> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut d = DList::new(); + /// let mut d = LinkedList::new(); /// assert_eq!(d.pop_front(), None); /// /// d.push_front(1); @@ -526,9 +532,9 @@ impl<T> DList<T> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut d = DList::new(); + /// let mut d = LinkedList::new(); /// d.push_back(1); /// d.push_back(3); /// assert_eq!(3, *d.back().unwrap()); @@ -544,9 +550,9 @@ impl<T> DList<T> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut d = DList::new(); + /// let mut d = LinkedList::new(); /// assert_eq!(d.pop_back(), None); /// d.push_back(1); /// d.push_back(3); @@ -569,9 +575,9 @@ impl<T> DList<T> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut d = DList::new(); + /// let mut d = LinkedList::new(); /// /// d.push_front(1); /// d.push_front(2); @@ -583,13 +589,13 @@ impl<T> DList<T> { /// assert_eq!(splitted.pop_front(), None); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn split_off(&mut self, at: usize) -> DList<T> { + pub fn split_off(&mut self, at: usize) -> LinkedList<T> { let len = self.len(); assert!(at <= len, "Cannot split off at a nonexistent index"); if at == 0 { - return mem::replace(self, DList::new()); + return mem::replace(self, LinkedList::new()); } else if at == len { - return DList::new(); + return LinkedList::new(); } // Below, we iterate towards the `i-1`th node, either from the start or the end, @@ -612,7 +618,7 @@ impl<T> DList<T> { iter.tail }; - let mut splitted_list = DList { + let mut splitted_list = LinkedList { list_head: None, list_tail: self.list_tail, length: len - at @@ -628,9 +634,9 @@ impl<T> DList<T> { #[unsafe_destructor] #[stable(feature = "rust1", since = "1.0.0")] -impl<T> Drop for DList<T> { +impl<T> Drop for LinkedList<T> { fn drop(&mut self) { - // Dissolve the dlist in backwards direction + // Dissolve the linked_list in backwards direction // Just dropping the list_head can lead to stack exhaustion // when length is >> 1_000_000 let mut tail = self.list_tail; @@ -761,9 +767,9 @@ impl<'a, A> IterMut<'a, A> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut list: DList<_> = vec![1, 3, 4].into_iter().collect(); + /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect(); /// /// { /// let mut it = list.iter_mut(); @@ -788,9 +794,9 @@ impl<'a, A> IterMut<'a, A> { /// # Examples /// /// ``` - /// use std::collections::DList; + /// use std::collections::LinkedList; /// - /// let mut list: DList<_> = vec![1, 2, 3].into_iter().collect(); + /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect(); /// /// let mut it = list.iter_mut(); /// assert_eq!(it.next().unwrap(), &1); @@ -829,16 +835,16 @@ impl<A> DoubleEndedIterator for IntoIter<A> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<A> FromIterator<A> for DList<A> { - fn from_iter<T: Iterator<Item=A>>(iterator: T) -> DList<A> { +impl<A> FromIterator<A> for LinkedList<A> { + fn from_iter<T: IntoIterator<Item=A>>(iter: T) -> LinkedList<A> { let mut ret = DList::new(); - ret.extend(iterator); + ret.extend(iter); ret } } #[stable(feature = "rust1", since = "1.0.0")] -impl<T> IntoIterator for DList<T> { +impl<T> IntoIterator for LinkedList<T> { type Item = T; type IntoIter = IntoIter<T>; @@ -848,7 +854,7 @@ impl<T> IntoIterator for DList<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T> IntoIterator for &'a DList<T> { +impl<'a, T> IntoIterator for &'a LinkedList<T> { type Item = &'a T; type IntoIter = Iter<'a, T>; @@ -857,7 +863,7 @@ impl<'a, T> IntoIterator for &'a DList<T> { } } -impl<'a, T> IntoIterator for &'a mut DList<T> { +impl<'a, T> IntoIterator for &'a mut LinkedList<T> { type Item = &'a mut T; type IntoIter = IterMut<'a, T>; @@ -867,54 +873,54 @@ impl<'a, T> IntoIterator for &'a mut DList<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<A> Extend<A> for DList<A> { - fn extend<T: Iterator<Item=A>>(&mut self, iterator: T) { - for elt in iterator { self.push_back(elt); } +impl<A> Extend<A> for LinkedList<A> { + fn extend<T: IntoIterator<Item=A>>(&mut self, iter: T) { + for elt in iter { self.push_back(elt); } } } #[stable(feature = "rust1", since = "1.0.0")] -impl<A: PartialEq> PartialEq for DList<A> { - fn eq(&self, other: &DList<A>) -> bool { +impl<A: PartialEq> PartialEq for LinkedList<A> { + fn eq(&self, other: &LinkedList<A>) -> bool { self.len() == other.len() && iter::order::eq(self.iter(), other.iter()) } - fn ne(&self, other: &DList<A>) -> bool { + fn ne(&self, other: &LinkedList<A>) -> bool { self.len() != other.len() || iter::order::ne(self.iter(), other.iter()) } } #[stable(feature = "rust1", since = "1.0.0")] -impl<A: Eq> Eq for DList<A> {} +impl<A: Eq> Eq for LinkedList<A> {} #[stable(feature = "rust1", since = "1.0.0")] -impl<A: PartialOrd> PartialOrd for DList<A> { - fn partial_cmp(&self, other: &DList<A>) -> Option<Ordering> { +impl<A: PartialOrd> PartialOrd for LinkedList<A> { + fn partial_cmp(&self, other: &LinkedList<A>) -> Option<Ordering> { iter::order::partial_cmp(self.iter(), other.iter()) } } #[stable(feature = "rust1", since = "1.0.0")] -impl<A: Ord> Ord for DList<A> { +impl<A: Ord> Ord for LinkedList<A> { #[inline] - fn cmp(&self, other: &DList<A>) -> Ordering { + fn cmp(&self, other: &LinkedList<A>) -> Ordering { iter::order::cmp(self.iter(), other.iter()) } } #[stable(feature = "rust1", since = "1.0.0")] -impl<A: Clone> Clone for DList<A> { - fn clone(&self) -> DList<A> { - self.iter().map(|x| x.clone()).collect() +impl<A: Clone> Clone for LinkedList<A> { + fn clone(&self) -> LinkedList<A> { + self.iter().cloned().collect() } } #[stable(feature = "rust1", since = "1.0.0")] -impl<A: fmt::Debug> fmt::Debug for DList<A> { +impl<A: fmt::Debug> fmt::Debug for LinkedList<A> { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - try!(write!(f, "DList [")); + try!(write!(f, "LinkedList [")); for (i, e) in self.iter().enumerate() { if i != 0 { try!(write!(f, ", ")); } @@ -926,7 +932,8 @@ impl<A: fmt::Debug> fmt::Debug for DList<A> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for DList<A> { +#[cfg(stage0)] +impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for LinkedList<A> { fn hash(&self, state: &mut S) { self.len().hash(state); for elt in self { @@ -934,6 +941,16 @@ impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for DList<A> { } } } +#[stable(feature = "rust1", since = "1.0.0")] +#[cfg(not(stage0))] +impl<A: Hash> Hash for LinkedList<A> { + fn hash<H: Hasher>(&self, state: &mut H) { + self.len().hash(state); + for elt in self { + elt.hash(state); + } + } +} #[cfg(test)] mod tests { @@ -944,9 +961,9 @@ mod tests { use test::Bencher; use test; - use super::{DList, Node}; + use super::{LinkedList, Node}; - pub fn check_links<T>(list: &DList<T>) { + pub fn check_links<T>(list: &LinkedList<T>) { let mut len = 0; let mut last_ptr: Option<&Node<T>> = None; let mut node_ptr: &Node<T>; @@ -980,7 +997,7 @@ mod tests { #[test] fn test_basic() { - let mut m = DList::new(); + let mut m = LinkedList::new(); assert_eq!(m.pop_front(), None); assert_eq!(m.pop_back(), None); assert_eq!(m.pop_front(), None); @@ -999,7 +1016,7 @@ mod tests { m.push_back(box 7); assert_eq!(m.pop_front(), Some(box 1)); - let mut n = DList::new(); + let mut n = LinkedList::new(); n.push_front(2); n.push_front(3); { @@ -1019,21 +1036,21 @@ mod tests { } #[cfg(test)] - fn generate_test() -> DList<i32> { + fn generate_test() -> LinkedList<i32> { list_from(&[0,1,2,3,4,5,6]) } #[cfg(test)] - fn list_from<T: Clone>(v: &[T]) -> DList<T> { - v.iter().map(|x| (*x).clone()).collect() + fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> { + v.iter().cloned().collect() } #[test] fn test_append() { // Empty to empty { - let mut m = DList::<i32>::new(); - let mut n = DList::new(); + let mut m = LinkedList::<i32>::new(); + let mut n = LinkedList::new(); m.append(&mut n); check_links(&m); assert_eq!(m.len(), 0); @@ -1041,8 +1058,8 @@ mod tests { } // Non-empty to empty { - let mut m = DList::new(); - let mut n = DList::new(); + let mut m = LinkedList::new(); + let mut n = LinkedList::new(); n.push_back(2); m.append(&mut n); check_links(&m); @@ -1053,8 +1070,8 @@ mod tests { } // Empty to non-empty { - let mut m = DList::new(); - let mut n = DList::new(); + let mut m = LinkedList::new(); + let mut n = LinkedList::new(); m.push_back(2); m.append(&mut n); check_links(&m); @@ -1089,7 +1106,7 @@ mod tests { fn test_split_off() { // singleton { - let mut m = DList::new(); + let mut m = LinkedList::new(); m.push_back(1); let p = m.split_off(0); @@ -1130,7 +1147,7 @@ mod tests { // no-op on the last index { - let mut m = DList::new(); + let mut m = LinkedList::new(); m.push_back(1); let p = m.split_off(1); @@ -1148,7 +1165,7 @@ mod tests { for (i, elt) in m.iter().enumerate() { assert_eq!(i as i32, *elt); } - let mut n = DList::new(); + let mut n = LinkedList::new(); assert_eq!(n.iter().next(), None); n.push_front(4); let mut it = n.iter(); @@ -1160,7 +1177,7 @@ mod tests { #[test] fn test_iterator_clone() { - let mut n = DList::new(); + let mut n = LinkedList::new(); n.push_back(2); n.push_back(3); n.push_back(4); @@ -1174,7 +1191,7 @@ mod tests { #[test] fn test_iterator_double_end() { - let mut n = DList::new(); + let mut n = LinkedList::new(); assert_eq!(n.iter().next(), None); n.push_front(4); n.push_front(5); @@ -1196,7 +1213,7 @@ mod tests { for (i, elt) in m.iter().rev().enumerate() { assert_eq!((6 - i) as i32, *elt); } - let mut n = DList::new(); + let mut n = LinkedList::new(); assert_eq!(n.iter().rev().next(), None); n.push_front(4); let mut it = n.iter().rev(); @@ -1215,7 +1232,7 @@ mod tests { len -= 1; } assert_eq!(len, 0); - let mut n = DList::new(); + let mut n = LinkedList::new(); assert!(n.iter_mut().next().is_none()); n.push_front(4); n.push_back(5); @@ -1229,7 +1246,7 @@ mod tests { #[test] fn test_iterator_mut_double_end() { - let mut n = DList::new(); + let mut n = LinkedList::new(); assert!(n.iter_mut().next_back().is_none()); n.push_front(4); n.push_front(5); @@ -1278,7 +1295,7 @@ mod tests { for (i, elt) in m.iter_mut().rev().enumerate() { assert_eq!((6 - i) as i32, *elt); } - let mut n = DList::new(); + let mut n = LinkedList::new(); assert!(n.iter_mut().rev().next().is_none()); n.push_front(4); let mut it = n.iter_mut().rev(); @@ -1313,8 +1330,8 @@ mod tests { #[test] fn test_hash() { - let mut x = DList::new(); - let mut y = DList::new(); + let mut x = LinkedList::new(); + let mut y = LinkedList::new(); assert!(hash::hash::<_, SipHasher>(&x) == hash::hash::<_, SipHasher>(&y)); @@ -1382,16 +1399,16 @@ mod tests { #[test] fn test_show() { - let list: DList<_> = (0..10).collect(); - assert_eq!(format!("{:?}", list), "DList [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); + let list: LinkedList<_> = (0..10).collect(); + assert_eq!(format!("{:?}", list), "LinkedList [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); - let list: DList<_> = vec!["just", "one", "test", "more"].iter().cloned().collect(); - assert_eq!(format!("{:?}", list), "DList [\"just\", \"one\", \"test\", \"more\"]"); + let list: LinkedList<_> = vec!["just", "one", "test", "more"].iter().cloned().collect(); + assert_eq!(format!("{:?}", list), "LinkedList [\"just\", \"one\", \"test\", \"more\"]"); } #[cfg(test)] fn fuzz_test(sz: i32) { - let mut m: DList<_> = DList::new(); + let mut m: LinkedList<_> = LinkedList::new(); let mut v = vec![]; for i in 0..sz { check_links(&m); @@ -1432,13 +1449,13 @@ mod tests { fn bench_collect_into(b: &mut test::Bencher) { let v = &[0; 64]; b.iter(|| { - let _: DList<_> = v.iter().cloned().collect(); + let _: LinkedList<_> = v.iter().cloned().collect(); }) } #[bench] fn bench_push_front(b: &mut test::Bencher) { - let mut m: DList<_> = DList::new(); + let mut m: LinkedList<_> = LinkedList::new(); b.iter(|| { m.push_front(0); }) @@ -1446,7 +1463,7 @@ mod tests { #[bench] fn bench_push_back(b: &mut test::Bencher) { - let mut m: DList<_> = DList::new(); + let mut m: LinkedList<_> = LinkedList::new(); b.iter(|| { m.push_back(0); }) @@ -1454,7 +1471,7 @@ mod tests { #[bench] fn bench_push_back_pop_back(b: &mut test::Bencher) { - let mut m: DList<_> = DList::new(); + let mut m: LinkedList<_> = LinkedList::new(); b.iter(|| { m.push_back(0); m.pop_back(); @@ -1463,7 +1480,7 @@ mod tests { #[bench] fn bench_push_front_pop_front(b: &mut test::Bencher) { - let mut m: DList<_> = DList::new(); + let mut m: LinkedList<_> = LinkedList::new(); b.iter(|| { m.push_front(0); m.pop_front(); @@ -1473,7 +1490,7 @@ mod tests { #[bench] fn bench_iter(b: &mut test::Bencher) { let v = &[0; 128]; - let m: DList<_> = v.iter().cloned().collect(); + let m: LinkedList<_> = v.iter().cloned().collect(); b.iter(|| { assert!(m.iter().count() == 128); }) @@ -1481,7 +1498,7 @@ mod tests { #[bench] fn bench_iter_mut(b: &mut test::Bencher) { let v = &[0; 128]; - let mut m: DList<_> = v.iter().cloned().collect(); + let mut m: LinkedList<_> = v.iter().cloned().collect(); b.iter(|| { assert!(m.iter_mut().count() == 128); }) @@ -1489,7 +1506,7 @@ mod tests { #[bench] fn bench_iter_rev(b: &mut test::Bencher) { let v = &[0; 128]; - let m: DList<_> = v.iter().cloned().collect(); + let m: LinkedList<_> = v.iter().cloned().collect(); b.iter(|| { assert!(m.iter().rev().count() == 128); }) @@ -1497,7 +1514,7 @@ mod tests { #[bench] fn bench_iter_mut_rev(b: &mut test::Bencher) { let v = &[0; 128]; - let mut m: DList<_> = v.iter().cloned().collect(); + let mut m: LinkedList<_> = v.iter().cloned().collect(); b.iter(|| { assert!(m.iter_mut().rev().count() == 128); }) diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs index 06ae8127c00..776b8b3af14 100644 --- a/src/libcollections/slice.rs +++ b/src/libcollections/slice.rs @@ -88,7 +88,6 @@ #![stable(feature = "rust1", since = "1.0.0")] use alloc::boxed::Box; -use core::borrow::{BorrowFrom, BorrowFromMut, ToOwned}; use core::clone::Clone; use core::cmp::Ordering::{self, Greater, Less}; use core::cmp::{self, Ord, PartialEq}; @@ -105,6 +104,7 @@ use core::result::Result; use core::slice as core_slice; use self::Direction::*; +use borrow::{Borrow, BorrowMut, ToOwned}; use vec::Vec; pub use core::slice::{Chunks, AsSlice, Windows}; @@ -1175,18 +1175,19 @@ impl ElementSwaps { // Standard trait implementations for slices //////////////////////////////////////////////////////////////////////////////// -#[unstable(feature = "collections", reason = "trait is unstable")] -impl<T> BorrowFrom<Vec<T>> for [T] { - fn borrow_from(owned: &Vec<T>) -> &[T] { &owned[] } +#[stable(feature = "rust1", since = "1.0.0")] +impl<T> Borrow<[T]> for Vec<T> { + fn borrow(&self) -> &[T] { &self[..] } } -#[unstable(feature = "collections", reason = "trait is unstable")] -impl<T> BorrowFromMut<Vec<T>> for [T] { - fn borrow_from_mut(owned: &mut Vec<T>) -> &mut [T] { &mut owned[] } +#[stable(feature = "rust1", since = "1.0.0")] +impl<T> BorrowMut<[T]> for Vec<T> { + fn borrow_mut(&mut self) -> &mut [T] { &mut self[..] } } -#[unstable(feature = "collections", reason = "trait is unstable")] -impl<T: Clone> ToOwned<Vec<T>> for [T] { +#[stable(feature = "rust1", since = "1.0.0")] +impl<T: Clone> ToOwned for [T] { + type Owned = Vec<T>; fn to_owned(&self) -> Vec<T> { self.to_vec() } } @@ -1743,7 +1744,7 @@ mod tests { #[test] fn test_slice_from() { let vec: &[_] = &[1, 2, 3, 4]; - assert_eq!(&vec[], vec); + assert_eq!(&vec[..], vec); let b: &[_] = &[3, 4]; assert_eq!(&vec[2..], b); let b: &[_] = &[]; @@ -2264,15 +2265,15 @@ mod tests { #[test] fn test_total_ord() { let c = &[1, 2, 3]; - [1, 2, 3, 4][].cmp(c) == Greater; + [1, 2, 3, 4][..].cmp(c) == Greater; let c = &[1, 2, 3, 4]; - [1, 2, 3][].cmp(c) == Less; + [1, 2, 3][..].cmp(c) == Less; let c = &[1, 2, 3, 6]; - [1, 2, 3, 4][].cmp(c) == Equal; + [1, 2, 3, 4][..].cmp(c) == Equal; let c = &[1, 2, 3, 4, 5, 6]; - [1, 2, 3, 4, 5, 5, 5, 5][].cmp(c) == Less; + [1, 2, 3, 4, 5, 5, 5, 5][..].cmp(c) == Less; let c = &[1, 2, 3, 4]; - [2, 2][].cmp(c) == Greater; + [2, 2][..].cmp(c) == Greater; } #[test] diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs index 2d4dc2bcf30..ec0a487acdc 100644 --- a/src/libcollections/str.rs +++ b/src/libcollections/str.rs @@ -55,7 +55,6 @@ use self::RecompositionState::*; use self::DecompositionType::*; -use core::borrow::{BorrowFrom, ToOwned}; use core::char::CharExt; use core::clone::Clone; use core::iter::AdditiveIterator; @@ -68,7 +67,8 @@ use core::slice::AsSlice; use core::str as core_str; use unicode::str::{UnicodeStr, Utf16Encoder}; -use ring_buf::RingBuf; +use vec_deque::VecDeque; +use borrow::{Borrow, ToOwned}; use slice::SliceExt; use string::String; use unicode; @@ -261,7 +261,7 @@ enum RecompositionState { pub struct Recompositions<'a> { iter: Decompositions<'a>, state: RecompositionState, - buffer: RingBuf<char>, + buffer: VecDeque<char>, composee: Option<char>, last_ccc: Option<u8> } @@ -386,13 +386,14 @@ macro_rules! utf8_acc_cont_byte { ($ch:expr, $byte:expr) => (($ch << 6) | ($byte & 63u8) as u32) } -#[unstable(feature = "collections", reason = "trait is unstable")] -impl BorrowFrom<String> for str { - fn borrow_from(owned: &String) -> &str { &owned[] } +#[stable(feature = "rust1", since = "1.0.0")] +impl Borrow<str> for String { + fn borrow(&self) -> &str { &self[..] } } -#[unstable(feature = "collections", reason = "trait is unstable")] -impl ToOwned<String> for str { +#[stable(feature = "rust1", since = "1.0.0")] +impl ToOwned for str { + type Owned = String; fn to_owned(&self) -> String { unsafe { String::from_utf8_unchecked(self.as_bytes().to_owned()) @@ -466,7 +467,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { reason = "this functionality may be moved to libunicode")] fn nfd_chars(&self) -> Decompositions { Decompositions { - iter: self[].chars(), + iter: self[..].chars(), buffer: Vec::new(), sorted: false, kind: Canonical @@ -480,7 +481,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { reason = "this functionality may be moved to libunicode")] fn nfkd_chars(&self) -> Decompositions { Decompositions { - iter: self[].chars(), + iter: self[..].chars(), buffer: Vec::new(), sorted: false, kind: Compatible @@ -496,7 +497,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { Recompositions { iter: self.nfd_chars(), state: Composing, - buffer: RingBuf::new(), + buffer: VecDeque::new(), composee: None, last_ccc: None } @@ -511,7 +512,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { Recompositions { iter: self.nfkd_chars(), state: Composing, - buffer: RingBuf::new(), + buffer: VecDeque::new(), composee: None, last_ccc: None } @@ -530,7 +531,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn contains(&self, pat: &str) -> bool { - core_str::StrExt::contains(&self[], pat) + core_str::StrExt::contains(&self[..], pat) } /// Returns true if a string contains a char pattern. @@ -547,7 +548,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "might get removed in favour of a more generic contains()")] fn contains_char<P: CharEq>(&self, pat: P) -> bool { - core_str::StrExt::contains_char(&self[], pat) + core_str::StrExt::contains_char(&self[..], pat) } /// An iterator over the characters of `self`. Note, this iterates @@ -561,7 +562,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn chars(&self) -> Chars { - core_str::StrExt::chars(&self[]) + core_str::StrExt::chars(&self[..]) } /// An iterator over the bytes of `self` @@ -574,13 +575,13 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn bytes(&self) -> Bytes { - core_str::StrExt::bytes(&self[]) + core_str::StrExt::bytes(&self[..]) } /// An iterator over the characters of `self` and their byte offsets. #[stable(feature = "rust1", since = "1.0.0")] fn char_indices(&self) -> CharIndices { - core_str::StrExt::char_indices(&self[]) + core_str::StrExt::char_indices(&self[..]) } /// An iterator over substrings of `self`, separated by characters @@ -603,7 +604,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn split<P: CharEq>(&self, pat: P) -> Split<P> { - core_str::StrExt::split(&self[], pat) + core_str::StrExt::split(&self[..], pat) } /// An iterator over substrings of `self`, separated by characters @@ -630,7 +631,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn splitn<P: CharEq>(&self, count: usize, pat: P) -> SplitN<P> { - core_str::StrExt::splitn(&self[], count, pat) + core_str::StrExt::splitn(&self[..], count, pat) } /// An iterator over substrings of `self`, separated by characters @@ -659,7 +660,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[unstable(feature = "collections", reason = "might get removed")] fn split_terminator<P: CharEq>(&self, pat: P) -> SplitTerminator<P> { - core_str::StrExt::split_terminator(&self[], pat) + core_str::StrExt::split_terminator(&self[..], pat) } /// An iterator over substrings of `self`, separated by characters @@ -680,7 +681,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn rsplitn<P: CharEq>(&self, count: usize, pat: P) -> RSplitN<P> { - core_str::StrExt::rsplitn(&self[], count, pat) + core_str::StrExt::rsplitn(&self[..], count, pat) } /// An iterator over the start and end indices of the disjoint @@ -706,7 +707,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "might have its iterator type changed")] fn match_indices<'a>(&'a self, pat: &'a str) -> MatchIndices<'a> { - core_str::StrExt::match_indices(&self[], pat) + core_str::StrExt::match_indices(&self[..], pat) } /// An iterator over the substrings of `self` separated by the pattern `sep`. @@ -723,7 +724,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "might get removed in the future in favor of a more generic split()")] fn split_str<'a>(&'a self, pat: &'a str) -> SplitStr<'a> { - core_str::StrExt::split_str(&self[], pat) + core_str::StrExt::split_str(&self[..], pat) } /// An iterator over the lines of a string (subsequences separated @@ -739,7 +740,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn lines(&self) -> Lines { - core_str::StrExt::lines(&self[]) + core_str::StrExt::lines(&self[..]) } /// An iterator over the lines of a string, separated by either @@ -755,7 +756,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn lines_any(&self) -> LinesAny { - core_str::StrExt::lines_any(&self[]) + core_str::StrExt::lines_any(&self[..]) } /// Deprecated: use `s[a .. b]` instead. @@ -802,7 +803,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "may have yet to prove its worth")] fn slice_chars(&self, begin: usize, end: usize) -> &str { - core_str::StrExt::slice_chars(&self[], begin, end) + core_str::StrExt::slice_chars(&self[..], begin, end) } /// Takes a bytewise (not UTF-8) slice from a string. @@ -813,7 +814,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// the entire slice as well. #[stable(feature = "rust1", since = "1.0.0")] unsafe fn slice_unchecked(&self, begin: usize, end: usize) -> &str { - core_str::StrExt::slice_unchecked(&self[], begin, end) + core_str::StrExt::slice_unchecked(&self[..], begin, end) } /// Returns true if the pattern `pat` is a prefix of the string. @@ -825,7 +826,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn starts_with(&self, pat: &str) -> bool { - core_str::StrExt::starts_with(&self[], pat) + core_str::StrExt::starts_with(&self[..], pat) } /// Returns true if the pattern `pat` is a suffix of the string. @@ -837,7 +838,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn ends_with(&self, pat: &str) -> bool { - core_str::StrExt::ends_with(&self[], pat) + core_str::StrExt::ends_with(&self[..], pat) } /// Returns a string with all pre- and suffixes that match @@ -857,7 +858,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn trim_matches<P: CharEq>(&self, pat: P) -> &str { - core_str::StrExt::trim_matches(&self[], pat) + core_str::StrExt::trim_matches(&self[..], pat) } /// Returns a string with all prefixes that match @@ -877,7 +878,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn trim_left_matches<P: CharEq>(&self, pat: P) -> &str { - core_str::StrExt::trim_left_matches(&self[], pat) + core_str::StrExt::trim_left_matches(&self[..], pat) } /// Returns a string with all suffixes that match @@ -897,7 +898,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn trim_right_matches<P: CharEq>(&self, pat: P) -> &str { - core_str::StrExt::trim_right_matches(&self[], pat) + core_str::StrExt::trim_right_matches(&self[..], pat) } /// Check that `index`-th byte lies at the start and/or end of a @@ -926,7 +927,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "naming is uncertain with container conventions")] fn is_char_boundary(&self, index: usize) -> bool { - core_str::StrExt::is_char_boundary(&self[], index) + core_str::StrExt::is_char_boundary(&self[..], index) } /// Pluck a character out of a string and return the index of the next @@ -985,7 +986,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "naming is uncertain with container conventions")] fn char_range_at(&self, start: usize) -> CharRange { - core_str::StrExt::char_range_at(&self[], start) + core_str::StrExt::char_range_at(&self[..], start) } /// Given a byte position and a str, return the previous char and its position. @@ -1001,7 +1002,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "naming is uncertain with container conventions")] fn char_range_at_reverse(&self, start: usize) -> CharRange { - core_str::StrExt::char_range_at_reverse(&self[], start) + core_str::StrExt::char_range_at_reverse(&self[..], start) } /// Plucks the character starting at the `i`th byte of a string. @@ -1022,7 +1023,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "naming is uncertain with container conventions")] fn char_at(&self, i: usize) -> char { - core_str::StrExt::char_at(&self[], i) + core_str::StrExt::char_at(&self[..], i) } /// Plucks the character ending at the `i`th byte of a string. @@ -1034,7 +1035,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "naming is uncertain with container conventions")] fn char_at_reverse(&self, i: usize) -> char { - core_str::StrExt::char_at_reverse(&self[], i) + core_str::StrExt::char_at_reverse(&self[..], i) } /// Work with the byte buffer of a string as a byte slice. @@ -1046,7 +1047,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn as_bytes(&self) -> &[u8] { - core_str::StrExt::as_bytes(&self[]) + core_str::StrExt::as_bytes(&self[..]) } /// Returns the byte index of the first character of `self` that @@ -1074,7 +1075,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn find<P: CharEq>(&self, pat: P) -> Option<usize> { - core_str::StrExt::find(&self[], pat) + core_str::StrExt::find(&self[..], pat) } /// Returns the byte index of the last character of `self` that @@ -1102,7 +1103,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { /// ``` #[stable(feature = "rust1", since = "1.0.0")] fn rfind<P: CharEq>(&self, pat: P) -> Option<usize> { - core_str::StrExt::rfind(&self[], pat) + core_str::StrExt::rfind(&self[..], pat) } /// Returns the byte index of the first matching substring @@ -1127,7 +1128,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "might get removed in favor of a more generic find in the future")] fn find_str(&self, needle: &str) -> Option<usize> { - core_str::StrExt::find_str(&self[], needle) + core_str::StrExt::find_str(&self[..], needle) } /// Retrieves the first character from a string slice and returns @@ -1151,7 +1152,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "awaiting conventions about shifting and slices")] fn slice_shift_char(&self) -> Option<(char, &str)> { - core_str::StrExt::slice_shift_char(&self[]) + core_str::StrExt::slice_shift_char(&self[..]) } /// Returns the byte offset of an inner slice relative to an enclosing outer slice. @@ -1171,7 +1172,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "awaiting convention about comparability of arbitrary slices")] fn subslice_offset(&self, inner: &str) -> usize { - core_str::StrExt::subslice_offset(&self[], inner) + core_str::StrExt::subslice_offset(&self[..], inner) } /// Return an unsafe pointer to the strings buffer. @@ -1182,14 +1183,14 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[stable(feature = "rust1", since = "1.0.0")] #[inline] fn as_ptr(&self) -> *const u8 { - core_str::StrExt::as_ptr(&self[]) + core_str::StrExt::as_ptr(&self[..]) } /// Return an iterator of `u16` over the string encoded as UTF-16. #[unstable(feature = "collections", reason = "this functionality may only be provided by libunicode")] fn utf16_units(&self) -> Utf16Units { - Utf16Units { encoder: Utf16Encoder::new(self[].chars()) } + Utf16Units { encoder: Utf16Encoder::new(self[..].chars()) } } /// Return the number of bytes in this string @@ -1203,7 +1204,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[stable(feature = "rust1", since = "1.0.0")] #[inline] fn len(&self) -> usize { - core_str::StrExt::len(&self[]) + core_str::StrExt::len(&self[..]) } /// Returns true if this slice contains no bytes @@ -1216,7 +1217,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[inline] #[stable(feature = "rust1", since = "1.0.0")] fn is_empty(&self) -> bool { - core_str::StrExt::is_empty(&self[]) + core_str::StrExt::is_empty(&self[..]) } /// Parse this string into the specified type. @@ -1230,7 +1231,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[inline] #[stable(feature = "rust1", since = "1.0.0")] fn parse<F: FromStr>(&self) -> Result<F, F::Err> { - core_str::StrExt::parse(&self[]) + core_str::StrExt::parse(&self[..]) } /// Returns an iterator over the @@ -1255,7 +1256,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "this functionality may only be provided by libunicode")] fn graphemes(&self, is_extended: bool) -> Graphemes { - UnicodeStr::graphemes(&self[], is_extended) + UnicodeStr::graphemes(&self[..], is_extended) } /// Returns an iterator over the grapheme clusters of self and their byte offsets. @@ -1271,7 +1272,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "this functionality may only be provided by libunicode")] fn grapheme_indices(&self, is_extended: bool) -> GraphemeIndices { - UnicodeStr::grapheme_indices(&self[], is_extended) + UnicodeStr::grapheme_indices(&self[..], is_extended) } /// An iterator over the words of a string (subsequences separated @@ -1288,7 +1289,7 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "str_words", reason = "the precise algorithm to use is unclear")] fn words(&self) -> Words { - UnicodeStr::words(&self[]) + UnicodeStr::words(&self[..]) } /// Returns a string's displayed width in columns, treating control @@ -1303,25 +1304,25 @@ pub trait StrExt: Index<RangeFull, Output = str> { #[unstable(feature = "collections", reason = "this functionality may only be provided by libunicode")] fn width(&self, is_cjk: bool) -> usize { - UnicodeStr::width(&self[], is_cjk) + UnicodeStr::width(&self[..], is_cjk) } /// Returns a string with leading and trailing whitespace removed. #[stable(feature = "rust1", since = "1.0.0")] fn trim(&self) -> &str { - UnicodeStr::trim(&self[]) + UnicodeStr::trim(&self[..]) } /// Returns a string with leading whitespace removed. #[stable(feature = "rust1", since = "1.0.0")] fn trim_left(&self) -> &str { - UnicodeStr::trim_left(&self[]) + UnicodeStr::trim_left(&self[..]) } /// Returns a string with trailing whitespace removed. #[stable(feature = "rust1", since = "1.0.0")] fn trim_right(&self) -> &str { - UnicodeStr::trim_right(&self[]) + UnicodeStr::trim_right(&self[..]) } } @@ -2704,7 +2705,7 @@ mod tests { &["\u{378}\u{308}\u{903}"], &["\u{378}\u{308}", "\u{903}"]), ]; - for &(s, g) in &test_same[] { + for &(s, g) in &test_same[..] { // test forward iterator assert!(order::equals(s.graphemes(true), g.iter().cloned())); assert!(order::equals(s.graphemes(false), g.iter().cloned())); diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs index 69fd28d1723..3b179d0b94c 100644 --- a/src/libcollections/string.rs +++ b/src/libcollections/string.rs @@ -16,12 +16,11 @@ use core::prelude::*; -use core::borrow::{Cow, IntoCow}; use core::default::Default; use core::error::Error; use core::fmt; use core::hash; -use core::iter::FromIterator; +use core::iter::{IntoIterator, FromIterator}; use core::mem; use core::ops::{self, Deref, Add, Index}; use core::ptr; @@ -29,6 +28,7 @@ use core::raw::Slice as RawSlice; use unicode::str as unicode_str; use unicode::str::Utf16Item; +use borrow::{Cow, IntoCow}; use str::{self, CharRange, FromStr, Utf8Error}; use vec::{DerefVec, Vec, as_vec}; @@ -142,7 +142,7 @@ impl String { /// assert_eq!(output.as_slice(), "Hello \u{FFFD}World"); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn from_utf8_lossy<'a>(v: &'a [u8]) -> CowString<'a> { + pub fn from_utf8_lossy<'a>(v: &'a [u8]) -> Cow<'a, str> { let mut i = 0; match str::from_utf8(v) { Ok(s) => return Cow::Borrowed(s), @@ -709,18 +709,18 @@ impl Error for FromUtf16Error { #[stable(feature = "rust1", since = "1.0.0")] impl FromIterator<char> for String { - fn from_iter<I:Iterator<Item=char>>(iterator: I) -> String { + fn from_iter<I: IntoIterator<Item=char>>(iter: I) -> String { let mut buf = String::new(); - buf.extend(iterator); + buf.extend(iter); buf } } #[stable(feature = "rust1", since = "1.0.0")] impl<'a> FromIterator<&'a str> for String { - fn from_iter<I:Iterator<Item=&'a str>>(iterator: I) -> String { + fn from_iter<I: IntoIterator<Item=&'a str>>(iter: I) -> String { let mut buf = String::new(); - buf.extend(iterator); + buf.extend(iter); buf } } @@ -728,7 +728,8 @@ impl<'a> FromIterator<&'a str> for String { #[unstable(feature = "collections", reason = "waiting on Extend stabilization")] impl Extend<char> for String { - fn extend<I:Iterator<Item=char>>(&mut self, iterator: I) { + fn extend<I: IntoIterator<Item=char>>(&mut self, iterable: I) { + let iterator = iterable.into_iter(); let (lower_bound, _) = iterator.size_hint(); self.reserve(lower_bound); for ch in iterator { @@ -740,7 +741,8 @@ impl Extend<char> for String { #[unstable(feature = "collections", reason = "waiting on Extend stabilization")] impl<'a> Extend<&'a str> for String { - fn extend<I: Iterator<Item=&'a str>>(&mut self, iterator: I) { + fn extend<I: IntoIterator<Item=&'a str>>(&mut self, iterable: I) { + let iterator = iterable.into_iter(); // A guess that at least one byte per iterator element will be needed. let (lower_bound, _) = iterator.size_hint(); self.reserve(lower_bound); @@ -780,10 +782,10 @@ macro_rules! impl_eq { } impl_eq! { String, &'a str } -impl_eq! { CowString<'a>, String } +impl_eq! { Cow<'a, str>, String } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, 'b> PartialEq<&'b str> for CowString<'a> { +impl<'a, 'b> PartialEq<&'b str> for Cow<'a, str> { #[inline] fn eq(&self, other: &&'b str) -> bool { PartialEq::eq(&**self, &**other) } #[inline] @@ -791,11 +793,11 @@ impl<'a, 'b> PartialEq<&'b str> for CowString<'a> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, 'b> PartialEq<CowString<'a>> for &'b str { +impl<'a, 'b> PartialEq<Cow<'a, str>> for &'b str { #[inline] - fn eq(&self, other: &CowString<'a>) -> bool { PartialEq::eq(&**self, &**other) } + fn eq(&self, other: &Cow<'a, str>) -> bool { PartialEq::eq(&**self, &**other) } #[inline] - fn ne(&self, other: &CowString<'a>) -> bool { PartialEq::ne(&**self, &**other) } + fn ne(&self, other: &Cow<'a, str>) -> bool { PartialEq::ne(&**self, &**other) } } #[unstable(feature = "collections", reason = "waiting on Str stabilization")] @@ -833,12 +835,21 @@ impl fmt::Debug for String { } #[unstable(feature = "collections", reason = "waiting on Hash stabilization")] +#[cfg(stage0)] impl<H: hash::Writer + hash::Hasher> hash::Hash<H> for String { #[inline] fn hash(&self, hasher: &mut H) { (**self).hash(hasher) } } +#[stable(feature = "rust1", since = "1.0.0")] +#[cfg(not(stage0))] +impl hash::Hash for String { + #[inline] + fn hash<H: hash::Hasher>(&self, hasher: &mut H) { + (**self).hash(hasher) + } +} #[unstable(feature = "collections", reason = "recent addition, needs more experience")] @@ -857,7 +868,7 @@ impl ops::Index<ops::Range<usize>> for String { type Output = str; #[inline] fn index(&self, index: &ops::Range<usize>) -> &str { - &self[][*index] + &self[..][*index] } } #[stable(feature = "rust1", since = "1.0.0")] @@ -865,7 +876,7 @@ impl ops::Index<ops::RangeTo<usize>> for String { type Output = str; #[inline] fn index(&self, index: &ops::RangeTo<usize>) -> &str { - &self[][*index] + &self[..][*index] } } #[stable(feature = "rust1", since = "1.0.0")] @@ -873,7 +884,7 @@ impl ops::Index<ops::RangeFrom<usize>> for String { type Output = str; #[inline] fn index(&self, index: &ops::RangeFrom<usize>) -> &str { - &self[][*index] + &self[..][*index] } } #[stable(feature = "rust1", since = "1.0.0")] @@ -891,7 +902,7 @@ impl ops::Deref for String { #[inline] fn deref(&self) -> &str { - unsafe { mem::transmute(&self.vec[]) } + unsafe { mem::transmute(&self.vec[..]) } } } @@ -958,31 +969,34 @@ impl<T: fmt::Display + ?Sized> ToString for T { } } -impl IntoCow<'static, String, str> for String { +#[stable(feature = "rust1", since = "1.0.0")] +impl IntoCow<'static, str> for String { #[inline] - fn into_cow(self) -> CowString<'static> { + fn into_cow(self) -> Cow<'static, str> { Cow::Owned(self) } } -impl<'a> IntoCow<'a, String, str> for &'a str { +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a> IntoCow<'a, str> for &'a str { #[inline] - fn into_cow(self) -> CowString<'a> { + fn into_cow(self) -> Cow<'a, str> { Cow::Borrowed(self) } } -/// A clone-on-write string -#[stable(feature = "rust1", since = "1.0.0")] -pub type CowString<'a> = Cow<'a, String, str>; - -impl<'a> Str for CowString<'a> { +impl<'a> Str for Cow<'a, str> { #[inline] fn as_slice<'b>(&'b self) -> &'b str { &**self } } +/// A clone-on-write string +#[deprecated(since = "1.0.0", reason = "use Cow<'a, str> instead")] +#[stable(feature = "rust1", since = "1.0.0")] +pub type CowString<'a> = Cow<'a, str>; + #[stable(feature = "rust1", since = "1.0.0")] impl fmt::Write for String { #[inline] @@ -1287,7 +1301,7 @@ mod tests { #[test] fn test_slicing() { let s = "foobar".to_string(); - assert_eq!("foobar", &s[]); + assert_eq!("foobar", &s[..]); assert_eq!("foo", &s[..3]); assert_eq!("bar", &s[3..]); assert_eq!("oob", &s[1..4]); diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs index bde733644b5..1cc2a5235ab 100644 --- a/src/libcollections/vec.rs +++ b/src/libcollections/vec.rs @@ -50,24 +50,26 @@ use core::prelude::*; use alloc::boxed::Box; use alloc::heap::{EMPTY, allocate, reallocate, deallocate}; -use core::borrow::{Cow, IntoCow}; use core::cmp::max; use core::cmp::{Ordering}; use core::default::Default; use core::fmt; use core::hash::{self, Hash}; +use core::intrinsics::assume; use core::iter::{repeat, FromIterator, IntoIterator}; -use core::marker::{self, ContravariantLifetime, InvariantType}; +use core::marker::PhantomData; use core::mem; -use core::nonzero::NonZero; use core::num::{Int, UnsignedInt}; use core::ops::{Index, IndexMut, Deref, Add}; use core::ops; use core::ptr; +use core::ptr::Unique; use core::raw::Slice as RawSlice; use core::slice; use core::usize; +use borrow::{Cow, IntoCow}; + /// A growable list type, written `Vec<T>` but pronounced 'vector.' /// /// # Examples @@ -137,10 +139,9 @@ use core::usize; #[unsafe_no_drop_flag] #[stable(feature = "rust1", since = "1.0.0")] pub struct Vec<T> { - ptr: NonZero<*mut T>, + ptr: Unique<T>, len: usize, cap: usize, - _own: marker::PhantomData<T>, } unsafe impl<T: Send> Send for Vec<T> { } @@ -249,10 +250,9 @@ impl<T> Vec<T> { pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Vec<T> { Vec { - ptr: NonZero::new(ptr), + ptr: Unique::new(ptr), len: length, cap: capacity, - _own: marker::PhantomData, } } @@ -373,7 +373,7 @@ impl<T> Vec<T> { self.len * mem::size_of::<T>(), mem::min_align_of::<T>()) as *mut T; if ptr.is_null() { ::alloc::oom() } - self.ptr = NonZero::new(ptr); + self.ptr = Unique::new(ptr); } self.cap = self.len; } @@ -655,7 +655,7 @@ impl<T> Vec<T> { unsafe { let ptr = alloc_or_realloc(*self.ptr, old_size, size); if ptr.is_null() { ::alloc::oom() } - self.ptr = NonZero::new(ptr); + self.ptr = Unique::new(ptr); } self.cap = max(self.cap, 2) * 2; } @@ -756,7 +756,7 @@ impl<T> Vec<T> { Drain { ptr: begin, end: end, - marker: ContravariantLifetime, + marker: PhantomData, } } } @@ -871,6 +871,8 @@ impl<T> Vec<T> { end_t: unsafe { start.offset(offset) }, start_u: start as *mut U, end_u: start as *mut U, + + _marker: PhantomData, }; // start_t // start_u @@ -967,8 +969,7 @@ impl<T> Vec<T> { let mut pv = PartialVecZeroSized::<T,U> { num_t: vec.len(), num_u: 0, - marker_t: InvariantType, - marker_u: InvariantType, + marker: PhantomData, }; unsafe { mem::forget(vec); } @@ -1226,7 +1227,7 @@ impl<T> Vec<T> { unsafe { let ptr = alloc_or_realloc(*self.ptr, self.cap * mem::size_of::<T>(), size); if ptr.is_null() { ::alloc::oom() } - self.ptr = NonZero::new(ptr); + self.ptr = Unique::new(ptr); } self.cap = capacity; } @@ -1302,12 +1303,21 @@ impl<T:Clone> Clone for Vec<T> { } } +#[cfg(stage0)] impl<S: hash::Writer + hash::Hasher, T: Hash<S>> Hash<S> for Vec<T> { #[inline] fn hash(&self, state: &mut S) { Hash::hash(&**self, state) } } +#[stable(feature = "rust1", since = "1.0.0")] +#[cfg(not(stage0))] +impl<T: Hash> Hash for Vec<T> { + #[inline] + fn hash<H: hash::Hasher>(&self, state: &mut H) { + Hash::hash(&**self, state) + } +} #[stable(feature = "rust1", since = "1.0.0")] impl<T> Index<usize> for Vec<T> { @@ -1407,7 +1417,8 @@ impl<T> ops::DerefMut for Vec<T> { #[stable(feature = "rust1", since = "1.0.0")] impl<T> FromIterator<T> for Vec<T> { #[inline] - fn from_iter<I:Iterator<Item=T>>(mut iterator: I) -> Vec<T> { + fn from_iter<I: IntoIterator<Item=T>>(iterable: I) -> Vec<T> { + let mut iterator = iterable.into_iter(); let (lower, _) = iterator.size_hint(); let mut vector = Vec::with_capacity(lower); @@ -1480,7 +1491,8 @@ impl<'a, T> IntoIterator for &'a mut Vec<T> { #[unstable(feature = "collections", reason = "waiting on Extend stability")] impl<T> Extend<T> for Vec<T> { #[inline] - fn extend<I: Iterator<Item=T>>(&mut self, iterator: I) { + fn extend<I: IntoIterator<Item=T>>(&mut self, iterable: I) { + let iterator = iterable.into_iter(); let (lower, _) = iterator.size_hint(); self.reserve(lower); for element in iterator { @@ -1517,34 +1529,34 @@ macro_rules! impl_eq { impl_eq! { Vec<A>, &'b [B] } impl_eq! { Vec<A>, &'b mut [B] } -impl<'a, A, B> PartialEq<Vec<B>> for CowVec<'a, A> where A: PartialEq<B> + Clone { +impl<'a, A, B> PartialEq<Vec<B>> for Cow<'a, [A]> where A: PartialEq<B> + Clone { #[inline] fn eq(&self, other: &Vec<B>) -> bool { PartialEq::eq(&**self, &**other) } #[inline] fn ne(&self, other: &Vec<B>) -> bool { PartialEq::ne(&**self, &**other) } } -impl<'a, A, B> PartialEq<CowVec<'a, A>> for Vec<B> where A: Clone, B: PartialEq<A> { +impl<'a, A, B> PartialEq<Cow<'a, [A]>> for Vec<B> where A: Clone, B: PartialEq<A> { #[inline] - fn eq(&self, other: &CowVec<'a, A>) -> bool { PartialEq::eq(&**self, &**other) } + fn eq(&self, other: &Cow<'a, [A]>) -> bool { PartialEq::eq(&**self, &**other) } #[inline] - fn ne(&self, other: &CowVec<'a, A>) -> bool { PartialEq::ne(&**self, &**other) } + fn ne(&self, other: &Cow<'a, [A]>) -> bool { PartialEq::ne(&**self, &**other) } } macro_rules! impl_eq_for_cowvec { ($rhs:ty) => { - impl<'a, 'b, A, B> PartialEq<$rhs> for CowVec<'a, A> where A: PartialEq<B> + Clone { + impl<'a, 'b, A, B> PartialEq<$rhs> for Cow<'a, [A]> where A: PartialEq<B> + Clone { #[inline] fn eq(&self, other: &$rhs) -> bool { PartialEq::eq(&**self, &**other) } #[inline] fn ne(&self, other: &$rhs) -> bool { PartialEq::ne(&**self, &**other) } } - impl<'a, 'b, A, B> PartialEq<CowVec<'a, A>> for $rhs where A: Clone, B: PartialEq<A> { + impl<'a, 'b, A, B> PartialEq<Cow<'a, [A]>> for $rhs where A: Clone, B: PartialEq<A> { #[inline] - fn eq(&self, other: &CowVec<'a, A>) -> bool { PartialEq::eq(&**self, &**other) } + fn eq(&self, other: &Cow<'a, [A]>) -> bool { PartialEq::eq(&**self, &**other) } #[inline] - fn ne(&self, other: &CowVec<'a, A>) -> bool { PartialEq::ne(&**self, &**other) } + fn ne(&self, other: &Cow<'a, [A]>) -> bool { PartialEq::ne(&**self, &**other) } } } } @@ -1552,8 +1564,7 @@ macro_rules! impl_eq_for_cowvec { impl_eq_for_cowvec! { &'b [B] } impl_eq_for_cowvec! { &'b mut [B] } -#[unstable(feature = "collections", - reason = "waiting on PartialOrd stability")] +#[stable(feature = "rust1", since = "1.0.0")] impl<T: PartialOrd> PartialOrd for Vec<T> { #[inline] fn partial_cmp(&self, other: &Vec<T>) -> Option<Ordering> { @@ -1561,10 +1572,10 @@ impl<T: PartialOrd> PartialOrd for Vec<T> { } } -#[unstable(feature = "collections", reason = "waiting on Eq stability")] +#[stable(feature = "rust1", since = "1.0.0")] impl<T: Eq> Eq for Vec<T> {} -#[unstable(feature = "collections", reason = "waiting on Ord stability")] +#[stable(feature = "rust1", since = "1.0.0")] impl<T: Ord> Ord for Vec<T> { #[inline] fn cmp(&self, other: &Vec<T>) -> Ordering { @@ -1587,8 +1598,12 @@ impl<T> AsSlice<T> for Vec<T> { #[stable(feature = "rust1", since = "1.0.0")] fn as_slice(&self) -> &[T] { unsafe { + let p = *self.ptr; + if cfg!(not(stage0)) { // NOTE remove cfg after next snapshot + assume(p != 0 as *mut T); + } mem::transmute(RawSlice { - data: *self.ptr, + data: p, len: self.len }) } @@ -1643,26 +1658,26 @@ impl<T: fmt::Debug> fmt::Debug for Vec<T> { // Clone-on-write //////////////////////////////////////////////////////////////////////////////// -#[unstable(feature = "collections", - reason = "unclear how valuable this alias is")] /// A clone-on-write vector -pub type CowVec<'a, T> = Cow<'a, Vec<T>, [T]>; +#[deprecated(since = "1.0.0", reason = "use Cow<'a, [T]> instead")] +#[unstable(feature = "collections")] +pub type CowVec<'a, T> = Cow<'a, [T]>; #[unstable(feature = "collections")] -impl<'a, T> FromIterator<T> for CowVec<'a, T> where T: Clone { - fn from_iter<I: Iterator<Item=T>>(it: I) -> CowVec<'a, T> { +impl<'a, T> FromIterator<T> for Cow<'a, [T]> where T: Clone { + fn from_iter<I: IntoIterator<Item=T>>(it: I) -> Cow<'a, [T]> { Cow::Owned(FromIterator::from_iter(it)) } } -impl<'a, T: 'a> IntoCow<'a, Vec<T>, [T]> for Vec<T> where T: Clone { - fn into_cow(self) -> CowVec<'a, T> { +impl<'a, T: 'a> IntoCow<'a, [T]> for Vec<T> where T: Clone { + fn into_cow(self) -> Cow<'a, [T]> { Cow::Owned(self) } } -impl<'a, T> IntoCow<'a, Vec<T>, [T]> for &'a [T] where T: Clone { - fn into_cow(self) -> CowVec<'a, T> { +impl<'a, T> IntoCow<'a, [T]> for &'a [T] where T: Clone { + fn into_cow(self) -> Cow<'a, [T]> { Cow::Borrowed(self) } } @@ -1779,10 +1794,10 @@ impl<T> Drop for IntoIter<T> { #[unsafe_no_drop_flag] #[unstable(feature = "collections", reason = "recently added as part of collections reform 2")] -pub struct Drain<'a, T> { +pub struct Drain<'a, T:'a> { ptr: *const T, end: *const T, - marker: ContravariantLifetime<'a>, + marker: PhantomData<&'a T>, } #[stable(feature = "rust1", since = "1.0.0")] @@ -1867,9 +1882,9 @@ impl<'a, T> Drop for Drain<'a, T> { /// Wrapper type providing a `&Vec<T>` reference via `Deref`. #[unstable(feature = "collections")] -pub struct DerefVec<'a, T> { +pub struct DerefVec<'a, T:'a> { x: Vec<T>, - l: ContravariantLifetime<'a> + l: PhantomData<&'a T>, } #[unstable(feature = "collections")] @@ -1897,7 +1912,7 @@ pub fn as_vec<'a, T>(x: &'a [T]) -> DerefVec<'a, T> { unsafe { DerefVec { x: Vec::from_raw_parts(x.as_ptr() as *mut T, x.len(), x.len()), - l: ContravariantLifetime::<'a> + l: PhantomData, } } } @@ -1921,6 +1936,8 @@ struct PartialVecNonZeroSized<T,U> { end_u: *mut U, start_t: *mut T, end_t: *mut T, + + _marker: PhantomData<U>, } /// An owned, partially type-converted vector of zero-sized elements. @@ -1930,8 +1947,7 @@ struct PartialVecNonZeroSized<T,U> { struct PartialVecZeroSized<T,U> { num_t: usize, num_u: usize, - marker_t: InvariantType<T>, - marker_u: InvariantType<U>, + marker: PhantomData<::core::cell::Cell<(T,U)>>, } #[unsafe_destructor] @@ -2589,7 +2605,7 @@ mod tests { b.bytes = src_len as u64; b.iter(|| { - let dst = src.clone()[].to_vec(); + let dst = src.clone()[..].to_vec(); assert_eq!(dst.len(), src_len); assert!(dst.iter().enumerate().all(|(i, x)| i == *x)); }); diff --git a/src/libcollections/ring_buf.rs b/src/libcollections/vec_deque.rs index 6dcdb21f800..3ba22a41ff7 100644 --- a/src/libcollections/ring_buf.rs +++ b/src/libcollections/vec_deque.rs @@ -8,8 +8,8 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -//! RingBuf is a double-ended queue, which is implemented with the help of a -//! growing circular buffer. +//! VecDeque is a double-ended queue, which is implemented with the help of a +//! growing ring buffer. //! //! This queue has `O(1)` amortized inserts and removals from both ends of the //! container. It also has `O(1)` indexing like a vector. The contained elements @@ -28,20 +28,26 @@ use core::marker; use core::mem; use core::num::{Int, UnsignedInt}; use core::ops::{Index, IndexMut}; -use core::ptr; +use core::ptr::{self, Unique}; use core::raw::Slice as RawSlice; -use core::hash::{Writer, Hash, Hasher}; +use core::hash::{Hash, Hasher}; +#[cfg(stage0)] use core::hash::Writer; use core::cmp; use alloc::heap; +#[deprecated(since = "1.0.0", reason = "renamed to VecDeque")] +#[unstable(feature = "collections")] +pub use VecDeque as RingBuf; + static INITIAL_CAPACITY: usize = 7; // 2^3 - 1 static MINIMUM_CAPACITY: usize = 1; // 2 - 1 -/// `RingBuf` is a circular buffer, which can be used as a double-ended queue efficiently. +/// `VecDeque` is a growable ring buffer, which can be used as a +/// double-ended queue efficiently. #[stable(feature = "rust1", since = "1.0.0")] -pub struct RingBuf<T> { +pub struct VecDeque<T> { // tail and head are pointers into the buffer. Tail always points // to the first element that could be read, Head always points // to where data should be written. @@ -51,30 +57,30 @@ pub struct RingBuf<T> { tail: usize, head: usize, cap: usize, - ptr: *mut T + ptr: Unique<T>, } #[stable(feature = "rust1", since = "1.0.0")] -unsafe impl<T: Send> Send for RingBuf<T> {} +unsafe impl<T: Send> Send for VecDeque<T> {} #[stable(feature = "rust1", since = "1.0.0")] -unsafe impl<T: Sync> Sync for RingBuf<T> {} +unsafe impl<T: Sync> Sync for VecDeque<T> {} #[stable(feature = "rust1", since = "1.0.0")] -impl<T: Clone> Clone for RingBuf<T> { - fn clone(&self) -> RingBuf<T> { +impl<T: Clone> Clone for VecDeque<T> { + fn clone(&self) -> VecDeque<T> { self.iter().cloned().collect() } } #[unsafe_destructor] #[stable(feature = "rust1", since = "1.0.0")] -impl<T> Drop for RingBuf<T> { +impl<T> Drop for VecDeque<T> { fn drop(&mut self) { self.clear(); unsafe { if mem::size_of::<T>() != 0 { - heap::deallocate(self.ptr as *mut u8, + heap::deallocate(*self.ptr as *mut u8, self.cap * mem::size_of::<T>(), mem::min_align_of::<T>()) } @@ -83,22 +89,22 @@ impl<T> Drop for RingBuf<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<T> Default for RingBuf<T> { +impl<T> Default for VecDeque<T> { #[inline] - fn default() -> RingBuf<T> { RingBuf::new() } + fn default() -> VecDeque<T> { VecDeque::new() } } -impl<T> RingBuf<T> { +impl<T> VecDeque<T> { /// Turn ptr into a slice #[inline] unsafe fn buffer_as_slice(&self) -> &[T] { - mem::transmute(RawSlice { data: self.ptr, len: self.cap }) + mem::transmute(RawSlice { data: *self.ptr as *const T, len: self.cap }) } /// Turn ptr into a mut slice #[inline] unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T] { - mem::transmute(RawSlice { data: self.ptr, len: self.cap }) + mem::transmute(RawSlice { data: *self.ptr as *const T, len: self.cap }) } /// Moves an element out of the buffer @@ -149,48 +155,48 @@ impl<T> RingBuf<T> { } } -impl<T> RingBuf<T> { - /// Creates an empty `RingBuf`. +impl<T> VecDeque<T> { + /// Creates an empty `VecDeque`. #[stable(feature = "rust1", since = "1.0.0")] - pub fn new() -> RingBuf<T> { - RingBuf::with_capacity(INITIAL_CAPACITY) + pub fn new() -> VecDeque<T> { + VecDeque::with_capacity(INITIAL_CAPACITY) } - /// Creates an empty `RingBuf` with space for at least `n` elements. + /// Creates an empty `VecDeque` with space for at least `n` elements. #[stable(feature = "rust1", since = "1.0.0")] - pub fn with_capacity(n: usize) -> RingBuf<T> { + pub fn with_capacity(n: usize) -> VecDeque<T> { // +1 since the ringbuffer always leaves one space empty let cap = cmp::max(n + 1, MINIMUM_CAPACITY + 1).next_power_of_two(); assert!(cap > n, "capacity overflow"); let size = cap.checked_mul(mem::size_of::<T>()) .expect("capacity overflow"); - let ptr = if mem::size_of::<T>() != 0 { - unsafe { + let ptr = unsafe { + if mem::size_of::<T>() != 0 { let ptr = heap::allocate(size, mem::min_align_of::<T>()) as *mut T;; if ptr.is_null() { ::alloc::oom() } - ptr + Unique::new(ptr) + } else { + Unique::new(heap::EMPTY as *mut T) } - } else { - heap::EMPTY as *mut T }; - RingBuf { + VecDeque { tail: 0, head: 0, cap: cap, - ptr: ptr + ptr: ptr, } } - /// Retrieves an element in the `RingBuf` by index. + /// Retrieves an element in the `VecDeque` by index. /// /// # Examples /// /// ```rust - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// buf.push_back(3); /// buf.push_back(4); /// buf.push_back(5); @@ -206,14 +212,14 @@ impl<T> RingBuf<T> { } } - /// Retrieves an element in the `RingBuf` mutably by index. + /// Retrieves an element in the `VecDeque` mutably by index. /// /// # Examples /// /// ```rust - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// buf.push_back(3); /// buf.push_back(4); /// buf.push_back(5); @@ -245,9 +251,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ```rust - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// buf.push_back(3); /// buf.push_back(4); /// buf.push_back(5); @@ -266,15 +272,15 @@ impl<T> RingBuf<T> { } } - /// Returns the number of elements the `RingBuf` can hold without + /// Returns the number of elements the `VecDeque` can hold without /// reallocating. /// /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let buf: RingBuf<i32> = RingBuf::with_capacity(10); + /// let buf: VecDeque<i32> = VecDeque::with_capacity(10); /// assert!(buf.capacity() >= 10); /// ``` #[inline] @@ -282,7 +288,7 @@ impl<T> RingBuf<T> { pub fn capacity(&self) -> usize { self.cap - 1 } /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the - /// given `RingBuf`. Does nothing if the capacity is already sufficient. + /// given `VecDeque`. Does nothing if the capacity is already sufficient. /// /// Note that the allocator may give the collection more space than it requests. Therefore /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future @@ -295,9 +301,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf: RingBuf<i32> = vec![1].into_iter().collect(); + /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect(); /// buf.reserve_exact(10); /// assert!(buf.capacity() >= 11); /// ``` @@ -316,9 +322,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf: RingBuf<i32> = vec![1].into_iter().collect(); + /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect(); /// buf.reserve(10); /// assert!(buf.capacity() >= 11); /// ``` @@ -335,11 +341,12 @@ impl<T> RingBuf<T> { let new = count.checked_mul(mem::size_of::<T>()) .expect("capacity overflow"); unsafe { - self.ptr = heap::reallocate(self.ptr as *mut u8, - old, - new, - mem::min_align_of::<T>()) as *mut T; - if self.ptr.is_null() { ::alloc::oom() } + let ptr = heap::reallocate(*self.ptr as *mut u8, + old, + new, + mem::min_align_of::<T>()) as *mut T; + if ptr.is_null() { ::alloc::oom() } + self.ptr = Unique::new(ptr); } } @@ -390,9 +397,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::with_capacity(15); + /// let mut buf = VecDeque::with_capacity(15); /// buf.extend(0..4); /// assert_eq!(buf.capacity(), 15); /// buf.shrink_to_fit(); @@ -453,11 +460,12 @@ impl<T> RingBuf<T> { let old = self.cap * mem::size_of::<T>(); let new_size = target_cap * mem::size_of::<T>(); unsafe { - self.ptr = heap::reallocate(self.ptr as *mut u8, - old, - new_size, - mem::min_align_of::<T>()) as *mut T; - if self.ptr.is_null() { ::alloc::oom() } + let ptr = heap::reallocate(*self.ptr as *mut u8, + old, + new_size, + mem::min_align_of::<T>()) as *mut T; + if ptr.is_null() { ::alloc::oom() } + self.ptr = Unique::new(ptr); } } self.cap = target_cap; @@ -475,9 +483,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// buf.push_back(5); /// buf.push_back(10); /// buf.push_back(15); @@ -498,9 +506,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ```rust - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// buf.push_back(5); /// buf.push_back(3); /// buf.push_back(4); @@ -521,9 +529,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ```rust - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// buf.push_back(5); /// buf.push_back(3); /// buf.push_back(4); @@ -539,8 +547,8 @@ impl<T> RingBuf<T> { tail: self.tail, head: self.head, cap: self.cap, - ptr: self.ptr, - marker: marker::ContravariantLifetime, + ptr: *self.ptr, + marker: marker::PhantomData, } } @@ -553,7 +561,7 @@ impl<T> RingBuf<T> { } /// Returns a pair of slices which contain, in order, the contents of the - /// `RingBuf`. + /// `VecDeque`. #[inline] #[unstable(feature = "collections", reason = "matches collection reform specification, waiting for dust to settle")] @@ -573,7 +581,7 @@ impl<T> RingBuf<T> { } /// Returns a pair of slices which contain, in order, the contents of the - /// `RingBuf`. + /// `VecDeque`. #[inline] #[unstable(feature = "collections", reason = "matches collection reform specification, waiting for dust to settle")] @@ -596,14 +604,14 @@ impl<T> RingBuf<T> { } } - /// Returns the number of elements in the `RingBuf`. + /// Returns the number of elements in the `VecDeque`. /// /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut v = RingBuf::new(); + /// let mut v = VecDeque::new(); /// assert_eq!(v.len(), 0); /// v.push_back(1); /// assert_eq!(v.len(), 1); @@ -616,9 +624,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut v = RingBuf::new(); + /// let mut v = VecDeque::new(); /// assert!(v.is_empty()); /// v.push_front(1); /// assert!(!v.is_empty()); @@ -626,15 +634,15 @@ impl<T> RingBuf<T> { #[stable(feature = "rust1", since = "1.0.0")] pub fn is_empty(&self) -> bool { self.len() == 0 } - /// Creates a draining iterator that clears the `RingBuf` and iterates over + /// Creates a draining iterator that clears the `VecDeque` and iterates over /// the removed items from start to end. /// /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut v = RingBuf::new(); + /// let mut v = VecDeque::new(); /// v.push_back(1); /// assert_eq!(v.drain().next(), Some(1)); /// assert!(v.is_empty()); @@ -653,9 +661,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut v = RingBuf::new(); + /// let mut v = VecDeque::new(); /// v.push_back(1); /// v.clear(); /// assert!(v.is_empty()); @@ -672,9 +680,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut d = RingBuf::new(); + /// let mut d = VecDeque::new(); /// assert_eq!(d.front(), None); /// /// d.push_back(1); @@ -692,9 +700,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut d = RingBuf::new(); + /// let mut d = VecDeque::new(); /// assert_eq!(d.front_mut(), None); /// /// d.push_back(1); @@ -716,9 +724,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut d = RingBuf::new(); + /// let mut d = VecDeque::new(); /// assert_eq!(d.back(), None); /// /// d.push_back(1); @@ -736,9 +744,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut d = RingBuf::new(); + /// let mut d = VecDeque::new(); /// assert_eq!(d.back(), None); /// /// d.push_back(1); @@ -761,9 +769,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut d = RingBuf::new(); + /// let mut d = VecDeque::new(); /// d.push_back(1); /// d.push_back(2); /// @@ -787,9 +795,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut d = RingBuf::new(); + /// let mut d = VecDeque::new(); /// d.push_front(1); /// d.push_front(2); /// assert_eq!(d.front(), Some(&2)); @@ -811,9 +819,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ```rust - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// buf.push_back(1); /// buf.push_back(3); /// assert_eq!(3, *buf.back().unwrap()); @@ -836,9 +844,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ```rust - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// assert_eq!(buf.pop_back(), None); /// buf.push_back(1); /// buf.push_back(3); @@ -870,9 +878,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// assert_eq!(buf.swap_back_remove(0), None); /// buf.push_back(5); /// buf.push_back(99); @@ -903,9 +911,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// assert_eq!(buf.swap_front_remove(0), None); /// buf.push_back(15); /// buf.push_back(5); @@ -936,9 +944,9 @@ impl<T> RingBuf<T> { /// /// # Examples /// ```rust - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// buf.push_back(10); /// buf.push_back(12); /// buf.insert(1,11); @@ -1138,9 +1146,9 @@ impl<T> RingBuf<T> { /// /// # Examples /// ```rust - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// buf.push_back(5); /// buf.push_back(10); /// buf.push_back(12); @@ -1309,9 +1317,9 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf: RingBuf<_> = vec![1,2,3].into_iter().collect(); + /// let mut buf: VecDeque<_> = vec![1,2,3].into_iter().collect(); /// let buf2 = buf.split_off(1); /// // buf = [1], buf2 = [2, 3] /// assert_eq!(buf.len(), 1); @@ -1325,7 +1333,7 @@ impl<T> RingBuf<T> { assert!(at <= len, "`at` out of bounds"); let other_len = len - at; - let mut other = RingBuf::with_capacity(other_len); + let mut other = VecDeque::with_capacity(other_len); unsafe { let (first_half, second_half) = self.as_slices(); @@ -1336,7 +1344,7 @@ impl<T> RingBuf<T> { // `at` lies in the first half. let amount_in_first = first_len - at; - ptr::copy_nonoverlapping_memory(other.ptr, + ptr::copy_nonoverlapping_memory(*other.ptr, first_half.as_ptr().offset(at as isize), amount_in_first); @@ -1349,7 +1357,7 @@ impl<T> RingBuf<T> { // in the first half. let offset = at - first_len; let amount_in_second = second_len - offset; - ptr::copy_nonoverlapping_memory(other.ptr, + ptr::copy_nonoverlapping_memory(*other.ptr, second_half.as_ptr().offset(offset as isize), amount_in_second); } @@ -1371,10 +1379,10 @@ impl<T> RingBuf<T> { /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf: RingBuf<_> = vec![1, 2, 3].into_iter().collect(); - /// let mut buf2: RingBuf<_> = vec![4, 5, 6].into_iter().collect(); + /// let mut buf: VecDeque<_> = vec![1, 2, 3].into_iter().collect(); + /// let mut buf2: VecDeque<_> = vec![4, 5, 6].into_iter().collect(); /// buf.append(&mut buf2); /// assert_eq!(buf.len(), 6); /// assert_eq!(buf2.len(), 0); @@ -1388,16 +1396,16 @@ impl<T> RingBuf<T> { } } -impl<T: Clone> RingBuf<T> { +impl<T: Clone> VecDeque<T> { /// Modifies the ringbuf in-place so that `len()` is equal to new_len, /// either by removing excess elements or by appending copies of a value to the back. /// /// # Examples /// /// ``` - /// use std::collections::RingBuf; + /// use std::collections::VecDeque; /// - /// let mut buf = RingBuf::new(); + /// let mut buf = VecDeque::new(); /// buf.push_back(5); /// buf.push_back(10); /// buf.push_back(15); @@ -1434,7 +1442,7 @@ fn count(tail: usize, head: usize, size: usize) -> usize { (head - tail) & (size - 1) } -/// `RingBuf` iterator. +/// `VecDeque` iterator. #[stable(feature = "rust1", since = "1.0.0")] pub struct Iter<'a, T:'a> { ring: &'a [T], @@ -1511,14 +1519,14 @@ impl<'a, T> RandomAccessIterator for Iter<'a, T> { // FIXME This was implemented differently from Iter because of a problem // with returning the mutable reference. I couldn't find a way to // make the lifetime checker happy so, but there should be a way. -/// `RingBuf` mutable iterator. +/// `VecDeque` mutable iterator. #[stable(feature = "rust1", since = "1.0.0")] pub struct IterMut<'a, T:'a> { ptr: *mut T, tail: usize, head: usize, cap: usize, - marker: marker::ContravariantLifetime<'a>, + marker: marker::PhantomData<&'a mut T>, } #[stable(feature = "rust1", since = "1.0.0")] @@ -1563,10 +1571,10 @@ impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T> ExactSizeIterator for IterMut<'a, T> {} -/// A by-value RingBuf iterator +/// A by-value VecDeque iterator #[stable(feature = "rust1", since = "1.0.0")] pub struct IntoIter<T> { - inner: RingBuf<T>, + inner: VecDeque<T>, } #[stable(feature = "rust1", since = "1.0.0")] @@ -1596,11 +1604,11 @@ impl<T> DoubleEndedIterator for IntoIter<T> { #[stable(feature = "rust1", since = "1.0.0")] impl<T> ExactSizeIterator for IntoIter<T> {} -/// A draining RingBuf iterator +/// A draining VecDeque iterator #[unstable(feature = "collections", reason = "matches collection reform specification, waiting for dust to settle")] pub struct Drain<'a, T: 'a> { - inner: &'a mut RingBuf<T>, + inner: &'a mut VecDeque<T>, } #[unsafe_destructor] @@ -1641,33 +1649,34 @@ impl<'a, T: 'a> DoubleEndedIterator for Drain<'a, T> { impl<'a, T: 'a> ExactSizeIterator for Drain<'a, T> {} #[stable(feature = "rust1", since = "1.0.0")] -impl<A: PartialEq> PartialEq for RingBuf<A> { - fn eq(&self, other: &RingBuf<A>) -> bool { +impl<A: PartialEq> PartialEq for VecDeque<A> { + fn eq(&self, other: &VecDeque<A>) -> bool { self.len() == other.len() && self.iter().zip(other.iter()).all(|(a, b)| a.eq(b)) } } #[stable(feature = "rust1", since = "1.0.0")] -impl<A: Eq> Eq for RingBuf<A> {} +impl<A: Eq> Eq for VecDeque<A> {} #[stable(feature = "rust1", since = "1.0.0")] -impl<A: PartialOrd> PartialOrd for RingBuf<A> { - fn partial_cmp(&self, other: &RingBuf<A>) -> Option<Ordering> { +impl<A: PartialOrd> PartialOrd for VecDeque<A> { + fn partial_cmp(&self, other: &VecDeque<A>) -> Option<Ordering> { iter::order::partial_cmp(self.iter(), other.iter()) } } #[stable(feature = "rust1", since = "1.0.0")] -impl<A: Ord> Ord for RingBuf<A> { +impl<A: Ord> Ord for VecDeque<A> { #[inline] - fn cmp(&self, other: &RingBuf<A>) -> Ordering { + fn cmp(&self, other: &VecDeque<A>) -> Ordering { iter::order::cmp(self.iter(), other.iter()) } } #[stable(feature = "rust1", since = "1.0.0")] -impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for RingBuf<A> { +#[cfg(stage0)] +impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for VecDeque<A> { fn hash(&self, state: &mut S) { self.len().hash(state); for elt in self { @@ -1675,9 +1684,19 @@ impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for RingBuf<A> { } } } +#[stable(feature = "rust1", since = "1.0.0")] +#[cfg(not(stage0))] +impl<A: Hash> Hash for VecDeque<A> { + fn hash<H: Hasher>(&self, state: &mut H) { + self.len().hash(state); + for elt in self { + elt.hash(state); + } + } +} #[stable(feature = "rust1", since = "1.0.0")] -impl<A> Index<usize> for RingBuf<A> { +impl<A> Index<usize> for VecDeque<A> { type Output = A; #[inline] @@ -1687,7 +1706,7 @@ impl<A> Index<usize> for RingBuf<A> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<A> IndexMut<usize> for RingBuf<A> { +impl<A> IndexMut<usize> for VecDeque<A> { #[inline] fn index_mut(&mut self, i: &usize) -> &mut A { self.get_mut(*i).expect("Out of bounds access") @@ -1695,17 +1714,18 @@ impl<A> IndexMut<usize> for RingBuf<A> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<A> FromIterator<A> for RingBuf<A> { - fn from_iter<T: Iterator<Item=A>>(iterator: T) -> RingBuf<A> { +impl<A> FromIterator<A> for VecDeque<A> { + fn from_iter<T: IntoIterator<Item=A>>(iterable: T) -> VecDeque<A> { + let iterator = iterable.into_iter(); let (lower, _) = iterator.size_hint(); - let mut deq = RingBuf::with_capacity(lower); + let mut deq = VecDeque::with_capacity(lower); deq.extend(iterator); deq } } #[stable(feature = "rust1", since = "1.0.0")] -impl<T> IntoIterator for RingBuf<T> { +impl<T> IntoIterator for VecDeque<T> { type Item = T; type IntoIter = IntoIter<T>; @@ -1715,7 +1735,7 @@ impl<T> IntoIterator for RingBuf<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T> IntoIterator for &'a RingBuf<T> { +impl<'a, T> IntoIterator for &'a VecDeque<T> { type Item = &'a T; type IntoIter = Iter<'a, T>; @@ -1725,7 +1745,7 @@ impl<'a, T> IntoIterator for &'a RingBuf<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T> IntoIterator for &'a mut RingBuf<T> { +impl<'a, T> IntoIterator for &'a mut VecDeque<T> { type Item = &'a mut T; type IntoIter = IterMut<'a, T>; @@ -1735,18 +1755,18 @@ impl<'a, T> IntoIterator for &'a mut RingBuf<T> { } #[stable(feature = "rust1", since = "1.0.0")] -impl<A> Extend<A> for RingBuf<A> { - fn extend<T: Iterator<Item=A>>(&mut self, iterator: T) { - for elt in iterator { +impl<A> Extend<A> for VecDeque<A> { + fn extend<T: IntoIterator<Item=A>>(&mut self, iter: T) { + for elt in iter { self.push_back(elt); } } } #[stable(feature = "rust1", since = "1.0.0")] -impl<T: fmt::Debug> fmt::Debug for RingBuf<T> { +impl<T: fmt::Debug> fmt::Debug for VecDeque<T> { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - try!(write!(f, "RingBuf [")); + try!(write!(f, "VecDeque [")); for (i, e) in self.iter().enumerate() { if i != 0 { try!(write!(f, ", ")); } @@ -1768,12 +1788,12 @@ mod tests { use test::Bencher; use test; - use super::RingBuf; + use super::VecDeque; #[test] #[allow(deprecated)] fn test_simple() { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); assert_eq!(d.len(), 0); d.push_front(17); d.push_front(42); @@ -1812,7 +1832,7 @@ mod tests { #[cfg(test)] fn test_parameterized<T:Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) { - let mut deq = RingBuf::new(); + let mut deq = VecDeque::new(); assert_eq!(deq.len(), 0); deq.push_front(a.clone()); deq.push_front(b.clone()); @@ -1843,7 +1863,7 @@ mod tests { #[test] fn test_push_front_grow() { - let mut deq = RingBuf::new(); + let mut deq = VecDeque::new(); for i in 0..66 { deq.push_front(i); } @@ -1853,7 +1873,7 @@ mod tests { assert_eq!(deq[i], 65 - i); } - let mut deq = RingBuf::new(); + let mut deq = VecDeque::new(); for i in 0..66 { deq.push_back(i); } @@ -1865,7 +1885,7 @@ mod tests { #[test] fn test_index() { - let mut deq = RingBuf::new(); + let mut deq = VecDeque::new(); for i in 1..4 { deq.push_front(i); } @@ -1875,7 +1895,7 @@ mod tests { #[test] #[should_fail] fn test_index_out_of_bounds() { - let mut deq = RingBuf::new(); + let mut deq = VecDeque::new(); for i in 1..4 { deq.push_front(i); } @@ -1885,14 +1905,14 @@ mod tests { #[bench] fn bench_new(b: &mut test::Bencher) { b.iter(|| { - let ring: RingBuf<i32> = RingBuf::new(); + let ring: VecDeque<i32> = VecDeque::new(); test::black_box(ring); }) } #[bench] fn bench_push_back_100(b: &mut test::Bencher) { - let mut deq = RingBuf::with_capacity(101); + let mut deq = VecDeque::with_capacity(101); b.iter(|| { for i in 0..100 { deq.push_back(i); @@ -1904,7 +1924,7 @@ mod tests { #[bench] fn bench_push_front_100(b: &mut test::Bencher) { - let mut deq = RingBuf::with_capacity(101); + let mut deq = VecDeque::with_capacity(101); b.iter(|| { for i in 0..100 { deq.push_front(i); @@ -1916,7 +1936,7 @@ mod tests { #[bench] fn bench_pop_back_100(b: &mut test::Bencher) { - let mut deq= RingBuf::<i32>::with_capacity(101); + let mut deq= VecDeque::<i32>::with_capacity(101); b.iter(|| { deq.head = 100; @@ -1929,7 +1949,7 @@ mod tests { #[bench] fn bench_pop_front_100(b: &mut test::Bencher) { - let mut deq = RingBuf::<i32>::with_capacity(101); + let mut deq = VecDeque::<i32>::with_capacity(101); b.iter(|| { deq.head = 100; @@ -1943,7 +1963,7 @@ mod tests { #[bench] fn bench_grow_1025(b: &mut test::Bencher) { b.iter(|| { - let mut deq = RingBuf::new(); + let mut deq = VecDeque::new(); for i in 0..1025 { deq.push_front(i); } @@ -1953,7 +1973,7 @@ mod tests { #[bench] fn bench_iter_1000(b: &mut test::Bencher) { - let ring: RingBuf<_> = (0..1000).collect(); + let ring: VecDeque<_> = (0..1000).collect(); b.iter(|| { let mut sum = 0; @@ -1966,7 +1986,7 @@ mod tests { #[bench] fn bench_mut_iter_1000(b: &mut test::Bencher) { - let mut ring: RingBuf<_> = (0..1000).collect(); + let mut ring: VecDeque<_> = (0..1000).collect(); b.iter(|| { let mut sum = 0; @@ -1986,9 +2006,9 @@ mod tests { #[derive(Clone, PartialEq, Debug)] enum Taggypar<T> { - Onepar(i32), - Twopar(i32, i32), - Threepar(i32, i32, i32), + Onepar(T), + Twopar(T, T), + Threepar(T, T, T), } #[derive(Clone, PartialEq, Debug)] @@ -2027,17 +2047,17 @@ mod tests { #[test] fn test_with_capacity() { - let mut d = RingBuf::with_capacity(0); + let mut d = VecDeque::with_capacity(0); d.push_back(1); assert_eq!(d.len(), 1); - let mut d = RingBuf::with_capacity(50); + let mut d = VecDeque::with_capacity(50); d.push_back(1); assert_eq!(d.len(), 1); } #[test] fn test_with_capacity_non_power_two() { - let mut d3 = RingBuf::with_capacity(3); + let mut d3 = VecDeque::with_capacity(3); d3.push_back(1); // X = None, | = lo @@ -2062,7 +2082,7 @@ mod tests { d3.push_back(15); // There used to be a bug here about how the - // RingBuf made growth assumptions about the + // VecDeque made growth assumptions about the // underlying Vec which didn't hold and lead // to corruption. // (Vec grows to next power of two) @@ -2078,7 +2098,7 @@ mod tests { #[test] fn test_reserve_exact() { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); d.push_back(0); d.reserve_exact(50); assert!(d.capacity() >= 51); @@ -2086,7 +2106,7 @@ mod tests { #[test] fn test_reserve() { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); d.push_back(0); d.reserve(50); assert!(d.capacity() >= 51); @@ -2094,7 +2114,7 @@ mod tests { #[test] fn test_swap() { - let mut d: RingBuf<_> = (0..5).collect(); + let mut d: VecDeque<_> = (0..5).collect(); d.pop_front(); d.swap(0, 3); assert_eq!(d.iter().cloned().collect::<Vec<_>>(), vec!(4, 2, 3, 1)); @@ -2102,7 +2122,7 @@ mod tests { #[test] fn test_iter() { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); assert_eq!(d.iter().next(), None); assert_eq!(d.iter().size_hint(), (0, Some(0))); @@ -2134,7 +2154,7 @@ mod tests { #[test] fn test_rev_iter() { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); assert_eq!(d.iter().rev().next(), None); for i in 0..5 { @@ -2154,7 +2174,7 @@ mod tests { #[test] fn test_mut_rev_iter_wrap() { - let mut d = RingBuf::with_capacity(3); + let mut d = VecDeque::with_capacity(3); assert!(d.iter_mut().rev().next().is_none()); d.push_back(1); @@ -2169,7 +2189,7 @@ mod tests { #[test] fn test_mut_iter() { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); assert!(d.iter_mut().next().is_none()); for i in 0..3 { @@ -2192,7 +2212,7 @@ mod tests { #[test] fn test_mut_rev_iter() { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); assert!(d.iter_mut().rev().next().is_none()); for i in 0..3 { @@ -2218,7 +2238,7 @@ mod tests { // Empty iter { - let d: RingBuf<i32> = RingBuf::new(); + let d: VecDeque<i32> = VecDeque::new(); let mut iter = d.into_iter(); assert_eq!(iter.size_hint(), (0, Some(0))); @@ -2228,7 +2248,7 @@ mod tests { // simple iter { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } @@ -2239,7 +2259,7 @@ mod tests { // wrapped iter { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } @@ -2253,7 +2273,7 @@ mod tests { // partially used { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } @@ -2277,7 +2297,7 @@ mod tests { // Empty iter { - let mut d: RingBuf<i32> = RingBuf::new(); + let mut d: VecDeque<i32> = VecDeque::new(); { let mut iter = d.drain(); @@ -2292,7 +2312,7 @@ mod tests { // simple iter { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } @@ -2303,7 +2323,7 @@ mod tests { // wrapped iter { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } @@ -2317,7 +2337,7 @@ mod tests { // partially used { - let mut d: RingBuf<_> = RingBuf::new(); + let mut d: VecDeque<_> = VecDeque::new(); for i in 0..5 { d.push_back(i); } @@ -2343,12 +2363,12 @@ mod tests { fn test_from_iter() { use core::iter; let v = vec!(1,2,3,4,5,6,7); - let deq: RingBuf<_> = v.iter().cloned().collect(); + let deq: VecDeque<_> = v.iter().cloned().collect(); let u: Vec<_> = deq.iter().cloned().collect(); assert_eq!(u, v); let seq = iter::count(0, 2).take(256); - let deq: RingBuf<_> = seq.collect(); + let deq: VecDeque<_> = seq.collect(); for (i, &x) in deq.iter().enumerate() { assert_eq!(2*i, x); } @@ -2357,7 +2377,7 @@ mod tests { #[test] fn test_clone() { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); d.push_front(17); d.push_front(42); d.push_back(137); @@ -2374,13 +2394,13 @@ mod tests { #[test] fn test_eq() { - let mut d = RingBuf::new(); - assert!(d == RingBuf::with_capacity(0)); + let mut d = VecDeque::new(); + assert!(d == VecDeque::with_capacity(0)); d.push_front(137); d.push_front(17); d.push_front(42); d.push_back(137); - let mut e = RingBuf::with_capacity(0); + let mut e = VecDeque::with_capacity(0); e.push_back(42); e.push_back(17); e.push_back(137); @@ -2390,13 +2410,13 @@ mod tests { e.push_back(0); assert!(e != d); e.clear(); - assert!(e == RingBuf::new()); + assert!(e == VecDeque::new()); } #[test] fn test_hash() { - let mut x = RingBuf::new(); - let mut y = RingBuf::new(); + let mut x = VecDeque::new(); + let mut y = VecDeque::new(); x.push_back(1); x.push_back(2); @@ -2413,8 +2433,8 @@ mod tests { #[test] fn test_ord() { - let x = RingBuf::new(); - let mut y = RingBuf::new(); + let x = VecDeque::new(); + let mut y = VecDeque::new(); y.push_back(1); y.push_back(2); y.push_back(3); @@ -2426,13 +2446,13 @@ mod tests { #[test] fn test_show() { - let ringbuf: RingBuf<_> = (0..10).collect(); - assert_eq!(format!("{:?}", ringbuf), "RingBuf [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); + let ringbuf: VecDeque<_> = (0..10).collect(); + assert_eq!(format!("{:?}", ringbuf), "VecDeque [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); - let ringbuf: RingBuf<_> = vec!["just", "one", "test", "more"].iter() + let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"].iter() .cloned() .collect(); - assert_eq!(format!("{:?}", ringbuf), "RingBuf [\"just\", \"one\", \"test\", \"more\"]"); + assert_eq!(format!("{:?}", ringbuf), "VecDeque [\"just\", \"one\", \"test\", \"more\"]"); } #[test] @@ -2445,7 +2465,7 @@ mod tests { } } - let mut ring = RingBuf::new(); + let mut ring = VecDeque::new(); ring.push_back(Elem); ring.push_front(Elem); ring.push_back(Elem); @@ -2465,7 +2485,7 @@ mod tests { } } - let mut ring = RingBuf::new(); + let mut ring = VecDeque::new(); ring.push_back(Elem); ring.push_front(Elem); ring.push_back(Elem); @@ -2489,7 +2509,7 @@ mod tests { } } - let mut ring = RingBuf::new(); + let mut ring = VecDeque::new(); ring.push_back(Elem); ring.push_front(Elem); ring.push_back(Elem); @@ -2505,7 +2525,7 @@ mod tests { fn test_reserve_grow() { // test growth path A // [T o o H] -> [T o o H . . . . ] - let mut ring = RingBuf::with_capacity(4); + let mut ring = VecDeque::with_capacity(4); for i in 0..3 { ring.push_back(i); } @@ -2516,7 +2536,7 @@ mod tests { // test growth path B // [H T o o] -> [. T o o H . . . ] - let mut ring = RingBuf::with_capacity(4); + let mut ring = VecDeque::with_capacity(4); for i in 0..1 { ring.push_back(i); assert_eq!(ring.pop_front(), Some(i)); @@ -2531,7 +2551,7 @@ mod tests { // test growth path C // [o o H T] -> [o o H . . . . T ] - let mut ring = RingBuf::with_capacity(4); + let mut ring = VecDeque::with_capacity(4); for i in 0..3 { ring.push_back(i); assert_eq!(ring.pop_front(), Some(i)); @@ -2547,7 +2567,7 @@ mod tests { #[test] fn test_get() { - let mut ring = RingBuf::new(); + let mut ring = VecDeque::new(); ring.push_back(0); assert_eq!(ring.get(0), Some(&0)); assert_eq!(ring.get(1), None); @@ -2579,7 +2599,7 @@ mod tests { #[test] fn test_get_mut() { - let mut ring = RingBuf::new(); + let mut ring = VecDeque::new(); for i in 0..3 { ring.push_back(i); } @@ -2605,7 +2625,7 @@ mod tests { fn test(back: bool) { // This test checks that every single combination of tail position and length is tested. // Capacity 15 should be large enough to cover every case. - let mut tester = RingBuf::with_capacity(15); + let mut tester = VecDeque::with_capacity(15); let usable_cap = tester.capacity(); let final_len = usable_cap / 2; @@ -2649,7 +2669,7 @@ mod tests { // This test checks that every single combination of tail position, length, and // insertion position is tested. Capacity 15 should be large enough to cover every case. - let mut tester = RingBuf::with_capacity(15); + let mut tester = VecDeque::with_capacity(15); // can't guarantee we got 15, so have to get what we got. // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else // this test isn't covering what it wants to @@ -2683,7 +2703,7 @@ mod tests { // This test checks that every single combination of tail position, length, and // removal position is tested. Capacity 15 should be large enough to cover every case. - let mut tester = RingBuf::with_capacity(15); + let mut tester = VecDeque::with_capacity(15); // can't guarantee we got 15, so have to get what we got. // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else // this test isn't covering what it wants to @@ -2720,7 +2740,7 @@ mod tests { // This test checks that every single combination of head and tail position, // is tested. Capacity 15 should be large enough to cover every case. - let mut tester = RingBuf::with_capacity(15); + let mut tester = VecDeque::with_capacity(15); // can't guarantee we got 15, so have to get what we got. // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else // this test isn't covering what it wants to @@ -2749,7 +2769,7 @@ mod tests { #[test] fn test_front() { - let mut ring = RingBuf::new(); + let mut ring = VecDeque::new(); ring.push_back(10); ring.push_back(20); assert_eq!(ring.front(), Some(&10)); @@ -2761,7 +2781,7 @@ mod tests { #[test] fn test_as_slices() { - let mut ring: RingBuf<i32> = RingBuf::with_capacity(127); + let mut ring: VecDeque<i32> = VecDeque::with_capacity(127); let cap = ring.capacity() as i32; let first = cap/2; let last = cap - first; @@ -2789,7 +2809,7 @@ mod tests { #[test] fn test_as_mut_slices() { - let mut ring: RingBuf<i32> = RingBuf::with_capacity(127); + let mut ring: VecDeque<i32> = VecDeque::with_capacity(127); let cap = ring.capacity() as i32; let first = cap/2; let last = cap - first; @@ -2820,7 +2840,7 @@ mod tests { // This test checks that every single combination of tail position, length, and // split position is tested. Capacity 15 should be large enough to cover every case. - let mut tester = RingBuf::with_capacity(15); + let mut tester = VecDeque::with_capacity(15); // can't guarantee we got 15, so have to get what we got. // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else // this test isn't covering what it wants to @@ -2855,8 +2875,8 @@ mod tests { #[test] fn test_append() { - let mut a: RingBuf<_> = vec![1, 2, 3].into_iter().collect(); - let mut b: RingBuf<_> = vec![4, 5, 6].into_iter().collect(); + let mut a: VecDeque<_> = vec![1, 2, 3].into_iter().collect(); + let mut b: VecDeque<_> = vec![4, 5, 6].into_iter().collect(); // normal append a.append(&mut b); diff --git a/src/libcollections/vec_map.rs b/src/libcollections/vec_map.rs index 82ccfd0614f..54589a31423 100644 --- a/src/libcollections/vec_map.rs +++ b/src/libcollections/vec_map.rs @@ -20,7 +20,8 @@ use core::prelude::*; use core::cmp::Ordering; use core::default::Default; use core::fmt; -use core::hash::{Hash, Writer, Hasher}; +use core::hash::{Hash, Hasher}; +#[cfg(stage0)] use core::hash::Writer; use core::iter::{Enumerate, FilterMap, Map, FromIterator, IntoIterator}; use core::iter; use core::mem::replace; @@ -99,6 +100,7 @@ impl<V> Default for VecMap<V> { fn default() -> VecMap<V> { VecMap::new() } } +#[stable(feature = "rust1", since = "1.0.0")] impl<V:Clone> Clone for VecMap<V> { #[inline] fn clone(&self) -> VecMap<V> { @@ -111,6 +113,7 @@ impl<V:Clone> Clone for VecMap<V> { } } +#[cfg(stage0)] impl<S: Writer + Hasher, V: Hash<S>> Hash<S> for VecMap<V> { fn hash(&self, state: &mut S) { // In order to not traverse the `VecMap` twice, count the elements @@ -123,6 +126,20 @@ impl<S: Writer + Hasher, V: Hash<S>> Hash<S> for VecMap<V> { count.hash(state); } } +#[stable(feature = "rust1", since = "1.0.0")] +#[cfg(not(stage0))] +impl<V: Hash> Hash for VecMap<V> { + fn hash<H: Hasher>(&self, state: &mut H) { + // In order to not traverse the `VecMap` twice, count the elements + // during iteration. + let mut count: usize = 0; + for elt in self { + elt.hash(state); + count += 1; + } + count.hash(state); + } +} impl<V> VecMap<V> { /// Creates an empty `VecMap`. @@ -661,7 +678,7 @@ impl<V: fmt::Debug> fmt::Debug for VecMap<V> { #[stable(feature = "rust1", since = "1.0.0")] impl<V> FromIterator<(usize, V)> for VecMap<V> { - fn from_iter<Iter: Iterator<Item=(usize, V)>>(iter: Iter) -> VecMap<V> { + fn from_iter<I: IntoIterator<Item=(usize, V)>>(iter: I) -> VecMap<V> { let mut map = VecMap::new(); map.extend(iter); map @@ -700,7 +717,7 @@ impl<'a, T> IntoIterator for &'a mut VecMap<T> { #[stable(feature = "rust1", since = "1.0.0")] impl<V> Extend<(usize, V)> for VecMap<V> { - fn extend<Iter: Iterator<Item=(usize, V)>>(&mut self, iter: Iter) { + fn extend<I: IntoIterator<Item=(usize, V)>>(&mut self, iter: I) { for (k, v) in iter { self.insert(k, v); } @@ -859,7 +876,7 @@ pub struct IntoIter<V> { } #[unstable(feature = "collections")] -pub struct Drain<'a, V> { +pub struct Drain<'a, V:'a> { iter: FilterMap< Enumerate<vec::Drain<'a, Option<V>>>, fn((usize, Option<V>)) -> Option<(usize, V)>> |