src/number.h

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