/*
    Intruzív láncolt lista (intrusive linked list) https://www.data-structures-in-practice.com/intrusive-linked-lists/

    Mire jó?
    ----------
    Az "intruzív" lista egy speciális láncolt lista, ahol a láncoláshoz szükséges pointerek (kovetkezo, elozo) magában a tárolt objektumban vannak elhelyezve,
    nem pedig egy külön csomo vagy wrapper struktúrában. Ez azt jelenti, hogy maga az adatobjektum ismeri a listába való tartozását, és egy objektum akár
    több különböző listának is része lehet – ehhez minden listához külön pointerpárokat kell tartani benne. (Erre STL-lel nincs lehetőség!)

    Miért találták ki?
    -------------------
    - Ha nagy mennyiségű objektummal kell dolgozni, a plusz wrapper-objektum jelentős memória- és cache-többletet jelent.
    - Gyakran használják operációs rendszerekben (Linux kernel!), játékmotorokban, vagy embedded rendszerekben, ahol a teljesítmény/memória számít,
      illetve a struktúrák élettartama bonyolultabb (pl. egy objektum egyszerre több listához is tartozik).
    - Lehetővé teszi a nagyon gyors eltávolítást, ha ismerjük a pointerét (nem kell keresni!).

    Miben más, mint az STL list?
    -----------------------------
    - STL-ben nem tud egy objektum több listában lenni (mert ott a láncolás metaadatait a list kezelője tárolja, nem az elem!).
    - Nincs extra memória-allokáció minden beszúrásnál.
    - Eltávolítás garantált O(1), ha pointerrel hivatkozunk az elemre.
*/

#include <iostream>
#include <cstddef>   // offsetof

using namespace std;

// Alap csomópont típus, amit be lehet ágyazni objektumokba.
// Egy ilyen csomópont egyetlen listában való részvételhez elég.
struct IntruzivCsomo {

    IntruzivCsomo* kovetkezo = nullptr;
    IntruzivCsomo* elozo = nullptr;
};

// Egy elem, ami akár több listában is benne lehet.
// Itt két külön "hook"-ot (csomópontot) tartalmazunk:
// - hook1: az első listához
// - hook2: a második listához
struct Adat {

    IntruzivCsomo hook1; // első lista láncolása
    IntruzivCsomo hook2; // második lista láncolása
    int ertek;

    Adat(int ertek) : ertek(ertek) {}
};

// Egy intruzív lista implementáció
struct IntruzivLista {

    IntruzivCsomo* kezdopont = nullptr;
    IntruzivCsomo* vegpont = nullptr;

    // Beszúrás a lista végére (O(1))
    void vegere_beszuras(IntruzivCsomo* csomo) {

        csomo->kovetkezo = nullptr;
        csomo->elozo = vegpont;

        if (vegpont)                        // Ha a lista nem üres (vegpont nem nullptr), akkor a jelenlegi utolsó elem kovetkezo mutatóját beállítjuk az új csomópontra.
            vegpont->kovetkezo = csomo;
        else kezdopont = csomo;             // Ha üres akkor amit beszúrtunk az a kezdőpont

        vegpont = csomo;
    }

    // Törlés bármely pozícióból (O(1)), ha ismerjük az elemet!
    void torles(IntruzivCsomo* csomo) {

        if (csomo->elozo)                               // Ha van előző elem
            csomo->elozo->kovetkezo = csomo->kovetkezo; // Az előző elem kovetkezo mutatóját átállítjuk a törlendő elem utáni elemre
        else kezdopont = csomo->kovetkezo;              // Ha nincs a kezdopont-ot átállítjuk a törlendő utáni elemre (csomo->kovetkezo).

        if (csomo->kovetkezo)                           // Ha van következő elem
            csomo->kovetkezo->elozo = csomo->elozo;     // A következő elem elozo mutatóját átállítjuk a törlendő előtti elemre (kihagyjuk a törlendő elemet a láncból)
        else vegpont = csomo->elozo;                    // Ha a törlendő elem az utolsó a listában,  a vegpont-ot átállítjuk a törlendő előtti elemre

        csomo->kovetkezo = csomo->elozo = nullptr;
    }

    // Példa: Az STL-lel ilyet nem lehet!
    // Ugyanazt az objektumot (Adat b) több különböző listába is betehetjük,
    // ha minden listához külön kovetkezo/elozo pointert tárolunk.
    // Itt az Adat-ban két hook van (hook1 és hook2), tehát képes egyszerre két listában szerepelni.
    void print_all() {
        for (IntruzivCsomo* n = kezdopont; n; n = n->kovetkezo) {   // 1. IntruzivCsomo* n = kezdopont → a ciklus elején a n mutatót a lista első elemére (kezdopont) állítjuk.
                                                                    // 2. n; A ciklus addig fut, amíg n nem üres (amíg el nem érünk a lista végére).
                                                                    
                                                                    // Itt nem tudjuk automatikusan, melyik hookról van szó, mert az a használattól függ.
                                                                    // A felhasználónak kell tudnia, hogy pl. ez a lista az Adat hook1-jét vagy hook2-jét kezeli.
                                                                    // Ezért itt csak memóriacím alapján (static_cast) kaphatjuk vissza az Adat-ot.

            auto* d = reinterpret_cast<Adat*>(
                reinterpret_cast<char*>(n) - offsetof(Adat, hook1) // ha ez a lista hook1-et kezeli
                );                                                 // offsetof(Adat, hook1) → megmondja, hány bájttal az Adat eleje után kezdődik a hook1 tag.
            cout << d->ertek << " ";                               // reinterpret_cast<char*>(n) → a n címet byte pointerré alakítjuk, hogy bájtban lehessen vele számolni.
        }                                                          // visszalépünk pont annyit, amennyi a hook1 eltolása az Adat elejétől. Így megkapjuk az Adat báziscímét.
        cout << '\n';                                              // A külső reinterpret_cast<Adat*> pedig visszaalakítja az így kapott báziscímet Adat*-tá.

     }                                                             // Az intruzív listában nem a lista birtokolja a node-ot, hanem az objektum (itt Adat) tartalmazza a node-ot (hookot).
                                                                   //  Iteráláskor a listától csak a hook pointerét kapjuk. Ha az objektum többi adatára (pl. ertek)
};                                                                 //  is kíváncsiak vagyunk, akkor a hook címéből vissza kell következtetni a gazdaobjektum (Adat) elejére
                                                                   //  → ezt csinálja a fenti számítás.

                                                                   // Miért reinterpret_cast, és miért nem static_cast?
                                                                   // static_cast nem végezhet ilyen nyers címmanipulációt.
                                                                   // Itt szándékos, kontrollált pointeraritmetikát végzünk(byte szintű levonás), ezért kell a reinterpret_cast
    
                                                                   // Ha ugyanazzal a print_all()-lal akarod többféle hookot támogatni, érdemes a listába tenni egy mezőt pl:
                                                                   // size_t hook_offset; // pl. constructorban: hook_offset = offsetof(Adat, hook1);