* 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);
-void KIndexS_add(KIndexS *w, void *d)
--KIndexSの末尾にデータを追加します。ソート順序が保たれるかどうかは追加するデータ次第です。
-void KIndexS_sort(KIndexS *w);
-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 *)));
 }

* こめんと欄
#comment
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS