#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <list>
#include <functional>
#include <cassert>

//
// Functions
//

struct mod2 : public std::unary_function<int, int> {
  int operator()(int x) const { return x % 2; }
};

struct mod3 : public std::unary_function<int, int> {
  int operator()(int x) const { return x % 3; }
};

struct mod4 : public std::unary_function<int, int> {
  int operator()(int x) const { return x % 4; }
};


//
// Base class foo
//

struct foo {
  std::vector<int> data_m;

  foo() : data_m() {}

  int& insert(int x) {
    data_m.push_back(x);
    return data_m.back();
  }

  template<typename trans_T>
  std::list<std::pair<typename trans_T::result_type, int> >
  match(const typename trans_T::result_type& pattern,
	const trans_T& trans = trans_T()) const {
    std::list<std::pair<typename trans_T::result_type, int> > results;
    for (auto it = data_m.begin(); it != data_m.end(); ++it) {
      auto p = trans(*it);
      if (pattern == p) {
	results.push_back(std::make_pair(p, *it));
      }
    }
    return results;
  }
};


//
// Derived class bar
//

template<typename base_T, typename trans_T>
struct bar : public base_T {
  typedef base_T base_type;
  typedef std::multimap<typename trans_T::result_type, int> index_type;
  index_type index_m;

  bar(const trans_T& trans = trans_T()) : base_type(), index_m() {}

  int& insert(int x, const trans_T& trans = trans_T()) {
    return index_m.insert(typename index_type::value_type(trans(x), base_type::insert(x)))->second;
  }

  std::pair<typename index_type::const_iterator,
	    typename index_type::const_iterator>
  match(const typename trans_T::result_type& pattern,
	const trans_T& trans = trans_T()) const {
    return index_m.equal_range(pattern);
  }

  template<typename xtrans_T>
  decltype(base_type().match(typename xtrans_T::result_type(), xtrans_T()))
    match(const typename xtrans_T::result_type& pattern,
	  const xtrans_T& xtrans = xtrans_T()) const {
    return base_type::match(pattern, xtrans);
  }

};


//
// Begin/end functions present in Boost but not in GCC
//

template<typename iter_T>
iter_T begin(const std::pair<iter_T, iter_T>& range) {
  return range.first;
}

template<typename iter_T>
iter_T end(const std::pair<iter_T, iter_T>& range) {
  return range.second;
}


//
// Main
//

int main(const int argc, const char** argv) {
  using std::cout;
  using std::endl;

  bar<bar<foo, mod2>, mod3> baz;


  ///
  /// Insert some numbers
  ///

  for (int i = 0; i < 20; ++i) {
    baz.insert(i);
  }

  for (int i = 0; i < 5; ++i) {
    cout << "i = " << i << endl;

    ///
    /// Try to match with different functions
    ///

    auto baz_match_mod2 = baz.match(i, mod2());
    cout << "mod2:";
    for (auto it = begin(baz_match_mod2); it != end(baz_match_mod2); ++it) {
      assert(it->first == i);
      cout << ' ' << it->second;
    }
    cout << endl;

    auto baz_match_mod3 = baz.match(i, mod3());
    cout << "mod3:";
    for (auto it = begin(baz_match_mod3); it != end(baz_match_mod3); ++it) {
      assert(it->first == i);
      cout << ' ' << it->second;
    }
    cout << endl;

    auto baz_match_mod4 = baz.match(i, mod4());
    cout << "mod4:";
    for (auto it = begin(baz_match_mod4); it != end(baz_match_mod4); ++it) {
      assert(it->first == i);
      cout << ' ' << it->second;
    }
    cout << endl;
  }

  return 0;
}