
Boost : 
From: Andy Glew (glew_at_[hidden])
Date: 19991008 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 Ntuples
reln_many_to_1_to_many // a 3tuple
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk