Re: [Boost-users] [Multi-Index] Skip-Scan "virtual" ordered-non-unique index on top of composite ordered-unique index

Subject: Re: [Boost-users] [Multi-Index] Skip-Scan "virtual" ordered-non-unique index on top of composite ordered-unique index
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2013-11-29 14:47:38

Dominique Devienne <ddevienne <at> gmail.com> writes:

> 
> On Thu, Nov 28, 2013 at 8:37 PM, Joaquin M Lopez Munoz
> <joaquin <at> tid.es> wrote:
> Code requires C++11 support :-/
> 
> 
> Needless to say, this is going to require more than my current VS2010.

This can be backported to C++03 using the awesome Boost.Preprocessor
library. Code above has been tried with VS2012 but should work in your
compiler.

Joaquín M López Muñoz
Telefónica Digital

#include <boost/preprocessor/arithmetic/add.hpp>
#include <boost/preprocessor/arithmetic/sub.hpp>
#include <boost/preprocessor/logical/and.hpp>
#include <boost/preprocessor/punctuation/comma_if.hpp>
#include <boost/preprocessor/repetition/enum.hpp>
#include <boost/preprocessor/repetition/enum_binary_params.hpp>
#include <boost/preprocessor/repetition/enum_params.hpp>
#include <boost/preprocessor/repetition/repeat.hpp>
#include <boost/ref.hpp>
#include <boost/tuple/tuple.hpp>

#ifndef SKIP_SCAN_MAX_KEYS // user configurable
#define SKIP_SCAN_MAX_KEYS 5
#endif

#define SKIP_SCAN_TUPLE_FIRST(z,n,_) \
boost::cref(key<n>(c.key_extractor(),*it))

#define SKIP_SCAN_CLASS_INVOKE(z,m,n) \
template< \
  typename Container,typename F \
  BOOST_PP_COMMA_IF(m) \
  BOOST_PP_ENUM_PARAMS(m,typename T) \
> \
static void invoke( \
  const Container& c,F f \
  BOOST_PP_COMMA_IF(m) \
  BOOST_PP_ENUM_BINARY_PARAMS(m,const T, &t)) \
{ \
  for(auto it=c.begin(),it_end=c.end();it!=it_end;){ \
    for(auto rng=c.equal_range( \
          boost::make_tuple( \
            BOOST_PP_ENUM(n,SKIP_SCAN_TUPLE_FIRST,~) \
            BOOST_PP_COMMA_IF(BOOST_PP_AND(n,m)) \
            BOOST_PP_ENUM_PARAMS(m,t))); \
        rng.first!=rng.second;++rng.first){ \
      f(*rng.first); \
    } \
    it=c.upper_bound( \
      boost::make_tuple(BOOST_PP_ENUM(n,SKIP_SCAN_TUPLE_FIRST,~))); \
  } \
}

#define SKIP_SCAN_CLASS_SPECIALIZE(z,n,_) \
template<> struct skip_scan_class<n> \
{ \
  BOOST_PP_REPEAT( \
    BOOST_PP_ADD(BOOST_PP_SUB(SKIP_SCAN_MAX_KEYS,n),1), \
    SKIP_SCAN_CLASS_INVOKE,n) \
};

#define SKIP_SCAN_OVERLOAD(z,m,_) \
template< \
  int N,typename Container,typename F \
  BOOST_PP_COMMA_IF(m) \
  BOOST_PP_ENUM_PARAMS(m,typename T) \
> \
void skip_scan( \
  const Container& c,F f \
  BOOST_PP_COMMA_IF(m) \
  BOOST_PP_ENUM_BINARY_PARAMS(m,const T, &t)) \
{ \
  skip_scan_class<N>::invoke( \
    c,f \
    BOOST_PP_COMMA_IF(m) \
    BOOST_PP_ENUM_PARAMS(m,t) \
  ); \
}

template<int N,typename CompositeKey,typename Value>
auto key(const CompositeKey& ck,const Value& v)->decltype(
  boost::tuples::get<N>(ck.key_extractors())(v))
{
  return boost::tuples::get<N>(ck.key_extractors())(v);
}

template<int N>
struct skip_scan_class;

BOOST_PP_REPEAT(
  BOOST_PP_ADD(SKIP_SCAN_MAX_KEYS,1),SKIP_SCAN_CLASS_SPECIALIZE,~)
BOOST_PP_REPEAT(
  BOOST_PP_ADD(SKIP_SCAN_MAX_KEYS,1),SKIP_SCAN_OVERLOAD,~)

#undef SKIP_SCAN_OVERLOAD
#undef SKIP_SCAN_CLASS_SPECIALIZE
#undef SKIP_SCAN_CLASS_INVOKE
#undef SKIP_SCAN_TUPLE_FIRST

// testing

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <iostream>

using namespace boost::multi_index;

struct element
{
  element(int x0,int x1,int x2,int x3, int x4):
    x0(x0),x1(x1),x2(x2),x3(x3),x4(x4){}
  int x0,x1,x2,x3,x4;
};

std::ostream& operator<<(std::ostream& os,const element& v)
{
  os<<"("<<v.x0<<","<<v.x1<<","<<v.x2<<","<<v.x3<<","<<v.x4<<")";
  return os;
}

typedef multi_index_container<
  element,
  indexed_by<
    ordered_non_unique<
      composite_key<
        element,
        member<element,int,&element::x0>,
        member<element,int,&element::x1>,
        member<element,int,&element::x2>,
        member<element,int,&element::x3>,
        member<element,int,&element::x4>
      >
    >
  >
> multi_t;

static inline void print_element(const element& v){std::cout<<v<<" ";}

int main()
{
  multi_t c;
  c.emplace(0,1,2,3,4);
  c.emplace(0,1,2,3,5);
  c.emplace(0,1,3,4,0);
  c.emplace(1,0,0,0,0);
  c.emplace(1,1,2,3,0);
  c.emplace(1,1,2,3,0);
  c.emplace(2,1,2,1,0);
  c.emplace(2,2,2,3,0);

  skip_scan<1>(
    c,print_element,
    1,2,3);
  std::cout<<"\n";

  skip_scan<3>(
    c,print_element,
    3);
  std::cout<<"\n";

  skip_scan<2>(
    c,print_element,
    2,3);
  std::cout<<"\n";
}