[bigint/bigint.git] / NumberlikeArray.hh

/*
* Matt McCutchen's Big Integer Library
* http://mysite.verizon.net/mccutchen/bigint/
*/

/*
* This mechanism prevents files from being included twice.
* Each file gets its own `id' (here `NUMBERLIKEARRAY').
* When `#include'd, this file checks whether its `id' has
* already been flagged.  If not, it flags the `id' and
* loads the declarations.
*/
#ifndef NUMBERLIKEARRAY
#define NUMBERLIKEARRAY

// An essential memory-management constant.
// I wish this were built into C++ just as it is in Java.
#ifndef NULL
#define NULL 0
#endif

/*
* A NumberlikeArray<Blk> object holds a dynamically
* allocated array of Blk.  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;
*/

/*debug*/
#include <iostream>

template <class Blk>
class NumberlikeArray {
	public:
	
	typedef unsigned int Index; // Type for the index of a block in the array
	static const unsigned int N; // The number of bits in a block, defined below.
	
	// 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 *blk2; // Dynamically allocated array of the blocks
	
	static Blk x; // trash that [] can return for out-of-range requests
	
	void dump() const {
		std::cout << "Dumping NumberlikeArray @ " << (void *)(this) << '\n';
		std::cout << "Length " << (len) << ", capacity " << (cap) << '\n';
		for (unsigned int i = 0; i < len; i++) {
			std::cout << "Block " << i << ":" << blk2[i] << '\n';
		}
	}
	
	struct BoundsCheckingBlk {
		const NumberlikeArray *na;
		BoundsCheckingBlk(NumberlikeArray *na) {
			this->na = na;
		}
		Blk & operator [](Index index) const {
			if (index >= na->len) {
				std::cout << "== Out-of-bounds access to block " << index << ".  Affected NumberlikeArray: ==\n";
				na->dump();
				std::cout << "== End of dump. ==" << std::endl;
				return x;
			} else
				return na->blk2[index];
		} // dangerous because it allows ``always writable'', but OK for now
		/*const Blk & operator [](Index index) const {
			if (index >= na->len)
				std::cout << "OUT OF BOUNDS!  Length " << (na->len) << ", accessed " << index << std::endl;
			else
				return na->blk[index];
		}*/
		/*operator Blk * () {
			return na->blk2;
		}*/
	};
	
	BoundsCheckingBlk blk;
	
	/*
	* Change made on 2005.01.06:
	*
	* If a zero-length NumberlikeArray is desired, no array is actually allocated.
	* Instead, `blk' is set to `NULL', and `cap' and `len' are zero as usual.
	*
	* `blk' is never dereferenced if the array has zero length.  Furthermore,
	* `delete NULL;' does nothing and causes no error. Therefore, we can use
	* `NULL' as if it were a zero-length array from `new'.
	*
	* This is a great convenience because the only code that need be changed
	* is the array allocation code.  All other code will still work file.
	*/
	
	// MANAGEMENT
	NumberlikeArray(Index c) : cap(c), len(0), blk(this) { // Creates a NumberlikeArray with a capacity
		blk2 = (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
	
	/*
	* Default constructor.
	*
	* If a class derived from NumberlikeArray knows at initializer time what size array
	* it wants, it can call the first constructor listed above in an initializer.
	*
	* Otherwise, this default constructor will be implicitly invoked, pointing `blk' to
	* `NULL', a fake zero-length block array.  The derived class can allocate the desired
	* array itself and overwrite `blk'; it need not `delete [] blk' first.
	*
	* This change fixes a memory leak reported by Milan Tomic on 2005.01.06.
	* Integer-type-to-BigUnsigned (and BigInteger) conversion constructors have always
	* allocated their own array of length 0 or 1 after seeing whether the input is zero.
	* But when the NumberlikeArray transition occurred, these constructors contained an
	* implicit initializer call to the old NumberlikeArray default constructor, which
	* created a real `new'-allocated zero-length array.  This array would then be lost,
	* causing a small but annoying memory leak.
	*/
	NumberlikeArray() : cap(0), len(0), blk(this) {
		blk2 = NULL;
	}
	NumberlikeArray(const NumberlikeArray<Blk> &x); // Copy constructor
	void operator=(const NumberlikeArray<Blk> &x); // Assignment operator
	NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks
	~NumberlikeArray() { // Destructor
		delete [] blk2; // Does nothing and causes no error if `blk' is null.
	}
	
	// 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.
	bool operator ==(const NumberlikeArray<Blk> &x) const;
	bool operator !=(const NumberlikeArray<Blk> &x) const;
	
};

/*
* 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.
*/

template <class Blk>
Blk NumberlikeArray<Blk>::x = 0;

template <class Blk>
const unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk);

// MANAGEMENT

// This routine is called to ensure the array is at least a
// certain size before another value is written into it.
template <class Blk>
void NumberlikeArray<Blk>::allocate(Index c) {
	// If the requested capacity is more than the current capacity...
	if (c > cap) {
		// Delete the old number array
		delete [] blk2;
		// Allocate the new array
		cap = c;
		blk2 = new Blk[cap];
	}
}

// This routine is called to ensure the array is at least a
// certain size without losing its contents.
template <class Blk>
void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
	// If the requested capacity is more than the current capacity...
	if (c > cap) {
		Blk *oldBlk = blk2;
		// Allocate the new number array
		cap = c;
		blk2 = new Blk[cap];
		// Copy number blocks
		Index i;
		for (i = 0; i < len; i++)
			blk[i] = oldBlk[i];
		// Delete the old array
		delete [] oldBlk;
	}
}

