Intrusive Test

// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab
#include "OpQueue.h"

#include <functional>
#include <list>
#include <iostream>
#include <boost/intrusive/list.hpp>
#include <boost/intrusive/avl_set.hpp>

namespace bi = boost::intrusive;

using namespace std;

template <typename T>
class MapKey
{
  public:
  bool operator()(const int i, const T &k) const
  {
    return i < k.key;
  }
  bool operator()(const T &k, const int i) const
  {
    return k.key < i;
  }
};

template <typename T, typename K>
class WrrQueue :  public OpQueue <T, K>
{
  private:
    class ListPair : public bi::list_base_hook<>
    {
      public:
        unsigned cost;
        T item;
        ListPair(unsigned& c, T& i) :
          cost(c),
          item(i)
          {}
    };
    class Klass : public bi::avl_set_base_hook<>
    {
      typedef bi::list<ListPair> ListPairs;
      public:
        K key;      // klass
        ListPairs lp;
        Klass(K& k) :
          key(k)
          {}
    //friend bool operator< (const Klass &a, const Klass &b)
    //  { return a.key < b.key; }
    //friend bool operator> (const Klass &a, const Klass &b)
    //  { return a.key > b.key; }
    //friend bool operator== (const Klass &a, const Klass &b)
    //  { return a.key == b.key; }
    bool insert(unsigned& cost, T& item) {
      lp.push_back(*new ListPair(cost, item));
    }
    bool empty() const {
      return lp.empty();
    }
    unsigned filter_list_pairs(std::function<bool (T)>& f,
      std::list<T>* out) {
      unsigned ret = 0;
      // intrusive containers can't erase with a reverse_iterator
      // so we have to walk backwards on our own. Since there is
      // no iterator before begin, we have to test at the end.
      for (typename ListPairs::iterator i = --lp.end();; --i) {
        std::cout << "testing: " << i->cost << ", " << i->item << std::endl;
        if (f(i->item)) {
          std::cout << "Deleting: " << std::endl;
          if (out) {
        out->push_front(i->item);
          }
          i = lp.erase(i);
          ++ret;
        }
        if (i == lp.begin()) {
          break;
        }
      }
    }
    void print() const {
          typename ListPairs::const_iterator it(lp.begin()), ite(lp.end());
          for (; it != ite; ++it) {
            std::cout << "      L: " << it->cost << ", " << it->item << std::endl;
          }
        }
    };
    class SubQueue : public bi::avl_set_base_hook<>
    {
      typedef bi::avl_set<Klass> Klasses;
      typedef typename Klasses::iterator Ki;
      public:
    unsigned key;   // priority
    Klasses klasses;
    Ki next;
    SubQueue(unsigned& p) :
      key(p),
      next(klasses.begin())
      {}
      bool empty() const {
    return klasses.empty();
      }
      bool insert(K& cl, unsigned& cost, T& item) {
    typename Klasses::insert_commit_data insert_data;
        std::pair<typename Klasses::iterator, bool> ret =
      klasses.insert_check(cl, MapKey<Klass>(), insert_data);
        if (ret.second) {
          ret.first = klasses.insert_commit(*new Klass(cl), insert_data);
        }
        ret.first->insert(cost, item);
      }
      unsigned filter_list_pairs(std::function<bool (T)>& f,
    std::list<T>* out) {
    unsigned count = 0;
    for (typename Klasses::iterator i = klasses.begin();
      i != klasses.end();) {
      cout << "going to test klass: " << i->key << std::endl;
      count += i->filter_list_pairs(f, out);
      if (i->empty()) {
        // don't leak memory
        Klass * k = &*i;
        i = klasses.erase(i);
        delete k;
      } else {
        ++i;
      }
    }
    if (next == klasses.end()) {
      next = klasses.begin();
    }
    return count;
      }
      void print() const {
        typename Klasses::const_iterator it(klasses.begin()), ite(klasses.end());
        for (; it != ite; ++it) {
          std::cout << "   K: " << it->key << std::endl;
          it->print();
        }
      }
    };
    class Queue {
      typedef bi::avl_set<SubQueue> SubQueues;
      SubQueues queues;
      public:
    Queue() {}
    void insert(unsigned& p, K& cl, unsigned& cost, T& item) {
      typename SubQueues::insert_commit_data insert_data;
          std::pair<typename SubQueues::iterator, bool> ret =
            queues.insert_check(p, MapKey<SubQueue>(), insert_data);
          if (ret.second) {
            ret.first = queues.insert_commit(*new SubQueue(p), insert_data);
          }
          ret.first->insert(cl, cost, item);
    }
    void print() const {
      typename SubQueues::const_iterator it(queues.begin()), ite(queues.end());
          for (; it != ite; ++it) {
            std::cout << "P: " << it->key << std::endl;
            it->print();
          }
    }
    void filter_list_pairs(std::function<bool (T)>& f, std::list<T>* out) {
      for (typename SubQueues::iterator i = queues.begin(); i != queues.end();) {
            i->filter_list_pairs(f, out);
        if (i->empty()) {
          // don't leak memeory
          SubQueue * q = &*i;
          i = queues.erase(i);
          delete q;
        } else {
          ++i;
        }
          }
    }
    };

    void do_printme(T out)
    {
      cout << "WrrOp: " << out << "\n";
    }

    Queue normal;
  public:
    void whoami() final
    {
      cout << "WrrOp\n";
    }
    void printme(T out) final {
      do_printme(out);
    }
    WrrQueue() :
      normal()
      {}
    void remove_by_filter(std::function<bool (T)> f, std::list<T>* removed = 0) {
      normal.filter_list_pairs(f, removed);
    }
    void enqueue(unsigned p, K cl, unsigned cost, T item) {
      normal.insert(p, cl, cost, item);
    }
    void print_queue() const {
      normal.print();
    }
};