#include <iostream>
#include <string>
#include <cassert>
 
using namespace std;
 
class Item;
 
class List
{
public:
    Item* first;
    Item* last;
    List () : first (nullptr), last (nullptr) { }
    ~ List ();
private:
    void link(Item* before, Item* fresh, Item* after);
public:
    void insertFirst(int key0, string note0 = "");
    void insertLast(int key0, string note0 = "");
    void print();
    Item * find (int key0);
    friend class Item;
};
 
class Item
{
public:
    Item* prev;
    int key;
    string note;
    List* up;
    Item* next;
    Item(int k0, string n0 = "") : prev(nullptr), key(k0), note(n0), up (nullptr), next(nullptr) {}
    void insertBefore(int key0, string note0 = "");
    void insertAfter(int key0, string note0 = "");
    void unlink ();
};
 
void List::link(Item* before, Item* fresh, Item* after)
{
    assert(fresh != nullptr);
    assert(fresh->up == nullptr);
    fresh->up = this;
    fresh->prev = before;
    fresh->next = after;
 
    if (before != nullptr)
        before->next = fresh;
    else
        first = fresh;
 
    if (after != nullptr)
        after->prev = fresh;
    else
        last = fresh;
} 
 
void List::insertFirst(int key0, string note0) {
    Item* p = new Item(key0, note0);
    link(nullptr, p, first);
}
 
void List::insertLast(int key0, string note0) {
    Item* p = new Item(key0, note0);
    link (last, p, nullptr);
}
 
void Item::insertBefore(int key0, string note0)
{
    Item* p = new Item(key0, note0);
    up->link(prev, p, this);
}
 
void Item::insertAfter(int key0, string note0)
{
    Item* p = new Item(key0, note0);
    up->link(this, p, next);
}
 
void Item::unlink()
{
    assert (this != nullptr);
    assert (up != nullptr);
 
    Item* before = prev;
    Item* after = this->next;
 
    if (before != nullptr)
        before->next = after;
    else
        up->first = after;
 
    if (after != nullptr)
        after->prev = before;
    else
        up->last = before;
 
    up = nullptr; // na konec
    prev = nullptr;
    next = nullptr;
}
 
List :: ~ List ( )
{
    /*
    Item* p = first;
    while (p != nullptr)
    {
        Item* t = p->next;
        p->unlink();
        delete p;
        p = t;
    }
    */
 
    Item* p = first;
    while (p != nullptr)
    {
        Item* t = p->next;
        delete p;
        p = t;
    }
}
 
 
Item* List::find(int key0)
// vysledek ukazatel na nalezeny prvek nebo nullptr
{
    Item* p = first;
    while (p != nullptr && p->key != key0)
    {
        p = p->next;
    }
    return p;
}
 
void List::print()
{
    Item* p = first;
    if (p == nullptr)
        cout << "seznam je prazdny" << endl;
    while (p != nullptr)
    {
        cout << p->key << " : " << p->note << endl;
        p = p->next;
    }
}
 
int main()
{
    List a;
    a.insertLast (1, "abc");
    a.insertLast (4, "klm");
    a.first->insertAfter(2, "def");
    a.first->insertBefore(0, "aaa");
    a.last->insertBefore(3, "ghi");
    a.last->insertAfter(5, "zzz");
    a.print();
 
    Item* t = a.find(4);
    if (t != nullptr)
    {
        cout << "Nalezeno " << t->key << ":" << t->note << endl;
        t->unlink ();
        delete t;
    }
    else
        cout << "Nenalezeno" << endl;
 
    a.print();
 
    cout << "O.K.";
}