l3lib/l3lib_vc3/llqueue_dequeue.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
//
// LOW LEVEL LLQUEUE_DEQUEUE HEADERFILE
//

#ifndef _LLQUEUE_DEQUEUE_H
#define _LLQUEUE_DEQUEUE_H


#define LLQUEUE_DEQUEUE_DEFAULT_SIZE 32
#define EXPANDFAILED(s) DebugOutLn("Expand queue failed");
#define INDEXFAILED(s) DebugOutLn("Invalid Queue index");


/*
 * deque 
 */
template <class T> 
class dequeue {
	
public:
		dequeue();
		virtual ~dequeue();

		void Clear(void);		// logically clear the queue
		void Init(int max);		// set size of queue (hint)
								// Init destroys contents and resets all
		void PutFront( T *element);		// adds element on Front of queue
		T	*GetFront(void);			// zero if queue empty
		void PutBack( T *element);		// adds element on Back of queue
		T	*GetBack(void);				// zero if queue empty
		void Put( T* element ) { PutBack(element);}	// Put/Get Support
		T*	 Get(void) { return GetBack();}
		
		int  InQueue(void);			// returns number of elements queue
		bool IsEmpty(void) const;	// true if InQueue() returns zero
		
		// iteration
		void Set(int index);	// sets iteration index
		void Reset(void);		// resets iteration index (same as Set(0) )
		T	*Next(void);		// returns current element or 0 if no more left, Resets iterator
		T	*NextNoReset(void);	// returns current element or 0 if no more left, Does not reset iterator
		T* operator[](int i) const;	// returns element at index i
		T * SetAt(int i,T* newvalue); // direct access to element, replaces element 
		
		virtual	void Extend(void);	// called from Put*() if stacksize reaches max_elements
private:
		int	  CalcIndex(int i) const;
		void  ExtendQueue(void);
		T	  **m_array;
		int   m_iterator_index;			
		int   m_num_elements;
		int	  m_max_elements;
		int	  m_HeadIndex;
		int   m_TailIndex;
};



/*
 * Clears logically all entries
 * Caller must delete unused entries before calling Clear()
 */
template <class T> 
inline void dequeue<T>::Clear(void)
{
	m_num_elements=0;
	m_iterator_index=0;
	m_HeadIndex=0;
	m_TailIndex=0;
}


/*
 * resets iterator index
 */
template <class T> 
inline void dequeue<T>::Reset(void)
{
	m_iterator_index=0;
}                         

/*
 * Calc Index
 */
template<class T>
inline int dequeue<T>::CalcIndex(int i) const
{
    int Idx = m_HeadIndex + i;
    if(Idx >= m_max_elements )
		Idx -= m_max_elements;
    return Idx;
}

/*
 * set iterator index
 */
template <class T> 
inline void dequeue<T>::Set(int index)
{
	m_iterator_index=index<0?0:index;
}                         

/*
 * returns current item
 */
template <class T> 
inline T * dequeue<T>::Next(void)
{
	if( m_iterator_index < m_num_elements )
	{
		int idx = CalcIndex(m_iterator_index++);
		return m_array[idx];
	}
	Reset(); 
	return 0;
}                         

/*
 * returns current item, does not Reset Iterator
 * subsequent calls will return 0
 */
template <class T> 
inline T * dequeue<T>::NextNoReset(void)
{
	if( m_iterator_index < m_num_elements )
	{
		int idx = CalcIndex(m_iterator_index++);
		return m_array[idx];
	}
	return 0;
}                         

                
/*
 * returns number of items of the normal queue
 */
template <class T> 
inline int  dequeue<T>::InQueue(void)
{
	return m_num_elements;
}


/*
 * get a element from the bottom of the stack
 */
template <class T> 
inline T * dequeue<T>::GetBack(void)
{
	if( m_num_elements > 0 )
	{
		m_num_elements--;
		m_TailIndex--;

		if(m_TailIndex < 0)
			m_TailIndex += m_max_elements;

		return m_array[m_TailIndex];
	}
	return 0;
}		

