diff options
| author | Alex Crichton <alex@alexcrichton.com> | 2015-02-18 14:34:08 -0800 |
|---|---|---|
| committer | Alex Crichton <alex@alexcrichton.com> | 2015-02-18 14:34:08 -0800 |
| commit | 5a32b4a34fc6fbd78e293b16f7ba7d06caca7a48 (patch) | |
| tree | ea0ee2df4161fb0578705cd5f26635db5f3b4a1e | |
| parent | 9aee389b6e5a58eb867f4d035729f39e694f51ec (diff) | |
| parent | 66613e26b95438c02e2f5c273c557515454121f7 (diff) | |
| download | rust-5a32b4a34fc6fbd78e293b16f7ba7d06caca7a48.tar.gz rust-5a32b4a34fc6fbd78e293b16f7ba7d06caca7a48.zip | |
rollup merge of #22491: Gankro/into_iter
Conflicts: src/libcollections/bit.rs src/libcollections/linked_list.rs src/libcollections/vec_deque.rs src/libstd/sys/common/wtf8.rs
28 files changed, 990 insertions, 938 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 6c152f366fd..d9c2290e68c 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 { +impl FromIterator<bool> for BitVec { + fn from_iter<I: IntoIterator<Item=bool>>(iter: I) -> BitVec { let mut ret = Bitv::new(); - ret.extend(iterator); + 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 })); @@ -985,7 +986,7 @@ impl fmt::Debug for Bitv { #[stable(feature = "rust1", since = "1.0.0")] #[cfg(stage0)] -impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for Bitv { +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() { @@ -995,7 +996,7 @@ 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 Bitv { +impl hash::Hash for BitVec { fn hash<H: hash::Hasher>(&self, state: &mut H) { self.nbits.hash(state); for elem in self.blocks() { @@ -1005,9 +1006,9 @@ impl hash::Hash for Bitv { } #[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; } @@ -1016,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, } @@ -1036,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 } @@ -1054,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 } @@ -1076,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>; @@ -1101,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); @@ -1115,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); /// @@ -1125,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 { +impl FromIterator<usize> for BitSet { + fn from_iter<I: IntoIterator<Item=usize>>(iter: I) -> BitSet { let mut ret = BitvSet::new(); - ret.extend(iterator); + 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() { @@ -1241,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 @@ -1251,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. @@ -1272,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 @@ -1298,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); } } @@ -1318,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. @@ -1338,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; } } @@ -1384,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); /// @@ -1400,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() { @@ -1427,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} } @@ -1437,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) { @@ -1449,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 { @@ -1467,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) { @@ -1479,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, @@ -1497,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) { @@ -1516,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 { @@ -1535,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) { @@ -1547,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 { @@ -1564,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); } @@ -1587,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); } @@ -1611,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); } @@ -1643,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); } @@ -1665,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) } @@ -1728,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; } @@ -1745,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 { @@ -1768,7 +1777,7 @@ impl fmt::Debug for BitvSet { } #[cfg(stage0)] -impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for BitvSet { +impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for BitSet { fn hash(&self, state: &mut S) { for pos in self { pos.hash(state); @@ -1777,7 +1786,7 @@ impl<S: hash::Writer + hash::Hasher> hash::Hash<S> for BitvSet { } #[stable(feature = "rust1", since = "1.0.0")] #[cfg(not(stage0))] -impl hash::Hash for BitvSet { +impl hash::Hash for BitSet { fn hash<H: hash::Hasher>(&self, state: &mut H) { for pos in self { pos.hash(state); @@ -1785,19 +1794,19 @@ impl hash::Hash for BitvSet { } } -/// 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 @@ -1817,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; @@ -1831,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)) } } @@ -1840,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); } @@ -1868,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)) } } @@ -1906,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>; @@ -1920,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()); @@ -1941,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"); @@ -1963,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); @@ -1984,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); @@ -1994,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); @@ -2008,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, @@ -2016,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, @@ -2024,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); @@ -2040,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); @@ -2056,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); @@ -2071,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); @@ -2087,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, @@ -2095,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, @@ -2103,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); @@ -2119,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); @@ -2135,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); @@ -2151,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); @@ -2168,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, @@ -2176,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, @@ -2184,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); @@ -2200,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); @@ -2216,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); @@ -2232,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); @@ -2247,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); @@ -2272,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); } @@ -2287,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)); @@ -2307,32 +2316,32 @@ mod tests { #[test] fn test_from_bools() { let bools = vec![true, false, true, true]; - let bitv: Bitv = bools.iter().cloned().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().cloned().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().cloned().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); @@ -2345,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); @@ -2359,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()); @@ -2367,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); @@ -2391,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); @@ -2406,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]); @@ -2433,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]); @@ -2441,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]); @@ -2451,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); @@ -2474,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); @@ -2519,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])); } } @@ -2546,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; @@ -2565,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; } } @@ -2634,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 @@ -2653,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); @@ -2681,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(); @@ -2696,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)); @@ -2710,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)); @@ -2723,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)); @@ -2738,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)); @@ -2761,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)); @@ -2780,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)); @@ -2801,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)); @@ -2826,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); @@ -2852,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)); @@ -2870,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); @@ -2891,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); @@ -2902,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); @@ -2911,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); @@ -2921,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); @@ -2945,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); @@ -2974,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); @@ -2988,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); @@ -3002,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)); @@ -3017,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)); @@ -3041,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; @@ -3058,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/btree/map.rs b/src/libcollections/btree/map.rs index 73d2af28a04..a985a24f7ae 100644 --- a/src/libcollections/btree/map.rs +++ b/src/libcollections/btree/map.rs @@ -29,7 +29,7 @@ use core::ops::{Index, IndexMut}; use core::{iter, fmt, mem}; use Bound::{self, Included, Excluded, Unbounded}; -use ring_buf::RingBuf; +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, } @@ -826,7 +826,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,7 +836,7 @@ 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); } @@ -1199,7 +1199,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 { @@ -1231,7 +1231,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 { @@ -1260,7 +1260,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 { @@ -1352,7 +1352,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/set.rs b/src/libcollections/btree/set.rs index 7ef887b70cc..61497186623 100644 --- a/src/libcollections/btree/set.rs +++ b/src/libcollections/btree/set.rs @@ -473,7 +473,7 @@ impl<T: Ord> BTreeSet<T> { #[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..140c9edb5a3 100644 --- a/src/libcollections/enum_set.rs +++ b/src/libcollections/enum_set.rs @@ -250,9 +250,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 +268,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 06f7e825a14..335b15c4340 100644 --- a/src/libcollections/lib.rs +++ b/src/libcollections/lib.rs @@ -48,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; @@ -70,10 +86,10 @@ 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; @@ -82,15 +98,23 @@ pub mod vec_map; #[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")] diff --git a/src/libcollections/dlist.rs b/src/libcollections/linked_list.rs index 3734bfad28f..1c4b34b4650 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")] @@ -34,9 +34,13 @@ 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>>, @@ -58,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>, @@ -78,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 @@ -149,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>>) { @@ -209,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. @@ -233,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); @@ -249,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; @@ -303,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"); @@ -324,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); @@ -351,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); @@ -375,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 @@ -384,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); @@ -405,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); @@ -432,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); @@ -453,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); @@ -481,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); @@ -505,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); @@ -528,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()); @@ -546,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); @@ -571,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); @@ -585,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, @@ -614,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 @@ -630,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; @@ -763,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(); @@ -790,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); @@ -831,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>; @@ -850,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>; @@ -859,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>; @@ -869,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> { +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, ", ")); } @@ -929,7 +933,7 @@ impl<A: fmt::Debug> fmt::Debug for DList<A> { #[stable(feature = "rust1", since = "1.0.0")] #[cfg(stage0)] -impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for DList<A> { +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 { @@ -939,7 +943,7 @@ 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 DList<A> { +impl<A: Hash> Hash for LinkedList<A> { fn hash<H: Hasher>(&self, state: &mut H) { self.len().hash(state); for elt in self { @@ -957,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>; @@ -993,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); @@ -1012,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); { @@ -1032,7 +1036,7 @@ mod tests { } #[cfg(test)] - fn generate_test() -> DList<i32> { + fn generate_test() -> LinkedList<i32> { list_from(&[0,1,2,3,4,5,6]) } @@ -1045,8 +1049,8 @@ mod tests { 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); @@ -1054,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); @@ -1066,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); @@ -1102,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); @@ -1143,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); @@ -1161,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(); @@ -1173,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); @@ -1187,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); @@ -1209,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(); @@ -1228,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); @@ -1242,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); @@ -1291,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(); @@ -1326,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)); @@ -1395,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); @@ -1445,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); }) @@ -1459,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); }) @@ -1467,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(); @@ -1476,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(); @@ -1486,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); }) @@ -1494,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); }) @@ -1502,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); }) @@ -1510,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/str.rs b/src/libcollections/str.rs index 2d4dc2bcf30..94d81c74cd3 100644 --- a/src/libcollections/str.rs +++ b/src/libcollections/str.rs @@ -68,7 +68,7 @@ use core::slice::AsSlice; use core::str as core_str; use unicode::str::{UnicodeStr, Utf16Encoder}; -use ring_buf::RingBuf; +use vec_deque::VecDeque; 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> } @@ -496,7 +496,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 +511,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 } diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs index 6204c4427b5..db889725abd 100644 --- a/src/libcollections/string.rs +++ b/src/libcollections/string.rs @@ -21,7 +21,7 @@ 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; @@ -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); diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs index 203a3381c79..c77a6b9e8e5 100644 --- a/src/libcollections/vec.rs +++ b/src/libcollections/vec.rs @@ -1417,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); @@ -1490,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 { @@ -1664,7 +1666,7 @@ pub type CowVec<'a, T> = Cow<'a, Vec<T>, [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> { + fn from_iter<I: IntoIterator<Item=T>>(it: I) -> CowVec<'a, T> { Cow::Owned(FromIterator::from_iter(it)) } } diff --git a/src/libcollections/ring_buf.rs b/src/libcollections/vec_deque.rs index c241b096b39..712695841a2 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 @@ -37,12 +37,17 @@ 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. @@ -56,21 +61,21 @@ pub struct RingBuf<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 { @@ -84,12 +89,12 @@ 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] { @@ -150,16 +155,16 @@ 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"); @@ -176,7 +181,7 @@ impl<T> RingBuf<T> { heap::EMPTY as *mut T }; - RingBuf { + VecDeque { tail: 0, head: 0, cap: cap, @@ -184,14 +189,14 @@ impl<T> RingBuf<T> { } } - /// 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); @@ -207,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); @@ -246,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); @@ -267,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] @@ -283,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 @@ -296,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); /// ``` @@ -317,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); /// ``` @@ -391,9 +396,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(); @@ -476,9 +481,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); @@ -499,9 +504,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); @@ -522,9 +527,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); @@ -554,7 +559,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")] @@ -574,7 +579,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")] @@ -597,14 +602,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); @@ -617,9 +622,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()); @@ -627,15 +632,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()); @@ -654,9 +659,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()); @@ -673,9 +678,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); @@ -693,9 +698,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); @@ -717,9 +722,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); @@ -737,9 +742,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); @@ -762,9 +767,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); /// @@ -788,9 +793,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)); @@ -812,9 +817,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()); @@ -837,9 +842,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); @@ -871,9 +876,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); @@ -904,9 +909,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); @@ -937,9 +942,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); @@ -1139,9 +1144,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); @@ -1310,9 +1315,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); @@ -1326,7 +1331,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(); @@ -1372,10 +1377,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); @@ -1389,16 +1394,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); @@ -1435,7 +1440,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], @@ -1512,7 +1517,7 @@ 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, @@ -1564,10 +1569,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")] @@ -1597,11 +1602,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] @@ -1642,34 +1647,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")] #[cfg(stage0)] -impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for RingBuf<A> { +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 { @@ -1679,7 +1684,7 @@ 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 RingBuf<A> { +impl<A: Hash> Hash for VecDeque<A> { fn hash<H: Hasher>(&self, state: &mut H) { self.len().hash(state); for elt in self { @@ -1689,7 +1694,7 @@ impl<A: Hash> Hash for RingBuf<A> { } #[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] @@ -1699,7 +1704,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") @@ -1707,17 +1712,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>; @@ -1727,7 +1733,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>; @@ -1737,7 +1743,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>; @@ -1747,18 +1753,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, ", ")); } @@ -1780,12 +1786,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); @@ -1824,7 +1830,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()); @@ -1855,7 +1861,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); } @@ -1865,7 +1871,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); } @@ -1877,7 +1883,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); } @@ -1887,7 +1893,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); } @@ -1897,14 +1903,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); @@ -1916,7 +1922,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); @@ -1928,7 +1934,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; @@ -1941,7 +1947,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; @@ -1955,7 +1961,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); } @@ -1965,7 +1971,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; @@ -1978,7 +1984,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; @@ -2039,17 +2045,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 @@ -2074,7 +2080,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) @@ -2090,7 +2096,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); @@ -2098,7 +2104,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); @@ -2106,7 +2112,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)); @@ -2114,7 +2120,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))); @@ -2146,7 +2152,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 { @@ -2166,7 +2172,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); @@ -2181,7 +2187,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 { @@ -2204,7 +2210,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 { @@ -2230,7 +2236,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))); @@ -2240,7 +2246,7 @@ mod tests { // simple iter { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } @@ -2251,7 +2257,7 @@ mod tests { // wrapped iter { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } @@ -2265,7 +2271,7 @@ mod tests { // partially used { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } @@ -2289,7 +2295,7 @@ mod tests { // Empty iter { - let mut d: RingBuf<i32> = RingBuf::new(); + let mut d: VecDeque<i32> = VecDeque::new(); { let mut iter = d.drain(); @@ -2304,7 +2310,7 @@ mod tests { // simple iter { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } @@ -2315,7 +2321,7 @@ mod tests { // wrapped iter { - let mut d = RingBuf::new(); + let mut d = VecDeque::new(); for i in 0..5 { d.push_back(i); } @@ -2329,7 +2335,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); } @@ -2355,12 +2361,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); } @@ -2369,7 +2375,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); @@ -2386,13 +2392,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); @@ -2402,13 +2408,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); @@ -2425,8 +2431,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); @@ -2438,13 +2444,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] @@ -2457,7 +2463,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); @@ -2477,7 +2483,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); @@ -2501,7 +2507,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); @@ -2517,7 +2523,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); } @@ -2528,7 +2534,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)); @@ -2543,7 +2549,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)); @@ -2559,7 +2565,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); @@ -2591,7 +2597,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); } @@ -2617,7 +2623,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; @@ -2661,7 +2667,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 @@ -2695,7 +2701,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 @@ -2732,7 +2738,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 @@ -2761,7 +2767,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)); @@ -2773,7 +2779,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; @@ -2801,7 +2807,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; @@ -2832,7 +2838,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 @@ -2867,8 +2873,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 c271cb052ab..9f0489a4f96 100644 --- a/src/libcollections/vec_map.rs +++ b/src/libcollections/vec_map.rs @@ -678,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 @@ -717,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); } diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs index 8e5396f2229..7a6c3a00772 100644 --- a/src/libcore/iter.rs +++ b/src/libcore/iter.rs @@ -113,9 +113,9 @@ impl<'a, I: Iterator + ?Sized> Iterator for &'a mut I { #[rustc_on_unimplemented="a collection of type `{Self}` cannot be \ built from an iterator over elements of type `{A}`"] pub trait FromIterator<A> { - /// Build a container with elements from an external iterator. + /// Build a container with elements from something iterable. #[stable(feature = "rust1", since = "1.0.0")] - fn from_iter<T: Iterator<Item=A>>(iterator: T) -> Self; + fn from_iter<T: IntoIterator<Item=A>>(iterator: T) -> Self; } /// Conversion into an `Iterator` @@ -147,7 +147,7 @@ impl<I: Iterator> IntoIterator for I { pub trait Extend<A> { /// Extend a container with the elements yielded by an arbitrary iterator #[stable(feature = "rust1", since = "1.0.0")] - fn extend<T: Iterator<Item=A>>(&mut self, iterator: T); + fn extend<T: IntoIterator<Item=A>>(&mut self, iterable: T); } /// An extension trait providing numerous methods applicable to all iterators. diff --git a/src/libcore/option.rs b/src/libcore/option.rs index 9a89682127f..abfef72a5db 100644 --- a/src/libcore/option.rs +++ b/src/libcore/option.rs @@ -149,7 +149,7 @@ use clone::Clone; use cmp::{Eq, Ord}; use default::Default; use iter::{ExactSizeIterator}; -use iter::{Iterator, IteratorExt, DoubleEndedIterator, FromIterator}; +use iter::{Iterator, IteratorExt, DoubleEndedIterator, FromIterator, IntoIterator}; use mem; use ops::{Deref, FnOnce}; use result::Result::{Ok, Err}; @@ -909,7 +909,7 @@ impl<A, V: FromIterator<A>> FromIterator<Option<A>> for Option<V> { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - fn from_iter<I: Iterator<Item=Option<A>>>(iter: I) -> Option<V> { + fn from_iter<I: IntoIterator<Item=Option<A>>>(iter: I) -> Option<V> { // FIXME(#11084): This could be replaced with Iterator::scan when this // performance bug is closed. @@ -934,7 +934,7 @@ impl<A, V: FromIterator<A>> FromIterator<Option<A>> for Option<V> { } } - let mut adapter = Adapter { iter: iter, found_none: false }; + let mut adapter = Adapter { iter: iter.into_iter(), found_none: false }; let v: V = FromIterator::from_iter(adapter.by_ref()); if adapter.found_none { diff --git a/src/libcore/result.rs b/src/libcore/result.rs index 1a874ee178b..23e936a75d7 100644 --- a/src/libcore/result.rs +++ b/src/libcore/result.rs @@ -230,7 +230,8 @@ use self::Result::{Ok, Err}; use clone::Clone; use fmt; -use iter::{Iterator, IteratorExt, DoubleEndedIterator, FromIterator, ExactSizeIterator}; +use iter::{Iterator, IteratorExt, DoubleEndedIterator, + FromIterator, ExactSizeIterator, IntoIterator}; use ops::{FnMut, FnOnce}; use option::Option::{self, None, Some}; use slice::AsSlice; @@ -906,7 +907,7 @@ impl<A, E, V: FromIterator<A>> FromIterator<Result<A, E>> for Result<V, E> { /// assert!(res == Ok(vec!(2, 3))); /// ``` #[inline] - fn from_iter<I: Iterator<Item=Result<A, E>>>(iter: I) -> Result<V, E> { + fn from_iter<I: IntoIterator<Item=Result<A, E>>>(iter: I) -> Result<V, E> { // FIXME(#11084): This could be replaced with Iterator::scan when this // performance bug is closed. @@ -931,7 +932,7 @@ impl<A, E, V: FromIterator<A>> FromIterator<Result<A, E>> for Result<V, E> { } } - let mut adapter = Adapter { iter: iter, err: None }; + let mut adapter = Adapter { iter: iter.into_iter(), err: None }; let v: V = FromIterator::from_iter(adapter.by_ref()); match adapter.err { diff --git a/src/librustc/lint/builtin.rs b/src/librustc/lint/builtin.rs index ba108b5488e..582cd4f384f 100644 --- a/src/librustc/lint/builtin.rs +++ b/src/librustc/lint/builtin.rs @@ -37,7 +37,7 @@ use util::ppaux::{ty_to_string}; use util::nodemap::{FnvHashMap, NodeSet}; use lint::{Level, Context, LintPass, LintArray, Lint}; -use std::collections::BitvSet; +use std::collections::BitSet; use std::collections::hash_map::Entry::{Occupied, Vacant}; use std::num::SignedInt; use std::{cmp, slice}; @@ -1792,7 +1792,7 @@ impl LintPass for UnconditionalRecursion { let mut work_queue = vec![cfg.entry]; let mut reached_exit_without_self_call = false; let mut self_call_spans = vec![]; - let mut visited = BitvSet::new(); + let mut visited = BitSet::new(); while let Some(idx) = work_queue.pop() { let cfg_id = idx.node_id(); diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs index 4544f283e1c..6f515450a12 100644 --- a/src/librustc/middle/check_match.rs +++ b/src/librustc/middle/check_match.rs @@ -25,7 +25,7 @@ use middle::ty::*; use middle::ty; use std::cmp::Ordering; use std::fmt; -use std::iter::{range_inclusive, AdditiveIterator, FromIterator, repeat}; +use std::iter::{range_inclusive, AdditiveIterator, FromIterator, IntoIterator, repeat}; use std::num::Float; use std::slice; use syntax::ast::{self, DUMMY_NODE_ID, NodeId, Pat}; @@ -94,8 +94,8 @@ impl<'a> fmt::Debug for Matrix<'a> { } impl<'a> FromIterator<Vec<&'a Pat>> for Matrix<'a> { - fn from_iter<T: Iterator<Item=Vec<&'a Pat>>>(iterator: T) -> Matrix<'a> { - Matrix(iterator.collect()) + fn from_iter<T: IntoIterator<Item=Vec<&'a Pat>>>(iter: T) -> Matrix<'a> { + Matrix(iter.into_iter().collect()) } } diff --git a/src/librustc/middle/graph.rs b/src/librustc/middle/graph.rs index 4dd7a4a2266..436f04fc9e9 100644 --- a/src/librustc/middle/graph.rs +++ b/src/librustc/middle/graph.rs @@ -34,7 +34,7 @@ use std::fmt::{Formatter, Error, Debug}; use std::usize; -use std::collections::BitvSet; +use std::collections::BitSet; pub struct Graph<N,E> { nodes: Vec<Node<N>> , @@ -292,7 +292,7 @@ impl<N,E> Graph<N,E> { DepthFirstTraversal { graph: self, stack: vec![start], - visited: BitvSet::new() + visited: BitSet::new() } } } @@ -300,7 +300,7 @@ impl<N,E> Graph<N,E> { pub struct DepthFirstTraversal<'g, N:'g, E:'g> { graph: &'g Graph<N, E>, stack: Vec<NodeIndex>, - visited: BitvSet + visited: BitSet } impl<'g, N, E> Iterator for DepthFirstTraversal<'g, N, E> { diff --git a/src/libserialize/collection_impls.rs b/src/libserialize/collection_impls.rs index 7176ad7f88d..10cf02f85e8 100644 --- a/src/libserialize/collection_impls.rs +++ b/src/libserialize/collection_impls.rs @@ -17,12 +17,12 @@ use std::hash::Hash; use std::collections::hash_state::HashState; use {Decodable, Encodable, Decoder, Encoder}; -use std::collections::{DList, RingBuf, BTreeMap, BTreeSet, HashMap, HashSet, VecMap}; +use std::collections::{LinkedList, VecDeque, BTreeMap, BTreeSet, HashMap, HashSet, VecMap}; use collections::enum_set::{EnumSet, CLike}; impl< T: Encodable -> Encodable for DList<T> { +> Encodable for LinkedList<T> { fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> { s.emit_seq(self.len(), |s| { for (i, e) in self.iter().enumerate() { @@ -33,10 +33,10 @@ impl< } } -impl<T:Decodable> Decodable for DList<T> { - fn decode<D: Decoder>(d: &mut D) -> Result<DList<T>, D::Error> { +impl<T:Decodable> Decodable for LinkedList<T> { + fn decode<D: Decoder>(d: &mut D) -> Result<LinkedList<T>, D::Error> { d.read_seq(|d, len| { - let mut list = DList::new(); + let mut list = LinkedList::new(); for i in 0..len { list.push_back(try!(d.read_seq_elt(i, |d| Decodable::decode(d)))); } @@ -45,7 +45,7 @@ impl<T:Decodable> Decodable for DList<T> { } } -impl<T: Encodable> Encodable for RingBuf<T> { +impl<T: Encodable> Encodable for VecDeque<T> { fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> { s.emit_seq(self.len(), |s| { for (i, e) in self.iter().enumerate() { @@ -56,10 +56,10 @@ impl<T: Encodable> Encodable for RingBuf<T> { } } -impl<T:Decodable> Decodable for RingBuf<T> { - fn decode<D: Decoder>(d: &mut D) -> Result<RingBuf<T>, D::Error> { +impl<T:Decodable> Decodable for VecDeque<T> { + fn decode<D: Decoder>(d: &mut D) -> Result<VecDeque<T>, D::Error> { d.read_seq(|d, len| { - let mut deque: RingBuf<T> = RingBuf::new(); + let mut deque: VecDeque<T> = VecDeque::new(); for i in 0..len { deque.push_back(try!(d.read_seq_elt(i, |d| Decodable::decode(d)))); } diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs index f04bbbb1f4d..04f8bb0b0db 100644 --- a/src/libstd/collections/hash/map.rs +++ b/src/libstd/collections/hash/map.rs @@ -1534,7 +1534,8 @@ impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> { impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S> where K: Eq + Hash, S: HashState + Default { - fn from_iter<T: Iterator<Item=(K, V)>>(iter: T) -> HashMap<K, V, S> { + fn from_iter<T: IntoIterator<Item=(K, V)>>(iterable: T) -> HashMap<K, V, S> { + let iter = iterable.into_iter(); let lower = iter.size_hint().0; let mut map = HashMap::with_capacity_and_hash_state(lower, Default::default()); @@ -1547,7 +1548,7 @@ impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S> impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S> where K: Eq + Hash, S: HashState { - 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); } diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs index 7ff76452c1a..751dc86f533 100644 --- a/src/libstd/collections/hash/set.rs +++ b/src/libstd/collections/hash/set.rs @@ -614,7 +614,8 @@ impl<T, S> FromIterator<T> for HashSet<T, S> where T: Eq + Hash, S: HashState + Default, { - fn from_iter<I: Iterator<Item=T>>(iter: I) -> HashSet<T, S> { + fn from_iter<I: IntoIterator<Item=T>>(iterable: I) -> HashSet<T, S> { + let iter = iterable.into_iter(); let lower = iter.size_hint().0; let mut set = HashSet::with_capacity_and_hash_state(lower, Default::default()); set.extend(iter); @@ -627,7 +628,7 @@ impl<T, S> Extend<T> for HashSet<T, S> where T: Eq + Hash, S: HashState, { - fn extend<I: Iterator<Item=T>>(&mut self, iter: I) { + fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) { for k in iter { self.insert(k); } diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs index be441bfec88..0e64370df60 100644 --- a/src/libstd/collections/mod.rs +++ b/src/libstd/collections/mod.rs @@ -23,7 +23,7 @@ //! //! Rust's collections can be grouped into four major categories: //! -//! * Sequences: `Vec`, `RingBuf`, `DList`, `BitV` +//! * Sequences: `Vec`, `VecDeque`, `LinkedList`, `BitV` //! * Maps: `HashMap`, `BTreeMap`, `VecMap` //! * Sets: `HashSet`, `BTreeSet`, `BitVSet` //! * Misc: `BinaryHeap` @@ -43,13 +43,13 @@ //! * You want a resizable array. //! * You want a heap-allocated array. //! -//! ### Use a `RingBuf` when: +//! ### Use a `VecDeque` when: //! * You want a `Vec` that supports efficient insertion at both ends of the sequence. //! * You want a queue. //! * You want a double-ended queue (deque). //! -//! ### Use a `DList` when: -//! * You want a `Vec` or `RingBuf` of unknown size, and can't tolerate amortization. +//! ### Use a `LinkedList` when: +//! * You want a `Vec` or `VecDeque` of unknown size, and can't tolerate amortization. //! * You want to efficiently split and append lists. //! * You are *absolutely* certain you *really*, *truly*, want a doubly linked list. //! @@ -75,7 +75,7 @@ //! //! ### Use a `BitV` when: //! * You want to store an unbounded number of booleans in a small space. -//! * You want a bitvector. +//! * You want a bit vector. //! //! ### Use a `BitVSet` when: //! * You want a `VecSet`. @@ -106,20 +106,20 @@ //! //! ## Sequences //! -//! | | get(i) | insert(i) | remove(i) | append | split_off(i) | -//! |---------|----------------|-----------------|----------------|--------|----------------| -//! | Vec | O(1) | O(n-i)* | O(n-i) | O(m)* | O(n-i) | -//! | RingBuf | O(1) | O(min(i, n-i))* | O(min(i, n-i)) | O(m)* | O(min(i, n-i)) | -//! | DList | O(min(i, n-i)) | O(min(i, n-i)) | O(min(i, n-i)) | O(1) | O(min(i, n-i)) | -//! | Bitv | O(1) | O(n-i)* | O(n-i) | O(m)* | O(n-i) | +//! | | get(i) | insert(i) | remove(i) | append | split_off(i) | +//! |--------------|----------------|-----------------|----------------|--------|----------------| +//! | Vec | O(1) | O(n-i)* | O(n-i) | O(m)* | O(n-i) | +//! | VecDeque | O(1) | O(min(i, n-i))* | O(min(i, n-i)) | O(m)* | O(min(i, n-i)) | +//! | LinkedList | O(min(i, n-i)) | O(min(i, n-i)) | O(min(i, n-i)) | O(1) | O(min(i, n-i)) | +//! | BitVec | O(1) | O(n-i)* | O(n-i) | O(m)* | O(n-i) | //! -//! Note that where ties occur, Vec is generally going to be faster than RingBuf, and RingBuf -//! is generally going to be faster than DList. Bitv is not a general purpose collection, and +//! Note that where ties occur, Vec is generally going to be faster than VecDeque, and VecDeque +//! is generally going to be faster than LinkedList. BitVec is not a general purpose collection, and //! therefore cannot reasonably be compared. //! //! ## Maps //! -//! For Sets, all operations have the cost of the equivalent Map operation. For BitvSet, +//! For Sets, all operations have the cost of the equivalent Map operation. For BitSet, //! refer to VecMap. //! //! | | get | insert | remove | predecessor | @@ -166,7 +166,7 @@ //! //! Any `with_capacity` constructor will instruct the collection to allocate enough space //! for the specified number of elements. Ideally this will be for exactly that many -//! elements, but some implementation details may prevent this. `Vec` and `RingBuf` can +//! elements, but some implementation details may prevent this. `Vec` and `VecDeque` can //! be relied on to allocate exactly the requested amount, though. Use `with_capacity` //! when you know exactly how many elements will be inserted, or at least have a //! reasonable upper-bound on that number. @@ -240,10 +240,10 @@ //! ``` //! //! ``` -//! use std::collections::RingBuf; +//! use std::collections::VecDeque; //! //! let vec = vec![1, 2, 3, 4]; -//! let buf: RingBuf<_> = vec.into_iter().collect(); +//! let buf: VecDeque<_> = vec.into_iter().collect(); //! ``` //! //! Iterators also provide a series of *adapter* methods for performing common tasks to @@ -362,11 +362,11 @@ #![stable(feature = "rust1", since = "1.0.0")] pub use core_collections::Bound; -pub use core_collections::{BinaryHeap, Bitv, BitvSet, BTreeMap, BTreeSet}; -pub use core_collections::{DList, RingBuf, VecMap}; +pub use core_collections::{BinaryHeap, BitVec, BitSet, BTreeMap, BTreeSet}; +pub use core_collections::{LinkedList, VecDeque, VecMap}; -pub use core_collections::{binary_heap, bitv, bitv_set, btree_map, btree_set}; -pub use core_collections::{dlist, ring_buf, vec_map}; +pub use core_collections::{binary_heap, bit_vec, bit_set, btree_map, btree_set}; +pub use core_collections::{linked_list, vec_deque, vec_map}; pub use self::hash_map::HashMap; pub use self::hash_set::HashSet; diff --git a/src/libstd/path.rs b/src/libstd/path.rs index 1d992668900..2ad07462f20 100755 --- a/src/libstd/path.rs +++ b/src/libstd/path.rs @@ -110,7 +110,7 @@ use core::prelude::*; use ascii::*; use borrow::BorrowFrom; use cmp; -use iter; +use iter::{self, IntoIterator}; use mem; use ops::{self, Deref}; use string::CowString; @@ -953,7 +953,7 @@ impl PathBuf { } impl<'a, P: ?Sized + 'a> iter::FromIterator<&'a P> for PathBuf where P: AsPath { - fn from_iter<I: Iterator<Item = &'a P>>(iter: I) -> PathBuf { + fn from_iter<I: IntoIterator<Item = &'a P>>(iter: I) -> PathBuf { let mut buf = PathBuf::new(""); buf.extend(iter); buf @@ -961,7 +961,7 @@ impl<'a, P: ?Sized + 'a> iter::FromIterator<&'a P> for PathBuf where P: AsPath { } impl<'a, P: ?Sized + 'a> iter::Extend<&'a P> for PathBuf where P: AsPath { - fn extend<I: Iterator<Item = &'a P>>(&mut self, iter: I) { + fn extend<I: IntoIterator<Item = &'a P>>(&mut self, iter: I) { for p in iter { self.push(p) } diff --git a/src/libstd/sys/common/wtf8.rs b/src/libstd/sys/common/wtf8.rs index c4f2de7fb45..ca3ae1a7a34 100644 --- a/src/libstd/sys/common/wtf8.rs +++ b/src/libstd/sys/common/wtf8.rs @@ -33,7 +33,7 @@ use cmp; use fmt; use hash::{Hash, Hasher}; #[cfg(stage0)] use hash::Writer; -use iter::FromIterator; +use iter::{FromIterator, IntoIterator}; use mem; use num::Int; use ops; @@ -357,9 +357,9 @@ impl Wtf8Buf { /// This replaces surrogate code point pairs with supplementary code points, /// like concatenating ill-formed UTF-16 strings effectively would. impl FromIterator<CodePoint> for Wtf8Buf { - fn from_iter<T: Iterator<Item=CodePoint>>(iterator: T) -> Wtf8Buf { + fn from_iter<T: IntoIterator<Item=CodePoint>>(iter: T) -> Wtf8Buf { let mut string = Wtf8Buf::new(); - string.extend(iterator); + string.extend(iter); string } } @@ -369,7 +369,8 @@ impl FromIterator<CodePoint> for Wtf8Buf { /// This replaces surrogate code point pairs with supplementary code points, /// like concatenating ill-formed UTF-16 strings effectively would. impl Extend<CodePoint> for Wtf8Buf { - fn extend<T: Iterator<Item=CodePoint>>(&mut self, iterator: T) { + fn extend<T: IntoIterator<Item=CodePoint>>(&mut self, iterable: T) { + let iterator = iterable.into_iter(); let (low, _high) = iterator.size_hint(); // Lower bound of one byte per code point (ASCII only) self.bytes.reserve(low); diff --git a/src/libsyntax/attr.rs b/src/libsyntax/attr.rs index a3afe5780d0..56efa5e0c93 100644 --- a/src/libsyntax/attr.rs +++ b/src/libsyntax/attr.rs @@ -26,11 +26,11 @@ use parse::token; use ptr::P; use std::cell::{RefCell, Cell}; -use std::collections::BitvSet; +use std::collections::BitSet; use std::collections::HashSet; use std::fmt; -thread_local! { static USED_ATTRS: RefCell<BitvSet> = RefCell::new(BitvSet::new()) } +thread_local! { static USED_ATTRS: RefCell<BitSet> = RefCell::new(BitSet::new()) } pub fn mark_used(attr: &Attribute) { let AttrId(id) = attr.node.id; diff --git a/src/libsyntax/owned_slice.rs b/src/libsyntax/owned_slice.rs index 0f9a56baa17..f5201d4a8bc 100644 --- a/src/libsyntax/owned_slice.rs +++ b/src/libsyntax/owned_slice.rs @@ -10,7 +10,7 @@ use std::default::Default; use std::fmt; -use std::iter::FromIterator; +use std::iter::{IntoIterator, FromIterator}; use std::ops::Deref; use std::vec; use serialize::{Encodable, Decodable, Encoder, Decoder}; @@ -77,8 +77,8 @@ impl<T: Clone> Clone for OwnedSlice<T> { } impl<T> FromIterator<T> for OwnedSlice<T> { - fn from_iter<I: Iterator<Item=T>>(iter: I) -> OwnedSlice<T> { - OwnedSlice::from_vec(iter.collect()) + fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> OwnedSlice<T> { + OwnedSlice::from_vec(iter.into_iter().collect()) } } diff --git a/src/libsyntax/util/small_vector.rs b/src/libsyntax/util/small_vector.rs index b2009a7e848..0a39d380904 100644 --- a/src/libsyntax/util/small_vector.rs +++ b/src/libsyntax/util/small_vector.rs @@ -11,7 +11,7 @@ use self::SmallVectorRepr::*; use self::IntoIterRepr::*; -use std::iter::FromIterator; +use std::iter::{IntoIterator, FromIterator}; use std::mem; use std::slice; use std::vec; @@ -30,7 +30,7 @@ enum SmallVectorRepr<T> { } impl<T> FromIterator<T> for SmallVector<T> { - fn from_iter<I: Iterator<Item=T>>(iter: I) -> SmallVector<T> { + fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> SmallVector<T> { let mut v = SmallVector::zero(); v.extend(iter); v @@ -38,7 +38,7 @@ impl<T> FromIterator<T> for SmallVector<T> { } impl<T> Extend<T> for SmallVector<T> { - fn extend<I: Iterator<Item=T>>(&mut self, iter: I) { + fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) { for val in iter { self.push(val); } diff --git a/src/test/bench/core-set.rs b/src/test/bench/core-set.rs index 7cbc4e1d7af..994c9605fc3 100644 --- a/src/test/bench/core-set.rs +++ b/src/test/bench/core-set.rs @@ -16,7 +16,7 @@ extern crate collections; extern crate rand; use std::collections::BTreeSet; -use std::collections::BitvSet; +use std::collections::BitSet; use std::collections::HashSet; use std::hash::Hash; use std::env; @@ -52,7 +52,7 @@ impl<T: Ord> MutableSet<T> for BTreeSet<T> { fn remove(&mut self, k: &T) -> bool { self.remove(k) } fn contains(&self, k: &T) -> bool { self.contains(k) } } -impl MutableSet<usize> for BitvSet { +impl MutableSet<usize> for BitSet { fn insert(&mut self, k: usize) { self.insert(k); } fn remove(&mut self, k: &usize) -> bool { self.remove(k) } fn contains(&self, k: &usize) -> bool { self.contains(k) } @@ -221,7 +221,7 @@ fn main() { { let mut rng: rand::IsaacRng = rand::SeedableRng::from_seed(seed); let mut results = empty_results(); - results.bench_int(&mut rng, num_keys, max, || BitvSet::new()); - write_results("collections::bitv::BitvSet", &results); + results.bench_int(&mut rng, num_keys, max, || BitSet::new()); + write_results("collections::bit_vec::BitSet", &results); } } |