#include <vector>
#include <functional>

#include <iostream>

/*
 *	Class RuleQueue
 *
 *	maintains active rules, order by priorities acording to PartialOrder
 *	rules are erased acording to their Equivalence
 *
 */

template< typename T, typename PartialOrder = std::less< T>, typename Equivalence = std::equal_to< T> >
class RuleQueue {

public:
	typedef typename std::vector< T>::iterator iterator;

	void insert( const T& x) {
		_items.push_back(x);
	}

	bool erase( const T& x) {
		for(iterator it = _items.begin(); it != _items.end(); ++it) {
			if(eqiv(*it, x)) {
				_items.erase(it);
				return true;
			}
		}

		return false;
	}

	iterator top_begin() {

		_top.clear(); //initialize new top
		if(!_items.empty()) {

			T foo = _items.front(); //inicialize smallest element

			for(iterator it = _items.begin(); it != _items.end(); ++it) {
				if(comp(foo, *it)) {
					//new smallest found
					_top.clear();
					_top.push_back(*it);
					foo = *it;
		
				} else if(comp(*it, foo)) {
					//no op, is not smallest
				} else {
					//equals, i. e. is also smallest
					_top.push_back(*it);
				}
			}
		}

		return _top.begin();
	}

	iterator top_end() {
		return _top.end();
	}

	bool empty() {
		return _items.empty();
	}

	void Dump() {
		if(QUEUE_DEBUG != true) return;


		//std::cout << "Queue contains: ";

		for(iterator it = _items.begin(); it != _items.end(); ++it) {
			(*it)->out();
		}

		//std::cout<< std::endl;
		//std::cout<< "Top contains: ";

		for(iterator it = top_begin(); it != top_end(); ++it) {
			(*it)->out();
		}

		//std::cout << std::endl << std::endl;
	}

protected:
	PartialOrder comp;
	Equivalence eqiv;
		
	//items in the queue
	std::vector< T> _items;

	//items on top of the queue
	std::vector< T> _top;
};