#include <iostream>
#include <functional>
#include <cstdlib>
#include <ctime>
#include <cstring>

template <typename Type> struct ListElement {
    ListElement <Type>* next;
    Type value;

    ListElement() {
        next = NULL;
    }

    ListElement(Type _value) {
        next = NULL;
        value = _value;
    }
};

template <typename Type> struct List {
    ListElement <Type>* head;
    ListElement <Type>* tail;
    unsigned int length;

    List() {
        length = 0;
        // limiter
        head = tail = new ListElement <Type>();
    }

    ~List() {
        ListElement <Type>* curr = head;

        while(length + 1 != 0) {
            ListElement <Type>* deleted = curr;

            curr = curr->next;

            length--;
        }
    }

    void push(Type value) {
        tail->next = new ListElement <Type>(value);
        tail = tail->next;
        length++;
    }

    Type pop() {
        if(length == 0) {
            throw "List is empty";
        }

        Type returned = tail->value;

        ListElement <Type>* new_tail = head;

        while (new_tail->next != tail) {
            new_tail = new_tail->next;
        }

        tail = new_tail;
        tail->next = NULL;

        length--;

        delete tail->next;
        return returned;
    }

    void unshift(Type value) {
        ListElement <Type>* new_el = new ListElement <Type>(value);
        new_el->next = head->next;
        head->next = new_el;
        length++;
    }

    Type shift() {
        if(length == 0) {
            throw "List is empty";
        }

        ListElement <Type>* deleted = head->next;

        Type returned = deleted->value;

        head->next = deleted->next;

        length--;

        delete deleted;
        return returned;
    }

    void insert(unsigned int index, Type value) {
        if(index > length) {
            throw "Can't insert to such index";
        }

        ListElement <Type>* before = head;

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

        ListElement <Type>* inserted = new ListElement <Type>(value);

        inserted->next = before->next;
        before->next = inserted;

        if(index == length) {
            tail = inserted;
        }

        length++;
    }

    Type remove(unsigned int index) {
        if(index >= length) {
            throw "Can't remove such index";
        }

        ListElement <Type>* before = head;

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

        ListElement <Type>* deleted = before->next;

        before->next = deleted->next;

        Type returned = deleted->value;

        if(index == length - 1) {
            tail = before;
        }

        length--;

        delete deleted;
        return returned;
    }

    int find(Type value) {
        int index = 0;
        bool found = false;
        ListElement <Type>* current = head->next;

        while(current) {
            if(current->value == value) {
                found = true;
                break;
            }

            index++;
            current = current->next;
        }

        if(!found)
            index = -1;

        return index;
    }

    void forEach(std::function <void (Type, unsigned int)> func) {
        int index = 0;
        ListElement <Type>* current = head->next;

        while(current) {
            func(current->value, index);

            index++;
            current = current->next;
        }
    }

    friend std::ostream& operator<< (std::ostream& out, List<Type> list) {
        out << "[ ";

        list.forEach([&out, list](Type value, unsigned int i) {
            out << value << ((i < list.length - 1) ? ", " : " ");
        });

        out << "]";

        return out;
    }
};

int main() {
    srand(time(NULL));

    List <char> list;

    for(int i = 0; i < 10; i++)
        list.push(rand() % ('Z' - 'A') + 'A');


    std::cout << "Available commands:\n"
              << "  print\n"
              << "  push [X]\n"
              << "  pop\n"
              << "  unshift [X]\n"
              << "  shift\n"
              << "  insert [i] [X]\n"
              << "  remove [i]\n"
              << "  find X\n"
              << "  custom\n"
              << "  exit\n"

              << "\nInitial list: " << list

              << "\n\n> ";

    while(1) {
        char command[64];

        std::cin >> command;

        try {
            if(strcmp(command, "print") == 0) {
                std::cout << list;
            }
            else if(strcmp(command, "push") == 0) {
                char p;
                std::cin >> p;
                list.push(p);
            } else if(strcmp(command, "pop") == 0) {
                std::cout << list.pop();
            } else if(strcmp(command, "unshift") == 0) {
                char p;
                std::cin >> p;
                list.unshift(p);
            } else if(strcmp(command, "shift") == 0) {
                std::cout << list.shift();
            } else if(strcmp(command, "insert") == 0) {
                char p;
                int i;
                std::cin >> i >> p;
                list.insert(i, p);
            } else if(strcmp(command, "remove") == 0) {
                int i;
                std::cin >> i;
                std::cout << list.remove(i);
            } else if(strcmp(command, "find") == 0) {
                char p;
                std::cin >> p;
                std::cout << list.find(p);
            } else if(strcmp(command, "custom") == 0) {
                std::cout << "\nGreater than 'D':\n";
                list.forEach([](char c, int i) {
                    if(c > 'D')
                        std::cout << i << ": " << c << std::endl;
                });
            } else if(strcmp(command, "exit") == 0) {
                return 0;
            } else {
                std::cout << "Unknown command";
            }
        } catch(const char* err) {
            std::cout << err;
        }

        std::cout << "\n> ";
    }

    return 0;
}