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

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

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

Added Files:
	Vector.h 
Log Message:
Added tamplate based Vector class

--- NEW FILE: Vector.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/Vector.h,v $
  *****
  * Authors (chronological order):
  *   Pal Szasz, sp...@at...
  * Contributors (chronological order):
  *   $fname $lname, $email
  *****
  * T0D0 List:
  * -
  ***************************************************************************/

#ifndef _RTK_VECTOR_H_
#define _RTK_VECTOR_H_ 1

#include <stdlib.h> // malloc, realloc, free

#include "rchar.h"

namespace Rtk
{

#if USE_TEMPLATES

/**
 A (bit more) complex Array Class.
 Currently the resize policy is follows: when the array is full, the size
 is doubled. Should we implement that the use can select another policy?

 This class's Delete methoed does NOTHING. In order to really delete objects
 use the VectorP class (P stands for Pointer).
 */
template <class T>
class Vector
{
protected:
	bool _dealloc; ///< Should we deallocate objects
	int _size; ///< The number of allocated cells
	int _count; ///< The number of objects
	T* _data; ///< The stored objects

	void _Resize(int new_size)
	{
		_data = (T*)realloc(_data, new_size*sizeof(T));
	}

	/** This method deletes a given item.
	 In the base class nothing is done
	*/
	virtual void _Delete(int idx) { /* NOP */ }
public:
	/**
	 Constructs the Vector object allocating a predefined number of cells/slots
	 @param def_size the default size of the array
	 */
	Vector(int def_size = 4)
	:_dealloc(false), _size(def_size), _count(0)
	{
		_data = (T*)malloc(_size * sizeof(T));
	}

	/** Free the memory.
	 If dealloc is true, each object is deleted with delete.
	 */
	virtual ~Vector()
	{
		free(_data);
	}

	/** Returns the number of elements */
	int GetCount() const { return _count; }

	/** Returns the number of allocated cells */
	int GetSize() const { return _size; }

	/** Allocated the given number of cells.
	 @return false if there are more elements then the given number of cells,
	 so the resize operation cannot be done.
	 */
	bool SetSize(int new_size)
	{
		if (new_size < _count) return false;
		_Resize(new_size);
		return true;
	}

	///////////////////////////////////////////////////////////////
	// Standard Vector operations (add/delete/find)
	///////////////////////////////////////////////////////////////

	/** Removes all elements */
	void Clear()
	{
		if (_dealloc) {
			for(int i = 0; i < _count; i++)
				_Delete(i);
		}
		_count = 0;
	}

	/** Removes the n-th element.
	 @param idx the position of the element
	 @return true if it was successfull
	*/
	bool Remove(int idx)
	{
		if (idx < 0 || idx >= _count) return false; // invalid index
		if (_dealloc) _Delete(idx);
		_count--;
		while (idx < _count) {
			_data[idx] = _data[idx+1];
			idx++;
		}
		if (_count*4 < _size)
			_Resize(_size/2);
		return true;
	}

	/** Adds a new object the end of the array
	 @param obj the object to add
	 @return the index where it was added
	*/
	int Add(T obj)
	{
		if (_count == _size)
			_Resize(_size*2);
		_data[_count++] = obj;
		return _count-1;
	}

	/** Adds a new object at the given position
	 @param obj the object to add
	 @param idx the position where to add
	 @return true if it was successfull
	*/
	bool Add(T obj, int idx)
	{
		if (idx < 0) idx = 0;
		if (idx > _count) idx = _count;
		if (_count == _size)
			_Resize(_size*2);
		for(int i = _count; i > idx; i--)
			_data[i] = _data[i-1];
		_data[idx] = obj;
		_count++;
		return true;
	}

	/** Find the position of the given element.
	 It supports multiple searches: declare an integer variable,
	 set it to 0 and give a pointer to this integer as second argument.
	 The function will store the index where he can continue searching in
	 thi value.
	 @param obj the object to look up
	 @param idx where to start/continue
	 @return the index or -1 if not found
	*/
	int Find(const T obj, int* idx = NULL) const
	{
		int first = (idx == NULL) ? 0 : *idx;
		for(int i = first; i < _count; i++)
			if (obj == _data[i]) {
				if (idx) *idx = i+1;
				return i;
			}
		return -1;
	}

