---

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

using namespace std;

template <typename ItemType>
class Base_List;

template <typename ItemType>
ostream& operator<<(ostream& os, const Base_List<ItemType>& list);

template <typename ItemType>
class Base_List {
protected:
    int list_size;

public:
    Base_List() {
        list_size = 0;
    }

    virtual ~Base_List() {}

    int size() const {
        return list_size;
    }

    bool empty() const {
        return list_size == 0;
    }

    virtual const ItemType& operator[](const int index) const = 0;

    virtual Base_List<ItemType>& add_elem(const ItemType& It) = 0;

    virtual Base_List<ItemType>& swap_nodes(const int& first, const int& second) = 0;

    virtual Base_List<ItemType>& remove_by_value(const ItemType& value) = 0;

    virtual Base_List<ItemType>& remove_by_index(const int& a) = 0;

    template <typename U>
    friend ostream& operator<<(ostream& os, const Base_List<U>& list);
};

template <typename ItemType>
ostream& operator<<(ostream& os, const Base_List<ItemType>& list) {
    for (int i = 0; i < list.list_size; i++) {
        os << list[i] << " ";
    }

    return os;
}

template <typename ItemType>
class Sorted_List : public Base_List<ItemType> {
private:
    struct Node {
        ItemType data;
        Node* next;
        Node* prev;

        Node(const ItemType& value) {
            data = value;
            next = NULL;
            prev = NULL;
        }
    };

    Node* head;
    Node* tail;

    Node* get_node(const int index) const {
        if (index < 0 || index >= this->list_size) {
            cout << "Index error!" << endl;
            return NULL;
        }

        Node* current = head;

        for (int i = 0; i < index; i++) {
            current = current->next;
        }

        return current;
    }

    void delete_node(Node* node) {
        if (node == NULL) {
            return;
        }

        if (node->prev != NULL) {
            node->prev->next = node->next;
        }
        else {
            head = node->next;
        }

        if (node->next != NULL) {
            node->next->prev = node->prev;
        }
        else {
            tail = node->prev;
        }

        delete node;
        this->list_size--;
    }

public:
    Sorted_List() {
        head = NULL;
        tail = NULL;
        this->list_size = 0;
    }

    ~Sorted_List() {
        while (head != NULL) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }

        tail = NULL;
        this->list_size = 0;
    }

    const ItemType& operator[](const int index) const {
        Node* node = get_node(index);
        return node->data;
    }

    Base_List<ItemType>& add_elem(const ItemType& It) {
        Node* new_node = new Node(It);

        if (head == NULL) {
            head = new_node;
            tail = new_node;
        }
        else if (It >= head->data) {
            new_node->next = head;
            head->prev = new_node;
            head = new_node;
        }
        else if (It <= tail->data) {
            new_node->prev = tail;
            tail->next = new_node;
            tail = new_node;
        }
        else {
            Node* current = head;

            while (current != NULL && current->data > It) {
                current = current->next;
            }

            new_node->next = current;
            new_node->prev = current->prev;

            current->prev->next = new_node;
            current->prev = new_node;
        }

        this->list_size++;
        return *this;
    }

    Base_List<ItemType>& swap_nodes(const int& first, const int& second) {
        if (first == second) {
            return *this;
        }

        int a = first;
        int b = second;

        if (a > b) {
            int temp_index = a;
            a = b;
            b = temp_index;
        }

        Node* A = get_node(a);
        Node* B = get_node(b);

        if (A == NULL || B == NULL) {
            return *this;
        }

        if (A->next == B) {
            Node* beforeA = A->prev;
            Node* afterB = B->next;

            if (beforeA != NULL) {
                beforeA->next = B;
            }
            else {
                head = B;
            }

            if (afterB != NULL) {
                afterB->prev = A;
            }
            else {
                tail = A;
            }

            B->prev = beforeA;
            B->next = A;

            A->prev = B;
            A->next = afterB;
        }
        else {
            Node* beforeA = A->prev;
            Node* afterA = A->next;

            Node* beforeB = B->prev;
            Node* afterB = B->next;

            if (beforeA != NULL) {
                beforeA->next = B;
            }
            else {
                head = B;
            }

            if (afterA != NULL) {
                afterA->prev = B;
            }
            else {
                tail = B;
            }

            if (beforeB != NULL) {
                beforeB->next = A;
            }
            else {
                head = A;
            }

            if (afterB != NULL) {
                afterB->prev = A;
            }
            else {
                tail = A;
            }

            A->prev = beforeB;
            A->next = afterB;

            B->prev = beforeA;
            B->next = afterA;
        }

        return *this;
    }

    Base_List<ItemType>& remove_by_value(const ItemType& value) {
        Node* current = head;

        while (current != NULL) {
            if (current->data == value) {
                delete_node(current);
                return *this;
            }

            current = current->next;
        }

        return *this;
    }

    Base_List<ItemType>& remove_by_index(const int& a) {
        Node* node = get_node(a);

        if (node != NULL) {
            delete_node(node);
        }

        return *this;
    }
};

int main() {
    Sorted_List<int> list;

    list.add_elem(5);
    list.add_elem(10);
    list.add_elem(3);
    list.add_elem(7);
    list.add_elem(1);
    list.add_elem(15);

    cout << "Sorted list: " << list << endl;
    cout << "list[2] = " << list[2] << endl;

    list.remove_by_value(7);
    cout << "After remove value 7: " << list << endl;

    list.remove_by_index(1);
    cout << "After remove index 1: " << list << endl;

    list.swap_nodes(0, 2);
    cout << "After swap index 0 and 2: " << list << endl;

    Sorted_List<char> letters;

    letters.add_elem('b');
    letters.add_elem('z');
    letters.add_elem('a');
    letters.add_elem('k');

    cout << "Char list: " << letters << endl;

    return 0;
}