// A queue-like type that calls a function to add elements as needed.

// The function has a void *& argument that can be used as state.  The
// return value of the function is usually true; if it is false that
// indicates that it should not be called again.  Each time the
// function is called it is passed a pointer to an empty queue<T> and it
// may add 0 or more elements.

#ifndef _RQUEUE_H_
#define _RQUEUE_H_

#include <cstdio>
#include <cassert>
#include <iostream>
#include <queue>
#include "llist.h"

#ifndef MAXINT
#define MAXINT (int)(((unsigned int)-1) >> 1)
#endif

#define generic template <class T>

generic class rqueue;
// DOB: following declaration needed for g++ 3.4.0
generic rqueue<T>* filter(rqueue<T> *l, bool g(const T &));

#define RQUEUE_DEBUG 0
#define RQUEUE_DEBUG_VERBOSE 0

generic class rqueue {
 public:

  /* Types */

  typedef T value_type;
  typedef T& reference;
  typedef T const& const_reference;
  typedef queue<T> Q;
  typedef bool (*fn)(void *&, Q *); // returns false if it is kaput.

  friend rqueue<T>* filter<T>(rqueue<T> *l, bool g(const T &));

  /* Accessors */
  virtual reference front() { force(); return q->front(); }
  virtual const_reference front() const { force(); return q->front(); }
  virtual const_reference pop() {
    const_reference result = front(); q->pop(); return result;
  }
  virtual bool empty() const { force(); return q->empty(); }
  
  /* Utils */

  /* Return as many as the first n elements as a llist. */
  llist<T> *as_llist(int n = MAXINT) {
    llist<T> *result = NULL;
    while (!empty() && n-- > 0)
      result = cons(pop(), result);
    return dreverse(result);
  }

 private:
  void force() const {
    while (q->empty() && f != NULL)
      if (!(*f)(userdata, q))
	f = NULL;
  }

  /* Constructors */
 public:
  rqueue() {}
  virtual ~rqueue() {}
  rqueue(fn f0, void *userdata0) : q(new Q), f(f0), userdata(userdata0) {}
  rqueue(rqueue<T> *t) : q(t->q), f(t->f), userdata(t->userdata) {}

  virtual rqueue<T> * clone() const {
    rqueue *r = new rqueue<T>();
    *r = *this;
    return r;
  }

 protected:
  // The data
  mutable Q *q;
  mutable fn f;
  mutable void *userdata;
};

generic class filtered_rqueue : public rqueue<T> {
 public:

  typedef T value_type;
  typedef T& reference;
  typedef T const& const_reference;

  filtered_rqueue<T>(rqueue<T> *r0, bool g0(const_reference)) :
    r(r0), g(g0) {}

 public:
  rqueue<T> * clone() const {
    filtered_rqueue<T> *r = new filtered_rqueue<T>();
    *r = *this;
    return r;
  }

  /* Accessors */
  reference front() { skip(); return r->front(); }
  const_reference front() const { skip(); return r->front(); }
  const_reference pop() { skip(); return r->pop(); }
  bool empty() const { skip(); return r->empty(); }

 private:
  // Return when r is empty or (*g)(r->front), discarding elts of r as needed.
  void skip() const {
    while (!r->empty() && !(*g)(r->front()))
      r->pop();
  }

  filtered_rqueue<T>() {}

  bool (*g)(const_reference);
  rqueue<int> *r;
};

generic rqueue<T>* filter(rqueue<T> *l, bool g(const T &))
{
  return new filtered_rqueue<int>(l, g);
}

#undef generic

#endif // _RQUEUE_H_