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