Re: [boost] [ptr_container] and [multi_index] ?

From: Janek Kozicki (janek_listy_at_[hidden])
Date: 2006-11-22 16:06:29

Since I can't stop thinking about that, I'll try to describe the most
difficult data structure that I have here. Maybe you will have some
suggestions. And maybe it will help me to sort the thing out.

In my program I am calculating bodies collisions and other
kind of interactions. This is a physical simualtion stuff.

I have a container (an easier one) with bodies where each body has an
integer ID number. And the bodies can interact together, there are
various kinds of interaction. And I need to store those interactions
in a container. The keys are:

- interaction type: each polymorphic interaction type stored in this
  container is a different kind of interaction. Sometimes I need to
  interate over all interactions of selected type, thus it becomes
  one of the keys.
  This is an integer.

- a set of interacting bodies: any number of bodies can interact. Two
  or more bodies, but very rarely as much as four.
  - Sometimes I need to iterate over all interactions which
    involve a selected body or,
  - check if an interaction of given type between bodies 1, 2 and 3
    already exists, then get it, or add it, if it didn't exist.
  This is a list of integer values (IDs of bodies).

If I had only two-body interaction of single type then this could ba
a (sparse) two dimensional symmetric matrix. Boost.Graph library
treats two-body interaction as a graph edge, and the container used is
std::vector<std::set<T> > > which works well for that.

An example content of this container could be:

   interaction Type          IDs of bodies involved
+---------------------+--------------------------------------
|                     | (2,3) (2,3,4) (8,11,12,15)  (13,14)
+---------------------+--------------------------------------
| ElasticContact      |   X                X           X   
+---------------------+--------------------------------------
| MagneticInteraction |   X     X                      X   
+---------------------+-------------------------------------- 
| .
| .
| .

The 'X' means that there is an instance present.

One solution (a bit of pseudocode) could be:

multi_index_container<
  interaction*,
  indexed_by<
     ordered_non_unique<member<interaction*,int,&interaction::type> >

     ordered_unique    <member<interaction*,std::set<int>,&interaction::bodies> >
     // non_unique in fact. But uniqe with respect to &interaction::type.
     // That's why it's pseudocode

  >
>;

But how to make this and get a reasonable performance?

And how to make that std::set<int> working? :) (or maybe
tr1::hash_set<int>, if there is one)

How to iterate over all interactions involving a body with ID 3 of type 1 ?

For example I could use lazy deletion (only sets the field as
unused), with cleaning invoked from time to time.

Performance priorities (from most important, to least important):

A)iterating over all elements with the same &interaction::type must
  be constant access time.

B)finding if there is an interaction between (1,2,3) - great if it
  was constant time (N-dimensional matrix gives that), I guess that log(O)
  is the best we can have.

C)deleting and adding an interaction, again I guess that constant
time is not possible.

D)iterating over all interactions involving a body with given ID  is
used less often so can be a bit slower.

If you have any insights I'd appreciate that :)

-- 
Janek Kozicki                                                         |