ListG.inl

/*
 * utils/ListG.inl
 * Generating List.
 * List: A double circular linked list.
 */

#ifndef LISTG_TNAME
#   error LISTG_TNAME not defined.
#endif // ifndef LISTG_TNAME

#ifndef LISTG_ETYPE
#   error LISTG_ETYPE not defined.
#endif // ifndef LISTG_ETYPE

#undef LIST_NAME
#undef LIST_ELEM
#undef LIST_TSTRUCT
#undef LIST_P
#undef LIST_CP
#undef LIST_ISTRUCT
#undef LIST_I
#undef LIST_CI
#undef LIST_EP
#undef LIST_ECP
#undef LIST_ECTR
#undef LIST_EDTR
#undef LIST_EASR
#undef LIST_F

#define LIST_NAME LISTG_TNAME
#define LIST_ELEM LISTG_ETYPE

#define LIST_TSTRUCT CONCAT3(T, LIST_NAME, _)
#define LIST_P TWNP(LIST_NAME)
#define LIST_CP TWNCP(LIST_NAME)
#define LIST_ISTRUCT CONCAT3(TI, LIST_NAME, _)
#define LIST_I TWNI(LIST_NAME)
#define LIST_CI TWNCI(LIST_NAME)

#define LIST_EP TWNP(LIST_ELEM)
#define LIST_ECP TWNCP(LIST_ELEM)
#define LIST_ECTR CONCAT(LIST_ELEM, Create)
#define LIST_EDTR CONCAT(LIST_ELEM, Destroy)
#define LIST_EASR CONCAT(LIST_ELEM, Ass)

#define LIST_F(name_) CONCAT(LIST_NAME, name_)

// Type: P, CP.

TWDPCP(struct LIST_TSTRUCT, LIST_NAME)

// Iterator: I, CI.

TWDICI(struct LIST_ISTRUCT, LIST_NAME)

// Class: Create, Destroy.

LIST_P   LIST_F(Create) (void);
TVoid    LIST_F(Destroy)(LIST_P ptr);

// Class: Swap, Ass.

TVoid    LIST_F(Swap)    ( LIST_P ptr, LIST_P rhs);
TVoid    LIST_F(Ass)     ( LIST_P ptr, LIST_CP rhs);

// Container: Empty, Size, Clear.

TBool    LIST_F(Empty)   (LIST_CP ptr);
TSize    LIST_F(Size)    (LIST_CP ptr);
TVoid    LIST_F(Clear)   ( LIST_P ptr);

// Container: Front, FrontC, CFront, Back, BackC, CBack.

LIST_EP  LIST_F(Front)   ( LIST_P ptr);
LIST_ECP LIST_F(FrontC)  ( LIST_P ptr);
LIST_ECP LIST_F(CFront)  (LIST_CP ptr);
LIST_EP  LIST_F(Back)    ( LIST_P ptr);
LIST_ECP LIST_F(BackC)   ( LIST_P ptr);
LIST_ECP LIST_F(CBack)   (LIST_CP ptr);

// Container: EmplaceF, EmplaceB, PushF, PushB, PopF, PopB.

TVoid    LIST_F(EmplaceF)( LIST_P ptr, LIST_EP obj);
TVoid    LIST_F(EmplaceB)( LIST_P ptr, LIST_EP obj);
TVoid    LIST_F(PushF)   ( LIST_P ptr, LIST_ECP obj);
TVoid    LIST_F(PushB)   ( LIST_P ptr, LIST_ECP obj);
TVoid    LIST_F(PopF)    ( LIST_P ptr);
TVoid    LIST_F(PopB)    ( LIST_P ptr);

// Container: Emplace, Insert, Erase.

LIST_I   LIST_F(Emplace) ( LIST_P ptr, LIST_I itr, LIST_EP obj);
LIST_I   LIST_F(Insert)  ( LIST_P ptr, LIST_I itr, LIST_ECP obj);
LIST_I   LIST_F(Erase)   ( LIST_P ptr, LIST_I itr);

// Container: Begin, BeginC, CBegin, End, EndC, CEnd.

LIST_I   LIST_F(Begin)   ( LIST_P ptr);
LIST_CI  LIST_F(BeginC)  ( LIST_P ptr);
LIST_CI  LIST_F(CBegin)  (LIST_CP ptr);
LIST_I   LIST_F(End)     ( LIST_P ptr);
LIST_CI  LIST_F(EndC)    ( LIST_P ptr);
LIST_CI  LIST_F(CEnd)    (LIST_CP ptr);

// Iterator: Next, NextC, Prev, PrevC.

LIST_I   LIST_F(Next)    ( LIST_I itr);
LIST_CI  LIST_F(NextC)   (LIST_CI itr);
LIST_I   LIST_F(Prev)    ( LIST_I itr);
LIST_CI  LIST_F(PrevC)   (LIST_CI itr);

