/*
=================================================================================
This file is part of Cafu, the open-source game engine and graphics engine
for multiplayer, cross-platform, real-time 3D action.
Copyright (C) 2002-2012 Carsten Fuchs Software.
Cafu is free software: you can redistribute it and/or modify it under the terms
of the GNU General Public License as published by the Free Software Foundation,
either version 3 of the License, or (at your option) any later version.
Cafu is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with Cafu. If not, see .
For support and more information about Cafu, visit us at .
=================================================================================
*/
#ifndef CAFU_ARRAY_HPP_INCLUDED
#define CAFU_ARRAY_HPP_INCLUDED
#include
#include
// These classes are intentionally not defined in ArrayT,
// because we don't need them parametrised by T.
class cfArrayError {}; ///< General array error.
class cfOutOfRange : public cfArrayError {}; ///< Array index exceeds array boundaries.
class cfSizeOverflow : public cfArrayError {}; ///< Overflow of the arrays size.
template class ArrayT
{
private:
unsigned long MaxNrOfElements;
unsigned long NrOfElements;
T* Elements;
public:
ArrayT(); ///< Usual constructor
ArrayT(const ArrayT& OldArray); ///< Copy constructor
~ArrayT(); ///< Destructor
ArrayT& operator = (const ArrayT& OldArray); ///< Assignment operator
bool operator == (const ArrayT& Other) const; ///< Equality operator
bool operator != (const ArrayT& Other) const; ///< Inequality operator
unsigned long Size() const; ///< Get size of array
void Clear(); ///< Clear array (and free allocated memory)
void Overwrite(); ///< Clear array (but reuse memory)
T& operator [] (unsigned long Index);
const T& operator [] (unsigned long Index) const;
void PushBack(const T Element);
void PushBackEmpty(unsigned long Amount=1);
void PushBackEmptyExact(unsigned long Amount=1);
void DeleteBack(unsigned long Amount=1);
// "Convenience" methods.
void PushBack(const ArrayT& Other);
void InsertAt(unsigned long Index, const T Element); // TODO: Rename to InsertAtAndKeepOrder()
void RemoveAt(unsigned long Index);
void RemoveAtAndKeepOrder(unsigned long Index);
template
void QuickSort(Function IsLess);
// void QuickSort(unsigned long FirstIndex, unsigned long LastIndex, bool (*IsLess)(const T& E1, const T& E2));
int Find(const T& Element) const;
};
template inline ArrayT::ArrayT() // Usual constructor
{
MaxNrOfElements=0;
NrOfElements =0;
Elements =NULL;
}
template inline ArrayT::ArrayT(const ArrayT& OldArray) // Copy constructor
{
MaxNrOfElements=OldArray.MaxNrOfElements;
NrOfElements =OldArray.NrOfElements;
Elements =MaxNrOfElements>0 ? new T[MaxNrOfElements] : NULL;
for (unsigned long Nr=0; Nr inline ArrayT::~ArrayT() // Destructor
{
delete[] Elements;
}
template inline ArrayT& ArrayT::operator = (const ArrayT& OldArray) // Assignment op
{
// Handles self-assignment implicitly right!
T* NewElements=OldArray.MaxNrOfElements>0 ? new T[OldArray.MaxNrOfElements] : NULL;
for (unsigned long Nr=0; Nr inline bool ArrayT::operator == (const ArrayT& Other) const
{
if (NrOfElements != Other.NrOfElements)
return false;
for (unsigned long Nr=0; Nr inline bool ArrayT::operator != (const ArrayT& Other) const
{
return !(this->operator == (Other));
}
template inline unsigned long ArrayT::Size() const
{
return NrOfElements;
}
template inline void ArrayT::Clear()
{
delete[] Elements;
MaxNrOfElements=0;
NrOfElements =0;
Elements =NULL;
}
template inline void ArrayT::Overwrite()
{
// for (unsigned long Nr=0; Nr inline T& ArrayT::operator [] (unsigned long Index)
{
assert(Index inline const T& ArrayT::operator [] (unsigned long Index) const
{
assert(Index inline void ArrayT::PushBack(const T Element)
{
NrOfElements++;
if (NrOfElements>MaxNrOfElements)
{
if (!MaxNrOfElements) MaxNrOfElements=1;
while (MaxNrOfElements=0x80000000) throw cfSizeOverflow();
MaxNrOfElements*=2;
}
T* NewElements=new T[MaxNrOfElements];
for (unsigned long Nr=0; Nr inline void ArrayT::PushBackEmpty(unsigned long Amount)
{
NrOfElements+=Amount;
if (NrOfElements>MaxNrOfElements)
{
if (!MaxNrOfElements) MaxNrOfElements=1;
while (MaxNrOfElements=0x80000000) throw cfSizeOverflow();
MaxNrOfElements*=2;
}
T* NewElements=new T[MaxNrOfElements];
for (unsigned long Nr=0; Nr inline void ArrayT::PushBackEmptyExact(unsigned long Amount)
{
NrOfElements+=Amount;
if (NrOfElements>MaxNrOfElements)
{
MaxNrOfElements=NrOfElements;
T* NewElements=new T[MaxNrOfElements];
for (unsigned long Nr=0; Nr inline void ArrayT::DeleteBack(unsigned long Amount)
{
while (Amount>0 && NrOfElements>0)
{
Elements[NrOfElements-1]=T();
NrOfElements--;
Amount--;
}
}
template inline void ArrayT::PushBack(const ArrayT& Other)
{
for (unsigned long Nr=0; Nr inline void ArrayT::InsertAt(unsigned long Index, const T Element)
{
assert(Index<=NrOfElements); // This is intentionally <= and not <, because we immediately add an element below.
PushBackEmpty();
for (unsigned long Nr=NrOfElements-1; Nr>Index; Nr--)
Elements[Nr]=Elements[Nr-1];
Elements[Index]=Element;
}
template inline void ArrayT::RemoveAt(unsigned long Index)
{
assert(Index inline void ArrayT::RemoveAtAndKeepOrder(unsigned long Index)
{
assert(Index template inline void ArrayT::QuickSort(Function IsLess)
{
static ArrayT ToDoRanges;
if (NrOfElements<=1) return;
ToDoRanges.Overwrite();
ToDoRanges.PushBack(0);
ToDoRanges.PushBack(NrOfElements-1);
while (ToDoRanges.Size()>=2)
{
const unsigned long LastIndex =ToDoRanges[ToDoRanges.Size()-1]; ToDoRanges.DeleteBack();
const unsigned long FirstIndex=ToDoRanges[ToDoRanges.Size()-1]; ToDoRanges.DeleteBack();
if (FirstIndex0) { ToDoRanges.PushBack(FirstIndex); ToDoRanges.PushBack(i-1); }
}
}
}
/* // Simple recursive implementation from school.
template inline void ArrayT::QuickSort(unsigned long FirstIndex, unsigned long LastIndex, bool (*IsLess)(const T& E1, const T& E2))
{
if (FirstIndex0) QuickSort(FirstIndex, i-1, IsLess);
QuickSort(i+1, LastIndex, IsLess);
}
} */
template inline int ArrayT::Find(const T& Element) const
{
for (unsigned long Nr=0; Nr