Re: [boost] [multi_index] a more complicated container

From: Janek Kozicki (janek_listy_at_[hidden])
Date: 2007-07-18 12:00:32

Matias Capeletto said:     (by the date of Tue, 17 Jul 2007 14:28:28 -0300)

> It was accepted in march :)
> But your feedback will be great! Really...

Hi Matias, thanks for your faith in... how good my comments might be :)

Currently I'm not going to go straight to the C++ coding (aka.
testing Bimap "live"). I am preparing grounds for huge refactoring.
And I'm looking at how to do it the best way.

My codebase of 15k lines already works quite good. Now in fact I want
to reorganize everything inside so it will be clean again. Because
currently more and more hacks appear to get something done.

I plan to stop using my own plugin-loading and serialization library 
and switch to boost::extension and ::serialization. Propose my own
Multimethods lirbary for boost inclusion (after boostifying it ;).
And stop using my own containers, but use boost instead.

So... in fact I have another question about containers. But I'm
afraid that bimap is not an answer here... So I keep [multi_index] in
the subject line :-)

Imagine that in my scientific simulation software I have bodies that
can interact with each other. Any number of bodies can interact. As
you already know, bodies are idenfied by id numbers. But
interactions are identified by std::set<int> - a group of bodies that
are interacting. So I have a class Interaction and it's indexed by
sets of numbers like:

identifier  interaction
1,2,3       class Interaction between boedies 1,2,3
2,3         Interaction
3,4         Interaction
2,4,6       some other Interaction

This is 'groups' in fact (the one with which I started this thread).
To make stuff easier to manage, I'll use negative numbers for
group_id and positive for body_id. So basically I could rewrite above
with:

identifier  interaction
-1          class Interaction between boedies 1,2,3
-2          Interaction
-3          Interaction
-4          some other Interaction

What I need here is a *cooperation* between containers (because
information about group components is stored in other container). So
with the Interaction container above I need to iterate FAST on following
things:

- all interactions from first to last (easy)
- all bodies that take part in interaction -3, answer is: 3,4
- all interactions in which body 3 is involved, answer is: -1,-2,-3

This is convoluted :) And even worse... becasue I need interactions
to have groups too! We can call it a group of groups, like this:

identifier group  interaction
-1          -5    class Interaction between boedies 1,2,3
-2          -5    Interaction
-3          -6    Interaction
-4          -6    some other Interaction

You can see that group -5 has two components: -1,-2, and group -6 has -3 and -4.

now I need to
- iterate over all interactions from group -5, answer is: -1 -2
- iterate over all bodies from group -5, answer is: 1,2,3
- all interactions involving body 3 that are in group -5, answer: -1 -2
- all interactions in which group of bodies 2 and 3 interact, answer: -1 -2 (may be slower)

I'm stil not sure if that's all i need. Still working on it ;-)

The hardest(??) part is that I will need separate containers (cannot
make one huge container for everything). So imagine, I have a class
Model, that holds the context of my computations. 

To simplify a little: 

I have two classes that describe a single body. Those are BodyState
(position, velocity) and BodyShape (vertex positions). They reside in
a std::map.

So, I say, that body_states[5] and body_shapes[5] describe the same
body with body_id=5. And If I need to know to which groups it belongs I look in
groups[5]. To see its name (a body could have name too) I see into names[5].

Like this:

typedef int id;
typedef id body_id;
typedef id group_id;

class Model
{
   bimap< tagged< int, body_id >, multiset_of< tagged< int, group_id > > >
        groups; // a bimap between positive body_id <-> negative group_id

   bimap<id,std::string>
        names;

   std::map<body_id , BodyState*> 
        body_states;

   std::map<body_id , BodyShape*> 
        body_shapes;

/*

Now I want to throw interactions into the basket. They can (I'm still
not sure) use the 'groups' container to index the content. Easiest is to say:

*/
    
    std::map<group_id, Interaction*>
        interactions;
};

But here, group_id used in 'interactions' is a "group of groups".
And (of course) I want to iterate over all interactions involved (or
bodies involved) as described above.

So I guess that I need multi_index here, since bimap won't be enough? :)

PS: actually I have more classes and containers here, this is simplified a bit.

This is not the end.... ;)

But for the next part I'm almost sure that I'll need a custom container.
I'll not describe it now, just to keep you excited a bit.

-- 
Janek Kozicki                                                         |