単連結リストの整列 #10 任意の順序関係を指定する

今まで昇順になるようにしか整列させなかったので、
利用者側が任意の順序関係を定義して、
それに基づいた整列を行うように変更してみる。

list.h

...snip
void list_sort(list_t list, int (*issup)(int, int));
...snip

関数list_sortが二つ目の引数として関数ポインタをとるように変更する。
この関数issupはint値に関する利用者が規定した順序関係を表現するように定義する。
issupは、二つのint値を引数とし、
一つ目のint値の順序関係が二つ目よりも上位であれば非零を、さもなければ零を返す。
list_sortはこの順序関係に基づいてリストを昇順に整列する。
これに従って実装を変更する。

list.c

...snip
void list_sort(list_t list, int (*issup)(int, int))
{
    node_t *p, *q;
    if (list == NULL || list->head.next == NULL || list->head.next->next == NULL) return;
    for (q = NULL; q != list->head.next->next; q = p->next) {
        for (p = &list->head; p->next->next != q; p = p->next) {
            if (issup(p->next->val, p->next->next->val)) node_swap(p);
        }
    }
}

変更といっても、これまで直接比較していた隣り合う要素間の比較を、
与えられた関数issupを呼び出すことで行うようにif文の条件式を変更しただけである。

使用例を変更して昇順に整列したものをさらに降順で整列してみる。

test_list.c

...snip
static int is_sup(int x, int y)
{
    return x > y;
}

static int is_sup_r(int x, int y)
{
    return x < y;
}

int main(void)
{
    list_t list = list_new();
    srand(time(NULL));
    add_randnums(list);
    list_print(list);
    list_sort(list, is_sup);
    list_print(list);
    list_sort(list, is_sup_r);
    list_print(list);
    list_dispose(list);
    return 0;
}

is_supが昇順に整列するための比較関数、is_sup_rが降順で整列するための比較関数となる。
二つのの関数は、それぞれ第一引数、第二引数の値がもう一方よりも大きい時に、
第一引数の順序関係が第二引数よりも上位であると定義している。
つまりis_supでは値が大きい方が順序関係は上位であり、is_sup_rでは小さいほど順序関係が上位になる。
実行すると、

$ ./test_list
911 736 368 264 104 334 447 690 469 497 114 225 250 626 322 785 509 952 471 749
104 114 225 250 264 322 334 368 447 469 471 497 509 626 690 736 749 785 911 952
952 911 785 749 736 690 626 509 497 471 469 447 368 334 322 264 250 225 114 104