Phonebook

Overview

An ordered map based on SkipMap which allows duplicate keys.

In SkipMap, calling add(key, val) for a key which already exists overwrites the previous value. In a Phonebook, the new key-value pair is added AFTER the previous pair. Calling Phonebook:get(key) retrieves the FIRST value stored agains the key. Phonebook:remove(key) also removes the first value stored against key.

For more control over the handling of duplicate keys in a map, see Multimap.

Example usage:

> p = Phonebook:new()
> p:add('Doe', 'John'); p:add('Doe', 'Jane'); print(p)
{Doe="John", Doe="Jane"}
> p:add('Smith','Mike'); p:add('Smith','Mary'); p:add('Jones','Jim')
> print(p)
{Doe="John", Doe="Jane", Jones="Jim", Smith="Mike", Smith="Mary"}
> for first,last in p:iter('Doe','Jones') do print(first,last) end
Doe     John
Doe     Jane
Jones   Jim
> print(p:remove('Doe'))
John

Summary

`make`	Creates and returns a new Map, containing the mappings supplied.
`new`	Returns a newly constructed SkipMap using the specified ordering function, or self.cDefaultOrdering (initially natural increasing order) if none is specified.
`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).
`merge`	Merges another SkipMap into this SkipMap, ensuring that the merged map remains ordered.
`test`	Unit test.
`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.
`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.
`concatenate`	Concatenates skipmap onto the end of this SkipMap.
`contains`	Returns true if this SkipMap contains a value for the supplied key.
`containsAll`	Returns true iff collection:contains(e) for e in iter(iterable).
`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.
`INCREASING`	Returns x if x <= y and y otherwise.
`remove`	Removes the mapping associated with the supplied key and returns the value stored against key.
`removeAll`	Equivalent to calling set:remove(e) for e in iter(elements).
`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.
`valIter`	Equivalent to Map:iter() except that iteration steps return elements in the order val,key instead of key,val.

Detail

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

`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: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:test()`

Unit test.

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

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

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

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

`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: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}

`sets.removeAll(set, elements)`

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

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

`Map:valIter()`

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