20201201 ABB+Heap+Stack | Buscar las 150 palabras más repetidas en el libro "quijote de la mancha"

#include <iostream>
#include <fstream>
using namespace std;

/******************************************************************/
#include <queue>
template <class T> class Heap {
public:
    Heap() {};
    virtual ~Heap() {};

    void agregar(T dato, int prioridad) {
        ParPrioridadDato par;
        par.first = prioridad;
        par.second= dato;
        h2.push(par);
    };

    T extraer(){
        ParPrioridadDato par = h2.top();
        h2.pop();
        return par.second;
    }

    bool vacia() {
        return h2.empty();
    }

private:
    typedef std::pair<int, T> ParPrioridadDato; // Prioridad, orden

    class ComparePrioridad {
        public:
            bool operator() (ParPrioridadDato a, ParPrioridadDato b) {
                return a.first > b.first;
            }
    };
    std::priority_queue<ParPrioridadDato, std::vector<ParPrioridadDato>, ComparePrioridad> h2;
};

#include <stack>
template <class Tipo>
class Stack : private stack<Tipo> {
public:
    void push(Tipo _valor) {
        stack<Tipo>::push(_valor);
    }

    Tipo pop() {
        Tipo temp = stack<Tipo>::top();
        stack<Tipo>::pop();
        return temp;
    }

    bool empty () {
        return stack<Tipo>::empty();
    }
};
/******************************************************************/

struct Nodo {
    string key;
    int value;
    struct Nodo* izq;
    struct Nodo* der;
};
typedef Nodo* AB;

/*aunque podríamos utilizar la estructura Nodo,
ocuparemos la estructura ParDatos para que sea más ilustrativa
*/
struct ParDatos{
    string key;
    int value;
};

void insertar(AB &t, string key){
    if(t == NULL){
        t = new Nodo();
        t->key = key;
        t->value = 1; //es la primera vez que aparece la palabra
        t->izq = NULL;
        t->der = NULL;
    } else {
        if(key == t->key)
            t->value = t->value +1; //procesamos
        else {
            if(key < t->key)
                insertar(t->izq, key);
            else
                insertar(t->der, key);
        }
    }
}

//mostrar un árbol
void mostrarABB(AB raiz){
    if(raiz == NULL)
        return;
    cout <<raiz->key<<" ("<<raiz->value<<") ";
    mostrarABB(raiz->izq);
    mostrarABB(raiz->der);
}

void AbbToHeap(AB t, Heap<ParDatos> &h){
    if(t == NULL)
        return;

    ParDatos p;
    p.key   = t->key; //la palabra
    p.value = t->value; //cantidad de veces que aparece la palabra
    h.agregar(p, p.value);

    AbbToHeap(t->izq, h);
    AbbToHeap(t->der, h);
}

void mostrarHeap(Heap<ParDatos> h){
    while(!h.vacia()){
        ParDatos p = h.extraer();
        cout <<p.key<<" ("<<p.value<<") ";
    }
}

void heapToStack(Heap<ParDatos> h, Stack<ParDatos> &s){
    while(!h.vacia()){
        ParDatos p = h.extraer();
        s.push(p);
    }
}

void mostrarStackN(Stack<ParDatos> s, int contador){
    int c = contador+1;
    while(!s.empty()){
        ParDatos p = s.pop();
        cout <<c-contador<<" "<<p.key<<" ("<<p.value<<")"<<endl;
        contador--;
        if(contador <= 0)
            return;
    }
}

void leerArchivo(string nombreArchivo, AB &raiz){
    ifstream archivo;
    archivo.open(nombreArchivo.c_str(), ios::in);
    string palabra;
    if(archivo.is_open()){
        while(getline(archivo, palabra, ' '))
            insertar(raiz, palabra);
    } else
        cout <<"error en archivo"<<endl;
}

int main() {
    /**Objetivo: leer un archivo y obtener las 150 palabras que más se repiten**/
    setlocale(LC_CTYPE,"Spanish");
    AB raiz = NULL;

    Heap<ParDatos> h;

    Stack<ParDatos> s;

    //Para descargar el quijote https://gist.github.com/jsdario/6d6c69398cb0c73111e49f1218960f79
    leerArchivo("C:\\DATA\\el_quijote.txt", raiz);

    //mostrarABB(raiz);
    AbbToHeap(raiz, h);

    //mostrarHeap(h);
    heapToStack(h, s);

    mostrarStackN(s, 150);

    return 0;
}