X-Git-Url: https://mattmccutchen.net/bigint/bigint.git/blobdiff_plain/05780f4b578d6ae054be0b19b8498d32a4f16c60..HEAD:/NumberlikeArray.hh diff --git a/NumberlikeArray.hh b/NumberlikeArray.hh index 10b7262..53c8e5b 100644 --- a/NumberlikeArray.hh +++ b/NumberlikeArray.hh @@ -1,92 +1,95 @@ -/* -* Matt McCutchen's Big Integer Library -* http://mysite.verizon.net/mccutchen/bigint/ -*/ - -#ifndef NUMBERLIKEARRAY -#define NUMBERLIKEARRAY - -/* -* A NumberlikeArray object holds a dynamically -* allocated array of Blocks. It provides certain basic -* memory management features needed by both BigUnsigned -* and BigUnsignedInABase, which are both derived from it. -* -* NumberlikeArray provides no information hiding, so make -* sure you know what you are doing if you use it directly. -* Classes derived from it will probably wish to pass on -* some members of NumberlikeArray to their clients while -* keeping some safe for themselves. These classes should -* use protected inheritance and manually make some members -* public with declarations like this: -* -* public: -* NumberlikeArray< whatever >::getLength; -*/ +#ifndef NUMBERLIKEARRAY_H +#define NUMBERLIKEARRAY_H +// Make sure we have NULL. +#ifndef NULL +#define NULL 0 +#endif + +/* A NumberlikeArray object holds a heap-allocated array of Blk with a + * length and a capacity and provides basic memory management features. + * BigUnsigned and BigUnsignedInABase both subclass it. + * + * NumberlikeArray provides no information hiding. Subclasses should use + * nonpublic inheritance and manually expose members as desired using + * declarations like this: + * + * public: + * NumberlikeArray< the-type-argument >::getLength; + */ template class NumberlikeArray { - public: - - typedef unsigned int Index; // Type for the index of a block in the array - - // FIELDS - Index cap; // The current allocated capacity of this NumberlikeArray (in blocks) - Index len; // The actual length of the value stored in this NumberlikeArray (in blocks) - Blk *blk; // Dynamically allocated array of the blocks - - // MANAGEMENT - NumberlikeArray(int, Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity - blk = new Blk[cap]; +public: + + // Type for the index of a block in the array + typedef unsigned int Index; + // The number of bits in a block, defined below. + static const unsigned int N; + + // The current allocated capacity of this NumberlikeArray (in blocks) + Index cap; + // The actual length of the value stored in this NumberlikeArray (in blocks) + Index len; + // Heap-allocated array of the blocks (can be NULL if len == 0) + Blk *blk; + + // Constructs a ``zero'' NumberlikeArray with the given capacity. + NumberlikeArray(Index c) : cap(c), len(0) { + blk = (cap > 0) ? (new Blk[cap]) : NULL; } - void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents - void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents - - NumberlikeArray() : cap(0), len(0) { // Default constructor (empty array) - blk = new Blk[0]; + + /* Constructs a zero NumberlikeArray without allocating a backing array. + * A subclass that doesn't know the needed capacity at initialization + * time can use this constructor and then overwrite blk without first + * deleting it. */ + NumberlikeArray() : cap(0), len(0) { + blk = NULL; } - NumberlikeArray(const NumberlikeArray &x); // Copy constructor - void operator=(const NumberlikeArray &x); // Assignment operator - NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks - ~NumberlikeArray() { // Destructor + + // Destructor. Note that `delete NULL' is a no-op. + ~NumberlikeArray() { delete [] blk; } - - // PICKING APART - // These accessors can be used to get the pieces of the value - Index getCapacity() const { return cap; } - Index getLength() const { return len; } - Blk getBlock(Index i) const { return blk[i]; }; - bool isEmpty() const { return len == 0; } - - // Equality comparison: checks if arrays have same length and matching values - // Derived classes may wish to override these if differing arrays can - // sometimes be considered equivalent. + + /* Ensures that the array has at least the requested capacity; may + * destroy the contents. */ + void allocate(Index c); + + /* Ensures that the array has at least the requested capacity; does not + * destroy the contents. */ + void allocateAndCopy(Index c); + + // Copy constructor + NumberlikeArray(const NumberlikeArray &x); + + // Assignment operator + void operator=(const NumberlikeArray &x); + + // Constructor that copies from a given array of blocks + NumberlikeArray(const Blk *b, Index blen); + + // ACCESSORS + Index getCapacity() const { return cap; } + Index getLength() const { return len; } + Blk getBlock(Index i) const { return blk[i]; } + bool isEmpty() const { return len == 0; } + + /* Equality comparison: checks if both objects have the same length and + * equal (==) array elements to that length. Subclasses may wish to + * override. */ bool operator ==(const NumberlikeArray &x) const; - bool operator !=(const NumberlikeArray &x) const; - + + bool operator !=(const NumberlikeArray &x) const { + return !operator ==(x); + } }; -/* -* BELOW THIS POINT are template definitions; above are declarations. -* -* Definitions would ordinarily belong in a file NumberlikeArray.cc so that they would -* be compiled once into NumberlikeArray.o and then linked. -* -* However, because of the way templates are usually implemented, -* template ``definitions'' are treated as declarations by the compiler. -* When someone uses an instance of the template, definitions are generated, -* and the linker is smart enough to toss duplicate definitions for the same -* instance generated by different files. -* -* Thus, the template ``definitions'' for NumberlikeArray must appear in this header file -* so other files including NumberlikeArray will be able to generate real definitions. -*/ - -// MANAGEMENT - -// This routine is called to ensure the array is at least a -// certain size before another value is written into it. +/* BEGIN TEMPLATE DEFINITIONS. They are present here so that source files that + * include this header file can generate the necessary real definitions. */ + +template +const unsigned int NumberlikeArray::N = 8 * sizeof(Blk); + template void NumberlikeArray::allocate(Index c) { // If the requested capacity is more than the current capacity... @@ -99,8 +102,6 @@ void NumberlikeArray::allocate(Index c) { } } -// This routine is called to ensure the array is at least a -// certain size without losing its contents. template void NumberlikeArray::allocateAndCopy(Index c) { // If the requested capacity is more than the current capacity... @@ -118,9 +119,9 @@ void NumberlikeArray::allocateAndCopy(Index c) { } } -// Copy constructor template -NumberlikeArray::NumberlikeArray(const NumberlikeArray &x) : len(x.len) { +NumberlikeArray::NumberlikeArray(const NumberlikeArray &x) + : len(x.len) { // Create array cap = len; blk = new Blk[cap]; @@ -130,10 +131,10 @@ NumberlikeArray::NumberlikeArray(const NumberlikeArray &x) : len(x.len blk[i] = x.blk[i]; } -// Assignment operator template void NumberlikeArray::operator=(const NumberlikeArray &x) { - // Calls like a = a have no effect + /* Calls like a = a have no effect; catch them before the aliasing + * causes a problem */ if (this == &x) return; // Copy length @@ -146,9 +147,9 @@ void NumberlikeArray::operator=(const NumberlikeArray &x) { blk[i] = x.blk[i]; } -// Constructor from an array of blocks template -NumberlikeArray::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) { +NumberlikeArray::NumberlikeArray(const Blk *b, Index blen) + : cap(blen), len(blen) { // Create array blk = new Blk[cap]; // Copy blocks @@ -157,22 +158,18 @@ NumberlikeArray::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) { blk[i] = b[i]; } - -// EQUALITY TEST -// This uses == to compare Blks for equality. -// Therefore, Blks must have an == operator with the desired semantics. template bool NumberlikeArray::operator ==(const NumberlikeArray &x) const { - // Different lengths imply different objects. if (len != x.len) + // Definitely unequal. return false; else { - // Compare matching blocks one by one. + // Compare corresponding blocks one by one. Index i; for (i = 0; i < len; i++) if (blk[i] != x.blk[i]) return false; - // If no blocks differed, the objects are equal. + // No blocks differed, so the objects are equal. return true; } }