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 = "37966")]
  20 #![rustc_deprecated(since = "1.16.0", reason = "long since replaced")]
  21 #![allow(deprecated)]
  22
  23 use core::marker;
  24 use core::fmt;
  25 use core::iter::{FromIterator, FusedIterator};
  26 use core::ops::{Sub, BitOr, BitAnd, BitXor};
  27
  28 // FIXME(contentions): implement union family of methods? (general design may be
  29 // wrong here)
  30
  31 /// A specialized set implementation to use enum types.
  32 ///
  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
  41     bits: usize,
  42     marker: marker::PhantomData<E>,
  43 }
  44
  45 impl<E> Copy for EnumSet<E> {}
  46
  47 impl<E> Clone for EnumSet<E> {
  48     fn clone(&self) -> EnumSet<E> {
  49         *self
  50     }
  51 }
  52
  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()
  56     }
  57 }
  58
  59 /// An interface for casting C-like enum to usize and back.
  60 /// A typically implementation is as below.
  61 ///
  62 /// ```{rust,ignore}
  63 /// #[repr(usize)]
  64 /// enum Foo {
  65 ///     A, B, C
  66 /// }
  67 ///
  68 /// impl CLike for Foo {
  69 ///     fn to_usize(&self) -> usize {
  70 ///         *self as usize
  71 ///     }
  72 ///
  73 ///     fn from_usize(v: usize) -> Foo {
  74 ///         unsafe { mem::transmute(v) }
  75 ///     }
  76 /// }
  77 /// ```
  78 pub trait CLike {
  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;
  83 }
  84
  85 fn bit<E: CLike>(e: &E) -> usize {
  86     use core::mem;
  87     let value = e.to_usize();
  88     let bits = mem::size_of::<usize>() * 8;
  89     assert!(value < bits,
  90             "EnumSet only supports up to {} variants.",
  91             bits - 1);
  92     1 << value
  93 }
  94
  95 impl<E: CLike> EnumSet<E> {
  96     /// Returns an empty `EnumSet`.
  97     pub fn new() -> EnumSet<E> {
  98         EnumSet {
  99             bits: 0,
 100             marker: marker::PhantomData,
 101         }
 102     }
 103
 104     /// Returns the number of elements in the given `EnumSet`.
 105     pub fn len(&self) -> usize {
 106         self.bits.count_ones() as usize
 107     }
 108
 109     /// Returns true if the `EnumSet` is empty.
 110     pub fn is_empty(&self) -> bool {
 111         self.bits == 0
 112     }
 113
 114     pub fn clear(&mut self) {
 115         self.bits = 0;
 116     }
 117
 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
 121     }
 122
 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
 126     }
 127
 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)
 131     }
 132
 133     /// Returns the union of both `EnumSets`.
 134     pub fn union(&self, e: EnumSet<E>) -> EnumSet<E> {
 135         EnumSet {
 136             bits: self.bits | e.bits,
 137             marker: marker::PhantomData,
 138         }
 139     }
 140
 141     /// Returns the intersection of both `EnumSets`.
 142     pub fn intersection(&self, e: EnumSet<E>) -> EnumSet<E> {
 143         EnumSet {
 144             bits: self.bits & e.bits,
 145             marker: marker::PhantomData,
 146         }
 147     }
 148
 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);
 153         result
 154     }
 155
 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);
 160         result
 161     }
 162
 163     /// Returns `true` if an `EnumSet` contains a given enum.
 164     pub fn contains(&self, e: &E) -> bool {
 165         (self.bits & bit(e)) != 0
 166     }
 167
 168     /// Returns an iterator over an `EnumSet`.
 169     pub fn iter(&self) -> Iter<E> {
 170         Iter::new(self.bits)
 171     }
 172 }
 173
 174 impl<E: CLike> Sub for EnumSet<E> {
 175     type Output = EnumSet<E>;
 176
 177     fn sub(self, e: EnumSet<E>) -> EnumSet<E> {
 178         EnumSet {
 179             bits: self.bits & !e.bits,
 180             marker: marker::PhantomData,
 181         }
 182     }
 183 }
 184
 185 impl<E: CLike> BitOr for EnumSet<E> {
 186     type Output = EnumSet<E>;
 187
 188     fn bitor(self, e: EnumSet<E>) -> EnumSet<E> {
 189         EnumSet {
 190             bits: self.bits | e.bits,
 191             marker: marker::PhantomData,
 192         }
 193     }
 194 }
 195
 196 impl<E: CLike> BitAnd for EnumSet<E> {
 197     type Output = EnumSet<E>;
 198
 199     fn bitand(self, e: EnumSet<E>) -> EnumSet<E> {
 200         EnumSet {
 201             bits: self.bits & e.bits,
 202             marker: marker::PhantomData,
 203         }
 204     }
 205 }
 206
 207 impl<E: CLike> BitXor for EnumSet<E> {
 208     type Output = EnumSet<E>;
 209
 210     fn bitxor(self, e: EnumSet<E>) -> EnumSet<E> {
 211         EnumSet {
 212             bits: self.bits ^ e.bits,
 213             marker: marker::PhantomData,
 214         }
 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 {
 239             index: 0,
 240             bits: bits,
 241             marker: marker::PhantomData,
 242         }
 243     }
 244 }
 245
 246 impl<E: CLike> Iterator for Iter<E> {
 247     type Item = E;
 248
 249     fn next(&mut self) -> Option<E> {
 250         if self.bits == 0 {
 251             return None;
 252         }
 253
 254         while (self.bits & 1) == 0 {
 255             self.index += 1;
 256             self.bits >>= 1;
 257         }
 258         let elem = CLike::from_usize(self.index);
 259         self.index += 1;
 260         self.bits >>= 1;
 261         Some(elem)
 262     }
 263
 264     fn size_hint(&self) -> (usize, Option<usize>) {
 265         let exact = self.bits.count_ones() as usize;
 266         (exact, Some(exact))
 267     }
 268 }
 269
 270 #[unstable(feature = "fused", issue = "35602")]
 271 impl<E: CLike> FusedIterator for Iter<E> {}
 272
 273 impl<E: CLike> FromIterator<E> for EnumSet<E> {
 274     fn from_iter<I: IntoIterator<Item = E>>(iter: I) -> EnumSet<E> {
 275         let mut ret = EnumSet::new();
 276         ret.extend(iter);
 277         ret
 278     }
 279 }
 280
 281 impl<'a, E> IntoIterator for &'a EnumSet<E>
 282     where E: CLike
 283 {
 284     type Item = E;
 285     type IntoIter = Iter<E>;
 286
 287     fn into_iter(self) -> Iter<E> {
 288         self.iter()
 289     }
 290 }
 291
 292 impl<E: CLike> Extend<E> for EnumSet<E> {
 293     fn extend<I: IntoIterator<Item = E>>(&mut self, iter: I) {
 294         for element in iter {
 295             self.insert(element);
 296         }
 297     }
 298 }
 299
 300 impl<'a, E: 'a + CLike + Copy> Extend<&'a E> for EnumSet<E> {
 301     fn extend<I: IntoIterator<Item = &'a E>>(&mut self, iter: I) {
 302         self.extend(iter.into_iter().cloned());
 303     }
 304 }