// OrdVc.h     (c) 2001  adolfo@di-mare.com

typedef int T;  // T es un "int"

#include "Lista.h"

class Lista {
    class nodo { ... };

    class iter_ord {    friend class List;

        struct cont_vector {    friend class iter_ord;
            size_t   n;     // contador de iteradores conectados
            T     * _ap[];  // vector de punteros
        }; // cont_vector

        iter_ord();   // constructor
        ~iter_ord();  // destructor

        iter_ord(const iter_ord& ); // constructor copia
        iter_ord& operator=( const iter_ord& ); // copia

        friend bool operator == (const iter_ord&, const iter_ord& );
        friend bool operator != (const iter_ord&, const iter_ord& );

        iterator operator++();    // ++p
        iterator operator++(int); // p++

        iterator operator--();    // --p
        iterator operator--(int); // p--

        iterator operator+(int);  // p+i  <==>  p.operator+(i)
        iterator operator-(int);  // p-i

        T& operator*() { return *(_vc->_ap[_idx]); } // *p y p->

    private:
       cont_vector * _vc;
       size_t  _idx;
       size_t  _dim;
    }; // List::iter_ord

    static const iter_ord iter_ord_END;

    iter_ord begin_ord();
    iter_ord  end_ord()  { return iter_ord(); }
    iter_ord &end_ord()  { return iter_ord_END; }
}; // Lista
#endif

inline bool operator != (const iter_ord& izq, const iter_ord& der) {
    return !(izq == der);  // return !( operator == (izq, der) );
}


// EOF: OrdVc.h

// OrdVc.cpp   (c) 2001  adolfo@di-mare.com

/*  modelo:
    Este iterador tiene definidos en el Rep dos campos
    que son un puntero a un arreglo que contiene
    elementos de tipo PLpos, los que apuntan a los de la
    lista a recorrer; el otro espacio es el índice del
    elemento de la lista a procesar.

    Para recorrer en orden la lista, lo que se hace es
    construir primero el arreglo de punteros y luego
    ordenar esos punteros.

    Para lograr una mayor eficiencia, el arreglo de
    punteros se asigna en memoria dinámica y tiene
    exactamente el número de elementos requerido para
    recorrer la lista.

    El siguiente gráfico muestra esta estructura.

                 _______________________________________
                |         |         |         |         |
  _ap ========> |    0    |    1    |    2    |    3    |
                |_________|_________|_________|_________|
                |____*____|____*____|____*____|_________|
                     |         |         |         ||
                     |    +----+    +----+         ||
                     |    |         |              ||
                     +----+---------+----++        ||
                          |         |    ||        ||
                     ++---+    ++---+    ||        ||
                     ||        ||        ||        ||
                     \/        \/        \/        \/

             L == (  B         C         A         D )
*/

/*  invariante
*/

Lista::iter_ord::iter_ord() {
    _vc   = 0;  // No hay vector de punteros
    _idx = 0;
    _dim = 0;  // _ap[] tiene 0 elementos
}


Lista::iter_ord::~iter_ord() {
    if (_vc != 0) {   // se desconecta de su propio _vc->cont_vector
        _vc->n--;
        if (_vc->n == 0) {       // si es el último...
            delete[] _vc->_ap;   // ... mata el vector
            delete   _vc;
        }
    }
} // Lista::iter_ord::~iter_ord()


Lista::iter_ord( const Lista::iter_ord& o ) { // constructor copia
    // se conecta al nuevo contador de vector (el de "o")
    if (o._vc == 0) {
        _vc = 0;
    }
    else {
        o._vc->n++;   // aumenta cuenta
        _vc = o._vc;  // re-conecta
    }

    _dim = o._dim;    // termina de copiar "o"
    _idx = o._idx;
}


Lista::iter_ord& Lista::iter_ord::operator=( const Lista::iter_ord& o ) {
/*  resultado
    Copia el valor de "o" a "*this".
*/
    if (this == &o) {   // evita auto-copia
        return *this;
    }

    if (_vc != 0) {   // se desconecta de su propio _vc->cont_vector
        _vc->n--;
        if (_vc->n == 0) {       // si es el último...
            delete[] _vc->_ap;   // ... mata el vector
            delete   _vc;
        }
    }

    // se conecta al nuevo contador de vector (el de "o")
    if (o._vc == 0) {
        _vc = 0;
    }
    else {
        o._vc->n++;   // aumenta cuenta
        _vc = o._vc;  // re-conecta
    }

    _dim = o._dim;    // termina de copiar "o"
    _idx = o._idx;

    return *this;
} // Lista::iter_ord::operator=()


bool operator == (const iter_ord& izq, const iter_ord& der) {
    if ( (izq._dim != der._dim) || (izq._idx != der._idx) ) {
        return false;
    }

    assert( (izq._dim == der._dim) && (izq._idx == der._idx) );

    if (izq._vc == der._vc) {
        return true;
    }

    assert( izq._vc != der._vc );
//  #define assert(X) ((X) ? /* nada */ ; abort(#X) )

    for (int i = 0; i < izq._dim; ++i) {
        if (izq._vc->_ap[i] != der._vc->_ap[i]) {
            return false;
        }
    }

    return true;
} // operator == ()


