Reverse iterators para imprimir en orden

[z.facultad/75.29/dale.git] / src / number.h

diff --git a/src/number.h b/src/number.h
index 82c606787352c7d8c54e0d6eee97b45f45ddb5c0..22f2d3b44542e05d66babfab32efb4cfd471425a 100644 (file)
--- a/src/number.h
+++ b/src/number.h
@@ -1,3 +1,9 @@
+#ifdef _WIN32\r
+//min y max entran en conflicto con la windows.h, son rebautizadas en Windows\r
+#define min _cpp_min\r
+#define max _cpp_max\r
+#endif\r
+\r

 #include <vector>
 #include <algorithm>
 #include <iterator>
 #include <vector>
 #include <algorithm>
 #include <iterator>


@@ -10,64 +16,64 @@ struct number
 
        // Tipos
        typedef T atomic_type;
 
        // Tipos
        typedef T atomic_type;

+       enum sign_type { positive, negative };

        typedef typename std::vector< T > chunk_type;
        typedef typename chunk_type::size_type size_type;
        typedef typename std::vector< T > chunk_type;
        typedef typename chunk_type::size_type size_type;

-       typedef typename chunk_type::iterator iterator;
-       typedef typename chunk_type::const_iterator const_iterator;
+       typedef typename chunk_type::iterator iterator;\r
+       typedef typename chunk_type::const_iterator const_iterator;\r
+       typedef typename chunk_type::reverse_iterator reverse_iterator;\r
+       typedef typename chunk_type::const_reverse_iterator const_reverse_iterator;

 
 

-       // Constructores
+       // Constructores (después de construído, el chunk siempre tiene al menos
+       // un elemento).
+       // Constructor default (1 'átomo con valor 0)

        number(): chunk(1, 0) {}
        number(): chunk(1, 0) {}

-       number(atomic_type* buf, size_type len): chunk(buf, buf + len)
+       // Constructor a partir de buffer (de 'átomos') y tamaño
+       // Copia cada elemento del buffer como un 'átomo' del chunk
+       // (el átomo menos significativo es el chunk[0] == buf[0])
+       number(atomic_type* buf, size_type len, sign_type sign = positive):
+               chunk(buf, buf + len), sign(sign)

                { fix_empty(); }
                { fix_empty(); }

-       number(atomic_type* buf)
+       // Constructor a partir de un buffer (de 'átomos') terminado en 0
+       // FIXME (en realidad está 'roto' este contructor porque no puedo
+       // inicializar números con un átomo == 0 en el medio)
+       number(atomic_type* buf, sign_type sign = positive): sign(sign)

                { while (*buf) chunk.push_back(*(buf++)); fix_empty(); }
                { while (*buf) chunk.push_back(*(buf++)); fix_empty(); }

-       number(atomic_type n): chunk(1, n) {}
+       // Constructor a partir de un 'átomo' (lo asigna como único elemento del
+       // chunk)
+       number(atomic_type n, sign_type sign = positive):
+               chunk(1, n), sign(sign) {} // copia una vez n en el vector

        // TODO constructor a partir de string.
 
        // Operadores
        // TODO constructor a partir de string.
 
        // Operadores

-       number& operator++ () { if (!++chunk[0]) carry(1); return *this; }
-       number& operator+= (const number& n)
-       {
-               atomic_type c = 0;
-               size_type ini = 0;
-               size_type fin = std::min(chunk.size(), n.chunk.size());
-               for (size_type i = ini; i < fin; ++i)
-               {
-                       chunk[i] += n.chunk[i] + c;
-                       if (chunk[i] || (!n.chunk[i] && !c)) c = 0; // OK
-                       else                                 c = 1; // Overflow
-               }
-               if (chunk.size() >= n.chunk.size()) // No hay más
-               {
-                       if (c) carry(fin); // Propago carry
-                       return *this;
-               }
-               // Hay más
-               ini = fin;
-               fin = n.chunk.size();
-               for (size_type i = ini; i < fin; ++i)
-               {
-                       chunk.push_back(n.chunk[i] + c); // Agrego nuevo átomo
-                       if (chunk[i] || !c) c = 0; // OK
-                       else                c = 1; // Overflow
-               }
-               if (c) chunk.push_back(1); // Último carry
-               return *this;
-       }
+       number& operator++ () { carry(0); return *this; }
+       number& operator+= (const number& n);
+       // Devuelve referencia a 'átomo' i del chunk (no debería ser necesario
+       // si la multiplicación es un método de este objeto).

        atomic_type& operator[] (size_type i) { return chunk[i]; }
 
        atomic_type& operator[] (size_type i) { return chunk[i]; }
 

