#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
#include <time.h>


using namespace std;

struct Node
{
    int i;
    double d;
    char c;
    Node* prev;
    Node* next;
};

class List
{
public:
    List()
    {
        m_head = NULL;
    }

    bool add_node(int key)
    {
        if (m_head == NULL)
        {
            Node* node = new Node();
            node->c = 'T';
            node->d = double(rand() % 1000) + double(rand() % 100) / 100.0;
            node->i = key;
            node->prev = node;
            node->next = node;

            m_head = node;
            return true;
        }
        else
        {
            if (key < m_head->i)
            {
                Node* newHead = new Node();
                newHead->c = 'T';
                newHead->d = double(rand() % 1000) + double(rand() % 100) / 100.0;
                newHead->i = key;
                newHead->prev = m_head->prev;
                newHead->next = m_head;

                m_head->prev->next = newHead;
                m_head->prev = newHead;
                m_head = newHead;
                return true;
            }
            else if (key == m_head->i)
            {
                return false;
            }
            else if (key > m_head->prev->i)
            {
                Node* newTail = new Node();
                newTail->c = 'T';
                newTail->d = double(rand() % 1000) + double(rand() % 100) / 100.0;
                newTail->i = key;
                newTail->prev = m_head->prev;
                newTail->next = m_head;

                m_head->prev->next = newTail;
                m_head->prev = newTail;
                return true;
            }
            else if (key == m_head->prev->i)
                return false;
            else
            {
                Node* actual = m_head;
                Node* tail = m_head->prev;

                while (actual != tail)
                {
                    if (actual->i == key)
                    {
                        return false;
                    }
                    else if (actual->i < key && actual->next->i > key)
                    {
                        Node* newNode = new Node();
                        newNode->c = 'T';
                        newNode->d = double(rand() % 1000) + double(rand() % 100) / 100.0;
                        newNode->i = key;
                        newNode->prev = actual;
                        newNode->next = actual->next;

                        actual->next->prev = newNode;
                        actual->next = newNode;
                        return true;
                    }
                    actual = actual->next;
                }
            }
            return false;
        }
    }

    void add_nodes(int count)
    {
        srand(time(NULL));
        while (count > 0)
        {
            int random_number = (rand() + rand() + rand()) % 99901 + 99;
            if (add_node(random_number)) count--;
        }

    }

    Node* find(int key)
    {
        if (m_head == NULL)
            return NULL;

        Node* actual = m_head;

        do {
            if (actual->i == key) return actual;
            actual = actual->next;
        } while (actual != m_head);

        return NULL;
    }

    bool erase(int key)
    {
        Node* node = find(key);
        if (node == NULL)
            return false;

        if (element_count() == 1)
        {
            m_head = NULL;
        }
        else if (node == m_head)
        {
            m_head->prev->next = node->next;
            m_head->next->prev = m_head->prev;
            m_head = node->next;
        }
        else if (node == m_head->prev)
        {
            Node* old_tail = m_head->prev;
            m_head->prev = old_tail->prev;
            old_tail->prev->next = m_head;
        }
        else
        {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }

        delete node;
        return true;
    }

    void erase_all()
    {
        while (m_head)
        {
            erase(m_head->i);
        }
    }

    int element_count()
    {
        if (m_head == NULL)
        {
            return 0;
        }
        else
        {
            int count = 0;
            Node* node = m_head;

            do {
                count++;
                node = node->next;
            } while (node != m_head);

            return count*2;
        }
    }

    int element_count2()
    {
        if (m_head == NULL)
        {
            return 0;
        }
        else
        {
            int count = 0;
            Node* node = m_head;

            do {
                count++;
                node = node->next;
            } while (node != m_head);

            return count;
        }
    }

    void show_from_start(int count)
    {
        if (count > element_count())
        {
            std::cout << "Brak wezlow w liscie!\n";
            return;
        }

        Node* actual = m_head;
        int i = 1;
        while (count > 0)
        {
            std::cout << " " << actual->i << " " << i;
            actual = actual->next;
            i++;
            count--;

        }
        std::cout << '\n';
    }

    void funkcja2(int count)
    {
        if (count > element_count2())
        {
            std::cout << "Brak wezlow w liscie!\n";
            return;
        }

        Node* actual = m_head;
        while (count > 0)
        {
            std::cout << " " << actual->i;
            actual = actual->next;
            count--;

        }
        std::cout << '\n';
    }

private:
    Node * m_head;
};

int main()
{
    char c;
    cout << "Czy rozklad kluczy ma byc losowy? [t/n] "; cin >> c;
    if (c == 't' || c == 'T')
    {
        int N;
        cout << "Podaj ilosc kluczy do wylosowania: " << endl;
        cin >> N;

        clock_t begin, end;
        double time_spent;

        begin = clock();

        List list;
        list.add_nodes(N);
        printf("%d elementow\n", list.element_count2());
    //  list.funkcja2(N);

        end = clock();

        time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
        printf("Minelo %f sekund\n", time_spent);

    }
    else
    {
        int N;
        cout << "Podaj ilosc kluczy do wylosowania: " << endl;
        cin >> N;

        clock_t begin, end;
        double time_spent;

        begin = clock();

        List list;
        list.add_nodes(N);
        printf("%d elementow\n", list.element_count());
    //  list.show_from_start(N);

        end = clock();

        time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
        printf("Minelo %f sekund\n", time_spent);
    }

    system("pause");
    return 0;
}