	/** Find the object using a function.
	 The function has two parameters, the first will be the
	 items in the array, the second is a user specified value.
	 @param fn the comparision function
	 @param param the second parameter to the comparision function
	 @param idx where to start/continue
	 @return the index of the object or -1 if not found
	 */
	template <class T2>
	int Find(bool (*fn)(const T obj, T2 obj2), T2 param, int* idx = NULL)
	{
		int first = (idx == NULL) ? 0 : *idx;
		for(int i = first; i < _count; i++)
			if (fn(_data[i], param)) {
				if (idx) *idx = i+1;
				return i;
			}
		return -1;
	}

	/** A search iterator.
	 This iterator can be usefull to easily search the Vector.
	 Just call the Next() method to get the next object.
	 */
	template <class T2>
	class SearchIterator
	{
		protected:
			int _idx;
			Vector<T>& _v;
			bool (*_fn)(const T obj, T2 obj2);
			T2 _param;
		public:
			SearchIterator(Vector<T>& v, bool (*fn)(const T obj, T2 obj2), T2 param)
			:_idx(0), _v(v), _fn(fn), _param(param)
			{}

			T Next()
			{
				int pos = _v.Find(_fn, _param, &_idx);
				if (pos < 0) return (T)0;
				return _v.At(pos);
			}

			const T Next() const
			{
				int pos = _v.Find(_fn, _param, &_idx);
				if (pos < 0) return (T)0;
				return _v.At(pos);
			}
	}; // SearchIterator

	/** Create a search iterator */
	template <class T2>
	SearchIterator<T2>* Search(bool (*fn)(const T obj, T2 obj2), T2 param)
	{
		return new SearchIterator<T2>(*this, fn, param);
	}

	/** Returns the n-th item.
	 @param idx the position of the item
	 @return 0 typecasted to T if index is out of bounds, otherwise the item
	 */
	T Get(int idx)
	{
		if (idx < 0 || idx >= _count) return (T)0;
		return _data[idx];
	}

	/** Returns the n-th item.
	 @param idx the position of the item
	 @return 0 typecasted to T if index is out of bounds, otherwise the item
	 */
	const T Get(int idx) const
	{
		if (idx < 0 || idx >= _count) return (T)0;
		return _data[idx];
	}

	/** Returns a reference to the n-th item.
	 @param idx the position of the item
	 @return the reference to the item, no range checking is done
	 */
	T& At(int idx)
	{
		return _data[idx];
	}

	/** Returns a constant reference to the n-th item.
	 @param idx the position of the item
	 @return the reference to the item, no range checking is done
	 */
	const T& At(int idx) const
	{
		return _data[idx];
	}

	/** Returns a reference to the n-th item.
	 @param idx the position of the item
	 @return the reference to the item, no range checking is done
	 */
	inline T& operator[](int idx)
	{
		return _data[idx];
	}

	/** Returns a constant reference to the n-th item.
	 @param idx the position of the item
	 @return the reference to the item, no range checking is done
	 */
	inline const T& operator[](int idx) const
	{
		return _data[idx];
	}
	///////////////////////////////////////////////////////////////
	// Simulate a stack
	///////////////////////////////////////////////////////////////

	/** Simulate a stack push */
	inline void Push(T obj)
	{
		Add(obj);
	}

	/** Simulate a stack pop.
	 When the stack is empty returns 0 typecasted to T
	*/
	inline T Pop()
	{
		if (_count == 0) return (T)0;
		return _data[--_count];
	}

	/** Returns the top of the stack */
	inline T Top() const
	{
		return _data[_count-1];
	}

	///////////////////////////////////////////////////////////////
	// Simulate a queue
	///////////////////////////////////////////////////////////////

	/** Adds an item to the end of the queue */
	inline void Queue(T obj)
	{
		Add(obj);
	}

	/** Removes and returns the item from the head of the queue */
	T Dequeue()
	{
		T ret = _data[0];
		_count--;
		for(int i = 0; i < _count; i++)
			_data[i] = _data[i+1];
		return ret;
	}

}; // class Vector

/**
 This version of Vector deletes object in the Delete method (if dealloc == true).
 */
template <class T>
class VectorP: public Vector<T>
{
protected:
	void _Delete(int idx)
	{
		delete _data[idx];
	}

public:
	VectorP(int def_size = 4)
		:Vector<T>(def_size)
	{
		_dealloc = true;
	}

	~VectorP()
	{
		Clear();
	}
};

typedef Vector<int> IntVector;
typedef Vector<RCHAR*> RCharVector;

#endif // USE_TEMPLATES

}; // namespace Rtk

#endif // _RTK_VECTOR_H_

/**
  * $Id: Vector.h,v 1.1 2004/02/26 20:05:32 space2 Exp $
  ***************************************************************************/