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