//:Header:82, "squeue", 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 squeue template class // //:----------------------------------------------------------------------------- #if !defined(_LLQUEUE_SQUEUE_H) #define _LLQUEUE_SQUEUE_H //:Include #include #include #include #include #include #include "llmem.h" //:Custom #ifndef LLQUEUE_DEFAULT_SIZE #define LLQUEUE_DEFAULT_SIZE (32) #define EXPANDFAILED(s) DebugOutLn("Expand squeue failed"); #define INDEXFAILED(s) DebugOutLn("Invalid Queue index"); #endif //:End Custom //:> +-------------------------------+ //:>---------------------| squeue Class Declaration |---------------------- //:> +-------------------------------+ //:Class template< typename T > class squeue { public: //::1 // +---------------+ // | Constructor | // +---------------+ squeue(); //::2 // +--------------+ // | Destructor | // +--------------+ ~squeue(); //::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); //:Description // // Insert Element an Stelle 0. // inline void SPutFront( 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); //::8 // +----------+ // | SGet() | // +----------+ //:Description // // Liefert Elementpointer vom Stack. // Liefert 0 wenn der Stack leer war, in diesem Fall wird implizit ein Swap() // durchgeführt. // inline T * SGet(); //::18 // +----------+ // | Sort() | // +----------+ //:Description // // QuickSort // void Sort( int (*compare)(const void *, const void *)); //::7 // +----------+ // | SPut() | // +----------+ //:Description // // Hängt neuen Elementpointer an den Shadowstack. // inline void SPut( T *element); //::9 // +----------+ // | Swap() | // +----------+ //:Description // // Tausch zwischen Shadow und Normal Queue // inline void Swap(); //:=6 // +----------+ // | m_Qptr | // +----------+ T * * m_Qptr; //:=7 // +-----------+ // | m_sQptr | // +-----------+ T * * m_sQptr; //:=8 // +------------+ // | m_array1 | // +------------+ T * * m_array1; //:=9 // +------------+ // | m_array2 | // +------------+ T * * m_array2; //:=10 // +-------------------+ // | m_shadow_active | // +-------------------+ bool m_shadow_active; //:=11 // +--------------------+ // | m_iterator_index | // +--------------------+ int m_iterator_index; //:=12 // +------------------+ // | m_num_elements | // +------------------+ int m_num_elements; //:=13 // +-------------------------+ // | m_num_shadow_elements | // +-------------------------+ int m_num_shadow_elements; //:=14 // +------------------+ // | m_max_elements | // +------------------+ int m_max_elements; //::19 // +-----------------+ // | ExpandQueue() | // +-----------------+ void ExpandQueue(); }; //:> +-------------------------------+ //:>---------------------| squeue Iterator Class |---------------------- //:> +-------------------------------+ //:Class template< typename T > class squeue_itr { public: //::1 // +---------------+ // | Constructor | // +---------------+ squeue_itr(squeue &queue_to_iterate ) : m_Q(queue_to_iterate) { m_local_iterator_index = m_Q.m_iterator_index; m_local_shadow_active = m_Q.m_shadow_active; m_local_iterator_index = 0; }; T * Next() { if(m_local_shadow_active){ if( m_local_iterator_index < m_Q.m_num_shadow_elements ) return m_Q.m_array2[m_local_iterator_index++]; } else { if( m_local_iterator_index < m_Q.m_num_elements ) return m_Q.m_array1[m_local_iterator_index++]; } m_local_iterator_index = 0; return 0; } T * NextNoReset() { if(m_local_shadow_active){ if( m_local_iterator_index < m_Q.m_num_shadow_elements ) return m_Q.m_array2[m_local_iterator_index++]; } else { 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: squeue & m_Q; bool m_local_shadow_active; int m_local_iterator_index; }; //:> +-----------------------------------+ //:>-------------------| Member Function Definitions |-------------------- //:> +-----------------------------------+ //::1 // +---------------+ // | Constructor | // +---------------+ template< typename T > squeue::squeue() { m_array1=0; m_array2=0; Clear(); m_max_elements=0; } //::2 // +--------------+ // | Destructor | // +--------------+ template< typename T > squeue::~squeue() { Clear(); if( m_array1 ) llmem_free(m_array1); if( m_array2 ) llmem_free(m_array2); m_array1=0; m_array2=0; } //::3 // +-----------+ // | Clear() | // +-----------+ template< typename T > inline void squeue::Clear() { m_num_elements=0; m_num_shadow_elements=0; m_iterator_index=0; m_shadow_active=false; m_Qptr=m_array1; m_sQptr=m_array2; } //::19 // +-----------------+ // | ExpandQueue() | // +-----------------+ template< typename T > void squeue::ExpandQueue() { int newsize = m_num_elements>m_num_shadow_elements?m_num_elements:m_num_shadow_elements; newsize = newsize>m_max_elements?newsize:m_max_elements; newsize += (newsize>>1); if(!newsize) newsize=LLQUEUE_DEFAULT_SIZE; m_array1 = (T**)llmem_realloc(m_array1,newsize*sizeof(T*)); m_array2 = (T**)llmem_realloc(m_array2,newsize*sizeof(T*)); if(!m_array1||!m_array2) EXPANDFAILED(newsize*sizeof(T*)); if(m_shadow_active) { m_sQptr=m_array1; m_Qptr=m_array2; } else { m_Qptr=m_array1; m_sQptr=m_array2; } m_Qptr += m_num_elements; m_sQptr += m_num_shadow_elements; m_max_elements = newsize; } //::6 // +---------+ // | Get() | // +---------+ template< typename T > inline T * squeue::Get() { if( m_num_elements > 0 ) { m_num_elements--; return *--m_Qptr; } return 0; } //::4 // +----------+ // | Init() | // +----------+ template< typename T > void squeue::Init( int imax) { Clear(); m_max_elements = imax>0?imax:LLQUEUE_DEFAULT_SIZE; ExpandQueue(); } //::10 // +-------------+ // | InQueue() | // +-------------+ template< typename T > inline int squeue::InQueue() { return m_num_elements; } //::11 // +-------------+ // | IsEmpty() | // +-------------+ template< typename T > inline bool squeue::IsEmpty() const { return m_num_elements == 0 ? true : false; } //::14 // +----------+ // | Next() | // +----------+ template< typename T > inline T * squeue::Next() { if( m_iterator_index < m_num_elements ) { if(m_shadow_active) return m_array2[m_iterator_index++]; else return m_array1[m_iterator_index++]; } Reset(); return 0; } //::15 // +-----------------+ // | NextNoReset() | // +-----------------+ template< typename T > inline T * squeue::NextNoReset() { if( m_iterator_index < m_num_elements ) { if(m_shadow_active) return m_array2[m_iterator_index++]; else return m_array1[m_iterator_index++]; } return 0; } //::16 // +-----------------+ // | operator []() | // +-----------------+ template< typename T > T * squeue::operator []( int i) const { if( i >= 0 && i < m_num_elements ) { if(m_shadow_active) return m_array2[i]; else return m_array1[i]; } return 0; } //::5 // +---------+ // | Put() | // +---------+ template< typename T > inline void squeue::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 squeue::InsertAt(int idx, T *element) { if( idx > m_num_elements ) INDEXFAILED(idx); if( (m_num_elements + 1) < m_max_elements ) { if(m_shadow_active) { memmove( &m_array2[idx+1], &m_array2[idx], (m_num_elements-idx)*sizeof(T*) ); m_array2[idx]=element; } else { 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* squeue::RemoveAt(int idx) { if( idx > m_num_elements ) INDEXFAILED(idx); T* rc; if( m_num_elements > 0 ) { if(m_shadow_active) { rc = m_array2[idx]; memmove( &m_array2[idx], &m_array2[idx+1], (m_num_elements-idx-1)*sizeof(T*) ); } else { 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; } return NULL; } //::5 // +---------------------+ // | Remove(T *element) | // +---------------------+ template< typename T > int squeue::Remove(T * element) { int rc = 0; for( int idx = 0 ; idx < m_num_elements; idx ++ ) { if(m_shadow_active) { if( m_array2[idx] == element ) { memmove( &m_array2[idx], &m_array2[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++; } } else { 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 squeue::PutFront( T *element) { if( m_num_elements < m_max_elements ) { if(m_shadow_active) { memmove( &m_array2[1], &m_array2[0], m_num_elements*sizeof(T*) ); m_array2[0]=element; } else { 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); } //::5 // +---------------+ // | SPutFront() | // +---------------+ template< typename T > inline void squeue::SPutFront( T *element) { if( m_num_elements < m_max_elements ) { if(!m_shadow_active) { memmove( &m_array2[1], &m_array2[0], m_num_elements*sizeof(T*) ); m_array2[0]=element; } else { memmove( &m_array1[1], &m_array1[0], m_num_elements*sizeof(T*) ); m_array1[0]=element; } m_num_elements++; m_Qptr++; return; } ExpandQueue(); SPutFront(element); } //::13 // +-----------+ // | Reset() | // +-----------+ template< typename T > inline void squeue::Reset() { m_iterator_index=0; } //::12 // +---------+ // | Set() | // +---------+ template< typename T > inline void squeue::Set( int index) { m_iterator_index=index<0?0:index; } //::17 // +-----------+ // | SetAt() | // +-----------+ template< typename T > T * squeue::SetAt( int i, T* newvalue) { T* oldvalue; if( i < m_num_elements ) { if(m_shadow_active) { oldvalue=m_array2[i]; m_array2[i]=newvalue; } else { oldvalue=m_array1[i]; m_array1[i]=newvalue; } return oldvalue; } INDEXFAILED(i); return 0; } //::8 // +----------+ // | SGet() | // +----------+ template< typename T > inline T * squeue::SGet() { if( m_num_elements > 0 ) { m_num_elements--; return *--m_Qptr; } Swap(); return 0; } //::18 // +----------+ // | Sort() | // +----------+ template< typename T > void squeue::Sort( int(*compare)(const void *, const void *) ) { qsort(m_array1,m_num_elements,sizeof(T*),compare); } //::7 // +----------+ // | SPut() | // +----------+ template< typename T > inline void squeue::SPut( T *element) { if( m_num_shadow_elements < m_max_elements ) { m_num_shadow_elements++; *m_sQptr++=element; return; } ExpandQueue(); m_num_shadow_elements++; *m_sQptr++=element; return; } //::9 // +----------+ // | Swap() | // +----------+ template< typename T > inline void squeue::Swap() { int x; T **xx; x=m_num_elements; m_num_elements=m_num_shadow_elements; m_num_shadow_elements=x; xx=m_Qptr; m_Qptr=m_sQptr; m_sQptr=xx; if(m_shadow_active) m_shadow_active=false; else m_shadow_active=true; Reset(); } #endif // _LLQUEUE_SQUEUE_H