/*********************************************************************
 * This file is part of the cpplibs suite.
 *
 * Copyright (C) 2001 Topi Mäenpää
 * All rights reserved.
 *
 * This program is free software. You can redistribute and/or modify
 * it under the terms of the free software licence found in the
 * accompanying file "COPYING". The licence terms must always be
 * redistributed with this source file. The above copyright notice
 * must be reproduced in all modified and unmodified copies of this
 * source file.
 *
 * $Revision: 1.5 $
 *********************************************************************/

#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H

#include <stdlib.h>
#include "Object.h"

namespace util
{
	/**
	 * LinkedList objects can be used to create linked lists. Each
	 * object represents one node in the list. Each node is created
	 * initially unlinked, and deleting a node deletes all nodes
	 * following the deleted one.
	 **/
	template <class content> class LinkedList : virtual public Object
	{
	public:
		/**
		 * Create an unlinked node with the contents initialized to a
		 * default value.
		 **/
		LinkedList(void) : _pNext(NULL) {}
		/**
		 * Create an unlinked node with the given contents.
		 * @param obj the object to be stored in this list node
		 **/
		LinkedList(const content& obj) : _pNext(NULL), _item(obj) {}

		/**
		 * Delete this node and all successors.
		 **/
		virtual ~LinkedList() { delete _pNext; }

		/**
		 * Get a pointer to the next node in sequence.
		 * @return the next node or NULL if this is the last one
		 **/
		LinkedList* getNext(void) { return _pNext; }
		/**
		 * Get a const pointer to the next node in sequence.
		 * @return the next node or NULL if this is the last one
		 **/
		const LinkedList* getNext(void) const { return _pNext; }
		/**
		 * Set the next node for this node.
		 * @param node the next node for this node
		 **/
		virtual void setNext(LinkedList* node) { _pNext = node; }
		/**
		 * Insert a linked list after this node. The whole list pointed by
		 * <i>node</i> is inserted after this node.
		 * @param node the list to be inserted
		 **/
		virtual void insertAfter(LinkedList* node);

		/**
		 * Get the data stored in this node.
		 * @return the data
		 **/
		content getData(void) const { return _item; }
		/**
		 * Get a reference to the stored data.
		 **/
		content& data(void) { return _item; }
		/**
		 * Get a const reference to the stored data.
		 **/
		const content& data(void) const { return _item; }
		/**
		 * Set the data stored in this node.
		 * @param obj the new data
		 **/
		void setData(const content& obj) { _item = obj; }

		/**
		 * Get the number of nodes in a sequence. If this node has no
		 * successors, the return value is one.
		 *
		 * @return the number of nodes following this one + 1
		 **/
		int getLength(void) const { return _pNext ? _pNext->getLength()+1 : 1; }

		/**
		 * Remove a given node from the sequence following this node. The
		 * successors of the current node are searched until <i>node</i>
		 * is found. The node is then removed from the list but not deleted.
		 * @param node the node to be removed
		 * @return a pointer to the removed node or NULL if it was not found
		 **/
		virtual LinkedList* remove(LinkedList* node);
		/**
		 * Remove a given node from the sequence following this node. The
		 * successors of the current node are searched until a node with
		 * contents equal to <i>obj</i> is found. The node is then
		 * removed from the list but not deleted.
		 * @param obj the data whose container is to be removed
		 * @return a pointer to the removed node or NULL if it was not found
		 **/
		virtual LinkedList* remove(const content& obj);

		/**
		 * Get the last element in a linked list. The sequence is seeked
		 * until getNext returns NULL.
		 *
		 * @return the last element in a sequence
		 **/
		const LinkedList* getLastElement(void) const { return _pNext ? _pNext->getLastElement() : this; }

		/**
		 * Get the last element in a linked list. The sequence is seeked
		 * until getNext returns NULL.
		 *
		 * @return the last element in a sequence
		 **/
		LinkedList* getLastElement(void) { return _pNext ? _pNext->getLastElement() : this; }
		
	protected:
		/**
		 * A pointer to the next element in sequence.
		 **/
		LinkedList* _pNext;
		/**
		 * The data stored in this node.
		 **/
		content _item;
	};

	template <class content> void LinkedList<content>::insertAfter(LinkedList<content>* node)
	{
		if (node)
			node->getLastElement()->_pNext = _pNext;
		_pNext = node;
	}

	template <class content> LinkedList<content>* LinkedList<content>::remove(LinkedList<content>* node)
	{
		LinkedList<content>* previousNode = this, *currentNode = _pNext, *nextNode = NULL;
		while (currentNode)
			{
				nextNode = currentNode->_pNext;
				if (currentNode == node)
					{
						previousNode->_pNext = nextNode;
						currentNode->_pNext = NULL;
						return currentNode;
					}
				previousNode = currentNode;
				currentNode = currentNode->_pNext;
			}
		return NULL;
	}

	template <class content> LinkedList<content>* LinkedList<content>::remove(const content& obj)
	{
		LinkedList<content>* previousNode = this, *currentNode = _pNext, *nextNode = NULL;
		while (currentNode)
			{
				nextNode = currentNode->_pNext;
				if (currentNode->_item == obj)
					{
						previousNode->_pNext = nextNode;
						currentNode->_pNext = NULL;
						return currentNode;
					}
				previousNode = currentNode;
				currentNode = currentNode->_pNext;
			}
		return NULL;
	}

