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         typedef typename std::vector< T > chunk_type;
  14         typedef typename chunk_type::size_type size_type;
  15         typedef typename chunk_type::iterator iterator;
  16         typedef typename chunk_type::const_iterator const_iterator;
  17
  18         // Constructores
  19         number(): chunk(1, 0) {}
  20         number(atomic_type* buf, size_type len): chunk(buf, buf + len)
  21                 { fix_empty(); }
  22         number(atomic_type* buf)
  23                 { while (*buf) chunk.push_back(*(buf++)); fix_empty(); }
  24         number(atomic_type n): chunk(1, n) {}
  25         // TODO constructor a partir de string.
  26
  27         // Operadores
  28         number& operator++ () { if (!++chunk[0]) carry(1); return *this; }
  29         number& operator+= (const number& n)
  30         {
  31                 atomic_type c = 0;
  32                 size_type ini = 0;
  33                 size_type fin = std::min(chunk.size(), n.chunk.size());
  34                 for (size_type i = ini; i < fin; ++i)
  35                 {
  36                         chunk[i] += n.chunk[i] + c;
  37                         if (chunk[i] || (!n.chunk[i] && !c)) c = 0; // OK
  38                         else                                 c = 1; // Overflow
  39                 }
  40                 if (chunk.size() >= n.chunk.size()) // No hay más
  41                 {
  42                         if (c) carry(fin); // Propago carry
  43                         return *this;
  44                 }
  45                 // Hay más
  46                 ini = fin;
  47                 fin = n.chunk.size();
  48                 for (size_type i = ini; i < fin; ++i)
  49                 {
  50                         chunk.push_back(n.chunk[i] + c); // Agrego nuevo átomo
  51                         if (chunk[i] || !c) c = 0; // OK
  52                         else                c = 1; // Overflow
  53                 }
  54                 if (c) chunk.push_back(1); // Último carry
  55                 return *this;
  56         }
  57         atomic_type& operator[] (size_type i) { return chunk[i]; }
  58
  59         // Iteradores
  60         iterator begin() { return chunk.begin(); }
  61         iterator end() { return chunk.end(); }
  62         const_iterator begin() const { return chunk.begin(); }
  63         const_iterator end() const { return chunk.end(); }
  64
  65         private:
  66         // Atributos
  67         chunk_type chunk;
  68
  69         // Helpers
  70         void fix_empty() { if (!chunk.size()) chunk.push_back(0); }
  71         void carry(size_type i)
  72         {
  73                 if (chunk.size() > i)
  74                 {
  75                         ++chunk[i];
  76                         if (!chunk[i]) carry(i+1); // Overflow
  77                 }
  78                 else chunk.push_back(1);
  79         }
  80 };
  81
  82 template < typename T >
  83 number< T > operator+ (const number< T >& n1, const number< T >& n2)
  84 {
  85         number< T > tmp = n1;
  86         tmp += n2;
  87         return tmp;
  88 }
  89
  90 template < typename T >
  91 std::ostream& operator<< (std::ostream& os, const number< T >& n)
  92 {
  93         // FIXME sacar una salida bonita en ASCII =)
  94         std::copy(n.begin(), n.end(), std::ostream_iterator< T >(os, " "));
  95         return os;
  96 }
  97