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