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 * 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