[boost] Re: Two way maps/multimaps

From: Andy Glew (glew_at_[hidden])
Date: 1999-10-08 01:52:00

While we're at it, I'd like to solicit advice as to
the interfaces for a family of such consistent structures.

To begin with, the basic groups:

        reln_1_to_1
        reln_1_to_N
        reln_N_to_N

    These are the basic components. It then seems to me that you
    might want to extend this, for example, to variously transitively closed
    operations:

            reln_equivalence
                    if (A,B) and (B,C) , then (A,C)
                    i.e. A,B, and C are all linked equally.

            I am tempted to include total orders here,
            but I think that is too expensive, much more so than
            equivalence groups.

    Similarly, you may want to build N-tuples

            reln_many_to_1_to_many        // a 3-tuple
    
                I have some hope of defining constructors 
                for these in terms of the binary relations.

The innards for reln_1_to_1

        class reln_1_to_1 {
            // base class
            template<class From> class reverse_ptr {
                From* value;
                // not directly assignable, is dereferenceable, etc.
            }
            template<class To> class forward_ptr {
                From* value;
            }
        }

        template<class From, Class To>
        class reln_1_to_1 {
        public:
                void link( From f, To t );
        public:
                class forward_map {
                    // defines reln[From] = To
                }
                class reverse_map { ... };
        public:
                class iterator {
                    // the usual iterator stuff, sto scan a whole relation
                }
        public:
                // find(f,t)
                // erase(iterator)
        }

        template<class From, Class To, &From::ForwardLink, &To::BackwardLink >
        class reln_1_to_1 {
            // as above, but also keeps the member pointers consistent
        }

i.e. the basic approach is to define forward_map and reverse_map member classes,
and to use these to encapsulate particular queries.

reln_1_to_N is similar, but instead of having simple pointers, has lists or maps
in the reverse direction

        class reln_1_to_N {
            // base class
            template<class From> class reverse_list {
                list<From*> value;
                // not directly assignable, is dereferenceable, etc.
            }
            template<class To> class forward_ptr {
                From* value;
            }
        }

        template<class From, Class To>
        class reln_1_to_N {
        public:
                void link( From f, To t );
        public:
                class forward_map {
                    // defines To operator[] ( From& f)
                }
                class reverse_map { 
                   // defines const list<From> operator[] ( To& t)   
                };
        public:
                class iterator {
                    // the usual iterator stuff, so scan a whole relation
                }
        public:
                // find(f,t)
                // erase(iterator)
        }

        template<class From, Class To, &From::ForwardLink, &To::BackwardLink >
        class reln_1_to_N {
            // as above, but also keeps the member pointers consistent
        }

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.