Priority Queue

#include <iostream>
using namespace std;

template <class H> class Nodo{
    H* key;
    Nodo<H> *next, *prev;

public:
    Nodo(H* key = NULL){
        this->key = NULL;
        if(key) this->key = new H(*key);
        next = prev = NULL;
    }

    Nodo<H>* getPrev(){ return prev; }
    Nodo<H>* getNext(){ return next; }
    H* getKey(){ return key; }

    void setPrev(Nodo<H>* prev){ this->prev = prev; }
    void setNext(Nodo<H>* next){ this->next = next; }
    void setKey(H* key){ if(key) this->key = new H(*key); }
};

template <class H> class List{

protected:
    Nodo<H> *header, *trailer, *current;
    int n;

    Nodo<H>* _search(H x){
        Nodo<H>* tmp = header->getNext();
        while(tmp != trailer && *tmp->getKey() != x)
            tmp = tmp->getNext();
        return tmp;
    }

public:
    List(){
        header = new Nodo<H>();
        trailer = new Nodo<H>();
        header->setNext(trailer);
        trailer->setPrev(header);
        n = 0;
    }

    void insert(H x){
        Nodo<H> *nd = new Nodo<H>(&x);

        n++;

        Nodo<H>* tmp = header->getNext();
        if(tmp == trailer){
            nd->setNext(trailer);
            nd->setPrev(header);
            header->setNext(nd);
            trailer->setPrev(nd);
            return;
        }

        while(tmp != trailer && *tmp->getKey() > *nd->getKey())
            tmp = tmp->getNext();

        nd->setPrev(tmp->getPrev());
        nd->setNext(tmp);
        tmp->getPrev()->setNext(nd);
        tmp->setPrev(nd);
    }

    void del(H x){
        Nodo<H>* tmp = _search(x);
        if(tmp != trailer){
            tmp->getPrev()->setNext(tmp->getNext());
            tmp->getNext()->setPrev(tmp->getPrev());
            delete tmp;
            n--;
        }
    }

    H* begin(){
        current = header;
        return next();
    }

    H* next(){
        if(current->getNext() == trailer) return NULL;
        current = current->getNext();
        return current->getKey();
    }

    int isEmpty(){ return n == 0; }
};

template <class H> class ListQueue: public List<H>{
    int prior, n;

public:
    ListQueue(int prior) : List<H>() {
        this->prior = prior;
        n = 0;
    }

    ListQueue<H>* enqueue(H x){
        Nodo<H>* nd = new Nodo<H>(&x);
        nd->setNext(List<H>::trailer);
        nd->setPrev(List<H>::trailer->getPrev());
        nd->getNext()->setPrev(nd);
        nd->getPrev()->setNext(nd);
        n++;
        return this;
    }

    H* dequeue(){
        Nodo<H>* tmp = List<H>::header->getNext();
        if(tmp != List<H>::trailer){
            H* val = tmp->getKey();
            tmp->getNext()->setPrev(List<H>::header);
            tmp->getPrev()->setNext(tmp->getNext());
            delete tmp;
            n--;
            return val;
        }
        return NULL;
    }

    int getPriority(){ return prior; }
};

/************ OVERLOADING OPERATORI ***********/

int operator>(ListQueue<int>& a, ListQueue<int>& b){
    if(!a.begin()) return 0;
    if(!b.begin()) return 1;
    return (a.getPriority() > b.getPriority()) ? 1 : 0;
}

int operator!=(ListQueue<int>& a, ListQueue<int>& b){
    if(!a.begin() || !b.begin()) return 1;
    return (a.getPriority() != b.getPriority()) ? 1 : 0;
}

template <class H> ostream& operator<<(ostream& out, ListQueue<H>& obj){
    for(H* it = obj.begin(); it; it = obj.next())
        out << *it << " ";
    return out;
}

/********* IMPLEMENTAZIONE PQUEUE *************/

template <class H> class PQueue {
public:
    virtual PQueue<H>* enqueue(H x, int p) = 0;
    virtual H* dequeue() = 0;
    virtual void print() = 0;
};

template <class H> class MyPQueue: public PQueue<H>{
    List< ListQueue<H> >* MPQ;
    int n;

public:
    MyPQueue(){
        MPQ = new List< ListQueue<H> >();
        n = 0;
    }

    PQueue<H>* enqueue(H x, int p){
        n++;

        if(!MPQ->begin()){
            ListQueue<H>* tmp = new ListQueue<H>(p);
            tmp->enqueue(x);
            MPQ->insert(*tmp);
            return this;
        }

        ListQueue<H>* it = MPQ->begin();
        while(it && it->getPriority() != p) it = MPQ->next();

        if(!it){
            ListQueue<H>* tmp = new ListQueue<H>(p);
            tmp->enqueue(x);
            MPQ->insert(*tmp);
        }else it->enqueue(x);
        return this;
    }

    H* dequeue(){
        if(!MPQ->isEmpty()){
            ListQueue<H>* tmp = MPQ->begin();
            H* val = tmp->dequeue();
            if(tmp->isEmpty()) MPQ->del(*tmp);
            return val;
        }
        return NULL;
    }

    void print(){
        for(ListQueue<H>* it = MPQ->begin(); it; it = MPQ->next())
            cout << *it << endl;
        cout << endl;
    }
};

int main(){
    MyPQueue<int>* MPQ = new MyPQueue<int>();
    MPQ->enqueue(2, 8)->enqueue(4, 7)->print();
    MPQ->enqueue(8, 7)->print();
    MPQ->enqueue(13, 4)->enqueue(28, 3)->print();
}