[comp.lang.c++] Map class for partially ordered keys

vaughan@puma.cad.mcc.com (Paul Vaughan) (08/15/89)

	Has anyone implemented a map class that supports
inheritance-like lookup for partially ordered keys?  For example, given
the partial ordering

	A
       / \
      B   C

and a map with entries

A => 1
B => 2

then you could make the following queries and expect the given results

A => 1
B => 2
C => 1

Other queries would result in either a runtime error or a default
value.  Either hierarchies or general partial orderings (as in
Multiple Inheritance) would do at the moment.

 Paul Vaughan, MCC CAD Program | ARPA: vaughan@mcc.com | Phone: [512] 338-3639
 Box 200195, Austin, TX 78720  | UUCP: ...!cs.utexas.edu!milano!cadillac!vaughan

ark@alice.UUCP (Andrew Koenig) (08/15/89)

In article <2239@cadillac.CAD.MCC.COM>, vaughan@puma.cad.mcc.com (Paul Vaughan) writes:

> 	Has anyone implemented a map class that supports
> inheritance-like lookup for partially ordered keys?  For example, given

That's a real interesting problem.

Do you know an efficient algorithm for doing it?  Note that you
can't just impose a total ordering on top of the partial ordering.
-- 
				--Andrew Koenig
				  ark@europa.att.com