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 #[allow(deprecated)]
  85 fn bit<E: CLike>(e: &E) -> usize {
  86     use core::usize;
  87     let value = e.to_usize();
  88     assert!(value < usize::BITS,
  89             "EnumSet only supports up to {} variants.",
  90             usize::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 }