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::fmt;
  18 use core::num::Int;
  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 #[deriving(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
  29     bits: uint
  30 }
  31
  32 impl<E> Copy for EnumSet<E> {}
  33
  34 impl<E:CLike+fmt::Show> fmt::Show for EnumSet<E> {
  35     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
  36         try!(write!(fmt, "{{"));
  37         let mut first = true;
  38         for e in self.iter() {
  39             if !first {
  40                 try!(write!(fmt, ", "));
  41             }
  42             try!(write!(fmt, "{}", e));
  43             first = false;
  44         }
  45         write!(fmt, "}}")
  46     }
  47 }
  48
  49 /// An interface for casting C-like enum to uint and back.
  50 /// A typically implementation is as below.
  51 ///
  52 /// ```{rust,ignore}
  53 /// #[repr(uint)]
  54 /// enum Foo {
  55 ///     A, B, C
  56 /// }
  57 ///
  58 /// impl CLike for Foo {
  59 ///     fn to_uint(&self) -> uint {
  60 ///         *self as uint
  61 ///     }
  62 ///
  63 ///     fn from_uint(v: uint) -> Foo {
  64 ///         unsafe { mem::transmute(v) }
  65 ///     }
  66 /// }
  67 /// ```
  68 pub trait CLike {
  69     /// Converts a C-like enum to a `uint`.
  70     fn to_uint(&self) -> uint;
  71     /// Converts a `uint` to a C-like enum.
  72     fn from_uint(uint) -> Self;
  73 }
  74
  75 fn bit<E:CLike>(e: &E) -> uint {
  76     use core::uint;
  77     let value = e.to_uint();
  78     assert!(value < uint::BITS,
  79             "EnumSet only supports up to {} variants.", uint::BITS - 1);
  80     1 << value
  81 }
  82
  83 impl<E:CLike> EnumSet<E> {
  84     /// Deprecated: Renamed to `new`.
  85     #[deprecated = "Renamed to `new`"]
  86     pub fn empty() -> EnumSet<E> {
  87         EnumSet::new()
  88     }
  89
  90     /// Returns an empty `EnumSet`.
  91     #[unstable = "matches collection reform specification, waiting for dust to settle"]
  92     pub fn new() -> EnumSet<E> {
  93         EnumSet {bits: 0}
  94     }
  95
  96     /// Returns the number of elements in the given `EnumSet`.
  97     #[unstable = "matches collection reform specification, waiting for dust to settle"]
  98     pub fn len(&self) -> uint {
  99         self.bits.count_ones()
 100     }
 101
 102     /// Returns true if the `EnumSet` is empty.
 103     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 104     pub fn is_empty(&self) -> bool {
 105         self.bits == 0
 106     }
 107
 108     pub fn clear(&mut self) {
 109         self.bits = 0;
 110     }
 111
 112     /// Returns `true` if the `EnumSet` contains any enum of the given `EnumSet`.
 113     /// Deprecated: Use `is_disjoint`.
 114     #[deprecated = "Use `is_disjoint`"]
 115     pub fn intersects(&self, e: EnumSet<E>) -> bool {
 116         !self.is_disjoint(&e)
 117     }
 118
 119     /// Returns `false` if the `EnumSet` contains any enum of the given `EnumSet`.
 120     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 121     pub fn is_disjoint(&self, other: &EnumSet<E>) -> bool {
 122         (self.bits & other.bits) == 0
 123     }
 124
 125     /// Returns `true` if a given `EnumSet` is included in this `EnumSet`.
 126     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 127     pub fn is_superset(&self, other: &EnumSet<E>) -> bool {
 128         (self.bits & other.bits) == other.bits
 129     }
 130
 131     /// Returns `true` if this `EnumSet` is included in the given `EnumSet`.
 132     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 133     pub fn is_subset(&self, other: &EnumSet<E>) -> bool {
 134         other.is_superset(self)
 135     }
 136
 137     /// Returns the union of both `EnumSets`.
 138     pub fn union(&self, e: EnumSet<E>) -> EnumSet<E> {
 139         EnumSet {bits: self.bits | e.bits}
 140     }
 141
 142     /// Returns the intersection of both `EnumSets`.
 143     pub fn intersection(&self, e: EnumSet<E>) -> EnumSet<E> {
 144         EnumSet {bits: self.bits & e.bits}
 145     }
 146
 147     /// Deprecated: Use `insert`.
 148     #[deprecated = "Use `insert`"]
 149     pub fn add(&mut self, e: E) {
 150         self.insert(e);
 151     }
 152
 153     /// Adds an enum to the `EnumSet`, and returns `true` if it wasn't there before
 154     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 155     pub fn insert(&mut self, e: E) -> bool {
 156         let result = !self.contains(&e);
 157         self.bits |= bit(&e);
 158         result
 159     }
 160
 161     /// Removes an enum from the EnumSet
 162     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 163     pub fn remove(&mut self, e: &E) -> bool {
 164         let result = self.contains(e);
 165         self.bits &= !bit(e);
 166         result
 167     }
 168
 169     /// Deprecated: use `contains`.
 170     #[deprecated = "use `contains"]
 171     pub fn contains_elem(&self, e: E) -> bool {
 172         self.contains(&e)
 173     }
 174
 175     /// Returns `true` if an `EnumSet` contains a given enum.
 176     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 177     pub fn contains(&self, e: &E) -> bool {
 178         (self.bits & bit(e)) != 0
 179     }
 180
 181     /// Returns an iterator over an `EnumSet`.
 182     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 183     pub fn iter(&self) -> Iter<E> {
 184         Iter::new(self.bits)
 185     }
 186 }
 187
 188 impl<E:CLike> Sub for EnumSet<E> {
 189     type Output = EnumSet<E>;
 190
 191     fn sub(self, e: EnumSet<E>) -> EnumSet<E> {
 192         EnumSet {bits: self.bits & !e.bits}
 193     }
 194 }
 195
 196 impl<E:CLike> BitOr for EnumSet<E> {
 197     type Output = EnumSet<E>;
 198
 199     fn bitor(self, e: EnumSet<E>) -> EnumSet<E> {
 200         EnumSet {bits: self.bits | e.bits}
 201     }
 202 }
 203
 204 impl<E:CLike> BitAnd for EnumSet<E> {
 205     type Output = EnumSet<E>;
 206
 207     fn bitand(self, e: EnumSet<E>) -> EnumSet<E> {
 208         EnumSet {bits: self.bits & e.bits}
 209     }
 210 }
 211
 212 impl<E:CLike> BitXor for EnumSet<E> {
 213     type Output = EnumSet<E>;
 214
 215     fn bitxor(self, e: EnumSet<E>) -> EnumSet<E> {
 216         EnumSet {bits: self.bits ^ e.bits}
 217     }
 218 }
 219
 220 /// An iterator over an EnumSet
 221 pub struct Iter<E> {
 222     index: uint,
 223     bits: uint,
 224 }
 225
 226 // FIXME(#19839) Remove in favor of `#[deriving(Clone)]`
 227 impl<E> Clone for Iter<E> {
 228     fn clone(&self) -> Iter<E> {
 229         Iter {
 230             index: self.index,
 231             bits: self.bits,
 232         }
 233     }
 234 }
 235
 236 impl<E:CLike> Iter<E> {
 237     fn new(bits: uint) -> Iter<E> {
 238         Iter { index: 0, bits: bits }
 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_uint(self.index);
 255         self.index += 1;
 256         self.bits >>= 1;
 257         Some(elem)
 258     }
 259
 260     fn size_hint(&self) -> (uint, Option<uint>) {
 261         let exact = self.bits.count_ones();
 262         (exact, Some(exact))
 263     }
 264 }
 265
 266 impl<E:CLike> FromIterator<E> for EnumSet<E> {
 267     fn from_iter<I:Iterator<Item=E>>(iterator: I) -> EnumSet<E> {
 268         let mut ret = EnumSet::new();
 269         ret.extend(iterator);
 270         ret
 271     }
 272 }
 273
 274 impl<E:CLike> Extend<E> for EnumSet<E> {
 275     fn extend<I: Iterator<Item=E>>(&mut self, mut iterator: I) {
 276         for element in iterator {
 277             self.insert(element);
 278         }
 279     }
 280 }
 281
 282 #[cfg(test)]
 283 mod test {
 284     use self::Foo::*;
 285     use prelude::*;
 286     use core::mem;
 287
 288     use super::{EnumSet, CLike};
 289
 290     #[deriving(Copy, PartialEq, Show)]
 291     #[repr(uint)]
 292     enum Foo {
 293         A, B, C
 294     }
 295
 296     impl CLike for Foo {
 297         fn to_uint(&self) -> uint {
 298             *self as uint
 299         }
 300
 301         fn from_uint(v: uint) -> Foo {
 302             unsafe { mem::transmute(v) }
 303         }
 304     }
 305
 306     #[test]
 307     fn test_new() {
 308         let e: EnumSet<Foo> = EnumSet::new();
 309         assert!(e.is_empty());
 310     }
 311
 312     #[test]
 313     fn test_show() {
 314         let mut e = EnumSet::new();
 315         assert_eq!("{}", e.to_string());
 316         e.insert(A);
 317         assert_eq!("{A}", e.to_string());
 318         e.insert(C);
 319         assert_eq!("{A, C}", e.to_string());
 320     }
 321
 322     #[test]
 323     fn test_len() {
 324         let mut e = EnumSet::new();
 325         assert_eq!(e.len(), 0);
 326         e.insert(A);
 327         e.insert(B);
 328         e.insert(C);
 329         assert_eq!(e.len(), 3);
 330         e.remove(&A);
 331         assert_eq!(e.len(), 2);
 332         e.clear();
 333         assert_eq!(e.len(), 0);
 334     }
 335
 336     ///////////////////////////////////////////////////////////////////////////
 337     // intersect
 338
 339     #[test]
 340     fn test_two_empties_do_not_intersect() {
 341         let e1: EnumSet<Foo> = EnumSet::new();
 342         let e2: EnumSet<Foo> = EnumSet::new();
 343         assert!(e1.is_disjoint(&e2));
 344     }
 345
 346     #[test]
 347     fn test_empty_does_not_intersect_with_full() {
 348         let e1: EnumSet<Foo> = EnumSet::new();
 349
 350         let mut e2: EnumSet<Foo> = EnumSet::new();
 351         e2.insert(A);
 352         e2.insert(B);
 353         e2.insert(C);
 354
 355         assert!(e1.is_disjoint(&e2));
 356     }
 357
 358     #[test]
 359     fn test_disjoint_intersects() {
 360         let mut e1: EnumSet<Foo> = EnumSet::new();
 361         e1.insert(A);
 362
 363         let mut e2: EnumSet<Foo> = EnumSet::new();
 364         e2.insert(B);
 365
 366         assert!(e1.is_disjoint(&e2));
 367     }
 368
 369     #[test]
 370     fn test_overlapping_intersects() {
 371         let mut e1: EnumSet<Foo> = EnumSet::new();
 372         e1.insert(A);
 373
 374         let mut e2: EnumSet<Foo> = EnumSet::new();
 375         e2.insert(A);
 376         e2.insert(B);
 377
 378         assert!(!e1.is_disjoint(&e2));
 379     }
 380
 381     ///////////////////////////////////////////////////////////////////////////
 382     // contains and contains_elem
 383
 384     #[test]
 385     fn test_superset() {
 386         let mut e1: EnumSet<Foo> = EnumSet::new();
 387         e1.insert(A);
 388
 389         let mut e2: EnumSet<Foo> = EnumSet::new();
 390         e2.insert(A);
 391         e2.insert(B);
 392
 393         let mut e3: EnumSet<Foo> = EnumSet::new();
 394         e3.insert(C);
 395
 396         assert!(e1.is_subset(&e2));
 397         assert!(e2.is_superset(&e1));
 398         assert!(!e3.is_superset(&e2));
 399         assert!(!e2.is_superset(&e3))
 400     }
 401
 402     #[test]
 403     fn test_contains() {
 404         let mut e1: EnumSet<Foo> = EnumSet::new();
 405         e1.insert(A);
 406         assert!(e1.contains(&A));
 407         assert!(!e1.contains(&B));
 408         assert!(!e1.contains(&C));
 409
 410         e1.insert(A);
 411         e1.insert(B);
 412         assert!(e1.contains(&A));
 413         assert!(e1.contains(&B));
 414         assert!(!e1.contains(&C));
 415     }
 416
 417     ///////////////////////////////////////////////////////////////////////////
 418     // iter
 419
 420     #[test]
 421     fn test_iterator() {
 422         let mut e1: EnumSet<Foo> = EnumSet::new();
 423
 424         let elems: ::vec::Vec<Foo> = e1.iter().collect();
 425         assert!(elems.is_empty());
 426
 427         e1.insert(A);
 428         let elems: ::vec::Vec<_> = e1.iter().collect();
 429         assert_eq!(vec![A], elems);
 430
 431         e1.insert(C);
 432         let elems: ::vec::Vec<_> = e1.iter().collect();
 433         assert_eq!(vec![A,C], elems);
 434
 435         e1.insert(C);
 436         let elems: ::vec::Vec<_> = e1.iter().collect();
 437         assert_eq!(vec![A,C], elems);
 438
 439         e1.insert(B);
 440         let elems: ::vec::Vec<_> = e1.iter().collect();
 441         assert_eq!(vec![A,B,C], elems);
 442     }
 443
 444     ///////////////////////////////////////////////////////////////////////////
 445     // operators
 446
 447     #[test]
 448     fn test_operators() {
 449         let mut e1: EnumSet<Foo> = EnumSet::new();
 450         e1.insert(A);
 451         e1.insert(C);
 452
 453         let mut e2: EnumSet<Foo> = EnumSet::new();
 454         e2.insert(B);
 455         e2.insert(C);
 456
 457         let e_union = e1 | e2;
 458         let elems: ::vec::Vec<_> = e_union.iter().collect();
 459         assert_eq!(vec![A,B,C], elems);
 460
 461         let e_intersection = e1 & e2;
 462         let elems: ::vec::Vec<_> = e_intersection.iter().collect();
 463         assert_eq!(vec![C], elems);
 464
 465         // Another way to express intersection
 466         let e_intersection = e1 - (e1 - e2);
 467         let elems: ::vec::Vec<_> = e_intersection.iter().collect();
 468         assert_eq!(vec![C], elems);
 469
 470         let e_subtract = e1 - e2;
 471         let elems: ::vec::Vec<_> = e_subtract.iter().collect();
 472         assert_eq!(vec![A], elems);
 473
 474         // Bitwise XOR of two sets, aka symmetric difference
 475         let e_symmetric_diff = e1 ^ e2;
 476         let elems: ::vec::Vec<_> = e_symmetric_diff.iter().collect();
 477         assert_eq!(vec![A,B], elems);
 478
 479         // Another way to express symmetric difference
 480         let e_symmetric_diff = (e1 - e2) | (e2 - e1);
 481         let elems: ::vec::Vec<_> = e_symmetric_diff.iter().collect();
 482         assert_eq!(vec![A,B], elems);
 483
 484         // Yet another way to express symmetric difference
 485         let e_symmetric_diff = (e1 | e2) - (e1 & e2);
 486         let elems: ::vec::Vec<_> = e_symmetric_diff.iter().collect();
 487         assert_eq!(vec![A,B], elems);
 488     }
 489
 490     #[test]
 491     #[should_fail]
 492     fn test_overflow() {
 493         #[allow(dead_code)]
 494         #[deriving(Copy)]
 495         #[repr(uint)]
 496         enum Bar {
 497             V00, V01, V02, V03, V04, V05, V06, V07, V08, V09,
 498             V10, V11, V12, V13, V14, V15, V16, V17, V18, V19,
 499             V20, V21, V22, V23, V24, V25, V26, V27, V28, V29,
 500             V30, V31, V32, V33, V34, V35, V36, V37, V38, V39,
 501             V40, V41, V42, V43, V44, V45, V46, V47, V48, V49,
 502             V50, V51, V52, V53, V54, V55, V56, V57, V58, V59,
 503             V60, V61, V62, V63, V64, V65, V66, V67, V68, V69,
 504         }
 505
 506         impl CLike for Bar {
 507             fn to_uint(&self) -> uint {
 508                 *self as uint
 509             }
 510
 511             fn from_uint(v: uint) -> Bar {
 512                 unsafe { mem::transmute(v) }
 513             }
 514         }
 515         let mut set = EnumSet::new();
 516         set.insert(Bar::V64);
 517     }
 518 }