// Copy constructor
template <class Blk>
NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len), blk(this) {
	// Create array
	cap = len;
	blk2 = new Blk[cap];
	// Copy blocks
	Index i;
	for (i = 0; i < len; i++)
		blk[i] = x.blk[i];
}

// Assignment operator
template <class Blk>
void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
	// Calls like a = a have no effect
	if (this == &x)
		return;
	// Copy length
	len = x.len;
	// Expand array if necessary
	allocate(len);
	// Copy number blocks
	Index i;
	for (i = 0; i < len; i++)
		blk[i] = x.blk[i];
}

// Constructor from an array of blocks
template <class Blk>
NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l), blk(this) {
	// Create array
	blk2 = new Blk[cap];
	// Copy blocks
	Index i;
	for (i = 0; i < len; i++)
		blk[i] = b[i];
}


// EQUALITY TEST
// This uses == to compare Blks for equality.
// Therefore, Blks must have an == operator with the desired semantics.
template <class Blk>
bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
	// Different lengths imply different objects.
	if (len != x.len)
		return false;
	else {
		// Compare matching 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.
		return true;
	}
}

#endif
Commit	Line	Data
05780f4b MM	1	/*
	2	* Matt McCutchen's Big Integer Library
	3	* http://mysite.verizon.net/mccutchen/bigint/
	4	*/
	5
b3fe29df MM	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	*/
05780f4b MM	13	#ifndef NUMBERLIKEARRAY
	14	#define NUMBERLIKEARRAY
	15
b3fe29df MM	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
05780f4b	22	/*
4efbb076 MM	23	* A NumberlikeArray<Blk> object holds a dynamically
4efbb076 MM	24	* allocated array of Blk. It provides certain basic
05780f4b MM	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
e257a1b2 MM	40	/debug/
	41	#include <iostream>
	42
05780f4b MM	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
4efbb076	48	static const unsigned int N; // The number of bits in a block, defined below.
05780f4b MM	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)
e257a1b2 MM	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;
2f145f11	91
b3fe29df MM	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	*/
05780f4b MM	105
05780f4b MM	106	// MANAGEMENT
e257a1b2 MM	107	NumberlikeArray(Index c) : cap(c), len(0), blk(this) { // Creates a NumberlikeArray with a capacity
e257a1b2 MM	108	blk2 = (cap > 0) ? (new Blk[cap]) : NULL;
05780f4b MM	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
b3fe29df MM	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	*/
e257a1b2 MM	131	NumberlikeArray() : cap(0), len(0), blk(this) {
e257a1b2 MM	132	blk2 = NULL;
05780f4b MM	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
e257a1b2	138	delete [] blk2; // Does nothing and causes no error if `blk' is null.
05780f4b MM	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
e257a1b2 MM	172	template <class Blk>
	173	Blk NumberlikeArray<Blk>::x = 0;
	174
2f145f11	175	template <class Blk>
4efbb076	176	const unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk);
2f145f11	177
05780f4b MM	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
e257a1b2	187	delete [] blk2;
05780f4b MM	188	// Allocate the new array
05780f4b MM	189	cap = c;
e257a1b2	190	blk2 = new Blk[cap];
05780f4b MM	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) {
e257a1b2	200	Blk *oldBlk = blk2;
05780f4b MM	201	// Allocate the new number array
05780f4b MM	202	cap = c;
e257a1b2	203	blk2 = new Blk[cap];
05780f4b MM	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>
e257a1b2	215	NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len), blk(this) {
05780f4b MM	216	// Create array
05780f4b MM	217	cap = len;
e257a1b2	218	blk2 = new Blk[cap];
05780f4b MM	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>
e257a1b2	243	NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l), blk(this) {
05780f4b	244	// Create array
e257a1b2	245	blk2 = new Blk[cap];
05780f4b MM	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