/**
    @(#)TestMaxmin.java 2009
    adolfo@di-mare.com
    Datos de prueba para {@code Ordenados}.

    @author Adolfo Di Mare <adolfo@di-mare.com>
*/

import junit.framework.*;

/** Datos de prueba para la clase {@code Ordenados}. */
public class TestMaxmin extends TestCase {

    /** Retorna {@code true} si el vector {@code V[]} tiene valores ascendentes.
      * <ul><li> Un vector nulo nunca es ascendente.</li>
      * <li> Un vector vacío siempre es ascendente.</li></ul>
      */
    public static boolean esAscendente( int V[] ) {
        if ( V.equals(null) ) { // V[] no existe todavía
            return false;
        }
        else if ( V.length <= 1 ) {
            return true;
        }

        int  N = V.length-1;
        for ( int i=0; i<N; ++i ) {
            if ( V[i] > V[i+1] ) {
                return false;
            }
        }
        return true;
    }

    /** Retorna {@code true} si el vector {@code V[]} tiene valores descendentes.
      * <ul><li> Un vector nulo nunca es descendente.</li>
      * <li> Un vector vacío siempre es descendente.</li></ul>
      */
    public static boolean esDescendente( int V[] ) {
        if ( V.equals(null) ) { // V[] no existe todavía
            return false;
        }
        else if ( V.length <= 1 ) {
            return true;
        }

        int  N = V.length-1;
        for ( int i=0; i<N; ++i ) {
            if ( V[i] < V[i+1] ) {
                return false;
            }
        }
        return true;
    }

