1  package frost.collections
  2  
  3  ====================================================================================================
  4  An implementation of the set abstract data type. Sets are collections which cannot contain duplicate
  5  entries; adding an element which already exists to a set does not do anything.
  6  ====================================================================================================
  7  class HashSet<T:HashKey<T>> : Collection<T> {
  8      @private
  9      def contents := HashMap<T, T>()
 10  
 11      ================================================================================================
 12      Creates a new empty set.
 13      ================================================================================================
 14      init() {
 15      }
 16  
 17      ================================================================================================
 18      Creates a new set containing all of the elements from another collection. Duplicate entries are
 19      filtered out, so
 20  
 21          -- testcase HashSetInit
 22          HashSet<Int>(list).count
 23  
 24      is an easy way to determine how many unique entries `list` contains.
 25      ================================================================================================
 26      init(c:CollectionView<T>) {
 27          addAll(c)
 28      }
 29  
 30      @override
 31      method add(value:T) {
 32          contents[value] := value
 33      }
 34  
 35      @override
 36      method addAll(c:CollectionView<T>) {
 37          for v in c {
 38              add(v)
 39          }
 40      }
 41  
 42      ================================================================================================
 43      Removes an entry from the set, if present.
 44      ================================================================================================
 45      method remove(value:T) {
 46          contents.remove(value)
 47      }
 48  
 49      @override
 50      function get_count():Int {
 51          return contents.count
 52      }
 53  
 54      @override
 55      method clear() {
 56          contents.clear()
 57      }
 58  
 59      @override
 60      function get_iterator():Iterator<T> {
 61          return contents.keys
 62      }
 63  
 64      ================================================================================================
 65      Returns `true` if the value is present in the set.
 66      ================================================================================================
 67      function contains(value:T):Bit {
 68          return contents.contains(value)
 69      }
 70  
 71      @override
 72      method filterInPlace(test:(T)=>(Bit)) {
 73          contents.filterInPlace((k, v) => test(k))
 74      }
 75  
 76      @override
 77      method mapInPlace(f:(T)=>(T)) {
 78          for (k, v) in contents.entries {
 79              contents[k] := f(v)     
 80          }
 81      }
 82  
 83      @override
 84      function get_toString():String {
 85          def result := MutableString("[")
 86          var separator := ""
 87          for v in contents.keys {
 88              result.append(separator)
 89              -- FIXME cast shouldn't be necessary
 90              if v->Object? !== null {
 91                  result.append(v)
 92              }
 93              else {
 94                  result.append("<null>")
 95              }
 96              separator := ", "
 97          }
 98          result.append("]")
 99          return result.finish()
100      }
101  }
102