qsieve

qsieve Mercurial Source Tree


Root/src/TinyVector.H

#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
Source at commit 32e9f1cc7aae created 11 years 9 months ago.
By Nathan Adams, adding variable

Archive Download this file

Branches

Tags

Page rendered in 1.12408s using 11 queries.