esame-150302.cpp

#include <iostream>
using namespace std;

template <typename H> class MultiList {
    public:
    virtual MultiList<H>* ins(H x) = 0;
    virtual int multiplicity(H x) = 0;
    virtual void print() = 0;
};

template <typename H> class Node
{
    private:
        H key;
        Node<H> *next, *prev;
        int mul;
    public:
        Node(H x)
        {
            key = x;
            mul = 1;
            next = prev = NULL;
        }
        H getKey(){ return key; }
        int getMul(){ return mul; }
        Node<H>* getNext() { return next; }
        Node<H>* getPrev() { return prev; }
        void setNext(Node<H>* next) { this->next = next; }
        void setPrev(Node<H>* prev) { this->prev = prev; }
        void incMul(){ mul++; }
        void decMul(){ mul--; }
};

template <typename H> class MyMultiList: public MultiList<H>
{
    private:
        Node<H> *head, *tail;

        Node<H>* isBigger(H x){
            Node<H> *temp = head;
            while(temp){
                if( temp->getKey() > x )
                    return temp->getPrev();
                temp = temp->getNext();
            }
            return tail;
        }

    public:
        MyMultiList(){
            head = tail = NULL;
        }
        bool isEmpty(){
            if(!head)
                return true;
            return false;
        }
        MyMultiList<H>* ins(H x){
            if(isEmpty()){
                Node<H>* temp = new Node<H>(x);
                head = tail = temp;
                return this;
            }
            Node<H> *p = isBigger(x);
            if(p == NULL){
                Node<H>* temp = new Node<H>(x);
                temp->setNext(head);
                head->setPrev(temp);
                head = temp;
                return this;
            }
            if(p && p!=tail){
                if(p->getKey() == x){
                    p->incMul();
                    return this;
                }
                Node<H>* temp = new Node<H>(x);
                temp->setNext(p->getNext());
                p->getNext()->setPrev(temp);
                p->setNext(temp);
                temp->setPrev(p);
                return this;
            }
            if(p->getKey() == x){
                p->incMul();
                return this;
            }
            Node<H>* temp = new Node<H>(x);
            tail->setNext(temp);
            temp->setPrev(tail);
            tail = temp;
            return this; // è___é
        }
        Node<H>* search(H x){
            if(isEmpty()){
                cout << "Lista Vuota!" << endl;
                return NULL;
            }
            Node<H> *temp = head;
            while(temp){
                if(temp->getKey() == x)
                    return temp;
                temp = temp->getNext();
            }
            return NULL;
        }
        int rank(H x){
            if(isEmpty()){
                return 0;
            }
            if(!search(x))
                return 0;
            int i = 1;
            Node<H> *temp = head;
            while(temp->getKey() != x){
                i += temp->getMul();
                temp = temp->getNext();
            }
            return i;
        }
        MyMultiList<H>* del(H x){
            if(isEmpty()){
                cout << "Lista Vuota!" << endl;
                return this;
            }
            if(!search(x)){
                cout << "Elemento Inesistente " << x << endl;
                return this;
            }
            Node<H>* temp = search(x);
            if(temp->getMul() > 1){
                temp->decMul();
                return this;
            }
            if(temp == head){
                head = head->getNext();
                head->setPrev(NULL);
                delete(temp);
                return this;
            }
            if( temp == tail ){
                tail = tail->getPrev();
                tail->setNext(NULL);
                delete(temp);
                return this;
            }
            temp->getPrev()->setNext(temp->getNext());
            temp->getNext()->setPrev(temp->getPrev());
            temp->setPrev(NULL);
            temp->setNext(NULL);
            delete(temp);
            return this;
        }

        int multiplicity(H x){
            if(!search(x))
                return 0;
            return search(x)->getMul();
        }
        void print(){
            if(isEmpty()){
                cout << "Lista Vuota!" << endl;
                return;
            }
            Node<H> *temp = head;
            while(temp){
                for(int i = 0 ; i < temp->getMul() ; i++){
                    cout << temp->getKey();
                    if(temp->getNext() != NULL || i < temp->getMul()-1)
                        cout  << ",";
                }
                temp = temp->getNext();
            }
            cout << endl;
        }

};

int main(){
    MyMultiList<int> *T = new MyMultiList<int>();
    T->ins(10)->ins(5)->ins(8)->ins(3)->ins(5)->ins(1)->ins(6)->ins(5)->ins(8)->ins(1)->ins(12)->ins(7);
    T->print();
    T->del(6)->del(5)->del(8)->del(3)->del(8);
    T->print();
    cout << T->rank(5) << " " << T->rank(6) << " " << T->rank(12) << endl;
    return 0;
}