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.

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

`SkipMap:new([orderFn])`

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

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.

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

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

`SkipMap:__eq(other)`

`SkipMap:add(key, val)`

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

`SkipMap:first()`

time complexity: O(1)

`SkipMap:get(key)`

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

`SkipMap:last()`

time complexity: O(lg(size))

`SkipMap:merge(skipmap)`

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

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

`SkipMap:splice(start [, stop])`

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

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

`maps.toString(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)`

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.

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

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

`collections.containsAll(collection, elements)`

`sets.removeAll(set, elements)`

`Map:valIter()`