#ifndef ARRAYORD_H
#define ARRAYORD_H

#include <cassert>
#include <iostream>
#include "auxiliares.hpp"

using namespace std;

/*
    Modulo ArregloOrdenado
    Arreglo con interfaz para insercion ordenada y busqueda en orden O(log n)

    Diferencias con el diseño:
        + Se agregó dentro del módulo la funcionalidad para hacer busqueda en orden O(log n),
          que en el diseño era un auxiliar del modulo Sistema.
        + El arreglo es de punteros al tipo, no de referencias al tipo.
          Esto es porque en C++ las referencias son inmutables y se
          deseaba mantener la copia en O(1)
        + La implementacion de insertar ordenado es ligeramente distinta.
          Al momento de dejar el espacio necesario para que entre el nuevo elemento,
          En vez de mantener dos indices e ir de izquierda a derecha, lo que se hace
          es ir de derecha a izquierda intercambiando posicion sucesivas, evitando asi
          necesitar mantener dos indices.
*/

//NOTA: El tipo T debe tener igualdad, menor o igual y copia
template<typename T>
class ArregloOrdenado{
    public:
        //Constructor
        ArregloOrdenado(Nat m);
        //Constructor por copia
        ArregloOrdenado(const ArregloOrdenado<T> & a);
        //Destructor
        ~ArregloOrdenado();
        //Devuelve el tamanio del arreglo
        Nat Tamanio() const;
        //Devuelve el tamanio maximo del arreglo, es decir la maxima cantidad de elementos que se puede insertar.
        Nat TamanioMaximo() const;
        /*
        Devuelve el valor correspondiente al lugar en el indice pasado por parametro.
        ALIASING: El valor correspondiente se devuelve por referencia y es modificable.
        PRE: El indice tiene que ser menor o igual que la cantidad de elementos del arreglo
        */
        T & operator[](Nat i) const;
        /*
        Inserta un elemento en el arreglo de manera que, ademas de introducirse el nuevo elemento, el arreglo siga ordenado
        ALIASING: El valor correspondiente se asigna por copia.
        PRE: El tamanio actual del arreglo debe ser menor que el tamaño maximo. Es decir, tiene que haber espacio para el elemento.
        */
        void AgregarOrdenado(const T & e);
        /*
        Busca la posicion en el arreglo del valor pasado como parametro. Usa busqueda binaria por lo tanto la complejidad es O(log n)
        PRE: El elemento debe estar en el arreglo.
        */
        Nat Buscar(const T & e) const;

    private:
        //Tamaño y tamaño maximo del arreglo
        Nat _tam, _tamMax;
        //Arreglo de punteros a elementos del arreglo.
        T** _elems;
};

template<typename T>
ArregloOrdenado<T>::ArregloOrdenado(Nat n){
    _tam = 0;
    _tamMax = n;
    _elems = new T*[n];
}

template<typename T>
ArregloOrdenado<T>::ArregloOrdenado(const ArregloOrdenado<T> & a){
    _tam = a.tamanio();
    _tamMax = a.tamanioMaximo();

    //Creo el arreglo
    _elems = new T*[_tam];

    //Copio cada uno de los elementos, asignandole punteros
    for(Nat i = 0; i < _tam; i++)
        _elems[i] = new T(a[i]);
}

template<typename T>
ArregloOrdenado<T>::~ArregloOrdenado(){
    //Primero borro todos los elementos.
    for(Nat i = 0; i < _tam; i++)
        delete _elems[i];

    //Y despues el arreglo tambien.
    delete [] _elems;
}

template<typename T>
Nat ArregloOrdenado<T>::Tamanio() const{
    return _tam;
}

template<typename T>
Nat ArregloOrdenado<T>::TamanioMaximo() const{
    return _tamMax;
}

template<typename T>
T & ArregloOrdenado<T>::operator[](Nat i) const{
    assert(i >= 0 && i < _tam);
    return *_elems[i];
}

template<typename T>
void ArregloOrdenado<T>::AgregarOrdenado(const T & e) {
    assert(_tam < _tamMax);

    Nat i = 0;
    //Primero busco en que lugar del arreglo tengo que insertarlo.
    //Puesto que la complejidad es O(n) si o si, por simplicidad esta busqueda se hace de manera lineal.
    while(i < _tam && e > *(_elems[i]))
        i++;

    //Incremento el tamaño porque tengo un elemento mas
    _tam++;

    //Muevo todos los elementos que a partir de i un lugar para adelante.
    //Entonces libero el espacio donde tengo que poner el nuevo valor.
    for(Nat j = _tam-1; j >= i+1; j--){
        //Todas las copias aca son O(1) porque se copian punteros.
        T * temp = _elems[j];
        _elems[j] = _elems[j-1];
        _elems[j-1] = temp;
    }

    //Ahora que el lugar esta liberado, copio el valor a agregar y lo asigno a donde tiene que ir.
    _elems[i] = new T(e);
}

template<typename T>
Nat ArregloOrdenado<T>::Buscar(const T & e) const{
    /*
    Hago busqueda binaria sobre el arreglo
    Inicialmente l es el extremo izquierdo y r es el extremo derecho del arreglo.
    Por estar ordenados sabemos que a[l] < e
    */

    Nat l = 0, r = _tam;
    while(r-l > 1){
        Nat m = (l+r)/2;

        if(e > (*_elems[m])){
            //Si el elemento es mas grande que el del medio, tenemos que mirar la mitad derecha.
            l = m;
        }else{
            //Sino, tenemos que mirar la mitad izquierda.
            r = m;
        }
    }

    /*
    Al final del ciclo se mantiene invariante que a[l] < e
    Pero porque r-l = 1, a[l] es el ultimo valor tal que a[l] < e
    Por lo tanto, e tiene que ser igual a a[l] o a[r]
    */
    return e == (*_elems[l]) ? l : r;
}

//PARA PROPOSITOS DE DEBUGGEO.
template<typename T>
std::ostream & operator<<(std::ostream & out, const ArregloOrdenado<T> & a){
    out << "{ ";
    for(Nat i = 0; i < a.tamanio(); i++)
        out << a[i] << " ";
    out << "}";

    return out;
}

#endif