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