// Iterator: Data, DataC.

LIST_EP  LIST_F(Data)    ( LIST_I itr);
LIST_ECP LIST_F(DataC)   (LIST_CI itr);

// Container: Sort.

TVoid    LIST_F(Sort)    ( LIST_P ptr, TBool (*cmp)(LIST_ECP, LIST_ECP));

// Implementation:

#ifdef LISTG_IMPLEMENT

#undef LIST_TT
#undef LIST_TI

#define LIST_TT TWNT(LIST_NAME)
#define LIST_TI TWNT(LIST_I)

TWDT(struct LIST_TSTRUCT, LIST_NAME)
TWDT(struct LIST_ISTRUCT, LIST_I)

struct LIST_ISTRUCT {
    LIST_EP x_data;
    LIST_I  x_next;
    LIST_I  x_prev;
};

struct LIST_TSTRUCT {
    TSize   x_size;
    LIST_TI x_nil;
};

static inline LIST_I X_ICMove(LIST_EP obj) {
    LIST_I itr = MAlloc(LIST_I, MSize(LIST_TI));
    itr->x_data = obj;
    return itr;
}

static inline LIST_I X_ICCopy(LIST_ECP obj) {
    LIST_I itr = MAlloc(LIST_I, MSize(LIST_TI));
    itr->x_data = LIST_ECTR();
    LIST_EASR(itr->x_data, obj);
    return itr;
}

static inline TVoid X_IDestroy(LIST_I itr) {
    LIST_EDTR(itr->x_data);
    MFree(itr);
}

static inline TVoid X_ILink(LIST_I lhs, LIST_I rhs) {
    lhs->x_next = rhs;
    rhs->x_prev = lhs;
}

static inline TVoid X_Ctor(LIST_P ptr) {
    ptr->x_size = 0U;
    ptr->x_nil.x_next = ptr->x_nil.x_prev = &ptr->x_nil;
    ptr->x_nil.x_data = NULL;
}

static inline TVoid X_Dtor(LIST_P ptr) {
    for (LIST_I i = ptr->x_nil.x_next; i != &ptr->x_nil; ) {
        LIST_I p = i;
        i = i->x_next;
        X_IDestroy(p);
    }
}

TVoid LIST_F(Swap)(LIST_P ptr, LIST_P rhs) {
    MSwap(&ptr, &rhs, MSize(LIST_TT));
}

TVoid LIST_F(Ass)(LIST_P ptr, LIST_CP rhs) {
    while (ptr->x_size > rhs->x_size)
        LIST_F(PopB)(ptr);
    while (ptr->x_size < rhs->x_size)
        LIST_F(EmplaceB)(ptr, LIST_ECTR());
    LIST_I  i = ptr->x_nil.x_next;
    LIST_CI j = rhs->x_nil.x_next;
    while (i != &ptr->x_nil) {
        LIST_EASR(i->x_data, j->x_data);
        i = i->x_next;
        j = j->x_next;
    }
}

TBool LIST_F(Empty)(LIST_CP ptr) {
    return !ptr->x_size;
}

TSize LIST_F(Size)(LIST_CP ptr) {
    return ptr->x_size;
}

TVoid LIST_F(Clear)(LIST_P ptr) {
    X_Dtor(ptr);
    X_Ctor(ptr);
}

LIST_EP LIST_F(Front)(LIST_P ptr) {
    return ptr->x_nil.x_next->x_data;
}

LIST_ECP LIST_F(FrontC)(LIST_P ptr) {
    return ptr->x_nil.x_next->x_data;
}

LIST_ECP LIST_F(CFront)(LIST_CP ptr) {
    return ptr->x_nil.x_next->x_data;
}

LIST_EP LIST_F(Back)(LIST_P ptr) {
    return ptr->x_nil.x_prev->x_data;
}

LIST_ECP LIST_F(BackC)(LIST_P ptr) {
    return ptr->x_nil.x_prev->x_data;
}

LIST_ECP LIST_F(CBack)(LIST_CP ptr) {
    return ptr->x_nil.x_prev->x_data;
}

TVoid LIST_F(EmplaceF)(LIST_P ptr, LIST_EP obj) {
    LIST_I i = X_ICMove(obj);
    X_ILink(i, ptr->x_nil.x_next);
    X_ILink(&ptr->x_nil, i);
    ++ptr->x_size;
}

TVoid LIST_F(EmplaceB)(LIST_P ptr, LIST_EP obj) {
    LIST_I i = X_ICMove(obj);
    X_ILink(ptr->x_nil.x_prev, i);
    X_ILink(i, &ptr->x_nil);
    ++ptr->x_size;
}

TVoid LIST_F(PushF)(LIST_P ptr, LIST_ECP obj) {
    LIST_I i = X_ICCopy(obj);
    X_ILink(i, ptr->x_nil.x_next);
    X_ILink(&ptr->x_nil, i);
    ++ptr->x_size;
}