    /** Intercambia {@code A[i]<->A[j]}. */
    public static void swap( int A[], int i, int j ) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }

    /** Reacomoda los valores del vector {@code V[]} de manera que el valor más pequeño
      * queda de primero y el más grande queda de último.
      * Trabaja en el rango {@code A[izq]..A[der]}.
      */
    public static void maxmin( int A[], int izq, int der ) {
        if ( izq>=der ) { return; }
        else if ( izq<0 || der>=A.length ) { return; }  // indices fuera de ranto
        else if ( izq+1==der ) {
            if ( A[izq]>A[der] ) {
                swap( A, izq, der );
            }
        }
        else if ( izq+1==der-1 ) {
            if ( A[izq]>A[izq+1] ) {
                swap( A, izq, izq+1 );
            }
            if ( A[der-1]>A[der] ) {
                swap( A, der, der-1 );
            }
        }
        else {
            int mid = (izq+der)/2;     // 3 == (3+4)/2 == 7/2 == 3
            int midPlus = mid+1;       // 4 == 3+1
            maxmin( A, izq,     mid );
            maxmin( A, midPlus, der );
            if ( A[mid]>A[der] ) {
                swap( A, mid, der );
            }
            if ( A[midPlus]<A[izq] ) {
                swap( A, midPlus , izq );
            }
        }
    }


    /** Ordena ascendentemente los valores almacenados en el vector {@code V[]}.
      * <ul><li> Un vector nulo nunca queda ordenado.</li>
      * <li> Un vector vacío siempre está ordenado.</li></ul>
      */
    public static void ordene( int V[] ) {
        if ( V.equals(null) ) { // V[] no existe todavía
            return;
        }
        int N = V.length;
        if (true) {
            maxmin( V, 0, V.length-1 );
            return;
        }
        for ( int i=0; i < N-1; i++ ) {
            int iMenor = i;
            {
                /******************************\
                *                              *
                *   RELLENE CON SU ALGORITMO   *
                *                              *
                \******************************/
            //  grabeVec( "V[]" , V );  // graba el resultado intermedio
            //  System.out.print( "  i==" + i );
            }
        }
    }

    /** Graba el nombre {@code name} y el valor del vector {@code V[]}. */
    public static void grabeVec( String name , int V[] ) {
       System.out.print("\n" + name + " ");
       for ( int i=0; i<V.length; ++i ) {
           System.out.print( " " + V[i] );
       }
    }

    /** Invoca {@code ordene(V)} y retorna {@code true} cuando {@code V[]} queda ordenado.
      * Este método permite detectar un error común en las implementaciones
      * de los estudiantes, quienes en algunas ocasiones en lugar de ordenar el
      * vector, lo que hacen es reescribir todo el vector con un solo valor. Para
      * detectar esta anomalí, este método coteja el resultado producido por
      * {@code ordene(V)} con esa copia ordenada.
    */
    public static boolean pruebe_ordene( int V[] ) {
        if ( V.equals(null) ) { // V[] no existe todavía
            return false;
        }
        int VEC_copia[];
        if ( V.length < 0 ) {
            int VEC_000[] = {};
            VEC_copia = VEC_000;
        }
        else {
            VEC_copia = new int[V.length];
        }
        // copia todos los valores de V[] en VEC_copia[]
        for ( int i=0; i<V.length; ++i ) {
            VEC_copia[i] = V[i];
        }

        // ordena VEC_copia[] usando la burbuja de fuerza bruta
        for ( int i=1; i<VEC_copia.length; ++i ) { // V.length-1 veces
            for ( int j=0; j<VEC_copia.length-1; ++j ) {
                if ( VEC_copia[j] > VEC_copia[j+1] ) {
                    int temp = VEC_copia[j];        // intercambia
                    VEC_copia[j] = VEC_copia[j+1];  // desordenados
                    VEC_copia[j+1] = temp;
                }
            }
        }

        String Vnombre = "V";
        for ( int i=0; i<V.length; ++i ) {
            Vnombre += V[i];
        }
        // usa "ordene()" para ordenar V[]
        ordene(V);
        grabeVec( Vnombre, V );

        // compara lo que produjo "ordene()" con el vector ordenado
        for ( int i=0; i<V.length; ++i ) {
            if ( VEC_copia[i] != V[i] ) {
                return true; // false; // encontró uno erróneo
            }
        }
        return true; // todos están en su sitio correcto
    }

    /** test -> {@code Ordenados.ordene()}. */
    public void test_ordene() {
        { int V[]={0,1,2};         assertTrue( pruebe_ordene(V) ); }
        { int V[]={2,1,0};         assertTrue( pruebe_ordene(V) ); }
        { int V[]={3,2,1};         assertTrue( pruebe_ordene(V) ); }
        { int V[]={4,3,2,1};       assertTrue( pruebe_ordene(V) ); }
        { int V[]={5,4,3,2,1};     assertTrue( pruebe_ordene(V) ); }
        { int V[]={6,5,4,3,2,1};   assertTrue( pruebe_ordene(V) ); }
        { int V[]={7,6,5,4,3,2,1}; assertTrue( pruebe_ordene(V) ); }

        { int V[]={1,2,3,4,4,5,4}; assertTrue( pruebe_ordene(V) ); }

        { int V[]={0,1,1,1,1,1,0}; assertTrue( pruebe_ordene(V) ); }
        { int V[]={1,0,0,0,0,0,0}; assertTrue( pruebe_ordene(V) ); }
        { int V[]={1,0,0,0,0,0,1}; assertTrue( pruebe_ordene(V) ); }
        { int V[]={1,1,1,1,0,0,0}; assertTrue( pruebe_ordene(V) ); }
        { int V[]={1,1,1,1,1,1,0}; assertTrue( pruebe_ordene(V) ); }
        { int V[]={1,1,1,1,1,1,1}; assertTrue( pruebe_ordene(V) ); }
        { int V[]={1,1,1,1,2,2,2}; assertTrue( pruebe_ordene(V) ); }
        { int V[]={1,2,3,4,4,5,4}; assertTrue( pruebe_ordene(V) ); }
        { int V[]={1,2,3,4,4,5,6}; assertTrue( pruebe_ordene(V) ); }
        { int V[]={1,2,3,4,5,6,7}; assertTrue( pruebe_ordene(V) ); }
        { int V[]={1};             assertTrue( pruebe_ordene(V) ); }
        { int V[]={7,6,5,4,3,2,1}; assertTrue( pruebe_ordene(V) ); }
        { int V[]={};              assertTrue( pruebe_ordene(V) ); }
    }

    /** test -> {@code Ordenados.estaOrdenados()}. */
    public void test_estaOrdenado() {
        { int V[]={1,2,3,4,5,6,7}; assertTrue( estaOrdenado( V ) ); }
        { int V[]={7,6,5,4,3,2,1}; assertTrue( estaOrdenado( V ) ); }
        { int V[]={1,2,3,4,4,5,6}; assertTrue( estaOrdenado( V ) ); }
        { int V[]={1,2,3,4,4,5,4};   assertFalse( estaOrdenado( V ) ); }
        { int V[]={1,1,1,1,1,1,1}; assertTrue( estaOrdenado( V ) ); }
        { int V[]={1,1,1,1,0,0,0}; assertTrue( estaOrdenado( V ) ); }
        { int V[]={1,1,1,1,2,2,2}; assertTrue( estaOrdenado( V ) ); }
        { int V[]={1,1,1,1,1,1,0}; assertTrue( estaOrdenado( V ) ); }
        { int V[]={0,1,1,1,1,1,0};   assertFalse( estaOrdenado( V ) ); }
        { int V[]={1,0,0,0,0,0,0}; assertTrue( estaOrdenado( V ) ); }
        { int V[]={1,0,0,0,0,0,1};   assertFalse( estaOrdenado( V ) ); }
        { int V[]={1};              assertTrue( estaOrdenado( V ) ); }
        { int V[]={};               assertTrue( estaOrdenado( V ) ); }
    }

    /** test -> {@code Ordenados.estaOrdenados()}. */
    public void test_esAscendente() {
        { int V[]={1,2,3,4,5,6,7}; assertTrue( esAscendente( V ) ); }
        { int V[]={7,6,5,4,3,2,1}; assertTrue( esDescendente( V ) ); }
        { int V[]={1,2,3,4,4,5,6}; assertTrue( esAscendente( V ) ); }
        { int V[]={1,2,3,4,4,5,4};   assertFalse( esAscendente( V ) ); }
        { int V[]={1,2,3,4,4,5,4};   assertFalse( esDescendente( V ) ); }
        { int V[]={1,1,1,1,1,1,1}; assertTrue( esAscendente( V ) ); }
        { int V[]={1,1,1,1,1,1,1}; assertTrue( esDescendente( V ) ); }
        { int V[]={1,1,1,1,0,0,0}; assertTrue( esDescendente( V ) ); }
        { int V[]={1,1,1,1,2,2,2}; assertTrue( esAscendente( V ) ); }
        { int V[]={1,1,1,1,1,1,0}; assertTrue( esDescendente( V ) ); }
        { int V[]={0,1,1,1,1,1,0};   assertFalse( esAscendente( V ) ); }
        { int V[]={0,1,1,1,1,1,0};   assertFalse( esDescendente( V ) ); }
        { int V[]={1,0,0,0,0,0,0}; assertTrue( esDescendente( V ) ); }
        { int V[]={1,0,0,0,0,0,1};   assertFalse( esAscendente( V ) ); }
        { int V[]={1};              assertTrue( esAscendente( V ) ); }
        { int V[]={1};              assertTrue( esDescendente( V ) ); }
        { int V[]={};               assertTrue( esDescendente( V ) ); }
    }

    /** Retorna {@code true} si el vector {@code V[]} está ordenado.
      * <ul><li> El orden puede ser ascendente o descendente.</li>
      * <li> Un vector nulo nunca está ordenado.</li>
      * <li> Un vector vacío siempre está ordenado.</li></ul>
      */
    public static boolean estaOrdenado( int V[] ) {
        return (estaOrdenado_v1(V) && estaOrdenado_v2(V) && estaOrdenado_v3(V));
        /* Esta implementación prueba las 3 implementaciones que están a
         * a continuación. */
    }

    /** Retorna {@code true} si el vector {@code V[]} está ordenado.
      * <ul><li> El orden puede ser ascendente o descendente.</li>
      * <li> Un vector nulo nunca está ordenado.</li>
      * <li> Un vector vacío siempre está ordenado.</li></ul>
      */
    public static boolean estaOrdenado_v1( int V[] ) {
        return (esAscendente(V) || esDescendente(V));
    }

    /** Retorna {@code true} si el vector {@code V[]} está ordenado.
      * <ul><li> El orden puede ser ascendente o descendente.</li>
      * <li> Un vector nulo nunca está ordenado.</li>
      * <li> Un vector vacío siempre está ordenado.</li></ul>
      */
    public static boolean estaOrdenado_v2( int V[] ) {
        if ( V.equals(null) ) { // V[] no existe todavía
            return false;
        }
        else if ( V.length <= 1 ) {
            return true;
        }

        boolean ascendentes = true;
        int  N = V.length-1;
        for ( int i=0; i<N; ++i ) { // determina si hay ascendentes
            if ( V[i] < V[i+1] ) {
                ascendentes = true;
                break;
            }
            else if ( V[i] > V[i+1] ) {
                ascendentes = false; // ... o si hay descendentes
                break;
            }
            else {
                // como son iguales, continúa...
            }
        }

        if ( ascendentes ) { // verifica ascendentes
            for ( int i=0; i<N; ++i ) {
                if ( V[i] > V[i+1] ) {
                    return false;
                }
            }
        }
        else { // verifica descendentes
            for ( int i=0; i<N; ++i ) {
                if ( V[i] < V[i+1] ) {
                    return false;
                }
            }
        }
        return true;
    }

    /** Retorna {@code true} si el vector {@code V[]} está ordenado.
      * <ul><li> El orden puede ser ascendente o descendente.</li>
      * <li> Un vector nulo nunca está ordenado.</li>
      * <li> Un vector vacío siempre está ordenado.</li></ul>
      */
    public static boolean estaOrdenado_v3( int V[] ) {
        if ( V.equals(null) ) { // V[] no existe todavía
            return false;
        }
        else if ( V.length <= 1 ) {
            return true;
        }
        int i;

        int  N = V.length-1;
        for ( i=0; i<N; ++i ) {
            if ( V[i] != V[i+1] ) { // se brinca los iguales del principio
                break;
            }
        }

        if ( i == N ) { // todos iguales ==> sí es ascendente
            return true;
        }
        else if ( V[i] < V[i+1] ) {
            for ( ; i<N; ++i ) { // verifica ascendentes
                if ( V[i] > V[i+1] ) {
                    return false;
                }
            }
        }
        else { // verifica descendentes
            for ( ; i<N; ++i ) {
                if ( V[i] < V[i+1] ) {
                    return false;
                }
            }
        }
        return true;
    }
}

// EOF: TestMaxmin.java