type Set[A: (Hashable #read & Equatable[A] #read)] is HashSet[A, HashEq[A]]
type SetIs[A] is HashSet[A, HashIs[A!]]
class HashSet[A, H: HashFunction[A!] val] is Comparable[HashSet[A, H] box]
"""
A set, built on top of a HashMap. This is implemented as map of an alias of
a type to itself
"""
embed _map: HashMap[A!, A, H]
new create(prealloc: USize = 8) =>
"""
Defaults to a prealloc of 8.
"""
_map = _map.create(prealloc)
fun size(): USize =>
"""
The number of items in the set.
"""
_map.size()
fun space(): USize =>
"""
The available space in the set.
"""
_map.space()
fun apply(value: box->A!): this->A ? =>
"""
Return the value if its in the set, otherwise raise an error.
"""
_map(value)?
fun contains(value: box->A!): Bool =>
"""
Checks whether the set contains the value.
"""
_map.contains(value)
fun ref clear() =>
"""
Remove all elements from the set.
"""
_map.clear()
fun ref set(value: A) =>
"""
Add a value to the set.
"""
_map(value) = consume value
fun ref unset(value: box->A!) =>
"""
Remove a value from the set.
"""
try _map.remove(value)? end
fun ref extract(value: box->A!): A^ ? =>
"""
Remove a value from the set and return it. Raises an error if the value
wasn't in the set.
"""
_map.remove(value)?._2
fun ref union(that: Iterator[A^]) =>
"""
Add everything in that to the set.
"""
for value in that do
set(consume value)
end
fun ref intersect[K: HashFunction[box->A!] val = H](
that: HashSet[box->A!, K])
=>
"""
Remove everything that isn't in that.
"""
let start_size = _map.size()
var seen: USize = 0
var i: USize = -1
while seen < start_size do
try
i = next_index(i)?
if not that.contains(index(i)?) then
unset(index(i)?)
end
end
seen = seen + 1
end
fun ref difference(that: Iterator[A^]) =>
"""
Remove elements in this which are also in that. Add elements in that which
are not in this.
"""
for value in that do
try
extract(value)?
else
set(consume value)
end
end
fun ref remove(that: Iterator[box->A!]) =>
"""
Remove everything that is in that.
"""
for value in that do
unset(value)
end
fun add[K: HashFunction[this->A!] val = H](
value: this->A!)
: HashSet[this->A!, K]^
=>
"""
Add a value to the set.
"""
clone[K]() .> set(value)
fun sub[K: HashFunction[this->A!] val = H](
value: box->this->A!)
: HashSet[this->A!, K]^
=>
"""
Remove a value from the set.
"""
clone[K]() .> unset(value)
fun op_or[K: HashFunction[this->A!] val = H](
that: this->HashSet[A, H])
: HashSet[this->A!, K]^
=>
"""
Create a set with the elements of both this and that.
"""
let r = clone[K]()
for value in that.values() do
r.set(value)
end
r
fun op_and[K: HashFunction[this->A!] val = H](
that: this->HashSet[A, H])
: HashSet[this->A!, K]^
=>
"""
Create a set with the elements that are in both this and that.
"""
let r = HashSet[this->A!, K](size().min(that.size()))
for value in values() do
try
that(value)?
r.set(value)
end
end
r
fun op_xor[K: HashFunction[this->A!] val = H](
that: this->HashSet[A, H])
: HashSet[this->A!, K]^
=>
"""
Create a set with the elements that are in either set but not both.
"""
let r = HashSet[this->A!, K](size().max(that.size()))
for value in values() do
try
that(value)?
else
r.set(value)
end
end
for value in that.values() do
try
this(value)?
else
r.set(value)
end
end
r
fun without[K: HashFunction[this->A!] val = H](
that: this->HashSet[A, H])
: HashSet[this->A!, K]^
=>
"""
Create a set with the elements of this that are not in that.
"""
let r = HashSet[this->A!, K](size())
for value in values() do
try
that(value)?
else
r.set(value)
end
end
r
fun clone[K: HashFunction[this->A!] val = H](): HashSet[this->A!, K]^ =>
"""
Create a clone. The element type may be different due to aliasing and
viewpoint adaptation.
"""
let r = HashSet[this->A!, K](size())
for value in values() do
r.set(value)
end
r
fun eq(that: HashSet[A, H] box): Bool =>
"""
Returns true if the sets contain the same elements.
"""
(size() == that.size()) and (this <= that)
fun ne(that: HashSet[A, H] box): Bool =>
"""
Returns false if the sets contain the same elements.
"""
not (this == that)
fun lt(that: HashSet[A, H] box): Bool =>
"""
Returns 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 =>
"""
Returns true if every element in this is also in that.
"""
try
for value in values() do
that(value)?
end
true
else
false
end
fun gt(that: HashSet[A, H] box): Bool =>
"""
Returns 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 =>
"""
Returns true if every element in that is also in this.
"""
that <= this
fun next_index(prev: USize = -1): USize ? =>
"""
Given an index, return the next index that has a populated value. Raise an
error if there is no next populated index.
"""
_map.next_index(prev)?
fun index(i: USize): this->A ? =>
"""
Returns the value at a given index. Raise an error if the index is not
populated.
"""
_map.index(i)?._2
fun values(): SetValues[A, H, this->HashSet[A, H]]^ =>
"""
Return an iterator over the values.
"""
SetValues[A, H, this->HashSet[A, H]](this)
class SetValues[A, H: HashFunction[A!] val, S: HashSet[A, H] #read] is
Iterator[S->A]
"""
An iterator over the values in a set.
"""
let _set: S
var _i: USize = -1
var _count: USize = 0
new create(set: S) =>
"""
Creates an iterator for the given set.
"""
_set = set
fun has_next(): Bool =>
"""
True if it believes there are remaining entries. May not be right if values
were added or removed from the set.
"""
_count < _set.size()
fun ref next(): S->A ? =>
"""
Returns the next value, or raises an error if there isn't one. If values
are added during iteration, this may not return all values.
"""
_i = _set.next_index(_i)?
_count = _count + 1
_set.index(_i)?