PROG2_Esame-08-04-2015

#include <iostream>
using namespace std;

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

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

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

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

    void setNext(Nodo<H>* next){
        this->next = next;
    }

    void setPrev(Nodo<H>* prev){
        this->prev = prev;
    }
};

template <class H> class MySDList : public SDList<H>{
    Nodo<H> *header, *trailer;
    Nodo<H> **array;

    Nodo<H>* _search(Nodo<H>* n){
        for(int i = 0; array[i] && i < 9; i++){
            Nodo<H>* tmp = array[i];
            while(tmp != array[i+1]){
                if(tmp->getKey() >= n->getKey()) return tmp;
                tmp = tmp->getNext();
            }
        }
        return NULL;
    }

    Nodo<H>* __search(H x){
        for(int i = 0; array[i] && i < 9; i++){
            Nodo<H>* tmp = array[i];
            while(tmp != array[i+1]){
                if(tmp->getKey() == x) return tmp;
                tmp = tmp->getNext();
            }
        }
        return NULL;
    }

    void ptrOrder(){
        Nodo<H>* tmp = header->getNext();
        int i = 0;
        while(tmp != trailer){
            while(tmp->getKey() > i*10)
                array[i++] = tmp;
            tmp = tmp->getNext();
        }
    }

public:
    MySDList(){
        trailer = new Nodo<H>(0);
        header = new Nodo<H>(0, trailer);
        trailer->setPrev(header);
        array = new Nodo<H>*[10];
        for(int i = 0; i < 10; i++) array[i] = NULL;
    }

    SDList<H>* ins(H x){
        Nodo<H> *n = new Nodo<H>(x),
                *tmp = _search(n);

        if(tmp){
            n->setNext(tmp);
            n->setPrev(tmp->getPrev());
            tmp->getPrev()->setNext(n);
            tmp->setPrev(n);
        }else{
            n->setNext(trailer);
            n->setPrev(trailer->getPrev());
            trailer->getPrev()->setNext(n);
            trailer->setPrev(n);
        }

        ptrOrder();
        return this;
    }

    MySDList<H>* del(H x){
        Nodo<H>* tmp = __search(x);
        if(tmp){
            int i = 0, j = 0;
            while(!j){
                if(array[i] == tmp){
                    j = 1;
                    array[i] = NULL;
                }else i++;
            }

            tmp->getPrev()->setNext(tmp->getNext());
            tmp->getNext()->setPrev(tmp->getPrev());
            delete tmp;



            ptrOrder();
        }
        return this;
    }

    int search(H x){
        Nodo<H>* tmp = __search(x);
        if(tmp) return 1;
        return 0;
    }

    void print(){
        Nodo<H>* tmp = header->getNext();
        while(tmp != trailer){
            cout << tmp->getKey() << " ";
            tmp = tmp->getNext();
        }
    }

    void ptrPrint(){
        for(int i = 0; array[i] && i < 10; i++)
            cout << array[i]->getKey() << " ";
        cout << endl;
    }

};

int main(){
    MySDList<int>* list = new MySDList<int>();
    list->ins(7)->ins(13)->ins(2)->ins(6)
        ->ins(9)->ins(10)->ins(21)->ins(32)->ins(4)->ins(12)->print();

    cout << endl << endl;
    cout << list->search(13) << endl;
    cout << list->search(21) << endl;
    cout << list->search(25) << endl << endl;

    list->del(7)->del(4)->del(32)->del(10)->print();

    cout << endl << endl;

    list->ptrPrint();
}