/*
   Copyright (C) 2004 Michael Nelson Moran

   This file is part of OSCL.

   OSCL is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   OSCL is distributed in the hope that it will be useful, but WITHOUT
   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
   License for more details.

   You should have received a copy of the GNU General Public License
   along with OSCL; see the file COPYING.  If not, write to the Free
   Software Foundation, 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.

   To negotiate other licensing arrangments/agreements contact
   the copyright holder:

   Michael N. Moran
   5009 Old Field Ct.         mike@mnmoran.org
   Kennesaw, GA, USA 30144    http://mnmoran.org
*/

#ifndef _oscl_queue_queueh_
#define _oscl_queue_queueh_
#include "queueitem.h"

/** */
namespace Oscl {

/** This template class implements a singly linked list
	which maintains a FIFO ordering.
 */
template <class qType>
	class Queue {
		private:

			/** Points to the first QueueItem in the list.
			 */
			qType*	_head;

			/** Points to the last QueueItem in the list.
			 */
			qType*	_tail;

		private:
			/** This copy constructor is intentionally NOT implemented.
				This would create two list heads with pointers to the
				same elements. In such a case, one list would be
				inconsistent if the content of one were changed.
			 */
			explicit Queue(const Queue&) throw();

		public:

			/** Public constructor initializes head and tail pointers.
			 */
			Queue() throw();

			/** Specialized copy constructor that moves "other"
				queue contents to this queue. The "other" queue
				is left empty.
			 */
			Queue(Queue& other) throw();

			/** This assignment operator moves the contents of the
				other queue into this queue. The other queue is
				emptied after the operation.
			 */
			Queue&	operator=(Queue& other) throw();

			/** Remove next element from queue and return a pointer to
				it as a result. qType must be a subclass of QueueItem.
			 */
			qType*	get(void) throw();

			/** Remove last element from queue and return a pointer to
				it as a result. qType must be a subclass of QueueItem.
			 */
			qType*	getLast(void) throw();

			/** Remove next element from beginning of the queue and
				return a pointer to it as a result. This operation
				does the same thing as the get() operation, but
				clarifies the use of the queue as a stack in combination
				with the push() operation.
				qType must be a subclass of QueueItem.
			 */
			qType*	pop(void) throw();

			/** Thread into the linked list at the end of the FIFO queue.
				qType is a subclass of QueueItem.
			 */
			void	put(qType* item) throw();

			/** Thread into the linked list at the beginning of the FIFO queue.
				qType is a subclass of QueueItem.
			 */
			void	push(qType* item) throw();

			/** Remove specified qType element from the queue.
				qType must be a subclass of QueueItem.
				Returns zero if the item is not found in
				the queue. Otherwise it returns item.
			 */
			qType*	remove(qType* item) throw();

			/** Insert the "item" qType into the queue behind the
				"after" qType element.
				qType must be a subclass of QueueItem.
			 */
			void	insertAfter(qType* after,qType* item) throw();

			/** Insert the "item" qType into the queue ahead of the
				"before" qType element.
				qType must be a subclass of QueueItem.
			 */
			void	insertBefore(qType* before,qType* item) throw();

			/** Return a pointer to the first qType item in the queue.
				The returned item remains in the queue.
				qType is a subclass of QueueItem.
			 */
			qType*	first(void) const throw();

			/** Return a pointer to the last qType item in the queue.
				The returned item remains in the queue.
				qType is a subclass of QueueItem.
			 */
			qType*	last(void) const throw();

			/** Return a pointer to the qType item after the qType item "prev".
				Both items remain in the queue.
				qType is a subclass of QueueItem.
			 */
			qType*	next(qType* prev) const throw();

		};

template <class qType>
	Queue<qType>::Queue(void) throw():_head(0),_tail(0){
		}

template <class qType>
Queue<qType>::Queue(Queue<qType>& other) throw(){
	_head	= other._head;
	_tail	= other._tail;
	other._head	= 0;
	other._tail	= 0;
	}

template <class qType>
Queue<qType>&	Queue<qType>::operator=(Queue<qType>& other) throw(){
	_head	= other._head;
	_tail	= other._tail;
	other._head	= 0;
	other._tail	= 0;
	return *this;
	}

template <class qType>
	inline qType* Queue<qType>::get(void) throw(){
		qType*			next;
		if((next = _head)){
			_head	= (qType*)next->__qitemlink;
			}
		return(next);
		}

template <class qType>
	inline qType* Queue<qType>::getLast(void) throw(){
		qType*			lastInQ;
		lastInQ	= last();
		if(!lastInQ) return 0;
		return remove(lastInQ);
		}

template <class qType>
	inline qType* Queue<qType>::pop(void) throw(){
		return get();
		}

template <class qType>
	inline void	Queue<qType>::put(qType* item) throw(){
		if(_head){
			_tail->__qitemlink	= item;
			}
		else{
			_head	= item;
			}
		_tail		= item;
		item->__qitemlink	= 0;
		}

template <class qType>
	inline void	Queue<qType>::push(qType* item) throw(){
		if(_head){
			item->__qitemlink	= _head;
			_head		= item;
			}
		else{
			_head	= _tail	= item;
			item->__qitemlink	= 0;
			}
		}

template <class qType>
	inline qType*	Queue<qType>::remove(qType* item) throw(){
		qType*			nxt;
		qType*			prv;
		for(nxt=first(),prv=0;nxt;prv=nxt,nxt=next(nxt)){
			if(nxt == item){
				if(prv){
					if(!(prv->__qitemlink=nxt->__qitemlink)){
						_tail	= prv;
						}
					}
				else{
					if(!(_head=(qType*)nxt->__qitemlink)){
						_tail	= 0;
						}
					}
				return item;
				}
			}
		return 0;
		}

template <class qType>
	inline void	Queue<qType>::insertAfter(qType* prev,qType* item) throw(){
		item->__qitemlink	= prev->__qitemlink;
		prev->__qitemlink	= item;
		}

template <class qType>
	inline void	Queue<qType>::insertBefore(qType* before,qType* item) throw(){
		qType*			nxt;
		qType*			prv;
		for(nxt=first(),prv=0;nxt;prv=nxt,nxt=next(nxt)){
			if(nxt == before){
				item->__qitemlink	= nxt;
				if(prv){
					prv->__qitemlink	=item;
					}
				else{
					_head		= item;
					}
				break;
				}
			}
		}

template <class qType>
	inline qType* Queue<qType>::first(void) const throw(){
		return(_head);
		}

template <class qType>
	inline qType* Queue<qType>::last(void) const throw(){
		if(_head){
			return _tail;
			}
		return 0;
		}

template <class qType>
	inline qType* Queue<qType>::next(qType* prev) const throw(){
		return((qType*)prev->__qitemlink);
		}

};

#endif