1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
#ifndef NUMBERLIKEARRAY_H
#define NUMBERLIKEARRAY_H
// Make sure we have NULL.
#ifndef NULL
#define NULL 0
#endif
/* A NumberlikeArray<Blk> 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 Blk>
class NumberlikeArray {
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;
}
/* 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;
}
// Destructor. Note that `delete NULL' is a no-op.
~NumberlikeArray() {
delete [] blk;
}
/* 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<Blk> &x);
// Assignment operator
void operator=(const NumberlikeArray<Blk> &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<Blk> &x) const;
bool operator !=(const NumberlikeArray<Blk> &x) const {
return !operator ==(x);
}
};
/* BEGIN TEMPLATE DEFINITIONS. They are present here so that source files that
* include this header file can generate the necessary real definitions. */
template <class Blk>
const unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk);
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 [] blk;
// Allocate the new array
cap = c;
blk = new Blk[cap];
}
}
template <class Blk>
void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
// If the requested capacity is more than the current capacity...
if (c > cap) {
Blk *oldBlk = blk;
// Allocate the new number array
cap = c;
blk = new Blk[cap];
// Copy number blocks
Index i;
for (i = 0; i < len; i++)
blk[i] = oldBlk[i];
// Delete the old array
delete [] oldBlk;
}
}
template <class Blk>
NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x)
: len(x.len) {
// Create array
cap = len;
blk = new Blk[cap];
// Copy blocks
Index i;
for (i = 0; i < len; i++)
blk[i] = x.blk[i];
}
template <class Blk>
void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
/* Calls like a = a have no effect; catch them before the aliasing
* causes a problem */
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];
}
template <class Blk>
NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index blen)
: cap(blen), len(blen) {
// Create array
blk = new Blk[cap];
// Copy blocks
Index i;
for (i = 0; i < len; i++)
blk[i] = b[i];
}
template <class Blk>
bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
if (len != x.len)
// Definitely unequal.
return false;
else {
// Compare corresponding blocks one by one.
Index i;
for (i = 0; i < len; i++)
if (blk[i] != x.blk[i])
return false;
// No blocks differed, so the objects are equal.
return true;
}
}
#endif
|
