NumberlikeArray.hh

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