kclib1_0010
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* kclib1のページ#10
-(by [[K]], 2019.04.22)
** (18) KIndexS
-KSizPtrを使った、ソートされたインデックスです。末尾のSは...
-この関数群はインデックス構造だけを管理するので、データ本...
-データの登録手法としては、insで普通に入れていく方法と、a...
--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 *o...
--KIndexSを初期化します。s1は初期サイズで、まあよくわから...
--cmpとoptは整列順序を決めるための比較関数でkqsortに準じ...
-void KIndexS_free(KIndexS *w)
--KIndexSが管理していた内部のテーブルを解放します。
-int KIndexS_search(KIndexS *w, void *key, int *cr)
--KIndexSの中からkeyがどこにあるかを二分探索で探します。...
--戻り値から「何番目」の情報なのかを知りたいときは、sizeo...
-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 *o...
{
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 0x800000...
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 (v...
}
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
終了行:
* kclib1のページ#10
-(by [[K]], 2019.04.22)
** (18) KIndexS
-KSizPtrを使った、ソートされたインデックスです。末尾のSは...
-この関数群はインデックス構造だけを管理するので、データ本...
-データの登録手法としては、insで普通に入れていく方法と、a...
--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 *o...
--KIndexSを初期化します。s1は初期サイズで、まあよくわから...
--cmpとoptは整列順序を決めるための比較関数でkqsortに準じ...
-void KIndexS_free(KIndexS *w)
--KIndexSが管理していた内部のテーブルを解放します。
-int KIndexS_search(KIndexS *w, void *key, int *cr)
--KIndexSの中からkeyがどこにあるかを二分探索で探します。...
--戻り値から「何番目」の情報なのかを知りたいときは、sizeo...
-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 *o...
{
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 0x800000...
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 (v...
}
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
ページ名: