#include <iostream>
#include "assert.h"
using namespace std;
 
class Item;
 
class List
{
private:
    Item* first;
    Item* last;
 
public:
    Item* getFirst() { return first; }
    Item* getLast() { return last; }
 
private:
    void link(Item* before, Item* fresh, Item* after);
 
public:
    void insertFirst(Item* fresh);
    void insertLast(Item* fresh);
 
    void insertBefore(Item* target, Item* fresh);
    void insertAfter(Item* target, Item* fresh);
 
    void unlink(Item* elem);
    void remove(Item* elem);
 
    Item* find(string name0);
    Item* get(int inx);
    void print(int level = 1);
    int count();
 
    void move(List& other);
    void reverse();
 
    void add(string name0);
    void add(Item* elem);
    void sort();
 
    List();
    ~List();
};
 
class Item
{
public:
    string name;
    List data;
 
private:
    Item* prev;
    Item* next;
    // List* up;
 
public:
    Item* getPrev() { return prev; }
    Item* getNext() { return next; }
 
    Item(string name0);
 
    friend class List;
};
 
List::List() :
    first(nullptr),
    last(nullptr)
{
}
 
List :: ~List()
{
    while (first != nullptr)
    {
        remove(first);
    }
}
 
Item::Item(string name0) :
    name(name0),
    prev(nullptr),
    next(nullptr)
{
}
 
void List::link(Item* before, Item* fresh, Item* after)
// a - seznam do ktereho vkladame
// fresh - nove vkladany prvek (musi existovat, nesmi byt v zadnem seznamu)
// before - ukazatel na predchozi prvek ( before == nullptr => fresh bude prvni)
// after - ukazatel na nasledujici prvek ( after == nullptr => fresh bude posledni)
{
    fresh->prev = before;
    fresh->next = after;
 
    if (before != nullptr)
        before->next = fresh; // nekdo je pred
    else
        first = fresh; // jsme prvni
 
    if (after != nullptr)
        after->prev = fresh;
    else
        last = fresh;
}
 
void List::insertFirst(Item* fresh)
{
    link(nullptr, fresh, first);
}
 
void List::insertLast(Item* fresh)
{
    link(last, fresh, nullptr);
}
 
void List::insertBefore(Item* target, Item* fresh)
{
    assert(target != nullptr);
    // assert(target->up == this);
    link(target->prev, fresh, target);
}
 
void List::insertAfter(Item* target, Item* fresh)
{
    assert(target != nullptr);
    link(target, fresh, target->next);
}
 
void List::unlink(Item* elem)
{
    if (elem != nullptr)
    {
        Item* before = elem->prev;
        Item* after = elem->next;
 
        if (before != nullptr)
            before->next = after;
        else
            first = after;
 
        if (after != nullptr)
            after->prev = before;
        else
            last = before;
 
        elem->prev = nullptr;
        elem->next = nullptr;
    }
}
 
void List::remove(Item* elem)
{
    if (elem != nullptr)
    {
        unlink(elem);
        delete elem;
    }
}
 
Item* List::get(int inx) // inx == 0, prvni prvek
{
    Item* p = first;
    while (inx > 0 && p != nullptr) {
        inx--;
        p = p->next;
    }
    return p;
}
 
 
void List::move(List& other)
// a.move (b); ... presunout prvky ze seznamu b do seznamu a
{
    while (other.first != nullptr)
    {
        Item* a = other.first;
        other.unlink(other.first);
        insertLast(a);
    }
}
 
void List::reverse()
{
    List other;
    other.move(*this);
    while (other.first != nullptr)
    {
        Item* a = other.first;
        other.unlink(other.first);
        insertFirst(a);
    }
 
    /*
    Item* p = other.first;
    while (p != nullptr)
    {
        Item * t = p->next;
        other.unlink(p);
        insertFirst (p);
        p = t;
    }
    */
}
 
/*
void List::add(string name0)
{
    Item* p = first;
    while (p != nullptr && p->name <= name0) p = p->next;
    if (p == nullptr)
        insertLast(new Item(name0));
    else
        insertBefore(p, new Item(name0));
}
*/
 
void List::add(string name0)
{
    Item* p = new Item(name0);
    add(p);
}
 
void List::add(Item* elem)
{
    Item* p = first;
    while (p != nullptr && p->name <= elem->name) p = p->next;
    if (p == nullptr)
        insertLast(elem);
    else
        insertBefore(p, elem);
}
 
void List::sort()
{
    List other;
    other.move(*this);
 
    Item* p = other.first;
    while (p != nullptr)
    {
        Item* t = p->next;
        other.unlink(p);
        add(p);
        p = t;
    }
 
    /*
    Item* p = other.first;
    while (p != nullptr)
    {
        add (p->name);
        p = p->next;
    }
    */
}
 
void List::print(int level)
{
    Item* p = first;
 
    while (p != nullptr)
    {
        for (int i = 1; i <= level; i++)
            cout << "---";
        cout << p->name << endl;
        p->data.print(level+1);
        p = p->next;
    }
    //cout << endl;
}
 
Item* List::find(string name0)
{
    Item* result = nullptr;
    Item* p = first;
    while (result == nullptr && p != nullptr)
    {
        if (p->name == name0)
            result = p;
        if (result == nullptr)
            result = p->data.find (name0);
        p = p->next;
    }
    return result;
}
 
int List::count()
{
    int result = 0;
    Item* p = first;
    while (p != nullptr)
    {
        result ++;
        result += p->data.count();
        p = p->next;
    }
    return result;
}
 
List savci; // trida
 
int main()
{
    Item* selmy = new Item("selmy"); // rad
    selmy->data.add("kockovite"); // celed
    selmy->data.getFirst()->data.add("tigr"); // druh
 
    savci.add(selmy);
    savci.add("lichokopytnici");
    savci.add("sudokopytnici");
    savci.add("kytovci");
 
    savci.find("lichokopytnici")->data.add("tapiroviti");
    savci.find("tapiroviti")->data.add("tapir");
 
    selmy->data.add("psovite");
    selmy->data.find("psovite")->data.add("vlk"); 
 
    savci.print();
    //selmy->data.print();
    //selmy->data.getFirst()->data.print();
    cout << savci.count();
}