kclib1のページ#10

  • (by K, 2019.04.22)

(18) KIndexS

  • KSizPtrを使った、ソートされたインデックスです。末尾のSはソートの略です。
  • この関数群はインデックス構造だけを管理するので、データ本体は管理しません。
  • データの登録手法としては、insで普通に入れていく方法と、addして最後にsortする方法の二通りをサポートしています。
    • ins方式: O(N*N*logN)
    • add+sort方式: O(N*logN)
    • Nが小さいうちはinsのほうが少し速いですがすぐに逆転します。
  • searchのスピードは1件に付きO(logN)です。

  • void KIndexS_init(KIndexS *w, int s1, void *cmp, void *opt)
    • KIndexSを初期化します。s1は初期サイズで、まあよくわからなければ0でいいです。単位はバイトではなく要素数です。
    • cmpとoptは整列順序を決めるための比較関数でkqsortに準じます。
  • void KIndexS_free(KIndexS *w)
    • KIndexSが管理していた内部のテーブルを解放します。
  • int KIndexS_search(KIndexS *w, void *key, int *cr)
    • KIndexSの中からkeyがどこにあるかを二分探索で探します。見つかった場合、*cr=0になります。見つからなかった場合、*crは負の値になり、関数の戻り値は「そのkeyをinsするとしたらどこがいいか」をバイト単位で表した値になっています。
    • 戻り値から「何番目」の情報なのかを知りたいときは、sizeof (void *)で割り算する必要があります。
  • int KIndexS_ins(KIndexS *w, void *d)
    • KIndexSにデータを一つ追加します。ソート順序は保たれます。
  • int KIndexS_del(KIndexS *w, void *d)
    • KIndexSからデータを一つ消します。
  • void KIndexS_add(KIndexS *w, void *d)
    • KIndexSの末尾にデータを追加します。ソート順序が保たれるかどうかは追加するデータ次第です。
  • void KIndexS_sort(KIndexS *w)
    • KInidexSの中のデータの順序の乱れを一気に修正します。
  • int KIndexS_getN(KIndexS *w)
    • KIndexSが管理してしているデータの個数を返します。
  • void *KIndexS_getPtr(KIndexS *w, int i)
    • KIndexSの順序で、i番目のデータへのポインタを返します。

  • [内部実装]
    typedef struct KIndexS_ {
        KSizPtr sp;
        void *cmp, *opt;
    } KIndexS;

  • [内部実装]
    #include "kclib1.h"
    
    void KIndexS_init(KIndexS *w, int s1, void *cmp, void *opt)
    {
        KSizPtr_init(&w->sp, s1 * sizeof (void *));
        w->cmp = cmp;
        w->opt = opt;
    }
    
    void KIndexS_free(KIndexS *w)
    {
        KSizPtr_free(&w->sp);
    }
    
    int KIndexS_search(KIndexS *w, void *key, int *cr)
    {
        int a, b, c, cc, ccb;
        int (*cmp)(void *, void *, void *);
        void *opt = w->opt, *pk = &key;
        if (w->sp.s <= 0) {
            *cr = -1;
            return 0;
        }
        cmp = w->cmp;
        cc = cmp(opt, pk, w->sp.p);
        if (cc <= 0) {
            *cr = cc;
            return 0;
        }
        cc = cmp(opt, pk, w->sp.p + w->sp.s - sizeof (void *));
        if (cc > 0) {
            *cr = -1;
            return w->sp.s;
        }
        if (cc == 0) {
            *cr = 0;
            return w->sp.s - sizeof (void *);
        }
        ccb = cc;
        a = 0;
        b = w->sp.s - sizeof (void *);
        for (;;) {
            c = ((b - a) >> 1) & (- sizeof (void *));
            if (c == 0) break;
            c += a;
            cc = cmp(opt, pk, w->sp.p + c);
            if (cc > 0)
                a = c;
            else {
                b = c;
                ccb = c;
            }
        }
        *cr = cc;
        return b;
    }
    
    int KIndexS_ins(KIndexS *w, void *d)
    {
         int cr, i;
         i = KIndexS_search(w, d, &cr);
    //   if (cr == 0) return ~i;
         KSizPtr_insPtr(&w->sp, i, d);
         return i;
    }
    
    int KIndexS_del(KIndexS *w, void *d)
    {
        int cr, i;
        i = KIndexS_search(w, d, &cr);
        if (cr != 0) return ~i;
        if (*((void **) (w->sp.p + i)) != d) return 0x80000000;
        KSizPtr_delPtr(&w->sp, i);
        return i;
    }
    
    void KIndexS_add(KIndexS *w, void *d)
    {
        KSizPtr_addPtr(&w->sp, d);
    }
    
    void KIndexS_sort(KIndexS *w)
    {
        kqsort(w->sp.p, w->sp.s / sizeof (void *), sizeof (void *), w->cmp, w->opt);
    }
    
    int KIndexS_getN(KIndexS *w)
    {
         return w->sp.s / sizeof (void *);
    }
    
    void *KIndexS_getPtr(KIndexS *w, int i)
    {
        return *((void **) (w->sp.p + i * sizeof (void *)));
    }

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-04-22 (月) 16:32:31 (123d)