Lista::iter_ord& operator++() { // ++p
    if (_idx != _dim) {
        _idx++;
        return *this;
    }
    else {
        if (_vc != 0) {   // se desconecta de su propio _vc->cont_vector
            _vc->n--;
            if (_vc->n == 0) {       // si es el último...
                delete[] _vc->_ap;   // ... mata el vector
                delete   _vc;
            }
        }
        _vc  = 0;
        _dim = 0;
        _idx = 0;
        return *this;
    }
} // ++p

Lista::iter_ord Lista::iter_ord operator++(int) { // p++
/* FALTA HACERLO DE MANERA SIMILAR A:
    iterator operator++(int); // p++
        { iterator q = _puntero; _puntero = _puntero -> next; return q; }
*/
} // p++


void Sort(T* A[], size_t N) {
/* resultado
    Ordena el vector de posiciones de lista "A" usando
    el método de la búrbuja.
    - "N" es la cantidad de elementos del vector.
*/
    size_t i,j;
    bool cambiado;
    j = 0;
    do {
        cambiado = false;
        for ( i = 0 ; i < N - j ; ++i) {
            if (*A[i+1] =< *A[i]) { // fuera de orden
                cambiado = TRUE;

                // intercambia A[i] <====> A[i+1]
                T * temp = A[i+1];
                A[i+1]   = A[i];
                A[i]     = temp;
            }
        }
        j++;
     } while (! cambiado);
}  // Sort

Lista::iter_ord Lista::begin_ord() {
    iter_ord B; // B queda inicializado en nulo

    B._dim = count();

    B._vc     = new cont_vector;   // crea el primer contador
    B._vc->_n = 1;                 // sólo "B" le apunta

    B._vc->_ap = new T* [B._dim];  // crea el vector del contador

    // meter en _ap[] los punteros a nodos
    for (size_t i=0, iterator p = begin(); p != end(); ++p, ++i) {
        B._vc->_ap[i] = &(*p); // & ( p.operator*() );
    }

    Sort(B._vc->_ap, B._dim);
    return B;
} // Lista::begin_ord()


#if 0
{ modelo para implementar la invariante del itr_ord::ok()  }
{ La lista es circular, y el campo _last es el último nodo }

FUNCTION  OK(            { EXPORT }     { ADH }
  {+} VAR L : TList      { SELF }
) {>>>>>>>} : BOOLEAN;
{ RESULTADO
  Verifica que la invariante de TList sea verdadera,
  o sea que la lista "L" esté construída
  adecuadamente. }
{ REQUIERE
  - Si "L" es una lista bien construida, entonces
    esta función retornará TRUE. Si no, es posible
    que no retorne, o que el programa se cancele.
  - OK() no es un procedimiento realmente correcto,
    pues es posible que regrese TRUE aún cuando la
    lista está rota. }

{ NOTA
  En general, la operación OK no es tan simple de
  implementar, y muchas veces NO es posible
  implementarla adecuadamente, principalmente si el
  Rep del ADT usa memoria dinámica. }
VAR
  n : LONGINT;  { número de nodos  }
  p : PNode;    { nodo de la lista }
BEGIN { OK }
{
  Como es muy difícil saber si una cadena está
  realmente rota, lo que se hace es recorrer la lista
  "L" hasta que sucede una de tres cosas:
  - Se encuentra el último elemento de "L", que se
    reconoce porque se da la condición L.Rep._last = p
  - Se itera MaxLongInt veces sobre la lista. Como no
    hay suficiente memoria para implementar una lista
    tan grande, entonces se puede deducir que la lista
    está rota, o que tiene un ciclo interno.
  - Se encuentra un elemento que no está bien
    construido.

  Lo malo es que no siempre es posible saber DONDE
  está mala la lista...
}
  IF L.Rep._last = NIL THEN BEGIN
    OK := TRUE;
    EXIT;         { Se sale si la lista está vacía }
  END;

  IF CORRUPTED in L.Rep._bhvr THEN BEGIN
    OK := FALSE;
    EXIT;
  END;

  n := 0;
  p := L.Rep._last;
  REPEAT
    IF (p = NIL) OR (n = MaxLongInt) THEN BEGIN
      OK := FALSE;
      EXIT;
    END
    ELSE IF NOT Elem.OK(p^.elem) THEN BEGIN
      OK := FALSE;
      EXIT;
    END;
    p := p^.next;
    INC(n);
  UNTIL p = L.Rep._last;

  OK := TRUE;

  {$IFDEF CPU86} { ==> INTEL x86 }
  {
    Si el computador no tiene TODA la memoria
    direccionable (1 megabyte), y si "L" está rota y
    alguno de sus punteros apunta a una dirección de
    memoria que no existe en el computador, entonces
    es posible que el programa se cancele al tratar
    de accesar una posición inválidad de memoria.
  }
  {$ENDIF CPU86}
END;  { OK }
#endif


// EOF: OrdVc.cpp