#include <iostream>
#include "assert.h"
using namespace std;
 
class Item
{
public:
    string name;
 
private:
    Item* up;
    Item* prev;
    Item* next;
    Item* first;
    Item* last;
 
public:
    Item* getUp() { return up; }
 
    Item* getPrev() { return prev; }
    Item* getNext() { return next; }
 
    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* fresh);
    void insertAfter(Item* fresh);
 
    void unlink();
 
    void add(Item* elem);
    void add(string name0);
 
    Item* find(string name0);
    void print (int level = 1);
    int count();
 
    Item(string name0 = "");
    ~Item();
};
 
Item::Item(string name0) :
    name(name0),
    up(nullptr),
    prev(nullptr),
    next(nullptr),
    first(nullptr),
    last(nullptr)
{
}
 
Item::~Item()
{
    Item * p = last;
    while (p != nullptr)
    {
        Item* t = p->prev;
        delete p;
        p = t;
    }
}
 
void Item::link(Item* before, Item* fresh, Item* after)
// this - 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)
{
    assert(fresh->up == nullptr);
    fresh->up = this;
    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 Item::insertFirst(Item* fresh)
{
    link(nullptr, fresh, first);
}
 
void Item::insertLast(Item* fresh)
{
    link(last, fresh, nullptr);
}
 
void Item::insertBefore(Item* fresh)
{
    assert(up != this);
    up->link (prev, fresh, this);
}
 
void Item::insertAfter(Item* fresh)
{
    assert(up != nullptr);
    link(this, fresh, next);
}
 
void Item::unlink()
{
    assert (up != nullptr);
    Item* before = prev;
    Item* after = next;
 
    if (before != nullptr)
        before->next = after;
    else
        up->first = after;
 
    if (after != nullptr)
        after->prev = before;
    else
        up->last = before;
 
    up = nullptr;
    prev = nullptr;
    next = nullptr;
}
 
void Item::add(Item* elem)
{
    insertLast(elem);
}
 
void Item::add(string name0)
{
    Item* p = new Item(name0);
    add(p);
}
 
void Item::print(int level)
{
    Item* p = first;
 
    while (p != nullptr)
    {
        for (int i = 1; i <= level; i++)
            cout << "---";
        cout << p->name << endl;
        p->print(level + 1);
        p = p->next;
    }
}
 
Item* Item::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->find(name0);
        p = p->next;
    }
    return result;
}
 
int Item::count()
{
    int result = 0;
    Item* p = first;
    while (p != nullptr)
    {
        result++;
        result += p->count();
        p = p->next;
    }
    return result;
}
 
void vypis(Item * list, string name0)
{
    Item* v = list->find(name0);
    while (v != nullptr)
    {
        cout << v->name << endl;
        v = v->getUp();
    }
}
 
// vypis(savci, "vlk");
 
void domain(Item* p)
{
    /*
    while (p != nullptr)
    {
        cout << p->name;
        p = p->getUp();
        if (p != nullptr) cout << ".";
    }
    */
    cout << p->name;
    if (p->getUp() != nullptr)
    {
        cout << ".";
        domain(p->getUp());
    }
}
 
// domain (savci->find ("tapir"));
// tapir.tapiroviti.lichokopytnici.savci
 
void prog(Item* p)
{
    if (p->getUp() != nullptr)
    {
        prog(p->getUp());
        cout << ".";
    }
    cout << p->name;
}
 
// prog (savci->find ("tapir"));
// savci.lichokopytnici.tapiroviti.tapir
 
int depth(Item* p)
{
    int result = 0;
    if (p != nullptr)
    {
        Item* t = p->getFirst(); // t ... podstromy
        while (t != nullptr)
        {
            int d = depth(t); // d ... hloubka podstromu
            if (d > result)
                result = d;
            t = t->getNext();
        }
        // result ... delka nejdelsiho podstromu
        result ++; // nas prvek p
    }
    return result;
}
 
#include <iostream>
#include <fstream>
void send(ostream & f, Item * list, int level = 0)
{
    for (int i = 1; i <= level; i++)
        f << "---";
 
    f << list->name << endl;
 
    Item* p = list->getFirst ();
    while (p != nullptr)
    {
        send (f, p, level + 1);
        p = p->getNext ();
    }
}
 
Item * savci = new Item ("savci"); // trida
 
int main()
{
    Item* selmy = new Item("selmy"); // rad
    selmy->add("kockovite"); // celed
    selmy->getFirst()->add("tigr"); // druh
 
    savci->add(selmy);
    savci->add("lichokopytnici");
    savci->add("sudokopytnici");
    savci->add("kytovci");
 
    savci->find("lichokopytnici")->add("tapiroviti");
    savci->find("tapiroviti")->add("tapir");
 
    selmy->add("psovite");
    selmy->find("psovite")->add("vlk");
 
    savci->print();
    cout << savci->count() << endl;
    cout << endl;
 
    vypis (savci, "vlk");
    cout << endl;
    domain(savci->find("tapir"));
    cout << endl;
    prog(savci->find("tapir"));
    cout << endl;
 
    cout << depth(savci) << endl;
    cout << depth(savci->find ("tigr")) << endl;
 
    send(cout, savci, 1);
    ofstream g ("abc.txt");
    send(g, savci);
    g.close ();
 
    delete savci;
}