★ /prog/ challenge No. 666 ★ (Easy)

THE CHALLENGE:
Implement ``Tohosort'' (http://www.freewebs.com/tohosort/) ^{66in Lisp99} in your programming language of choice.

Post the source code of your implementation. It should at least read the input from stdin and print a sorted list after making the comparisons.

Deadline: 2013-01-21 00:00.

The programs will be judged by elegance, speed and number of comparisons made using a random list that will be published the day of the deadline. The winner will be awarded with Ten (10) שקליםSuss (that's Suss-shekels for you goyim), which is enough to pay the fee needed to cross the Sanzu River by ferry.

Splitting into four posts since it was too large and I don't know the max post length.
#include <ctype.h>
#include <locale.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define    PC98        0xf8000000
#define HRtP        0x80000000
#define STG        0x7fff0000
#define PC98_STG    0x78000000
#define SoEW        0x40000000
#define LLS        0x20000000
#define MS        0x10000000
#define PHANTASMAGORIA    0x0c000000
#define PoDD        0x08000000
#define WINDOWS     0x07fff000
#define WINDOWS_STG    0x07ff0000
#define PoFV        0x04000000
#define EoSD        0x02000000
#define PCB        0x01000000
#define IN        0x00800000
#define MoF        0x00400000
#define SA        0x00200000
#define UFO        0x00100000
#define FW        0x00080000
#define TD        0x00040000
#define AYA_GAMES    0x00030000
#define StB        0x00020000
#define DS        0x00010000
#define FIGHTER        0x0000f000
#define IaMP        0x00008000
#define SWR        0x00004000
#define SOKU        0x00002000
#define HM        0X00001000
#define MUSIC        0x00000e00
#define ZUN_MUSIC_COL    0x00000c00
#define DiPP        0x00000800
#define GFC        0x00000400
#define AUS        0x00000200
#define PRINT_WORKS    0x000001ff
#define COMICS        0x000001f4
#define KOURINDOU    0x00000100
#define MOON_WORKS    0x00000080
#define FAIRY_WORKS    0x00000040
#define WaHH        0x00000020
#define FS        0x00000010
#define LORE        0x0000000f
#define BAiJR        0x00000008
#define PMiSS        0x00000004
#define GoM        0x00000002
#define SoPM        0x00000001
#define REIMU        0xfffdfbff
#define MARI        0x7ffdfbff
#define PATCHY        0x07a2f0fe
#define REMI        0x07c2d0df
#define AYA        0x046b41ef
#define YUKARI        0x01a2d1fe
#define PADS        0x0782f0de
#define YUYU        0x0586c0ef
#define YOUMU        0x0586c1cf
#define ALICE        0x11a260fe
#define CIRNO        0x070a20ef
#define SUIKA        0x0023c0fe
#define RAN        0x0182d0de
#define CHEN        RAN
#define SUWAKO        0x007120e3
#define KANAKO        SUWAKO
#define SANAE        0x007520a3
#define NITORI        0x006100f3
#define FLANDRE        0x028200de
#define TEI        0x048200de
#define HONG        0x0202a0ce
#define EIRIN        0x048240ce
#define UDONGE        EIRIN
#define KOMACHI        0x040240f6
#define LUNA        0x000811fc
#define MYSTIA        0x048000e7
#define NAZRIN        0x00111073
#define OKUU        0x00312063
#define NUE        0x00151071
#define STAR        0x000811dc
#define SUNNY        STAR
#define LILY        0x050c10c4
#define AKI        0x004100d3
#define HINA        AKI
#define KUMOI        0x00911071
#define KEINE        0x008200ce
#define WRIGGLE        KEINE
#define MOKOU        KEINE
#define KAGUYA        KEINE
#define LETTY        0x010200ce
#define RUMIA        0x020200ce
#define PRISM        0x0500108e
#define YUUKA        0x3c0008c4
#define KISUME        0x00210053
#define TENSHI        0x00014063
#define YUUGI        0x00210063
#define PARSEE        YUUGI
#define KOMEIJI        YUUGI
#define MURASA        0x00111061
#define KOGASA        0x00150061
#define YAMA        0x040200c6
#define MIMA        0xd8000a00
#define ORIN        0x00210043
#define YAMAME        ORIN
#define SHOU        0x00110061
#define MOMIJI        0x00410061
#define UNZAN        0x00111041
#define MEDI        0x04020086
#define IKU        0x00014003
#define SEIGA        0x00040031
#define YOSHIKA        SEIGA
#define MAMIZOU        SEIGA
#define HATATE        0x00010061
#define HIJIRI        0x00110041
#define GENJI        PC98_STG
#define SHANGHAI    0x01008000
#define AKYU        0x00000205
#define FUTO        0x00040011
#define KYOUKO        0x00040021
#define RINNOSUKE    0x0000010c
#define DAICHAN        0x02080040
#define MIKO        0x00040001
#define TOJIKO        MIKO
#define KASEN        0x00000060
#define KOA        0x02000040
#define HOURAI        0x0180c000
#define AYA_CROW    0x08004000
#define EVIL_EYE    0x60000000
#define FAIRY_MAID    0x020011c0
#define BAKEBAKE    0x78000040
#define HAIRBALL    0x03c00000
#define ZOMBIE_FAIRY    0x00210002
#define SUNFLOWER_FAIRY    0x04780000

typedef struct th th;
struct th {
    unsigned char _;
#define UNKNOWN     0x01
    const uint32_t app;
    const char *const name;
    th *tie;
    th *win;
    th *pre;
};

typedef struct {
    th *btm;
    th *top;
} thls;

#define _2HU(x,y)   {0,x,y}
#define NHU(x,y)    _2HU(x,"Nameless "y)
#define UHU(x,y)    _2HU(x,"Unnamed "y)
#define NM(x,y)     NHU(x,"Midboss "y)
#define PHU(x)      _2HU(PRISM,x" Prismriver")
#define KHU(x)      _2HU(KOMEIJI,x" Komeiji")
#define MHU(x)      _2HU(MOON_WORKS,x)
#define WHU(x)      MHU("Watatsuki no "x)
#define _PoDD(x)    _2HU(PoDD,x)
#define _MS(x)      _2HU(MS,x)
#define _LLS(x)     _2HU(LLS,x)
#define _SoEW(x)    _2HU(SoEW,x)
#define _HRtP(x)    _2HU(HRtP,x)
#define _GFC(x)     _2HU(GFC,x)
#define _AKI(x)     _2HU(AKI,x" Aki")

static th ths[] =
{
    _2HU(REIMU, "Reimu Hakurei"),    _2HU(MARI, "Marisa Kirisame"),
    _2HU(PATCHY, "Patchouli Knowledge"),
    _2HU(REMI, "Remilia Scarlet"),    _2HU(AYA, "Aya Shameimaru"),
    _2HU(YUKARI, "Yukari Yakumo"),    _2HU(PADS, "Sakuya Izayoi"),
    _2HU(YUYU, "Yuyuko Saigyouji"),    _2HU(YOUMU, "Youmu Konpaku"),
    _2HU(ALICE, "Alice Margatroid"),
    _2HU(CIRNO, "Cirno"),
    _2HU(SUIKA, "Suika Ibuki"),    _2HU(RAN, "Ran Yakumo"),
    _2HU(CHEN, "Chen"),        _2HU(SUWAKO, "Suwako Moriya"),
    _2HU(KANAKO, "Kanako Yasaka"),    _2HU(SANAE, "Sanae Kochiya"),
    _2HU(NITORI, "Nitori Kawashiro"),
    _2HU(FLANDRE, "Flandre Scarlet"),
    _2HU(TEI, "Inaba Tei"),        _2HU(HONG, "Hong Meiling"),
    _2HU(EIRIN, "Eirin Yagokoro"),    _2HU(UDONGE, "Reisen Udongein Inaba"),
    _2HU(KOMACHI, "Komachi Onozuka"),
    _2HU(LUNA, "Luna Child"),
    _2HU(MYSTIA, "Mystia Lorelei"),    _2HU(NAZRIN, "Nazrin"),
    _2HU(OKUU, "Utsuho Reiuji"),    _2HU(NUE, "Nue Houjuu"),
    _2HU(STAR, "Star Sapphire"),    _2HU(SUNNY, "Sunny Milk"),
    _2HU(LILY, "Lily White"),    _AKI("Shizuha"),
    _AKI("Minoriko"),        _2HU(HINA, "Hina Kagiyama"),
    _2HU(KUMOI, "Ichirin Kumoi"),    _2HU(WRIGGLE, "Wriggle Nightbug"),
    _2HU(MOKOU, "Fujiwara no Mokou"),
    _2HU(KAGUYA, "Kaguya Houraisan"),
    _2HU(KEINE, "Keine Kamishirasawa"),
    _2HU(LETTY, "Letty Whiterock"),    _2HU(RUMIA, "Rumia"),
    PHU("Lunasa"),            PHU("Lyrica"),
    PHU("Merlin"),            _2HU(YUUKA, "Yuuka Kazami"),
    _2HU(KISUME, "Kisume"),        _2HU(TENSHI, "Tenshi Hinanawi"),
    _2HU(PARSEE, "Parsee Mizuhashi"),
    _2HU(YUUGI, "Yuugi Hoshiguma"),    KHU("Satori"), KHU("Koishi"),
    _2HU(MURASA, "Minamitsu Murasa"),
    _2HU(KOGASA, "Kogasa Tatara"),    _2HU(YAMA, "Eiki Shiki Yamaxanadu"),
    _2HU(MIMA, "Mima"),        _2HU(YAMAME, "Yamame Kurodani"),
    _2HU(ORIN, "Rin Kaenbyou"),    _2HU(SHOU, "Shou Toramaru"),
    _2HU(MOMIJI, "Momiji Inubashiri"),
    _2HU(UNZAN, "Unzan"),        _2HU(MEDI, "Medicine Melancholy"),
    _2HU(IKU, "Iku Nagae"),        _2HU(YOSHIKA, "Yoshika Miyako"),
    _2HU(SEIGA, "Seiga Kaku"),    _2HU(MAMIZOU, "Mamizou Futatsuiwa"),
    _2HU(HATATE, "Hatate Himekaidou"),
    _2HU(HIJIRI, "Byakuren Hijiri"),
    _2HU(GENJI, "Genji"),        _2HU(SHANGHAI, "Shanghai"),
    _2HU(AKYU, "Hieda no Akyu"),    _2HU(FUTO, "Mononobe no Futo"),
    _2HU(KYOUKO, "Kyouko Kasodani"),
    _2HU(RINNOSUKE, "Rinnosuke Morichika"),
    _2HU(DAICHAN, "Daiyousei"),    _2HU(TOJIKO, "Soga no Tojiko"),
    _2HU(MIKO, "Toyosatomimi no Miko"),
    _2HU(KASEN, "Ibara Kasen"),    _2HU(KOA, "Koakuma"),
    _2HU(HOURAI, "Hourai"),        _2HU(SOKU, "Goliath Doll"),
    _2HU(FS, "Kosuzu Motoori"),    MHU("Reisen 2"),
    WHU("Toyohime"),        WHU("Yorihime"),
    _PoDD("Ellen"),            _PoDD("Kotohime"),
    _PoDD("Kana"),            _PoDD("Rikako"),
    _PoDD("Chiyuri"),        _PoDD("Yumemi"),
    _PoDD("Ruukoto"),        _MS("Sara"),
    _MS("Louise"),            _MS("Yuki"),
    _MS("Mai"),            _MS("Yumeko"),
    _MS("Shinki"),            _LLS("Orange"),
    _LLS("Kurumi"),            _LLS("Elly"),
    _LLS("Mugetsu"),        _LLS("Gengetsu"),
    _SoEW("Rika"),            _SoEW("Flower Tank"),
    _SoEW("Evil Eye Sigma"),    _SoEW("Meira"),
    _HRtP("Shingyoku"),        _HRtP("Yuugen Magan"),
    _HRtP("Elis"),            _HRtP("Sariel"),
    _HRtP("Kikuri"),        _HRtP("Konngara"),
    _GFC("Renko Usami"),        _GFC("Maribel Hearn"),
    _2HU(EoSD, "Rin Satsuki"),    _2HU(KOURINDOU, "`Tokiko'"),
    NM(SoEW, "Tank"),        _SoEW("`Noroiko'"),
    NM(SoEW, "Magic Things"),    NM(SoEW, "Angel"),
    NHU(LLS, "Flower"),        _LLS("Magic Mirror (Demon)"),
    _MS("Magic Mirror (Angel)"),    NM(LLS, "Ball of light"),
    NM(MS, "Card"),            NM(TD, "Divine Spirit"),
    NM(LLS, "Fairy(?)"),        NM(MS, "Demon"),
    UHU(DiPP, "girl on DiPP Jacket"),
    UHU(WaHH, "Dragon"),        _2HU(PMiSS, "Dragon God"),
    /* stage chara */
    _2HU(FAIRY_MAID, "Fairy Maid"),    _2HU(EVIL_EYE, "Evil Eye"),
    _SoEW("Five Magic Stones"),    _2HU(HAIRBALL, "Hairball"),
    _PoDD("Hoshizako"),        _2HU(BAKEBAKE, "Bakebake"),
    _2HU(SUNFLOWER_FAIRY, "Sunflower Fairy"),
    _2HU(ZOMBIE_FAIRY, "Zombie Fairy"),
    /* weapons chara */
    _PoDD("Mimi-chan"),
    /* animals */
    _2HU(SOKU, "Giant Catfish"),    _2HU(BAiJR, "Giant Toad"),
    _2HU(WaHH, "Unnamed Dapeng"),    _2HU(MOON_WORKS, "Sake bug"),
    /* pets */
    _2HU(AYA_CROW, "Aya's Crow"),    _MS("Alice's Cat"),
    _PoDD("Sokrates"),        _2HU(FAIRY_WORKS, "Tsuchinoko"),
    UHU(WaHH, "Raijuu"),        _2HU(WaHH, "Kanda"),
    _2HU(WaHH, "Kume")
};

static thls ls;
static size_t thlen = (sizeof(ths) / sizeof(th));

#define SETB(x, b)  (x |= b)
#define ISB(x, b)   (x & b)
#define ISU(x)      ISB(x->_, UNKNOWN)

static __inline int
select_(void)
{
    int selection = 0;
    int i = scanf("%d", &selection);
    if(i == 1) return selection;
    else if(i == EOF)  printf("scanf eofuk'd; no 2hus for you\n"), abort();
    return -1;
}

#define NEWL(e)    ls.btm = e, ls.top = e

static __inline void
pushb(th *t)
{
    if(ls.btm != NULL) t->pre = ls.top, ls.top = t;
    else NEWL(t);
}

static __inline void
pushf(th *t)
{
    if(ls.btm != NULL) ls.btm->pre = t, ls.btm = t;
    else NEWL(t);
}

#define WIN_(w,l)   w->win = l
#define TIE_(t,x)   t->tie = x

static __inline void
addt(th **a, th *b)
{
    th *t = (*a);
    for(; t->tie != NULL; t = t->tie);
    TIE_(t, b), b->win = NULL;
}

static __inline void
pushu(th *t)
{
    if(ls.btm != NULL)
    {
        if(ISU(ls.btm)) addt(&ls.btm, t);
    }
    else SETB(t->_, UNKNOWN), pushf(t);
}


#define USTR        "\n0 - Both are unknown"
#define THSTR        "\n1 - %s\n2 - %s"
#define TIESTR        "\n3 - Tie"
#define U2STR        "\n4 - Don't know %s\n5 - Don't know %s\n"

#define PRIN2HU(x,y)    printf(THSTR TIESTR "\n:", x->name, y->name)
#define PRINTUHU(x,y)    printf(USTR THSTR TIESTR U2STR ":",\
                x->name, y->name, x->name, y->name)

static void
dicksort(void)
{
    th *n1, *n2, *pw;
    if(ISU(ls.top)) return;
    while((ls.top->pre != NULL) && !ISU(ls.top->pre))
    {
        pw = NULL, n1 = ls.top, n2 = n1->pre;
        ls.top->pre = n2->pre, n2->pre = NULL;
    INNERLOOP:
        PRIN2HU(n1, n2);
        switch(select_()) {
        case 1:
            pw = n1;
            n1 = n1->win;
            if(!n1)
            {
                WIN_(pw, n2);
                continue;
            }
            goto INNERLOOP;
        case 2:
        {
            th *ne = n2->win;
            if(n1 == ls.top)
            {
                n2->pre = ls.top->pre;
                ls.top->pre = NULL;
                ls.top = n2;
            }
            else
                pw->win = n2;
            WIN_(n2, n1);
            if(ne == NULL)
                continue;
            pw = n2;
            n2 = ne;
            goto INNERLOOP;
        }
        case 3:
        {
            th *ne = n2->win, *te = n1->win;
            addt(&n1, n2);
            pw = n1;
            n1 = te, n2 = ne;
            if(n1 == NULL && n2 == NULL)
                continue;
            else if(n1 == NULL)
            {
                pw->win = n2;
                continue;
            }
            else if(n2 == NULL)
            {
                pw->win = n1;
                continue;
            }
            else
                goto INNERLOOP;
        }
        default:
            goto INNERLOOP;
        }
    }
}

static void
list(th *th1, th *th2)
{
    while(1)
    {
        PRINTUHU(th1, th2);
        switch(select_()) {
        case 0: TIE_(th1, th2); pushu(th1); return;
        case 1: WIN_(th1, th2); pushb(th1); return;
        case 2: WIN_(th2, th1); pushb(th2); return;
        case 3: TIE_(th1, th2); pushb(th1); return;
        case 4: pushu(th1);    pushb(th2); return;
        case 5: pushu(th2);    pushb(th1); return;
        default: continue;
        }
    }
}

#define FOPT "Filter options:\n"
#define FR1  "\t 0 - ALL\t 1 - HRtP\t 2 - SoEW\t 3 - PoDD\n"
#define FR2  "\t 4 - LLS\t 5 - MS\t\t 6 - EoSD\t 7 - PCB\n"
#define FR3  "\t 8 - IN\t\t 9 - PoFV\t10 - MoF\t11 - SA\n"
#define FR4  "\t12 - UFO\t13 - TD\t\t14 - StB\t15 - DS\n"
#define FR5  "\t16 - FW\t\t17 - IaMP\t18 - SWR\t19 - SOKU\n"
#define FR6  "\t20 - HM\t\t21 - PC98\t22 - STG\t23 - PC98 STG\n"
#define FR7  "\t24 - PHANTASM\t25 - Windows\t26 - WIN STG\t27 - Fighter\n"
#define FR8  "\t28 - Aya games\n\t29 - Music\t30 - DiPP\t31 - GFC\n"
#define FR9  "\t32 - ZUN music\t33 - Akyu Untouched\n\t34 - Print\t35 - Manga\n"
#define FR10 "\t36 - Kourindou\t37 - Bougetsu\t38 - Sangetsu\t39 - Ibarakasen\n"
#define FR11 "\t40 - Suzunaan\t41 - Lore\t42 - BAiJR/SDV\t43 - PMiSS\n"
#define FR12 "\t44 - Grimoire\t45 - Symposium\n"
#define FDOPT "default: ALL\n:"
#define FOPSTR FOPT FR1 FR2 FR3 FR4 FR5 FR6 FR7 FR8 FR9 FR10 FR11 FR12 FDOPT

static uint32_t
getbits(void)
{
    uint32_t i, ret;
    char buf[3], c;
    buf[2] = 0, i = 0, ret = 0;
    printf(FOPSTR);
    while((c = getc(stdin)) != EOF)
    {
        if(isdigit(c))
        {
            if(i > 1) printf("2 digits motherfucker!\n"), abort();
            buf[i++] = c;
        }
        else if(isspace(c))
        {
            switch(atoi(buf)) {
            case 1: SETB(ret, HRtP);        break;
            case 2: SETB(ret, SoEW);        break;
            case 3: SETB(ret, PoDD);        break;
            case 4: SETB(ret, LLS);            break;
            case 5: SETB(ret, MS);            break;
            case 6: SETB(ret, EoSD);        break;
            case 7: SETB(ret, PCB);            break;
            case 8: SETB(ret, IN);            break;
            case 9: SETB(ret, PoFV);        break;
            case 10: SETB(ret, MoF);        break;
            case 11: SETB(ret, SA);            break;
            case 12: SETB(ret, UFO);        break;
            case 13: SETB(ret, TD);            break;
            case 14: SETB(ret, StB);        break;
            case 15: SETB(ret, DS);            break;
            case 16: SETB(ret, FW);            break;
            case 17: SETB(ret, IaMP);        break;
            case 18: SETB(ret, SWR);        break;
            case 19: SETB(ret, SOKU);        break;
            case 20: SETB(ret, HM);            break;
            case 21: SETB(ret, PC98);        break;
            case 22: SETB(ret, STG);        break;
            case 23: SETB(ret, PC98_STG);        break;
            case 24: SETB(ret, PHANTASMAGORIA);    break;
            case 25: SETB(ret, WINDOWS);        break;
            case 26: SETB(ret, WINDOWS_STG);    break;
            case 27: SETB(ret, FIGHTER);        break;
            case 28: SETB(ret, AYA_GAMES);        break;
            case 29: SETB(ret, MUSIC);        break;
            case 30: SETB(ret, DiPP);        break;
            case 31: SETB(ret, GFC);        break;
            case 32: SETB(ret, ZUN_MUSIC_COL);    break;
            case 33: SETB(ret, AUS);        break;
            case 34: SETB(ret, PRINT_WORKS);    break;
            case 35: SETB(ret, COMICS);        break;
            case 36: SETB(ret, KOURINDOU);        break;
            case 37: SETB(ret, MOON_WORKS);        break;
            case 38: SETB(ret, FAIRY_WORKS);    break;
            case 39: SETB(ret, WaHH);        break;
            case 40: SETB(ret, FS);            break;
            case 41: SETB(ret, LORE);        break;
            case 42: SETB(ret, BAiJR);        break;
            case 43: SETB(ret, PMiSS);        break;
            case 44: SETB(ret, GoM);        break;
            case 45: SETB(ret, SoPM);        break;
            default: return 0;
            }
            buf[0] = 0;
            buf[1] = 0;
            i = 0;
            if(c == '\n') break;
        }
        else return 0;
    }
    return ret;
}

static __inline void
printties(th *t, int i)
{
    while(t != NULL) printf("%3d: %s\n", i, t->name), t = t->tie;
}

#define PRINTSLW(t,i)    printf("%3d: %s\n", i, t->name)

static void
printls(void)
{
    printf("\n\n+++\n");
    th *l, *t;
    int i;
    for(i = 1, l = ls.top , t = l ;t != NULL; l = l->pre, t = l)
    {
        if(ISU(t))
        {
            printties(t, -1);
            break;
        }
        else
        {
            while(t != NULL)
            {
                if(t->tie != NULL) printties(t, i);
                else PRINTSLW(t,i);
                t = t->win;
                i++;
            }
        }
    }
    printf("+++\n\n");
}

#define APPLY_FILTER_INNER(flt,t,i)\
for(;i < thlen;)\
{\
    if(ISB(ths[i].app, flt))\
    {\
        list(t, &ths[i++]);\
        t = NULL;\
        break;\
    }\
    else i++;\
}

#define APPLY_FILTER(flt)    \
th * t;\
int i;\
for(i = 0; i< thlen;)\
{\
    if(ISB(ths[i].app, flt))\
    {\
        t = &ths[i++];\
        APPLY_FILTER_INNER(flt,t,i);\
    }\
    else i++;\
}\
if(t != NULL) pushb(t);\

int
main(void)
{
    setlocale(LC_ALL, "C");
    uint32_t flt;
    flt = getbits();
    if(flt)
    {
        APPLY_FILTER(flt);
    }
    else
    {
        int i = 0, j = 1;
        for(; i < thlen && j < thlen; i += 2, j += 2)
            list(&ths[j], &ths[i]);
        if(j == thlen) pushb(&ths[i]);
    }
    dicksort();
    printls();
    return EXIT_SUCCESS;
}