rationale.qbk

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

[[support/  ][optional metafunctions and free functions]]
[[detail/   ][things not intended for the user's eyes]]
]

[endsect]

[section The student and the mentor]

[tip It is a good idea to read the original
[@http://h1.ripway.com/mcape/boost/libs/misc/ Boost.Misc SoC proposal] first.]

[:[^- The discussion starts with Joaquin trying to strip out the "misc" name out of the library -]]

__JOAQUIN_PHOTO__

[*Joaquin]
[:['
Thinking about it, the unifying principle of MISC containers is perhaps
misleading: certainly all miscs use multi-indexing internally, but this does
not reflect much in the external interface (as it should be, OTOH). So, from
the user's point of view, miscs are entirely heterogeneous beasts. Moreover,
there isn't in your proposal any kind of global facility common to all miscs.
What about dropping the misc principle and working on each container as a
separate library, then? You'd have boost::bimap, boost::mru, etc, and no common
intro to them. This also opens up the possibility to add other containers to
the suite which aren't based on B.MI. What's your stance on this? Do you see a
value in keeping miscs conceptually together?
]]

__MATIAS_PHOTO__

[*Matias]
[:['
As the original proposal states only two containers (bimap and mru set) both 
based in B.MI, it was straight forward to group them together. When I was 
writing the SoC proposal I experienced a similar feeling when the two families 
begin to grow. As you say, the only common denominator is their internal 
implementation. I thought a bit about a more general framework to join this two
families (and other internally related ones) and finally came up with an idea: 
Boost.MultiIndex! So I think that it is not a good idea to try to unify the two 
families and I voted in favor of get rid of the misc part of boost::misc::bimap
and boost::misc::mru. Anyway, for my SoC application it seems OK to put the 
two families in the same project because although from the outside they are 
completely unrelated, the work I will have to do in order to build the libraries 
will be consistent and what I will learn coding the bimap family will be used 
when I start to code the mru family. When the mru family is in place, I will 
surely have learnt other things to improve the bimap group.
]]
[:['
On the other hand, I think it will be useful for the general user to
have at least some document linked in the B.MI documentation that
enumerates the most common cases of uses (a bimap and an mru set for
example) and points where to find clean implementation for this useful
containers. For now, a link to boost::bimap and other one to boost::mru
will suffice. If you think about the title of such a document,
you will probably come up with something like: Common Multi Index
Specialized Containers, and we are back to our misc proposal.
So, to order some ideas:
]]
[:['- A new family of containers that can be accessed by both key will
be created. (boost::bimap)]]
[:['- A new family of time aware containers will see the light.
(boost::mru)]]
[:['- A page can be added to B.MI documentation, titled misc that links
this new libraries.]]
[:['
This is a clearer framework for the user. They can use a mru container
without hearing about Boost.MultiIndex at all.
And B.MI users will get some of their common containers already
implemented with an STL friendly interface in other libraries.
And as you stated this is more extensible because opens the door to use
other libraries in bimap and mru families than just Boost.MultiIndex
without compromising the more general boost framework.
The word "misc" it is going to disappear from the code and
the documentation of bimap and mru. From now on the only use for it will be to
identify our SoC project. I am thinking in a name for the bimap library.
What about Boost.BidirectionalMap? Ideas?
]]

[*Joaquin]
[:['
Yes, Boost.Bimap. In my opinion, bimap is a well known name
in the Boost and even in the C++ community. It sounds and is short. Why not to
vindicate yourself as the owner of this name?
]]

[^- Then after a week of work -]

[*Matias]
[:['
Now that Boost.Bimap is getting some shape, I see that as
you have told me, we must offer a "one_to_many_map" and a "multi_bimap"
as part of the library. The framework I am actually working allowed to
construct this kind of bidirectional maps and it is easy to understand from
the user side.
]]

[*Joaquin]
[:['
OK, I am glad we agree on this point.
]]

[*Matias]
[:['
With respect to the symmetry of the key access names, I have to
agree that there is not much a difference between the following ones:
]]
[:['- to - from]]
[:['- to - b]]
[:['- 0 - 1]]
[:['- left - right]]
[:['
In my opinion it is a matter of taste, but left/right sounds more symmetrical than
the others.
]]

[*Joaquin]
[:['
I like very much the left/right notation, it is very simple to
remember and it is a lot more symmetrical than to/from.
]]

[*Matias]
[:['
At first my idea was to obtain ease of use hiding the B.MI
core, making it more STL-intuitive. Nevertheless I have realized
that B.MI is a lot more coherent and easy to use that I had imagined. This
makes me think again in the problem. In the design that I am coding now, bimap
*is-a* multi_index_container specializes with a data type very comfortable
called bipair, that can be seen like any of the two maps that integrates it
using map views. This scheme has great benefits for users:
]]
[:['
- If the user already knows B.MI, he can take advantage of the tools that
it provides and that are not present in the STL containers. In addition, in some
cases the use to indices to see the data can be very useful.
]]
[:['
- If the user does not know anything about B.MI but have an STL framework,
the learning curve is reduced to understand the bimap instantiation and how a
is obtained the desired map view.
]]
[:['
Another very important benefit holds: All the algorithms done for
B.MI continues to work with Boost.Bimap and if B.MI continues growing, bimap
grow automatically.
]]

[*Joaquin]
[:['
Umm... This is an interesting design decision, but
controversial in my opinion. Basically you decide to expose the
implementation of bimap; that has advantages, as you stated, but also
a nonsmall disadvantage: once *you have documented* the implementation,
it is not possible to change it anymore. It is a marriage with B.MI without
the chance of divorce. The other possibility, to hide the implementation and
to duplicate and document the provided functionality, explicitly or
implicitly due to the same characteristics of the implementation, is
of course heavier to maintain, but it gives a degree of freedom to change
the guts of your software if you need to. Do not take this like a frontal
objection, but I think that it is quite important design decision, not only
in the context of bimap but in general.
]]

[*Matias]
[:['
You are quite right here. I think we have to choose the hardest
path and hide the B.MI core from the user. I am sending you the first draft of
bimap along with some documentation.
]]

[^- This completes the second week, the documentation was basically the first
section of this rationale -]

[*Joaquin]
[:['
I must confess that I am beginning to like what I see.
I am mathematical by vocation, and when I see symmetry in a formulation
I believe that it is in the right track.
]]

[*Matias]
[:['
We are two mathematicians by vocation then.
]]

[*Joaquin]
[:['
I think that the part of std::set theory is very clear.
To me, it turns out to me somewhat strange to consider the rank of a map
(values X) like a std::set, but of course the formulation is consistent.
]]

[*Matias]
[:['
I like it very much, it can be a little odd at first, but
now that I have get used to it, it is very easy to express in the code my
contrains on the data, and I believe that if somebody reads the code and
sees the bimap instantiation he is not going to have problems understanding
it. Perhaps it is easier to understand it if we use your notation:
ordered_nonunique, unordered_unique, but this goes against our STL facade.
In my opinion the user that comes from STL must have to learn as less as possible.
]]

[*Joaquin]
[:['
Considering a relation like a `struct {left, right}`
is clean and clear. If I understand it well, one relation has views of type
`pair{first, second}`, is this correct? 
]]

[*Matias]
[:['
Yes, I believe that the left/right notation to express symmetry
is great. I believe that to people is going to love it.
]]

[*Joaquin]
[:['
OK, perfect. I likes this very much:
]]
[:['- bm.left is compatible with std::map<A,B>]]
[:['- bm.right is compatible with std::map<B,A>]]
[:['- bm is compatible with std::set<relation<A,B>>]]
[:['
It is elegant and symmetric. I feel good vibrations here.
]]

[*Matias]
[:['
Great!
]]

[*Joaquin]
[:['
Moving on, the support for N-1, N-N, and hashed index is very easy
to grasp, and it fits well in framework.
However I do not finish to understand very well the "set<relation> constraints" section.
Will you came up with some examples of which is the meaning of the different
cases that you enumerate?
]]

[*Matias - ]
[:['
Yes, I mean:
]]
[:['- based on the left]]
[:['- based on the right]]
[:['
The bimap core must be based on some index of multi index. If the index
of the left is of the type hash, then in fact the main view is going
to be an unordered_set< relation<A,B> >. Perhaps this is not what the user
prefers and he wants to base its main view on the right index.
]]
[:['- set_of_relation ]]
[:['- multiset_of_relation ]]
[:['- unordered_set_of_relation ]]
[:['- unordered_multiset_of_relation ]]
[:['
However, if both of them are hash indexes, the user may want the main view
to be ordered. As we have a B.MI core this is very easy to support, we just have
to add another index to it.
]]

[*Joaquin]
[:['
I understand it now. OK, I do not know if we have to include this
in the first version, is going to be a functionality avalanche!
]]

[*Matias]
[:['
The user is not affected by the addition of this functionality,
because by default it will be based on the left index that is a very natural
behaviour. I do not think that this is functionality bloat, but I agree with
you that it is a functionality avalanche. 
]]

[*Joaquin]
[:['
There are restrictions between the left and right set types
and the possible main view set types. For example if some of the index is
of unique type, then the main view cannot be of type multiset_of_relation.
To the inverse one, if the main view is of type set_of_relation the left and
the right index cannot be of type multi_set. All this subject of the unicity
constrictions and the resulting interactions between indexes is one of the subtle
subjects of B.MI. 
]]

[*Matias]
[:['
This can be checked at compile time and informed as an error
in compile time. 
]]

[*Joaquin]
[:['
It can be interesting.
]]

[^- And right when everything seems to be perfect... - ]

[*Joaquin]
[:['
I have some worse news with respect to mutant, it is very a