use core::ops::Index;
use core::slice::{Iter, IterMut};
use core::{u8, u32, uint};
+use bitv_set; //so meta
use Vec;
-type Blocks<'a> = Cloned<Iter<'a, u32>>;
-type MutBlocks<'a> = IterMut<'a, u32>;
+type Blocks<'a> = Cloned<slice::Iter<'a, u32>>;
+type MutBlocks<'a> = slice::IterMut<'a, u32>;
type MatchWords<'a> = Chain<Enumerate<Blocks<'a>>, Skip<Take<Enumerate<Repeat<u32>>>>>;
fn reverse_bits(byte: u8) -> u8 {
/// println!("{}", bv.to_string());
/// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
/// ```
+#[stable]
pub struct Bitv {
/// Internal representation of the bit vector
storage: Vec<u32>,
// FIXME(Gankro): NopeNopeNopeNopeNope (wait for IndexGet to be a thing)
impl Index<uint,bool> for Bitv {
#[inline]
- fn index<'a>(&'a self, i: &uint) -> &'a bool {
+ fn index(&self, i: &uint) -> &bool {
if self.get(*i).expect("index out of bounds") {
&TRUE
} else {
/// use std::collections::Bitv;
/// let mut bv = Bitv::new();
/// ```
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn new() -> Bitv {
Bitv { storage: Vec::new(), nbits: 0 }
}
pub fn from_elem(nbits: uint, bit: bool) -> Bitv {
let nblocks = blocks_for_bits(nbits);
let mut bitv = Bitv {
- storage: Vec::from_elem(nblocks, if bit { !0u32 } else { 0u32 }),
+ storage: repeat(if bit { !0u32 } else { 0u32 }).take(nblocks).collect(),
nbits: nbits
};
bitv.fix_last_block();
///
/// It is important to note that this function does not specify the
/// *length* of the returned bitvector, but only the *capacity*.
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn with_capacity(nbits: uint) -> Bitv {
Bitv {
storage: Vec::with_capacity(blocks_for_bits(nbits)),
/// assert_eq!(bv[1], true);
/// ```
#[inline]
- #[unstable = "panic semantics are likely to change in the future"]
+ #[stable]
pub fn get(&self, i: uint) -> Option<bool> {
if i >= self.nbits {
return None;
/// assert_eq!(bv.iter().filter(|x| *x).count(), 7);
/// ```
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
- pub fn iter<'a>(&'a self) -> Bits<'a> {
- Bits { bitv: self, next_idx: 0, end_idx: self.nbits }
+ #[stable]
+ pub fn iter(&self) -> Iter {
+ Iter { bitv: self, next_idx: 0, end_idx: self.nbits }
}
/// Returns `true` if all bits are 0.
let len = self.nbits/8 +
if self.nbits % 8 == 0 { 0 } else { 1 };
- Vec::from_fn(len, |i|
+ range(0, len).map(|i|
bit(self, i, 0) |
bit(self, i, 1) |
bit(self, i, 2) |
bit(self, i, 5) |
bit(self, i, 6) |
bit(self, i, 7)
- )
+ ).collect()
}
/// Deprecated: Use `iter().collect()`.
/// bv.truncate(2);
/// assert!(bv.eq_vec(&[false, true]));
/// ```
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn truncate(&mut self, len: uint) {
if len < self.len() {
self.nbits = len;
/// assert_eq!(bv.len(), 3);
/// assert!(bv.capacity() >= 13);
/// ```
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn reserve(&mut self, additional: uint) {
let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
let storage_len = self.storage.len();
/// assert_eq!(bv.len(), 3);
/// assert!(bv.capacity() >= 13);
/// ```
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn reserve_exact(&mut self, additional: uint) {
let desired_cap = self.len().checked_add(additional).expect("capacity overflow");
let storage_len = self.storage.len();
/// assert!(bv.capacity() >= 10);
/// ```
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn capacity(&self) -> uint {
self.storage.capacity().checked_mul(u32::BITS).unwrap_or(uint::MAX)
}
// Allocate new words, if needed
if new_nblocks > self.storage.len() {
let to_add = new_nblocks - self.storage.len();
- self.storage.grow(to_add, full_value);
+ self.storage.extend(repeat(full_value).take(to_add));
}
// Adjust internal bit count
/// assert_eq!(bv.pop(), Some(false));
/// assert_eq!(bv.len(), 6);
/// ```
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn pop(&mut self) -> Option<bool> {
if self.is_empty() {
None
/// bv.push(false);
/// assert!(bv.eq_vec(&[true, false]));
/// ```
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn push(&mut self, elem: bool) {
if self.nbits % u32::BITS == 0 {
self.storage.push(0);
/// Return the total number of bits in this vector
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn len(&self) -> uint { self.nbits }
/// Returns true if there are no bits in this vector
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn is_empty(&self) -> bool { self.len() == 0 }
/// Clears all bits in this vector.
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn clear(&mut self) {
for w in self.storage.iter_mut() { *w = 0u32; }
}
#[stable]
impl Default for Bitv {
#[inline]
- #[stable]
fn default() -> Bitv { Bitv::new() }
}
+#[stable]
impl FromIterator<bool> for Bitv {
fn from_iter<I:Iterator<bool>>(iterator: I) -> Bitv {
let mut ret = Bitv::new();
}
}
+#[stable]
impl Extend<bool> for Bitv {
#[inline]
fn extend<I: Iterator<bool>>(&mut self, mut iterator: I) {
}
}
+#[stable]
impl PartialOrd for Bitv {
#[inline]
fn partial_cmp(&self, other: &Bitv) -> Option<Ordering> {
}
}
+#[stable]
impl Ord for Bitv {
#[inline]
fn cmp(&self, other: &Bitv) -> Ordering {
}
}
+#[stable]
impl fmt::Show for Bitv {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
for bit in self.iter() {
}
}
+#[stable]
impl<S: hash::Writer> hash::Hash<S> for Bitv {
fn hash(&self, state: &mut S) {
self.nbits.hash(state);
}
}
+#[stable]
impl cmp::PartialEq for Bitv {
#[inline]
fn eq(&self, other: &Bitv) -> bool {
}
}
+#[stable]
impl cmp::Eq for Bitv {}
/// An iterator for `Bitv`.
-pub struct Bits<'a> {
+#[stable]
+#[deriving(Clone)]
+pub struct Iter<'a> {
bitv: &'a Bitv,
next_idx: uint,
end_idx: uint,
}
-impl<'a> Iterator<bool> for Bits<'a> {
+#[stable]
+impl<'a> Iterator<bool> for Iter<'a> {
#[inline]
fn next(&mut self) -> Option<bool> {
if self.next_idx != self.end_idx {
}
}
-impl<'a> DoubleEndedIterator<bool> for Bits<'a> {
+#[stable]
+impl<'a> DoubleEndedIterator<bool> for Iter<'a> {
#[inline]
fn next_back(&mut self) -> Option<bool> {
if self.next_idx != self.end_idx {
}
}
-impl<'a> ExactSizeIterator<bool> for Bits<'a> {}
+#[stable]
+impl<'a> ExactSizeIterator<bool> for Iter<'a> {}
-impl<'a> RandomAccessIterator<bool> for Bits<'a> {
+#[stable]
+impl<'a> RandomAccessIterator<bool> for Iter<'a> {
#[inline]
fn indexable(&self) -> uint {
self.end_idx - self.next_idx
/// assert!(bv[3]);
/// ```
#[deriving(Clone)]
+#[stable]
pub struct BitvSet {
bitv: Bitv,
}
+#[stable]
impl Default for BitvSet {
#[inline]
fn default() -> BitvSet { BitvSet::new() }
}
+#[stable]
impl FromIterator<uint> for BitvSet {
fn from_iter<I:Iterator<uint>>(iterator: I) -> BitvSet {
let mut ret = BitvSet::new();
}
}
+#[stable]
impl Extend<uint> for BitvSet {
#[inline]
fn extend<I: Iterator<uint>>(&mut self, mut iterator: I) {
}
}
+#[stable]
impl PartialOrd for BitvSet {
#[inline]
fn partial_cmp(&self, other: &BitvSet) -> Option<Ordering> {
}
}
+#[stable]
impl Ord for BitvSet {
#[inline]
fn cmp(&self, other: &BitvSet) -> Ordering {
}
}
+#[stable]
impl cmp::PartialEq for BitvSet {
#[inline]
fn eq(&self, other: &BitvSet) -> bool {
}
}
+#[stable]
impl cmp::Eq for BitvSet {}
impl BitvSet {
/// let mut s = BitvSet::new();
/// ```
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn new() -> BitvSet {
BitvSet { bitv: Bitv::new() }
}
/// assert!(s.capacity() >= 100);
/// ```
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn with_capacity(nbits: uint) -> BitvSet {
let bitv = Bitv::from_elem(nbits, false);
BitvSet::from_bitv(bitv)
/// assert!(s.capacity() >= 100);
/// ```
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn capacity(&self) -> uint {
self.bitv.capacity()
}
/// s.reserve_len(10);
/// assert!(s.capacity() >= 10);
/// ```
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn reserve_len(&mut self, len: uint) {
let cur_len = self.bitv.len();
if len >= cur_len {
/// s.reserve_len_exact(10);
/// assert!(s.capacity() >= 10);
/// ```
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn reserve_len_exact(&mut self, len: uint) {
let cur_len = self.bitv.len();
if len >= cur_len {
/// assert_eq!(bv[0], true);
/// ```
#[inline]
- pub fn get_ref<'a>(&'a self) -> &'a Bitv {
+ pub fn get_ref(&self) -> &Bitv {
&self.bitv
}
/// println!("new capacity: {}", s.capacity());
/// ```
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn shrink_to_fit(&mut self) {
let bitv = &mut self.bitv;
// Obtain original length
/// }
/// ```
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
- pub fn iter<'a>(&'a self) -> BitPositions<'a> {
- BitPositions {set: self, next_idx: 0u}
+ #[stable]
+ pub fn iter(&self) -> bitv_set::Iter {
+ SetIter {set: self, next_idx: 0u}
}
/// Iterator over each u32 stored in `self` union `other`.
/// }
/// ```
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
- pub fn union<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
+ #[stable]
+ pub fn union<'a>(&'a self, other: &'a BitvSet) -> Union<'a> {
fn or(w1: u32, w2: u32) -> u32 { w1 | w2 }
- TwoBitPositions {
+ Union(TwoBitPositions {
set: self,
other: other,
merge: or,
current_word: 0u32,
next_idx: 0u
- }
+ })
}
/// Iterator over each uint stored in `self` intersect `other`.
/// }
/// ```
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
- pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Take<TwoBitPositions<'a>> {
+ #[stable]
+ pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Intersection<'a> {
fn bitand(w1: u32, w2: u32) -> u32 { w1 & w2 }
let min = cmp::min(self.bitv.len(), other.bitv.len());
- TwoBitPositions {
+ Intersection(TwoBitPositions {
set: self,
other: other,
merge: bitand,
current_word: 0u32,
next_idx: 0
- }.take(min)
+ }.take(min))
}
/// Iterator over each uint stored in the `self` setminus `other`.
/// }
/// ```
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
- pub fn difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
+ #[stable]
+ pub fn difference<'a>(&'a self, other: &'a BitvSet) -> Difference<'a> {
fn diff(w1: u32, w2: u32) -> u32 { w1 & !w2 }
- TwoBitPositions {
+ Difference(TwoBitPositions {
set: self,
other: other,
merge: diff,
current_word: 0u32,
next_idx: 0
- }
+ })
}
/// Iterator over each u32 stored in the symmetric difference of `self` and `other`.
/// }
/// ```
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
- pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
+ #[stable]
+ pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> SymmetricDifference<'a> {
fn bitxor(w1: u32, w2: u32) -> u32 { w1 ^ w2 }
- TwoBitPositions {
+ SymmetricDifference(TwoBitPositions {
set: self,
other: other,
merge: bitxor,
current_word: 0u32,
next_idx: 0
- }
+ })
}
/// Unions in-place with the specified other bit vector.
/// Return the number of set bits in this set.
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn len(&self) -> uint {
self.bitv.blocks().fold(0, |acc, n| acc + n.count_ones())
}
/// Returns whether there are no bits set in this set
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn is_empty(&self) -> bool {
self.bitv.none()
}
/// Clears all bits in this set
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn clear(&mut self) {
self.bitv.clear();
}
/// Returns `true` if this set contains the specified integer.
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn contains(&self, value: &uint) -> bool {
let bitv = &self.bitv;
*value < bitv.nbits && bitv[*value]
/// Returns `true` if the set has no elements in common with `other`.
/// This is equivalent to checking for an empty intersection.
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn is_disjoint(&self, other: &BitvSet) -> bool {
self.intersection(other).next().is_none()
}
/// Returns `true` if the set is a subset of another.
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn is_subset(&self, other: &BitvSet) -> bool {
let self_bitv = &self.bitv;
let other_bitv = &other.bitv;
/// Returns `true` if the set is a superset of another.
#[inline]
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn is_superset(&self, other: &BitvSet) -> bool {
other.is_subset(self)
}
/// Adds a value to the set. Returns `true` if the value was not already
/// present in the set.
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn insert(&mut self, value: uint) -> bool {
if self.contains(&value) {
return false;
/// Removes a value from the set. Returns `true` if the value was
/// present in the set.
- #[unstable = "matches collection reform specification, waiting for dust to settle"]
+ #[stable]
pub fn remove(&mut self, value: &uint) -> bool {
if !self.contains(value) {
return false;
}
/// An iterator for `BitvSet`.
-pub struct BitPositions<'a> {
+#[deriving(Clone)]
+#[stable]
+pub struct SetIter<'a> {
set: &'a BitvSet,
next_idx: uint
}
/// An iterator combining two `BitvSet` iterators.
-pub struct TwoBitPositions<'a> {
+#[deriving(Clone)]
+struct TwoBitPositions<'a> {
set: &'a BitvSet,
other: &'a BitvSet,
merge: fn(u32, u32) -> u32,
next_idx: uint
}
-impl<'a> Iterator<uint> for BitPositions<'a> {
+#[stable]
+pub struct Union<'a>(TwoBitPositions<'a>);
+#[stable]
+pub struct Intersection<'a>(Take<TwoBitPositions<'a>>);
+#[stable]
+pub struct Difference<'a>(TwoBitPositions<'a>);
+#[stable]
+pub struct SymmetricDifference<'a>(TwoBitPositions<'a>);
+
+#[stable]
+impl<'a> Iterator<uint> for SetIter<'a> {
fn next(&mut self) -> Option<uint> {
while self.next_idx < self.set.bitv.len() {
let idx = self.next_idx;
}
}
+#[stable]
impl<'a> Iterator<uint> for TwoBitPositions<'a> {
fn next(&mut self) -> Option<uint> {
while self.next_idx < self.set.bitv.len() ||
}
}
+#[stable]
+impl<'a> Iterator<uint> for Union<'a> {
+ #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
+ #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
+}
+
+#[stable]
+impl<'a> Iterator<uint> for Intersection<'a> {
+ #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
+ #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
+}
+#[stable]
+impl<'a> Iterator<uint> for Difference<'a> {
+ #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
+ #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
+}
+#[stable]
+impl<'a> Iterator<uint> for SymmetricDifference<'a> {
+ #[inline] fn next(&mut self) -> Option<uint> { self.0.next() }
+ #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.0.size_hint() }
+}
#[cfg(test)]
projects / rust.git / blobdiff