[Rtk-cvs] rtk/rtk DList.h,NONE,1.1

[<sp...@us...>]

Update of /cvsroot/rtk/rtk/rtk
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv14933/rtk

Added Files:
	DList.h 
Log Message:
Added tamplate based double linked list

--- NEW FILE: DList.h ---
/**
  *
  * RTK
  * Fast and easy cross-platform GUI ToolKit.
  *
  * Copyright (C) 2001-200x RTK Development Team
  *
  * This library is free software; you can redistribute it and/or modify it
  * under the terms of the slightly modified (see the "EXCEPTION NOTICE" part
  * of RTK Library License) GNU Lesser General Public License as published
  * by the Free Software Foundation; either version 2.1 of the License, or
  * (at your option) any later version.
  *
  * This library 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 Lesser General Public
  * License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public License
  * and along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA .
  *
  * Also you should have received a copy of RTK Library License, if not please
  * write an e-mail to some of RTK authors (listed in file AUTHORS).
  *
  * Bug reports: bu...@rt...
  * Suggestions: rf...@rt...
  ***************************************************************************/

/**
  * $Source: /cvsroot/rtk/rtk/rtk/DList.h,v $
  *****
  * Authors (chronological order):
  *   Pal Szasz, sp...@at...
  * Contributors (chronological order):
  *   $fname $lname, $email
  *****
  * T0D0 List:
  * -
  ***************************************************************************/

#ifndef _RTK_DLIST_H_
#define _RTK_DLIST_H_ 1


#include "rchar.h"

namespace Rtk
{

#if USE_TEMPLATES

/** Double linked list */
template <class T>
class DList
{
protected:

	/** Internal class to represent a node */
	class Node
	{
	public:
		Node* prev;
		Node* next;
		T value;

		Node(Node* p, Node* n, T v)
			:prev(p), next(n), value(v)
		{}
		Node(T v)
			:prev(NULL), next(NULL), value(v)
		{}
	}; // Node

	Node* _head; ///< Head of the list
	Node* _tail; ///< End of the list

	/** In subclassess this method can perform aditional memory deallocation */
	virtual void _Delete(Node* node) {
		// NOP
	}
	
public:
	DList()
		:_head(NULL), _tail(NULL)
	{}

	virtual ~DList()
	{
		Clear();
	}

	///////////////////////////////////////////////////////////////
	// Standard list operations
	///////////////////////////////////////////////////////////////

	void AddFront(T obj)
	{
		Node* node = new Node(NULL, _head, obj);
		if (_head == NULL) {
			_tail = node;
		} else {
			_head->prev = node;
		}
		_head = node;
	}

	T RemoveFront()
	{
		if (_head == NULL) return (T)0;
		T ret = _head->value;
		Node* nhead = _head->next;
		_Delete(_head);
		_head = nhead;
		_head->prev = NULL;
		return ret;
	}

	void AddTail(T obj)
	{
		Node* node = new Node(_tail, NULL, obj);
		if (_head == NULL) {
			_head = node;
		} else {
			_tail->next = node;
		}
		_tail = node;
	}

	T RemoveTail()
	{
		if (_tail == NULL) return (T)0;
		T ret = _tail->value;
		Node* ntail = _tail->prev;
		_Delete(_tail);
		_tail = ntail;
		_tail->next = NULL;
		return ret;
	}

	void Clear()
	{
		while (_head) {
			Node* tmp = _head;
			_head = _head->next;
			_Delete(tmp);
		}
	}
	
	///////////////////////////////////////////////////////////////
	// A few special things: add&sort, find, etc
	///////////////////////////////////////////////////////////////

	/**
	 Adds an object to the list to the corresponding position.
	 @param obj the object
	 @param fn_less a function which returns true if arg1 < arg2
	 */
	void Add(T obj, bool (*fn_less)(T obj1, T obj2))
	{
		if (_head == NULL) {
			_head = _tail = new Node(obj);
		} else {
			Node* cur = _head;
			while (cur && fn_less(cur->value, obj))
				cur = cur->next;
			if (cur == NULL) {
				AddTail(obj);
			} else {
				Node* node = new Node(cur->prev, cur, obj);
				if (node->prev) node->prev->next = node;
					else _head = node;
				if (node->next) node->next->prev = node;
					else _tail = node;
			}
		}
	}

	///////////////////////////////////////////////////////////////
	// Stack simulation
	///////////////////////////////////////////////////////////////

	inline void Push(T obj) { AddTail(obj); }
	inline T Pop() { return RemoveTail(); }

	///////////////////////////////////////////////////////////////
	// Queue simulation
	///////////////////////////////////////////////////////////////

	inline void Queue(T obj) { AddTail(obj); }
	inline T Dequeue() { return RemoveFront(); }

	///////////////////////////////////////////////////////////////
	// Iterators
	///////////////////////////////////////////////////////////////

	/** Forward/Backward iterator */
	class Iterator
	{
	protected:
		Node* _cur;
		bool _fwd;
	public:
		Iterator(Node* start, bool fwd = true)
			:_cur(start), _fwd(fwd)
		{}

		T Next()
		{
			T ret = (T)0;
			if (_cur) {
				ret = _cur->value;
				_cur = _fwd ? _cur->next : _cur->prev;
			}
			return ret;
		}
		
		const T Next() const
		{
			T ret = (T)0;
			if (_cur) {
				ret = _cur->value;
				_cur = _fwd ? _cur->next : _cur->prev;
			}
			return ret;
		}
	}; // Iterator

	/** Creates a forward iterator */
	Iterator* GetIterator()
	{
		Iterator* iter = new Iterator(_head);
		return iter;
	}

	/** Creates a backward iterator */
	Iterator* GetBackIterator()
	{
		Iterator* iter = new Iterator(_head, false);
		return iter;
	}

	///////////////////////////////////////////////////////////////
	// Filters (special iterators)
	///////////////////////////////////////////////////////////////

	/** Forward/Backward iterator */
	template <class T2>
	class Filter
	{
	protected:
		Node* _cur;
		bool _fwd;
		bool (*_fn)(T, T2);
		T2 _param;
	public:
		Filter(Node* start, bool (*fn)(T, T2), T2 param = (T2)0, bool fwd = true)
			:_cur(start), _fwd(fwd), _fn(fn), _param(param)
		{}

		T Next()
		{
			T ret;
			do {
				if (!_cur) return (T)0;
				ret = _cur->value;
				_cur = _fwd ? _cur->next : _cur->prev;
			} while (!_fn(ret, _param));
			return ret;
		}
	}; // Iterator

	/** Creates a filter */
	template <class T2>
	Filter<T2>* GetFilter(bool (*fn)(T, T2), T2 param = (T2)0, bool fwd = true)
	{
		Filter<T2>* filter = new Filter<T2>(fwd ? _head : _tail, fn, param);
		return filter;
	}

}; // DList

/** Double linked lists which deletes objects */
template <class T>
class DListP : public DList<T>
{
protected:
//	class Node : public DList<T>::Node {};
	
	void _Delete(typename DList<T>::Node* node)
	{
		delete node->value;
	}
public:
	~DListP()
	{
		Clear();
	}
};

typedef DList<int> IntDList;
typedef DList<RCHAR*> RCharDList;

#endif // USE_TEMPLATES

}; // namespace Rtk

#endif // _RTK_DLIST_H_

/**
  * $Id: DList.h,v 1.1 2004/02/26 20:07:41 space2 Exp $
  ***************************************************************************/