efficient functional data structure for finite bijections

Question

I'm looking for a functional data structure that represents finite bijections between two types, that is space-efficient and time-efficient.

For instance, I'd be happy if, considering a bijection f of size n:

• extending f with a new pair of elements has complexity O(ln n)
• querying f(x) or f^-1(x) has complexity O(ln n)
• the internal representation for f is more space efficient than having 2 finite maps (representing f and its inverse)

I am aware of efficient representation of permutations, like this paper, but it does not seem to solve my problem.

Answer 1

Please have a look at my answer for a relatively similar question. The provided code can handle general NxM relations, but also be specialized to just bijections (just as you would for a binary search tree).

Pasting the answer here for completeness:

The simplest way is to use a pair of unidirectional maps. It has some cost, but you won't get much better (you could get a bit better using dedicated binary trees, but you have a huge complexity cost to pay if you have to implement it yourself). In essence, lookups will be just as fast, but addition and deletion will be twice as slow. Which isn't so bad for a logarithmic operation. Another advantage of this technique is that you can use specialized maps types for the key or value type if you have one available. You won't get as much flexibility with a specific generalist data structure.

A different solution is to use a quadtree (instead of considering a NxN relation as a pair of 1xN and Nx1 relations, you see it as a set of elements in the cartesian product (Key*Value) of your types, that is, a spatial plane), but it's not clear to me that the time and memory costs are better than with two maps. I suppose it needs to be tested.

Answer 2

Although it doesn't satisfy your third requirement, bimaps seem like the way to go. (They just make two finite maps, one in each direction, convenient to use.)