l3lib/l3lib_vc2003/llqueue.h

//:Header:82, "queue", 3b93fb4c
//
// File: llqueue.h
//
// G A M E.O.N.E - LOW LEVEL LIB V1.0
// Copyright (C) 2001 LEVEL ONE ENTERTAINMENT, 
// Licensed under the terms of LGPL.
//:---------------------------------------------------------------------------
//:Description
// Fast all purpose queue template class
//
//:-----------------------------------------------------------------------------

#if !defined(_LLQUEUE_H)
#define _LLQUEUE_H

//:Include
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <search.h>
#include <memory.h>
#include "llmem.h"

//:Custom
#define LLQUEUE_DEFAULT_SIZE	(32)
#define EXPANDFAILED(s) DebugOutLn("Expand queue failed");
#define INDEXFAILED(s) DebugOutLn("Invalid Queue index");
//:End Custom

//:>                     +-------------------------------+
//:>---------------------|    queue Class Declaration    |----------------------
//:>                     +-------------------------------+
//:Class

template<
	typename T >

class queue
{

  public:

	//::1
	// +---------------+
	// |  Constructor  |
	// +---------------+

	queue();

	//::2
	// +--------------+
	// |  Destructor  |
	// +--------------+

	~queue();

	//::3
	// +-----------+
	// |  Clear()  |
	// +-----------+

	//:Description
	//
	// Setzt die Anzahl der Elemente auf 0. Logisches Löschen.
	//
	inline void Clear();

	//::6
	// +---------+
	// |  Get()  |
	// +---------+

	//:Description
	//
	// Entfernt einen Elementpointer vom Ende der Queue.
	//
	inline T * Get();

	//::4
	// +----------+
	// |  Init()  |
	// +----------+

	//:Description
	//
	// Setzt Initialgrösse des Arrays.
	// Aktuelles Array wird dabei zerstört und durch die neue grösse Ersetzt.
	// Alle Variablen werden Resetet.
	//
	void Init(
		int imax);

	//::10
	// +-------------+
	// |  InQueue()  |
	// +-------------+

	//:Description
	//
	// Liefert Anzahl der Elemente.
	//
	inline int InQueue();

	//::11
	// +-------------+
	// |  IsEmpty()  |
	// +-------------+

	//:Description
	//
	// Liefert true wenn die Queue leer ist.
	//
	inline bool IsEmpty() const;

	//::14
	// +----------+
	// |  Next()  |
	// +----------+

	//:Description
	//
	// Liefert ElementPtr an der aktuellen Iteration-Index Stelle.
	// Bei jedem Aufruf von Next() wird der Interations-Index um eins erhöht.
	// Ist der Index ungültig, d.h. Ausserhalb des Arrays, dann wird 0 geliefert und
	// der Iterations-Index auf 0 gesetz.
	//
	inline T * Next();

	//::15
	// +-----------------+
	// |  NextNoReset()  |
	// +-----------------+

	//:Description
	//
	// Liefert ElementPtr an der aktuellen Iteration-Index Stelle.
	// Bei jedem Aufruf von Next() wird der Interations-Index um eins erhöht.
	// Ist der Index ungültig, d.h. Ausserhalb des Arrays, dann wird 0 geliefert.
	//
	// Im Gegensatz zur Funktion Next(), wird der Iteration-Index nicht zurückgestellt.
	// Jeder weiterer Aufruf von NextNoReset() liefert eine 0.
	//
	inline T * NextNoReset();

	//::16
	// +-----------------+
	// |  operator []()  |
	// +-----------------+

	//:Description
	//
	//  Direct Access
	//
	T * operator [](
		int i) const;

	//::5
	// +---------+
	// |  Put()  |
	// +---------+

	//:Description
	//
	// Hängt neuen Elementpointer an den NormalStack.
	//
	inline void Put(
		T *element);

	//::5
	// +---------+
	// |  Put()  |
	// +---------+
	
	//:Description
	//
	// Insert Element an Stelle 0.
	//
	inline void PutFront(
		T *element);


	// Insert Element an Stelle idx
	inline void InsertAt(int idx, T *element);

	// Entfernt Element an Stelle idx
	inline T* RemoveAt(int idx);
	inline int Remove(T * element);

	//::13
	// +-----------+
	// |  Reset()  |
	// +-----------+

	//:Description
	//
	// Setzt Inerations-Index auf 0. Entspricht Set(0).
	//
	inline void Reset();

	//::12
	// +---------+
	// |  Set()  |
	// +---------+

	//:Description
	//
	// Setzt den Iteration-Index.
	//
	inline void Set(
		int index);

