src/number.h

   1 #include <vector>
   2 #include <algorithm>
   3 #include <iterator>
   4
   5 //XXX Pensado para andar con unsigned's (si anda con otra cosa es casualidad =)
   6
   7 template < typename T >
   8 struct number
   9 {
  10
  11         // Tipos
  12         typedef T atomic_type;
  13         enum sign_type { positive, negative };
  14         typedef typename std::vector< T > chunk_type;
  15         typedef typename chunk_type::size_type size_type;
  16         typedef typename chunk_type::iterator iterator;
  17         typedef typename chunk_type::const_iterator const_iterator;
  18
  19         // Constructores (después de construído, el chunk siempre tiene al menos
  20         // un elemento).
  21         // Constructor default (1 'átomo con valor 0)
  22         number(): chunk(1, 0) {}
  23         // Constructor a partir de buffer (de 'átomos') y tamaño
  24         // Copia cada elemento del buffer como un 'átomo' del chunk
  25         // (el átomo menos significativo es el chunk[0] == buf[0])
  26         number(atomic_type* buf, size_type len, sign_type sign = positive):
  27                 chunk(buf, buf + len), sign(sign)
  28                 { fix_empty(); }
  29         // Constructor a partir de un buffer (de 'átomos') terminado en 0
  30         // FIXME (en realidad está 'roto' este contructor porque no puedo
  31         // inicializar números con un átomo == 0 en el medio)
  32         number(atomic_type* buf, sign_type sign = positive): sign(sign)
  33                 { while (*buf) chunk.push_back(*(buf++)); fix_empty(); }
  34         // Constructor a partir de un 'átomo' (lo asigna como único elemento del
  35         // chunk)
  36         number(atomic_type n, sign_type sign = positive):
  37                 chunk(1, n), sign(sign) {} // copia una vez n en el vector
  38         // TODO constructor a partir de string.
  39
  40         // Operadores
  41         number& operator++ () { carry(0); return *this; }
  42         number& operator+= (const number& n);
  43         // Devuelve referencia a 'átomo' i del chunk (no debería ser necesario
  44         // si la multiplicación es un método de este objeto).
  45         atomic_type& operator[] (size_type i) { return chunk[i]; }
  46
  47         // Iteradores (no deberían ser necesarios)
  48         iterator begin() { return chunk.begin(); }
  49         iterator end() { return chunk.end(); }
  50         const_iterator begin() const { return chunk.begin(); }
  51         const_iterator end() const { return chunk.end(); }
  52
  53         private:
  54         // Atributos
  55         chunk_type chunk;
  56         sign_type sign;
  57
  58         // Helpers
  59         // Pone un chunk en 0 para que sea un invariante de representación que
  60         // el chunk no sea vacío (siempre tenga la menos un elemento).
  61         void fix_empty() { if (!chunk.size()) chunk.push_back(0); }
  62         // Propaga carry a partir del 'átomo' i (suma 1 al 'átomo' i propagando
  63         // carry)
  64         void carry(size_type i)
  65         {
  66                 if (chunk.size() > i)
  67                 {
  68                         ++chunk[i];
  69                         if (!chunk[i]) carry(i+1); // Overflow
  70                 }
  71                 else chunk.push_back(1);
  72         }
  73 };
  74
  75 template < typename T >
  76 number< T >& number< T >::operator+= (const number< T >& n)
  77 {
  78         atomic_type c = 0;
  79         size_type ini = 0;
  80         size_type fin = std::min(chunk.size(), n.chunk.size());
  81         // "intersección" entre ambos chunks
  82         // +-----+-----+------+------+
  83         // |     |     |      |      | <--- mio
  84         // +-----+-----+------+------+
  85         // +-----+-----+------+
  86         // |     |     |      |        <--- chunk de n
  87         // +-----+-----+------+
  88         //
  89         // |------------------|
  90         // Esto se procesa en este for
  91         for (size_type i = ini; i < fin; ++i)
  92         {
  93                 chunk[i] += n.chunk[i] + c;
  94                 if (chunk[i] || (!n.chunk[i] && !c)) c = 0; // OK
  95                 else                                 c = 1; // Overflow
  96         }
  97         // si mi chunk es más grande que el del otro, sólo me queda
  98         // propagar el carry
  99         if (chunk.size() >= n.chunk.size())
 100         {
 101                 if (c) carry(fin); // Propago carry
 102                 return *this;
 103         }
 104         // Hay más
 105         // +-----+-----+------+
 106         // |     |     |      |         <--- mío
 107         // +-----+-----+------+
 108         // +-----+-----+------+------+
 109         // |     |     |      |      |  <--- chunk de n
 110         // +-----+-----+------+------+
 111         //
 112         //                    |------|
 113         //            Esto se procesa en este for
 114         // (suma los chunks de n propagando algún carry si lo había)
 115         ini = fin;
 116         fin = n.chunk.size();
 117         for (size_type i = ini; i < fin; ++i)
 118         {
 119                 chunk.push_back(n.chunk[i] + c); // Agrego nuevo átomo
 120                 if (chunk[i] || !c) c = 0; // OK
 121                 else                c = 1; // Overflow
 122         }
 123         // Si me queda algún carry colgado, hay que agregar un "átomo"
 124         // más al chunk.
 125         if (c) chunk.push_back(1); // Último carry
 126         return *this;
 127 }
 128
 129 template < typename T >
 130 number< T > operator+ (const number< T >& n1, const number< T >& n2)
 131 {
 132         number< T > tmp = n1;
 133         tmp += n2;
 134         return tmp;
 135 }
 136
 137 template < typename T >
 138 std::ostream& operator<< (std::ostream& os, const number< T >& n)
 139 {
 140         // FIXME sacar una salida bonita en ASCII =)
 141         std::copy(n.begin(), n.end(), std::ostream_iterator< T >(os, " "));
 142         return os;
 143 }
 144