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.
12 use std
::marker
::PhantomData
;
14 use std
::ops
::{Deref, DerefMut, Range}
;
15 use bitslice
::{BitSlice, Word}
;
16 use bitslice
::{bitwise, Union, Subtract}
;
19 /// Represents a set (or packed family of sets), of some element type
20 /// E, where each E is identified by some unique index type `T`.
22 /// In other words, `T` is the type used to index into the bitvector
23 /// this type uses to represent the set of object it holds.
24 pub struct IdxSetBuf
<T
: Idx
> {
25 _pd
: PhantomData
<fn(&T
)>,
29 impl<T
: Idx
> Clone
for IdxSetBuf
<T
> {
30 fn clone(&self) -> Self {
31 IdxSetBuf { _pd: PhantomData, bits: self.bits.clone() }
35 // pnkfelix wants to have this be `IdxSet<T>([Word]) and then pass
36 // around `&mut IdxSet<T>` or `&IdxSet<T>`.
38 // WARNING: Mapping a `&IdxSetBuf<T>` to `&IdxSet<T>` (at least today)
39 // requires a transmute relying on representation guarantees that may
40 // not hold in the future.
42 /// Represents a set (or packed family of sets), of some element type
43 /// E, where each E is identified by some unique index type `T`.
45 /// In other words, `T` is the type used to index into the bitslice
46 /// this type uses to represent the set of object it holds.
47 pub struct IdxSet
<T
: Idx
> {
48 _pd
: PhantomData
<fn(&T
)>,
52 impl<T
: Idx
> fmt
::Debug
for IdxSetBuf
<T
> {
53 fn fmt(&self, w
: &mut fmt
::Formatter
) -> fmt
::Result { self.bits.fmt(w) }
56 impl<T
: Idx
> fmt
::Debug
for IdxSet
<T
> {
57 fn fmt(&self, w
: &mut fmt
::Formatter
) -> fmt
::Result { self.bits.fmt(w) }
60 impl<T
: Idx
> IdxSetBuf
<T
> {
61 fn new(init
: Word
, universe_size
: usize) -> Self {
62 let bits_per_word
= mem
::size_of
::<Word
>() * 8;
63 let num_words
= (universe_size
+ (bits_per_word
- 1)) / bits_per_word
;
65 _pd
: Default
::default(),
66 bits
: vec
![init
; num_words
],
70 /// Creates set holding every element whose index falls in range 0..universe_size.
71 pub fn new_filled(universe_size
: usize) -> Self {
72 Self::new(!0, universe_size
)
75 /// Creates set holding no elements.
76 pub fn new_empty(universe_size
: usize) -> Self {
77 Self::new(0, universe_size
)
81 impl<T
: Idx
> IdxSet
<T
> {
82 unsafe fn from_slice(s
: &[Word
]) -> &Self {
83 mem
::transmute(s
) // (see above WARNING)
86 unsafe fn from_slice_mut(s
: &mut [Word
]) -> &mut Self {
87 mem
::transmute(s
) // (see above WARNING)
91 impl<T
: Idx
> Deref
for IdxSetBuf
<T
> {
92 type Target
= IdxSet
<T
>;
93 fn deref(&self) -> &IdxSet
<T
> {
94 unsafe { IdxSet::from_slice(&self.bits[..]) }
98 impl<T
: Idx
> DerefMut
for IdxSetBuf
<T
> {
99 fn deref_mut(&mut self) -> &mut IdxSet
<T
> {
100 unsafe { IdxSet::from_slice_mut(&mut self.bits[..]) }
104 impl<T
: Idx
> IdxSet
<T
> {
105 pub fn to_owned(&self) -> IdxSetBuf
<T
> {
107 _pd
: Default
::default(),
108 bits
: self.bits
.to_owned(),
112 /// Removes `elem` from the set `self`; returns true iff this changed `self`.
113 pub fn remove(&mut self, elem
: &T
) -> bool
{
114 self.bits
.clear_bit(elem
.index())
117 /// Adds `elem` to the set `self`; returns true iff this changed `self`.
118 pub fn add(&mut self, elem
: &T
) -> bool
{
119 self.bits
.set_bit(elem
.index())
122 pub fn range(&self, elems
: &Range
<T
>) -> &Self {
123 let elems
= elems
.start
.index()..elems
.end
.index();
124 unsafe { Self::from_slice(&self.bits[elems]) }
127 pub fn range_mut(&mut self, elems
: &Range
<T
>) -> &mut Self {
128 let elems
= elems
.start
.index()..elems
.end
.index();
129 unsafe { Self::from_slice_mut(&mut self.bits[elems]) }
132 /// Returns true iff set `self` contains `elem`.
133 pub fn contains(&self, elem
: &T
) -> bool
{
134 self.bits
.get_bit(elem
.index())
137 pub fn words(&self) -> &[Word
] {
141 pub fn words_mut(&mut self) -> &mut [Word
] {
145 pub fn clone_from(&mut self, other
: &IdxSet
<T
>) {
146 self.words_mut().clone_from_slice(other
.words());
149 pub fn union(&mut self, other
: &IdxSet
<T
>) -> bool
{
150 bitwise(self.words_mut(), other
.words(), &Union
)
153 pub fn subtract(&mut self, other
: &IdxSet
<T
>) -> bool
{
154 bitwise(self.words_mut(), other
.words(), &Subtract
)