#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/shared_ptr.hpp>
#include <iostream>
#include <set>
#include <typeinfo>
#include <utility>

// Hierarchy layout:
//
//  A-->B------>C-->C1
//        | |
//        | --->D
//        |
//        ----->E
//

struct A
{
  A(int id):id(id){}
  virtual ~A(){}
  
  int id;
};

struct B:A
{
  B(int id):A(id){}
};

struct C:B
{
  C(int id):B(id){}
};

struct C1:C
{
  C1(int id):C(id){}
};

struct D:B
{
  D(int id):B(id){}
};

struct E:B
{
  E(int id):B(id){}
};

// type-based key extraction framework

class is_a
{
public:
  explicit is_a(const std::type_info& type):type(&type){}
  
  const std::type_info* type;
};

class hierarchical_type_order
{
public:
  template<typename Base,typename Derived>
  static void declare_base_and_derived()
  {
    hierarchical_type_order b(typeid(Base));
    hierarchical_type_order d(typeid(Derived));
    reg.find(d)->base=&(*reg.find(b));
  }
  
  hierarchical_type_order(const std::type_info& type):type(&type),base(0)
  {
    base=reg.insert(*this).first->base;
  }
  
  friend bool operator<(
    const hierarchical_type_order& x,const hierarchical_type_order& y)
  {
   const hierarchical_type_order* px=&x;
   const hierarchical_type_order* py=&y;

   while(px->base&&!py->is_same_or_derived_from(px->base->type))px=px->base;
   while(py->base&&!px->is_same_or_derived_from(py->base->type))py=py->base;
   return px->type->before(*(py->type));
  }
  
  friend bool operator<(
    const hierarchical_type_order& x,const is_a& y)
  {
    if(x.is_same_or_derived_from(y.type))return false;
    return x<hierarchical_type_order(*(y.type));
  }

  friend bool operator<(
    const is_a& x, const hierarchical_type_order& y)
  {
    if(y.is_same_or_derived_from(x.type))return false;
    return hierarchical_type_order(*(x.type))<y;
  }

private:
  struct type_info_compare
  {
    bool operator()(    
      const hierarchical_type_order& x,const hierarchical_type_order& y)const
    {
      return x.type->before(*(y.type));
    }
  };
  
  typedef std::set<
    hierarchical_type_order,
    type_info_compare>       registry_type;

  static registry_type       reg;

  bool is_same_or_derived_from(const std::type_info* type)const
  {
    const hierarchical_type_order* p=this;
    do{
      if(*(p->type)==*type)return true;
      p=p->base;
    }while(p);
    return false;
  }
  
  typedef const hierarchical_type_order* base_type;

  const std::type_info* type;
  mutable base_type     base;
};

hierarchical_type_order::registry_type hierarchical_type_order::reg;

struct hierarchical_type_order_extractor
{
  typedef hierarchical_type_order result_type;
  
  template<typename T>
  hierarchical_type_order operator()(const T& t)const
  {
    return typeid(t);
  }
};

namespace std{

template<>
struct less<hierarchical_type_order>:
  std::binary_function<hierarchical_type_order,hierarchical_type_order,bool>
{
  bool operator()(
    const hierarchical_type_order& x,const hierarchical_type_order& y)const
  {
    return x<y;
  }
  
  bool operator()(
    const hierarchical_type_order& x,const is_a& y)const
  {
    return x<y;
  }

  bool operator()(
    const is_a& x, const hierarchical_type_order& y)const
  {
    return x<y;
  }
};

} // namespace std

using namespace boost::multi_index;

typedef multi_index_container<
  boost::shared_ptr<A>,
  indexed_by<
    // This index sorts by hierarchical type order, then by id.
    // Use it to extract subviews based on the class of the element.
    
    ordered_non_unique<
      composite_key<
        A,
        hierarchical_type_order_extractor,
        member<A,int,&A::id>
      >
    >,
    
    // Regular index which does not differentiate between types.
    ordered_non_unique<
      member<A,int,&A::id>
    >
  >
> multi_class_container;

template<typename InputIterator>
static void dump(InputIterator first,InputIterator last)
{
  while(first!=last){
    std::cout<<(*first++)->id<<" ";
  }
  std::cout<<std::endl;
}

template<typename InputIterator>
static void dump(
  const std::pair<InputIterator,InputIterator>& p)
{
  dump(p.first,p.second);
}

int main()
{
  // Register the base-derived relationships of the hierarchy.
  // We only register direct base-derived pairs, that is, we
  // mustn't register A-->C, for instance.

  hierarchical_type_order::declare_base_and_derived<A,B>();
  hierarchical_type_order::declare_base_and_derived<B,C>();
  hierarchical_type_order::declare_base_and_derived<B,D>();
  hierarchical_type_order::declare_base_and_derived<B,E>();
  hierarchical_type_order::declare_base_and_derived<C,C1>();
  
  typedef boost::shared_ptr<A> element_ptr;
  
  // populate the container
  
  multi_class_container m;
  m.insert(element_ptr(new A(0)));
  m.insert(element_ptr(new A(1)));
  m.insert(element_ptr(new A(2)));
  m.insert(element_ptr(new B(3)));
  m.insert(element_ptr(new B(4)));
  m.insert(element_ptr(new C(5)));
  m.insert(element_ptr(new C(6)));
  m.insert(element_ptr(new D(7)));
  m.insert(element_ptr(new E(8)));
  m.insert(element_ptr(new E(9)));
  m.insert(element_ptr(new C1(10)));

  // extract the different views based on typeid
  
  std::cout<<"A: ";     dump(m.equal_range(typeid(A)));  
  std::cout<<"B: ";     dump(m.equal_range(typeid(B)));  
  std::cout<<"C: ";     dump(m.equal_range(typeid(C)));  
  std::cout<<"C1: ";    dump(m.equal_range(typeid(C1)));  
  std::cout<<"D: ";     dump(m.equal_range(typeid(D)));  
  std::cout<<"E: ";     dump(m.equal_range(typeid(E)));

  // extract views of given types and its derived classes
  // ("intermediate type" feature)

  std::cout<<"is_a A: ";dump(m.equal_range(is_a(typeid(A))));
  std::cout<<"is_a B: ";dump(m.equal_range(is_a(typeid(B))));
  std::cout<<"is_a C: ";dump(m.equal_range(is_a(typeid(C))));

  // do a normal query without discriminating typeid's
  
  std::cout<<"not less than five: ";
  dump(m.get<1>().lower_bound(5),m.get<1>().end());   
}