what is an efficient immutable one-to-many map with links both ways

[Tim P]

Hi
I want an efficient immutable structure that allows a one-to-many
mapping that allows me to query it it both directions.
I can do this with two maps:
Map{A, Set[B]]
Map[B, A]

which will probably work quite nicely but it does mean maintaining 2
structures and I wondered if there was some better data structure out
there.

Typical usage:
The List[B] is mostly just one item and unlikely to get large (i.e
rarely more than 2 or 3)
Queries are much more common that updates
Apart from the initial population activity, insertions and deletions
are equally common.
Total structure size of the order of 200 - 3000 of type B

BTW how efficient is the standard immutable Set with very low numbers
of members? Would I be better off using List and managing the "set"
property elsewhere?

Tim

[Sonnenschein]

Hi Tim,

> BTW how efficient is the standard immutable Set with very low numbers
of members? Would I be better off using List and managing the "set"
property elsewhere?

Very efficient as there are special implementations for small numbers
of elements.

> I wondered if there was some better data structure out there.

What you've depicted is actually a graph structure. If you are
interested in more graph-related functionality you may also consider
http://www.assembla.com/spaces/scala-graph/wiki.

Peter