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<Block> object holds a dynamically
  24 * allocated array of Blocks.  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
  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         * Change made on 2005.01.06:
  52         *
  53         * If a zero-length NumberlikeArray is desired, no array is actually allocated.
  54         * Instead, `blk' is set to `NULL', and `cap' and `len' are zero as usual.
  55         *
  56         * `blk' is never dereferenced if the array has zero length.  Furthermore,
  57         * `delete NULL;' does nothing and causes no error. Therefore, we can use
  58         * `NULL' as if it were a zero-length array from `new'.
  59         *
  60         * This is a great convenience because the only code that need be changed
  61         * is the array allocation code.  All other code will still work file.
  62         */
  63
  64         // MANAGEMENT
  65         NumberlikeArray(Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity
  66                 blk = (cap > 0) ? (new Blk[cap]) : NULL;
  67         }
  68         void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents
  69         void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents
  70
  71         /*
  72         * Default constructor.
  73         *
  74         * If a class derived from NumberlikeArray knows at initializer time what size array
  75         * it wants, it can call the first constructor listed above in an initializer.
  76         *
  77         * Otherwise, this default constructor will be implicitly invoked, pointing `blk' to
  78         * `NULL', a fake zero-length block array.  The derived class can allocate the desired
  79         * array itself and overwrite `blk'; it need not `delete [] blk' first.
  80         *
  81         * This change fixes a memory leak reported by Milan Tomic on 2005.01.06.
  82         * Integer-type-to-BigUnsigned (and BigInteger) conversion constructors have always
  83         * allocated their own array of length 0 or 1 after seeing whether the input is zero.
  84         * But when the NumberlikeArray transition occurred, these constructors contained an
  85         * implicit initializer call to the old NumberlikeArray default constructor, which
  86         * created a real `new'-allocated zero-length array.  This array would then be lost,
  87         * causing a small but annoying memory leak.
  88         */
  89         NumberlikeArray() : cap(0), len(0) {
  90                 blk = NULL;
  91         }
  92         NumberlikeArray(const NumberlikeArray<Blk> &x); // Copy constructor
  93         void operator=(const NumberlikeArray<Blk> &x); // Assignment operator
  94         NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks
  95         ~NumberlikeArray() { // Destructor
  96                 delete [] blk; // Does nothing and causes no error if `blk' is null.
  97         }
  98
  99         // PICKING APART
 100         // These accessors can be used to get the pieces of the value
 101         Index getCapacity() const { return cap; }
 102         Index getLength() const { return len; }
 103         Blk getBlock(Index i) const { return blk[i]; };
 104         bool isEmpty() const { return len == 0; }
 105
 106         // Equality comparison: checks if arrays have same length and matching values
 107         // Derived classes may wish to override these if differing arrays can
 108         // sometimes be considered equivalent.
 109         bool operator ==(const NumberlikeArray<Blk> &x) const;
 110         bool operator !=(const NumberlikeArray<Blk> &x) const;
 111
 112 };
 113
 114 /*
 115 * BELOW THIS POINT are template definitions; above are declarations.
 116 *
 117 * Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would
 118 * be compiled once into NumberlikeArray.o and then linked.
 119 *
 120 * However, because of the way templates are usually implemented,
 121 * template ``definitions'' are treated as declarations by the compiler.
 122 * When someone uses an instance of the template, definitions are generated,
 123 * and the linker is smart enough to toss duplicate definitions for the same
 124 * instance generated by different files.
 125 *
 126 * Thus, the template ``definitions'' for NumberlikeArray must appear in this header file
 127 * so other files including NumberlikeArray will be able to generate real definitions.
 128 */
 129
 130 // MANAGEMENT
 131
 132 // This routine is called to ensure the array is at least a
 133 // certain size before another value is written into it.
 134 template <class Blk>
 135 void NumberlikeArray<Blk>::allocate(Index c) {
 136         // If the requested capacity is more than the current capacity...
 137         if (c > cap) {
 138                 // Delete the old number array
 139                 delete [] blk;
 140                 // Allocate the new array
 141                 cap = c;
 142                 blk = new Blk[cap];
 143         }
 144 }
 145
 146 // This routine is called to ensure the array is at least a
 147 // certain size without losing its contents.
 148 template <class Blk>
 149 void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
 150         // If the requested capacity is more than the current capacity...
 151         if (c > cap) {
 152                 Blk *oldBlk = blk;
 153                 // Allocate the new number array
 154                 cap = c;
 155                 blk = new Blk[cap];
 156                 // Copy number blocks
 157                 Index i;
 158                 for (i = 0; i < len; i++)
 159                         blk[i] = oldBlk[i];
 160                 // Delete the old array
 161                 delete [] oldBlk;
 162         }
 163 }
 164
 165 // Copy constructor
 166 template <class Blk>
 167 NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len) {
 168         // Create array
 169         cap = len;
 170         blk = new Blk[cap];
 171         // Copy blocks
 172         Index i;
 173         for (i = 0; i < len; i++)
 174                 blk[i] = x.blk[i];
 175 }
 176
 177 // Assignment operator
 178 template <class Blk>
 179 void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
 180         // Calls like a = a have no effect
 181         if (this == &x)
 182                 return;
 183         // Copy length
 184         len = x.len;
 185         // Expand array if necessary
 186         allocate(len);
 187         // Copy number blocks
 188         Index i;
 189         for (i = 0; i < len; i++)
 190                 blk[i] = x.blk[i];
 191 }
 192
 193 // Constructor from an array of blocks
 194 template <class Blk>
 195 NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) {
 196         // Create array
 197         blk = new Blk[cap];
 198         // Copy blocks
 199         Index i;
 200         for (i = 0; i < len; i++)
 201                 blk[i] = b[i];
 202 }
 203
 204
 205 // EQUALITY TEST
 206 // This uses == to compare Blks for equality.
 207 // Therefore, Blks must have an == operator with the desired semantics.
 208 template <class Blk>
 209 bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
 210         // Different lengths imply different objects.
 211         if (len != x.len)
 212                 return false;
 213         else {
 214                 // Compare matching blocks one by one.
 215                 Index i;
 216                 for (i = 0; i < len; i++)
 217                         if (blk[i] != x.blk[i])
 218                                 return false;
 219                 // If no blocks differed, the objects are equal.
 220                 return true;
 221         }
 222 }
 223
 224 #endif