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