TVoid LIST_F(PushB)(LIST_P ptr, LIST_ECP obj) {
    LIST_I i = X_ICCopy(obj);
    X_ILink(ptr->x_nil.x_prev, i);
    X_ILink(i, &ptr->x_nil);
    ++ptr->x_size;
}

TVoid LIST_F(PopF)(LIST_P ptr) {
    LIST_I i = ptr->x_nil.x_next;
    X_ILink(&ptr->x_nil, i->x_next);
    X_IDestroy(i);
    --ptr->x_size;
}
TVoid LIST_F(PopB)(LIST_P ptr) {
    LIST_I i = ptr->x_nil.x_prev;
    X_ILink(i->x_prev, &ptr->x_nil);
    X_IDestroy(i);
    --ptr->x_size;
}

LIST_I LIST_F(Emplace)(LIST_P ptr, LIST_I itr, LIST_EP obj) {
    LIST_I i = X_ICMove(obj);
    X_ILink(i, itr->x_next);
    X_ILink(itr, i);
    ++ptr->x_size;
    return i;
}

LIST_I LIST_F(Insert)(LIST_P ptr, LIST_I itr, LIST_ECP obj) {
    LIST_I i = X_ICCopy(obj);
    X_ILink(i, itr->x_next);
    X_ILink(itr, i);
    ++ptr->x_size;
    return i;
}

LIST_I LIST_F(Erase)(LIST_P ptr, LIST_I itr) {
    LIST_I i = itr->x_next;
    X_ILink(itr->x_prev, i);
    X_IDestroy(itr);
    --ptr->x_size;
    return i;
}

LIST_I LIST_F(Begin)(LIST_P ptr) {
    return ptr->x_nil.x_next;
}

LIST_CI LIST_F(BeginC)(LIST_P ptr) {
    return ptr->x_nil.x_next;
}

LIST_CI LIST_F(CBegin)(LIST_CP ptr) {
    return ptr->x_nil.x_next;
}

LIST_I LIST_F(End)(LIST_P ptr) {
    return &ptr->x_nil;
}

LIST_CI LIST_F(EndC)(LIST_P ptr) {
    return &ptr->x_nil;
}

LIST_CI LIST_F(CEnd)(LIST_CP ptr) {
    return &ptr->x_nil;
}

LIST_I LIST_F(Next)(LIST_I itr) {
    return itr->x_next;
}

LIST_CI LIST_F(NextC)(LIST_CI itr) {
    return itr->x_next;
}

LIST_I LIST_F(Prev)(LIST_I itr) {
    return itr->x_prev;
}

LIST_CI LIST_F(PrevC)(LIST_CI itr) {
    return itr->x_prev;
}

LIST_EP LIST_F(Data)(LIST_I itr) {
    return itr->x_data;
}

LIST_ECP LIST_F(DataC)(LIST_CI itr) {
    return itr->x_data;
}

static LIST_I X_Sort(LIST_I p, TSize cnt, TBool(*cmp)(LIST_ECP, LIST_ECP)) {
    if (cnt == 1) {
        p->x_next = NULL;
        return p;
    }
    LIST_I q = p;
    TSize hlf = cnt >> 1U;
    for (TSize i = 0; i < hlf; ++i)
        q = q->x_next;
    LIST_I l = X_Sort(p, hlf, cmp);
    LIST_I r = X_Sort(q, cnt - hlf, cmp);
    LIST_TI it;
    LIST_I u = &it;
    while (l || r) {
        if (!l || (r && cmp(r->x_data, l->x_data))) {
            u->x_next = r;
            u = r;
            r = r->x_next;
        }
        else {
            u->x_next = l;
            u = l;
            l = l->x_next;
        }
    }
    u->x_next = NULL;
    return it.x_next;
}

TVoid LIST_F(Sort)(LIST_P ptr, TBool(*cmp)(LIST_ECP, LIST_ECP)) {
    if (!ptr->x_size)
        return;
    LIST_I p = &ptr->x_nil;
    p->x_next = X_Sort(ptr->x_nil.x_next, ptr->x_size, cmp);
    while (p->x_next) {
        p->x_next->x_prev = p;
        p = p->x_next;
    }
    X_ILink(p, &ptr->x_nil);
}

LIST_P LIST_F(Create)(void) {
    LIST_P ptr = MAlloc(LIST_P, MSize(LIST_TT));
    X_Ctor(ptr);
    return ptr;
}

TVoid LIST_F(Destroy)(LIST_P ptr) {
    X_Dtor(ptr);
    MFree(ptr);
}

#endif // ifdef LISTG_IMPLEMENT

#undef LISTG_TNAME
#undef LISTG_ETYPE
#undef LISTG_IMPLEMENT