SkipMap

Overview

An ordered map implementation with performance characteristics similar to a balanced binary tree.

The name 'SkipMap' comes from the implementation, which is based on skip-lists.

Example of usage:

> local s1 = SkipMap:make{a=1,b=2,c=3,d=4,e=5}
> assert( s1:size()==5 )
> assert( ordering.isSorted(s1) )
> assert( s1:get("a")==1 )
> assert( s1:get("e")==5 )
> assert( s1:first()=="a" )
> assert( s1:last()=="e" )
> assert( s1:remove("b")==2 ) -- can also remove a key range
> -- iterate just from keys=="c" or after
> for k,v in s1:iter("c") do print(k,v) end
c   3
d   4
e   5

SkipSet is just a SkipMap where the keys map to true for all elements that exist in the set. Phonebook is a SkipMap which allows duplicate key-value pairs.

Summary

`new`	Returns a newly constructed SkipMap using the specified ordering function, or self.cDefaultOrdering (initially natural increasing order) if none is specified.
`make`	Creates and returns a new Map, containing the mappings supplied.
`get`	Returns the value associated with the supplied key, or nil if none exists.
`__eq`	Returns true if both SkipMaps have the same size and contain the same elements in the same order.
`add`	Adds a new key-value pair to this SkipMap and returns the old value stored against key (or nil if the pair is new).
`concatenate`	Concatenates skipmap onto the end of this SkipMap.
`contains`	Returns true if this SkipMap contains a value for the supplied key.
`first`	Returns the first key-value pair in this map, or nil if the map is empty.
`get`	Returns the value associated with the supplied key, or nil if none exists.
`last`	Returns the last key-value pair in this map, or nil if the map is empty.
`merge`	Merges another SkipMap into this SkipMap, ensuring that the merged map remains ordered.
`remove`	Removes the mapping associated with the supplied key and returns the value stored against key.
`size`	Returns the number of mappings in this SkipMap.
`splice`	Removes all elements ordered between start and stop (both inclusive) and returns them as a new SkipMap.
`split`	Removes all elements ordered at or after splitKey and returns them in a new SkipMap.
`test`	Unit test.
`toString`	Returns a string representation of map.
`addMappings`	Adds mappings to this Map and returns Map to allow chaining.
`INCREASING`	Returns x if x <= y and y otherwise.
`containsAll`	Returns true iff collection:contains(e) for e in iter(iterable).
`removeAll`	Equivalent to calling set:remove(e) for e in iter(elements).
`valIter`	Equivalent to Map:iter() except that iteration steps return elements in the order val,key instead of key,val.

Detail

`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

`Map:make(mappings [, vals])`

Creates and returns a new Map, containing the mappings supplied.

input can be one of several types:

A single Lua table {a=1,b=2,c=3,d=4,e=5}
A single iteration which returns two values per iteration step: iter.zip("abcde",iter.count())
Two iterables which both return one value per iteration step - this is a shorthand for 2.
Any table with an iter method which, when called, returns an iteration satisfying 2.

So, the following are all equivalent:

Map:make{a=1,b=2,c=3,d=4,e=5} 
  == Map:make(iter.zip("abcde",iter.count()))
  == Map:make("abcde",iter.count())
  == Map:make(Map:make{a=1,b=2,c=3,d=4,e=5})

`SkipMap:get(key)`

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

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

`SkipMap:__eq(other)`

Returns true if both SkipMaps have the same size and contain the same elements in the same order.

`SkipMap:add(key, val)`

Adds a new key-value pair to this SkipMap and returns the old value stored against key (or nil if the pair is new).

`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.

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

`SkipMap:last()`

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

time complexity: O(lg(size))

`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)).

`SkipMap:remove(key [, last])`

Removes the mapping associated with the supplied key and returns the value stored against key.

Supplying a second parameter makes this equalivalent to calling SkipMap:splice().

Examples:

{a=1,b=2,c=3}:remove("a") == 1
{a=1,b=2,c=3}:remove("a","b") == {a=1,b=2}

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

`SkipMap:test()`

Unit test.

`maps.toString(map)`

Returns a string representation of map.

Example:

> x = HashMap:make{a=1,b=2,c=3,d=4}
> print(x)
{a=1, d=4, c=3, b=2}

`Map:addMappings(mappings, vals)`

Adds mappings to this Map and returns Map to allow chaining.

input can be one of several types:

A single Lua table {a=1,b=2,c=3,d=4,e=5}
A single iteration which returns two values per iteration step: iter.zip("abcde",iter.count())
Two iterables which both return one value per iteration step - this is a shorthand for 2.
Any table with an iter method which, when called, returns an iteration satisfying 2.

So, the following are all equivalent:

Map:addMappings{a=1,b=2,c=3,d=4,e=5} 
  == Map:addMappings(iter.zip("abcde",iter.count()))
  == Map:addMappings("abcde",iter.count())
  == Map:addMappings(Map:addMappings{a=1,b=2,c=3,d=4,e=5})

`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.

`collections.containsAll(collection, elements)`

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

`sets.removeAll(set, elements)`

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

`Map:valIter()`

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