#ifndef tinyvector_header
#define tinyvector_header
// provide a simple dynamic array.
// Main task: sparse representation of factor indices
// for the static factorbase in qsieve.
// (C) 1999 by Thorsten Reinecke
// major rewrite 2003-10 by Thorsten Reinecke
// last change: 2004-11-30 by Thorsten Reinecke
/*! @file
* @brief
* provides some templates for constructing C++-Arrays and a tiny implementation of them
*/
#include <limits>
#include <stdexcept>
//
// base types of C-Arrays, who are encapsulated in a "struct"
//
// the following prefixes are introduced, because identifiers of the form "_" + capital letter are reserved
// prefix TT_ stands for "template type"
// prefix VTBC_ stands for "virtual template base class"
template <typename TT_Datatype, typename TT_Sizetype = int> class VTBC_StructArray
{
public:
typedef TT_Datatype Datatype;
typedef TT_Sizetype Sizetype;
Datatype* v; // property: v is allowed to get replaced by another pointer
Sizetype Capacity; // number of allocated elements
Sizetype akt_size;
VTBC_StructArray(Datatype* const _v, const Sizetype myCapacity, const Sizetype _size=0)
: v(_v), Capacity(myCapacity), akt_size(_size) { }
private:
VTBC_StructArray(const VTBC_StructArray&);
inline const VTBC_StructArray& operator= (const VTBC_StructArray&) const { MARK; exit(9); return *this; }
public:
// max_size is the maximum count of elements in the array.
// (Allocating a larger array for "v" is allowed in this class!)
inline Sizetype max_size(void) const { return std::numeric_limits<Sizetype>::max(); }
};
template <typename TT_Datatype, typename TT_Sizetype = int> class VTBC_FixedStructArray
{
public:
typedef TT_Datatype Datatype;
typedef TT_Sizetype Sizetype;
Datatype* const v; // property: v is no more allowed to be changed
const Sizetype Capacity; // constant number of allocated elements
Sizetype akt_size;
VTBC_FixedStructArray(Datatype* const _v, const Sizetype myCapacity, const Sizetype _size=0)
: v(_v), Capacity(myCapacity), akt_size(_size) { }
// max_size is the maximum count of elements in the array.
// (Allocating a larger array for "v" is forbidden in this class!)
inline Sizetype max_size(void) const { return Capacity; }
};
//
// Enrich the base types with useful methods
//
//#define RANGE_CHECKS
// some useful methods
template <typename StructArraytype> class EnrichedArray
: protected StructArraytype
{
public:
typedef typename StructArraytype::Datatype Datatype;
typedef typename StructArraytype::Sizetype Sizetype;
EnrichedArray(Datatype* const _v, const Sizetype myCapacity, const Sizetype _size=0)
: StructArraytype(_v,myCapacity,_size) { }
#ifndef RANGE_CHECKS
inline void set_size(const Sizetype new_size) { StructArraytype::akt_size=new_size; }
#else
inline void set_size(const Sizetype new_size)
{
if (new_size>StructArraytype::Capacity || new_size<0)
{
cerr << "set_size: Range Overflow! " << new_size << " > " << StructArraytype::Capacity << endl;
throw std::length_error("set_size: new_size out of range!");
}
StructArraytype::akt_size=new_size;
}
#endif
inline Sizetype size(void) const { return StructArraytype::akt_size; }
inline bool empty(void) const { return (StructArraytype::akt_size==0); }
inline Sizetype capacity(void) const { return StructArraytype::Capacity; }
// redefine max_size because of protected inheritance
inline Sizetype max_size(void) const { return StructArraytype::max_size(); }
#ifndef RANGE_CHECKS
inline const Datatype& operator[] (const Sizetype pos) const { return StructArraytype::v[pos]; }
inline Datatype& operator[] (const Sizetype pos) { return StructArraytype::v[pos]; }
#else
inline const Datatype& operator[] (const Sizetype pos) const
{
if ( pos>capacity() || pos<0 || capacity()<1 )
{
cerr << "r/operator[]: Range Overflow! " << pos << " > " << StructArraytype::Capacity << endl;
throw std::out_of_range("r/operator[]: pos is out of range");
}
return StructArraytype::v[pos];
}
inline Datatype& operator[] (const Sizetype pos)
{
if ( pos>capacity() || pos<0 || capacity()<1 )
{
cerr << "rw/operator[]: Range Overflow! " << pos << " > " << StructArraytype::Capacity << endl;
throw std::out_of_range("rw/operator[]: pos is out of range");
}
return StructArraytype::v[pos];
}
#endif
};
// constructor-/destructor, who do the real work of allocating/deallocating elements
template <typename StructArraytype> class AutofiedStructArray
: public StructArraytype
{
private:
typedef typename StructArraytype::Datatype Datatype;
typedef typename StructArraytype::Sizetype Sizetype;
public:
explicit AutofiedStructArray(const Sizetype myCapacity)
: StructArraytype(new Datatype[myCapacity],myCapacity,0) { }
AutofiedStructArray(Datatype* const _v, const Sizetype myCapacity, const Sizetype _size=0)
: StructArraytype(_v,myCapacity,_size) { }
virtual ~AutofiedStructArray() { delete [] AutofiedStructArray::v; }
};
// macro for template composition analogous to composition of mathematical functions: g(f(X))=(gof)(X)
// "Composed_"-template (f) is composed by the "Composer_"-template (g);
// the composition of these templates results in the "Compositum_" (gof).
// example: B<A<T1,T2> > --TemplateComposition--> C<T1,T2> (accessible as C<T1,T2>::Type)
#define TemplateComposition(Composer_, Composed_, Compositum_) \
template <typename T1, typename T2 = int> struct Compositum_ \
{ \
typedef Composer_ < Composed_ <T1,T2> > Type; \
};
TemplateComposition(EnrichedArray,VTBC_StructArray,StructArray)
TemplateComposition(EnrichedArray,VTBC_FixedStructArray,FixedStructArray)
#define TemplateComposition2(Composer_, Composed1_, Composed2_, Compositum_) \
template <typename T1, typename T2 = int> struct Compositum_ \
{ \
typedef Composer_ < Composed1_ < Composed2_ <T1,T2> > > Type; \
};
// two-step composition: h(g(f(X)))=(hogof)(X)
TemplateComposition2(AutofiedStructArray,EnrichedArray,VTBC_StructArray,AutoStructArray)
TemplateComposition2(AutofiedStructArray,EnrichedArray,VTBC_FixedStructArray,AutoFixedStructArray)
template <typename Datatype, typename Sizetype=int, Sizetype DefaultResizeStep=32> class CTinyVector
: public AutoStructArray<Datatype,Sizetype>::Type
{
typedef typename AutoStructArray<Datatype,Sizetype>::Type Ancestor;
public:
inline explicit CTinyVector(const Sizetype MaxSize = DefaultResizeStep) // constructor
: Ancestor(new Datatype [MaxSize],MaxSize) { }
inline CTinyVector(const Datatype* Feld, const Sizetype Size)
: Ancestor(Size)
// constructor: initialize with a given array
{
for(Sizetype i=0; i<Size; i++) Ancestor::v[i]=Feld[i];
Ancestor::akt_size=Size;
}
inline CTinyVector(const CTinyVector<Datatype>& tv)
// constructor: initialize with another TinyVector
: Ancestor(tv.size())
{
Ancestor::akt_size=tv.akt_size;
for(Sizetype i=0; i<Ancestor::akt_size; i++) Ancestor::v[i]=tv[i];
}
inline void reset(void)
{
Ancestor::akt_size=0;
}
inline void resize(const Sizetype new_size)
{
if (new_size<Ancestor::akt_size)
{
cerr << "CTinyVector: Resizing not possible!" << endl;
throw std::runtime_error("CTinyVector: Resizing not possible!");
}
if (new_size==Ancestor::capacity()) return; // nothing to do...
#ifdef VERBOSE
cout << "CTinyVector: resizing from " << Ancestor::capacity() << " to " << new_size << endl;
#endif
Datatype* vnew = new Datatype [new_size];
for (Sizetype i=0; i<Ancestor::akt_size; i++) vnew[i]=Ancestor::v[i];
delete [] Ancestor::v; Ancestor::v=vnew; Ancestor::Capacity=new_size;
}
inline void optisize(void) // optimize size of dynamic array
{
// to avoid heap pollution do not resize when difference in size is marginal
if (Ancestor::capacity()>Ancestor::akt_size+DefaultResizeStep)
resize(Ancestor::akt_size);
}
inline void append(const Datatype value)
{
if (Ancestor::akt_size>=Ancestor::Capacity)
{
cerr << "TinyVector: Index " << Ancestor::akt_size
<< " is out Of Range!"
<< " Auto-Resizing by " << DefaultResizeStep << endl;
resize(Ancestor::akt_size+DefaultResizeStep);
}
if (!Ancestor::empty() && value<=Ancestor::v[Ancestor::akt_size-1])
{ cerr << "TinyVector: unsorted append!" << endl; }
Ancestor::v[Ancestor::akt_size++]=value;
}
inline void fast_append(const Datatype value)
{
Ancestor::v[Ancestor::akt_size++]=value;
}
inline Datatype last(void) const
{
if (!Ancestor::empty()) return Ancestor::v[Ancestor::akt_size-1];
else
{
cerr << "TinyVector: no last Element!" << endl;
throw std::runtime_error("TinyVector: last() called for empty vector");
}
}
inline void copy_from(const Datatype* Feld, const Sizetype Size)
{
if (Size>Ancestor::capacity())
{
#ifdef VERBOSE
cout << "CTinyVector:copy_from(), reallocate from " << Ancestor::capacity() << " to " << Size << endl;
#endif
delete [] Ancestor::v;
Ancestor::v = new Datatype [Size];
Ancestor::Capacity=Size;
}
Ancestor::akt_size=Size;
for(Sizetype i=0; i<Size; i++) Ancestor::v[i]=Feld[i];
}
inline void copy_from(const CTinyVector<Datatype> &tv)
{
#if 0
// this alternative ignores v.capacity()
copy_from(tv.v,tv.size());
#else
// this alternative allocates v.capacity() entries, if reallocation is necessary
if (tv.size()>Ancestor::capacity())
{
#ifdef VERBOSE
cout << "CTinyVector:copy_from(), reallocate from " << Ancestor::capacity() << " to " << tv.capacity()
<< " using " << tv.size() << endl;
#endif
delete [] Ancestor::v;
Ancestor::v = new Datatype [tv.capacity()];
Ancestor::Capacity=tv.capacity();
}
Ancestor::akt_size=tv.size();
for(Sizetype i=0; i<tv.size(); i++) Ancestor::v[i]=tv[i];
#endif
}
inline void optisized_copy_from(const Datatype* Feld, const Sizetype Size)
{
if (Size>Ancestor::capacity() || Size+DefaultResizeStep<Ancestor::capacity())
{
cout << "CTinyVector:optisized_copy_from(), reallocate from " << Ancestor::capacity() << " to " << Size << endl;
delete [] Ancestor::v; Ancestor::v = new Datatype [Size];
}
Ancestor::akt_size=Ancestor::Capacity=Size;
for(Sizetype i=0; i<Size; i++) Ancestor::v[i]=Feld[i];
}
inline void optisized_copy_from(const CTinyVector<Datatype> &tv)
{
if (this==&tv) { optisize(); return; } // optimize copy from myself!
optisized_copy_from(tv.v,tv.size());
}
inline const CTinyVector<Datatype>& operator= (const CTinyVector<Datatype> &tv)
{
copy_from(tv.v,tv.size()); return *this;
}
};
#endif