Commit | Line | Data |
---|---|---|
05780f4b MM |
1 | /* |
2 | * Matt McCutchen's Big Integer Library | |
05780f4b MM |
3 | */ |
4 | ||
5 | #ifndef BIGUNSIGNEDINABASE | |
6 | #define BIGUNSIGNEDINABASE | |
7 | ||
8 | #include "NumberlikeArray.hh" | |
9 | #include "BigUnsigned.hh" | |
10 | #include <string> | |
11 | ||
12 | /* | |
13 | * A BigUnsignedInABase object represents a nonnegative | |
14 | * integer of size limited only by available memory, | |
15 | * represented in a user-specified base that can fit in | |
16 | * an `unsigned short' (most can, and this saves memory). | |
17 | * | |
18 | * BigUnsignedInABase is intended as an intermediary class | |
19 | * with little functionality of its own. BigUnsignedInABase | |
20 | * objects can be constructed from, and converted to, | |
21 | * BigUnsigneds (requiring multiplication, mods, etc.) and | |
22 | * `std::string's (by switching digit values for appropriate | |
23 | * characters). | |
24 | * | |
25 | * BigUnsignedInABase is similar to BigUnsigned. Note the following: | |
26 | * | |
27 | * (1) They represent the number in exactly the same way, except | |
28 | * that BigUnsignedInABase uses ``digits'' (or Digit) where BigUnsigned uses | |
29 | * ``blocks'' (or Blk). | |
30 | * | |
31 | * (2) Both use the management features of NumberlikeArray. (In fact, | |
32 | * my desire to add a BigUnsignedInABase class without duplicating a | |
33 | * lot of code led me to introduce NumberlikeArray.) | |
34 | * | |
35 | * (3) The only arithmetic operation supported by BigUnsignedInABase | |
36 | * is an equality test. Use BigUnsigned for arithmetic. | |
37 | */ | |
38 | ||
39 | class BigUnsignedInABase : protected NumberlikeArray<unsigned short> { | |
40 | ||
41 | // TYPES | |
42 | public: | |
43 | typedef unsigned short Digit; // The digit type that BigUnsignedInABases are built from | |
44 | typedef Digit Base; | |
45 | ||
46 | // FIELDS | |
47 | protected: | |
48 | Base base; // The base of this BigUnsignedInABase | |
49 | ||
50 | // MANAGEMENT | |
51 | protected: | |
52 | // These members generally defer to those in NumberlikeArray, possibly with slight changes. | |
53 | // It might be nice if one could request that constructors be inherited in C++. | |
54 | ||
55 | BigUnsignedInABase(int, Index c) : NumberlikeArray<Digit>(0, c) {} // Creates a BigUnsignedInABase with a capacity | |
56 | ||
57 | void zapLeadingZeros() { // Decreases len to eliminate leading zeros | |
58 | while (len > 0 && blk[len - 1] == 0) | |
59 | len--; | |
60 | } | |
61 | ||
62 | //void allocate(Index c); // (NlA) Ensures the number array has at least the indicated capacity, maybe discarding contents | |
63 | //void allocateAndCopy(Index c); // (NlA) Ensures the number array has at least the indicated capacity, preserving its contents | |
64 | ||
65 | public: | |
66 | BigUnsignedInABase() : NumberlikeArray<Digit>(), base(2) {} // Default constructor (value is 0 in base 2) | |
67 | BigUnsignedInABase(const BigUnsignedInABase &x) : NumberlikeArray<Digit>(x), base(x.base) {} // Copy constructor | |
68 | ||
69 | void operator =(const BigUnsignedInABase &x) { // Assignment operator | |
70 | NumberlikeArray<Digit>::operator =(x); | |
71 | base = x.base; | |
72 | } | |
73 | ||
74 | BigUnsignedInABase(const Digit *d, Index l) : NumberlikeArray<Digit>(d, l) { // Constructor from an array of digits | |
75 | zapLeadingZeros(); | |
76 | } | |
77 | ||
78 | // LINKS TO BIGUNSIGNED | |
79 | BigUnsignedInABase(const BigUnsigned &x, Base base); | |
80 | operator BigUnsigned() const; | |
81 | ||
82 | /* LINKS TO STRINGS | |
83 | * | |
84 | * These use the symbols ``0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'' to represent | |
85 | * digits of 0 through 35. When parsing strings, lowercase is also accepted. | |
86 | * | |
87 | * All string representations are big-endian (big-place-value digits first). | |
88 | * (Computer scientists have adopted zero-based counting; why can't they | |
89 | * tolerate little-endian numbers? It makes a lot of sense!) | |
90 | * | |
91 | * No string representation has a ``base indicator'' like ``0x''. | |
92 | * | |
93 | * An exception is made for zero: it is converted to ``0'' and not the empty string. | |
94 | * | |
95 | * If you want different conventions, write your | |
96 | * own routines to go between BigUnsignedInABase and strings. It's not hard. | |
97 | */ | |
98 | operator std::string() const; | |
99 | BigUnsignedInABase(const std::string &s, Base base); | |
100 | ||
101 | // PICKING APART | |
102 | // These accessors can be used to get the pieces of the number | |
103 | public: | |
104 | Base getBase() const { return base; } | |
105 | NumberlikeArray<Digit>::getCapacity; // (NlA) | |
106 | NumberlikeArray<Digit>::getLength; // (NlA) | |
107 | // Note that getDigit returns 0 if the digit index is beyond the length of the number. | |
108 | // A routine that uses this accessor can safely assume a BigUnsigned has 0s infinitely to the left. | |
109 | Digit getDigit(Index i) const { return i >= len ? 0 : blk[i]; } | |
110 | // Note how we replace one level of abstraction with another. | |
111 | bool isZero() const { return NumberlikeArray<Digit>::isEmpty(); } // Often convenient for loops | |
112 | ||
113 | // EQUALITY TEST | |
114 | public: | |
115 | // Equality test | |
116 | bool operator ==(const BigUnsignedInABase &x) const { | |
117 | return base == x.base && NumberlikeArray<Digit>::operator ==(x); | |
118 | } | |
119 | bool operator !=(const BigUnsignedInABase &x) const { return !operator ==(x); } | |
120 | ||
121 | }; | |
122 | ||
123 | #endif |