/*
 * rtlist.templ.cpp
 * 
 * Copyright (c) 2000-2004 by Florian Fischer (florianfischer@gmx.de)
 * and Martin Trautmann (martintrautmann@gmx.de) 
 * 
 * This file may be distributed and/or modified under the terms of the 
 * GNU General Public License version 2 as published by the Free Software 
 * Foundation. 
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 * 
 */

////////////// Implementation of the double-linked list template List

#ifndef __LRT_LIST_TEMPL__
#define __LRT_LIST_TEMPL__

#include "rtlist.h"

namespace lrt {

//template<class T> List<T>::Iterator List<T>::noElement;

template<class T> List<T>::List() : len(0), _begin(0), _end(0)
{}

template<class T> List<T>::List(const List<T> &list) : len(0),
	_begin(0), _end(0)
{
	for(Iterator<T> i = list.begin(); i.hasElement(); ++i)
	{
		append(*i);
	}
}

template<class T> List<T>& List<T>::operator=(const List<T> &list)
{
	clear();
	for(Iterator<T> i = list.begin(); i.hasElement(); ++i)
	{
		append(*i);
	}
	return *this;
}

template<class T> List<T>::~List()
{
	clear();
}

template<class T> T& List<T>::append( const T& elem )
{
	Node *newNode = new Node(elem);
	if(len == 0)
	{
		_begin = newNode;
		_end = newNode;
	}
	else 
	{
		_end->setNext(newNode);
		newNode->setPrev(_end);
		_end = newNode;
	}
	len++;
	return newNode->accessElement();
}

template<class T> T& List<T>::prepend( const T& elem )
{
	Node *newNode = new Node(elem);
	if(len == 0)
	{
		_begin = newNode;
		_end = newNode;
	}
	else 
	{
		newNode->setNext(_begin);
		_begin->setPrev(newNode);
		_begin = newNode;
	}
	len++;
	return newNode->accessElement();
}

template<class T> T& List<T>::insertBefore( Iterator<T> &p, const T& elem )
{
	IteratorImpl* pos = LRT_DYNAMIC_CAST(IteratorImpl*)(p.getImpl());
	if(!pos) return const_cast<T&>(elem);

	if(!pos->hasElement()) { return append(elem); }

	Node* bef = pos->element;
	if(bef == _begin) { return prepend(elem); }
	
	Node* after = bef->getPrev();
	Node* newNode = new Node(elem);

	after->setNext(newNode);
	newNode->setPrev(after);
	bef->setPrev(newNode);
	newNode->setNext(bef);
	
	len++;
	return newNode->accessElement();
}

template<class T> T& List<T>::insertAfter ( Iterator<T> &p, const T& elem )
{
	IteratorImpl* pos = LRT_DYNAMIC_CAST(IteratorImpl*)(p.getImpl());
	if(!pos) return const_cast<T&>(elem);

	if(!pos->hasElement()) { return append(elem); }

	Node* after = pos->element;
	if(after == _end) { return append(elem); }
	
	Node* bef = after->getNext();
	Node* newNode = new Node(elem);

	after->setNext(newNode);
	newNode->setPrev(after);
	bef->setPrev(newNode);
	newNode->setNext(bef);
	
	len++;
	return newNode->accessElement();
}

template<class T> void List<T>::remove( Iterator<T> &p )
{
	IteratorImpl* pos = LRT_DYNAMIC_CAST(IteratorImpl*)(p.getImpl());
	if(!pos) return; // only delete from List::Iterators!

	if(pos->list != this) return; // only delete from this list!
	if(!pos->hasElement()) return; // only delete from iterators with elements!

	Node* elem = pos->element;
	pos->goToNext(); // point the iterator to the next element (not to the deleted one)
	remove(elem);
}

template<class T> typename List<T>::Node* List<T>::remove(Node* node)
{
	Node* before = node->getPrev();
	Node* after = node->getNext();

	if(!before) { // remove _begin
		_begin = after;
	}
	else {
		before->setNext(after);
	}
	if(!after) { // remove _end
		_end = before;
	}
	else {
		after->setPrev(before);
	}

	delete node;
	len--;	

	return after;
}

template<class T> void List<T>::clear()
{
	Node* oldPos = 0;
	for(Node* pos = _begin; pos != 0; pos = pos->getNext())
	{
		delete oldPos;
		oldPos = pos;
	}
	delete oldPos; // last node

	_begin = 0;
	_end = 0;
	len = 0;
}

template<class T> int List<T>::length() const
{
	return len;
}

template<class T> int List<T>::getSize() const
{
	return len;
}

// unmodifyable iterators ("constant")
template<class T> Iterator<T> List<T>::begin() const
{
	return Iterator<T>(new IteratorImpl(const_cast<List<T>* const>(this), _begin, false));
}

template<class T> Iterator<T> List<T>::end() const
{
	return Iterator<T>(new IteratorImpl(const_cast<List<T>* const>(this), _end, false));
}

// modifyable iterators 
template<class T> Iterator<T> List<T>::begin()
{
	return Iterator<T>(new IteratorImpl(this, _begin, true));
}

template<class T> Iterator<T> List<T>::end()
{
	return Iterator<T>(new IteratorImpl(this, _end, true));
}


// Direct access to the list nodes
template<class T> typename List<T>::Node* List<T>::first()
{
	return _begin;
}
template<class T> typename List<T>::Node* List<T>::last()
{
	return _end;
}
template<class T> const typename List<T>::Node* List<T>::first() const
{
	return _begin;
}
template<class T> const typename List<T>::Node* List<T>::last() const
{
	return _end;
}

template<class T> void deleteNode(List<T>& list, typename List<T>::Node*& n)
{
	if(!n) return;
	delete n->accessElement();
	n = list.remove(n);
}


////////////////// Iterator
/*
template<class T> List<T>::Iterator::Iterator() : 
	element(0)
{}

// STL-like access
template<class T> List<T>::Iterator List<T>::Iterator::operator++() const
{
	if(element == 0) return List<T>::noElement;
	return Iterator(element->getNext());
}

template<class T> List<T>::Iterator& List<T>::Iterator::operator++(int)
{
	if(element == 0) return List<T>::noElement;
	element = element->getNext();
	return *this;
}

template<class T> List<T>::Iterator List<T>::Iterator::operator--() const
{
	if(element == 0) return List<T>::noElement;
	return Iterator(element->getPrev());
}

template<class T> List<T>::Iterator& List<T>::Iterator::operator--(int)
{
	if(element == 0) return List<T>::noElement;
	element = element->getPrev();
	return *this;
}

template<class T> T& List<T>::Iterator::operator*()
{
	return element->accessElement();
}

template<class T> const T& List<T>::Iterator::operator*() const
{
	return element->accessElement();
}

template<class T> bool List<T>::Iterator::operator==( const Iterator & iter) const
{
	return (element == iter.element);
}

// Java-like access

template<class T> T& List<T>::Iterator::next()
{
	Node* ret = element;
	if(ret != 0) element = ret->getNext();
	return ret->accessElement();
}

template<class T> bool List<T>::Iterator::hasNext() const
{
	if(!element) return false;
	return (element->getNext() != 0);
}

template<class T> bool List<T>::Iterator::hasPrev() const
{
	if(!element) return false;
	return (element->getPrev() != 0);
}

template<class T> bool List<T>::Iterator::hasElement() const
{
	return (element != 0);
}

template<class T> List<T>::Iterator List<T>::Iterator::getNext() const
{
	if(!element) return List<T>::noElement;
	return Iterator(element->getNext());
}

//// Iterator:: private
template<class T> List<T>::Iterator::Iterator( Node* el) : 
	element(el)
{}

*/
/*
//////////////// Node /////////////////////

template<class T> List<T>::Node::Node( const T &element ) : 
	element(element), next(0), prev(0)
{	
}

template<class T> List<T>::Node* List<T>::Node::getNext() const
{
	return next;
}

template<class T> List<T>::Node* List<T>::Node::getPrev() const
{
	return prev;
}

template<class T> void List<T>::Node::setNext( Node* node)
{
	next = node;
}

template<class T> void List<T>::Node::setPrev( Node* node)
{
	prev = node;
}

template<class T> T& List<T>::Node::accessElement()
{
	return element;
}
*/

} // namespace

#endif