2 * Matt McCutchen's Big Integer Library
6 * This mechanism prevents files from being included twice.
7 * Each file gets its own `id' (here `NUMBERLIKEARRAY').
8 * When `#include'd, this file checks whether its `id' has
9 * already been flagged. If not, it flags the `id' and
10 * loads the declarations.
12 #ifndef NUMBERLIKEARRAY
13 #define NUMBERLIKEARRAY
15 // An essential memory-management constant.
16 // I wish this were built into C++ just as it is in Java.
22 * A NumberlikeArray<Blk> object holds a dynamically
23 * allocated array of Blk. It provides certain basic
24 * memory management features needed by both BigUnsigned
25 * and BigUnsignedInABase, which are both derived from it.
27 * NumberlikeArray provides no information hiding, so make
28 * sure you know what you are doing if you use it directly.
29 * Classes derived from it will probably wish to pass on
30 * some members of NumberlikeArray to their clients while
31 * keeping some safe for themselves. These classes should
32 * use protected inheritance and manually make some members
33 * public with declarations like this:
36 * NumberlikeArray< whatever >::getLength;
40 class NumberlikeArray {
43 typedef unsigned int Index; // Type for the index of a block in the array
44 static const unsigned int N; // The number of bits in a block, defined below.
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
52 * Change made on 2005.01.06:
54 * If a zero-length NumberlikeArray is desired, no array is actually allocated.
55 * Instead, `blk' is set to `NULL', and `cap' and `len' are zero as usual.
57 * `blk' is never dereferenced if the array has zero length. Furthermore,
58 * `delete NULL;' does nothing and causes no error. Therefore, we can use
59 * `NULL' as if it were a zero-length array from `new'.
61 * This is a great convenience because the only code that need be changed
62 * is the array allocation code. All other code will still work fine.
66 NumberlikeArray(Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity
67 blk = (cap > 0) ? (new Blk[cap]) : NULL;
69 void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents
70 void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents
73 * Default constructor.
75 * If a class derived from NumberlikeArray knows at initializer time what size array
76 * it wants, it can call the first constructor listed above in an initializer.
78 * Otherwise, this default constructor will be implicitly invoked, pointing `blk' to
79 * `NULL', a fake zero-length block array. The derived class can allocate the desired
80 * array itself and overwrite `blk'; it need not `delete [] blk' first.
82 * This change fixes a memory leak reported by Milan Tomic on 2005.01.06.
83 * Integer-type-to-BigUnsigned (and BigInteger) conversion constructors have always
84 * allocated their own array of length 0 or 1 after seeing whether the input is zero.
85 * But when the NumberlikeArray transition occurred, these constructors contained an
86 * implicit initializer call to the old NumberlikeArray default constructor, which
87 * created a real `new'-allocated zero-length array. This array would then be lost,
88 * causing a small but annoying memory leak.
90 NumberlikeArray() : cap(0), len(0) {
93 NumberlikeArray(const NumberlikeArray<Blk> &x); // Copy constructor
94 void operator=(const NumberlikeArray<Blk> &x); // Assignment operator
95 NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks
96 ~NumberlikeArray() { // Destructor
97 delete [] blk; // Does nothing and causes no error if `blk' is null.
101 // These accessors can be used to get the pieces of the value
102 Index getCapacity() const { return cap; }
103 Index getLength() const { return len; }
104 Blk getBlock(Index i) const { return blk[i]; };
105 bool isEmpty() const { return len == 0; }
107 // Equality comparison: checks if arrays have same length and matching values
108 // Derived classes may wish to override these if differing arrays can
109 // sometimes be considered equivalent.
110 bool operator ==(const NumberlikeArray<Blk> &x) const;
111 bool operator !=(const NumberlikeArray<Blk> &x) const { return !operator ==(x); }
116 * =================================
117 * BELOW THIS POINT are template definitions; above are declarations.
119 * Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would
120 * be compiled once into NumberlikeArray.o and then linked.
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.
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.
133 const unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk);
137 // This routine is called to ensure the array is at least a
138 // certain size before another value is written into it.
140 void NumberlikeArray<Blk>::allocate(Index c) {
141 // If the requested capacity is more than the current capacity...
143 // Delete the old number array
145 // Allocate the new array
151 // This routine is called to ensure the array is at least a
152 // certain size without losing its contents.
154 void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
155 // If the requested capacity is more than the current capacity...
158 // Allocate the new number array
161 // Copy number blocks
163 for (i = 0; i < len; i++)
165 // Delete the old array
172 NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len) {
178 for (i = 0; i < len; i++)
182 // Assignment operator
184 void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
185 // Calls like a = a have no effect
190 // Expand array if necessary
192 // Copy number blocks
194 for (i = 0; i < len; i++)
198 // Constructor from an array of blocks
200 NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) {
205 for (i = 0; i < len; i++)
211 // This uses == to compare Blks for equality.
212 // Therefore, Blks must have an == operator with the desired semantics.
214 bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
215 // Different lengths imply different objects.
219 // Compare matching blocks one by one.
221 for (i = 0; i < len; i++)
222 if (blk[i] != x.blk[i])
224 // If no blocks differed, the objects are equal.