NumberlikeArray.hh

   1 /*
   2 * Matt McCutchen's Big Integer Library
   3 * http://mysite.verizon.net/mccutchen/bigint/
   4 */
   5
   6 #ifndef NUMBERLIKEARRAY
   7 #define NUMBERLIKEARRAY
   8
   9 /*
  10 * A NumberlikeArray<Block> object holds a dynamically
  11 * allocated array of Blocks.  It provides certain basic
  12 * memory management features needed by both BigUnsigned
  13 * and BigUnsignedInABase, which are both derived from it.
  14 *
  15 * NumberlikeArray provides no information hiding, so make
  16 * sure you know what you are doing if you use it directly.
  17 * Classes derived from it will probably wish to pass on
  18 * some members of NumberlikeArray to their clients while
  19 * keeping some safe for themselves.  These classes should
  20 * use protected inheritance and manually make some members
  21 * public with declarations like this:
  22 *
  23 * public:
  24 *     NumberlikeArray< whatever >::getLength;
  25 */
  26
  27 template <class Blk>
  28 class NumberlikeArray {
  29         public:
  30
  31         typedef unsigned int Index; // Type for the index of a block in the array
  32
  33         // FIELDS
  34         Index cap; // The current allocated capacity of this NumberlikeArray (in blocks)
  35         Index len; // The actual length of the value stored in this NumberlikeArray (in blocks)
  36         Blk *blk; // Dynamically allocated array of the blocks
  37
  38         // MANAGEMENT
  39         NumberlikeArray(int, Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity
  40                 blk = new Blk[cap];
  41         }
  42         void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents
  43         void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents
  44
  45         NumberlikeArray() : cap(0), len(0) { // Default constructor (empty array)
  46                 blk = new Blk[0];
  47         }
  48         NumberlikeArray(const NumberlikeArray<Blk> &x); // Copy constructor
  49         void operator=(const NumberlikeArray<Blk> &x); // Assignment operator
  50         NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks
  51         ~NumberlikeArray() { // Destructor
  52                 delete [] blk;
  53         }
  54
  55         // PICKING APART
  56         // These accessors can be used to get the pieces of the value
  57         Index getCapacity() const { return cap; }
  58         Index getLength() const { return len; }
  59         Blk getBlock(Index i) const { return blk[i]; };
  60         bool isEmpty() const { return len == 0; }
  61
  62         // Equality comparison: checks if arrays have same length and matching values
  63         // Derived classes may wish to override these if differing arrays can
  64         // sometimes be considered equivalent.
  65         bool operator ==(const NumberlikeArray<Blk> &x) const;
  66         bool operator !=(const NumberlikeArray<Blk> &x) const;
  67
  68 };
  69
  70 /*
  71 * BELOW THIS POINT are template definitions; above are declarations.
  72 *
  73 * Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would
  74 * be compiled once into NumberlikeArray.o and then linked.
  75 *
  76 * However, because of the way templates are usually implemented,
  77 * template ``definitions'' are treated as declarations by the compiler.
  78 * When someone uses an instance of the template, definitions are generated,
  79 * and the linker is smart enough to toss duplicate definitions for the same
  80 * instance generated by different files.
  81 *
  82 * Thus, the template ``definitions'' for NumberlikeArray must appear in this header file
  83 * so other files including NumberlikeArray will be able to generate real definitions.
  84 */
  85
  86 // MANAGEMENT
  87
  88 // This routine is called to ensure the array is at least a
  89 // certain size before another value is written into it.
  90 template <class Blk>
  91 void NumberlikeArray<Blk>::allocate(Index c) {
  92         // If the requested capacity is more than the current capacity...
  93         if (c > cap) {
  94                 // Delete the old number array
  95                 delete [] blk;
  96                 // Allocate the new array
  97                 cap = c;
  98                 blk = new Blk[cap];
  99         }
 100 }
 101
 102 // This routine is called to ensure the array is at least a
 103 // certain size without losing its contents.
 104 template <class Blk>
 105 void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
 106         // If the requested capacity is more than the current capacity...
 107         if (c > cap) {
 108                 Blk *oldBlk = blk;
 109                 // Allocate the new number array
 110                 cap = c;
 111                 blk = new Blk[cap];
 112                 // Copy number blocks
 113                 Index i;
 114                 for (i = 0; i < len; i++)
 115                         blk[i] = oldBlk[i];
 116                 // Delete the old array
 117                 delete [] oldBlk;
 118         }
 119 }
 120
 121 // Copy constructor
 122 template <class Blk>
 123 NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len) {
 124         // Create array
 125         cap = len;
 126         blk = new Blk[cap];
 127         // Copy blocks
 128         Index i;
 129         for (i = 0; i < len; i++)
 130                 blk[i] = x.blk[i];
 131 }
 132
 133 // Assignment operator
 134 template <class Blk>
 135 void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
 136         // Calls like a = a have no effect
 137         if (this == &x)
 138                 return;
 139         // Copy length
 140         len = x.len;
 141         // Expand array if necessary
 142         allocate(len);
 143         // Copy number blocks
 144         Index i;
 145         for (i = 0; i < len; i++)
 146                 blk[i] = x.blk[i];
 147 }
 148
 149 // Constructor from an array of blocks
 150 template <class Blk>
 151 NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) {
 152         // Create array
 153         blk = new Blk[cap];
 154         // Copy blocks
 155         Index i;
 156         for (i = 0; i < len; i++)
 157                 blk[i] = b[i];
 158 }
 159
 160
 161 // EQUALITY TEST
 162 // This uses == to compare Blks for equality.
 163 // Therefore, Blks must have an == operator with the desired semantics.
 164 template <class Blk>
 165 bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
 166         // Different lengths imply different objects.
 167         if (len != x.len)
 168                 return false;
 169         else {
 170                 // Compare matching blocks one by one.
 171                 Index i;
 172                 for (i = 0; i < len; i++)
 173                         if (blk[i] != x.blk[i])
 174                                 return false;
 175                 // If no blocks differed, the objects are equal.
 176                 return true;
 177         }
 178 }
 179
 180 #endif