#ifndef _SACO_H_
#define _SACO_H_

const int MAX_NUM_ELEMENTOS = 1000;

// Interfaz del TAD. Pre-declaraciones:

template<typename Elemento> struct Saco;
/* El tipo Elemento requerirá tener las funciones
 * int precio(const Elemento& e);
 * bool operator==(const Elemento& e1, const Elemento& e2);
 */

template<typename Elemento> void vacio(Saco<Elemento>& s);
template<typename Elemento> bool meter(Saco<Elemento>& s, const Elemento& e);
template<typename Elemento> void sacar(Saco<Elemento>& s, const Elemento& e);
template<typename Elemento> int cuantos(const Saco<Elemento>& s, const Elemento& e);
template<typename Elemento> int valor(const Saco<Elemento>& s);

// Operación auxiliar (interna)

template<typename Elemento> int buscar(const Saco<Elemento>& s, const Elemento& e);

// Declaración

template<typename Elemento> struct Saco {
    friend void vacio<Elemento>(Saco<Elemento>& s);
    friend bool meter<Elemento>(Saco<Elemento>& s, const Elemento& e);
    friend void sacar<Elemento>(Saco<Elemento>& s, const Elemento& e);
    friend int cuantos<Elemento>(const Saco<Elemento>& s, const Elemento& e);
    friend int valor<Elemento>(const Saco<Elemento>& s);
    friend int buscar<Elemento>(const Saco<Elemento>& s, const Elemento& e);
private:
    struct Repeticiones {
        Elemento dato;
        int numRep;
    };
    Repeticiones elementos [MAX_NUM_ELEMENTOS];
    int total;
};


// Implementación de las operaciones

template<typename Elemento> void vacio(Saco<Elemento>& s) {
    s.total = 0;
}

template<typename Elemento> int buscar(const Saco<Elemento>& s, const Elemento& e) {
    int pos = 0;
    while (pos < s.total && !(s.elementos[pos].dato == e)) {
        pos = pos + 1;
    }
    if (pos == s.total) {
        pos = -1;
    }
    return pos;
} 
    
template<typename Elemento> bool meter(Saco<Elemento>& s, const Elemento& e) {
    bool sePuede = true;
    int pos = buscar(s,e);
    if (pos != -1) {
        s.elementos[pos].numRep = s.elementos[pos].numRep + 1;
    } 
    else {
        sePuede = s.total < MAX_NUM_ELEMENTOS;
        if (sePuede) {
            s.elementos[s.total].dato = e;
            s.elementos[s.total].numRep = 1;
            s.total = s.total + 1;
        }
    }            
    return sePuede;
}

template<typename Elemento> void sacar(Saco<Elemento>& s, const Elemento& e) {
    int pos = buscar(s,e);
    if (pos != -1) {
        if (s.elementos[pos].numRep > 1) {
            s.elementos[pos].numRep = s.elementos[pos].numRep - 1;
        }
        else { // al sacar, quedan 0 unidades de ese elemento
            if (s.total == 1) {
                s.total = 0;
            }
            else { // sustituirlo por el ultimo de la tabla
                s.total = s.total - 1;
                s.elementos[pos].dato = s.elementos[s.total].dato;
                s.elementos[pos].numRep = s.elementos[s.total].numRep;
            }
        }
    }
}

template<typename Elemento> int cuantos(const Saco<Elemento>& s, const Elemento& e) {
    int pos = buscar(s,e);
    if (pos != -1) {
        return s.elementos[pos].numRep;
    }
    else {
        return 0;
    }
}

template<typename Elemento> int valor(const Saco<Elemento>& s) {
    int res = 0;
    for (int i = 0; i < s.total; i++) {
        res = res + s.elementos[i].numRep * precio(s.elementos[i].dato);
    }
    return res;
}

#endif