+++ /dev/null
-// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-use array_vec::ArrayVec;
-use std::fmt;
-use std::mem;
-use std::slice;
-use bitvec::{bitwise, BitArray, BitIter, Intersect, Subtract, Union, Word, WORD_BITS};
-use indexed_vec::Idx;
-use rustc_serialize;
-
-/// This is implemented by all the index sets so that IdxSet::union() can be
-/// passed any type of index set.
-pub trait UnionIntoIdxSet<T: Idx> {
- // Performs `other = other | self`.
- fn union_into(&self, other: &mut IdxSet<T>) -> bool;
-}
-
-/// This is implemented by all the index sets so that IdxSet::subtract() can be
-/// passed any type of index set.
-pub trait SubtractFromIdxSet<T: Idx> {
- // Performs `other = other - self`.
- fn subtract_from(&self, other: &mut IdxSet<T>) -> bool;
-}
-
-/// Represents a set of some element type E, where each E is identified by some
-/// unique index type `T`.
-///
-/// In other words, `T` is the type used to index into the bitvector
-/// this type uses to represent the set of object it holds.
-///
-/// The representation is dense, using one bit per possible element.
-#[derive(Clone, Eq, PartialEq)]
-pub struct IdxSet<T: Idx>(BitArray<T>);
-
-impl<T: Idx> rustc_serialize::Encodable for IdxSet<T> {
- fn encode<E: rustc_serialize::Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> {
- self.0.encode(encoder)
- }
-}
-
-impl<T: Idx> rustc_serialize::Decodable for IdxSet<T> {
- fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<IdxSet<T>, D::Error> {
- Ok(IdxSet(rustc_serialize::Decodable::decode(d)?))
- }
-}
-
-impl<T: Idx> fmt::Debug for IdxSet<T> {
- fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
- w.debug_list()
- .entries(self.iter())
- .finish()
- }
-}
-
-impl<T: Idx> IdxSet<T> {
- /// Creates set holding no elements.
- pub fn new_empty(domain_size: usize) -> Self {
- IdxSet(BitArray::new_empty(domain_size))
- }
-
- /// Creates set holding every element whose index falls in range 0..domain_size.
- pub fn new_filled(domain_size: usize) -> Self {
- IdxSet(BitArray::new_filled(domain_size))
- }
-
- /// Duplicates as a hybrid set.
- pub fn to_hybrid(&self) -> HybridIdxSet<T> {
- // This domain_size may be slightly larger than the one specified
- // upon creation, due to rounding up to a whole word. That's ok.
- let domain_size = self.words().len() * WORD_BITS;
-
- // Note: we currently don't bother trying to make a Sparse set.
- HybridIdxSet::Dense(self.to_owned(), domain_size)
- }
-
- /// Removes all elements
- pub fn clear(&mut self) {
- self.0.clear();
- }
-
- /// Sets all elements up to `domain_size`
- pub fn set_up_to(&mut self, domain_size: usize) {
- self.0.set_up_to(domain_size);
- }
-
- /// Removes `elem` from the set `self`; returns true iff this changed `self`.
- pub fn remove(&mut self, elem: &T) -> bool {
- self.0.remove(*elem)
- }
-
- /// Adds `elem` to the set `self`; returns true iff this changed `self`.
- pub fn add(&mut self, elem: &T) -> bool {
- self.0.insert(*elem)
- }
-
- /// Returns true iff set `self` contains `elem`.
- pub fn contains(&self, elem: &T) -> bool {
- self.0.contains(*elem)
- }
-
- pub fn words(&self) -> &[Word] {
- self.0.words()
- }
-
- pub fn words_mut(&mut self) -> &mut [Word] {
- self.0.words_mut()
- }
-
- /// Efficiently overwrite `self` with `other`. Panics if `self` and `other`
- /// don't have the same length.
- pub fn overwrite(&mut self, other: &IdxSet<T>) {
- self.words_mut().clone_from_slice(other.words());
- }
-
- /// Set `self = self | other` and return true if `self` changed
- /// (i.e., if new bits were added).
- pub fn union(&mut self, other: &impl UnionIntoIdxSet<T>) -> bool {
- other.union_into(self)
- }
-
- /// Set `self = self - other` and return true if `self` changed.
- /// (i.e., if any bits were removed).
- pub fn subtract(&mut self, other: &impl SubtractFromIdxSet<T>) -> bool {
- other.subtract_from(self)
- }
-
- /// Set `self = self & other` and return true if `self` changed.
- /// (i.e., if any bits were removed).
- pub fn intersect(&mut self, other: &IdxSet<T>) -> bool {
- bitwise(self.words_mut(), other.words(), &Intersect)
- }
-
- pub fn iter(&self) -> BitIter<T> {
- self.0.iter()
- }
-}
-
-impl<T: Idx> UnionIntoIdxSet<T> for IdxSet<T> {
- fn union_into(&self, other: &mut IdxSet<T>) -> bool {
- bitwise(other.words_mut(), self.words(), &Union)
- }
-}
-
-impl<T: Idx> SubtractFromIdxSet<T> for IdxSet<T> {
- fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
- bitwise(other.words_mut(), self.words(), &Subtract)
- }
-}
-
-const SPARSE_MAX: usize = 8;
-
-/// A sparse index set with a maximum of SPARSE_MAX elements. Used by
-/// HybridIdxSet; do not use directly.
-///
-/// The elements are stored as an unsorted vector with no duplicates.
-#[derive(Clone, Debug)]
-pub struct SparseIdxSet<T: Idx>(ArrayVec<[T; SPARSE_MAX]>);
-
-impl<T: Idx> SparseIdxSet<T> {
- fn new() -> Self {
- SparseIdxSet(ArrayVec::new())
- }
-
- fn len(&self) -> usize {
- self.0.len()
- }
-
- fn contains(&self, elem: &T) -> bool {
- self.0.contains(elem)
- }
-
- fn add(&mut self, elem: &T) -> bool {
- // Ensure there are no duplicates.
- if self.0.contains(elem) {
- false
- } else {
- self.0.push(*elem);
- true
- }
- }
-
- fn remove(&mut self, elem: &T) -> bool {
- if let Some(i) = self.0.iter().position(|e| e == elem) {
- // Swap the found element to the end, then pop it.
- let len = self.0.len();
- self.0.swap(i, len - 1);
- self.0.pop();
- true
- } else {
- false
- }
- }
-
- fn to_dense(&self, domain_size: usize) -> IdxSet<T> {
- let mut dense = IdxSet::new_empty(domain_size);
- for elem in self.0.iter() {
- dense.add(elem);
- }
- dense
- }
-
- fn iter(&self) -> slice::Iter<T> {
- self.0.iter()
- }
-}
-
-impl<T: Idx> UnionIntoIdxSet<T> for SparseIdxSet<T> {
- fn union_into(&self, other: &mut IdxSet<T>) -> bool {
- let mut changed = false;
- for elem in self.iter() {
- changed |= other.add(&elem);
- }
- changed
- }
-}
-
-impl<T: Idx> SubtractFromIdxSet<T> for SparseIdxSet<T> {
- fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
- let mut changed = false;
- for elem in self.iter() {
- changed |= other.remove(&elem);
- }
- changed
- }
-}
-
-/// Like IdxSet, but with a hybrid representation: sparse when there are few
-/// elements in the set, but dense when there are many. It's especially
-/// efficient for sets that typically have a small number of elements, but a
-/// large `domain_size`, and are cleared frequently.
-#[derive(Clone, Debug)]
-pub enum HybridIdxSet<T: Idx> {
- Sparse(SparseIdxSet<T>, usize),
- Dense(IdxSet<T>, usize),
-}
-
-impl<T: Idx> HybridIdxSet<T> {
- pub fn new_empty(domain_size: usize) -> Self {
- HybridIdxSet::Sparse(SparseIdxSet::new(), domain_size)
- }
-
- pub fn clear(&mut self) {
- let domain_size = match *self {
- HybridIdxSet::Sparse(_, size) => size,
- HybridIdxSet::Dense(_, size) => size,
- };
- *self = HybridIdxSet::new_empty(domain_size);
- }
-
- /// Returns true iff set `self` contains `elem`.
- pub fn contains(&self, elem: &T) -> bool {
- match self {
- HybridIdxSet::Sparse(sparse, _) => sparse.contains(elem),
- HybridIdxSet::Dense(dense, _) => dense.contains(elem),
- }
- }
-
- /// Adds `elem` to the set `self`.
- pub fn add(&mut self, elem: &T) -> bool {
- match self {
- HybridIdxSet::Sparse(sparse, _) if sparse.len() < SPARSE_MAX => {
- // The set is sparse and has space for `elem`.
- sparse.add(elem)
- }
- HybridIdxSet::Sparse(sparse, _) if sparse.contains(elem) => {
- // The set is sparse and does not have space for `elem`, but
- // that doesn't matter because `elem` is already present.
- false
- }
- HybridIdxSet::Sparse(_, _) => {
- // The set is sparse and full. Convert to a dense set.
- //
- // FIXME: This code is awful, but I can't work out how else to
- // appease the borrow checker.
- let dummy = HybridIdxSet::Sparse(SparseIdxSet::new(), 0);
- match mem::replace(self, dummy) {
- HybridIdxSet::Sparse(sparse, domain_size) => {
- let mut dense = sparse.to_dense(domain_size);
- let changed = dense.add(elem);
- assert!(changed);
- mem::replace(self, HybridIdxSet::Dense(dense, domain_size));
- changed
- }
- _ => panic!("impossible"),
- }
- }
-
- HybridIdxSet::Dense(dense, _) => dense.add(elem),
- }
- }
-
- /// Removes `elem` from the set `self`.
- pub fn remove(&mut self, elem: &T) -> bool {
- // Note: we currently don't bother going from Dense back to Sparse.
- match self {
- HybridIdxSet::Sparse(sparse, _) => sparse.remove(elem),
- HybridIdxSet::Dense(dense, _) => dense.remove(elem),
- }
- }
-
- /// Converts to a dense set, consuming itself in the process.
- pub fn to_dense(self) -> IdxSet<T> {
- match self {
- HybridIdxSet::Sparse(sparse, domain_size) => sparse.to_dense(domain_size),
- HybridIdxSet::Dense(dense, _) => dense,
- }
- }
-
- /// Iteration order is unspecified.
- pub fn iter(&self) -> HybridIter<T> {
- match self {
- HybridIdxSet::Sparse(sparse, _) => HybridIter::Sparse(sparse.iter()),
- HybridIdxSet::Dense(dense, _) => HybridIter::Dense(dense.iter()),
- }
- }
-}
-
-impl<T: Idx> UnionIntoIdxSet<T> for HybridIdxSet<T> {
- fn union_into(&self, other: &mut IdxSet<T>) -> bool {
- match self {
- HybridIdxSet::Sparse(sparse, _) => sparse.union_into(other),
- HybridIdxSet::Dense(dense, _) => dense.union_into(other),
- }
- }
-}
-
-impl<T: Idx> SubtractFromIdxSet<T> for HybridIdxSet<T> {
- fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
- match self {
- HybridIdxSet::Sparse(sparse, _) => sparse.subtract_from(other),
- HybridIdxSet::Dense(dense, _) => dense.subtract_from(other),
- }
- }
-}
-
-pub enum HybridIter<'a, T: Idx> {
- Sparse(slice::Iter<'a, T>),
- Dense(BitIter<'a, T>),
-}
-
-impl<'a, T: Idx> Iterator for HybridIter<'a, T> {
- type Item = T;
-
- fn next(&mut self) -> Option<T> {
- match self {
- HybridIter::Sparse(sparse) => sparse.next().map(|e| *e),
- HybridIter::Dense(dense) => dense.next(),
- }
- }
-}
projects / rustc.git / blobdiff