HashSet

Overview

Table-based set implementation with support for user defined hash functions and nil elements.

Examples:

> set = oop.methodCaller(HashSet, "make")
> s = set(iter.count(10))
> s2 = set(iter.count(5,15))
> print(s + s2) -- synonym for s:union(s2)
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
> print(s - s2)
{1, 2, 3, 4}
> print(s:intersection(s2))
{5, 6, 7, 8, 9, 10}
> print(s:size())
10
> print(s:contains(3), s(3)) -- __call is synonym for contains
true  true
> print(set(1,2,3) == set(1,2,3))
true

HashSets are themselves hashable, so they can be stored in HashSets or used as keys in HashMaps, for example:

> s = set(set(1,2), set(2,1), set(3,4))
> print(s)
{{1, 2}, {3, 4}}

HashSet can also store nil as an element, although when iterating over a HashSet, the nil element will cause the iteration to halt, as Lua uses nil to signal the end of an iteration. To work around this, use the enum method:

> s = set(1,2); s:add(nil)
> for _,e in s:enum() do print(e) end
1
2
nil

See HashMap for more information on how the Sano library handles hashing of user defined objects.

Summary

`make`	Creates and returns a new instance of self containing the elements passed in as vararg params.
`contains`	Returns true if element exists in this set.
`__eq`	Returns true if both sets have the same size and both contain the same elements.
`add`	Adds element to this HashSet and returns true if it did not already exist in the set.
`contains`	Returns true if element exists in this set.
`iter`	Returns an iterator over the elements of this HashSet.
`remove`	Removes and returns the element if it existed in this HashSet; otherwise returns nil.
`size`	Returns the number of elements in this HashSet.
`test`	Unit test.
`union`	Returns the union of set1 and set2 as a new set.
`hash`	Returns the sum of utils.hash(i) for i in set.
`difference`	Returns the set that would be created by removing from set1 all elements in intersection(set1,set2).
`toString`	Returns a string representation of set.
`addAll`	Calls collection:add(e) for each e in iter(iterable).
`containsAll`	Returns true iff collection:contains(e) for e in iter(iterable).
`containsAny`	Returns true if for collection:contains(e) for some e in iter(iterable).
`difference`	Returns the set that would be created by removing from set1 all elements in intersection(set1,set2).
`enum`	Decorates another iteration to return the index of each element returned from the decorated iteration.
`intersection`	Computes and returns the intersection of set1 and set2.
`difference`	Returns the set that would be created by removing from set1 all elements in intersection(set1,set2).
`removeAll`	Equivalent to calling set:remove(e) for e in iter(elements).
`removeElement`	Equivalent to set:remove(element).
`retainOnly`	Removes all elements from set which do not also appear in elements.
`union`	Returns the union of set1 and set2 as a new set.
`uniqueFilter`	Create and return a uniqueness filter based on set.
`xor`	Returns the set of elements which appear in either set1 or set2, but not in both.

Detail

`HashSet:new()`

Creates and returns a new, empty HashSet

`collections.make(self, ...)`

Creates and returns a new instance of self containing the elements passed in as vararg params.

If #args is 1, the argument is assumed to be iterable and its elements are added to the Collection.

Example, assuming Collection is a sequence type:

