SkipSet

Overview

Ordered set implementation based on SkipMap.

The SkipSet class was created by a call to sano.maps.makeSet(SkipMap:new()). The set is implemented by storing the elements of the set as the keys in SkipMap, where all keys simply map to the value 'true'.

Example usage:

> oset = function(...) return SkipSet:make(unpack(arg)) end
> -- above is equivalent to: oset = sano.makers.oset
> s = oset(1,2,3,3,4); print(s)
{1, 2, 3, 4}
> print(s == oset(4,3,2,1))
true
> print(s == oset(1,3,5,7))
false
> print(s:remove(1))
1
> s:addAll(iter.count(10,15)); print(s)
{2, 3, 4, 10, 11, 12, 13, 14, 15}
> s:removeAll(iter.count(2,4)); print(s)
{10, 11, 12, 13, 14, 15}
> print(s:size())
6

Summary

makeCreates and returns a new instance of self containing the elements passed in as vararg params.
newReturns a newly constructed SkipMap using the specified ordering function, or self.cDefaultOrdering (initially natural increasing order) if none is specified.
testUnit test.
unionReturns the union of set1 and set2 as a new set.
containsReturns true if this SkipMap contains a value for the supplied key.
hashReturns the sum of utils.hash(i) for i in set.
differenceReturns the set that would be created by removing from set1 all elements in intersection(set1,set2).
toStringReturns a string representation of set.
addAdds element to this set and returns true on success, false if element already existed in this set.
addAllCalls collection:add(e) for each e in iter(iterable).
INCREASINGReturns x if x <= y and y otherwise.
concatenateConcatenates skipmap onto the end of this SkipMap.
containsReturns true if this SkipMap contains a value for the supplied key.
containsAllReturns true iff collection:contains(e) for e in iter(iterable).
containsAnyReturns true if for collection:contains(e) for some e in iter(iterable).
differenceReturns the set that would be created by removing from set1 all elements in intersection(set1,set2).
enumDecorates another iteration to return the index of each element returned from the decorated iteration.
firstReturns the first key-value pair in this map, or nil if the map is empty.
getReturns the value associated with the supplied key, or nil if none exists.
intersectionComputes and returns the intersection of set1 and set2.
lastReturns the last key-value pair in this map, or nil if the map is empty.
INCREASINGReturns x if x <= y and y otherwise.
mergeMerges another SkipMap into this SkipMap, ensuring that the merged map remains ordered.
differenceReturns the set that would be created by removing from set1 all elements in intersection(set1,set2).
removeRemoves and returns element from this set, or returns nil if element was not a member of this set.
removeAllEquivalent to calling set:remove(e) for e in iter(elements).
removeElementEquivalent to set:remove(element).
retainOnlyRemoves all elements from set which do not also appear in elements.
sizeReturns the number of mappings in this SkipMap.
spliceRemoves all elements ordered between start and stop (both inclusive) and returns them as a new SkipMap.
splitRemoves all elements ordered at or after splitKey and returns them in a new SkipMap.
unionReturns the union of set1 and set2 as a new set.
uniqueFilterCreate and return a uniqueness filter based on set.
valIterEquivalent to Map:iter() except that iteration steps return elements in the order val,key instead of key,val.
xorReturns the set of elements which appear in either set1 or set2, but not in both.

Detail

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.

SkipMap:new([orderFn])

Returns a newly constructed SkipMap using the specified ordering function, or self.cDefaultOrdering (initially natural increasing order) if none is specified.

The newly created map can be used to create other maps with the same default ordering, for instance:

> MaxFirstSkipMap = SkipMap:new(ordering.DECREASING)
> maxFirstMap = MaxFirstSkipMap:make{a=1,b=2,c=3,d=4}
> print(maxFirstMap:first())
d

SkipSet: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

SkipMap:contains(key)

Returns true if this SkipMap contains a value for the supplied key.

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}

Set:add(element)

Adds element to this set and returns true on success, false if element already existed in this set.

collections.addAll(collection, iterable)

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

ordering.INCREASING(x,y)

Returns x if x <= y and y otherwise.

This ordering is the default ordering typically used in functions where an (optional) ordering function is left unspecified.

SkipMap:concatenate(skipmap)

Concatenates skipmap onto the end of this SkipMap.

This method throws an error if the two maps overlap. If the two maps are expected to have overlapping keysets according to the ordering, then use SkipMap:merge().

skiplist is destroyed as a result of this call.

time complexity: O(lg(size))

SkipMap:contains(key)

Returns true if this SkipMap contains a value for the supplied key.

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

SkipMap:first()

Returns the first key-value pair in this map, or nil if the map is empty.

time complexity: O(1)

SkipMap:get(key)

Returns the value associated with the supplied key, or nil if none exists.

synonyms: map:get(key) == map(key)

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()

SkipMap:last()

Returns the last key-value pair in this map, or nil if the map is empty.

time complexity: O(lg(size))

ordering.INCREASING(x,y)

Returns x if x <= y and y otherwise.

This ordering is the default ordering typically used in functions where an (optional) ordering function is left unspecified.

SkipMap:merge(skipmap)

Merges another SkipMap into this SkipMap, ensuring that the merged map remains ordered.

The other SkipMap is destroyed as result of this call.

The time complexity of this operation depends on the amount of overlap. The worst case, when entries need to be perfectly interlaced, takes O(size(self)+size(skipmap)). The best case, when entries are completely disjoint, takes only O(lg(size)).

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

Set:remove(element)

Removes and returns element from this set, or returns nil if element was not a member of this set.

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.

SkipMap:size()

Returns the number of mappings in this SkipMap.

SkipMap:splice(start [, stop])

Removes all elements ordered between start and stop (both inclusive) and returns them as a new SkipMap.

param stop: the last key (inclusive) to remove, default SkipMap:last()

time complexity: O(lg(size) + |stop-start|) (Unfortunately, the linear term is needed to recompute sizes - todo is to recompute these lazily)

SkipMap:split(splitKey)

Removes all elements ordered at or after splitKey and returns them in a new SkipMap.

Example, given the map m = {a=1,b=2,c=3,d=4}, m:split("b") would return {b=2,c=3,d=4}.

The same result can be acheived by calling SkipMap:splice(splitKey). splice() is a more general method in that it also allows an end key.

time complexity: O(lg(size))

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]

Map:valIter()

Equivalent to Map:iter() except that iteration steps return elements in the order val,key instead of key,val.

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.