BigUnsignedInABase.hh

   1 /*
   2  * Matt McCutchen's Big Integer Library
   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