alexp
/
l3lib
1
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
main
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'main'
${ noResults }
l3lib/l3lib_vc2003/llqueue_squeue.h

993 lines
16 KiB
C++
Raw Permalink Blame History

//: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 <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <search.h>
#include <memory.h>
#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<T>(squeue<T> &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<T> & m_Q;
bool m_local_shadow_active;
int m_local_iterator_index;
};
//:> +-----------------------------------+
//:>-------------------| Member Function Definitions |--------------------
//:> +-----------------------------------+
//::1
// +---------------+
// | Constructor |
// +---------------+
template<
typename T >
squeue<T>::squeue()
{
m_array1=0;
m_array2=0;
Clear();
m_max_elements=0;
}
//::2
// +--------------+
// | Destructor |
// +--------------+
template<
typename T >
squeue<T>::~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<T>::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<T>::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<T>::Get()
{
if( m_num_elements > 0 )
{
m_num_elements--;
return *--m_Qptr;
}
return 0;
}
//::4
// +----------+
// | Init() |
// +----------+
template<
typename T >
void squeue<T>::Init(
int imax)
{
Clear();
m_max_elements = imax>0?imax:LLQUEUE_DEFAULT_SIZE;
ExpandQueue();
}
//::10
// +-------------+
// | InQueue() |
// +-------------+
template<
typename T >
inline int squeue<T>::InQueue()
{
return m_num_elements;
}
//::11
// +-------------+
// | IsEmpty() |
// +-------------+
template<
typename T >
inline bool squeue<T>::IsEmpty() const
{
return m_num_elements == 0 ? true : false;
}
//::14
// +----------+
// | Next() |
// +----------+
template<
typename T >
inline T * squeue<T>::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<T>::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<T>::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<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 squeue<T>::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<T>::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<T>::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<T>::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<T>::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<T>::Reset()
{
m_iterator_index=0;
}
//::12
// +---------+
// | Set() |
// +---------+
template<
typename T >
inline void squeue<T>::Set(
int index)
{
m_iterator_index=index<0?0:index;
}
//::17
// +-----------+
// | SetAt() |
// +-----------+
template<
typename T >
T * squeue<T>::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<T>::SGet()
{
if( m_num_elements > 0 )
{
m_num_elements--;
return *--m_Qptr;
}
Swap();
return 0;
}
//::18
// +----------+
// | Sort() |
// +----------+
template<
typename T >
void squeue<T>::Sort( int(*compare)(const void *, const void *) )
{
qsort(m_array1,m_num_elements,sizeof(T*),compare);
}
//::7
// +----------+
// | SPut() |
// +----------+
template<
typename T >
inline void squeue<T>::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<T>::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
Reference in New Issue View Git Blame Copy Permalink