> print( Collection:make(1,2,3,4) )
[1, 2, 3, 4]
> print( Collection:make(iter.count(4) )
[1, 2, 3, 4]
> v = Collection:make(1,2,3,4); print( Collection:make(v) )
[1, 2, 3, 4]

This method is used as the make method for LinkedList, SkipVector, HashSet, SkipSet, QueueVector, and PairingHeap. It assumes that self has new() and addAll() methods.

`HashSet:contains(element)`

Returns true if element exists in this set.

Since HashSet can be used to store nil elements, this method returns true if element is nil and there has been a prior call to add(nil)

The __call metamethod is a synonym for contains.

`HashSet:__eq(set2)`

Returns true if both sets have the same size and both contain the same elements.

`HashSet:add(element)`

Adds element to this HashSet and returns true if it did not already exist in the set.

nil may be added to a HashSet.

`HashSet:contains(element)`

Returns true if element exists in this set.

Since HashSet can be used to store nil elements, this method returns true if element is nil and there has been a prior call to add(nil)

The __call metamethod is a synonym for contains.

`HashSet:iter()`

Returns an iterator over the elements of this HashSet.

`HashSet:remove(element)`

Removes and returns the element if it existed in this HashSet; otherwise returns nil.

`HashSet:size()`

Returns the number of elements in this HashSet.

`HashSet:test()`

Unit test.

`sets.union(set1, set2 [, setType])`

Returns the union of set1 and set2 as a new set.

The returned set is created by a call to:

(setType or getmetatable(set1)):make(...)

synonyms: __add

`sets.hash(set)`

Returns the sum of utils.hash(i) for i in set.

This is the hash function used by all set implementations.

`sets.difference(set1, set2 [,setType])`

Returns the set that would be created by removing from set1 all elements in intersection(set1,set2).

The returned set is created by a call to:

(setType or getmetatable(set1)):new()

synonyms: __sub, minus

`sets.toString(set)`

Returns a string representation of set.

The order in which elements appear in the representation is the same as the iteration order of elements of the set.

Example:

> print(HashSet:make(1,1,3,2,5,6,4))
{1, 2, 3, 4, 5, 6}

`collections.addAll(collection, iterable)`

Calls collection:add(e) for each e in iter(iterable).

`collections.containsAll(collection, elements)`

Returns true iff collection:contains(e) for e in iter(iterable).

`collections.containsAny(collection, iterable)`

Returns true if for collection:contains(e) for some e in iter(iterable).

`sets.difference(set1, set2 [,setType])`

Returns the set that would be created by removing from set1 all elements in intersection(set1,set2).

The returned set is created by a call to:

(setType or getmetatable(set1)):new()

synonyms: __sub, minus

`iter.enum(iterable [, size, stop, step])`

Decorates another iteration to return the index of each element returned from the decorated iteration.

If iterable is an object with a size() method, or if size is explicitly specified, the iteration will halt after iterable:size() steps. Otherwise, the iteration halts as soon as iter(iterable) halts (this may be undesireable if the iteration is expected to contain nil values)

If 2 args are given the indices will range from 1 to arg[2]. If 3 args are given the second and third arguments are interpreted as a counting range for the enumeration; If a 4th argument is specified, args 2 and 3 specify the counting range, and arg 4 specifies the step increment.

Examples:

> for ind,v in vector("abcd"):enum() do print(ind,v) end
1       a
2       b
3       c
4       d
> vec = vector("abc"); vec:add(nil)
> for ind,v in vec:enum() do print(ind, v) end
1       a
2       b
3       c
4       nil

`sets.intersection(set1, set2 [, setType])`

Computes and returns the intersection of set1 and set2.

The returned set is created by a call to:

(setType or getmetatable(set1)):new()

`sets.difference(set1, set2 [,setType])`

Returns the set that would be created by removing from set1 all elements in intersection(set1,set2).

The returned set is created by a call to:

(setType or getmetatable(set1)):new()

synonyms: __sub, minus

`sets.removeAll(set, elements)`

Equivalent to calling set:remove(e) for e in iter(elements).

`sets.removeElement(set, element)`

Equivalent to set:remove(element).

In a sequence, the remove() method takes as input an index while the removeElement method takes as input the element to be removed. This method has the same semantics across both set and sequence implementations.

`sets.retainOnly(set, elements)`

Removes all elements from set which do not also appear in elements.

If elements is also a set, s, set is modified to be the intersection of set and s.

`sets.union(set1, set2 [, setType])`

Returns the union of set1 and set2 as a new set.

The returned set is created by a call to:

(setType or getmetatable(set1)):make(...)

synonyms: __add

`sets.uniqueFilter(set)`

Create and return a uniqueness filter based on set.

The filter is a function which returns true only for objects it has not yet seen. This can be used in conjuction with iter.filter. For example:

> v = vector(1,1,1,2,3,3,4,1,5,5)
> print(vector(iter.filter(v, HashSet:uniqueFilter())))
[1, 2, 3, 4, 5]

`sets.xor(set1, set2 [,setType])`

Returns the set of elements which appear in either set1 or set2, but not in both.

This operation is also often called the symmetric set difference.