BigUnsignedInABase.hh

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