include/AD/contain/idxable.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef indexable_h
  26 #define indexable_h
  27
  28 //////////////////////////////////////////////////////////////////////////
  29 //  Indexable<T> is a type of array-like objects that can grow or shrink.
  30 //////////////////////////////////////////////////////////////////////////
  31
  32 #include <AD/generic/generic.h>  // generic definitions
  33 #include <AD/generic/tables.h>   // tables of Fibonacci numbers
  34
  35 ////////////////////////////////////////////////////////////////////////
  36 // Class Indexable<T> is actually implemented as a bi-level table.
  37 // The first level is an index into a second level tables.
  38 // The second level tables are allocated only if needed.
  39 ////////////////////////////////////////////////////////////////////////
  40 template <class T>
  41    class Indexable {
  42    protected:
  43
  44       T **      table;             // a bi-level index.
  45       int       segments;          // number of segments currently allocated.
  46       int       limit;             // current limit
  47       const int Max_segments = 32;
  48
  49    public:
  50
  51       /////////////////////////////////////////////////////////////////
  52       // Constructors and destructor
  53       /////////////////////////////////////////////////////////////////
  54       Indexable();
  55       Indexable(const Indexable&);
  56       Indexable(int n, const T []);
  57      ~Indexable();
  58
  59       /////////////////////////////////////////////////////////////////
  60       // Assignment
  61       /////////////////////////////////////////////////////////////////
  62       Indexable& operator = (const Indexable&);
  63
  64       /////////////////////////////////////////////////////////////////
  65       // Selectors
  66       /////////////////////////////////////////////////////////////////
  67       inline int size()     const { return limit; }
  68       inline int length()   const { return limit; }
  69       inline int capacity() const { return limit; }
  70       inline int lo()       const { return 0; }
  71       inline int hi()       const { return limit - 1; }
  72       const T& operator [] (int i) const;
  73             T& operator [] (int i);
  74
  75       /////////////////////////////////////////////////////////////////
  76       // Mutators
  77       /////////////////////////////////////////////////////////////////
  78       void clear  ();
  79       void resize (int n);
  80
  81       /////////////////////////////////////////////////////////////////
  82       // Iterators(active):
  83       //    Since indexing with operator [] is not the fastest way
  84       //    to get to the data, we provide an iterator service to the
  85       //    client.
  86       /////////////////////////////////////////////////////////////////
  87       inline Ix       first()            const  { return Ix(1); }
  88       inline Ix       last()             const  { return Ix(limit + 1); }
  89       inline Ix       next(Ix i)         const  { return Ix((int)i+1); }
  90       inline Ix       prev(Ix i)         const  { return Ix((int)i-1); }
  91       inline const T& operator () (Ix i) const  { return (*this)[(int)i]; }
  92       inline       T& operator () (Ix i)        { return (*this)[(int)i]; }
  93    };
  94
  95 //////////////////////////////////////////////////////////////////////////////
  96 //  Implementation of the template methods
  97 //////////////////////////////////////////////////////////////////////////////
  98
  99 //////////////////////////////////////////////////////////////////////////////
 100 //  Constructor
 101 //////////////////////////////////////////////////////////////////////////////
 102 template <class T>
 103    Indexable<T>::Indexable()
 104    {  table = new T * [ Max_segments ]; segments = limit = 0; }
 105
 106 //////////////////////////////////////////////////////////////////////////////
 107 //  Copy constructor
 108 //////////////////////////////////////////////////////////////////////////////
 109 template <class T>
 110    Indexable<T>::Indexable(const Indexable<T>& I)
 111    {  table = new T * [ Max_segments ]; segments = limit = 0;
 112       *this = I;
 113    }
 114
 115 //////////////////////////////////////////////////////////////////////////////
 116 //  Constructor
 117 //////////////////////////////////////////////////////////////////////////////
 118 template <class T>
 119    Indexable<T>::Indexable(int n, const T t[])
 120    {  table = new T * [ Max_segments ]; segments = limit = 0;
 121       resize(n);
 122       register const T * a = t;
 123       for (int i = 0; i < segments; i++) {
 124          register T * b = tables[i];
 125          for (register int j = fibnacci[i+5] - 1; j >= 0; j--) *b++ = *a++;
 126       }
 127    }
 128
 129 //////////////////////////////////////////////////////////////////////////////
 130 //  Destructor
 131 //////////////////////////////////////////////////////////////////////////////
 132 template <class T>
 133    Indexable<T>::~Indexable() { clear(); delete [] table; }
 134
 135 //////////////////////////////////////////////////////////////////////////////
 136 //  Assignment
 137 //////////////////////////////////////////////////////////////////////////////
 138 template <class T>
 139    Indexable<T>& Indexable<T>::operator = (const Indexable<T>& t)
 140    {  if (this != &t) {
 141          resize(t.length());
 142          for (int i = 0; i < segments; i++) {
 143             register const T * a = t.tables[i];
 144             register T * b = tables[i];
 145             for (register int j = fibnacci[i+5] - 1; j >= 0; j--) *b++ = *a++;
 146          }
 147       }
 148       return *this;
 149    }
 150
 151 //////////////////////////////////////////////////////////////////////////////
 152 //  Clear
 153 //////////////////////////////////////////////////////////////////////////////
 154 template <class T>
 155    void Indexable<T>::clear()
 156    {  for (int i = segments - 1; i >= 0; i--)
 157          delete [] table[i];
 158       limit = segments = 0;
 159    }
 160
 161 //////////////////////////////////////////////////////////////////////////////
 162 //  Indexing
 163 //////////////////////////////////////////////////////////////////////////////
 164 template <class T>
 165    const T& Indexable<T>::operator [] (int i) const
 166    {  for (int j = 0; j < Max_segments; j++)
 167          if (fibonacci[j+6] > i) break;
 168       return tables[j][ i - fibonacci[j+5] ];
 169    }
 170
 171 //////////////////////////////////////////////////////////////////////////////
 172 //  Indexing
 173 //////////////////////////////////////////////////////////////////////////////
 174 template <class T>
 175    T& Indexable<T>::operator [] (int i)
 176    {  if (i >= limit) resize(i);
 177       for (int j = 0; j < Max_segments; j++)
 178          if (fibonacci[j+6] > i) break;
 179       return tables[j][ i - fibonacci[j+5] ];
 180    }
 181
 182 //////////////////////////////////////////////////////////////////////////////
 183 //  Resizing
 184 //////////////////////////////////////////////////////////////////////////////
 185 template <class T>
 186    void Indexable<T>::resize(int n)
 187    {  if (n < limit) return;
 188       while (fibonacci[segments+6] < n) {
 189          table[segments] = new T fibonacci[segments+5];
 190          segments++;
 191       }
 192       limit = fibonacci[segments+6];
 193    }
 194
 195 #endif