Implement RFC 580

This commit implements RFC 580 by renaming: * DList -> LinkedList * Bitv -> BitVec * BitvSet -> BitSet * RingBuf -> VecDeque More details are in [the RFC](https://github.com/rust-lang/rfcs/pull/580) [breaking-change]
author: Aaron Turon <aturon@mozilla.com> 2015-02-17 23:44:55 -0800
committer: Alexis <a.beingessner@gmail.com> 2015-02-18 14:01:46 -0500
commit: 5fa9de16df87ab844452821acff1b6c74e948327 (patch)
tree: c4f4c06960f557277c07457b14bf61f8861ba8e2
parent: dfc5c0f1e8799f47f9033bdcc8a7cd8a217620a5 (diff)
download: rust-5fa9de16df87ab844452821acff1b6c74e948327.tar.gz
rust-5fa9de16df87ab844452821acff1b6c74e948327.zip
12 files changed, 917 insertions, 876 deletions
diff --git a/src/libcollections/bit.rs b/src/libcollections/bit.rs
index 0b762788b20..a2e36155933 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,22 +917,22 @@ impl Bitv {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl Default for Bitv {
+impl Default for BitVec {
     #[inline]
-    fn default() -> Bitv { Bitv::new() }
+    fn default() -> BitVec { BitVec::new() }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl FromIterator<bool> for Bitv {
-    fn from_iter<I:Iterator<Item=bool>>(iterator: I) -> Bitv {
-        let mut ret = Bitv::new();
+impl FromIterator<bool> for BitVec {
+    fn from_iter<I:Iterator<Item=bool>>(iterator: I) -> BitVec {
+        let mut ret = BitVec::new();
         ret.extend(iterator);
         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) {
         let (min, _) = iterator.size_hint();
@@ -944,37 +944,37 @@ impl Extend<bool> for Bitv {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl Clone for Bitv {
+impl Clone for BitVec {
     #[inline]
-    fn clone(&self) -> Bitv {
-        Bitv { storage: self.storage.clone(), nbits: self.nbits }
+    fn clone(&self) -> BitVec {
+        BitVec { storage: self.storage.clone(), nbits: self.nbits }
     }
 
     #[inline]
-    fn clone_from(&mut self, source: &Bitv) {
+    fn clone_from(&mut self, source: &BitVec) {
         self.nbits = source.nbits;
         self.storage.clone_from(&source.storage);
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl PartialOrd for Bitv {
+impl PartialOrd for BitVec {
     #[inline]
-    fn partial_cmp(&self, other: &Bitv) -> Option<Ordering> {
+    fn partial_cmp(&self, other: &BitVec) -> Option<Ordering> {
         iter::order::partial_cmp(self.iter(), other.iter())
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl Ord for Bitv {
+impl Ord for BitVec {
     #[inline]
-    fn cmp(&self, other: &Bitv) -> Ordering {
+    fn cmp(&self, other: &BitVec) -> Ordering {
         iter::order::cmp(self.iter(), other.iter())
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl fmt::Debug for Bitv {
+impl fmt::Debug for BitVec {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
         for bit in self {
             try!(write!(fmt, "{}", if bit { 1u32 } else { 0u32 }));
@@ -984,7 +984,7 @@ impl fmt::Debug for Bitv {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-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() {
@@ -994,9 +994,9 @@ impl<S: hash::Writer + hash::Hasher> hash::Hash<S> 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;
         }
@@ -1005,13 +1005,13 @@ impl cmp::PartialEq for Bitv {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl cmp::Eq for Bitv {}
+impl cmp::Eq for BitVec {}
 
-/// An iterator for `Bitv`.
+/// An iterator for `BitVec`.
 #[stable(feature = "rust1", since = "1.0.0")]
 #[derive(Clone)]
 pub struct Iter<'a> {
-    bitv: &'a Bitv,
+    bit_vec: &'a BitVec,
     next_idx: usize,
     end_idx: usize,
 }
@@ -1025,7 +1025,7 @@ impl<'a> Iterator for Iter<'a> {
         if self.next_idx != self.end_idx {
             let idx = self.next_idx;
             self.next_idx += 1;
-            Some(self.bitv[idx])
+            Some(self.bit_vec[idx])
         } else {
             None
         }
@@ -1043,7 +1043,7 @@ impl<'a> DoubleEndedIterator for Iter<'a> {
     fn next_back(&mut self) -> Option<bool> {
         if self.next_idx != self.end_idx {
             self.end_idx -= 1;
-            Some(self.bitv[self.end_idx])
+            Some(self.bit_vec[self.end_idx])
         } else {
             None
         }
@@ -1065,13 +1065,13 @@ impl<'a> RandomAccessIterator for Iter<'a> {
         if index >= self.indexable() {
             None
         } else {
-            Some(self.bitv[index])
+            Some(self.bit_vec[index])
         }
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<'a> IntoIterator for &'a Bitv {
+impl<'a> IntoIterator for &'a BitVec {
     type Item = bool;
     type IntoIter = Iter<'a>;
 
@@ -1090,10 +1090,10 @@ impl<'a> IntoIterator for &'a Bitv {
 /// # Examples
 ///
 /// ```
-/// use std::collections::{BitvSet, Bitv};
+/// use std::collections::{BitSet, BitVec};
 ///
 /// // It's a regular set
-/// let mut s = BitvSet::new();
+/// let mut s = BitSet::new();
 /// s.insert(0);
 /// s.insert(3);
 /// s.insert(7);
@@ -1104,8 +1104,8 @@ impl<'a> IntoIterator for &'a Bitv {
 ///     println!("There is no 7");
 /// }
 ///
-/// // Can initialize from a `Bitv`
-/// let other = BitvSet::from_bitv(Bitv::from_bytes(&[0b11010000]));
+/// // Can initialize from a `BitVec`
+/// let other = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11010000]));
 ///
 /// s.union_with(&other);
 ///
@@ -1114,34 +1114,34 @@ impl<'a> IntoIterator for &'a Bitv {
 ///     println!("{}", x);
 /// }
 ///
-/// // Can convert back to a `Bitv`
-/// let bv: Bitv = s.into_bitv();
+/// // Can convert back to a `BitVec`
+/// let bv: BitVec = s.into_bit_vec();
 /// assert!(bv[3]);
 /// ```
 #[derive(Clone)]
 #[unstable(feature = "collections",
            reason = "RFC 509")]
-pub struct BitvSet {
-    bitv: Bitv,
+pub struct BitSet {
+    bit_vec: BitVec,
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl Default for BitvSet {
+impl Default for BitSet {
     #[inline]
-    fn default() -> BitvSet { BitvSet::new() }
+    fn default() -> BitSet { BitSet::new() }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl FromIterator<usize> for BitvSet {
-    fn from_iter<I:Iterator<Item=usize>>(iterator: I) -> BitvSet {
-        let mut ret = BitvSet::new();
+impl FromIterator<usize> for BitSet {
+    fn from_iter<I:Iterator<Item=usize>>(iterator: I) -> BitSet {
+        let mut ret = BitSet::new();
         ret.extend(iterator);
         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 {
@@ -1151,78 +1151,78 @@ impl Extend<usize> for BitvSet {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl PartialOrd for BitvSet {
+impl PartialOrd for BitSet {
     #[inline]
-    fn partial_cmp(&self, other: &BitvSet) -> Option<Ordering> {
+    fn partial_cmp(&self, other: &BitSet) -> Option<Ordering> {
         let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
         iter::order::partial_cmp(a_iter, b_iter)
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl Ord for BitvSet {
+impl Ord for BitSet {
     #[inline]
-    fn cmp(&self, other: &BitvSet) -> Ordering {
+    fn cmp(&self, other: &BitSet) -> Ordering {
         let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
         iter::order::cmp(a_iter, b_iter)
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl cmp::PartialEq for BitvSet {
+impl cmp::PartialEq for BitSet {
     #[inline]
-    fn eq(&self, other: &BitvSet) -> bool {
+    fn eq(&self, other: &BitSet) -> bool {
         let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref());
         iter::order::eq(a_iter, b_iter)
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl cmp::Eq for BitvSet {}
+impl cmp::Eq for BitSet {}
 
-impl BitvSet {
-    /// Creates a new empty `BitvSet`.
+impl BitSet {
+    /// Creates a new empty `BitSet`.
     ///
     /// # Examples
     ///
     /// ```
-    /// use std::collections::BitvSet;
+    /// use std::collections::BitSet;
     ///
-    /// let mut s = BitvSet::new();
+    /// let mut s = BitSet::new();
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn new() -> BitvSet {
-        BitvSet { bitv: Bitv::new() }
+    pub fn new() -> BitSet {
+        BitSet { bit_vec: BitVec::new() }
     }
 
-    /// Creates a new `BitvSet` with initially no contents, able to
+    /// Creates a new `BitSet` with initially no contents, able to
     /// hold `nbits` elements without resizing.
     ///
     /// # Examples
     ///
     /// ```
-    /// use std::collections::BitvSet;
+    /// use std::collections::BitSet;
     ///
-    /// let mut s = BitvSet::with_capacity(100);
+    /// let mut s = BitSet::with_capacity(100);
     /// assert!(s.capacity() >= 100);
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn with_capacity(nbits: usize) -> BitvSet {
-        let bitv = Bitv::from_elem(nbits, false);
-        BitvSet::from_bitv(bitv)
+    pub fn with_capacity(nbits: usize) -> BitSet {
+        let bit_vec = BitVec::from_elem(nbits, false);
+        BitSet::from_bit_vec(bit_vec)
     }
 
-    /// Creates a new `BitvSet` from the given bit vector.
+    /// Creates a new `BitSet` from the given bit vector.
     ///
     /// # Examples
     ///
     /// ```
-    /// use std::collections::{Bitv, BitvSet};
+    /// use std::collections::{BitVec, BitSet};
     ///
-    /// let bv = Bitv::from_bytes(&[0b01100000]);
-    /// let s = BitvSet::from_bitv(bv);
+    /// let bv = BitVec::from_bytes(&[0b01100000]);
+    /// let s = BitSet::from_bit_vec(bv);
     ///
     /// // Print 1, 2 in arbitrary order
     /// for x in s.iter() {
@@ -1230,8 +1230,16 @@ impl BitvSet {
     /// }
     /// ```
     #[inline]
-    pub fn from_bitv(bitv: Bitv) -> BitvSet {
-        BitvSet { bitv: bitv }
+    pub fn from_bit_vec(bit_vec: BitVec) -> BitSet {
+        BitSet { bit_vec: bit_vec }
+    }
+
+    /// Deprecated: use `from_bit_vec`.
+    #[inline]
+    #[deprecated(since = "1.0.0", reason = "renamed to from_bit_vec")]
+    #[unstable(feature = "collections")]
+    pub fn from_bitv(bit_vec: BitVec) -> BitSet {
+        BitSet { bit_vec: bit_vec }
     }
 
     /// Returns the capacity in bits for this bit vector. Inserting any
@@ -1240,19 +1248,19 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::BitvSet;
+    /// use std::collections::BitSet;
     ///
-    /// let mut s = BitvSet::with_capacity(100);
+    /// let mut s = BitSet::with_capacity(100);
     /// assert!(s.capacity() >= 100);
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn capacity(&self) -> usize {
-        self.bitv.capacity()
+        self.bit_vec.capacity()
     }
 
-    /// Reserves capacity for the given `BitvSet` to contain `len` distinct elements. In the case
-    /// of `BitvSet` this means reallocations will not occur as long as all inserted elements
+    /// Reserves capacity for the given `BitSet` to contain `len` distinct elements. In the case
+    /// of `BitSet` this means reallocations will not occur as long as all inserted elements
     /// are less than `len`.
     ///
     /// The collection may reserve more space to avoid frequent reallocations.
@@ -1261,22 +1269,22 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::BitvSet;
+    /// use std::collections::BitSet;
     ///
-    /// let mut s = BitvSet::new();
+    /// let mut s = BitSet::new();
     /// s.reserve_len(10);
     /// assert!(s.capacity() >= 10);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn reserve_len(&mut self, len: usize) {
-        let cur_len = self.bitv.len();
+        let cur_len = self.bit_vec.len();
         if len >= cur_len {
-            self.bitv.reserve(len - cur_len);
+            self.bit_vec.reserve(len - cur_len);
         }
     }
 
-    /// Reserves the minimum capacity for the given `BitvSet` to contain `len` distinct elements.
-    /// In the case of `BitvSet` this means reallocations will not occur as long as all inserted
+    /// Reserves the minimum capacity for the given `BitSet` to contain `len` distinct elements.
+    /// In the case of `BitSet` this means reallocations will not occur as long as all inserted
     /// elements are less than `len`.
     ///
     /// Note that the allocator may give the collection more space than it requests. Therefore
@@ -1287,17 +1295,17 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::BitvSet;
+    /// use std::collections::BitSet;
     ///
-    /// let mut s = BitvSet::new();
+    /// let mut s = BitSet::new();
     /// s.reserve_len_exact(10);
     /// assert!(s.capacity() >= 10);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn reserve_len_exact(&mut self, len: usize) {
-        let cur_len = self.bitv.len();
+        let cur_len = self.bit_vec.len();
         if len >= cur_len {
-            self.bitv.reserve_exact(len - cur_len);
+            self.bit_vec.reserve_exact(len - cur_len);
         }
     }
 
@@ -1307,19 +1315,19 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::BitvSet;
+    /// use std::collections::BitSet;
     ///
-    /// let mut s = BitvSet::new();
+    /// let mut s = BitSet::new();
     /// s.insert(0);
     /// s.insert(3);
     ///
-    /// let bv = s.into_bitv();
+    /// let bv = s.into_bit_vec();
     /// assert!(bv[0]);
     /// assert!(bv[3]);
     /// ```
     #[inline]
-    pub fn into_bitv(self) -> Bitv {
-        self.bitv
+    pub fn into_bit_vec(self) -> BitVec {
+        self.bit_vec
     }
 
     /// Returns a reference to the underlying bit vector.
@@ -1327,44 +1335,44 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::BitvSet;
+    /// use std::collections::BitSet;
     ///
-    /// let mut s = BitvSet::new();
+    /// let mut s = BitSet::new();
     /// s.insert(0);
     ///
     /// let bv = s.get_ref();
     /// assert_eq!(bv[0], true);
     /// ```
     #[inline]
-    pub fn get_ref(&self) -> &Bitv {
-        &self.bitv
+    pub fn get_ref(&self) -> &BitVec {
+        &self.bit_vec
     }
 
     #[inline]
-    fn other_op<F>(&mut self, other: &BitvSet, mut f: F) where F: FnMut(u32, u32) -> u32 {
-        // Unwrap Bitvs
-        let self_bitv = &mut self.bitv;
-        let other_bitv = &other.bitv;
+    fn other_op<F>(&mut self, other: &BitSet, mut f: F) where F: FnMut(u32, u32) -> u32 {
+        // Unwrap BitVecs
+        let self_bit_vec = &mut self.bit_vec;
+        let other_bit_vec = &other.bit_vec;
 
-        let self_len = self_bitv.len();
-        let other_len = other_bitv.len();
+        let self_len = self_bit_vec.len();
+        let other_len = other_bit_vec.len();
 
         // Expand the vector if necessary
         if self_len < other_len {
-            self_bitv.grow(other_len - self_len, false);
+            self_bit_vec.grow(other_len - self_len, false);
         }
 
         // virtually pad other with 0's for equal lengths
         let other_words = {
-            let (_, result) = match_words(self_bitv, other_bitv);
+            let (_, result) = match_words(self_bit_vec, other_bit_vec);
             result
         };
 
         // Apply values found in other
         for (i, w) in other_words {
-            let old = self_bitv.storage[i];
+            let old = self_bit_vec.storage[i];
             let new = f(old, w);
-            self_bitv.storage[i] = new;
+            self_bit_vec.storage[i] = new;
         }
     }
 
@@ -1373,9 +1381,9 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::BitvSet;
+    /// use std::collections::BitSet;
     ///
-    /// let mut s = BitvSet::new();
+    /// let mut s = BitSet::new();
     /// s.insert(32183231);
     /// s.remove(&32183231);
     ///
@@ -1389,25 +1397,25 @@ impl BitvSet {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn shrink_to_fit(&mut self) {
-        let bitv = &mut self.bitv;
+        let bit_vec = &mut self.bit_vec;
         // Obtain original length
-        let old_len = bitv.storage.len();
+        let old_len = bit_vec.storage.len();
         // Obtain coarse trailing zero length
-        let n = bitv.storage.iter().rev().take_while(|&&n| n == 0).count();
+        let n = bit_vec.storage.iter().rev().take_while(|&&n| n == 0).count();
         // Truncate
         let trunc_len = cmp::max(old_len - n, 1);
-        bitv.storage.truncate(trunc_len);
-        bitv.nbits = trunc_len * u32::BITS;
+        bit_vec.storage.truncate(trunc_len);
+        bit_vec.nbits = trunc_len * u32::BITS;
     }
 
-    /// Iterator over each u32 stored in the `BitvSet`.
+    /// Iterator over each u32 stored in the `BitSet`.
     ///
     /// # Examples
     ///
     /// ```
-    /// use std::collections::{Bitv, BitvSet};
+    /// use std::collections::{BitVec, BitSet};
     ///
-    /// let s = BitvSet::from_bitv(Bitv::from_bytes(&[0b01001010]));
+    /// let s = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01001010]));
     ///
     /// // Print 1, 4, 6 in arbitrary order
     /// for x in s.iter() {
@@ -1416,7 +1424,7 @@ impl BitvSet {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn iter(&self) -> bitv_set::Iter {
+    pub fn iter(&self) -> bit_set::Iter {
         SetIter {set: self, next_idx: 0}
     }
 
@@ -1426,10 +1434,10 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::{Bitv, BitvSet};
+    /// use std::collections::{BitVec, BitSet};
     ///
-    /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
-    /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
+    /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
+    /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
     ///
     /// // Print 0, 1, 2, 4 in arbitrary order
     /// for x in a.union(&b) {
@@ -1438,7 +1446,7 @@ impl BitvSet {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn union<'a>(&'a self, other: &'a BitvSet) -> Union<'a> {
+    pub fn union<'a>(&'a self, other: &'a BitSet) -> Union<'a> {
         fn or(w1: u32, w2: u32) -> u32 { w1 | w2 }
 
         Union(TwoBitPositions {
@@ -1456,10 +1464,10 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::{Bitv, BitvSet};
+    /// use std::collections::{BitVec, BitSet};
     ///
-    /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
-    /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
+    /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
+    /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
     ///
     /// // Print 2
     /// for x in a.intersection(&b) {
@@ -1468,9 +1476,9 @@ impl BitvSet {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Intersection<'a> {
+    pub fn intersection<'a>(&'a self, other: &'a BitSet) -> Intersection<'a> {
         fn bitand(w1: u32, w2: u32) -> u32 { w1 & w2 }
-        let min = cmp::min(self.bitv.len(), other.bitv.len());
+        let min = cmp::min(self.bit_vec.len(), other.bit_vec.len());
         Intersection(TwoBitPositions {
             set: self,
             other: other,
@@ -1486,10 +1494,10 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::{BitvSet, Bitv};
+    /// use std::collections::{BitSet, BitVec};
     ///
-    /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
-    /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
+    /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
+    /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
     ///
     /// // Print 1, 4 in arbitrary order
     /// for x in a.difference(&b) {
@@ -1505,7 +1513,7 @@ impl BitvSet {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn difference<'a>(&'a self, other: &'a BitvSet) -> Difference<'a> {
+    pub fn difference<'a>(&'a self, other: &'a BitSet) -> Difference<'a> {
         fn diff(w1: u32, w2: u32) -> u32 { w1 & !w2 }
 
         Difference(TwoBitPositions {
@@ -1524,10 +1532,10 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::{BitvSet, Bitv};
+    /// use std::collections::{BitSet, BitVec};
     ///
-    /// let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101000]));
-    /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100000]));
+    /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
+    /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
     ///
     /// // Print 0, 1, 4 in arbitrary order
     /// for x in a.symmetric_difference(&b) {
@@ -1536,7 +1544,7 @@ impl BitvSet {
     /// ```
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> SymmetricDifference<'a> {
+    pub fn symmetric_difference<'a>(&'a self, other: &'a BitSet) -> SymmetricDifference<'a> {
         fn bitxor(w1: u32, w2: u32) -> u32 { w1 ^ w2 }
 
         SymmetricDifference(TwoBitPositions {
@@ -1553,21 +1561,21 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::{BitvSet, Bitv};
+    /// use std::collections::{BitSet, BitVec};
     ///
     /// let a   = 0b01101000;
     /// let b   = 0b10100000;
     /// let res = 0b11101000;
     ///
-    /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
-    /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
-    /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res]));
+    /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
+    /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
+    /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));
     ///
     /// a.union_with(&b);
     /// assert_eq!(a, res);
     /// ```
     #[inline]
-    pub fn union_with(&mut self, other: &BitvSet) {
+    pub fn union_with(&mut self, other: &BitSet) {
         self.other_op(other, |w1, w2| w1 | w2);
     }
 
@@ -1576,21 +1584,21 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::{BitvSet, Bitv};
+    /// use std::collections::{BitSet, BitVec};
     ///
     /// let a   = 0b01101000;
     /// let b   = 0b10100000;
     /// let res = 0b00100000;
     ///
-    /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
-    /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
-    /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res]));
+    /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
+    /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
+    /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));
     ///
     /// a.intersect_with(&b);
     /// assert_eq!(a, res);
     /// ```
     #[inline]
-    pub fn intersect_with(&mut self, other: &BitvSet) {
+    pub fn intersect_with(&mut self, other: &BitSet) {
         self.other_op(other, |w1, w2| w1 & w2);
     }
 
@@ -1600,29 +1608,29 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::{BitvSet, Bitv};
+    /// use std::collections::{BitSet, BitVec};
     ///
     /// let a   = 0b01101000;
     /// let b   = 0b10100000;
     /// let a_b = 0b01001000; // a - b
     /// let b_a = 0b10000000; // b - a
     ///
-    /// let mut bva = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
-    /// let bvb = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
-    /// let bva_b = BitvSet::from_bitv(Bitv::from_bytes(&[a_b]));
-    /// let bvb_a = BitvSet::from_bitv(Bitv::from_bytes(&[b_a]));
+    /// let mut bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
+    /// let bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
+    /// let bva_b = BitSet::from_bit_vec(BitVec::from_bytes(&[a_b]));
+    /// let bvb_a = BitSet::from_bit_vec(BitVec::from_bytes(&[b_a]));
     ///
     /// bva.difference_with(&bvb);
     /// assert_eq!(bva, bva_b);
     ///
-    /// let bva = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
-    /// let mut bvb = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
+    /// let bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
+    /// let mut bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
     ///
     /// bvb.difference_with(&bva);
     /// assert_eq!(bvb, bvb_a);
     /// ```
     #[inline]
-    pub fn difference_with(&mut self, other: &BitvSet) {
+    pub fn difference_with(&mut self, other: &BitSet) {
         self.other_op(other, |w1, w2| w1 & !w2);
     }
 
@@ -1632,21 +1640,21 @@ impl BitvSet {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::{BitvSet, Bitv};
+    /// use std::collections::{BitSet, BitVec};
     ///
     /// let a   = 0b01101000;
     /// let b   = 0b10100000;
     /// let res = 0b11001000;
     ///
-    /// let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[a]));
-    /// let b = BitvSet::from_bitv(Bitv::from_bytes(&[b]));
-    /// let res = BitvSet::from_bitv(Bitv::from_bytes(&[res]));
+    /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
+    /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
+    /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));
     ///
     /// a.symmetric_difference_with(&b);
     /// assert_eq!(a, res);
     /// ```
     #[inline]
-    pub fn symmetric_difference_with(&mut self, other: &BitvSet) {
+    pub fn symmetric_difference_with(&mut self, other: &BitSet) {
         self.other_op(other, |w1, w2| w1 ^ w2);
     }
 
@@ -1654,57 +1662,57 @@ impl BitvSet {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn len(&self) -> usize  {
-        self.bitv.blocks().fold(0, |acc, n| acc + n.count_ones())
+        self.bit_vec.blocks().fold(0, |acc, n| acc + n.count_ones())
     }
 
     /// Returns whether there are no bits set in this set
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn is_empty(&self) -> bool {
-        self.bitv.none()
+        self.bit_vec.none()
     }
 
     /// Clears all bits in this set
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn clear(&mut self) {
-        self.bitv.clear();
+        self.bit_vec.clear();
     }
 
     /// Returns `true` if this set contains the specified integer.
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn contains(&self, value: &usize) -> bool {
-        let bitv = &self.bitv;
-        *value < bitv.nbits && bitv[*value]
+        let bit_vec = &self.bit_vec;
+        *value < bit_vec.nbits && bit_vec[*value]
     }
 
     /// Returns `true` if the set has no elements in common with `other`.
     /// This is equivalent to checking for an empty intersection.
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn is_disjoint(&self, other: &BitvSet) -> bool {
+    pub fn is_disjoint(&self, other: &BitSet) -> bool {
         self.intersection(other).next().is_none()
     }
 
     /// Returns `true` if the set is a subset of another.
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn is_subset(&self, other: &BitvSet) -> bool {
-        let self_bitv = &self.bitv;
-        let other_bitv = &other.bitv;
-        let other_blocks = blocks_for_bits(other_bitv.len());
+    pub fn is_subset(&self, other: &BitSet) -> bool {
+        let self_bit_vec = &self.bit_vec;
+        let other_bit_vec = &other.bit_vec;
+        let other_blocks = blocks_for_bits(other_bit_vec.len());
 
         // Check that `self` intersect `other` is self
-        self_bitv.blocks().zip(other_bitv.blocks()).all(|(w1, w2)| w1 & w2 == w1) &&
+        self_bit_vec.blocks().zip(other_bit_vec.blocks()).all(|(w1, w2)| w1 & w2 == w1) &&
         // Make sure if `self` has any more blocks than `other`, they're all 0
-        self_bitv.blocks().skip(other_blocks).all(|w| w == 0)
+        self_bit_vec.blocks().skip(other_blocks).all(|w| w == 0)
     }
 
     /// Returns `true` if the set is a superset of another.
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn is_superset(&self, other: &BitvSet) -> bool {
+    pub fn is_superset(&self, other: &BitSet) -> bool {
         other.is_subset(self)
     }
 
@@ -1717,12 +1725,12 @@ impl BitvSet {
         }
 
         // Ensure we have enough space to hold the new element
-        let len = self.bitv.len();
+        let len = self.bit_vec.len();
         if value >= len {
-            self.bitv.grow(value - len + 1, false)
+            self.bit_vec.grow(value - len + 1, false)
         }
 
-        self.bitv.set(value, true);
+        self.bit_vec.set(value, true);
         return true;
     }
 
@@ -1734,16 +1742,16 @@ impl BitvSet {
             return false;
         }
 
-        self.bitv.set(*value, false);
+        self.bit_vec.set(*value, false);
 
         return true;
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl fmt::Debug for BitvSet {
+impl fmt::Debug for BitSet {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        try!(write!(fmt, "BitvSet {{"));
+        try!(write!(fmt, "BitSet {{"));
         let mut first = true;
         for n in self {
             if !first {
@@ -1756,7 +1764,7 @@ impl fmt::Debug for BitvSet {
     }
 }
 
-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);
@@ -1764,19 +1772,19 @@ impl<S: hash::Writer + hash::Hasher> hash::Hash<S> 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
@@ -1796,7 +1804,7 @@ impl<'a> Iterator for SetIter<'a> {
     type Item = usize;
 
     fn next(&mut self) -> Option<usize> {
-        while self.next_idx < self.set.bitv.len() {
+        while self.next_idx < self.set.bit_vec.len() {
             let idx = self.next_idx;
             self.next_idx += 1;
 
@@ -1810,7 +1818,7 @@ impl<'a> Iterator for SetIter<'a> {
 
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
-        (0, Some(self.set.bitv.len() - self.next_idx))
+        (0, Some(self.set.bit_vec.len() - self.next_idx))
     }
 }
 
@@ -1819,20 +1827,20 @@ impl<'a> Iterator for TwoBitPositions<'a> {
     type Item = usize;
 
     fn next(&mut self) -> Option<usize> {
-        while self.next_idx < self.set.bitv.len() ||
-              self.next_idx < self.other.bitv.len() {
+        while self.next_idx < self.set.bit_vec.len() ||
+              self.next_idx < self.other.bit_vec.len() {
             let bit_idx = self.next_idx % u32::BITS;
             if bit_idx == 0 {
-                let s_bitv = &self.set.bitv;
-                let o_bitv = &self.other.bitv;
+                let s_bit_vec = &self.set.bit_vec;
+                let o_bit_vec = &self.other.bit_vec;
                 // Merging the two words is a bit of an awkward dance since
-                // one Bitv might be longer than the other
+                // one BitVec might be longer than the other
                 let word_idx = self.next_idx / u32::BITS;
-                let w1 = if word_idx < s_bitv.storage.len() {
-                             s_bitv.storage[word_idx]
+                let w1 = if word_idx < s_bit_vec.storage.len() {
+                             s_bit_vec.storage[word_idx]
                          } else { 0 };
-                let w2 = if word_idx < o_bitv.storage.len() {
-                             o_bitv.storage[word_idx]
+                let w2 = if word_idx < o_bit_vec.storage.len() {
+                             o_bit_vec.storage[word_idx]
                          } else { 0 };
                 self.current_word = (self.merge)(w1, w2);
             }
@@ -1847,7 +1855,7 @@ impl<'a> Iterator for TwoBitPositions<'a> {
 
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
-        let cap = cmp::max(self.set.bitv.len(), self.other.bitv.len());
+        let cap = cmp::max(self.set.bit_vec.len(), self.other.bit_vec.len());
         (0, Some(cap - self.next_idx))
     }
 }
@@ -1885,7 +1893,7 @@ impl<'a> Iterator for SymmetricDifference<'a> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<'a> IntoIterator for &'a BitvSet {
+impl<'a> IntoIterator for &'a BitSet {
     type Item = usize;
     type IntoIter = SetIter<'a>;
 
@@ -1899,20 +1907,20 @@ mod tests {
     use prelude::*;
     use core::u32;
 
-    use super::Bitv;
+    use super::BitVec;
 
     #[test]
     fn test_to_str() {
-        let zerolen = Bitv::new();
+        let zerolen = BitVec::new();
         assert_eq!(format!("{:?}", zerolen), "");
 
-        let eightbits = Bitv::from_elem(8, false);
+        let eightbits = BitVec::from_elem(8, false);
         assert_eq!(format!("{:?}", eightbits), "00000000")
     }
 
     #[test]
     fn test_0_elements() {
-        let act = Bitv::new();
+        let act = BitVec::new();
         let exp = Vec::new();
         assert!(act.eq_vec(&exp));
         assert!(act.none() && act.all());
@@ -1920,17 +1928,17 @@ mod tests {
 
     #[test]
     fn test_1_element() {
-        let mut act = Bitv::from_elem(1, false);
+        let mut act = BitVec::from_elem(1, false);
         assert!(act.eq_vec(&[false]));
         assert!(act.none() && !act.all());
-        act = Bitv::from_elem(1, true);
+        act = BitVec::from_elem(1, true);
         assert!(act.eq_vec(&[true]));
         assert!(!act.none() && act.all());
     }
 
     #[test]
     fn test_2_elements() {
-        let mut b = Bitv::from_elem(2, false);
+        let mut b = BitVec::from_elem(2, false);
         b.set(0, true);
         b.set(1, false);
         assert_eq!(format!("{:?}", b), "10");
@@ -1942,18 +1950,18 @@ mod tests {
         let mut act;
         // all 0
 
-        act = Bitv::from_elem(10, false);
+        act = BitVec::from_elem(10, false);
         assert!((act.eq_vec(
                     &[false, false, false, false, false, false, false, false, false, false])));
         assert!(act.none() && !act.all());
         // all 1
 
-        act = Bitv::from_elem(10, true);
+        act = BitVec::from_elem(10, true);
         assert!((act.eq_vec(&[true, true, true, true, true, true, true, true, true, true])));
         assert!(!act.none() && act.all());
         // mixed
 
-        act = Bitv::from_elem(10, false);
+        act = BitVec::from_elem(10, false);
         act.set(0, true);
         act.set(1, true);
         act.set(2, true);
@@ -1963,7 +1971,7 @@ mod tests {
         assert!(!act.none() && !act.all());
         // mixed
 
-        act = Bitv::from_elem(10, false);
+        act = BitVec::from_elem(10, false);
         act.set(5, true);
         act.set(6, true);
         act.set(7, true);
@@ -1973,7 +1981,7 @@ mod tests {
         assert!(!act.none() && !act.all());
         // mixed
 
-        act = Bitv::from_elem(10, false);
+        act = BitVec::from_elem(10, false);
         act.set(0, true);
         act.set(3, true);
         act.set(6, true);
@@ -1987,7 +1995,7 @@ mod tests {
         let mut act;
         // all 0
 
-        act = Bitv::from_elem(31, false);
+        act = BitVec::from_elem(31, false);
         assert!(act.eq_vec(
                 &[false, false, false, false, false, false, false, false, false, false, false,
                   false, false, false, false, false, false, false, false, false, false, false,
@@ -1995,7 +2003,7 @@ mod tests {
         assert!(act.none() && !act.all());
         // all 1
 
-        act = Bitv::from_elem(31, true);
+        act = BitVec::from_elem(31, true);
         assert!(act.eq_vec(
                 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
                   true, true, true, true, true, true, true, true, true, true, true, true, true,
@@ -2003,7 +2011,7 @@ mod tests {
         assert!(!act.none() && act.all());
         // mixed
 
-        act = Bitv::from_elem(31, false);
+        act = BitVec::from_elem(31, false);
         act.set(0, true);
         act.set(1, true);
         act.set(2, true);
@@ -2019,7 +2027,7 @@ mod tests {
         assert!(!act.none() && !act.all());
         // mixed
 
-        act = Bitv::from_elem(31, false);
+        act = BitVec::from_elem(31, false);
         act.set(16, true);
         act.set(17, true);
         act.set(18, true);
@@ -2035,7 +2043,7 @@ mod tests {
         assert!(!act.none() && !act.all());
         // mixed
 
-        act = Bitv::from_elem(31, false);
+        act = BitVec::from_elem(31, false);
         act.set(24, true);
         act.set(25, true);
         act.set(26, true);
@@ -2050,7 +2058,7 @@ mod tests {
         assert!(!act.none() && !act.all());
         // mixed
 
-        act = Bitv::from_elem(31, false);
+        act = BitVec::from_elem(31, false);
         act.set(3, true);
         act.set(17, true);
         act.set(30, true);
@@ -2066,7 +2074,7 @@ mod tests {
         let mut act;
         // all 0
 
-        act = Bitv::from_elem(32, false);
+        act = BitVec::from_elem(32, false);
         assert!(act.eq_vec(
                 &[false, false, false, false, false, false, false, false, false, false, false,
                   false, false, false, false, false, false, false, false, false, false, false,
@@ -2074,7 +2082,7 @@ mod tests {
         assert!(act.none() && !act.all());
         // all 1
 
-        act = Bitv::from_elem(32, true);
+        act = BitVec::from_elem(32, true);
         assert!(act.eq_vec(
                 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
                   true, true, true, true, true, true, true, true, true, true, true, true, true,
@@ -2082,7 +2090,7 @@ mod tests {
         assert!(!act.none() && act.all());
         // mixed
 
-        act = Bitv::from_elem(32, false);
+        act = BitVec::from_elem(32, false);
         act.set(0, true);
         act.set(1, true);
         act.set(2, true);
@@ -2098,7 +2106,7 @@ mod tests {
         assert!(!act.none() && !act.all());
         // mixed
 
-        act = Bitv::from_elem(32, false);
+        act = BitVec::from_elem(32, false);
         act.set(16, true);
         act.set(17, true);
         act.set(18, true);
@@ -2114,7 +2122,7 @@ mod tests {
         assert!(!act.none() && !act.all());
         // mixed
 
-        act = Bitv::from_elem(32, false);
+        act = BitVec::from_elem(32, false);
         act.set(24, true);
         act.set(25, true);
         act.set(26, true);
@@ -2130,7 +2138,7 @@ mod tests {
         assert!(!act.none() && !act.all());
         // mixed
 
-        act = Bitv::from_elem(32, false);
+        act = BitVec::from_elem(32, false);
         act.set(3, true);
         act.set(17, true);
         act.set(30, true);
@@ -2147,7 +2155,7 @@ mod tests {
         let mut act;
         // all 0
 
-        act = Bitv::from_elem(33, false);
+        act = BitVec::from_elem(33, false);
         assert!(act.eq_vec(
                 &[false, false, false, false, false, false, false, false, false, false, false,
                   false, false, false, false, false, false, false, false, false, false, false,
@@ -2155,7 +2163,7 @@ mod tests {
         assert!(act.none() && !act.all());
         // all 1
 
-        act = Bitv::from_elem(33, true);
+        act = BitVec::from_elem(33, true);
         assert!(act.eq_vec(
                 &[true, true, true, true, true, true, true, true, true, true, true, true, true,
                   true, true, true, true, true, true, true, true, true, true, true, true, true,
@@ -2163,7 +2171,7 @@ mod tests {
         assert!(!act.none() && act.all());
         // mixed
 
-        act = Bitv::from_elem(33, false);
+        act = BitVec::from_elem(33, false);
         act.set(0, true);
         act.set(1, true);
         act.set(2, true);
@@ -2179,7 +2187,7 @@ mod tests {
         assert!(!act.none() && !act.all());
         // mixed
 
-        act = Bitv::from_elem(33, false);
+        act = BitVec::from_elem(33, false);
         act.set(16, true);
         act.set(17, true);
         act.set(18, true);
@@ -2195,7 +2203,7 @@ mod tests {
         assert!(!act.none() && !act.all());
         // mixed
 
-        act = Bitv::from_elem(33, false);
+        act = BitVec::from_elem(33, false);
         act.set(24, true);
         act.set(25, true);
         act.set(26, true);
@@ -2211,7 +2219,7 @@ mod tests {
         assert!(!act.none() && !act.all());
         // mixed
 
-        act = Bitv::from_elem(33, false);
+        act = BitVec::from_elem(33, false);
         act.set(3, true);
         act.set(17, true);
         act.set(30, true);
@@ -2226,24 +2234,24 @@ mod tests {
 
     #[test]
     fn test_equal_differing_sizes() {
-        let v0 = Bitv::from_elem(10, false);
-        let v1 = Bitv::from_elem(11, false);
+        let v0 = BitVec::from_elem(10, false);
+        let v1 = BitVec::from_elem(11, false);
         assert!(v0 != v1);
     }
 
     #[test]
     fn test_equal_greatly_differing_sizes() {
-        let v0 = Bitv::from_elem(10, false);
-        let v1 = Bitv::from_elem(110, false);
+        let v0 = BitVec::from_elem(10, false);
+        let v1 = BitVec::from_elem(110, false);
         assert!(v0 != v1);
     }
 
     #[test]
     fn test_equal_sneaky_small() {
-        let mut a = Bitv::from_elem(1, false);
+        let mut a = BitVec::from_elem(1, false);
         a.set(0, true);
 
-        let mut b = Bitv::from_elem(1, true);
+        let mut b = BitVec::from_elem(1, true);
         b.set(0, true);
 
         assert_eq!(a, b);
@@ -2251,12 +2259,12 @@ mod tests {
 
     #[test]
     fn test_equal_sneaky_big() {
-        let mut a = Bitv::from_elem(100, false);
+        let mut a = BitVec::from_elem(100, false);
         for i in 0..100 {
             a.set(i, true);
         }
 
-        let mut b = Bitv::from_elem(100, true);
+        let mut b = BitVec::from_elem(100, true);
         for i in 0..100 {
             b.set(i, true);
         }
@@ -2266,18 +2274,18 @@ mod tests {
 
     #[test]
     fn test_from_bytes() {
-        let bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
+        let bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
         let str = concat!("10110110", "00000000", "11111111");
-        assert_eq!(format!("{:?}", bitv), str);
+        assert_eq!(format!("{:?}", bit_vec), str);
     }
 
     #[test]
     fn test_to_bytes() {
-        let mut bv = Bitv::from_elem(3, true);
+        let mut bv = BitVec::from_elem(3, true);
         bv.set(1, false);
         assert_eq!(bv.to_bytes(), vec!(0b10100000));
 
-        let mut bv = Bitv::from_elem(9, false);
+        let mut bv = BitVec::from_elem(9, false);
         bv.set(2, true);
         bv.set(8, true);
         assert_eq!(bv.to_bytes(), vec!(0b00100000, 0b10000000));
@@ -2286,32 +2294,32 @@ mod tests {
     #[test]
     fn test_from_bools() {
         let bools = vec![true, false, true, true];
-        let bitv: Bitv = bools.iter().map(|n| *n).collect();
-        assert_eq!(format!("{:?}", bitv), "1011");
+        let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
+        assert_eq!(format!("{:?}", bit_vec), "1011");
     }
 
     #[test]
     fn test_to_bools() {
         let bools = vec![false, false, true, false, false, true, true, false];
-        assert_eq!(Bitv::from_bytes(&[0b00100110]).iter().collect::<Vec<bool>>(), bools);
+        assert_eq!(BitVec::from_bytes(&[0b00100110]).iter().collect::<Vec<bool>>(), bools);
     }
 
     #[test]
-    fn test_bitv_iterator() {
+    fn test_bit_vec_iterator() {
         let bools = vec![true, false, true, true];
-        let bitv: Bitv = bools.iter().map(|n| *n).collect();
+        let bit_vec: BitVec = bools.iter().map(|n| *n).collect();
 
-        assert_eq!(bitv.iter().collect::<Vec<bool>>(), bools);
+        assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), bools);
 
         let long: Vec<_> = (0i32..10000).map(|i| i % 2 == 0).collect();
-        let bitv: Bitv = long.iter().map(|n| *n).collect();
-        assert_eq!(bitv.iter().collect::<Vec<bool>>(), long)
+        let bit_vec: BitVec = long.iter().map(|n| *n).collect();
+        assert_eq!(bit_vec.iter().collect::<Vec<bool>>(), long)
     }
 
     #[test]
     fn test_small_difference() {
-        let mut b1 = Bitv::from_elem(3, false);
-        let mut b2 = Bitv::from_elem(3, false);
+        let mut b1 = BitVec::from_elem(3, false);
+        let mut b2 = BitVec::from_elem(3, false);
         b1.set(0, true);
         b1.set(1, true);
         b2.set(1, true);
@@ -2324,8 +2332,8 @@ mod tests {
 
     #[test]
     fn test_big_difference() {
-        let mut b1 = Bitv::from_elem(100, false);
-        let mut b2 = Bitv::from_elem(100, false);
+        let mut b1 = BitVec::from_elem(100, false);
+        let mut b2 = BitVec::from_elem(100, false);
         b1.set(0, true);
         b1.set(40, true);
         b2.set(40, true);
@@ -2338,7 +2346,7 @@ mod tests {
 
     #[test]
     fn test_small_clear() {
-        let mut b = Bitv::from_elem(14, true);
+        let mut b = BitVec::from_elem(14, true);
         assert!(!b.none() && b.all());
         b.clear();
         assert!(b.none() && !b.all());
@@ -2346,16 +2354,16 @@ mod tests {
 
     #[test]
     fn test_big_clear() {
-        let mut b = Bitv::from_elem(140, true);
+        let mut b = BitVec::from_elem(140, true);
         assert!(!b.none() && b.all());
         b.clear();
         assert!(b.none() && !b.all());
     }
 
     #[test]
-    fn test_bitv_lt() {
-        let mut a = Bitv::from_elem(5, false);
-        let mut b = Bitv::from_elem(5, false);
+    fn test_bit_vec_lt() {
+        let mut a = BitVec::from_elem(5, false);
+        let mut b = BitVec::from_elem(5, false);
 
         assert!(!(a < b) && !(b < a));
         b.set(2, true);
@@ -2370,8 +2378,8 @@ mod tests {
 
     #[test]
     fn test_ord() {
-        let mut a = Bitv::from_elem(5, false);
-        let mut b = Bitv::from_elem(5, false);
+        let mut a = BitVec::from_elem(5, false);
+        let mut b = BitVec::from_elem(5, false);
 
         assert!(a <= b && a >= b);
         a.set(1, true);
@@ -2385,26 +2393,26 @@ mod tests {
 
 
     #[test]
-    fn test_small_bitv_tests() {
-        let v = Bitv::from_bytes(&[0]);
+    fn test_small_bit_vec_tests() {
+        let v = BitVec::from_bytes(&[0]);
         assert!(!v.all());
         assert!(!v.any());
         assert!(v.none());
 
-        let v = Bitv::from_bytes(&[0b00010100]);
+        let v = BitVec::from_bytes(&[0b00010100]);
         assert!(!v.all());
         assert!(v.any());
         assert!(!v.none());
 
-        let v = Bitv::from_bytes(&[0xFF]);
+        let v = BitVec::from_bytes(&[0xFF]);
         assert!(v.all());
         assert!(v.any());
         assert!(!v.none());
     }
 
     #[test]
-    fn test_big_bitv_tests() {
-        let v = Bitv::from_bytes(&[ // 88 bits
+    fn test_big_bit_vec_tests() {
+        let v = BitVec::from_bytes(&[ // 88 bits
             0, 0, 0, 0,
             0, 0, 0, 0,
             0, 0, 0]);
@@ -2412,7 +2420,7 @@ mod tests {
         assert!(!v.any());
         assert!(v.none());
 
-        let v = Bitv::from_bytes(&[ // 88 bits
+        let v = BitVec::from_bytes(&[ // 88 bits
             0, 0, 0b00010100, 0,
             0, 0, 0, 0b00110100,
             0, 0, 0]);
@@ -2420,7 +2428,7 @@ mod tests {
         assert!(v.any());
         assert!(!v.none());
 
-        let v = Bitv::from_bytes(&[ // 88 bits
+        let v = BitVec::from_bytes(&[ // 88 bits
             0xFF, 0xFF, 0xFF, 0xFF,
             0xFF, 0xFF, 0xFF, 0xFF,
             0xFF, 0xFF, 0xFF]);
@@ -2430,8 +2438,8 @@ mod tests {
     }
 
     #[test]
-    fn test_bitv_push_pop() {
-        let mut s = Bitv::from_elem(5 * u32::BITS - 2, false);
+    fn test_bit_vec_push_pop() {
+        let mut s = BitVec::from_elem(5 * u32::BITS - 2, false);
         assert_eq!(s.len(), 5 * u32::BITS - 2);
         assert_eq!(s[5 * u32::BITS - 3], false);
         s.push(true);
@@ -2453,29 +2461,29 @@ mod tests {
     }
 
     #[test]
-    fn test_bitv_truncate() {
-        let mut s = Bitv::from_elem(5 * u32::BITS, true);
+    fn test_bit_vec_truncate() {
+        let mut s = BitVec::from_elem(5 * u32::BITS, true);
 
-        assert_eq!(s, Bitv::from_elem(5 * u32::BITS, true));
+        assert_eq!(s, BitVec::from_elem(5 * u32::BITS, true));
         assert_eq!(s.len(), 5 * u32::BITS);
         s.truncate(4 * u32::BITS);
-        assert_eq!(s, Bitv::from_elem(4 * u32::BITS, true));
+        assert_eq!(s, BitVec::from_elem(4 * u32::BITS, true));
         assert_eq!(s.len(), 4 * u32::BITS);
         // Truncating to a size > s.len() should be a noop
         s.truncate(5 * u32::BITS);
-        assert_eq!(s, Bitv::from_elem(4 * u32::BITS, true));
+        assert_eq!(s, BitVec::from_elem(4 * u32::BITS, true));
         assert_eq!(s.len(), 4 * u32::BITS);
         s.truncate(3 * u32::BITS - 10);
-        assert_eq!(s, Bitv::from_elem(3 * u32::BITS - 10, true));
+        assert_eq!(s, BitVec::from_elem(3 * u32::BITS - 10, true));
         assert_eq!(s.len(), 3 * u32::BITS - 10);
         s.truncate(0);
-        assert_eq!(s, Bitv::from_elem(0, true));
+        assert_eq!(s, BitVec::from_elem(0, true));
         assert_eq!(s.len(), 0);
     }
 
     #[test]
-    fn test_bitv_reserve() {
-        let mut s = Bitv::from_elem(5 * u32::BITS, true);
+    fn test_bit_vec_reserve() {
+        let mut s = BitVec::from_elem(5 * u32::BITS, true);
         // Check capacity
         assert!(s.capacity() >= 5 * u32::BITS);
         s.reserve(2 * u32::BITS);
@@ -2498,25 +2506,25 @@ mod tests {
     }
 
     #[test]
-    fn test_bitv_grow() {
-        let mut bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010]);
-        bitv.grow(32, true);
-        assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
+    fn test_bit_vec_grow() {
+        let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010]);
+        bit_vec.grow(32, true);
+        assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
                                      0xFF, 0xFF, 0xFF, 0xFF]));
-        bitv.grow(64, false);
-        assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
+        bit_vec.grow(64, false);
+        assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
                                      0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0]));
-        bitv.grow(16, true);
-        assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
+        bit_vec.grow(16, true);
+        assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b10101010,
                                      0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF]));
     }
 
     #[test]
-    fn test_bitv_extend() {
-        let mut bitv = Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
-        let ext = Bitv::from_bytes(&[0b01001001, 0b10010010, 0b10111101]);
-        bitv.extend(ext.iter());
-        assert_eq!(bitv, Bitv::from_bytes(&[0b10110110, 0b00000000, 0b11111111,
+    fn test_bit_vec_extend() {
+        let mut bit_vec = BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111]);
+        let ext = BitVec::from_bytes(&[0b01001001, 0b10010010, 0b10111101]);
+        bit_vec.extend(ext.iter());
+        assert_eq!(bit_vec, BitVec::from_bytes(&[0b10110110, 0b00000000, 0b11111111,
                                      0b01001001, 0b10010010, 0b10111101]));
     }
 }
@@ -2525,14 +2533,14 @@ mod tests {
 
 
 #[cfg(test)]
-mod bitv_bench {
+mod bit_vec_bench {
     use std::prelude::v1::*;
     use std::rand;
     use std::rand::Rng;
     use std::u32;
     use test::{Bencher, black_box};
 
-    use super::Bitv;
+    use super::BitVec;
 
     static BENCH_BITS : usize = 1 << 14;
 
@@ -2544,67 +2552,67 @@ mod bitv_bench {
     #[bench]
     fn bench_usize_small(b: &mut Bencher) {
         let mut r = rng();
-        let mut bitv = 0 as usize;
+        let mut bit_vec = 0 as usize;
         b.iter(|| {
             for _ in 0..100 {
-                bitv |= 1 << ((r.next_u32() as usize) % u32::BITS);
+                bit_vec |= 1 << ((r.next_u32() as usize) % u32::BITS);
             }
-            black_box(&bitv);
+            black_box(&bit_vec);
         });
     }
 
     #[bench]
-    fn bench_bitv_set_big_fixed(b: &mut Bencher) {
+    fn bench_bit_set_big_fixed(b: &mut Bencher) {
         let mut r = rng();
-        let mut bitv = Bitv::from_elem(BENCH_BITS, false);
+        let mut bit_vec = BitVec::from_elem(BENCH_BITS, false);
         b.iter(|| {
             for _ in 0..100 {
-                bitv.set((r.next_u32() as usize) % BENCH_BITS, true);
+                bit_vec.set((r.next_u32() as usize) % BENCH_BITS, true);
             }
-            black_box(&bitv);
+            black_box(&bit_vec);
         });
     }
 
     #[bench]
-    fn bench_bitv_set_big_variable(b: &mut Bencher) {
+    fn bench_bit_set_big_variable(b: &mut Bencher) {
         let mut r = rng();
-        let mut bitv = Bitv::from_elem(BENCH_BITS, false);
+        let mut bit_vec = BitVec::from_elem(BENCH_BITS, false);
         b.iter(|| {
             for _ in 0..100 {
-                bitv.set((r.next_u32() as usize) % BENCH_BITS, r.gen());
+                bit_vec.set((r.next_u32() as usize) % BENCH_BITS, r.gen());
             }
-            black_box(&bitv);
+            black_box(&bit_vec);
         });
     }
 
     #[bench]
-    fn bench_bitv_set_small(b: &mut Bencher) {
+    fn bench_bit_set_small(b: &mut Bencher) {
         let mut r = rng();
-        let mut bitv = Bitv::from_elem(u32::BITS, false);
+        let mut bit_vec = BitVec::from_elem(u32::BITS, false);
         b.iter(|| {
             for _ in 0..100 {
-                bitv.set((r.next_u32() as usize) % u32::BITS, true);
+                bit_vec.set((r.next_u32() as usize) % u32::BITS, true);
             }
-            black_box(&bitv);
+            black_box(&bit_vec);
         });
     }
 
     #[bench]
-    fn bench_bitv_big_union(b: &mut Bencher) {
-        let mut b1 = Bitv::from_elem(BENCH_BITS, false);
-        let b2 = Bitv::from_elem(BENCH_BITS, false);
+    fn bench_bit_vec_big_union(b: &mut Bencher) {
+        let mut b1 = BitVec::from_elem(BENCH_BITS, false);
+        let b2 = BitVec::from_elem(BENCH_BITS, false);
         b.iter(|| {
             b1.union(&b2)
         })
     }
 
     #[bench]
-    fn bench_bitv_small_iter(b: &mut Bencher) {
-        let bitv = Bitv::from_elem(u32::BITS, false);
+    fn bench_bit_vec_small_iter(b: &mut Bencher) {
+        let bit_vec = BitVec::from_elem(u32::BITS, false);
         b.iter(|| {
             let mut sum = 0;
             for _ in 0..10 {
-                for pres in &bitv {
+                for pres in &bit_vec {
                     sum += pres as usize;
                 }
             }
@@ -2613,11 +2621,11 @@ mod bitv_bench {
     }
 
     #[bench]
-    fn bench_bitv_big_iter(b: &mut Bencher) {
-        let bitv = Bitv::from_elem(BENCH_BITS, false);
+    fn bench_bit_vec_big_iter(b: &mut Bencher) {
+        let bit_vec = BitVec::from_elem(BENCH_BITS, false);
         b.iter(|| {
             let mut sum = 0;
-            for pres in &bitv {
+            for pres in &bit_vec {
                 sum += pres as usize;
             }
             sum
@@ -2632,27 +2640,27 @@ mod bitv_bench {
 
 
 #[cfg(test)]
-mod bitv_set_test {
+mod bit_set_test {
     use prelude::*;
     use std::iter::range_step;
 
-    use super::{Bitv, BitvSet};
+    use super::{BitVec, BitSet};
 
     #[test]
-    fn test_bitv_set_show() {
-        let mut s = BitvSet::new();
+    fn test_bit_set_show() {
+        let mut s = BitSet::new();
         s.insert(1);
         s.insert(10);
         s.insert(50);
         s.insert(2);
-        assert_eq!("BitvSet {1, 2, 10, 50}", format!("{:?}", s));
+        assert_eq!("BitSet {1, 2, 10, 50}", format!("{:?}", s));
     }
 
     #[test]
-    fn test_bitv_set_from_usizes() {
+    fn test_bit_set_from_usizes() {
         let usizes = vec![0, 2, 2, 3];
-        let a: BitvSet = usizes.into_iter().collect();
-        let mut b = BitvSet::new();
+        let a: BitSet = usizes.into_iter().collect();
+        let mut b = BitSet::new();
         b.insert(0);
         b.insert(2);
         b.insert(3);
@@ -2660,14 +2668,14 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_iterator() {
+    fn test_bit_set_iterator() {
         let usizes = vec![0, 2, 2, 3];
-        let bitv: BitvSet = usizes.into_iter().collect();
+        let bit_vec: BitSet = usizes.into_iter().collect();
 
-        let idxs: Vec<_> = bitv.iter().collect();
+        let idxs: Vec<_> = bit_vec.iter().collect();
         assert_eq!(idxs, vec![0, 2, 3]);
 
-        let long: BitvSet = (0..10000).filter(|&n| n % 2 == 0).collect();
+        let long: BitSet = (0..10000).filter(|&n| n % 2 == 0).collect();
         let real: Vec<_> = range_step(0, 10000, 2).collect();
 
         let idxs: Vec<_> = long.iter().collect();
@@ -2675,12 +2683,12 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_frombitv_init() {
+    fn test_bit_set_frombit_vec_init() {
         let bools = [true, false];
         let lengths = [10, 64, 100];
         for &b in &bools {
             for &l in &lengths {
-                let bitset = BitvSet::from_bitv(Bitv::from_elem(l, b));
+                let bitset = BitSet::from_bit_vec(BitVec::from_elem(l, b));
                 assert_eq!(bitset.contains(&1), b);
                 assert_eq!(bitset.contains(&(l-1)), b);
                 assert!(!bitset.contains(&l));
@@ -2689,9 +2697,9 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_masking() {
-        let b = Bitv::from_elem(140, true);
-        let mut bs = BitvSet::from_bitv(b);
+    fn test_bit_vec_masking() {
+        let b = BitVec::from_elem(140, true);
+        let mut bs = BitSet::from_bit_vec(b);
         assert!(bs.contains(&139));
         assert!(!bs.contains(&140));
         assert!(bs.insert(150));
@@ -2702,8 +2710,8 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_basic() {
-        let mut b = BitvSet::new();
+    fn test_bit_set_basic() {
+        let mut b = BitSet::new();
         assert!(b.insert(3));
         assert!(!b.insert(3));
         assert!(b.contains(&3));
@@ -2717,9 +2725,9 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_intersection() {
-        let mut a = BitvSet::new();
-        let mut b = BitvSet::new();
+    fn test_bit_set_intersection() {
+        let mut a = BitSet::new();
+        let mut b = BitSet::new();
 
         assert!(a.insert(11));
         assert!(a.insert(1));
@@ -2740,9 +2748,9 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_difference() {
-        let mut a = BitvSet::new();
-        let mut b = BitvSet::new();
+    fn test_bit_set_difference() {
+        let mut a = BitSet::new();
+        let mut b = BitSet::new();
 
         assert!(a.insert(1));
         assert!(a.insert(3));
@@ -2759,9 +2767,9 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_symmetric_difference() {
-        let mut a = BitvSet::new();
-        let mut b = BitvSet::new();
+    fn test_bit_set_symmetric_difference() {
+        let mut a = BitSet::new();
+        let mut b = BitSet::new();
 
         assert!(a.insert(1));
         assert!(a.insert(3));
@@ -2780,9 +2788,9 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_union() {
-        let mut a = BitvSet::new();
-        let mut b = BitvSet::new();
+    fn test_bit_set_union() {
+        let mut a = BitSet::new();
+        let mut b = BitSet::new();
         assert!(a.insert(1));
         assert!(a.insert(3));
         assert!(a.insert(5));
@@ -2805,9 +2813,9 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_subset() {
-        let mut set1 = BitvSet::new();
-        let mut set2 = BitvSet::new();
+    fn test_bit_set_subset() {
+        let mut set1 = BitSet::new();
+        let mut set2 = BitSet::new();
 
         assert!(set1.is_subset(&set2)); //  {}  {}
         set2.insert(100);
@@ -2831,11 +2839,11 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_is_disjoint() {
-        let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
-        let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01000000]));
-        let c = BitvSet::new();
-        let d = BitvSet::from_bitv(Bitv::from_bytes(&[0b00110000]));
+    fn test_bit_set_is_disjoint() {
+        let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+        let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01000000]));
+        let c = BitSet::new();
+        let d = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00110000]));
 
         assert!(!a.is_disjoint(&d));
         assert!(!d.is_disjoint(&a));
@@ -2849,19 +2857,19 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_union_with() {
+    fn test_bit_set_union_with() {
         //a should grow to include larger elements
-        let mut a = BitvSet::new();
+        let mut a = BitSet::new();
         a.insert(0);
-        let mut b = BitvSet::new();
+        let mut b = BitSet::new();
         b.insert(5);
-        let expected = BitvSet::from_bitv(Bitv::from_bytes(&[0b10000100]));
+        let expected = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10000100]));
         a.union_with(&b);
         assert_eq!(a, expected);
 
         // Standard
-        let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
-        let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010]));
+        let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+        let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010]));
         let c = a.clone();
         a.union_with(&b);
         b.union_with(&c);
@@ -2870,10 +2878,10 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_intersect_with() {
+    fn test_bit_set_intersect_with() {
         // Explicitly 0'ed bits
-        let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
-        let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
+        let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+        let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
         let c = a.clone();
         a.intersect_with(&b);
         b.intersect_with(&c);
@@ -2881,8 +2889,8 @@ mod bitv_set_test {
         assert!(b.is_empty());
 
         // Uninitialized bits should behave like 0's
-        let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
-        let mut b = BitvSet::new();
+        let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+        let mut b = BitSet::new();
         let c = a.clone();
         a.intersect_with(&b);
         b.intersect_with(&c);
@@ -2890,8 +2898,8 @@ mod bitv_set_test {
         assert!(b.is_empty());
 
         // Standard
-        let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
-        let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010]));
+        let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+        let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010]));
         let c = a.clone();
         a.intersect_with(&b);
         b.intersect_with(&c);
@@ -2900,22 +2908,22 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_difference_with() {
+    fn test_bit_set_difference_with() {
         // Explicitly 0'ed bits
-        let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
-        let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
+        let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
+        let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
         a.difference_with(&b);
         assert!(a.is_empty());
 
         // Uninitialized bits should behave like 0's
-        let mut a = BitvSet::new();
-        let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b11111111]));
+        let mut a = BitSet::new();
+        let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11111111]));
         a.difference_with(&b);
         assert!(a.is_empty());
 
         // Standard
-        let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
-        let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01100010]));
+        let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+        let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010]));
         let c = a.clone();
         a.difference_with(&b);
         b.difference_with(&c);
@@ -2924,27 +2932,27 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_symmetric_difference_with() {
+    fn test_bit_set_symmetric_difference_with() {
         //a should grow to include larger elements
-        let mut a = BitvSet::new();
+        let mut a = BitSet::new();
         a.insert(0);
         a.insert(1);
-        let mut b = BitvSet::new();
+        let mut b = BitSet::new();
         b.insert(1);
         b.insert(5);
-        let expected = BitvSet::from_bitv(Bitv::from_bytes(&[0b10000100]));
+        let expected = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10000100]));
         a.symmetric_difference_with(&b);
         assert_eq!(a, expected);
 
-        let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
-        let b = BitvSet::new();
+        let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+        let b = BitSet::new();
         let c = a.clone();
         a.symmetric_difference_with(&b);
         assert_eq!(a, c);
 
         // Standard
-        let mut a = BitvSet::from_bitv(Bitv::from_bytes(&[0b11100010]));
-        let mut b = BitvSet::from_bitv(Bitv::from_bytes(&[0b01101010]));
+        let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11100010]));
+        let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101010]));
         let c = a.clone();
         a.symmetric_difference_with(&b);
         b.symmetric_difference_with(&c);
@@ -2953,10 +2961,10 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_eq() {
-        let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
-        let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
-        let c = BitvSet::new();
+    fn test_bit_set_eq() {
+        let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+        let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
+        let c = BitSet::new();
 
         assert!(a == a);
         assert!(a != b);
@@ -2967,10 +2975,10 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_set_cmp() {
-        let a = BitvSet::from_bitv(Bitv::from_bytes(&[0b10100010]));
-        let b = BitvSet::from_bitv(Bitv::from_bytes(&[0b00000000]));
-        let c = BitvSet::new();
+    fn test_bit_set_cmp() {
+        let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
+        let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
+        let c = BitSet::new();
 
         assert_eq!(a.cmp(&b), Greater);
         assert_eq!(a.cmp(&c), Greater);
@@ -2981,8 +2989,8 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_remove() {
-        let mut a = BitvSet::new();
+    fn test_bit_vec_remove() {
+        let mut a = BitSet::new();
 
         assert!(a.insert(1));
         assert!(a.remove(&1));
@@ -2996,8 +3004,8 @@ mod bitv_set_test {
     }
 
     #[test]
-    fn test_bitv_clone() {
-        let mut a = BitvSet::new();
+    fn test_bit_vec_clone() {
+        let mut a = BitSet::new();
 
         assert!(a.insert(1));
         assert!(a.insert(100));
@@ -3020,14 +3028,14 @@ mod bitv_set_test {
 
 
 #[cfg(test)]
-mod bitv_set_bench {
+mod bit_set_bench {
     use std::prelude::v1::*;
     use std::rand;
     use std::rand::Rng;
     use std::u32;
     use test::{Bencher, black_box};
 
-    use super::{Bitv, BitvSet};
+    use super::{BitVec, BitSet};
 
     static BENCH_BITS : usize = 1 << 14;
 
@@ -3037,36 +3045,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 747211e9238..96052156df0 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,
 }
 
@@ -1189,7 +1189,7 @@ impl<K, V> BTreeMap<K, V> {
     pub fn iter(&self) -> Iter<K, V> {
         let len = self.len();
         // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases.
-        let mut lca = RingBuf::new();
+        let mut lca = VecDeque::new();
         lca.push_back(Traverse::traverse(&self.root));
         Iter {
             inner: AbsIter {
@@ -1221,7 +1221,7 @@ impl<K, V> BTreeMap<K, V> {
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn iter_mut(&mut self) -> IterMut<K, V> {
         let len = self.len();
-        let mut lca = RingBuf::new();
+        let mut lca = VecDeque::new();
         lca.push_back(Traverse::traverse(&mut self.root));
         IterMut {
             inner: AbsIter {
@@ -1250,7 +1250,7 @@ impl<K, V> BTreeMap<K, V> {
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn into_iter(self) -> IntoIter<K, V> {
         let len = self.len();
-        let mut lca = RingBuf::new();
+        let mut lca = VecDeque::new();
         lca.push_back(Traverse::traverse(self.root));
         IntoIter {
             inner: AbsIter {
@@ -1342,7 +1342,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/lib.rs b/src/libcollections/lib.rs
index cacbf3bce80..b9f50fc385b 100644
--- a/src/libcollections/lib.rs
+++ b/src/libcollections/lib.rs
@@ -49,17 +49,33 @@ extern crate alloc;
 #[cfg(test)] #[macro_use] extern crate log;
 
 pub use binary_heap::BinaryHeap;
-pub use bitv::Bitv;
-pub use bitv_set::BitvSet;
+pub use bit_vec::BitVec;
+pub use bit_set::BitSet;
 pub use btree_map::BTreeMap;
 pub use btree_set::BTreeSet;
-pub use dlist::DList;
+pub use linked_list::LinkedList;
 pub use enum_set::EnumSet;
-pub use ring_buf::RingBuf;
+pub use vec_deque::VecDeque;
 pub use string::String;
 pub use vec::Vec;
 pub use vec_map::VecMap;
 
+#[deprecated(since = "1.0.0", reason = "renamed to vec_deque")]
+#[unstable(feature = "collections")]
+pub use vec_deque as ring_buf;
+
+#[deprecated(since = "1.0.0", reason = "renamed to linked_list")]
+#[unstable(feature = "collections")]
+pub use linked_list as dlist;
+
+#[deprecated(since = "1.0.0", reason = "renamed to bit_vec")]
+#[unstable(feature = "collections")]
+pub use bit_vec as bitv;
+
+#[deprecated(since = "1.0.0", reason = "renamed to bit_set")]
+#[unstable(feature = "collections")]
+pub use bit_set as bitv_set;
+
 // Needed for the vec! macro
 pub use alloc::boxed;
 
@@ -71,10 +87,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;
@@ -83,15 +99,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 eb1bf93c0aa..550c1450b93 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")]
@@ -32,9 +32,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>>,
@@ -56,7 +60,7 @@ struct Node<T> {
     value: T,
 }
 
-/// An iterator over references to the items of a `DList`.
+/// An iterator over references to the items of a `LinkedList`.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Iter<'a, T:'a> {
     head: &'a Link<T>,
@@ -76,20 +80,20 @@ impl<'a, T> Clone for Iter<'a, T> {
     }
 }
 
-/// An iterator over mutable references to the items of a `DList`.
+/// An iterator over mutable references to the items of a `LinkedList`.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IterMut<'a, T:'a> {
-    list: &'a mut DList<T>,
+    list: &'a mut LinkedList<T>,
     head: Rawlink<Node<T>>,
     tail: Rawlink<Node<T>>,
     nelem: usize,
 }
 
-/// An iterator over mutable references to the items of a `DList`.
+/// An iterator over mutable references to the items of a `LinkedList`.
 #[derive(Clone)]
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IntoIter<T> {
-    list: DList<T>
+    list: LinkedList<T>
 }
 
 /// Rawlink is a type like Option<T> but for holding a raw pointer
@@ -147,7 +151,7 @@ fn link_with_prev<T>(mut next: Box<Node<T>>, prev: Rawlink<Node<T>>)
 }
 
 // private methods
-impl<T> DList<T> {
+impl<T> LinkedList<T> {
     /// Add a Node first in the list
     #[inline]
     fn push_front_node(&mut self, mut new_head: Box<Node<T>>) {
@@ -207,18 +211,18 @@ impl<T> DList<T> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<T> Default for DList<T> {
+impl<T> Default for LinkedList<T> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    fn default() -> DList<T> { DList::new() }
+    fn default() -> LinkedList<T> { LinkedList::new() }
 }
 
-impl<T> DList<T> {
-    /// Creates an empty `DList`.
+impl<T> LinkedList<T> {
+    /// Creates an empty `LinkedList`.
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn new() -> DList<T> {
-        DList{list_head: None, list_tail: Rawlink::none(), length: 0}
+    pub fn new() -> LinkedList<T> {
+        LinkedList{list_head: None, list_tail: Rawlink::none(), length: 0}
     }
 
     /// Moves all elements from `other` to the end of the list.
@@ -231,10 +235,10 @@ impl<T> DList<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut a = DList::new();
-    /// let mut b = DList::new();
+    /// let mut a = LinkedList::new();
+    /// let mut b = LinkedList::new();
     /// a.push_back(1);
     /// a.push_back(2);
     /// b.push_back(3);
@@ -247,7 +251,7 @@ impl<T> DList<T> {
     /// }
     /// println!("{}", b.len()); // prints 0
     /// ```
-    pub fn append(&mut self, other: &mut DList<T>) {
+    pub fn append(&mut self, other: &mut LinkedList<T>) {
         match self.list_tail.resolve() {
             None => {
                 self.length = other.length;
@@ -301,16 +305,16 @@ impl<T> DList<T> {
         IntoIter{list: self}
     }
 
-    /// Returns `true` if the `DList` is empty.
+    /// Returns `true` if the `LinkedList` is empty.
     ///
     /// This operation should compute in O(1) time.
     ///
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut dl = DList::new();
+    /// let mut dl = LinkedList::new();
     /// assert!(dl.is_empty());
     ///
     /// dl.push_front("foo");
@@ -322,16 +326,16 @@ impl<T> DList<T> {
         self.list_head.is_none()
     }
 
-    /// Returns the length of the `DList`.
+    /// Returns the length of the `LinkedList`.
     ///
     /// This operation should compute in O(1) time.
     ///
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut dl = DList::new();
+    /// let mut dl = LinkedList::new();
     ///
     /// dl.push_front(2);
     /// assert_eq!(dl.len(), 1);
@@ -349,16 +353,16 @@ impl<T> DList<T> {
         self.length
     }
 
-    /// Removes all elements from the `DList`.
+    /// Removes all elements from the `LinkedList`.
     ///
     /// This operation should compute in O(n) time.
     ///
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut dl = DList::new();
+    /// let mut dl = LinkedList::new();
     ///
     /// dl.push_front(2);
     /// dl.push_front(1);
@@ -373,7 +377,7 @@ impl<T> DList<T> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn clear(&mut self) {
-        *self = DList::new()
+        *self = LinkedList::new()
     }
 
     /// Provides a reference to the front element, or `None` if the list is
@@ -382,9 +386,9 @@ impl<T> DList<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut dl = DList::new();
+    /// let mut dl = LinkedList::new();
     /// assert_eq!(dl.front(), None);
     ///
     /// dl.push_front(1);
@@ -403,9 +407,9 @@ impl<T> DList<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut dl = DList::new();
+    /// let mut dl = LinkedList::new();
     /// assert_eq!(dl.front(), None);
     ///
     /// dl.push_front(1);
@@ -430,9 +434,9 @@ impl<T> DList<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut dl = DList::new();
+    /// let mut dl = LinkedList::new();
     /// assert_eq!(dl.back(), None);
     ///
     /// dl.push_back(1);
@@ -451,9 +455,9 @@ impl<T> DList<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut dl = DList::new();
+    /// let mut dl = LinkedList::new();
     /// assert_eq!(dl.back(), None);
     ///
     /// dl.push_back(1);
@@ -479,9 +483,9 @@ impl<T> DList<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut dl = DList::new();
+    /// let mut dl = LinkedList::new();
     ///
     /// dl.push_front(2);
     /// assert_eq!(dl.front().unwrap(), &2);
@@ -503,9 +507,9 @@ impl<T> DList<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut d = DList::new();
+    /// let mut d = LinkedList::new();
     /// assert_eq!(d.pop_front(), None);
     ///
     /// d.push_front(1);
@@ -526,9 +530,9 @@ impl<T> DList<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut d = DList::new();
+    /// let mut d = LinkedList::new();
     /// d.push_back(1);
     /// d.push_back(3);
     /// assert_eq!(3, *d.back().unwrap());
@@ -544,9 +548,9 @@ impl<T> DList<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut d = DList::new();
+    /// let mut d = LinkedList::new();
     /// assert_eq!(d.pop_back(), None);
     /// d.push_back(1);
     /// d.push_back(3);
@@ -569,9 +573,9 @@ impl<T> DList<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut d = DList::new();
+    /// let mut d = LinkedList::new();
     ///
     /// d.push_front(1);
     /// d.push_front(2);
@@ -583,13 +587,13 @@ impl<T> DList<T> {
     /// assert_eq!(splitted.pop_front(), None);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
-    pub fn split_off(&mut self, at: usize) -> DList<T> {
+    pub fn split_off(&mut self, at: usize) -> LinkedList<T> {
         let len = self.len();
         assert!(at <= len, "Cannot split off at a nonexistent index");
         if at == 0 {
-            return mem::replace(self, DList::new());
+            return mem::replace(self, LinkedList::new());
         } else if at == len {
-            return DList::new();
+            return LinkedList::new();
         }
 
         // Below, we iterate towards the `i-1`th node, either from the start or the end,
@@ -612,7 +616,7 @@ impl<T> DList<T> {
             iter.tail
         };
 
-        let mut splitted_list = DList {
+        let mut splitted_list = LinkedList {
             list_head: None,
             list_tail: self.list_tail,
             length: len - at
@@ -628,9 +632,9 @@ impl<T> DList<T> {
 
 #[unsafe_destructor]
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<T> Drop for DList<T> {
+impl<T> Drop for LinkedList<T> {
     fn drop(&mut self) {
-        // Dissolve the dlist in backwards direction
+        // Dissolve the linked_list in backwards direction
         // Just dropping the list_head can lead to stack exhaustion
         // when length is >> 1_000_000
         let mut tail = self.list_tail;
@@ -761,9 +765,9 @@ impl<'a, A> IterMut<'a, A> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut list: DList<_> = vec![1, 3, 4].into_iter().collect();
+    /// let mut list: LinkedList<_> = vec![1, 3, 4].into_iter().collect();
     ///
     /// {
     ///     let mut it = list.iter_mut();
@@ -788,9 +792,9 @@ impl<'a, A> IterMut<'a, A> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::DList;
+    /// use std::collections::LinkedList;
     ///
-    /// let mut list: DList<_> = vec![1, 2, 3].into_iter().collect();
+    /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
     ///
     /// let mut it = list.iter_mut();
     /// assert_eq!(it.next().unwrap(), &1);
@@ -829,16 +833,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> {
-        let mut ret = DList::new();
+impl<A> FromIterator<A> for LinkedList<A> {
+    fn from_iter<T: Iterator<Item=A>>(iterator: T) -> LinkedList<A> {
+        let mut ret = LinkedList::new();
         ret.extend(iterator);
         ret
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<T> IntoIterator for DList<T> {
+impl<T> IntoIterator for LinkedList<T> {
     type Item = T;
     type IntoIter = IntoIter<T>;
 
@@ -848,7 +852,7 @@ impl<T> IntoIterator for DList<T> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, T> IntoIterator for &'a DList<T> {
+impl<'a, T> IntoIterator for &'a LinkedList<T> {
     type Item = &'a T;
     type IntoIter = Iter<'a, T>;
 
@@ -857,7 +861,7 @@ impl<'a, T> IntoIterator for &'a DList<T> {
     }
 }
 
-impl<'a, T> IntoIterator for &'a mut DList<T> {
+impl<'a, T> IntoIterator for &'a mut LinkedList<T> {
     type Item = &'a mut T;
     type IntoIter = IterMut<'a, T>;
 
@@ -867,54 +871,54 @@ impl<'a, T> IntoIterator for &'a mut DList<T> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A> Extend<A> for DList<A> {
+impl<A> Extend<A> for LinkedList<A> {
     fn extend<T: Iterator<Item=A>>(&mut self, iterator: T) {
         for elt in iterator { 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().map(|x| x.clone()).collect()
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A: fmt::Debug> fmt::Debug for DList<A> {
+impl<A: fmt::Debug> fmt::Debug for LinkedList<A> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        try!(write!(f, "DList ["));
+        try!(write!(f, "LinkedList ["));
 
         for (i, e) in self.iter().enumerate() {
             if i != 0 { try!(write!(f, ", ")); }
@@ -926,7 +930,7 @@ impl<A: fmt::Debug> fmt::Debug for DList<A> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for DList<A> {
+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 {
@@ -944,9 +948,9 @@ mod tests {
     use test::Bencher;
     use test;
 
-    use super::{DList, Node};
+    use super::{LinkedList, Node};
 
-    pub fn check_links<T>(list: &DList<T>) {
+    pub fn check_links<T>(list: &LinkedList<T>) {
         let mut len = 0;
         let mut last_ptr: Option<&Node<T>> = None;
         let mut node_ptr: &Node<T>;
@@ -980,7 +984,7 @@ mod tests {
 
     #[test]
     fn test_basic() {
-        let mut m = DList::new();
+        let mut m = LinkedList::new();
         assert_eq!(m.pop_front(), None);
         assert_eq!(m.pop_back(), None);
         assert_eq!(m.pop_front(), None);
@@ -999,7 +1003,7 @@ mod tests {
         m.push_back(box 7);
         assert_eq!(m.pop_front(), Some(box 1));
 
-        let mut n = DList::new();
+        let mut n = LinkedList::new();
         n.push_front(2);
         n.push_front(3);
         {
@@ -1019,12 +1023,12 @@ mod tests {
     }
 
     #[cfg(test)]
-    fn generate_test() -> DList<i32> {
+    fn generate_test() -> LinkedList<i32> {
         list_from(&[0,1,2,3,4,5,6])
     }
 
     #[cfg(test)]
-    fn list_from<T: Clone>(v: &[T]) -> DList<T> {
+    fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
         v.iter().map(|x| (*x).clone()).collect()
     }
 
@@ -1032,8 +1036,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);
@@ -1041,8 +1045,8 @@ mod tests {
         }
         // Non-empty to empty
         {
-            let mut m = DList::new();
-            let mut n = DList::new();
+            let mut m = LinkedList::new();
+            let mut n = LinkedList::new();
             n.push_back(2);
             m.append(&mut n);
             check_links(&m);
@@ -1053,8 +1057,8 @@ mod tests {
         }
         // Empty to non-empty
         {
-            let mut m = DList::new();
-            let mut n = DList::new();
+            let mut m = LinkedList::new();
+            let mut n = LinkedList::new();
             m.push_back(2);
             m.append(&mut n);
             check_links(&m);
@@ -1089,7 +1093,7 @@ mod tests {
     fn test_split_off() {
         // singleton
         {
-            let mut m = DList::new();
+            let mut m = LinkedList::new();
             m.push_back(1);
 
             let p = m.split_off(0);
@@ -1130,7 +1134,7 @@ mod tests {
 
         // no-op on the last index
         {
-            let mut m = DList::new();
+            let mut m = LinkedList::new();
             m.push_back(1);
 
             let p = m.split_off(1);
@@ -1148,7 +1152,7 @@ mod tests {
         for (i, elt) in m.iter().enumerate() {
             assert_eq!(i as i32, *elt);
         }
-        let mut n = DList::new();
+        let mut n = LinkedList::new();
         assert_eq!(n.iter().next(), None);
         n.push_front(4);
         let mut it = n.iter();
@@ -1160,7 +1164,7 @@ mod tests {
 
     #[test]
     fn test_iterator_clone() {
-        let mut n = DList::new();
+        let mut n = LinkedList::new();
         n.push_back(2);
         n.push_back(3);
         n.push_back(4);
@@ -1174,7 +1178,7 @@ mod tests {
 
     #[test]
     fn test_iterator_double_end() {
-        let mut n = DList::new();
+        let mut n = LinkedList::new();
         assert_eq!(n.iter().next(), None);
         n.push_front(4);
         n.push_front(5);
@@ -1196,7 +1200,7 @@ mod tests {
         for (i, elt) in m.iter().rev().enumerate() {
             assert_eq!((6 - i) as i32, *elt);
         }
-        let mut n = DList::new();
+        let mut n = LinkedList::new();
         assert_eq!(n.iter().rev().next(), None);
         n.push_front(4);
         let mut it = n.iter().rev();
@@ -1215,7 +1219,7 @@ mod tests {
             len -= 1;
         }
         assert_eq!(len, 0);
-        let mut n = DList::new();
+        let mut n = LinkedList::new();
         assert!(n.iter_mut().next().is_none());
         n.push_front(4);
         n.push_back(5);
@@ -1229,7 +1233,7 @@ mod tests {
 
     #[test]
     fn test_iterator_mut_double_end() {
-        let mut n = DList::new();
+        let mut n = LinkedList::new();
         assert!(n.iter_mut().next_back().is_none());
         n.push_front(4);
         n.push_front(5);
@@ -1278,7 +1282,7 @@ mod tests {
         for (i, elt) in m.iter_mut().rev().enumerate() {
             assert_eq!((6 - i) as i32, *elt);
         }
-        let mut n = DList::new();
+        let mut n = LinkedList::new();
         assert!(n.iter_mut().rev().next().is_none());
         n.push_front(4);
         let mut it = n.iter_mut().rev();
@@ -1313,8 +1317,8 @@ mod tests {
 
     #[test]
     fn test_hash() {
-      let mut x = DList::new();
-      let mut y = DList::new();
+      let mut x = LinkedList::new();
+      let mut y = LinkedList::new();
 
       assert!(hash::hash::<_, SipHasher>(&x) == hash::hash::<_, SipHasher>(&y));
 
@@ -1382,16 +1386,16 @@ mod tests {
 
     #[test]
     fn test_show() {
-        let list: DList<_> = (0..10).collect();
-        assert_eq!(format!("{:?}", list), "DList [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
+        let list: LinkedList<_> = (0..10).collect();
+        assert_eq!(format!("{:?}", list), "LinkedList [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
 
-        let list: DList<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
-        assert_eq!(format!("{:?}", list), "DList [\"just\", \"one\", \"test\", \"more\"]");
+        let list: LinkedList<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
+        assert_eq!(format!("{:?}", list), "LinkedList [\"just\", \"one\", \"test\", \"more\"]");
     }
 
     #[cfg(test)]
     fn fuzz_test(sz: i32) {
-        let mut m: DList<_> = DList::new();
+        let mut m: LinkedList<_> = LinkedList::new();
         let mut v = vec![];
         for i in 0..sz {
             check_links(&m);
@@ -1432,13 +1436,13 @@ mod tests {
     fn bench_collect_into(b: &mut test::Bencher) {
         let v = &[0; 64];
         b.iter(|| {
-            let _: DList<_> = v.iter().cloned().collect();
+            let _: LinkedList<_> = v.iter().cloned().collect();
         })
     }
 
     #[bench]
     fn bench_push_front(b: &mut test::Bencher) {
-        let mut m: DList<_> = DList::new();
+        let mut m: LinkedList<_> = LinkedList::new();
         b.iter(|| {
             m.push_front(0);
         })
@@ -1446,7 +1450,7 @@ mod tests {
 
     #[bench]
     fn bench_push_back(b: &mut test::Bencher) {
-        let mut m: DList<_> = DList::new();
+        let mut m: LinkedList<_> = LinkedList::new();
         b.iter(|| {
             m.push_back(0);
         })
@@ -1454,7 +1458,7 @@ mod tests {
 
     #[bench]
     fn bench_push_back_pop_back(b: &mut test::Bencher) {
-        let mut m: DList<_> = DList::new();
+        let mut m: LinkedList<_> = LinkedList::new();
         b.iter(|| {
             m.push_back(0);
             m.pop_back();
@@ -1463,7 +1467,7 @@ mod tests {
 
     #[bench]
     fn bench_push_front_pop_front(b: &mut test::Bencher) {
-        let mut m: DList<_> = DList::new();
+        let mut m: LinkedList<_> = LinkedList::new();
         b.iter(|| {
             m.push_front(0);
             m.pop_front();
@@ -1473,7 +1477,7 @@ mod tests {
     #[bench]
     fn bench_iter(b: &mut test::Bencher) {
         let v = &[0; 128];
-        let m: DList<_> = v.iter().cloned().collect();
+        let m: LinkedList<_> = v.iter().cloned().collect();
         b.iter(|| {
             assert!(m.iter().count() == 128);
         })
@@ -1481,7 +1485,7 @@ mod tests {
     #[bench]
     fn bench_iter_mut(b: &mut test::Bencher) {
         let v = &[0; 128];
-        let mut m: DList<_> = v.iter().cloned().collect();
+        let mut m: LinkedList<_> = v.iter().cloned().collect();
         b.iter(|| {
             assert!(m.iter_mut().count() == 128);
         })
@@ -1489,7 +1493,7 @@ mod tests {
     #[bench]
     fn bench_iter_rev(b: &mut test::Bencher) {
         let v = &[0; 128];
-        let m: DList<_> = v.iter().cloned().collect();
+        let m: LinkedList<_> = v.iter().cloned().collect();
         b.iter(|| {
             assert!(m.iter().rev().count() == 128);
         })
@@ -1497,7 +1501,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/ring_buf.rs b/src/libcollections/vec_deque.rs
index 6dcdb21f800..76b2d5b968e 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
@@ -36,12 +36,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.
@@ -55,21 +60,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 {
@@ -83,12 +88,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] {
@@ -149,16 +154,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");
@@ -175,7 +180,7 @@ impl<T> RingBuf<T> {
             heap::EMPTY as *mut T
         };
 
-        RingBuf {
+        VecDeque {
             tail: 0,
             head: 0,
             cap: cap,
@@ -183,14 +188,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);
@@ -206,14 +211,14 @@ impl<T> RingBuf<T> {
         }
     }
 
-    /// Retrieves an element in the `RingBuf` mutably by index.
+    /// Retrieves an element in the `VecDeque` mutably by index.
     ///
     /// # Examples
     ///
     /// ```rust
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf = RingBuf::new();
+    /// let mut buf = VecDeque::new();
     /// buf.push_back(3);
     /// buf.push_back(4);
     /// buf.push_back(5);
@@ -245,9 +250,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```rust
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf = RingBuf::new();
+    /// let mut buf = VecDeque::new();
     /// buf.push_back(3);
     /// buf.push_back(4);
     /// buf.push_back(5);
@@ -266,15 +271,15 @@ impl<T> RingBuf<T> {
         }
     }
 
-    /// Returns the number of elements the `RingBuf` can hold without
+    /// Returns the number of elements the `VecDeque` can hold without
     /// reallocating.
     ///
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let buf: RingBuf<i32> = RingBuf::with_capacity(10);
+    /// let buf: VecDeque<i32> = VecDeque::with_capacity(10);
     /// assert!(buf.capacity() >= 10);
     /// ```
     #[inline]
@@ -282,7 +287,7 @@ impl<T> RingBuf<T> {
     pub fn capacity(&self) -> usize { self.cap - 1 }
 
     /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
-    /// given `RingBuf`. Does nothing if the capacity is already sufficient.
+    /// given `VecDeque`. Does nothing if the capacity is already sufficient.
     ///
     /// Note that the allocator may give the collection more space than it requests. Therefore
     /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
@@ -295,9 +300,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf: RingBuf<i32> = vec![1].into_iter().collect();
+    /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
     /// buf.reserve_exact(10);
     /// assert!(buf.capacity() >= 11);
     /// ```
@@ -316,9 +321,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);
     /// ```
@@ -390,9 +395,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();
@@ -475,9 +480,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf = RingBuf::new();
+    /// let mut buf = VecDeque::new();
     /// buf.push_back(5);
     /// buf.push_back(10);
     /// buf.push_back(15);
@@ -498,9 +503,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```rust
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf = RingBuf::new();
+    /// let mut buf = VecDeque::new();
     /// buf.push_back(5);
     /// buf.push_back(3);
     /// buf.push_back(4);
@@ -521,9 +526,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);
@@ -553,7 +558,7 @@ impl<T> RingBuf<T> {
     }
 
     /// Returns a pair of slices which contain, in order, the contents of the
-    /// `RingBuf`.
+    /// `VecDeque`.
     #[inline]
     #[unstable(feature = "collections",
                reason = "matches collection reform specification, waiting for dust to settle")]
@@ -573,7 +578,7 @@ impl<T> RingBuf<T> {
     }
 
     /// Returns a pair of slices which contain, in order, the contents of the
-    /// `RingBuf`.
+    /// `VecDeque`.
     #[inline]
     #[unstable(feature = "collections",
                reason = "matches collection reform specification, waiting for dust to settle")]
@@ -596,14 +601,14 @@ impl<T> RingBuf<T> {
         }
     }
 
-    /// Returns the number of elements in the `RingBuf`.
+    /// Returns the number of elements in the `VecDeque`.
     ///
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut v = RingBuf::new();
+    /// let mut v = VecDeque::new();
     /// assert_eq!(v.len(), 0);
     /// v.push_back(1);
     /// assert_eq!(v.len(), 1);
@@ -616,9 +621,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut v = RingBuf::new();
+    /// let mut v = VecDeque::new();
     /// assert!(v.is_empty());
     /// v.push_front(1);
     /// assert!(!v.is_empty());
@@ -626,15 +631,15 @@ impl<T> RingBuf<T> {
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 
-    /// Creates a draining iterator that clears the `RingBuf` and iterates over
+    /// Creates a draining iterator that clears the `VecDeque` and iterates over
     /// the removed items from start to end.
     ///
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut v = RingBuf::new();
+    /// let mut v = VecDeque::new();
     /// v.push_back(1);
     /// assert_eq!(v.drain().next(), Some(1));
     /// assert!(v.is_empty());
@@ -653,9 +658,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut v = RingBuf::new();
+    /// let mut v = VecDeque::new();
     /// v.push_back(1);
     /// v.clear();
     /// assert!(v.is_empty());
@@ -672,9 +677,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut d = RingBuf::new();
+    /// let mut d = VecDeque::new();
     /// assert_eq!(d.front(), None);
     ///
     /// d.push_back(1);
@@ -692,9 +697,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut d = RingBuf::new();
+    /// let mut d = VecDeque::new();
     /// assert_eq!(d.front_mut(), None);
     ///
     /// d.push_back(1);
@@ -716,9 +721,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut d = RingBuf::new();
+    /// let mut d = VecDeque::new();
     /// assert_eq!(d.back(), None);
     ///
     /// d.push_back(1);
@@ -736,9 +741,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut d = RingBuf::new();
+    /// let mut d = VecDeque::new();
     /// assert_eq!(d.back(), None);
     ///
     /// d.push_back(1);
@@ -761,9 +766,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut d = RingBuf::new();
+    /// let mut d = VecDeque::new();
     /// d.push_back(1);
     /// d.push_back(2);
     ///
@@ -787,9 +792,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut d = RingBuf::new();
+    /// let mut d = VecDeque::new();
     /// d.push_front(1);
     /// d.push_front(2);
     /// assert_eq!(d.front(), Some(&2));
@@ -811,9 +816,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```rust
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf = RingBuf::new();
+    /// let mut buf = VecDeque::new();
     /// buf.push_back(1);
     /// buf.push_back(3);
     /// assert_eq!(3, *buf.back().unwrap());
@@ -836,9 +841,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```rust
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf = RingBuf::new();
+    /// let mut buf = VecDeque::new();
     /// assert_eq!(buf.pop_back(), None);
     /// buf.push_back(1);
     /// buf.push_back(3);
@@ -870,9 +875,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf = RingBuf::new();
+    /// let mut buf = VecDeque::new();
     /// assert_eq!(buf.swap_back_remove(0), None);
     /// buf.push_back(5);
     /// buf.push_back(99);
@@ -903,9 +908,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf = RingBuf::new();
+    /// let mut buf = VecDeque::new();
     /// assert_eq!(buf.swap_front_remove(0), None);
     /// buf.push_back(15);
     /// buf.push_back(5);
@@ -936,9 +941,9 @@ impl<T> RingBuf<T> {
     ///
     /// # Examples
     /// ```rust
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf = RingBuf::new();
+    /// let mut buf = VecDeque::new();
     /// buf.push_back(10);
     /// buf.push_back(12);
     /// buf.insert(1,11);
@@ -1138,9 +1143,9 @@ impl<T> RingBuf<T> {
     ///
     /// # Examples
     /// ```rust
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf = RingBuf::new();
+    /// let mut buf = VecDeque::new();
     /// buf.push_back(5);
     /// buf.push_back(10);
     /// buf.push_back(12);
@@ -1309,9 +1314,9 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf: RingBuf<_> = vec![1,2,3].into_iter().collect();
+    /// let mut buf: VecDeque<_> = vec![1,2,3].into_iter().collect();
     /// let buf2 = buf.split_off(1);
     /// // buf = [1], buf2 = [2, 3]
     /// assert_eq!(buf.len(), 1);
@@ -1325,7 +1330,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();
@@ -1371,10 +1376,10 @@ impl<T> RingBuf<T> {
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf: RingBuf<_> = vec![1, 2, 3].into_iter().collect();
-    /// let mut buf2: RingBuf<_> = vec![4, 5, 6].into_iter().collect();
+    /// let mut buf: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
+    /// let mut buf2: VecDeque<_> = vec![4, 5, 6].into_iter().collect();
     /// buf.append(&mut buf2);
     /// assert_eq!(buf.len(), 6);
     /// assert_eq!(buf2.len(), 0);
@@ -1388,16 +1393,16 @@ impl<T> RingBuf<T> {
     }
 }
 
-impl<T: Clone> RingBuf<T> {
+impl<T: Clone> VecDeque<T> {
     /// Modifies the ringbuf in-place so that `len()` is equal to new_len,
     /// either by removing excess elements or by appending copies of a value to the back.
     ///
     /// # Examples
     ///
     /// ```
-    /// use std::collections::RingBuf;
+    /// use std::collections::VecDeque;
     ///
-    /// let mut buf = RingBuf::new();
+    /// let mut buf = VecDeque::new();
     /// buf.push_back(5);
     /// buf.push_back(10);
     /// buf.push_back(15);
@@ -1434,7 +1439,7 @@ fn count(tail: usize, head: usize, size: usize) -> usize {
     (head - tail) & (size - 1)
 }
 
-/// `RingBuf` iterator.
+/// `VecDeque` iterator.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Iter<'a, T:'a> {
     ring: &'a [T],
@@ -1511,7 +1516,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,
@@ -1563,10 +1568,10 @@ impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
 
-/// A by-value RingBuf iterator
+/// A by-value VecDeque iterator
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IntoIter<T> {
-    inner: RingBuf<T>,
+    inner: VecDeque<T>,
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1596,11 +1601,11 @@ impl<T> DoubleEndedIterator for IntoIter<T> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ExactSizeIterator for IntoIter<T> {}
 
-/// A draining RingBuf iterator
+/// A draining VecDeque iterator
 #[unstable(feature = "collections",
            reason = "matches collection reform specification, waiting for dust to settle")]
 pub struct Drain<'a, T: 'a> {
-    inner: &'a mut RingBuf<T>,
+    inner: &'a mut VecDeque<T>,
 }
 
 #[unsafe_destructor]
@@ -1641,33 +1646,33 @@ impl<'a, T: 'a> DoubleEndedIterator for Drain<'a, T> {
 impl<'a, T: 'a> ExactSizeIterator for Drain<'a, T> {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A: PartialEq> PartialEq for RingBuf<A> {
-    fn eq(&self, other: &RingBuf<A>) -> bool {
+impl<A: PartialEq> PartialEq for VecDeque<A> {
+    fn eq(&self, other: &VecDeque<A>) -> bool {
         self.len() == other.len() &&
             self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A: Eq> Eq for RingBuf<A> {}
+impl<A: Eq> Eq for VecDeque<A> {}
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A: PartialOrd> PartialOrd for RingBuf<A> {
-    fn partial_cmp(&self, other: &RingBuf<A>) -> Option<Ordering> {
+impl<A: PartialOrd> PartialOrd for VecDeque<A> {
+    fn partial_cmp(&self, other: &VecDeque<A>) -> Option<Ordering> {
         iter::order::partial_cmp(self.iter(), other.iter())
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A: Ord> Ord for RingBuf<A> {
+impl<A: Ord> Ord for VecDeque<A> {
     #[inline]
-    fn cmp(&self, other: &RingBuf<A>) -> Ordering {
+    fn cmp(&self, other: &VecDeque<A>) -> Ordering {
         iter::order::cmp(self.iter(), other.iter())
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<S: Writer + Hasher, A: Hash<S>> Hash<S> for RingBuf<A> {
+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 {
@@ -1677,7 +1682,7 @@ impl<S: Writer + Hasher, A: Hash<S>> Hash<S> 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]
@@ -1687,7 +1692,7 @@ impl<A> Index<usize> for RingBuf<A> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A> IndexMut<usize> for RingBuf<A> {
+impl<A> IndexMut<usize> for VecDeque<A> {
     #[inline]
     fn index_mut(&mut self, i: &usize) -> &mut A {
         self.get_mut(*i).expect("Out of bounds access")
@@ -1695,17 +1700,17 @@ 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: Iterator<Item=A>>(iterator: T) -> VecDeque<A> {
         let (lower, _) = iterator.size_hint();
-        let mut deq = RingBuf::with_capacity(lower);
+        let mut deq = VecDeque::with_capacity(lower);
         deq.extend(iterator);
         deq
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<T> IntoIterator for RingBuf<T> {
+impl<T> IntoIterator for VecDeque<T> {
     type Item = T;
     type IntoIter = IntoIter<T>;
 
@@ -1715,7 +1720,7 @@ impl<T> IntoIterator for RingBuf<T> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, T> IntoIterator for &'a RingBuf<T> {
+impl<'a, T> IntoIterator for &'a VecDeque<T> {
     type Item = &'a T;
     type IntoIter = Iter<'a, T>;
 
@@ -1725,7 +1730,7 @@ impl<'a, T> IntoIterator for &'a RingBuf<T> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<'a, T> IntoIterator for &'a mut RingBuf<T> {
+impl<'a, T> IntoIterator for &'a mut VecDeque<T> {
     type Item = &'a mut T;
     type IntoIter = IterMut<'a, T>;
 
@@ -1735,7 +1740,7 @@ impl<'a, T> IntoIterator for &'a mut RingBuf<T> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<A> Extend<A> for RingBuf<A> {
+impl<A> Extend<A> for VecDeque<A> {
     fn extend<T: Iterator<Item=A>>(&mut self, iterator: T) {
         for elt in iterator {
             self.push_back(elt);
@@ -1744,9 +1749,9 @@ impl<A> Extend<A> for RingBuf<A> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-impl<T: fmt::Debug> fmt::Debug for RingBuf<T> {
+impl<T: fmt::Debug> fmt::Debug for VecDeque<T> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        try!(write!(f, "RingBuf ["));
+        try!(write!(f, "VecDeque ["));
 
         for (i, e) in self.iter().enumerate() {
             if i != 0 { try!(write!(f, ", ")); }
@@ -1768,12 +1773,12 @@ mod tests {
     use test::Bencher;
     use test;
 
-    use super::RingBuf;
+    use super::VecDeque;
 
     #[test]
     #[allow(deprecated)]
     fn test_simple() {
-        let mut d = RingBuf::new();
+        let mut d = VecDeque::new();
         assert_eq!(d.len(), 0);
         d.push_front(17);
         d.push_front(42);
@@ -1812,7 +1817,7 @@ mod tests {
 
     #[cfg(test)]
     fn test_parameterized<T:Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) {
-        let mut deq = RingBuf::new();
+        let mut deq = VecDeque::new();
         assert_eq!(deq.len(), 0);
         deq.push_front(a.clone());
         deq.push_front(b.clone());
@@ -1843,7 +1848,7 @@ mod tests {
 
     #[test]
     fn test_push_front_grow() {
-        let mut deq = RingBuf::new();
+        let mut deq = VecDeque::new();
         for i in 0..66 {
             deq.push_front(i);
         }
@@ -1853,7 +1858,7 @@ mod tests {
             assert_eq!(deq[i], 65 - i);
         }
 
-        let mut deq = RingBuf::new();
+        let mut deq = VecDeque::new();
         for i in 0..66 {
             deq.push_back(i);
         }
@@ -1865,7 +1870,7 @@ mod tests {
 
     #[test]
     fn test_index() {
-        let mut deq = RingBuf::new();
+        let mut deq = VecDeque::new();
         for i in 1..4 {
             deq.push_front(i);
         }
@@ -1875,7 +1880,7 @@ mod tests {
     #[test]
     #[should_fail]
     fn test_index_out_of_bounds() {
-        let mut deq = RingBuf::new();
+        let mut deq = VecDeque::new();
         for i in 1..4 {
             deq.push_front(i);
         }
@@ -1885,14 +1890,14 @@ mod tests {
     #[bench]
     fn bench_new(b: &mut test::Bencher) {
         b.iter(|| {
-            let ring: RingBuf<i32> = RingBuf::new();
+            let ring: VecDeque<i32> = VecDeque::new();
             test::black_box(ring);
         })
     }
 
     #[bench]
     fn bench_push_back_100(b: &mut test::Bencher) {
-        let mut deq = RingBuf::with_capacity(101);
+        let mut deq = VecDeque::with_capacity(101);
         b.iter(|| {
             for i in 0..100 {
                 deq.push_back(i);
@@ -1904,7 +1909,7 @@ mod tests {
 
     #[bench]
     fn bench_push_front_100(b: &mut test::Bencher) {
-        let mut deq = RingBuf::with_capacity(101);
+        let mut deq = VecDeque::with_capacity(101);
         b.iter(|| {
             for i in 0..100 {
                 deq.push_front(i);
@@ -1916,7 +1921,7 @@ mod tests {
 
     #[bench]
     fn bench_pop_back_100(b: &mut test::Bencher) {
-        let mut deq= RingBuf::<i32>::with_capacity(101);
+        let mut deq= VecDeque::<i32>::with_capacity(101);
 
         b.iter(|| {
             deq.head = 100;
@@ -1929,7 +1934,7 @@ mod tests {
 
     #[bench]
     fn bench_pop_front_100(b: &mut test::Bencher) {
-        let mut deq = RingBuf::<i32>::with_capacity(101);
+        let mut deq = VecDeque::<i32>::with_capacity(101);
 
         b.iter(|| {
             deq.head = 100;
@@ -1943,7 +1948,7 @@ mod tests {
     #[bench]
     fn bench_grow_1025(b: &mut test::Bencher) {
         b.iter(|| {
-            let mut deq = RingBuf::new();
+            let mut deq = VecDeque::new();
             for i in 0..1025 {
                 deq.push_front(i);
             }
@@ -1953,7 +1958,7 @@ mod tests {
 
     #[bench]
     fn bench_iter_1000(b: &mut test::Bencher) {
-        let ring: RingBuf<_> = (0..1000).collect();
+        let ring: VecDeque<_> = (0..1000).collect();
 
         b.iter(|| {
             let mut sum = 0;
@@ -1966,7 +1971,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;
@@ -2027,17 +2032,17 @@ mod tests {
 
     #[test]
     fn test_with_capacity() {
-        let mut d = RingBuf::with_capacity(0);
+        let mut d = VecDeque::with_capacity(0);
         d.push_back(1);
         assert_eq!(d.len(), 1);
-        let mut d = RingBuf::with_capacity(50);
+        let mut d = VecDeque::with_capacity(50);
         d.push_back(1);
         assert_eq!(d.len(), 1);
     }
 
     #[test]
     fn test_with_capacity_non_power_two() {
-        let mut d3 = RingBuf::with_capacity(3);
+        let mut d3 = VecDeque::with_capacity(3);
         d3.push_back(1);
 
         // X = None, | = lo
@@ -2062,7 +2067,7 @@ mod tests {
 
         d3.push_back(15);
         // There used to be a bug here about how the
-        // RingBuf made growth assumptions about the
+        // VecDeque made growth assumptions about the
         // underlying Vec which didn't hold and lead
         // to corruption.
         // (Vec grows to next power of two)
@@ -2078,7 +2083,7 @@ mod tests {
 
     #[test]
     fn test_reserve_exact() {
-        let mut d = RingBuf::new();
+        let mut d = VecDeque::new();
         d.push_back(0);
         d.reserve_exact(50);
         assert!(d.capacity() >= 51);
@@ -2086,7 +2091,7 @@ mod tests {
 
     #[test]
     fn test_reserve() {
-        let mut d = RingBuf::new();
+        let mut d = VecDeque::new();
         d.push_back(0);
         d.reserve(50);
         assert!(d.capacity() >= 51);
@@ -2094,7 +2099,7 @@ mod tests {
 
     #[test]
     fn test_swap() {
-        let mut d: RingBuf<_> = (0..5).collect();
+        let mut d: VecDeque<_> = (0..5).collect();
         d.pop_front();
         d.swap(0, 3);
         assert_eq!(d.iter().cloned().collect::<Vec<_>>(), vec!(4, 2, 3, 1));
@@ -2102,7 +2107,7 @@ mod tests {
 
     #[test]
     fn test_iter() {
-        let mut d = RingBuf::new();
+        let mut d = VecDeque::new();
         assert_eq!(d.iter().next(), None);
         assert_eq!(d.iter().size_hint(), (0, Some(0)));
 
@@ -2134,7 +2139,7 @@ mod tests {
 
     #[test]
     fn test_rev_iter() {
-        let mut d = RingBuf::new();
+        let mut d = VecDeque::new();
         assert_eq!(d.iter().rev().next(), None);
 
         for i in 0..5 {
@@ -2154,7 +2159,7 @@ mod tests {
 
     #[test]
     fn test_mut_rev_iter_wrap() {
-        let mut d = RingBuf::with_capacity(3);
+        let mut d = VecDeque::with_capacity(3);
         assert!(d.iter_mut().rev().next().is_none());
 
         d.push_back(1);
@@ -2169,7 +2174,7 @@ mod tests {
 
     #[test]
     fn test_mut_iter() {
-        let mut d = RingBuf::new();
+        let mut d = VecDeque::new();
         assert!(d.iter_mut().next().is_none());
 
         for i in 0..3 {
@@ -2192,7 +2197,7 @@ mod tests {
 
     #[test]
     fn test_mut_rev_iter() {
-        let mut d = RingBuf::new();
+        let mut d = VecDeque::new();
         assert!(d.iter_mut().rev().next().is_none());
 
         for i in 0..3 {
@@ -2218,7 +2223,7 @@ mod tests {
 
         // Empty iter
         {
-            let d: RingBuf<i32> = RingBuf::new();
+            let d: VecDeque<i32> = VecDeque::new();
             let mut iter = d.into_iter();
 
             assert_eq!(iter.size_hint(), (0, Some(0)));
@@ -2228,7 +2233,7 @@ mod tests {
 
         // simple iter
         {
-            let mut d = RingBuf::new();
+            let mut d = VecDeque::new();
             for i in 0..5 {
                 d.push_back(i);
             }
@@ -2239,7 +2244,7 @@ mod tests {
 
         // wrapped iter
         {
-            let mut d = RingBuf::new();
+            let mut d = VecDeque::new();
             for i in 0..5 {
                 d.push_back(i);
             }
@@ -2253,7 +2258,7 @@ mod tests {
 
         // partially used
         {
-            let mut d = RingBuf::new();
+            let mut d = VecDeque::new();
             for i in 0..5 {
                 d.push_back(i);
             }
@@ -2277,7 +2282,7 @@ mod tests {
 
         // Empty iter
         {
-            let mut d: RingBuf<i32> = RingBuf::new();
+            let mut d: VecDeque<i32> = VecDeque::new();
 
             {
                 let mut iter = d.drain();
@@ -2292,7 +2297,7 @@ mod tests {
 
         // simple iter
         {
-            let mut d = RingBuf::new();
+            let mut d = VecDeque::new();
             for i in 0..5 {
                 d.push_back(i);
             }
@@ -2303,7 +2308,7 @@ mod tests {
 
         // wrapped iter
         {
-            let mut d = RingBuf::new();
+            let mut d = VecDeque::new();
             for i in 0..5 {
                 d.push_back(i);
             }
@@ -2317,7 +2322,7 @@ mod tests {
 
         // partially used
         {
-            let mut d: RingBuf<_> = RingBuf::new();
+            let mut d: VecDeque<_> = VecDeque::new();
             for i in 0..5 {
                 d.push_back(i);
             }
@@ -2343,12 +2348,12 @@ mod tests {
     fn test_from_iter() {
         use core::iter;
         let v = vec!(1,2,3,4,5,6,7);
-        let deq: RingBuf<_> = v.iter().cloned().collect();
+        let deq: VecDeque<_> = v.iter().cloned().collect();
         let u: Vec<_> = deq.iter().cloned().collect();
         assert_eq!(u, v);
 
         let seq = iter::count(0, 2).take(256);
-        let deq: RingBuf<_> = seq.collect();
+        let deq: VecDeque<_> = seq.collect();
         for (i, &x) in deq.iter().enumerate() {
             assert_eq!(2*i, x);
         }
@@ -2357,7 +2362,7 @@ mod tests {
 
     #[test]
     fn test_clone() {
-        let mut d = RingBuf::new();
+        let mut d = VecDeque::new();
         d.push_front(17);
         d.push_front(42);
         d.push_back(137);
@@ -2374,13 +2379,13 @@ mod tests {
 
     #[test]
     fn test_eq() {
-        let mut d = RingBuf::new();
-        assert!(d == RingBuf::with_capacity(0));
+        let mut d = VecDeque::new();
+        assert!(d == VecDeque::with_capacity(0));
         d.push_front(137);
         d.push_front(17);
         d.push_front(42);
         d.push_back(137);
-        let mut e = RingBuf::with_capacity(0);
+        let mut e = VecDeque::with_capacity(0);
         e.push_back(42);
         e.push_back(17);
         e.push_back(137);
@@ -2390,13 +2395,13 @@ mod tests {
         e.push_back(0);
         assert!(e != d);
         e.clear();
-        assert!(e == RingBuf::new());
+        assert!(e == VecDeque::new());
     }
 
     #[test]
     fn test_hash() {
-      let mut x = RingBuf::new();
-      let mut y = RingBuf::new();
+      let mut x = VecDeque::new();
+      let mut y = VecDeque::new();
 
       x.push_back(1);
       x.push_back(2);
@@ -2413,8 +2418,8 @@ mod tests {
 
     #[test]
     fn test_ord() {
-        let x = RingBuf::new();
-        let mut y = RingBuf::new();
+        let x = VecDeque::new();
+        let mut y = VecDeque::new();
         y.push_back(1);
         y.push_back(2);
         y.push_back(3);
@@ -2426,13 +2431,13 @@ mod tests {
 
     #[test]
     fn test_show() {
-        let ringbuf: RingBuf<_> = (0..10).collect();
-        assert_eq!(format!("{:?}", ringbuf), "RingBuf [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
+        let ringbuf: VecDeque<_> = (0..10).collect();
+        assert_eq!(format!("{:?}", ringbuf), "VecDeque [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
 
-        let ringbuf: RingBuf<_> = vec!["just", "one", "test", "more"].iter()
+        let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"].iter()
                                                                         .cloned()
                                                                         .collect();
-        assert_eq!(format!("{:?}", ringbuf), "RingBuf [\"just\", \"one\", \"test\", \"more\"]");
+        assert_eq!(format!("{:?}", ringbuf), "VecDeque [\"just\", \"one\", \"test\", \"more\"]");
     }
 
     #[test]
@@ -2445,7 +2450,7 @@ mod tests {
             }
         }
 
-        let mut ring = RingBuf::new();
+        let mut ring = VecDeque::new();
         ring.push_back(Elem);
         ring.push_front(Elem);
         ring.push_back(Elem);
@@ -2465,7 +2470,7 @@ mod tests {
             }
         }
 
-        let mut ring = RingBuf::new();
+        let mut ring = VecDeque::new();
         ring.push_back(Elem);
         ring.push_front(Elem);
         ring.push_back(Elem);
@@ -2489,7 +2494,7 @@ mod tests {
             }
         }
 
-        let mut ring = RingBuf::new();
+        let mut ring = VecDeque::new();
         ring.push_back(Elem);
         ring.push_front(Elem);
         ring.push_back(Elem);
@@ -2505,7 +2510,7 @@ mod tests {
     fn test_reserve_grow() {
         // test growth path A
         // [T o o H] -> [T o o H . . . . ]
-        let mut ring = RingBuf::with_capacity(4);
+        let mut ring = VecDeque::with_capacity(4);
         for i in 0..3 {
             ring.push_back(i);
         }
@@ -2516,7 +2521,7 @@ mod tests {
 
         // test growth path B
         // [H T o o] -> [. T o o H . . . ]
-        let mut ring = RingBuf::with_capacity(4);
+        let mut ring = VecDeque::with_capacity(4);
         for i in 0..1 {
             ring.push_back(i);
             assert_eq!(ring.pop_front(), Some(i));
@@ -2531,7 +2536,7 @@ mod tests {
 
         // test growth path C
         // [o o H T] -> [o o H . . . . T ]
-        let mut ring = RingBuf::with_capacity(4);
+        let mut ring = VecDeque::with_capacity(4);
         for i in 0..3 {
             ring.push_back(i);
             assert_eq!(ring.pop_front(), Some(i));
@@ -2547,7 +2552,7 @@ mod tests {
 
     #[test]
     fn test_get() {
-        let mut ring = RingBuf::new();
+        let mut ring = VecDeque::new();
         ring.push_back(0);
         assert_eq!(ring.get(0), Some(&0));
         assert_eq!(ring.get(1), None);
@@ -2579,7 +2584,7 @@ mod tests {
 
     #[test]
     fn test_get_mut() {
-        let mut ring = RingBuf::new();
+        let mut ring = VecDeque::new();
         for i in 0..3 {
             ring.push_back(i);
         }
@@ -2605,7 +2610,7 @@ mod tests {
         fn test(back: bool) {
             // This test checks that every single combination of tail position and length is tested.
             // Capacity 15 should be large enough to cover every case.
-            let mut tester = RingBuf::with_capacity(15);
+            let mut tester = VecDeque::with_capacity(15);
             let usable_cap = tester.capacity();
             let final_len = usable_cap / 2;
 
@@ -2649,7 +2654,7 @@ mod tests {
         // This test checks that every single combination of tail position, length, and
         // insertion position is tested. Capacity 15 should be large enough to cover every case.
 
-        let mut tester = RingBuf::with_capacity(15);
+        let mut tester = VecDeque::with_capacity(15);
         // can't guarantee we got 15, so have to get what we got.
         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
         // this test isn't covering what it wants to
@@ -2683,7 +2688,7 @@ mod tests {
         // This test checks that every single combination of tail position, length, and
         // removal position is tested. Capacity 15 should be large enough to cover every case.
 
-        let mut tester = RingBuf::with_capacity(15);
+        let mut tester = VecDeque::with_capacity(15);
         // can't guarantee we got 15, so have to get what we got.
         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
         // this test isn't covering what it wants to
@@ -2720,7 +2725,7 @@ mod tests {
         // This test checks that every single combination of head and tail position,
         // is tested. Capacity 15 should be large enough to cover every case.
 
-        let mut tester = RingBuf::with_capacity(15);
+        let mut tester = VecDeque::with_capacity(15);
         // can't guarantee we got 15, so have to get what we got.
         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
         // this test isn't covering what it wants to
@@ -2749,7 +2754,7 @@ mod tests {
 
     #[test]
     fn test_front() {
-        let mut ring = RingBuf::new();
+        let mut ring = VecDeque::new();
         ring.push_back(10);
         ring.push_back(20);
         assert_eq!(ring.front(), Some(&10));
@@ -2761,7 +2766,7 @@ mod tests {
 
     #[test]
     fn test_as_slices() {
-        let mut ring: RingBuf<i32> = RingBuf::with_capacity(127);
+        let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
         let cap = ring.capacity() as i32;
         let first = cap/2;
         let last  = cap - first;
@@ -2789,7 +2794,7 @@ mod tests {
 
     #[test]
     fn test_as_mut_slices() {
-        let mut ring: RingBuf<i32> = RingBuf::with_capacity(127);
+        let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
         let cap = ring.capacity() as i32;
         let first = cap/2;
         let last  = cap - first;
@@ -2820,7 +2825,7 @@ mod tests {
         // This test checks that every single combination of tail position, length, and
         // split position is tested. Capacity 15 should be large enough to cover every case.
 
-        let mut tester = RingBuf::with_capacity(15);
+        let mut tester = VecDeque::with_capacity(15);
         // can't guarantee we got 15, so have to get what we got.
         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
         // this test isn't covering what it wants to
@@ -2855,8 +2860,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/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/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 f81edca8371..ac56cc37506 100644
--- a/src/libserialize/collection_impls.rs
+++ b/src/libserialize/collection_impls.rs
@@ -16,12 +16,12 @@ use std::hash::{Hash, Hasher};
 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() {
@@ -32,10 +32,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))));
             }
@@ -44,7 +44,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() {
@@ -55,10 +55,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/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/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/test/bench/core-set.rs b/src/test/bench/core-set.rs
index 1d440c4540c..8bddd655e23 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::collections::hash_map::Hasher;
 use std::hash::Hash;
@@ -53,7 +53,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) }
@@ -222,7 +222,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);
     }
 }
author	Aaron Turon <aturon@mozilla.com>	2015-02-17 23:44:55 -0800
committer	Alexis <a.beingessner@gmail.com>	2015-02-18 14:01:46 -0500
commit	5fa9de16df87ab844452821acff1b6c74e948327 (patch)
tree	c4f4c06960f557277c07457b14bf61f8861ba8e2
parent	dfc5c0f1e8799f47f9033bdcc8a7cd8a217620a5 (diff)
download	rust-5fa9de16df87ab844452821acff1b6c74e948327.tar.gz rust-5fa9de16df87ab844452821acff1b6c74e948327.zip