単連結リストの整列 #77 双方向連結リストの実装

双方向連結リストでインタフェイスintlist.hを実現してみた。

intdlist.c

#include <stddef.h>
#include <stdlib.h>
#include <assert.h>
#include "listsort.h"
#include "intlist.h"

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

struct tag_intlist {
    intelem_t head;
    intelem_t tail;
    unsigned long compare_counts;
    unsigned long swap_counts;
};

struct tag_intelem {
    int val;
    intelem_t next;
    intelem_t prev;
};

struct tag_intiter {
    cintlist_t list;
    intelem_t curr;
};

struct combined_arg {
    void *arg;
    int (*issup)(cintelem_t, cintelem_t, void *);
    intlist_t list;
};

static intelem_t intelem_new(int val)
{
    intelem_t elem = malloc(sizeof(struct tag_intelem));
    if (elem != NULL) elem->val = val;
    return elem;
}

static void intelem_dispose(intelem_t elem)
{
    free(elem);
}

static void *head(const void *list, void *listarg)
{
    UNUSED_ARG(listarg);
    return ((intlist_t)list)->head->next;
}

static void *next(const void *list, const void *p, void *listarg)
{
    UNUSED_ARG(list), UNUSED_ARG(listarg);
    return ((intelem_t)p)->next;
}

static int isvalid(const void *list, const void *p, void *listarg)
{
    UNUSED_ARG(listarg);
    return p != ((intlist_t)list)->tail && p != ((intlist_t)list)->head && p != NULL;
}

/* move p after q */
static void move_after(intlist_t list, intelem_t p, intelem_t q)
{
    UNUSED_ARG(list);
    p->prev->next = p->next;
    p->next->prev = p->prev;
    p->next = q->next;
    p->prev = q;
    q->next->prev = p;
    q->next = p;
}

static void swap(void *list, void *p, void *q, void *listarg)
{
    intelem_t t;
    UNUSED_ARG(listarg);
    (((intlist_t)list)->swap_counts)++;
    if (p == q) return;
    if (((intelem_t)p)->prev == q) {
        t = p;
        p = q;
        q = t;
    }
    t = ((intelem_t)p)->prev;
    move_after(list, p, q);
    move_after(list, q, t);
}

static int issuperior(const void *p, const void *q, void *args)
{
    (((struct combined_arg *)args)->list->compare_counts)++;
    return (((struct combined_arg *)args)->issup)(p, q, ((struct combined_arg *)args)->arg);
}

intlist_t intlist_new(void)
{
    intlist_t list = malloc(sizeof(struct tag_intlist));
    if (list != NULL) {
        list->head = intelem_new(0);
        list->tail = intelem_new(0);
        if (list->head != NULL && list->tail != NULL) {
            list->head->next = list->tail;
            list->head->prev = NULL;
            list->tail->next = NULL;
            list->tail->prev = list->head;
            list->compare_counts = 0;
            list->swap_counts = 0;
        } else {
            free(list->head);
            free(list->tail);
            free(list);
            list = NULL;
        }
    }
    return list;
}

void intlist_dispose(intlist_t list)
{
    intelem_t p, q;
    for (p = list->head; p != NULL; p = q) {
        q = p->next;
        intelem_dispose(p);
    }
    free(list);
}

int intlist_add_first(intlist_t list, int val)
{
    intelem_t p;
    if (list == NULL || (p = intelem_new(val)) == NULL) return 1;
    p->next = list->head->next;
    list->head->next = p;
    p->prev = p->next->prev;
    p->next->prev = p;
    return 0;
}

intiter_t intlist_iterator(cintlist_t list)
{
    intiter_t iter;
    if (list == NULL) return NULL;
    iter = malloc(sizeof(struct tag_intiter));
    if (iter != NULL) {
        iter->list = list;
        iter->curr = list->head->next;
    }
    return iter;
}

void intlist_sort(intlist_t list, int (*issup)(cintelem_t, cintelem_t, void *), void *arg)
{
    struct combined_arg args;
    if (list == NULL) return;
    args.arg = arg;
    args.issup = issup;
    args.list = list;
    listsort(list, head, next, isvalid, swap, NULL, issuperior, &args);
}

void intlist_reset_counts(intlist_t list)
{
    if (list == NULL) return;
    list->compare_counts = 0;
    list->swap_counts = 0;
}

unsigned long intlist_get_compare_counts(cintlist_t list)
{
    assert(list != NULL);
    return list->compare_counts;
}

unsigned long intlist_get_swap_counts(cintlist_t list)
{
    assert(list != NULL);
    return list->swap_counts;
}

int intelem_get_val(cintelem_t e)
{
    return e->val;
}

int intiter_has_next(cintiter_t iter)
{
    return iter != NULL && isvalid(iter->list, iter->curr, NULL);
}

cintelem_t intiter_next(intiter_t iter)
{
    intelem_t p;
    if (! intiter_has_next(iter)) return NULL;
    p = iter->curr;
    iter->curr = p->next;
    return p;
}

void intiter_dispose(intiter_t iter)
{
    free(iter);
}

単連結リストによる実現intlist.cと双方向連結リストによる実現intdlist.cにはそれほど大きな違いはない。
一つ前の要素の参照についても操作しないといけない分、少し記述が増えるだけである。
listsort用の要素交換関数swapについてはシンプルな記述になるよう少し変えた。
そもそも単連結リストと異なり一つ前の要素の参照を各要素が保持しているので、
一つ前の要素を先頭要素から順番にたどって探索する必要がなくなる。
また、一つの要素をリストから取り出し指定要素の次に挿入する関数move_afterを定義し、
交換はこの関数を二回呼び出すだけで済むようにしている。
intlist.cでの交換関数swapはこの辺りをそのままだらだらとswap内に書いたのであまり簡潔でない。
交換すべき二つの要素の関係を条件にしてメインの処理が三つに分かれているのも複雑さを増やしている。
intdlist.cでは、第三引数の要素qの次が第二引数の要素pになっている場合だけ、
二つの要素の参照の関数内での役割を入れ替えて、後の処理を共通化している。
qとpを入れ替えるのもpとqを入れ替えるのも同じである。