NumberlikeArray.hh

   1 /*
   2 * Matt McCutchen's Big Integer Library
   3 */
   4
   5 /*
   6 * This mechanism prevents files from being included twice.
   7 * Each file gets its own `id' (here `NUMBERLIKEARRAY').
   8 * When `#include'd, this file checks whether its `id' has
   9 * already been flagged.  If not, it flags the `id' and
  10 * loads the declarations.
  11 */
  12 #ifndef NUMBERLIKEARRAY
  13 #define NUMBERLIKEARRAY
  14
  15 // An essential memory-management constant.
  16 // I wish this were built into C++ just as it is in Java.
  17 #ifndef NULL
  18 #define NULL 0
  19 #endif
  20
  21 /*
  22 * A NumberlikeArray<Blk> object holds a dynamically
  23 * allocated array of Blk.  It provides certain basic
  24 * memory management features needed by both BigUnsigned
  25 * and BigUnsignedInABase, which are both derived from it.
  26 *
  27 * NumberlikeArray provides no information hiding, so make
  28 * sure you know what you are doing if you use it directly.
  29 * Classes derived from it will probably wish to pass on
  30 * some members of NumberlikeArray to their clients while
  31 * keeping some safe for themselves.  These classes should
  32 * use protected inheritance and manually make some members
  33 * public with declarations like this:
  34 *
  35 * public:
  36 *     NumberlikeArray< whatever >::getLength;
  37 */
  38
  39 template <class Blk>
  40 class NumberlikeArray {
  41         public:
  42
  43         typedef unsigned int Index; // Type for the index of a block in the array
  44         static const unsigned int N; // The number of bits in a block, defined below.
  45
  46         // FIELDS
  47         Index cap; // The current allocated capacity of this NumberlikeArray (in blocks)
  48         Index len; // The actual length of the value stored in this NumberlikeArray (in blocks)
  49         Blk *blk; // Dynamically allocated array of the blocks
  50
  51         /*
  52         * Change made on 2005.01.06:
  53         *
  54         * If a zero-length NumberlikeArray is desired, no array is actually allocated.
  55         * Instead, `blk' is set to `NULL', and `cap' and `len' are zero as usual.
  56         *
  57         * `blk' is never dereferenced if the array has zero length.  Furthermore,
  58         * `delete NULL;' does nothing and causes no error. Therefore, we can use
  59         * `NULL' as if it were a zero-length array from `new'.
  60         *
  61         * This is a great convenience because the only code that need be changed
  62         * is the array allocation code.  All other code will still work fine.
  63         */
  64
  65         // MANAGEMENT
  66         NumberlikeArray(Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity
  67                 blk = (cap > 0) ? (new Blk[cap]) : NULL;
  68         }
  69         void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents
  70         void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents
  71
  72         /*
  73         * Default constructor.
  74         *
  75         * If a class derived from NumberlikeArray knows at initializer time what size array
  76         * it wants, it can call the first constructor listed above in an initializer.
  77         *
  78         * Otherwise, this default constructor will be implicitly invoked, pointing `blk' to
  79         * `NULL', a fake zero-length block array.  The derived class can allocate the desired
  80         * array itself and overwrite `blk'; it need not `delete [] blk' first.
  81         *
  82         * This change fixes a memory leak reported by Milan Tomic on 2005.01.06.
  83         * Integer-type-to-BigUnsigned (and BigInteger) conversion constructors have always
  84         * allocated their own array of length 0 or 1 after seeing whether the input is zero.
  85         * But when the NumberlikeArray transition occurred, these constructors contained an
  86         * implicit initializer call to the old NumberlikeArray default constructor, which
  87         * created a real `new'-allocated zero-length array.  This array would then be lost,
  88         * causing a small but annoying memory leak.
  89         */
  90         NumberlikeArray() : cap(0), len(0) {
  91                 blk = NULL;
  92         }
  93         NumberlikeArray(const NumberlikeArray<Blk> &x); // Copy constructor
  94         void operator=(const NumberlikeArray<Blk> &x); // Assignment operator
  95         NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks
  96         ~NumberlikeArray() { // Destructor
  97                 delete [] blk; // Does nothing and causes no error if `blk' is null.
  98         }
  99
 100         // PICKING APART
 101         // These accessors can be used to get the pieces of the value
 102         Index getCapacity() const { return cap; }
 103         Index getLength() const { return len; }
 104         Blk getBlock(Index i) const { return blk[i]; };
 105         bool isEmpty() const { return len == 0; }
 106
 107         // Equality comparison: checks if arrays have same length and matching values
 108         // Derived classes may wish to override these if differing arrays can
 109         // sometimes be considered equivalent.
 110         bool operator ==(const NumberlikeArray<Blk> &x) const;
 111         bool operator !=(const NumberlikeArray<Blk> &x) const { return !operator ==(x); }
 112
 113 };
 114
 115 /*
 116 * =================================
 117 * BELOW THIS POINT are template definitions; above are declarations.
 118 *
 119 * Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would
 120 * be compiled once into NumberlikeArray.o and then linked.
 121 *
 122 * However, because of the way templates are usually implemented,
 123 * template ``definitions'' are treated as declarations by the compiler.
 124 * When someone uses an instance of the template, definitions are generated,
 125 * and the linker is smart enough to toss duplicate definitions for the same
 126 * instance generated by different files.
 127 *
 128 * Thus, the template ``definitions'' for NumberlikeArray must appear in this header file
 129 * so other files including NumberlikeArray will be able to generate real definitions.
 130 */
 131
 132 template <class Blk>
 133 const unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk);
 134
 135 // MANAGEMENT
 136
 137 // This routine is called to ensure the array is at least a
 138 // certain size before another value is written into it.
 139 template <class Blk>
 140 void NumberlikeArray<Blk>::allocate(Index c) {
 141         // If the requested capacity is more than the current capacity...
 142         if (c > cap) {
 143                 // Delete the old number array
 144                 delete [] blk;
 145                 // Allocate the new array
 146                 cap = c;
 147                 blk = new Blk[cap];
 148         }
 149 }
 150
 151 // This routine is called to ensure the array is at least a
 152 // certain size without losing its contents.
 153 template <class Blk>
 154 void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
 155         // If the requested capacity is more than the current capacity...
 156         if (c > cap) {
 157                 Blk *oldBlk = blk;
 158                 // Allocate the new number array
 159                 cap = c;
 160                 blk = new Blk[cap];
 161                 // Copy number blocks
 162                 Index i;
 163                 for (i = 0; i < len; i++)
 164                         blk[i] = oldBlk[i];
 165                 // Delete the old array
 166                 delete [] oldBlk;
 167         }
 168 }
 169
 170 // Copy constructor
 171 template <class Blk>
 172 NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len) {
 173         // Create array
 174         cap = len;
 175         blk = new Blk[cap];
 176         // Copy blocks
 177         Index i;
 178         for (i = 0; i < len; i++)
 179                 blk[i] = x.blk[i];
 180 }
 181
 182 // Assignment operator
 183 template <class Blk>
 184 void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
 185         // Calls like a = a have no effect
 186         if (this == &x)
 187                 return;
 188         // Copy length
 189         len = x.len;
 190         // Expand array if necessary
 191         allocate(len);
 192         // Copy number blocks
 193         Index i;
 194         for (i = 0; i < len; i++)
 195                 blk[i] = x.blk[i];
 196 }
 197
 198 // Constructor from an array of blocks
 199 template <class Blk>
 200 NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) {
 201         // Create array
 202         blk = new Blk[cap];
 203         // Copy blocks
 204         Index i;
 205         for (i = 0; i < len; i++)
 206                 blk[i] = b[i];
 207 }
 208
 209
 210 // EQUALITY TEST
 211 // This uses == to compare Blks for equality.
 212 // Therefore, Blks must have an == operator with the desired semantics.
 213 template <class Blk>
 214 bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
 215         // Different lengths imply different objects.
 216         if (len != x.len)
 217                 return false;
 218         else {
 219                 // Compare matching blocks one by one.
 220                 Index i;
 221                 for (i = 0; i < len; i++)
 222                         if (blk[i] != x.blk[i])
 223                                 return false;
 224                 // If no blocks differed, the objects are equal.
 225                 return true;
 226         }
 227 }
 228
 229 #endif