// main.cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "lista.hpp"

using namespace std;

int main()
{
    Lista<int> lista;

    for(unsigned i = 0; i < 20; ++i)
        lista.dodaj_porzadkowo(rand());
    lista.wypisz();

    return 0;
}

// lista.hpp
#include <iostream>

using namespace std;

template <class T>
struct element_listy
{
    T wartosc;
    element_listy* next;
    element_listy* prev;
};

template <class T>
class Lista
{
    element_listy<T>* head;
    element_listy<T>* last;
    unsigned rozmiar;
public:
    Lista();
    ~Lista();
    unsigned size() const
    {
        return rozmiar;
    }
    void dodaj_na_koniec(T);
    void dodaj_na_poczatek(T);
    void clear();
    int szukaj(T);
    void usun_element(unsigned);
    void usun_pierwszy();
    void usun_ostatni();
    void wypisz();
    void szukaj_i_usun(T);
    bool zmien_wartosc(T, unsigned);
    bool dodaj_na_pozycje(T, unsigned);
    void dodaj_porzadkowo(T);
};

template <class T>
Lista<T>::Lista() : head(nullptr), rozmiar(0) {}

template <class T>
Lista<T>::~Lista()
{
    element_listy<T>* temp;
    element_listy<T>* pretemp=nullptr;

    while (head)
    {
        temp = head;

        // przechodzimy na koniec listy:
        while (temp->next)
        {
            pretemp = temp;
            temp = temp->next;
        }
        delete temp;
        pretemp->next = nullptr;

        if (pretemp == head)     // zostaje ostatni element
        {
            delete head;
            head = nullptr;
            cout << "Usunieto element\n";
        }
        cout << "Usunieto element\n";
    }
    cout << "Koniec destruktora\n";
}

template <class T>
void Lista<T>::dodaj_na_koniec(T value)
{
    element_listy<T>* nowy = new element_listy<T>;
    nowy->wartosc = value;
    nowy->next = nullptr;

    // pierwszy element listy:
    if (head == nullptr)
    {
        head = nowy;
        head->prev = nullptr;
        last = head;
        cout << "dodano wartosc " << head->wartosc << endl;
    }

    else
    {
        element_listy<T>* temp = head;
        while (temp->next)
            temp = temp->next;

        nowy->prev = temp;
        temp->next = nowy;
        cout << "dodano wartosc " << temp->next->wartosc << endl;
        last = nowy;
    }

    ++rozmiar;
}

template <class T>
void Lista<T>::clear()
{
    element_listy<T>* temp;
    element_listy<T>* pretemp = nullptr;;

    while (head)
    {
        temp = head;

        // przechodzimy na koniec listy:
        while (temp->next)
        {
            pretemp = temp;
            temp = temp->next;
        }
        delete temp;
        pretemp->next = nullptr;

        if (pretemp == head)     // zostaje ostatni element
        {
            delete head;
            head = nullptr;
        }
    }
    rozmiar = 0;
}

template <class T>
int Lista<T>::szukaj(T value)
{

    if (head->wartosc == value)
        return 0;

    element_listy<T>* temp = head->next;

    if (temp)
        for (int i = 1; i < rozmiar; ++i)
        {
            if (temp->wartosc == value)
                return i;
            temp = temp->next;
        }
    else
    {
        return -1;
    }
}

template <class T>
void Lista<T>::usun_element(unsigned nr)
{
    if (nr == 0)
    {
        element_listy<T>* temp = head->next;
        delete head;
        head = temp;
        --rozmiar;

    }

    // kasowanie ostatniego
    else if (nr == rozmiar - 1)
    {
        element_listy<T>* kasowany = head;
        for (unsigned i = 0; i < nr; ++i)
            kasowany = kasowany->next;

        element_listy<T>* temp_prev = kasowany->prev;


        temp_prev->next = nullptr;          // zmiana


        delete kasowany;
        --rozmiar;
    }
    else
    {
        element_listy<T>* kasowany = head;
        for (unsigned i = 0; i < nr; ++i)
            kasowany = kasowany->next;

        element_listy<T>* temp_next = kasowany->next;
        element_listy<T>* temp_prev = kasowany->prev;

        temp_prev->next = temp_next;
        temp_next->prev = temp_prev;

        delete kasowany;
        --rozmiar;
    }
}


template<class T>
void Lista<T>::usun_pierwszy()
{
    usun_element(0);
}

template<class T>
void Lista<T>::usun_ostatni()
{
    usun_element(rozmiar - 1);
}


template <class T>
void Lista<T>::wypisz()
{
    cout << "Rozmiar listy: " << rozmiar << endl;
    cout << "Adresy komorek i dane:\n";

    element_listy<T>* temp = head;

    for (unsigned i = 0; i < rozmiar; ++i)
    {
        cout << '\t' << i << ": " << temp << '\t' << temp->wartosc;
        if(i > 0)
            cout << '\t' << "poprzedni: " << temp->prev;
        cout << endl;
        temp = temp->next;
    }
}

template <class T>
void Lista<T>::szukaj_i_usun(T value)
{
    int x = szukaj(value);
    usun_element(x);
}

template <class T>
bool Lista<T>::zmien_wartosc(T value, unsigned nr)
{
    if(nr >= rozmiar)
        return false;

    if(nr == 0)
    {
        head->wartosc = value;
        return true;
    }

    element_listy<T>* temp = head;
    for(unsigned i = 0; i < nr; ++i)
        temp = temp->next;

    temp->wartosc = value;
    return true;
}

template <class T>
void Lista<T>::dodaj_na_poczatek(T value)
{
    if(rozmiar == 0)
    {
        dodaj_na_koniec(value);
        return;
    }

    element_listy<T>* nowy = new element_listy<T>;
    nowy->wartosc = value;

    element_listy<T>* temp = head;
    head = nowy;
    head->prev = nullptr;
    head->next = temp;
    head->next->prev = head;

    ++rozmiar;
}

template <class T>
bool Lista<T>::dodaj_na_pozycje(T value, unsigned nr)
{
    if(nr > rozmiar) return false;
    if(nr == rozmiar)
    {
        dodaj_na_koniec(value);
        return true;
    }

    if(nr == 0)
    {
        dodaj_na_poczatek(value);
        return true;
    }

    element_listy<T>* temp = head;

    for(unsigned i = 0; i < nr; ++i)
        temp = temp->next;

    element_listy<T>* temp_prev = temp->prev;
    element_listy<T>* temp_next = temp;


    element_listy<T>* nowy = new element_listy<T>;
    nowy->wartosc = value;
    nowy->next = temp_next;
    nowy->prev = temp_prev;

    temp_prev->next = nowy;
    temp_next->prev = nowy;
    ++rozmiar;
    return true;
}

template <class T>
int abs(T a, T b)
{
    if(a >= b)
        return a - b;
    return b - a;
}

template <class T>
void Lista<T>::dodaj_porzadkowo(T value)
{
    if(rozmiar == 0)
    {
        dodaj_na_koniec(value);
        return;
    }

    unsigned pozycja = 0;
    T porownanie = head->wartosc;
    T best_value = abs(value, head->wartosc);

    element_listy<T>* temp = head->next;

    for(unsigned i = 1; i < rozmiar; ++i)
    {
        if(abs(value, temp->wartosc) < best_value)
        {
            best_value = abs(value, temp->wartosc);
            porownanie = temp->wartosc;
            pozycja = i;
        }
        temp = temp->next;
    }

    if(value <= porownanie)
        dodaj_na_pozycje(value, pozycja);
    else
        dodaj_na_pozycje(value, pozycja + 1);
}