[boost] [Bimap] Review

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2007-02-23 19:29:56

Hello Matias,

Here's a partial review, focused on the first things I observed so far.

1.
The very first thing I see is a nice bold question: "What is a bimap?"
However, everything that follows doesn't feel like a good answer. Is more 
like the explanation of the missing answer.
For such a concrete question I would expect a concrete answer like: "A Bimap 
is a data structure that represents bidirectional relations between elements 
of two collections", or something like that.

Furthermore, at this introductory point in the tutorial, the very first 
mention of "bm.left" should IMHO be closely followed by its definition, yet 
the statement "is signature compatible with std::map<A,B>" is a bit 
simplistic at that.
The same goes for bm.right and 'bm' itself.

2.
The next thing one sees is the nice diagram. It's so nice that it sticks and 
weights in the understanding of the nature of a bimap. Even if one reads 
through the text, the picture drives the understanding. At least that's how 
it works in my head.
However, it's a bit misleading, and I finally figured what, IMHO, is wrong 
with this picture :) Bare with me...

On the one hand I see two sets, X and Y (drawn as Venn diagrams), and a 
biyective relation (the arrows). Pretty straightforward.

On the other hand I see class bimap<X,Y>, followed by set< relation<X,Y> >, 
which one interprets as it's true nature given the way it is presented.

Now, on yet another hand, or a left foot maybe, I also see bimap<X,Y>::left, 
which is really a map<X,Y>,
and then a bimap<X,Y>::right, which is really a map<Y,X>.

Eventually, I realized one of the most important aspects of a bimap: its 
triality (yes, this is a word).
It is at the same time a set of elements (which happen to be relations), a 
map from left to right, and a map from right to left.  Thus, set< 
relation<X,Y> > is not the only true nature of a bimap even though it stands 
up-front in the picture.

In fact, it could be argued that the reverse view is the whole point of 
bimap<>. It's the reason of its existence.

That is, the set< relation<X,Y> > nature of it, even if useful and novel, is 
secondary. One could have the same for an ordinary map for that matter.

So, on the one hand, I would focus the presentation on the symmetric views 
first, then extend it to incorporate the (secondary) set-of-relations 
interface.

So, let's see the pictorialization of the two symmetric maps.

In the current picture, you see the left map sightly on top of the set X, 
and the right map slightly on top of the set Y.
Bur this draws the subconscious association between the left map and X and 
the right map and Y. However, a map is a relation, so *both* elements are 
part of a map. Therefore, the picture should better relate both X and Y to 
each of the maps.

Furthermore, these maps overlay each other over the same data structure, 
they are not just two disjoint maps.

I noticed that part of the confusion comes from the fact that each map is 
enclosed in disjoint ballons, and, actually, those ballons have no real 
iconic value (they don't represent anything useful by themselves).

The maps could be drawn at both sides of the sets and the ballons could be 
drawn to enclose both sets, such that at the intersection of both ballons, 
you see "the bimap" (the two sets and the relations between them).

Also, to further guide the role of each map as a directed view of the 
relation, I would use two colors and two single-headed arrows, one of each 
color, instead of one double-headed arrow as it is now.

Finally, I would put the set< relation<X,Y> > role at the bottom, to move 
the focus away from it, and its ballon would also enclose the two sets.

In the end, there are three ballons all intersecting at the region 
containing the Veen diagrams, expressing the fact
that a bimap<> offers three views over the same thing.

4.The following is from the second tutorial page (headed "The Tutorial")

4.a.It says:

"New concepts are however presented to extend the mapping framework to 
bidirectional maps"

That is confusing because at that point of the reading, there is no such 
thing as "a mapping framework". I would say "the std map class" instead.

4.b.

The expression "new framework" is also confusing.
A "new" something must relate to an "old" soemthing, and boost::bimap, IMO, 
should NOT be seen as something "new" while std::map as something old.
I would say "the Bimap framework" instead (this applies to many other pages 
in the docs)

4.d.

Here's the first time the expression "set type" is used.
This expression is used all over the documentation but there is problem: the 
term "set" is not defined so one is forced to imagine its definition. Is it 
an STL set? Is it a mathematical set? Does it have special requirements?

Granted, one eventually realizes you meant a mathematical set instead of an 
STL set, but even then, Bimap is purposedly designed to relax all such 
requirements, even uniqueness, so I think a better word for this concept is 
"collection".

The reason is that you can actually use a vector for this type, which can 
hardly be considered as representing a mathematical set (because it doesn't 
guarantee uniqueness).

5.
Here's an analysis of the "standard mapping framework" picture (following 
the same ideas as before);

5.a.The ballow should enclose both Venn diagrams since a map contains both 
elements.

5.b.The words "first/second" on top of std::map are confusing IMO. I would 
remove them.

5.c.In a std::map there is no explicit "set type" for the collection of 
keys, so at this point the label to it is confusing. I would removed it.

6.
After the picture you read "this is not wrong.".
What isn't?

7.
In the introduction of the standard mapping framework, the idea of a map 
seen as an overlay of two "set types" is presented, but unfortunately quite 
superficially.
This way of looking at it great, but is also a bit novel since the "standard 
framework" doesn't speak of left and right sets at all.
Thus, besides what I mentioned before about replacing "set" by "collection", 
I think you should add an entire page explicitely presenting the idea, at a 
conceptual level, that a map is the overlay of two collections. Much before 
the standard mapping framework is introduced.

That's all for now.. but there's more.

Best regards

And as promised:

!!! vamos vamos, Argentina !!

------
Fernando Cacciola
SciSoft

http://certuscode.wordpress.com
http://fcacciola.50webs.com
http://fcacciola.wordpress.com