2 * Matt McCutchen's Big Integer Library
3 * http://mysite.verizon.net/mccutchen/bigint/
6 #ifndef NUMBERLIKEARRAY
7 #define NUMBERLIKEARRAY
10 * A NumberlikeArray<Block> object holds a dynamically
11 * allocated array of Blocks. It provides certain basic
12 * memory management features needed by both BigUnsigned
13 * and BigUnsignedInABase, which are both derived from it.
15 * NumberlikeArray provides no information hiding, so make
16 * sure you know what you are doing if you use it directly.
17 * Classes derived from it will probably wish to pass on
18 * some members of NumberlikeArray to their clients while
19 * keeping some safe for themselves. These classes should
20 * use protected inheritance and manually make some members
21 * public with declarations like this:
24 * NumberlikeArray< whatever >::getLength;
28 class NumberlikeArray {
31 typedef unsigned int Index; // Type for the index of a block in the array
34 Index cap; // The current allocated capacity of this NumberlikeArray (in blocks)
35 Index len; // The actual length of the value stored in this NumberlikeArray (in blocks)
36 Blk *blk; // Dynamically allocated array of the blocks
39 NumberlikeArray(int, Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity
42 void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents
43 void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents
45 NumberlikeArray() : cap(0), len(0) { // Default constructor (empty array)
48 NumberlikeArray(const NumberlikeArray<Blk> &x); // Copy constructor
49 void operator=(const NumberlikeArray<Blk> &x); // Assignment operator
50 NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks
51 ~NumberlikeArray() { // Destructor
56 // These accessors can be used to get the pieces of the value
57 Index getCapacity() const { return cap; }
58 Index getLength() const { return len; }
59 Blk getBlock(Index i) const { return blk[i]; };
60 bool isEmpty() const { return len == 0; }
62 // Equality comparison: checks if arrays have same length and matching values
63 // Derived classes may wish to override these if differing arrays can
64 // sometimes be considered equivalent.
65 bool operator ==(const NumberlikeArray<Blk> &x) const;
66 bool operator !=(const NumberlikeArray<Blk> &x) const;
71 * BELOW THIS POINT are template definitions; above are declarations.
73 * Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would
74 * be compiled once into NumberlikeArray.o and then linked.
76 * However, because of the way templates are usually implemented,
77 * template ``definitions'' are treated as declarations by the compiler.
78 * When someone uses an instance of the template, definitions are generated,
79 * and the linker is smart enough to toss duplicate definitions for the same
80 * instance generated by different files.
82 * Thus, the template ``definitions'' for NumberlikeArray must appear in this header file
83 * so other files including NumberlikeArray will be able to generate real definitions.
88 // This routine is called to ensure the array is at least a
89 // certain size before another value is written into it.
91 void NumberlikeArray<Blk>::allocate(Index c) {
92 // If the requested capacity is more than the current capacity...
94 // Delete the old number array
96 // Allocate the new array
102 // This routine is called to ensure the array is at least a
103 // certain size without losing its contents.
105 void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
106 // If the requested capacity is more than the current capacity...
109 // Allocate the new number array
112 // Copy number blocks
114 for (i = 0; i < len; i++)
116 // Delete the old array
123 NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len) {
129 for (i = 0; i < len; i++)
133 // Assignment operator
135 void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
136 // Calls like a = a have no effect
141 // Expand array if necessary
143 // Copy number blocks
145 for (i = 0; i < len; i++)
149 // Constructor from an array of blocks
151 NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) {
156 for (i = 0; i < len; i++)
162 // This uses == to compare Blks for equality.
163 // Therefore, Blks must have an == operator with the desired semantics.
165 bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
166 // Different lengths imply different objects.
170 // Compare matching blocks one by one.
172 for (i = 0; i < len; i++)
173 if (blk[i] != x.blk[i])
175 // If no blocks differed, the objects are equal.