Dual look-up on keys?

[Bryan Olson]

Grant Edwards wrote:
> It may be  obvious that he has a question.  It's not the least
> bit obvious what that question is.

How can we efficiently implement an abstract data type, call it
'DoubleDict', where the state of a DoubleDict is a binary
relation, that is, a set of pairs (x, y); and the operations on
a DoubleDict are those on a Python set, plus:

     find_by_first(self, x):  return [y where (x, y) in DoubleDict]

     find_by_second(self, y):  return [x where (x, y) in DoubleDict]


Python can implement this ADT directly as specified, but the
find_by_ operations would run in time len(self).  We want an
implementation where the find_by's run in O(1 + k) where k is
the length of the returned sequence.


-- 
--Bryan