//Lista dwukierunkowa
//Emil Hotkowski
//www.algorytm.org

#include <iostream>
using namespace std;

//Deklaracja klasy listy dwukierunkowej
class lista{
      public:
             class ogniwo{
                   public:
                   ogniwo * next;
                   ogniwo * prev;
                   int value;
                   };
             class interator{
                   public:
                   ogniwo * wsk;
                   interator next(interator it);
                   };
             lista(int v);
             void wyswietl();
             interator poczatek;
             interator koniec;
             interator insert_list(interator it, int v);
             interator delete_list(interator it);
             interator begin();
             interator end();
             interator get(int v);
             int size;
      
      
      };
      
//Przyklad uzycia      
int main(int argc, char *argv[])
{
     //uwtorz liste z elementem o wartosci 2
     lista L(2);
     
     //pobierz wskaznik na pierwszy element listy
     lista::interator it = L.begin();
    
     //wstaw element 3, za pierwszym elementem
     L.insert_list(it,3);
    
     //przesun wskaznik na kolejny element
     it = it.next(it);

     //wstaw element o wartosci 8, za elementem o wartosci 3 
     L.insert_list(it,8);
     
     //wstaw element o wartosci 12, za elementem o wartosci 3     
     L.insert_list(it,12);
    
     //wyswietl zawartosc listy
     L.wyswietl();    
     cout << "\n";
     
     //pobierz wskaznik na element o wartosci 8
     it = L.get(8);
     cout << it.wsk->value << "\n";
     
     //usun element o wartosci 8 z listy
     L.delete_list(it);
     
     //wyswietl zawartosc listy
     L.wyswietl();
     cout << "\n";

     system("PAUSE");
     return EXIT_SUCCESS;
}


//***************
// METODY
//***************

//Konstruktor listy
//tworzy nowa liste dwukierunkowa z jednym elementem o zadanej wartosci v
lista::lista(int v){
     ogniwo * a= new ogniwo;
     a->next = a;
     a->prev = a;
     a->value = v;
     poczatek.wsk = a;
     koniec.wsk = a;
     size = 1;
}

//Wstawia nowy element do listy dwukierunkowej
//Element ma wartosc v i jest wstawiany za elementem wskazywanym przez iterator it
lista::interator lista::insert_list(interator it, int v){
     ogniwo * a = it.wsk;
     ogniwo * b = new ogniwo;
     ogniwo * c = a->next;
     b->next = c;
     b->prev = a;
     b->value = v;
     c->prev = b;
     a->next = b;
     if(b->next == b)koniec.wsk = b; //popraw koniec listy, jezeli dodajemy za ostatnim elementem
     size++;
     return it;
}

//Usuwa z listy dwukierunkowej element wskazywany przez iteroator it
lista::interator lista::delete_list(interator it){
     ogniwo * b = it.wsk;
     ogniwo * a = b->prev;
     ogniwo * c = b->next;
     a->next = c;
     c->prev = a;
     if(poczatek.wsk == b) poczatek.wsk = c; //popraw poczatek listy, jezeli usuwamy pierwszy element
     if(koniec.wsk == b) koniec.wsk = a;     //popraw koniec listy, jezeli usuwamy ostatni element
     delete b;
     it.wsk =a;
     size--;
     return it;
}

//Zwraca poczatek listy dwukierunkowej
lista::interator lista::begin(){
     return poczatek;
}
          
//Zwraca koniec listy dwukierunkowej
lista::interator lista::end(){
     return koniec;
}

//Wyswietla zwartosc listy dwukierunkowej
void lista::wyswietl(){
     interator it = poczatek;
     for(int i = 0 ; i < size ; i++){
          cout << it.wsk->value << " ";
          it.wsk = it.wsk->next;
     }
}      
         
//Zwraca wskaznik na kolejny element w liscie dwukierunkowej
lista::interator lista::interator::next(interator it){
     it.wsk = it.wsk->next;
     return it;
}  
     
//Zwraca wskaznik na element o zadanej wartosci v
lista::interator lista::get(int v){
     interator it = poczatek;
     for(int i = 0 ; i < size; i++){
          int x = it.wsk->value;
          if(x ==v) break;       
          else it.wsk = it.wsk->next;
     }
     return it;
}