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.
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.
11 //! A structure for holding a set of enum variants.
13 //! This module defines a container which uses an efficient bit mask
14 //! representation to hold C-like enum variants.
16 #![unstable(feature = "enumset",
17 reason = "matches collection reform specification, \
18 waiting for dust to settle",
20 #![rustc_deprecated(since = "1.16.0", reason = "long since replaced")]
25 use core::iter::{FromIterator, FusedIterator};
26 use core::ops::{Sub, BitOr, BitAnd, BitXor};
28 // FIXME(contentions): implement union family of methods? (general design may be
31 /// A specialized set implementation to use enum types.
33 /// It is a logic error for an item to be modified in such a way that the
34 /// transformation of the item to or from a `usize`, as determined by the
35 /// `CLike` trait, changes while the item is in the set. This is normally only
36 /// possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
37 #[derive(PartialEq, Eq, PartialOrd, Ord, Hash)]
38 pub struct EnumSet<E> {
39 // We must maintain the invariant that no bits are set
40 // for which no variant exists
42 marker: marker::PhantomData<E>,
45 impl<E> Copy for EnumSet<E> {}
47 impl<E> Clone for EnumSet<E> {
48 fn clone(&self) -> EnumSet<E> {
53 impl<E: CLike + fmt::Debug> fmt::Debug for EnumSet<E> {
54 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
55 fmt.debug_set().entries(self).finish()
59 /// An interface for casting C-like enum to usize and back.
60 /// A typically implementation is as below.
68 /// impl CLike for Foo {
69 /// fn to_usize(&self) -> usize {
73 /// fn from_usize(v: usize) -> Foo {
74 /// unsafe { mem::transmute(v) }
79 /// Converts a C-like enum to a `usize`.
80 fn to_usize(&self) -> usize;
81 /// Converts a `usize` to a C-like enum.
82 fn from_usize(usize) -> Self;
85 fn bit<E: CLike>(e: &E) -> usize {
87 let value = e.to_usize();
88 let bits = mem::size_of::<usize>() * 8;
90 "EnumSet only supports up to {} variants.",
95 impl<E: CLike> EnumSet<E> {
96 /// Returns an empty `EnumSet`.
97 pub fn new() -> EnumSet<E> {
100 marker: marker::PhantomData,
104 /// Returns the number of elements in the given `EnumSet`.
105 pub fn len(&self) -> usize {
106 self.bits.count_ones() as usize
109 /// Returns `true` if the `EnumSet` is empty.
110 pub fn is_empty(&self) -> bool {
114 pub fn clear(&mut self) {
118 /// Returns `false` if the `EnumSet` contains any enum of the given `EnumSet`.
119 pub fn is_disjoint(&self, other: &EnumSet<E>) -> bool {
120 (self.bits & other.bits) == 0
123 /// Returns `true` if a given `EnumSet` is included in this `EnumSet`.
124 pub fn is_superset(&self, other: &EnumSet<E>) -> bool {
125 (self.bits & other.bits) == other.bits
128 /// Returns `true` if this `EnumSet` is included in the given `EnumSet`.
129 pub fn is_subset(&self, other: &EnumSet<E>) -> bool {
130 other.is_superset(self)
133 /// Returns the union of both `EnumSets`.
134 pub fn union(&self, e: EnumSet<E>) -> EnumSet<E> {
136 bits: self.bits | e.bits,
137 marker: marker::PhantomData,
141 /// Returns the intersection of both `EnumSets`.
142 pub fn intersection(&self, e: EnumSet<E>) -> EnumSet<E> {
144 bits: self.bits & e.bits,
145 marker: marker::PhantomData,
149 /// Adds an enum to the `EnumSet`, and returns `true` if it wasn't there before
150 pub fn insert(&mut self, e: E) -> bool {
151 let result = !self.contains(&e);
152 self.bits |= bit(&e);
156 /// Removes an enum from the EnumSet
157 pub fn remove(&mut self, e: &E) -> bool {
158 let result = self.contains(e);
159 self.bits &= !bit(e);
163 /// Returns `true` if an `EnumSet` contains a given enum.
164 pub fn contains(&self, e: &E) -> bool {
165 (self.bits & bit(e)) != 0
168 /// Returns an iterator over an `EnumSet`.
169 pub fn iter(&self) -> Iter<E> {
174 impl<E: CLike> Sub for EnumSet<E> {
175 type Output = EnumSet<E>;
177 fn sub(self, e: EnumSet<E>) -> EnumSet<E> {
179 bits: self.bits & !e.bits,
180 marker: marker::PhantomData,
185 impl<E: CLike> BitOr for EnumSet<E> {
186 type Output = EnumSet<E>;
188 fn bitor(self, e: EnumSet<E>) -> EnumSet<E> {
190 bits: self.bits | e.bits,
191 marker: marker::PhantomData,
196 impl<E: CLike> BitAnd for EnumSet<E> {
197 type Output = EnumSet<E>;
199 fn bitand(self, e: EnumSet<E>) -> EnumSet<E> {
201 bits: self.bits & e.bits,
202 marker: marker::PhantomData,
207 impl<E: CLike> BitXor for EnumSet<E> {
208 type Output = EnumSet<E>;
210 fn bitxor(self, e: EnumSet<E>) -> EnumSet<E> {
212 bits: self.bits ^ e.bits,
213 marker: marker::PhantomData,
218 /// An iterator over an `EnumSet`
222 marker: marker::PhantomData<E>,
225 impl<E: fmt::Debug> fmt::Debug for Iter<E> {
226 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
227 f.debug_tuple("Iter")
234 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
235 impl<E> Clone for Iter<E> {
236 fn clone(&self) -> Iter<E> {
240 marker: marker::PhantomData,
245 impl<E: CLike> Iter<E> {
246 fn new(bits: usize) -> Iter<E> {
250 marker: marker::PhantomData,
255 impl<E: CLike> Iterator for Iter<E> {
258 fn next(&mut self) -> Option<E> {
263 while (self.bits & 1) == 0 {
267 let elem = CLike::from_usize(self.index);
273 fn size_hint(&self) -> (usize, Option<usize>) {
274 let exact = self.bits.count_ones() as usize;
279 #[unstable(feature = "fused", issue = "35602")]
280 impl<E: CLike> FusedIterator for Iter<E> {}
282 impl<E: CLike> FromIterator<E> for EnumSet<E> {
283 fn from_iter<I: IntoIterator<Item = E>>(iter: I) -> EnumSet<E> {
284 let mut ret = EnumSet::new();
290 impl<'a, E> IntoIterator for &'a EnumSet<E>
294 type IntoIter = Iter<E>;
296 fn into_iter(self) -> Iter<E> {
301 impl<E: CLike> Extend<E> for EnumSet<E> {
302 fn extend<I: IntoIterator<Item = E>>(&mut self, iter: I) {
303 for element in iter {
304 self.insert(element);
309 impl<'a, E: 'a + CLike + Copy> Extend<&'a E> for EnumSet<E> {
310 fn extend<I: IntoIterator<Item = &'a E>>(&mut self, iter: I) {
311 self.extend(iter.into_iter().cloned());