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