]>
Commit | Line | Data |
---|---|---|
3157f602 XL |
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. | |
4 | // | |
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. | |
10 | ||
3157f602 | 11 | use std::fmt; |
ea8adc8c | 12 | use std::iter; |
3157f602 XL |
13 | use std::marker::PhantomData; |
14 | use std::mem; | |
15 | use std::ops::{Deref, DerefMut, Range}; | |
ea8adc8c | 16 | use std::slice; |
3157f602 | 17 | use bitslice::{BitSlice, Word}; |
ea8adc8c | 18 | use bitslice::{bitwise, Union, Subtract, Intersect}; |
c30ab7b3 | 19 | use indexed_vec::Idx; |
3157f602 XL |
20 | |
21 | /// Represents a set (or packed family of sets), of some element type | |
22 | /// E, where each E is identified by some unique index type `T`. | |
23 | /// | |
24 | /// In other words, `T` is the type used to index into the bitvector | |
25 | /// this type uses to represent the set of object it holds. | |
ea8adc8c | 26 | #[derive(Eq, PartialEq)] |
3157f602 XL |
27 | pub struct IdxSetBuf<T: Idx> { |
28 | _pd: PhantomData<fn(&T)>, | |
29 | bits: Vec<Word>, | |
30 | } | |
31 | ||
32 | impl<T: Idx> Clone for IdxSetBuf<T> { | |
33 | fn clone(&self) -> Self { | |
34 | IdxSetBuf { _pd: PhantomData, bits: self.bits.clone() } | |
35 | } | |
36 | } | |
37 | ||
38 | // pnkfelix wants to have this be `IdxSet<T>([Word]) and then pass | |
39 | // around `&mut IdxSet<T>` or `&IdxSet<T>`. | |
40 | // | |
41 | // WARNING: Mapping a `&IdxSetBuf<T>` to `&IdxSet<T>` (at least today) | |
42 | // requires a transmute relying on representation guarantees that may | |
43 | // not hold in the future. | |
44 | ||
45 | /// Represents a set (or packed family of sets), of some element type | |
46 | /// E, where each E is identified by some unique index type `T`. | |
47 | /// | |
48 | /// In other words, `T` is the type used to index into the bitslice | |
49 | /// this type uses to represent the set of object it holds. | |
50 | pub struct IdxSet<T: Idx> { | |
51 | _pd: PhantomData<fn(&T)>, | |
52 | bits: [Word], | |
53 | } | |
54 | ||
55 | impl<T: Idx> fmt::Debug for IdxSetBuf<T> { | |
abe05a73 XL |
56 | fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { |
57 | w.debug_list() | |
58 | .entries(self.iter()) | |
59 | .finish() | |
60 | } | |
3157f602 XL |
61 | } |
62 | ||
63 | impl<T: Idx> fmt::Debug for IdxSet<T> { | |
abe05a73 XL |
64 | fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { |
65 | w.debug_list() | |
66 | .entries(self.iter()) | |
67 | .finish() | |
68 | } | |
3157f602 XL |
69 | } |
70 | ||
71 | impl<T: Idx> IdxSetBuf<T> { | |
72 | fn new(init: Word, universe_size: usize) -> Self { | |
73 | let bits_per_word = mem::size_of::<Word>() * 8; | |
74 | let num_words = (universe_size + (bits_per_word - 1)) / bits_per_word; | |
75 | IdxSetBuf { | |
76 | _pd: Default::default(), | |
77 | bits: vec![init; num_words], | |
78 | } | |
79 | } | |
80 | ||
81 | /// Creates set holding every element whose index falls in range 0..universe_size. | |
82 | pub fn new_filled(universe_size: usize) -> Self { | |
83 | Self::new(!0, universe_size) | |
84 | } | |
85 | ||
86 | /// Creates set holding no elements. | |
87 | pub fn new_empty(universe_size: usize) -> Self { | |
88 | Self::new(0, universe_size) | |
89 | } | |
90 | } | |
91 | ||
92 | impl<T: Idx> IdxSet<T> { | |
93 | unsafe fn from_slice(s: &[Word]) -> &Self { | |
94 | mem::transmute(s) // (see above WARNING) | |
95 | } | |
96 | ||
97 | unsafe fn from_slice_mut(s: &mut [Word]) -> &mut Self { | |
98 | mem::transmute(s) // (see above WARNING) | |
99 | } | |
100 | } | |
101 | ||
102 | impl<T: Idx> Deref for IdxSetBuf<T> { | |
103 | type Target = IdxSet<T>; | |
104 | fn deref(&self) -> &IdxSet<T> { | |
cc61c64b | 105 | unsafe { IdxSet::from_slice(&self.bits) } |
3157f602 XL |
106 | } |
107 | } | |
108 | ||
109 | impl<T: Idx> DerefMut for IdxSetBuf<T> { | |
110 | fn deref_mut(&mut self) -> &mut IdxSet<T> { | |
cc61c64b | 111 | unsafe { IdxSet::from_slice_mut(&mut self.bits) } |
3157f602 XL |
112 | } |
113 | } | |
114 | ||
115 | impl<T: Idx> IdxSet<T> { | |
116 | pub fn to_owned(&self) -> IdxSetBuf<T> { | |
117 | IdxSetBuf { | |
118 | _pd: Default::default(), | |
119 | bits: self.bits.to_owned(), | |
120 | } | |
121 | } | |
122 | ||
ea8adc8c XL |
123 | /// Removes all elements |
124 | pub fn clear(&mut self) { | |
125 | for b in &mut self.bits { | |
126 | *b = 0; | |
127 | } | |
128 | } | |
129 | ||
3157f602 XL |
130 | /// Removes `elem` from the set `self`; returns true iff this changed `self`. |
131 | pub fn remove(&mut self, elem: &T) -> bool { | |
132 | self.bits.clear_bit(elem.index()) | |
133 | } | |
134 | ||
135 | /// Adds `elem` to the set `self`; returns true iff this changed `self`. | |
136 | pub fn add(&mut self, elem: &T) -> bool { | |
137 | self.bits.set_bit(elem.index()) | |
138 | } | |
139 | ||
140 | pub fn range(&self, elems: &Range<T>) -> &Self { | |
141 | let elems = elems.start.index()..elems.end.index(); | |
142 | unsafe { Self::from_slice(&self.bits[elems]) } | |
143 | } | |
144 | ||
145 | pub fn range_mut(&mut self, elems: &Range<T>) -> &mut Self { | |
146 | let elems = elems.start.index()..elems.end.index(); | |
147 | unsafe { Self::from_slice_mut(&mut self.bits[elems]) } | |
148 | } | |
149 | ||
150 | /// Returns true iff set `self` contains `elem`. | |
151 | pub fn contains(&self, elem: &T) -> bool { | |
152 | self.bits.get_bit(elem.index()) | |
153 | } | |
154 | ||
155 | pub fn words(&self) -> &[Word] { | |
cc61c64b | 156 | &self.bits |
3157f602 XL |
157 | } |
158 | ||
159 | pub fn words_mut(&mut self) -> &mut [Word] { | |
cc61c64b | 160 | &mut self.bits |
3157f602 XL |
161 | } |
162 | ||
163 | pub fn clone_from(&mut self, other: &IdxSet<T>) { | |
164 | self.words_mut().clone_from_slice(other.words()); | |
165 | } | |
166 | ||
167 | pub fn union(&mut self, other: &IdxSet<T>) -> bool { | |
168 | bitwise(self.words_mut(), other.words(), &Union) | |
169 | } | |
170 | ||
171 | pub fn subtract(&mut self, other: &IdxSet<T>) -> bool { | |
172 | bitwise(self.words_mut(), other.words(), &Subtract) | |
173 | } | |
3b2f2976 | 174 | |
ea8adc8c XL |
175 | pub fn intersect(&mut self, other: &IdxSet<T>) -> bool { |
176 | bitwise(self.words_mut(), other.words(), &Intersect) | |
177 | } | |
178 | ||
179 | pub fn iter(&self) -> Iter<T> { | |
180 | Iter { | |
181 | cur: None, | |
182 | iter: self.words().iter().enumerate(), | |
183 | _pd: PhantomData, | |
184 | } | |
185 | } | |
186 | ||
3b2f2976 XL |
187 | /// Calls `f` on each index value held in this set, up to the |
188 | /// bound `max_bits` on the size of universe of indexes. | |
189 | pub fn each_bit<F>(&self, max_bits: usize, f: F) where F: FnMut(T) { | |
190 | each_bit(self, max_bits, f) | |
191 | } | |
192 | ||
193 | /// Removes all elements from this set. | |
194 | pub fn reset_to_empty(&mut self) { | |
195 | for word in self.words_mut() { *word = 0; } | |
196 | } | |
197 | ||
198 | pub fn elems(&self, universe_size: usize) -> Elems<T> { | |
199 | Elems { i: 0, set: self, universe_size: universe_size } | |
200 | } | |
201 | } | |
202 | ||
203 | pub struct Elems<'a, T: Idx> { i: usize, set: &'a IdxSet<T>, universe_size: usize } | |
204 | ||
205 | impl<'a, T: Idx> Iterator for Elems<'a, T> { | |
206 | type Item = T; | |
207 | fn next(&mut self) -> Option<T> { | |
208 | if self.i >= self.universe_size { return None; } | |
209 | let mut i = self.i; | |
210 | loop { | |
211 | if i >= self.universe_size { | |
212 | self.i = i; // (mark iteration as complete.) | |
213 | return None; | |
214 | } | |
215 | if self.set.contains(&T::new(i)) { | |
216 | self.i = i + 1; // (next element to start at.) | |
217 | return Some(T::new(i)); | |
218 | } | |
219 | i = i + 1; | |
220 | } | |
221 | } | |
222 | } | |
223 | ||
224 | fn each_bit<T: Idx, F>(words: &IdxSet<T>, max_bits: usize, mut f: F) where F: FnMut(T) { | |
225 | let usize_bits: usize = mem::size_of::<usize>() * 8; | |
226 | ||
227 | for (word_index, &word) in words.words().iter().enumerate() { | |
228 | if word != 0 { | |
229 | let base_index = word_index * usize_bits; | |
230 | for offset in 0..usize_bits { | |
231 | let bit = 1 << offset; | |
232 | if (word & bit) != 0 { | |
233 | // NB: we round up the total number of bits | |
234 | // that we store in any given bit set so that | |
235 | // it is an even multiple of usize::BITS. This | |
236 | // means that there may be some stray bits at | |
237 | // the end that do not correspond to any | |
238 | // actual value; that's why we first check | |
239 | // that we are in range of bits_per_block. | |
240 | let bit_index = base_index + offset as usize; | |
241 | if bit_index >= max_bits { | |
242 | return; | |
243 | } else { | |
244 | f(Idx::new(bit_index)); | |
245 | } | |
246 | } | |
247 | } | |
248 | } | |
249 | } | |
3157f602 | 250 | } |
ea8adc8c XL |
251 | |
252 | pub struct Iter<'a, T: Idx> { | |
253 | cur: Option<(Word, usize)>, | |
254 | iter: iter::Enumerate<slice::Iter<'a, Word>>, | |
255 | _pd: PhantomData<fn(&T)>, | |
256 | } | |
257 | ||
258 | impl<'a, T: Idx> Iterator for Iter<'a, T> { | |
259 | type Item = T; | |
260 | ||
261 | fn next(&mut self) -> Option<T> { | |
262 | let word_bits = mem::size_of::<Word>() * 8; | |
263 | loop { | |
264 | if let Some((ref mut word, offset)) = self.cur { | |
265 | let bit_pos = word.trailing_zeros() as usize; | |
266 | if bit_pos != word_bits { | |
267 | let bit = 1 << bit_pos; | |
268 | *word ^= bit; | |
269 | return Some(T::new(bit_pos + offset)) | |
270 | } | |
271 | } | |
272 | ||
273 | match self.iter.next() { | |
274 | Some((i, word)) => self.cur = Some((*word, word_bits * i)), | |
275 | None => return None, | |
276 | } | |
277 | } | |
278 | } | |
279 | } |