#include <algorithm>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <functional>
#include <iostream>
#include <iterator>
#include <utility>

using namespace boost::multi_index;
namespace bll=boost::lambda;

struct body
{
  body(int id):id(id){}

  int id;
};

struct interaction
{
  interaction(int id,int type):id(id),type(type){}

  int id;
  int type;
};

typedef std::pair<
  body*,
  interaction*
> body_interaction_value_type;

struct body_id_extractor
{
  typedef int result_type;

  result_type operator()(const body_interaction_value_type& x)const
  {
    return x.first->id;
  }
};

struct interaction_id_extractor
{
  typedef int result_type;

  result_type operator()(const body_interaction_value_type& x)const
  {
    return x.second->id;
  }
};

struct interaction_type_extractor
{
  typedef int result_type;

  result_type operator()(const body_interaction_value_type& x)const
  {
    return x.second->type;
  }
};

typedef multi_index_container<
  body_interaction_value_type,
  indexed_by<
    hashed_non_unique<body_id_extractor>,
    hashed_non_unique<interaction_id_extractor>,
    ordered_non_unique<interaction_type_extractor>
  >
> body_interaction;

typedef multi_index_container<
  int,
  indexed_by<hashed_unique<identity<int> > >
> int_accumulator;

template<typename InputIterator,typename IntExtractor>
void accumulate(
  int_accumulator& acc,
  std::pair<InputIterator,InputIterator> range,
  IntExtractor key)
{
  acc.clear();
  while(range.first!=range.second)acc.insert(key(*range.first++));
}

void print(const int_accumulator& acc)
{
  std::copy(
    acc.begin(),acc.end(),
    std::ostream_iterator<int>(std::cout," "));
  std::cout<<std::endl;
}

template<typename ForwardIterator,typename IntExtractor,typename Filter>
void print(
  std::pair<ForwardIterator,ForwardIterator> range,
  IntExtractor key,
  Filter filter)
{
  while(range.first!=range.second){
    if(filter(*range.first))std::cout<<key(*range.first)<<" ";
    ++range.first;
  }
  std::cout<<std::endl;
}

template<typename InputIterator,typename IntExtractor>
void print(std::pair<InputIterator,InputIterator> range,IntExtractor key)
{
  while(range.first!=range.second)std::cout<<key(*range.first++)<<" ";
  std::cout<<std::endl;
}

struct is_interaction_type
{
  typedef bool result_type;

  is_interaction_type(int type):type(type){}

  bool operator()(const body_interaction_value_type& x)const
  {
    return x.second->type==type;
  }

  int type;
};

struct does_interaction_affect_body
{
  typedef bool result_type;

  does_interaction_affect_body(
    int id,const body_interaction& bi):id(id),pbi(&bi){}

  bool operator()(const body_interaction_value_type& x)const
  {
    typedef body_interaction::nth_index_iterator<1>::type interaction_iterator;

    for(std::pair<interaction_iterator,interaction_iterator> p=
        pbi->get<1>().equal_range(x.second->id);
        p.first!=p.second;
        ++p.first){
      if(p.first->first->id==id)return true;
    }
    return false;
  }

  int                     id;
  const body_interaction* pbi;
};

int main()
{
  enum{collision=0,magnetic=1,gravitational=2};

  body         b1(1),b2(2),b3(3),b4(4),b5(5);
  interaction  i5(5,collision),i6(6,collision),i7(7,collision),
               i8(8,magnetic),i9(9,magnetic),i10(10,magnetic),
               i11(11,gravitational);

  body_interaction bi;
  bi.insert(std::make_pair(&b1,&i5));
  bi.insert(std::make_pair(&b1,&i8));
  bi.insert(std::make_pair(&b1,&i11));
  bi.insert(std::make_pair(&b2,&i5));
  bi.insert(std::make_pair(&b2,&i6));
  bi.insert(std::make_pair(&b2,&i8));
  bi.insert(std::make_pair(&b2,&i9));
  bi.insert(std::make_pair(&b2,&i11));
  bi.insert(std::make_pair(&b3,&i6));
  bi.insert(std::make_pair(&b3,&i9));
  bi.insert(std::make_pair(&b3,&i10));
  bi.insert(std::make_pair(&b3,&i11));
  bi.insert(std::make_pair(&b4,&i6));
  bi.insert(std::make_pair(&b4,&i7));
  bi.insert(std::make_pair(&b4,&i10));
  bi.insert(std::make_pair(&b4,&i11));
  bi.insert(std::make_pair(&b5,&i7));
  bi.insert(std::make_pair(&b5,&i11));

  int_accumulator acc;

  /* collision interactions */
  {
    accumulate(
      acc,bi.get<2>().equal_range(collision),interaction_id_extractor());
    print(acc);
  }

  /* bodies in collision interactions */
  {
    accumulate(
      acc,bi.get<2>().equal_range(collision),body_id_extractor());
    print(acc);
  }

  /* bodies in interaction 6 */
  {
    print(bi.get<1>().equal_range(6),body_id_extractor());
  }

  /* collision interactions involving body 4 */
  {
    print(
      bi.equal_range(4),interaction_id_extractor(),
      is_interaction_type(collision));
  }

  /* interactions involving body 1 */
  {
    print(bi.equal_range(1),interaction_id_extractor());
  }

  /* collision interactions involving bodies 2 and 4 */
  {
    print(
      bi.equal_range(2),interaction_id_extractor(),
      bll::bind(is_interaction_type(collision),bll::_1)&&
      bll::bind(does_interaction_affect_body(4,bi),bll::_1));
  }
}