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.
19 use core::iter::{FromIterator, IntoIterator};
20 use core::ops::{Sub, BitOr, BitAnd, BitXor};
22 // FIXME(contentions): implement union family of methods? (general design may be wrong here)
24 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
25 /// A specialized set implementation to use enum types.
26 pub struct EnumSet<E> {
27 // We must maintain the invariant that no bits are set
28 // for which no variant exists
32 impl<E> Copy for EnumSet<E> {}
34 #[stable(feature = "rust1", since = "1.0.0")]
35 impl<E:CLike + fmt::Debug> fmt::Debug for EnumSet<E> {
36 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
37 try!(write!(fmt, "EnumSet {{"));
41 try!(write!(fmt, ", "));
43 try!(write!(fmt, "{:?}", e));
50 /// An interface for casting C-like enum to uint and back.
51 /// A typically implementation is as below.
59 /// impl CLike for Foo {
60 /// fn to_uint(&self) -> uint {
64 /// fn from_uint(v: uint) -> Foo {
65 /// unsafe { mem::transmute(v) }
70 /// Converts a C-like enum to a `uint`.
71 fn to_uint(&self) -> uint;
72 /// Converts a `uint` to a C-like enum.
73 fn from_uint(uint) -> Self;
76 fn bit<E:CLike>(e: &E) -> uint {
78 let value = e.to_uint();
79 assert!(value < uint::BITS,
80 "EnumSet only supports up to {} variants.", uint::BITS - 1);
84 impl<E:CLike> EnumSet<E> {
85 /// Returns an empty `EnumSet`.
86 #[unstable(feature = "collections",
87 reason = "matches collection reform specification, waiting for dust to settle")]
88 pub fn new() -> EnumSet<E> {
92 /// Returns the number of elements in the given `EnumSet`.
93 #[unstable(feature = "collections",
94 reason = "matches collection reform specification, waiting for dust to settle")]
95 pub fn len(&self) -> uint {
96 self.bits.count_ones()
99 /// Returns true if the `EnumSet` is empty.
100 #[unstable(feature = "collections",
101 reason = "matches collection reform specification, waiting for dust to settle")]
102 pub fn is_empty(&self) -> bool {
106 pub fn clear(&mut self) {
110 /// Returns `false` if the `EnumSet` contains any enum of the given `EnumSet`.
111 #[unstable(feature = "collections",
112 reason = "matches collection reform specification, waiting for dust to settle")]
113 pub fn is_disjoint(&self, other: &EnumSet<E>) -> bool {
114 (self.bits & other.bits) == 0
117 /// Returns `true` if a given `EnumSet` is included in this `EnumSet`.
118 #[unstable(feature = "collections",
119 reason = "matches collection reform specification, waiting for dust to settle")]
120 pub fn is_superset(&self, other: &EnumSet<E>) -> bool {
121 (self.bits & other.bits) == other.bits
124 /// Returns `true` if this `EnumSet` is included in the given `EnumSet`.
125 #[unstable(feature = "collections",
126 reason = "matches collection reform specification, waiting for dust to settle")]
127 pub fn is_subset(&self, other: &EnumSet<E>) -> bool {
128 other.is_superset(self)
131 /// Returns the union of both `EnumSets`.
132 pub fn union(&self, e: EnumSet<E>) -> EnumSet<E> {
133 EnumSet {bits: self.bits | e.bits}
136 /// Returns the intersection of both `EnumSets`.
137 pub fn intersection(&self, e: EnumSet<E>) -> EnumSet<E> {
138 EnumSet {bits: self.bits & e.bits}
141 /// Adds an enum to the `EnumSet`, and returns `true` if it wasn't there before
142 #[unstable(feature = "collections",
143 reason = "matches collection reform specification, waiting for dust to settle")]
144 pub fn insert(&mut self, e: E) -> bool {
145 let result = !self.contains(&e);
146 self.bits |= bit(&e);
150 /// Removes an enum from the EnumSet
151 #[unstable(feature = "collections",
152 reason = "matches collection reform specification, waiting for dust to settle")]
153 pub fn remove(&mut self, e: &E) -> bool {
154 let result = self.contains(e);
155 self.bits &= !bit(e);
159 /// Returns `true` if an `EnumSet` contains a given enum.
160 #[unstable(feature = "collections",
161 reason = "matches collection reform specification, waiting for dust to settle")]
162 pub fn contains(&self, e: &E) -> bool {
163 (self.bits & bit(e)) != 0
166 /// Returns an iterator over an `EnumSet`.
167 #[unstable(feature = "collections",
168 reason = "matches collection reform specification, waiting for dust to settle")]
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> {
178 EnumSet {bits: self.bits & !e.bits}
182 impl<E:CLike> BitOr for EnumSet<E> {
183 type Output = EnumSet<E>;
185 fn bitor(self, e: EnumSet<E>) -> EnumSet<E> {
186 EnumSet {bits: self.bits | e.bits}
190 impl<E:CLike> BitAnd for EnumSet<E> {
191 type Output = EnumSet<E>;
193 fn bitand(self, e: EnumSet<E>) -> EnumSet<E> {
194 EnumSet {bits: self.bits & e.bits}
198 impl<E:CLike> BitXor for EnumSet<E> {
199 type Output = EnumSet<E>;
201 fn bitxor(self, e: EnumSet<E>) -> EnumSet<E> {
202 EnumSet {bits: self.bits ^ e.bits}
206 /// An iterator over an EnumSet
212 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
213 impl<E> Clone for Iter<E> {
214 fn clone(&self) -> Iter<E> {
222 impl<E:CLike> Iter<E> {
223 fn new(bits: uint) -> Iter<E> {
224 Iter { index: 0, bits: bits }
228 impl<E:CLike> Iterator for Iter<E> {
231 fn next(&mut self) -> Option<E> {
236 while (self.bits & 1) == 0 {
240 let elem = CLike::from_uint(self.index);
246 fn size_hint(&self) -> (uint, Option<uint>) {
247 let exact = self.bits.count_ones();
252 impl<E:CLike> FromIterator<E> for EnumSet<E> {
253 fn from_iter<I:Iterator<Item=E>>(iterator: I) -> EnumSet<E> {
254 let mut ret = EnumSet::new();
255 ret.extend(iterator);
260 impl<'a, E> IntoIterator for &'a EnumSet<E> where E: CLike {
263 fn into_iter(self) -> Iter<E> {
268 impl<E:CLike> Extend<E> for EnumSet<E> {
269 fn extend<I: Iterator<Item=E>>(&mut self, iterator: I) {
270 for element in iterator {
271 self.insert(element);
282 use super::{EnumSet, CLike};
284 #[derive(Copy, PartialEq, Debug)]
291 fn to_uint(&self) -> uint {
295 fn from_uint(v: uint) -> Foo {
296 unsafe { mem::transmute(v) }
302 let e: EnumSet<Foo> = EnumSet::new();
303 assert!(e.is_empty());
308 let mut e = EnumSet::new();
309 assert!(format!("{:?}", e) == "EnumSet {}");
311 assert!(format!("{:?}", e) == "EnumSet {A}");
313 assert!(format!("{:?}", e) == "EnumSet {A, C}");
318 let mut e = EnumSet::new();
319 assert_eq!(e.len(), 0);
323 assert_eq!(e.len(), 3);
325 assert_eq!(e.len(), 2);
327 assert_eq!(e.len(), 0);
330 ///////////////////////////////////////////////////////////////////////////
334 fn test_two_empties_do_not_intersect() {
335 let e1: EnumSet<Foo> = EnumSet::new();
336 let e2: EnumSet<Foo> = EnumSet::new();
337 assert!(e1.is_disjoint(&e2));
341 fn test_empty_does_not_intersect_with_full() {
342 let e1: EnumSet<Foo> = EnumSet::new();
344 let mut e2: EnumSet<Foo> = EnumSet::new();
349 assert!(e1.is_disjoint(&e2));
353 fn test_disjoint_intersects() {
354 let mut e1: EnumSet<Foo> = EnumSet::new();
357 let mut e2: EnumSet<Foo> = EnumSet::new();
360 assert!(e1.is_disjoint(&e2));
364 fn test_overlapping_intersects() {
365 let mut e1: EnumSet<Foo> = EnumSet::new();
368 let mut e2: EnumSet<Foo> = EnumSet::new();
372 assert!(!e1.is_disjoint(&e2));
375 ///////////////////////////////////////////////////////////////////////////
376 // contains and contains_elem
380 let mut e1: EnumSet<Foo> = EnumSet::new();
383 let mut e2: EnumSet<Foo> = EnumSet::new();
387 let mut e3: EnumSet<Foo> = EnumSet::new();
390 assert!(e1.is_subset(&e2));
391 assert!(e2.is_superset(&e1));
392 assert!(!e3.is_superset(&e2));
393 assert!(!e2.is_superset(&e3))
398 let mut e1: EnumSet<Foo> = EnumSet::new();
400 assert!(e1.contains(&A));
401 assert!(!e1.contains(&B));
402 assert!(!e1.contains(&C));
406 assert!(e1.contains(&A));
407 assert!(e1.contains(&B));
408 assert!(!e1.contains(&C));
411 ///////////////////////////////////////////////////////////////////////////
416 let mut e1: EnumSet<Foo> = EnumSet::new();
418 let elems: ::vec::Vec<Foo> = e1.iter().collect();
419 assert!(elems.is_empty());
422 let elems: ::vec::Vec<_> = e1.iter().collect();
423 assert_eq!(vec![A], elems);
426 let elems: ::vec::Vec<_> = e1.iter().collect();
427 assert_eq!(vec![A,C], elems);
430 let elems: ::vec::Vec<_> = e1.iter().collect();
431 assert_eq!(vec![A,C], elems);
434 let elems: ::vec::Vec<_> = e1.iter().collect();
435 assert_eq!(vec![A,B,C], elems);
438 ///////////////////////////////////////////////////////////////////////////
442 fn test_operators() {
443 let mut e1: EnumSet<Foo> = EnumSet::new();
447 let mut e2: EnumSet<Foo> = EnumSet::new();
451 let e_union = e1 | e2;
452 let elems: ::vec::Vec<_> = e_union.iter().collect();
453 assert_eq!(vec![A,B,C], elems);
455 let e_intersection = e1 & e2;
456 let elems: ::vec::Vec<_> = e_intersection.iter().collect();
457 assert_eq!(vec![C], elems);
459 // Another way to express intersection
460 let e_intersection = e1 - (e1 - e2);
461 let elems: ::vec::Vec<_> = e_intersection.iter().collect();
462 assert_eq!(vec![C], elems);
464 let e_subtract = e1 - e2;
465 let elems: ::vec::Vec<_> = e_subtract.iter().collect();
466 assert_eq!(vec![A], elems);
468 // Bitwise XOR of two sets, aka symmetric difference
469 let e_symmetric_diff = e1 ^ e2;
470 let elems: ::vec::Vec<_> = e_symmetric_diff.iter().collect();
471 assert_eq!(vec![A,B], elems);
473 // Another way to express symmetric difference
474 let e_symmetric_diff = (e1 - e2) | (e2 - e1);
475 let elems: ::vec::Vec<_> = e_symmetric_diff.iter().collect();
476 assert_eq!(vec![A,B], elems);
478 // Yet another way to express symmetric difference
479 let e_symmetric_diff = (e1 | e2) - (e1 & e2);
480 let elems: ::vec::Vec<_> = e_symmetric_diff.iter().collect();
481 assert_eq!(vec![A,B], elems);
491 V00, V01, V02, V03, V04, V05, V06, V07, V08, V09,
492 V10, V11, V12, V13, V14, V15, V16, V17, V18, V19,
493 V20, V21, V22, V23, V24, V25, V26, V27, V28, V29,
494 V30, V31, V32, V33, V34, V35, V36, V37, V38, V39,
495 V40, V41, V42, V43, V44, V45, V46, V47, V48, V49,
496 V50, V51, V52, V53, V54, V55, V56, V57, V58, V59,
497 V60, V61, V62, V63, V64, V65, V66, V67, V68, V69,
501 fn to_uint(&self) -> uint {
505 fn from_uint(v: uint) -> Bar {
506 unsafe { mem::transmute(v) }
509 let mut set = EnumSet::new();
510 set.insert(Bar::V64);