2 * Matt McCutchen's Big Integer Library
3 * http://mysite.verizon.net/mccutchen/bigint/
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.
13 #ifndef NUMBERLIKEARRAY
14 #define NUMBERLIKEARRAY
16 // An essential memory-management constant.
17 // I wish this were built into C++ just as it is in Java.
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.
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:
37 * NumberlikeArray< whatever >::getLength;
44 class NumberlikeArray {
47 typedef unsigned int Index; // Type for the index of a block in the array
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
54 static Blk x; // trash that [] can return for out-of-range requests
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';
64 struct BoundsCheckingBlk {
65 const NumberlikeArray *na;
66 BoundsCheckingBlk(NumberlikeArray *na) {
69 Blk & operator [](Index index) const {
70 if (index >= na->len) {
71 std::cout << "== Out-of-bounds access to block " << index << ". Affected NumberlikeArray: ==\n";
73 std::cout << "== End of dump. ==" << std::endl;
76 return na->blk2[index];
77 } // dangerous because it allows ``always writable'', but OK for now
78 /*const Blk & operator [](Index index) const {
80 std::cout << "OUT OF BOUNDS! Length " << (na->len) << ", accessed " << index << std::endl;
82 return na->blk[index];
89 BoundsCheckingBlk blk;
92 * Change made on 2005.01.06:
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.
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'.
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.
106 NumberlikeArray(Index c) : cap(c), len(0), blk(this) { // Creates a NumberlikeArray with a capacity
107 blk2 = (cap > 0) ? (new Blk[cap]) : NULL;
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
113 * Default constructor.
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.
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.
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.
130 NumberlikeArray() : cap(0), len(0), blk(this) {
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.
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; }
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;
156 * BELOW THIS POINT are template definitions; above are declarations.
158 * Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would
159 * be compiled once into NumberlikeArray.o and then linked.
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.
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.
172 Blk NumberlikeArray<Blk>::x = 0;
176 // This routine is called to ensure the array is at least a
177 // certain size before another value is written into it.
179 void NumberlikeArray<Blk>::allocate(Index c) {
180 // If the requested capacity is more than the current capacity...
182 // Delete the old number array
184 // Allocate the new array
190 // This routine is called to ensure the array is at least a
191 // certain size without losing its contents.
193 void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
194 // If the requested capacity is more than the current capacity...
197 // Allocate the new number array
200 // Copy number blocks
202 for (i = 0; i < len; i++)
204 // Delete the old array
211 NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len), blk(this) {
217 for (i = 0; i < len; i++)
221 // Assignment operator
223 void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
224 // Calls like a = a have no effect
229 // Expand array if necessary
231 // Copy number blocks
233 for (i = 0; i < len; i++)
237 // Constructor from an array of blocks
239 NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l), blk(this) {
244 for (i = 0; i < len; i++)
250 // This uses == to compare Blks for equality.
251 // Therefore, Blks must have an == operator with the desired semantics.
253 bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
254 // Different lengths imply different objects.
258 // Compare matching blocks one by one.
260 for (i = 0; i < len; i++)
261 if (blk[i] != x.blk[i])
263 // If no blocks differed, the objects are equal.