	//::17
	// +-----------+
	// |  SetAt()  |
	// +-----------+

	//:Description
	//
	// Direktzugriff auf das Stack Array.
	// Tauscht den Pointer an der Stelle 'i',
	// liefert vorherigen Wert.
	//
	T * SetAt(
		int i,
		T* newvalue);


	//::18
	// +----------+
	// |  Sort()  |
	// +----------+

	//:Description
	//
	// QuickSort
	//
	void Sort(
		int (*compare)(const void *, const void *));


	//:=6
	// +----------+
	// |  m_Qptr  |
	// +----------+

	T * * m_Qptr;

	//:=8
	// +------------+
	// |  m_array1  |
	// +------------+

	T * * m_array1;


	//:=11
	// +--------------------+
	// |  m_iterator_index  |
	// +--------------------+

	int m_iterator_index;

	//:=12
	// +------------------+
	// |  m_num_elements  |
	// +------------------+

	int m_num_elements;


	//:=14
	// +------------------+
	// |  m_max_elements  |
	// +------------------+

	int m_max_elements;

	//::19
	// +-----------------+
	// |  ExpandQueue()  |
	// +-----------------+

	void ExpandQueue();

};

//:>                     +-------------------------------+
//:>---------------------|    queue Iterator Class       |----------------------
//:>                     +-------------------------------+
//:Class
template<
typename T >

class queue_itr
{
	
  public:
	  
	  //::1
	  // +---------------+
	  // |  Constructor  |
	  // +---------------+
	  
	  queue_itr<T>(queue<T> &queue_to_iterate ) : m_Q(queue_to_iterate)
	  {
		m_local_iterator_index = m_Q.m_iterator_index;
		m_local_iterator_index = 0;
	  };

	  T * Next()
	  {
		  if( m_local_iterator_index < m_Q.m_num_elements )
			  return m_Q.m_array1[m_local_iterator_index++];
		  // reset:
		  m_local_iterator_index = 0;
		  return 0;
	  }

	  T * NextNoReset()
	  {
		  if( m_local_iterator_index < m_Q.m_num_elements )
			  return m_Q.m_array1[m_local_iterator_index++];
		  // No reset: m_local_iterator_index = 0;
		  return 0;
	  }

	  void Reset()
	  {
		  m_local_iterator_index = 0;
	  }

  private:
	queue<T> & m_Q;
	int  m_local_iterator_index;
};
	  
//:>                   +-----------------------------------+
//:>-------------------|    Member Function Definitions    |--------------------
//:>                   +-----------------------------------+

//::1
// +---------------+
// |  Constructor  |
// +---------------+

template<
	typename T >

queue<T>::queue()
{
	m_array1=0;
	Clear();
	m_max_elements=0;
	m_num_elements=0;
}

//::2
// +--------------+
// |  Destructor  |
// +--------------+

template<
	typename T >

queue<T>::~queue()
{
	Clear();
	if( m_array1 ) llmem_free(m_array1);
	m_array1=0;
}

//::3
// +-----------+
// |  Clear()  |
// +-----------+

template<
	typename T >

inline void queue<T>::Clear()
{
	m_num_elements=0;
	m_iterator_index=0;
	m_Qptr=m_array1;
}

//::19
// +-----------------+
// |  ExpandQueue()  |
// +-----------------+

template<
	typename T >

void queue<T>::ExpandQueue()
{
	int	newsize = m_max_elements;
	newsize += (newsize>>1);
	if(!newsize) newsize=LLQUEUE_DEFAULT_SIZE;
	
	m_array1	=	(T**)llmem_realloc(m_array1,newsize*sizeof(T*));
	if(!m_array1) EXPANDFAILED(newsize*sizeof(T*));
	
    m_Qptr =  m_array1;
	m_Qptr += m_num_elements;
	
	m_max_elements = newsize;
}

//::6
// +---------+
// |  Get()  |
// +---------+

template<
	typename T >

inline T * queue<T>::Get()
{
	if( m_num_elements > 0 )
	{
	    m_num_elements--;
	    return *--m_Qptr;
	}
	return 0;
}

//::4
// +----------+
// |  Init()  |
// +----------+

template<
	typename T >

void queue<T>::Init(
	int imax)
{
	Clear();
	m_max_elements	= imax>0?imax:LLQUEUE_DEFAULT_SIZE;
	ExpandQueue();
}

//::10
// +-------------+
// |  InQueue()  |
// +-------------+

template<
	typename T >

inline int queue<T>::InQueue()
{
	return m_num_elements;
}

//::11
// +-------------+
// |  IsEmpty()  |
// +-------------+

template<
	typename T >

