#include "stdafx.h"
#include "stdint.h"
#include <iostream>

template <typename T>
class linked_list_node
{
public:
    linked_list_node* previous;
    linked_list_node* next;
    T value;

    linked_list_node(T v, linked_list_node* prev)
    {
        value = v;
        if (prev != nullptr)
        {
            previous = prev;
            previous->next = this;
        }
    }
};

template <typename T>
class double_linked_list
{
public:
    linked_list_node<T>* first;
    linked_list_node<T>* last;

    double_linked_list()
    {
        first = nullptr;
        last = nullptr;
    }

    void add(T val)
    {
        if (first == nullptr)
        {
            first = new linked_list_node<T>(val, nullptr);
            last = first;
        }
        else
            last = new linked_list_node<T>(val, last);
    }

    void add_in_order(T val)
    {
        if (first == nullptr)
        {
            first = new linked_list_node<T>(val, nullptr);
            last = first;
        }
        else
        {
            linked_list_node<T>* current = first;
            while (current->next != nullptr && current->next->value < val)
            {
                current = current->next;
            }
            if (current->next == nullptr)
            {
                current->next = new linked_list_node<T>(val, current);
                last = current->next;
            }
            else
            {
                linked_list_node<T>* next = current->next;
                current->next->previous = new linked_list_node<T>(val, current);
                current->next->previous->next = next;
                current->next = current->next->previous;
            }
        }
    }

    bool check_order()
    {
        linked_list_node<T>* current = first;
        while (current != nullptr)
        {
            if (current != first && current->value < current->previous->value)
                return false;
            current = current->next;
        }
        return true;
    }
};

int main()
{
    std::cout << "Unsorted list:\n";
    auto unsorted_list = new double_linked_list<int>();
    unsorted_list->add(0);
    unsorted_list->add(13);
    unsorted_list->add(9);
    unsorted_list->add(255);
    unsorted_list->add(3);

    auto ucurrent = unsorted_list->first;
    while (ucurrent != nullptr)
    {
        std::cout << ucurrent->value << " ";
        ucurrent = ucurrent->next;
    }

    std::cout << "\n" << (unsorted_list->check_order() ? "Sorted" : "Not sorted") << "\n\n";

    std::cout << "Sorted list:\n";
    auto sorted_list = new double_linked_list<int>();
    sorted_list->add_in_order(0);
    sorted_list->add_in_order(13);
    sorted_list->add_in_order(9);
    sorted_list->add_in_order(255);
    sorted_list->add_in_order(3);

    auto scurrent = sorted_list->first;
    while (scurrent != nullptr)
    {
        std::cout << scurrent->value << " ";
        scurrent = scurrent->next;
    }

    std::cout << "\n" << (sorted_list->check_order() ? "Sorted" : "Not sorted") << "\n\n";
}