[boost] * to N relations: data structures for `N'

From: Andy Glew (glew_at_[hidden])
Date: 1999-10-08 16:39:16

> While we're at it, I'd like to solicit advice as to
> the interfaces for a family of such consistent structures.
> 
> The complexity of reln_1_to_N is that the reverse map  is a container.
> It is not clear to me whether that container should itself be a parameter,
> and, if so, how to parametrize it.  I.e. it is straightforward to have the reverse
> data structure always be a list, but sometimes you want it to be a map
> sorted on a key, sometimes a hash_map, etc.
> 
> reln_M_to_N is similar. Once we figure out what the proper way to
> represent 1:many relations is - or, more likely, what the proper way
> to handle multiple different desired representations - the rest follows.

Well, at least writing those diatribes last night got me thinking.
What I describe above is the real problem / interface design issue
that has got me blocked.

It is straightforward to implement once you decide what sort of
data structure you will use to go from the 1 to the many. You want
lists? Rings? A FIFO? A priority queue?

The problem is that, at least in my own code where I use such
concepts, I nearly always have some additional data structure
for the "many" that is important to my problem.

For example, in the producer/consumer example (a simplified
real example from a simulator I am working on now) I currently
want the data structure of consumers for any particular producer
to be a FIFO, i.e. sorted by request time.

At other times I want it to be sorted by consumer creation time,
and occasionally I need it to be sorted by consumer time in a
searchable way, as in a map.  At other times I have needed only a
priority queue based on some key, since I haven't needed ordered
search.

(And, oh, yeah, I want this selectable at run time, without the overhead 
of virtual functions. Good luck, you say? Well, many workers in my field
do things like recompiling a special version of the program for the user
to run; I've played with using CMIX partial evaluation.  Static selection
of methods at startup saves a hell of a lot of time compared to virtual
function overhead.  But that's another issue.)

Conceptually, what I want is a 

        TEMPLATE: 1 to N
                FROM     typename1
                                LINKAGE  &typename1::linkage
                TO            typename2
                                LINKAGE &typename2::linkage
                ACCESS-PATHS:
                        FROM:TO
                                        FIFO
                                        LRU
                                        priority_queue using typename2::prio
                                        map using typename2::key
                        TO:FROM
                                        pointer

i.e. I would like to specify at least one, and potentially several,
access paths to the "many"; I would like to be able to iterate over
any of those access paths independently; I would like an erase
using an iterator obtained from any one access path to apply to them all; 
I'd like an insert to insert on all access paths; but I would like to have
the ability to rearrange access paths once created, e.g. changing the
priority of an object, changing its LRU status, etc.

It may be that the right thing is to define a template

        reln_1_to_many< class T1, class T2, &T1::link1, &T2::link2, template Access_from_1_to_2>

(pardon, I don't have the syntax for passing templates as arguments quite down yet)

which creates the appropriate pallet, and then organizes those pallets as
        Access_from_1_to_2<pallet>

Somehow, I need to attach the auxiliary info for the access path, such as the key to
be sorted and indexed on.

But, the basic idea would be to pass a single access path from 1 to many;
if you need multiple, you would have to define a consistent combination 
of them youself and pass that in.