	/**
	 * Doubly linked list is an stronger version of the basic linked
	 * list. It features bidirectional links and can thus be searched in
	 * two directions.
	 **/
	template <class content> class DoublyLinkedList : public LinkedList<content>
	{
	public:
		/**
		 * Create an unlinked node.
		 **/
		DoublyLinkedList(void) : _pPrevious(NULL) {}
		/**
		 * Create an unlinked node with the given contents.
		 **/
		DoublyLinkedList(const content& obj) : LinkedList<content>(obj), _pPrevious(NULL) {}

		/**
		 * Set the next node for this node. The internal pointer to the
		 * next node and the "previous" pointer in <i>node</i> are
		 * updated.
		 *
		 * @param node the node to be set as the "next" node
		 **/
		void setNext(DoublyLinkedList* node);
		/**
		 * Calls setNext(DoublyLinkedList*)
		 **/
		void setNext(LinkedList<content>* node) { setNext((DoublyLinkedList*)node); }

		/**
		 * Insert a sequence of nodes after this node. <i>Node</i> is set
		 * to be the "next" for this node, and the last item in the linked
		 * list <i>node</i> is set to be the "previous" of the current
		 * "next" node.
		 *
		 * @param node the linked list that is to be inserted after this node
		 **/
		void insertAfter(DoublyLinkedList* node);
		/**
		 * Calls insertAfter(DoublyLinkedList*)
		 **/
		void insertAfter(LinkedList<content>* node) { insertAfter((DoublyLinkedList*)node); }

		/**
		 * Remove this node from a linked list.
		 **/
		void remove();

		/**
		 * Get the first element in this list. The sequence is seeked
		 * backwards until "getPrevious" returns NULL.
		 *
		 * @return the first node in a sequence
		 **/
		const DoublyLinkedList* getFirstElement(void) const { return _pPrevious ? _pPrevious->getFirstElement() : this; }

		/**
		 * Get the first element in this list. The sequence is seeked
		 * backwards until "getPrevious" returns NULL.
		 *
		 * @return the first node in a sequence
		 **/
		DoublyLinkedList* getFirstElement(void) { return _pPrevious ? _pPrevious->getFirstElement() : this; }

	protected:
		/**
		 * A pointer to the previous element in a sequence.
		 **/
		DoublyLinkedList* _pPrevious;
	};

	template <class content> void DoublyLinkedList<content>::setNext(DoublyLinkedList* node)
	{
		node->_pNext = _pNext;
		if (_pNext)
			_pNext->_pPrevious = node;
	}

	template <class content> void DoublyLinkedList<content>::insertAfter(DoublyLinkedList* node)
	{
		if (node)
			{
				DoublyLinkedList* last = (DoublyLinkedList*)node->getLastElement();
				last->_pNext = _pNext;
				if (_pNext)
					_pNext->_pPrevious = last;
				node->_pPrevious = this;
			}
		_pNext = node;
	}

	template <class content> void DoublyLinkedList<content>::remove(void)
	{
		if (_pNext)
			_pNext->_pPrevious = _pPrevious;
		if (_pPrevious)
			_pPrevious->_pNext = _pNext;

		_pPrevious = NULL;
		_pNext = NULL;
	}


	/**
	 * A linked list that maintains its elements in sorted order.
	 **/
	template <class content> class SortedLinkedList : public LinkedList<content>
	{
	public:
		/**
		 * Create an empty sorted linked list.
		 **/
		SortedLinkedList() {}
		/**
		 * Create an unlinked node with the given contents.
		 **/
		SortedLinkedList(const content& data) : LinkedList<content>(data) {}

		/**
		 * Add a node to this linked list, maintaining sort order. The
		 * list is seeked until a node with a content item not smaller
		 * than the provided one is found. The cardinality is checked
		 * using the < operator. The new node is inserted just before the
		 * found node, or to the end of the list if no applicable node
		 * cannot be found.<p>
		 *
		 * Using this method ensures that nodes are always sorted
		 * according to their contents. If you add nodes in any other way,
		 * the order cannot be guaranteed.
		 *
		 * @param node the node to be inserted to this list
		 * @return the node after which the new node was inserted. If the
		 *         return value is NULL, then the node was inserted to the
		 *         beginning of the list. In this case you must ensure that
		 *         your pointer to the beginning to the list is updated.
		 **/
		SortedLinkedList* addNode(SortedLinkedList* node);
	};

	template <class content> SortedLinkedList<content>* SortedLinkedList<content>::addNode(SortedLinkedList<content>* node)
	{
		LinkedList<content>* currentNode = this, *previousNode = NULL;
		while (currentNode && currentNode->data() < node->data())
			{
				previousNode = currentNode;
				currentNode = currentNode->getNext();
			}

		if (previousNode)
			previousNode->setNext(node);
		node->setNext(currentNode);

		return dynamic_cast<SortedLinkedList<content>*>(previousNode);
	}
}

#endif