set.pony

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
use mut = "collections"

type Set[A: (mut.Hashable val & Equatable[A])] is HashSet[A, mut.HashEq[A]]

type SetIs[A: Any #share] is HashSet[A, mut.HashIs[A]]

class val HashSet[A: Any #share, H: mut.HashFunction[A] val]
  is Comparable[HashSet[A, H] box]
  """
  A set, built on top of persistent Map. This is implemented as map of an
  alias of a type to itself.
  """
  let _map: HashMap[A, A, H]

  new val create() =>
    _map = HashMap[A, A, H]

  new val _create(map': HashMap[A, A, H]) =>
    _map = map'

  fun size(): USize =>
    """
    Return the number of elements in the set.
    """
    _map.size()

  fun apply(value: val->A): val->A ? =>
    """
    Return the value if it is in the set, otherwise raise an error.
    """
    _map(value)?

  fun contains(value: val->A): Bool =>
    """
    Check whether the set contains the value.
    """
    _map.contains(value)

  fun val add(value: val->A): HashSet[A, H] =>
    """
    Return a set with the value added.
    """
    _create(_map(value) = value)

  fun val sub(value: val->A): HashSet[A, H] =>
    """
    Return a set with the value removed.
    """
    try _create(_map.remove(value)?) else this end

  fun val op_or(that: (HashSet[A, H] | Iterator[A])): HashSet[A, H] =>
    """
    Return a set with the elements of both this and that.
    """
    let iter =
      match that
      | let s: HashSet[A, H] => s.values()
      | let i: Iterator[A] => i
      end
    var s' = this
    for v in iter do
      s' = s' + v
    end
    s'

  fun val op_and(that: (HashSet[A, H] | Iterator[A])): HashSet[A, H] =>
    """
    Return a set with the elements that are in both this and that.
    """
    let iter =
      match that
      | let s: HashSet[A, H] => s.values()
      | let i: Iterator[A] => i
      end
    var s' = create()
    for v in iter do
      if contains(v) then
        s' = s' + v
      end
    end
    s'

  fun val op_xor(that: (HashSet[A, H] | Iterator[A])): HashSet[A, H] =>
    """
    Return a set with elements that are in either this or that, but not both.
    """
    let iter =
      match that
      | let s: HashSet[A, H] => s.values()
      | let i: Iterator[A] => i
      end
    var s' = this
    for v in iter do
      if contains(v) then
        s' = s' - v
      else
        s' = s' + v
      end
    end
    s'

  fun val without(that: (HashSet[A, H] | Iterator[A])): HashSet[A, H] =>
    """
    Return a set with the elements of this that are not in that.
    """
    let iter =
      match that
      | let s: HashSet[A, H] => s.values()
      | let i: Iterator[A] => i
      end
    var s' = this
    for v in iter do
      if contains(v) then
        s' = s' - v
      end
    end
    s'

  fun eq(that: HashSet[A, H] box): Bool =>
    """
    Return true if this and that contain the same elements.
    """
    (size() == that.size()) and (this <= that)

  fun lt(that: HashSet[A, H] box): Bool =>
    """
    Return true if every element in this is also in that, and this has fewer
    elements than that.
    """
    (size() < that.size()) and (this <= that)

  fun le(that: HashSet[A, H] box): Bool =>
    """
    Return true if every element in this is also in that.
    """
    for v in values() do
      if not that.contains(v) then return false end
    end
    true

  fun gt(that: HashSet[A, H] box): Bool =>
    """
    Return true if every element in that is also in this, and this has more
    elements than that.
    """
    (size() > that.size()) and (that <= this)

  fun ge(that: HashSet[A, H] box): Bool =>
    """
    Return true if every element in that is also in this.
    """
    that <= this

  fun values(): Iterator[A]^ =>
    """
    Return an iterator over the values in the set.
    """
    _map.values()