inline bool queue<T>::IsEmpty() const
{
	return	m_num_elements == 0 ? true : false;
}

//::14
// +----------+
// |  Next()  |
// +----------+

template<
	typename T >

inline T * queue<T>::Next()
{
	if( m_iterator_index < m_num_elements )
	{
    	return m_array1[m_iterator_index++];
	}
	Reset();
	return 0;
}

//::15
// +-----------------+
// |  NextNoReset()  |
// +-----------------+

template<
	typename T >

inline T * queue<T>::NextNoReset()
{
	if( m_iterator_index < m_num_elements )
	{
    	return m_array1[m_iterator_index++];
	}
	return 0;
}

//::16
// +-----------------+
// |  operator []()  |
// +-----------------+

template<
	typename T >

T * queue<T>::operator [](
	int i) const
{
	if( i >= 0 && i < m_num_elements )
	{
    	return m_array1[i];
	}
	return 0;
}

//::5
// +---------+
// |  Put()  |
// +---------+

template<
	typename T >

inline void queue<T>::Put(
	T *element)
{
	if( m_num_elements < m_max_elements )
	{
	    m_num_elements++;
	    *m_Qptr++=element;
	    return;
	}
	
	ExpandQueue();
	
	m_num_elements++;
	*m_Qptr++=element;
	return;
}


//::5
// +--------------+
// |  InsertAt()  |
// +--------------+

template<
typename T >

inline void queue<T>::InsertAt(int idx,
							   T *element)
{
	if( idx > m_num_elements )
		INDEXFAILED(idx);

	if( (m_num_elements + 1) < m_max_elements )
	{
		memmove( &m_array1[idx+1], &m_array1[idx], (m_num_elements-idx)*sizeof(T*) );
		m_array1[idx]=element;
		
		m_num_elements++;
		m_Qptr++;
		return;
	}
	
	ExpandQueue();
	InsertAt(idx, element);
}

//::5
// +--------------+
// |  RemoveAt()  |
// +--------------+

template<
typename T >

T* queue<T>::RemoveAt(int idx)
{
	if( idx > m_num_elements )
		INDEXFAILED(idx);

	T* rc;

	if( m_num_elements > 0 )
	{
			
		rc = m_array1[idx];
		memmove( &m_array1[idx], &m_array1[idx+1], (m_num_elements-idx-1)*sizeof(T*) );
		
		if( m_iterator_index > 0 && m_iterator_index >= idx )
			m_iterator_index --;
		m_num_elements--;
		m_Qptr--;
		return rc;
	}

	return NULL;
}

//::5
// +---------------------+
// |  Remove(T *element) |
// +---------------------+

template<
typename T >
int queue<T>::Remove(T * element)
{
	int rc = 0;

	for( int idx = 0 ; idx < m_num_elements; idx ++ )
	{
		if( m_array1[idx] == element )
		{
			memmove( &m_array1[idx], &m_array1[idx+1], (m_num_elements-idx-1)*sizeof(T*) );
			if( m_iterator_index > 0 && m_iterator_index >= idx )
				m_iterator_index --;
			m_num_elements--;
			m_Qptr--;
			idx--;
			rc++;
		}
	}

	return rc; // remove count
}


//::5
// +--------------+
// |  PutFront()  |
// +--------------+

template<
typename T >

inline void queue<T>::PutFront(
						  T *element)
{
	if( m_num_elements < m_max_elements )
	{
		memmove( &m_array1[1], &m_array1[0], m_num_elements*sizeof(T*) );
		m_array1[0]=element;

		m_num_elements++;
		m_Qptr++;
		return;
	}
	
	ExpandQueue();
	PutFront(element);
}

//::13
// +-----------+
// |  Reset()  |
// +-----------+

template<
	typename T >

inline void queue<T>::Reset()
{
	m_iterator_index=0;
}

//::12
// +---------+
// |  Set()  |
// +---------+

template<
	typename T >

inline void queue<T>::Set(
	int index)
{
	m_iterator_index=index<0?0:index;
}

//::17
// +-----------+
// |  SetAt()  |
// +-----------+

template<
	typename T >

T * queue<T>::SetAt(
	int i,
	T* newvalue)
{
	T* oldvalue;
	if( i < m_num_elements )
	{
		oldvalue=m_array1[i];
		m_array1[i]=newvalue;
		return oldvalue;
	}
	INDEXFAILED(i);
	return 0;
}

//::18
// +----------+
// |  Sort()  |
// +----------+
template<
	typename T >

void queue<T>::Sort( int(*compare)(const void *, const void *) )
{
	qsort(m_array1,m_num_elements,sizeof(T*),compare);
}



#endif  							 // _LLQUEUE_H