/*
 * get a element from the bottom of the stack
 */
template <class T> 
inline void dequeue<T>::PutBack(T* element)
{
	if( m_num_elements < m_max_elements )
	{
		if( m_TailIndex == m_max_elements )
			m_TailIndex = 0;

		m_array[m_TailIndex] = element;
		m_TailIndex++;
		m_num_elements++;
	}
	else
	{
		Extend();
		PutBack(element);
	}
}	

/*
 * get a element from the front of the stack
 */
template <class T> 
inline T * dequeue<T>::GetFront(void)
{
	if( m_num_elements > 0 )
	{
		if( m_HeadIndex == m_max_elements )
			m_HeadIndex = 0;

		T* element = m_array[m_HeadIndex];

		m_HeadIndex++;
		m_num_elements--;

		return element;
	}
	return 0;
}		


/*
 * put a element on the stack
 */
template <class T> 
inline void dequeue<T>::PutFront(T* element )
{
	if( m_num_elements < m_max_elements )
	{
		m_num_elements++;
		m_HeadIndex--;
		if(m_HeadIndex < 0)
			m_HeadIndex += m_max_elements;
	
		m_array[m_HeadIndex] = element;	
	}
	else
	{
		Extend();
		PutFront(element);
	}
}	


                         
/*
 * Constructor
 */
template <class T> 
dequeue<T>::dequeue()
{
	m_array=0;
	Clear();
	m_max_elements=0;
}

template <class T> 
dequeue<T>::~dequeue()
{
	Clear();
	if( m_array ) llmem_free(m_array);
	m_array=0;
}

	
template <class T> 
void dequeue<T>::Init( int imax  )
{
	Clear();
	m_max_elements	= imax>1?imax:LLQUEUE_DEQUEUE_DEFAULT_SIZE;
	m_array = (T**)llmem_alloc(imax*sizeof(T*));
}

template <class T>
void dequeue<T>::Extend(void)
{
	ExtendQueue();
}

template <class T> 
void dequeue<T>::ExtendQueue(void)
{
	int	newsize = m_max_elements;
	newsize += (newsize>>1);
	if(newsize<LLQUEUE_DEQUEUE_DEFAULT_SIZE) newsize=LLQUEUE_DEQUEUE_DEFAULT_SIZE;
	
	T** tmp=(T**)llmem_alloc(newsize*sizeof(T*));
	if(!tmp) EXPANDFAILED(newsize*sizeof(T*));
	
	if( m_num_elements )
	{
		if(m_TailIndex > m_HeadIndex)
			memcpy(tmp, m_array + m_HeadIndex, m_num_elements*sizeof(T*));
		else
		{
			int Rest = m_max_elements - m_HeadIndex;
			memcpy(tmp, m_array + m_HeadIndex, Rest*sizeof(T*));
			memcpy(tmp + Rest, m_array, m_TailIndex*sizeof(T*));
		}
	}
	
	m_HeadIndex=0;
	m_TailIndex=m_num_elements;
	
	llmem_free(m_array);
	m_array=tmp;
	m_max_elements = newsize;
}

template<class T>
bool  dequeue<T>::IsEmpty() const
{
	return m_num_elements == 0 ? true : false;
}

template<class T>
T* dequeue<T>::operator[](int i) const
{
	if( i >= 0 && i < m_num_elements )
	{
		return m_array[CalcIndex(i)];
	}
	else
		return 0;
}

template<class T>
T * dequeue<T>::SetAt(int i,T* newvalue)
{
	T* oldvalue;
	if( i < m_num_elements )
	{
		int index = CalcIndex(i);
		oldvalue = m_array[index];
		m_array[index] = newvalue;
		return oldvalue;
	}
	INDEXFAILED(i);
	return 0;
}


#endif