TinyVector.H

Go to the documentation of this file.

#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

#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

---