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