-       // Iteradores
+       // Iteradores (no deberían ser necesarios)

        iterator begin() { return chunk.begin(); }
        iterator end() { return chunk.end(); }
        const_iterator begin() const { return chunk.begin(); }
        iterator begin() { return chunk.begin(); }
        iterator end() { return chunk.end(); }
        const_iterator begin() const { return chunk.begin(); }

-       const_iterator end() const { return chunk.end(); }
+       const_iterator end() const { return chunk.end(); }\r
+       reverse_iterator rbegin() { return chunk.rbegin(); }\r
+       reverse_iterator rend() { return chunk.rend(); }\r
+       const_reverse_iterator rbegin() const { return chunk.rbegin(); }\r
+       const_reverse_iterator rend() const { return chunk.rend(); }\r
+

 
        private:
        // Atributos
        chunk_type chunk;
 
        private:
        // Atributos
        chunk_type chunk;

+       sign_type sign;

 
        // Helpers
 
        // Helpers

+       // Pone un chunk en 0 para que sea un invariante de representación que
+       // el chunk no sea vacío (siempre tenga la menos un elemento).

        void fix_empty() { if (!chunk.size()) chunk.push_back(0); }
        void fix_empty() { if (!chunk.size()) chunk.push_back(0); }

+       // Propaga carry a partir del 'átomo' i (suma 1 al 'átomo' i propagando
+       // carry)

        void carry(size_type i)
        {
                if (chunk.size() > i)
        void carry(size_type i)
        {
                if (chunk.size() > i)


@@ -79,6 +85,62 @@ struct number
        }
 };
 
        }
 };
 

+template < typename T >
+number< T >& number< T >::operator+= (const number< T >& n)
+{
+       atomic_type c = 0;
+       size_type ini = 0;
+       size_type fin = std::min(chunk.size(), n.chunk.size());\r
+       size_type i; //problema de VC++, da error de redefinición\r
+
+       // "intersección" entre ambos chunks
+       // +-----+-----+------+------+
+       // |     |     |      |      | <--- mio
+       // +-----+-----+------+------+
+       // +-----+-----+------+
+       // |     |     |      |        <--- chunk de n
+       // +-----+-----+------+
+       // 
+       // |------------------|
+       // Esto se procesa en este for
+       for (i = ini; i < fin; ++i)
+       {
+               chunk[i] += n.chunk[i] + c;
+               if (chunk[i] || (!n.chunk[i] && !c)) c = 0; // OK
+               else                                 c = 1; // Overflow
+       }
+       // si mi chunk es más grande que el del otro, sólo me queda
+       // propagar el carry
+       if (chunk.size() >= n.chunk.size())
+       {
+               if (c) carry(fin); // Propago carry
+               return *this;
+       }
+       // Hay más
+       // +-----+-----+------+
+       // |     |     |      |         <--- mío
+       // +-----+-----+------+
+       // +-----+-----+------+------+
+       // |     |     |      |      |  <--- chunk de n
+       // +-----+-----+------+------+
+       // 
+       //                    |------|
+       //            Esto se procesa en este for
+       // (suma los chunks de n propagando algún carry si lo había)
+       ini = fin;
+       fin = n.chunk.size();
+       for (i = ini; i < fin; ++i)
+       {
+               chunk.push_back(n.chunk[i] + c); // Agrego nuevo átomo
+               if (chunk[i] || !c) c = 0; // OK
+               else                c = 1; // Overflow
+       }
+       // Si me queda algún carry colgado, hay que agregar un "átomo"
+       // más al chunk.
+       if (c) chunk.push_back(1); // Último carry
+       return *this;
+}
+

 template < typename T >
 number< T > operator+ (const number< T >& n1, const number< T >& n2)
 {
 template < typename T >
 number< T > operator+ (const number< T >& n1, const number< T >& n2)
 {


@@ -90,8 +152,8 @@ number< T > operator+ (const number< T >& n1, const number< T >& n2)
 template < typename T >
 std::ostream& operator<< (std::ostream& os, const number< T >& n)
 {
 template < typename T >
 std::ostream& operator<< (std::ostream& os, const number< T >& n)
 {

-       // FIXME sacar una salida bonita en ASCII =)
-       std::copy(n.begin(), n.end(), std::ostream_iterator< T >(os, " "));
+       // FIXME sacar una salida bonita en ASCII =)\r
+       std::copy(n.rbegin(), n.rend(), std::ostream_iterator< T >(os, " "));

        return os;
 }
 
        return os;
 }