//: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 #include #include #include #include #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(queue &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 & m_Q; int m_local_iterator_index; }; //:> +-----------------------------------+ //:>-------------------| Member Function Definitions |-------------------- //:> +-----------------------------------+ //::1 // +---------------+ // | Constructor | // +---------------+ template< typename T > queue::queue() { m_array1=0; Clear(); m_max_elements=0; m_num_elements=0; } //::2 // +--------------+ // | Destructor | // +--------------+ template< typename T > queue::~queue() { Clear(); if( m_array1 ) llmem_free(m_array1); m_array1=0; } //::3 // +-----------+ // | Clear() | // +-----------+ template< typename T > inline void queue::Clear() { m_num_elements=0; m_iterator_index=0; m_Qptr=m_array1; } //::19 // +-----------------+ // | ExpandQueue() | // +-----------------+ template< typename T > void queue::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::Get() { if( m_num_elements > 0 ) { m_num_elements--; return *--m_Qptr; } return 0; } //::4 // +----------+ // | Init() | // +----------+ template< typename T > void queue::Init( int imax) { Clear(); m_max_elements = imax>0?imax:LLQUEUE_DEFAULT_SIZE; ExpandQueue(); } //::10 // +-------------+ // | InQueue() | // +-------------+ template< typename T > inline int queue::InQueue() { return m_num_elements; } //::11 // +-------------+ // | IsEmpty() | // +-------------+ template< typename T > inline bool queue::IsEmpty() const { return m_num_elements == 0 ? true : false; } //::14 // +----------+ // | Next() | // +----------+ template< typename T > inline T * queue::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::NextNoReset() { if( m_iterator_index < m_num_elements ) { return m_array1[m_iterator_index++]; } return 0; } //::16 // +-----------------+ // | operator []() | // +-----------------+ template< typename T > T * queue::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::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::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::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::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::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::Reset() { m_iterator_index=0; } //::12 // +---------+ // | Set() | // +---------+ template< typename T > inline void queue::Set( int index) { m_iterator_index=index<0?0:index; } //::17 // +-----------+ // | SetAt() | // +-----------+ template< typename T > T * queue::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::Sort( int(*compare)(const void *, const void *) ) { qsort(m_array1,m_num_elements,sizeof(T*),compare); } #endif // _LLQUEUE_H