NumberlikeArray.hh

   1 #ifndef NUMBERLIKEARRAY_H
   2 #define NUMBERLIKEARRAY_H
   3
   4 // Make sure we have NULL.
   5 #ifndef NULL
   6 #define NULL 0
   7 #endif
   8
   9 /* A NumberlikeArray<Blk> object holds a heap-allocated array of Blk with a
  10  * length and a capacity and provides basic memory management features.
  11  * BigUnsigned and BigUnsignedInABase both subclass it.
  12  *
  13  * NumberlikeArray provides no information hiding.  Subclasses should use
  14  * nonpublic inheritance and manually expose members as desired using
  15  * declarations like this:
  16  *
  17  * public:
  18  *     NumberlikeArray< the-type-argument >::getLength;
  19  */
  20 template <class Blk>
  21 class NumberlikeArray {
  22 public:
  23
  24         // Type for the index of a block in the array
  25         typedef unsigned int Index;
  26         // The number of bits in a block, defined below.
  27         static const unsigned int N;
  28
  29         // The current allocated capacity of this NumberlikeArray (in blocks)
  30         Index cap;
  31         // The actual length of the value stored in this NumberlikeArray (in blocks)
  32         Index len;
  33         // Heap-allocated array of the blocks (can be NULL if len == 0)
  34         Blk *blk;
  35
  36         // Constructs a ``zero'' NumberlikeArray with the given capacity.
  37         NumberlikeArray(Index c) : cap(c), len(0) {
  38                 blk = (cap > 0) ? (new Blk[cap]) : NULL;
  39         }
  40
  41         /* Constructs a zero NumberlikeArray without allocating a backing array.
  42          * A subclass that doesn't know the needed capacity at initialization
  43          * time can use this constructor and then overwrite blk without first
  44          * deleting it. */
  45         NumberlikeArray() : cap(0), len(0) {
  46                 blk = NULL;
  47         }
  48
  49         // Destructor.  Note that `delete NULL' is a no-op.
  50         ~NumberlikeArray() {
  51                 delete [] blk;
  52         }
  53
  54         /* Ensures that the array has at least the requested capacity; may
  55          * destroy the contents. */
  56         void allocate(Index c);
  57
  58         /* Ensures that the array has at least the requested capacity; does not
  59          * destroy the contents. */
  60         void allocateAndCopy(Index c);
  61
  62         // Copy constructor
  63         NumberlikeArray(const NumberlikeArray<Blk> &x);
  64
  65         // Assignment operator
  66         void operator=(const NumberlikeArray<Blk> &x);
  67
  68         // Constructor that copies from a given array of blocks
  69         NumberlikeArray(const Blk *b, Index blen);
  70
  71         // ACCESSORS
  72         Index getCapacity()     const { return cap;      }
  73         Index getLength()       const { return len;      }
  74         Blk   getBlock(Index i) const { return blk[i];   }
  75         bool  isEmpty()         const { return len == 0; }
  76
  77         /* Equality comparison: checks if both objects have the same length and
  78          * equal (==) array elements to that length.  Subclasses may wish to
  79          * override. */
  80         bool operator ==(const NumberlikeArray<Blk> &x) const;
  81
  82         bool operator !=(const NumberlikeArray<Blk> &x) const {
  83                 return !operator ==(x);
  84         }
  85 };
  86
  87 /* BEGIN TEMPLATE DEFINITIONS.  They are present here so that source files that
  88  * include this header file can generate the necessary real definitions. */
  89
  90 template <class Blk>
  91 const unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk);
  92
  93 template <class Blk>
  94 void NumberlikeArray<Blk>::allocate(Index c) {
  95         // If the requested capacity is more than the current capacity...
  96         if (c > cap) {
  97                 // Delete the old number array
  98                 delete [] blk;
  99                 // Allocate the new array
 100                 cap = c;
 101                 blk = new Blk[cap];
 102         }
 103 }
 104
 105 template <class Blk>
 106 void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
 107         // If the requested capacity is more than the current capacity...
 108         if (c > cap) {
 109                 Blk *oldBlk = blk;
 110                 // Allocate the new number array
 111                 cap = c;
 112                 blk = new Blk[cap];
 113                 // Copy number blocks
 114                 Index i;
 115                 for (i = 0; i < len; i++)
 116                         blk[i] = oldBlk[i];
 117                 // Delete the old array
 118                 delete [] oldBlk;
 119         }
 120 }
 121
 122 template <class Blk>
 123 NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x)
 124                 : len(x.len) {
 125         // Create array
 126         cap = len;
 127         blk = new Blk[cap];
 128         // Copy blocks
 129         Index i;
 130         for (i = 0; i < len; i++)
 131                 blk[i] = x.blk[i];
 132 }
 133
 134 template <class Blk>
 135 void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
 136         /* Calls like a = a have no effect; catch them before the aliasing
 137          * causes a problem */
 138         if (this == &x)
 139                 return;
 140         // Copy length
 141         len = x.len;
 142         // Expand array if necessary
 143         allocate(len);
 144         // Copy number blocks
 145         Index i;
 146         for (i = 0; i < len; i++)
 147                 blk[i] = x.blk[i];
 148 }
 149
 150 template <class Blk>
 151 NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index blen)
 152                 : cap(blen), len(blen) {
 153         // Create array
 154         blk = new Blk[cap];
 155         // Copy blocks
 156         Index i;
 157         for (i = 0; i < len; i++)
 158                 blk[i] = b[i];
 159 }
 160
 161 template <class Blk>
 162 bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
 163         if (len != x.len)
 164                 // Definitely unequal.
 165                 return false;
 166         else {
 167                 // Compare corresponding blocks one by one.
 168                 Index i;
 169                 for (i = 0; i < len; i++)
 170                         if (blk[i] != x.blk[i])
 171                                 return false;
 172                 // No blocks differed, so the objects are equal.
 173                 return true;
 174         }
 175 }
 176
 177 #endif