/* Web Polygraph       http://www.web-polygraph.org/
 * (C) 2003-2006 The Measurement Factory
 * Licensed under the Apache License, Version 2.0 */

#ifndef POLYGRAPH__XSTD_QUEUE_H
#define POLYGRAPH__XSTD_QUEUE_H



// general purpose queue with one big limitation:
// a given item can be in no more than one queue at a time

// implements basic queue item actions and holds pointers
class QueueItem {
	public:
		QueueItem(): thePrev(0), theNext(0) {}

		QueueItem *next() const { return theNext; }
		QueueItem *prev() const { return thePrev; }
		bool isolated() const { return !theNext && !thePrev; }

		void next(QueueItem *n) { theNext = n; if (n) n->thePrev = this; }
		void prev(QueueItem *p) { thePrev = p; if (p) p->theNext = this; }
		void isolate() { theNext = thePrev = 0; }

	protected:
		QueueItem *thePrev;
		QueueItem *theNext;
};

// a queue with default FIFO interface
template <class Item>
class Queue {
	public:
		Queue(): theCount(0) { theAncor.next(&theAncor); }

		int count() const { return theCount; }
		bool empty() const { return theCount == 0; }

		inline void enqueueAfter(QueueItem *x, Item *i);
		inline Item *dequeue(Item *i);

		Item *begin() { return firstOut(); }
		Item *end() { return 0; }
		Item *next(Item *i) { return i == lastIn() ? 0 : (Item*)i->next(); }
		
		// FIFO
		Item *firstOut() { return (Item*)theAncor.next(); }
		const Item *firstOut() const { return (const Item*)theAncor.next(); }
		Item *lastIn() { return (Item*)theAncor.prev(); }
		const Item *lastIn() const { return (const Item*)theAncor.prev(); }
		void enqueue(Item *i) { enqueueAfter(lastIn(), i); }
		Item *dequeue() { return dequeue(firstOut()); }

	protected:
		QueueItem theAncor;
		int theCount;
};

/* implementaion of in-lined methods */

template <class Item>
inline
void Queue<Item>::enqueueAfter(QueueItem *x, Item *i) {
	Assert(i->isolated());
	i->next(x->next());
	x->next(i);
	theCount++;
}

template <class Item>
inline
Item *Queue<Item>::dequeue(Item *i) {
	Assert(theCount > 0);
	i->prev()->next(i->next());
	i->isolate();
	theCount--;
	return i;
}

#endif