]> git.proxmox.com Git - rustc.git/blob - src/libcollections/enum_set.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / libcollections / enum_set.rs
1 // Copyright 2012 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
11 //! A structure for holding a set of enum variants.
12 //!
13 //! This module defines a container which uses an efficient bit mask
14 //! representation to hold C-like enum variants.
15
16 #![unstable(feature = "enumset",
17 reason = "matches collection reform specification, \
18 waiting for dust to settle",
19 issue = "0")]
20
21 use core::marker;
22 use core::fmt;
23 use core::iter::FromIterator;
24 use core::ops::{Sub, BitOr, BitAnd, BitXor};
25
26 // FIXME(contentions): implement union family of methods? (general design may be
27 // wrong here)
28
29 /// A specialized set implementation to use enum types.
30 ///
31 /// It is a logic error for an item to be modified in such a way that the
32 /// transformation of the item to or from a `usize`, as determined by the
33 /// `CLike` trait, changes while the item is in the set. This is normally only
34 /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
35 #[derive(PartialEq, Eq, PartialOrd, Ord, Hash)]
36 pub struct EnumSet<E> {
37 // We must maintain the invariant that no bits are set
38 // for which no variant exists
39 bits: usize,
40 marker: marker::PhantomData<E>,
41 }
42
43 impl<E> Copy for EnumSet<E> {}
44
45 impl<E> Clone for EnumSet<E> {
46 fn clone(&self) -> EnumSet<E> {
47 *self
48 }
49 }
50
51 #[stable(feature = "rust1", since = "1.0.0")]
52 impl<E: CLike + fmt::Debug> fmt::Debug for EnumSet<E> {
53 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
54 fmt.debug_set().entries(self).finish()
55 }
56 }
57
58 /// An interface for casting C-like enum to usize and back.
59 /// A typically implementation is as below.
60 ///
61 /// ```{rust,ignore}
62 /// #[repr(usize)]
63 /// enum Foo {
64 /// A, B, C
65 /// }
66 ///
67 /// impl CLike for Foo {
68 /// fn to_usize(&self) -> usize {
69 /// *self as usize
70 /// }
71 ///
72 /// fn from_usize(v: usize) -> Foo {
73 /// unsafe { mem::transmute(v) }
74 /// }
75 /// }
76 /// ```
77 pub trait CLike {
78 /// Converts a C-like enum to a `usize`.
79 fn to_usize(&self) -> usize;
80 /// Converts a `usize` to a C-like enum.
81 fn from_usize(usize) -> Self;
82 }
83
84 fn bit<E: CLike>(e: &E) -> usize {
85 use core::mem;
86 let value = e.to_usize();
87 let bits = mem::size_of::<usize>() * 8;
88 assert!(value < bits,
89 "EnumSet only supports up to {} variants.",
90 bits - 1);
91 1 << value
92 }
93
94 impl<E: CLike> EnumSet<E> {
95 /// Returns an empty `EnumSet`.
96 pub fn new() -> EnumSet<E> {
97 EnumSet {
98 bits: 0,
99 marker: marker::PhantomData,
100 }
101 }
102
103 /// Returns the number of elements in the given `EnumSet`.
104 pub fn len(&self) -> usize {
105 self.bits.count_ones() as usize
106 }
107
108 /// Returns true if the `EnumSet` is empty.
109 pub fn is_empty(&self) -> bool {
110 self.bits == 0
111 }
112
113 pub fn clear(&mut self) {
114 self.bits = 0;
115 }
116
117 /// Returns `false` if the `EnumSet` contains any enum of the given `EnumSet`.
118 pub fn is_disjoint(&self, other: &EnumSet<E>) -> bool {
119 (self.bits & other.bits) == 0
120 }
121
122 /// Returns `true` if a given `EnumSet` is included in this `EnumSet`.
123 pub fn is_superset(&self, other: &EnumSet<E>) -> bool {
124 (self.bits & other.bits) == other.bits
125 }
126
127 /// Returns `true` if this `EnumSet` is included in the given `EnumSet`.
128 pub fn is_subset(&self, other: &EnumSet<E>) -> bool {
129 other.is_superset(self)
130 }
131
132 /// Returns the union of both `EnumSets`.
133 pub fn union(&self, e: EnumSet<E>) -> EnumSet<E> {
134 EnumSet {
135 bits: self.bits | e.bits,
136 marker: marker::PhantomData,
137 }
138 }
139
140 /// Returns the intersection of both `EnumSets`.
141 pub fn intersection(&self, e: EnumSet<E>) -> EnumSet<E> {
142 EnumSet {
143 bits: self.bits & e.bits,
144 marker: marker::PhantomData,
145 }
146 }
147
148 /// Adds an enum to the `EnumSet`, and returns `true` if it wasn't there before
149 pub fn insert(&mut self, e: E) -> bool {
150 let result = !self.contains(&e);
151 self.bits |= bit(&e);
152 result
153 }
154
155 /// Removes an enum from the EnumSet
156 pub fn remove(&mut self, e: &E) -> bool {
157 let result = self.contains(e);
158 self.bits &= !bit(e);
159 result
160 }
161
162 /// Returns `true` if an `EnumSet` contains a given enum.
163 pub fn contains(&self, e: &E) -> bool {
164 (self.bits & bit(e)) != 0
165 }
166
167 /// Returns an iterator over an `EnumSet`.
168 pub fn iter(&self) -> Iter<E> {
169 Iter::new(self.bits)
170 }
171 }
172
173 impl<E: CLike> Sub for EnumSet<E> {
174 type Output = EnumSet<E>;
175
176 fn sub(self, e: EnumSet<E>) -> EnumSet<E> {
177 EnumSet {
178 bits: self.bits & !e.bits,
179 marker: marker::PhantomData,
180 }
181 }
182 }
183
184 impl<E: CLike> BitOr for EnumSet<E> {
185 type Output = EnumSet<E>;
186
187 fn bitor(self, e: EnumSet<E>) -> EnumSet<E> {
188 EnumSet {
189 bits: self.bits | e.bits,
190 marker: marker::PhantomData,
191 }
192 }
193 }
194
195 impl<E: CLike> BitAnd for EnumSet<E> {
196 type Output = EnumSet<E>;
197
198 fn bitand(self, e: EnumSet<E>) -> EnumSet<E> {
199 EnumSet {
200 bits: self.bits & e.bits,
201 marker: marker::PhantomData,
202 }
203 }
204 }
205
206 impl<E: CLike> BitXor for EnumSet<E> {
207 type Output = EnumSet<E>;
208
209 fn bitxor(self, e: EnumSet<E>) -> EnumSet<E> {
210 EnumSet {
211 bits: self.bits ^ e.bits,
212 marker: marker::PhantomData,
213 }
214 }
215 }
216
217 /// An iterator over an EnumSet
218 pub struct Iter<E> {
219 index: usize,
220 bits: usize,
221 marker: marker::PhantomData<E>,
222 }
223
224 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
225 impl<E> Clone for Iter<E> {
226 fn clone(&self) -> Iter<E> {
227 Iter {
228 index: self.index,
229 bits: self.bits,
230 marker: marker::PhantomData,
231 }
232 }
233 }
234
235 impl<E: CLike> Iter<E> {
236 fn new(bits: usize) -> Iter<E> {
237 Iter {
238 index: 0,
239 bits: bits,
240 marker: marker::PhantomData,
241 }
242 }
243 }
244
245 impl<E: CLike> Iterator for Iter<E> {
246 type Item = E;
247
248 fn next(&mut self) -> Option<E> {
249 if self.bits == 0 {
250 return None;
251 }
252
253 while (self.bits & 1) == 0 {
254 self.index += 1;
255 self.bits >>= 1;
256 }
257 let elem = CLike::from_usize(self.index);
258 self.index += 1;
259 self.bits >>= 1;
260 Some(elem)
261 }
262
263 fn size_hint(&self) -> (usize, Option<usize>) {
264 let exact = self.bits.count_ones() as usize;
265 (exact, Some(exact))
266 }
267 }
268
269 impl<E: CLike> FromIterator<E> for EnumSet<E> {
270 fn from_iter<I: IntoIterator<Item = E>>(iter: I) -> EnumSet<E> {
271 let mut ret = EnumSet::new();
272 ret.extend(iter);
273 ret
274 }
275 }
276
277 #[stable(feature = "rust1", since = "1.0.0")]
278 impl<'a, E> IntoIterator for &'a EnumSet<E> where E: CLike
279 {
280 type Item = E;
281 type IntoIter = Iter<E>;
282
283 fn into_iter(self) -> Iter<E> {
284 self.iter()
285 }
286 }
287
288 impl<E: CLike> Extend<E> for EnumSet<E> {
289 fn extend<I: IntoIterator<Item = E>>(&mut self, iter: I) {
290 for element in iter {
291 self.insert(element);
292 }
293 }
294 }
295
296 #[stable(feature = "extend_ref", since = "1.2.0")]
297 impl<'a, E: 'a + CLike + Copy> Extend<&'a E> for EnumSet<E> {
298 fn extend<I: IntoIterator<Item = &'a E>>(&mut self, iter: I) {
299 self.extend(iter.into_iter().cloned());
300 }
301 }