単連結リストの整列 #19 複数のデータの組み合わせを整列する

これまでは単一のデータを保持しているものを要素とするリストを整列した。
複数のデータからなる要素の場合について行ってみる。

#include <stdio.h>
#include "lsort.h"

#define UNUSED_ARG(x) (void)(x)

typedef struct tag_phys_node pnode_t;
struct tag_phys_node {
    pnode_t *next;
    unsigned int id;
    unsigned int height;
    unsigned int weight;
};

static int sup(const void *xx, const void *yy, void *arg)
{
    pnode_t *x = (pnode_t *)xx, *y = (pnode_t *)yy;
    UNUSED_ARG(arg);
    if (x->height == y->height) {
        if (x->weight == y->weight) {
            return x->id > y->id;
        }
        return x->weight > y->weight;
    }
    return x->height > y->height;
}

static void print(pnode_t *node, char *s)
{
    pnode_t *p;
    if (s != NULL) puts(s);
    for (p = node; p != NULL; p = p->next) {
        printf("[id=%u, height=%u, weight=%u]\n", p->id, p->height, p->weight);
    }
}

int main(void)
{
    int i;
    pnode_t p[] = {
        {NULL, 1, 166, 53}, {NULL, 2, 157, 48}, {NULL, 3, 160, 53},
        {NULL, 4, 157, 47}, {NULL, 5, 161, 50}, {NULL, 6, 160, 53},
        {NULL, 0, 0, 0}
    }, *q, *node = p;
    for (i = 0, q = p; (++q)->id != 0; i++) p[i].next = q;
    print(node, "pre-sort");
    lsort(&node, sup, NULL);
    print(node, "post-sort");
    return 0;
}

pnode_t型は三種のunsigned int型のID、身長、体重をデータとして保持する。
pnode_t型で表される要素の順位は、supで定義しているように、
身長が高いほど高順位であり、同身長なら体重が重いほど高順位であり、
身長と体重が同じならIDが大きいものが高順位となる。
実行してみると、

pre-sort
[id=1, height=166, weight=53]
[id=2, height=157, weight=48]
[id=3, height=160, weight=53]
[id=4, height=157, weight=47]
[id=5, height=161, weight=50]
[id=6, height=160, weight=53]
post-sort
[id=4, height=157, weight=47]
[id=2, height=157, weight=48]
[id=3, height=160, weight=53]
[id=6, height=160, weight=53]
[id=5, height=161, weight=50]
[id=1, height=166, weight=53]

lsortによって、身長＞体重＞IDの優先順位で、それぞれ昇順に整列している。