1 // Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use array_vec::ArrayVec;
14 use std::marker::PhantomData;
17 use bitslice::{BitSlice, Word};
18 use bitslice::{bitwise, Union, Subtract, Intersect};
22 /// This is implemented by all the index sets so that IdxSet::union() can be
23 /// passed any type of index set.
24 pub trait UnionIntoIdxSet<T: Idx> {
25 // Performs `other = other | self`.
26 fn union_into(&self, other: &mut IdxSet<T>) -> bool;
29 /// This is implemented by all the index sets so that IdxSet::subtract() can be
30 /// passed any type of index set.
31 pub trait SubtractFromIdxSet<T: Idx> {
32 // Performs `other = other - self`.
33 fn subtract_from(&self, other: &mut IdxSet<T>) -> bool;
36 /// Represents a set of some element type E, where each E is identified by some
37 /// unique index type `T`.
39 /// In other words, `T` is the type used to index into the bitvector
40 /// this type uses to represent the set of object it holds.
42 /// The representation is dense, using one bit per possible element.
43 #[derive(Eq, PartialEq)]
44 pub struct IdxSet<T: Idx> {
45 _pd: PhantomData<fn(&T)>,
49 impl<T: Idx> Clone for IdxSet<T> {
50 fn clone(&self) -> Self {
51 IdxSet { _pd: PhantomData, bits: self.bits.clone() }
55 impl<T: Idx> rustc_serialize::Encodable for IdxSet<T> {
56 fn encode<E: rustc_serialize::Encoder>(&self,
58 -> Result<(), E::Error> {
59 self.bits.encode(encoder)
63 impl<T: Idx> rustc_serialize::Decodable for IdxSet<T> {
64 fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<IdxSet<T>, D::Error> {
65 let words: Vec<Word> = rustc_serialize::Decodable::decode(d)?;
74 const BITS_PER_WORD: usize = mem::size_of::<Word>() * 8;
76 impl<T: Idx> fmt::Debug for IdxSet<T> {
77 fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
84 impl<T: Idx> IdxSet<T> {
85 fn new(init: Word, domain_size: usize) -> Self {
86 let num_words = (domain_size + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
88 _pd: Default::default(),
89 bits: vec![init; num_words],
93 /// Creates set holding every element whose index falls in range 0..domain_size.
94 pub fn new_filled(domain_size: usize) -> Self {
95 let mut result = Self::new(!0, domain_size);
96 result.trim_to(domain_size);
100 /// Creates set holding no elements.
101 pub fn new_empty(domain_size: usize) -> Self {
102 Self::new(0, domain_size)
105 /// Duplicates as a hybrid set.
106 pub fn to_hybrid(&self) -> HybridIdxSet<T> {
107 // This domain_size may be slightly larger than the one specified
108 // upon creation, due to rounding up to a whole word. That's ok.
109 let domain_size = self.bits.len() * BITS_PER_WORD;
111 // Note: we currently don't bother trying to make a Sparse set.
112 HybridIdxSet::Dense(self.to_owned(), domain_size)
115 /// Removes all elements
116 pub fn clear(&mut self) {
117 for b in &mut self.bits {
122 /// Sets all elements up to `domain_size`
123 pub fn set_up_to(&mut self, domain_size: usize) {
124 for b in &mut self.bits {
127 self.trim_to(domain_size);
130 /// Clear all elements above `domain_size`.
131 fn trim_to(&mut self, domain_size: usize) {
132 // `trim_block` is the first block where some bits have
134 let trim_block = domain_size / BITS_PER_WORD;
136 // all the blocks above it have to be completely cleared.
137 if trim_block < self.bits.len() {
138 for b in &mut self.bits[trim_block+1..] {
142 // at that block, the `domain_size % BITS_PER_WORD` LSBs
144 let remaining_bits = domain_size % BITS_PER_WORD;
145 let mask = (1<<remaining_bits)-1;
146 self.bits[trim_block] &= mask;
150 /// Removes `elem` from the set `self`; returns true iff this changed `self`.
151 pub fn remove(&mut self, elem: &T) -> bool {
152 self.bits.clear_bit(elem.index())
155 /// Adds `elem` to the set `self`; returns true iff this changed `self`.
156 pub fn add(&mut self, elem: &T) -> bool {
157 self.bits.set_bit(elem.index())
160 /// Returns true iff set `self` contains `elem`.
161 pub fn contains(&self, elem: &T) -> bool {
162 self.bits.get_bit(elem.index())
165 pub fn words(&self) -> &[Word] {
169 pub fn words_mut(&mut self) -> &mut [Word] {
173 /// Efficiently overwrite `self` with `other`. Panics if `self` and `other`
174 /// don't have the same length.
175 pub fn overwrite(&mut self, other: &IdxSet<T>) {
176 self.words_mut().clone_from_slice(other.words());
179 /// Set `self = self | other` and return true if `self` changed
180 /// (i.e., if new bits were added).
181 pub fn union(&mut self, other: &impl UnionIntoIdxSet<T>) -> bool {
182 other.union_into(self)
185 /// Set `self = self - other` and return true if `self` changed.
186 /// (i.e., if any bits were removed).
187 pub fn subtract(&mut self, other: &impl SubtractFromIdxSet<T>) -> bool {
188 other.subtract_from(self)
191 /// Set `self = self & other` and return true if `self` changed.
192 /// (i.e., if any bits were removed).
193 pub fn intersect(&mut self, other: &IdxSet<T>) -> bool {
194 bitwise(self.words_mut(), other.words(), &Intersect)
197 pub fn iter(&self) -> Iter<T> {
200 iter: self.words().iter().enumerate(),
206 impl<T: Idx> UnionIntoIdxSet<T> for IdxSet<T> {
207 fn union_into(&self, other: &mut IdxSet<T>) -> bool {
208 bitwise(other.words_mut(), self.words(), &Union)
212 impl<T: Idx> SubtractFromIdxSet<T> for IdxSet<T> {
213 fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
214 bitwise(other.words_mut(), self.words(), &Subtract)
218 pub struct Iter<'a, T: Idx> {
219 cur: Option<(Word, usize)>,
220 iter: iter::Enumerate<slice::Iter<'a, Word>>,
221 _pd: PhantomData<fn(&T)>,
224 impl<'a, T: Idx> Iterator for Iter<'a, T> {
227 fn next(&mut self) -> Option<T> {
229 if let Some((ref mut word, offset)) = self.cur {
230 let bit_pos = word.trailing_zeros() as usize;
231 if bit_pos != BITS_PER_WORD {
232 let bit = 1 << bit_pos;
234 return Some(T::new(bit_pos + offset))
238 let (i, word) = self.iter.next()?;
239 self.cur = Some((*word, BITS_PER_WORD * i));
244 const SPARSE_MAX: usize = 8;
246 /// A sparse index set with a maximum of SPARSE_MAX elements. Used by
247 /// HybridIdxSet; do not use directly.
249 /// The elements are stored as an unsorted vector with no duplicates.
250 #[derive(Clone, Debug)]
251 pub struct SparseIdxSet<T: Idx>(ArrayVec<[T; SPARSE_MAX]>);
253 impl<T: Idx> SparseIdxSet<T> {
255 SparseIdxSet(ArrayVec::new())
258 fn len(&self) -> usize {
262 fn contains(&self, elem: &T) -> bool {
263 self.0.contains(elem)
266 fn add(&mut self, elem: &T) -> bool {
267 // Ensure there are no duplicates.
268 if self.0.contains(elem) {
276 fn remove(&mut self, elem: &T) -> bool {
277 if let Some(i) = self.0.iter().position(|e| e == elem) {
278 // Swap the found element to the end, then pop it.
279 let len = self.0.len();
280 self.0.swap(i, len - 1);
288 fn to_dense(&self, domain_size: usize) -> IdxSet<T> {
289 let mut dense = IdxSet::new_empty(domain_size);
290 for elem in self.0.iter() {
296 fn iter(&self) -> SparseIter<T> {
303 impl<T: Idx> UnionIntoIdxSet<T> for SparseIdxSet<T> {
304 fn union_into(&self, other: &mut IdxSet<T>) -> bool {
305 let mut changed = false;
306 for elem in self.iter() {
307 changed |= other.add(&elem);
313 impl<T: Idx> SubtractFromIdxSet<T> for SparseIdxSet<T> {
314 fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
315 let mut changed = false;
316 for elem in self.iter() {
317 changed |= other.remove(&elem);
323 pub struct SparseIter<'a, T: Idx> {
324 iter: slice::Iter<'a, T>,
327 impl<'a, T: Idx> Iterator for SparseIter<'a, T> {
330 fn next(&mut self) -> Option<T> {
331 self.iter.next().map(|e| *e)
335 /// Like IdxSet, but with a hybrid representation: sparse when there are few
336 /// elements in the set, but dense when there are many. It's especially
337 /// efficient for sets that typically have a small number of elements, but a
338 /// large `domain_size`, and are cleared frequently.
339 #[derive(Clone, Debug)]
340 pub enum HybridIdxSet<T: Idx> {
341 Sparse(SparseIdxSet<T>, usize),
342 Dense(IdxSet<T>, usize),
345 impl<T: Idx> HybridIdxSet<T> {
346 pub fn new_empty(domain_size: usize) -> Self {
347 HybridIdxSet::Sparse(SparseIdxSet::new(), domain_size)
350 pub fn clear(&mut self) {
351 let domain_size = match *self {
352 HybridIdxSet::Sparse(_, size) => size,
353 HybridIdxSet::Dense(_, size) => size,
355 *self = HybridIdxSet::new_empty(domain_size);
358 /// Returns true iff set `self` contains `elem`.
359 pub fn contains(&self, elem: &T) -> bool {
361 HybridIdxSet::Sparse(sparse, _) => sparse.contains(elem),
362 HybridIdxSet::Dense(dense, _) => dense.contains(elem),
366 /// Adds `elem` to the set `self`.
367 pub fn add(&mut self, elem: &T) -> bool {
369 HybridIdxSet::Sparse(sparse, _) if sparse.len() < SPARSE_MAX => {
370 // The set is sparse and has space for `elem`.
373 HybridIdxSet::Sparse(sparse, _) if sparse.contains(elem) => {
374 // The set is sparse and does not have space for `elem`, but
375 // that doesn't matter because `elem` is already present.
378 HybridIdxSet::Sparse(_, _) => {
379 // The set is sparse and full. Convert to a dense set.
381 // FIXME: This code is awful, but I can't work out how else to
382 // appease the borrow checker.
383 let dummy = HybridIdxSet::Sparse(SparseIdxSet::new(), 0);
384 match mem::replace(self, dummy) {
385 HybridIdxSet::Sparse(sparse, domain_size) => {
386 let mut dense = sparse.to_dense(domain_size);
387 let changed = dense.add(elem);
389 mem::replace(self, HybridIdxSet::Dense(dense, domain_size));
392 _ => panic!("impossible"),
396 HybridIdxSet::Dense(dense, _) => dense.add(elem),
400 /// Removes `elem` from the set `self`.
401 pub fn remove(&mut self, elem: &T) -> bool {
402 // Note: we currently don't bother going from Dense back to Sparse.
404 HybridIdxSet::Sparse(sparse, _) => sparse.remove(elem),
405 HybridIdxSet::Dense(dense, _) => dense.remove(elem),
409 /// Converts to a dense set, consuming itself in the process.
410 pub fn to_dense(self) -> IdxSet<T> {
412 HybridIdxSet::Sparse(sparse, domain_size) => sparse.to_dense(domain_size),
413 HybridIdxSet::Dense(dense, _) => dense,
417 /// Iteration order is unspecified.
418 pub fn iter(&self) -> HybridIter<T> {
420 HybridIdxSet::Sparse(sparse, _) => HybridIter::Sparse(sparse.iter()),
421 HybridIdxSet::Dense(dense, _) => HybridIter::Dense(dense.iter()),
426 impl<T: Idx> UnionIntoIdxSet<T> for HybridIdxSet<T> {
427 fn union_into(&self, other: &mut IdxSet<T>) -> bool {
429 HybridIdxSet::Sparse(sparse, _) => sparse.union_into(other),
430 HybridIdxSet::Dense(dense, _) => dense.union_into(other),
435 impl<T: Idx> SubtractFromIdxSet<T> for HybridIdxSet<T> {
436 fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
438 HybridIdxSet::Sparse(sparse, _) => sparse.subtract_from(other),
439 HybridIdxSet::Dense(dense, _) => dense.subtract_from(other),
444 pub enum HybridIter<'a, T: Idx> {
445 Sparse(SparseIter<'a, T>),
449 impl<'a, T: Idx> Iterator for HybridIter<'a, T> {
452 fn next(&mut self) -> Option<T> {
454 HybridIter::Sparse(sparse) => sparse.next(),
455 HybridIter::Dense(dense) => dense.next(),
465 let mut idx_buf: IdxSet<usize> = IdxSet::new_filled(128);
468 let elems: Vec<usize> = idx_buf.iter().collect();
469 let expected: Vec<usize> = (0..cmp::min(i, 128)).collect();
470 assert_eq!(elems, expected);
475 fn test_set_up_to() {
478 vec![IdxSet::new_empty(128), IdxSet::new_filled(128)]
481 idx_buf.set_up_to(i);
483 let elems: Vec<usize> = idx_buf.iter().collect();
484 let expected: Vec<usize> = (0..i).collect();
485 assert_eq!(elems, expected);
491 fn test_new_filled() {
493 let idx_buf = IdxSet::new_filled(i);
494 let elems: Vec<usize> = idx_buf.iter().collect();
495 let expected: Vec<usize> = (0..i).collect();
496 assert_eq!(elems, expected);