Multimap

Overview

Map in which each key maps to a collection of values.

A Multimap is a map in which each key maps to a collection of values. Multimaps merely provide a few convenience methods for behavior that is achievable with a regular Map.

When add(key, val) is called, Multimap first checks to see if there is already a collection stored against key. If yes, val is added to that collection. If no (val is the very first value to be stored against key), then a new collection is allocated and val is added to that collection. For example:

> m = Multimap:new()
> m:add("R. White","'Tater Salad")
> m:add("R. White", "The 'Tater")
> m:add("G. Pitcher", "The Ace")
> m:addValues("G. Pitcher", {"Ace", "The Kid"})
> print(m)
{G. Pitcher=["The Ace", "Ace", "The Kid"], 
 R. White  =["'Tater Salad", "The 'Tater"]}

Both the map implementation and values collection type can be specified in the Multimap constructor. By default, the map implementation is a HashMap and the values collection is a Vector. But, for instance:

> m = Multimap:new(HashMap, SkipSet)
...
> m:add("R. White", "The 'Tater")
> m:add("R. White", "The 'Tater")
> print(m:get("R. White")) -- The 'Tater only appears once, since the
{"'Tater Salad", "The 'Tater"} -- values collection is a set

Multimaps provide several other convenience methods, see the method documentation.

Summary

newCreates and returns a new Multimap, using the supplied map implementation and values collection.
makeCreates and returns a new Map, containing the mappings supplied.
getReturns the collection of values stored against key, or nil if no mapping exists.
__eqReturns true if self and other both have the same set of keys and collections of values.
addAdds val to the collection stored against key or to a new collection if no values are yet stored against key.
allValsIterReturns an iterator over all the values stored in this map.
allocateAllocate an empty collection of values for key.
decorateDecorates the supplied map's add method to have multimap behavior.
getReturns the collection of values stored against key, or nil if no mapping exists.
iterReturns an iterator over this map, or, if key is specified, over the values collection stored against key.
removeRemove all values stored against key, or, if value is specified, remove only value in the collection stored against key.
sizeReturns the number of keys in this Multimap.
testUnit test.
valSizeReturns the number of values in this Multimap.
toStringReturns a string representation of map.
addMappingsAdds mappings to this Map and returns Map to allow chaining.
HashMapTable-based implementation of a map with support for user-defined hash functions and nil values.
VectorTable implementation of a general purpose vector.
containsAllReturns true iff collection:contains(e) for e in iter(iterable).
removeAllEquivalent to calling set:remove(e) for e in iter(elements).
valIterEquivalent to Map:iter() except that iteration steps return elements in the order val,key instead of key,val.

Detail

Multimap:new(mapType, valuesCollection)

Creates and returns a new Multimap, using the supplied map implementation and values collection.

mapType defaults to self.cDefaultMapType, which is initially HashMap, and valuesCollection defaults to self.cDefaultValuesType, which is initally Vector.

Map:make(mappings [, vals])

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

input can be one of several types:

  1. A single Lua table {a=1,b=2,c=3,d=4,e=5}
  2. A single iteration which returns two values per iteration step: iter.zip("abcde",iter.count())
  3. Two iterables which both return one value per iteration step - this is a shorthand for 2.
  4. 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})

Multimap:get(key)

Returns the collection of values stored against key, or nil if no mapping exists.

Synonym: operator () ( so a:get(b) == a(b) ) Examples:

{a=[1,2,3]}:get(a) == [1,2,3]
{a=[1,2,3]}:get(b) == nil

Multimap:__eq(other)

Returns true if self and other both have the same set of keys and collections of values.

Multimap:add(key, val)

Adds val to the collection stored against key or to a new collection if no values are yet stored against key.

Examples:

{a=[1,2]}:add(a,3) results in {a=[1,2,3]}
{}:add(a,3) results in {a=[3]}

Multimap:addValues(key, vals)

Equivalent to the loop:
for v in iter(vals) do self:add(key,v) end

Multimap:allValsIter()

Returns an iterator over all the values stored in this map.

Example:

mmap = {a=[1,2,3],b=[4,5,6]}
print( vector(mmap:allValsIter()) )
[1, 2, 3, 4, 5, 6]

Multimap:allocate(key)

Allocate an empty collection of values for key.

Multimap:contains(key)

Returns true iff self:get(key) ~= nil

Multimap:decorate(map, valuesType)

Decorates the supplied map's add method to have multimap behavior.

After this method is called, map.add(key,val) will first check to see if there is a collection stored against key. If yes, val is added to that collection. If not, val is added to a newly allocated collection of type valuesType and the new collection is stored against key.

It also adds a method, valSize, which returns the total number of values in the map.

Multimap:get(key)

Returns the collection of values stored against key, or nil if no mapping exists.

Synonym: operator () ( so a:get(b) == a(b) ) Examples:

{a=[1,2,3]}:get(a) == [1,2,3]
{a=[1,2,3]}:get(b) == nil

Multimap:iter([key])

Returns an iterator over this map, or, if key is specified, over the values collection stored against key.

If key is specified but maps to nil, an empty iterator is returned.

Multimap:remove(key [,value])

Remove all values stored against key, or, if value is specified, remove only value in the collection stored against key.

Multimap:size()

Returns the number of keys in this Multimap.

Multimap:valSize() returns the number of values in this Multimap.

Multimap:test()

Unit test.

Multimap:valSize()

Returns the number of values in this Multimap.

Multimap:size() returns the number of keys in this Multimap.

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:

  1. A single Lua table {a=1,b=2,c=3,d=4,e=5}
  2. A single iteration which returns two values per iteration step: iter.zip("abcde",iter.count())
  3. Two iterables which both return one value per iteration step - this is a shorthand for 2.
  4. 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})

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.