#include <stdio.h>
#include <malloc.h>
#include "sbt.h"
#define osal_malloc(...) malloc(__VA_ARGS__)
#define osal_free(...) free(__VA_ARGS__)
struct sbt *root_dump = 0;
void sbt_dump (struct sbt *x, int lvl, const char *lr, sbt_print print)
{
if (!x) return ;
print (x->key, lvl, lr); printf (" %d\n", x->size);
sbt_dump (sbt_left(x), lvl+1, "L", print);
sbt_dump (sbt_right(x), lvl+1, "R", print);
}
////////////////////////////////////////////////////////////////////////////////
void sbt_walker (struct sbt *x, sbt_walker_func func)
{
if (!x) return ;
func (x->key);
sbt_walker (sbt_left(x), func);
sbt_walker (sbt_right(x), func);
}
////////////////////////////////////////////////////////////////////////////////
void *sbt_init (struct sbt *x, void *key)
{
x->key = key;
x->size = 1;
sbt_left(x) = sbt_right(x) = 0;
return x;
}
struct sbt *sbt_new (void *key)
{
struct sbt *x = osal_malloc (sizeof (struct sbt));
sbt_init (x, key);
return x;
}
/**旋轉
*/
void sbt_rotate (struct sbt **X, int d) // d: sbt_left sbt_right
{
struct sbt *x = *X;
struct sbt *y;
y = x->son[sbt_sibbling(d)]; // 指向要旋轉到父節點的子節點
x->son[sbt_sibbling(d)] = y->son[d];
y->son[d] = x;
y->size = x->size;
x->size = sbt_size(sbt_left(x)) + sbt_size(sbt_right(x)) + 1;
*X = y;
}
/**平衡操作
* 檢查(*X)->son[d]的子樹是否比(*X)->son[sbt_sibbling(d)]大
*/
void sbt_maintain (struct sbt **X, int d)
{
struct sbt *x = *X;
if (x->son[d] == 0) return;
if (sbt_size(x->son[sbt_sibbling(d)]) < sbt_size(x->son[d]->son[d]))
sbt_rotate (&x, sbt_sibbling(d));
else if (sbt_size(x->son[sbt_sibbling(d)]) < sbt_size(x->son[d]->son[sbt_sibbling(d)])) {
sbt_rotate (&x->son[d], d);
sbt_rotate (&x, sbt_sibbling(d));
} else return;
sbt_maintain (&sbt_left(x), SBT_LEFT);
sbt_maintain (&sbt_right(x), SBT_RIGHT);
sbt_maintain (&x, SBT_LEFT);
sbt_maintain (&x, SBT_RIGHT);
*X = x;
}
////////////////////////////////////////////////////////////////////////////////
/**
* 不提供衝突檢測和處理，要求每個插入的key之間沒有重疊。
*/
struct sbt *sbt_insert (struct sbt **X, void *key, sbt_gt gt)
{
struct sbt *x = *X;
struct sbt *r;
int d;
if (!x) return (*X = sbt_new (key));
x->size ++;
d = gt (key, x->key);
r = sbt_insert (&x->son[d], key, gt);
sbt_maintain (&x, d);
*X = x;
return r;
}
void sbt_remove (struct sbt **X)
{
struct sbt *x = *X;
if (sbt_left (x) == 0) {*X = sbt_right(x); osal_free (x);}
else if (sbt_right(x) == 0) {*X = sbt_left (x); osal_free (x);}
else {
struct sbt *p = x;
X = &sbt_right(x);
do {
x->size --;
X = &sbt_left(*X);
x = *X;
} while (sbt_left(x));
p->key = (*X)->key;
sbt_remove (X);
}
// if (root_dump) sbt_dump (root_dump, 1, ".", print);
}
/**
* 從sbt_remove可以看到，sbt_delete並不負責釋放key。
* 如果key是通過malloc等動態分配手段獲取的空間，需由調用者負責釋放。
* 但由fbt_new獲取的struct sbt空間，則會由sbt_remove釋放。
*/
void *sbt_delete (struct sbt **X, void *key, sbt_gt gt)
{
struct sbt *x = *X;
struct sbt *p;
void *k;
if (gt (x->key, key)) {
if (sbt_left(x) == 0) return 0;
k = sbt_delete (&sbt_left(x), key, gt);
x->size = sbt_size (sbt_left(x)) + sbt_size (sbt_right(x)) + 1;
// if (root_dump) sbt_dump (root_dump, 1, ".", print);
return k;
}
if (gt (key, x->key)) {
if (sbt_right(x) == 0) return 0;
k = sbt_delete (&sbt_right(x), key, gt);
x->size = sbt_size (sbt_left(x)) + sbt_size (sbt_right(x)) + 1;
// if (root_dump) sbt_dump (root_dump, 1, ".", print);
return k;
}
k = x->key;
sbt_remove (X);
return k;
}
////////////////////////////////////////////////////////////////////////////////
void *sbt_search (struct sbt *x, void *key, sbt_gt gt)
{
if (!x) return 0;
if (gt (x->key, key)) return sbt_search (sbt_left(x), key, gt);
if (gt (key, x->key)) return sbt_search (sbt_right(x), key, gt);
return x->key;
}
////////////////////////////////////////////////////////////////////////////////
/**
* 不提供衝突檢測和處理，要求每個插入的key之間沒有重疊。
*/
struct sbt *sbt_insert_node (struct sbt **X, struct sbt *key, sbt_gt gt)
{
struct sbt *x = *X;
struct sbt *r;
int d;
if (!x) return (*X = key);
x->size ++;
d = gt (key->key, x->key);
r = sbt_insert_node (&x->son[d], key, gt);
sbt_maintain (&x, d);
*X = x;
return r;
}
void sbt_removep (struct sbt **X)
{
struct sbt *x = *X;
if (x) *X = sbt_right(x);
}
struct sbt **sbt_smallest (struct sbt **X)
{
struct sbt *left;
if (!X || !*X) return 0;
while (left = sbt_left(*X)) {
X = &sbt_left(*X);
}
return X;
}
