#undef G_TREE_DEBUG
-#define MAX_GTREE_HEIGHT 40
-
typedef struct _GTreeNode GTreeNode;
struct _GTree
gpointer value; /* value stored at this node */
GTreeNode *left; /* left subtree */
GTreeNode *right; /* right subtree */
- gint8 balance; /* height (left) - height (right) */
- guint8 left_child;
- guint8 right_child;
+ GTreeNode *parent; /* parent node */
+ guint8 left_child; /* the node has a left child (else left points to the
+ previous node in the tree) */
+ guint8 right_child; /* the node has a right child (else right points to
+ the next node in the tree) */
};
static GTreeNode* g_tree_node_new (gpointer key,
gpointer value);
+static guint g_tree_priority (GTreeNode *node);
static void g_tree_insert_internal (GTree *tree,
gpointer key,
gpointer value,
static gboolean g_tree_remove_internal (GTree *tree,
gconstpointer key,
gboolean steal);
-static GTreeNode* g_tree_node_balance (GTreeNode *node);
static GTreeNode *g_tree_find_node (GTree *tree,
gconstpointer key);
static gint g_tree_node_pre_order (GTreeNode *node,
static gpointer g_tree_node_search (GTreeNode *node,
GCompareFunc search_func,
gconstpointer data);
+static gint g_tree_node_height (GTreeNode *node);
static GTreeNode* g_tree_node_rotate_left (GTreeNode *node);
static GTreeNode* g_tree_node_rotate_right (GTreeNode *node);
#ifdef G_TREE_DEBUG
static void g_tree_node_check (GTreeNode *node);
#endif
-
static GTreeNode*
g_tree_node_new (gpointer key,
gpointer value)
{
GTreeNode *node = g_slice_new (GTreeNode);
- node->balance = 0;
node->left = NULL;
node->right = NULL;
+ node->parent = NULL;
node->left_child = FALSE;
node->right_child = FALSE;
node->key = key;
* creating the #GTree, the passed key is freed using that function.
*
* The tree is automatically 'balanced' as new key/value pairs are added,
- * so that the distance from the root to every leaf is as small as possible.
+ * so that the distance from the root to every leaf is small.
**/
void
g_tree_insert (GTree *tree,
* freed using that function.
*
* The tree is automatically 'balanced' as new key/value pairs are added,
- * so that the distance from the root to every leaf is as small as possible.
+ * so that the distance from the root to every leaf is small.
**/
void
g_tree_replace (GTree *tree,
#endif
}
+/*
+ * Implementation of a treap
+ *
+ * (Copied from gsequence.c)
+ */
+static guint
+g_tree_priority (GTreeNode *node)
+{
+ guint key = GPOINTER_TO_UINT (node);
+
+ /* This hash function is based on one found on Thomas Wang's
+ * web page at
+ *
+ * http://www.concentric.net/~Ttwang/tech/inthash.htm
+ *
+ */
+ key = (key << 15) - key - 1;
+ key = key ^ (key >> 12);
+ key = key + (key << 2);
+ key = key ^ (key >> 4);
+ key = key + (key << 3) + (key << 11);
+ key = key ^ (key >> 16);
+
+ /* We rely on 0 being less than all other priorities */
+ return key? key : 1;
+}
+
/* internal insert routine */
static void
g_tree_insert_internal (GTree *tree,
gpointer value,
gboolean replace)
{
- GTreeNode *node;
- GTreeNode *path[MAX_GTREE_HEIGHT];
- int idx;
+ GTreeNode *node, *child;
g_return_if_fail (tree != NULL);
return;
}
- idx = 0;
- path[idx++] = NULL;
node = tree->root;
while (1)
{
- int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
+ gint cmp = tree->key_compare (key, node->key, tree->key_compare_data);
if (cmp == 0)
{
else if (cmp < 0)
{
if (node->left_child)
- {
- path[idx++] = node;
node = node->left;
- }
else
{
- GTreeNode *child = g_tree_node_new (key, value);
+ child = g_tree_node_new (key, value);
child->left = node->left;
child->right = node;
+ child->parent = node;
+
node->left = child;
node->left_child = TRUE;
- node->balance -= 1;
tree->nnodes++;
else
{
if (node->right_child)
- {
- path[idx++] = node;
node = node->right;
- }
else
{
- GTreeNode *child = g_tree_node_new (key, value);
+ child = g_tree_node_new (key, value);
child->right = node->right;
child->left = node;
+ child->parent = node;
+
node->right = child;
node->right_child = TRUE;
- node->balance += 1;
tree->nnodes++;
}
}
- /* restore balance. This is the goodness of a non-recursive
- implementation, when we are done with balancing we 'break'
- the loop and we are done. */
- while (1)
+ /* rotate the new node up until the heap property is restored */
+ node = child;
+ while (node->parent &&
+ g_tree_priority (node) < g_tree_priority (node->parent))
{
- GTreeNode *bparent = path[--idx];
- gboolean left_node = (bparent && node == bparent->left);
- g_assert (!bparent || bparent->left == node || bparent->right == node);
-
- if (node->balance < -1 || node->balance > 1)
- {
- node = g_tree_node_balance (node);
- if (bparent == NULL)
- tree->root = node;
- else if (left_node)
- bparent->left = node;
- else
- bparent->right = node;
- }
-
- if (node->balance == 0 || bparent == NULL)
- break;
-
- if (left_node)
- bparent->balance -= 1;
+ GTreeNode *const sp = node->parent->parent;
+ GTreeNode *const p = node->parent;
+ if (p->left == node)
+ g_tree_node_rotate_right (p);
else
- bparent->balance += 1;
+ g_tree_node_rotate_left (p);
- node = bparent;
+ if (!sp)
+ tree->root = node;
+ else if (sp->left == p)
+ sp->left = node;
+ else
+ sp->right = node;
}
}
gconstpointer key,
gboolean steal)
{
- GTreeNode *node, *parent, *balance;
- GTreeNode *path[MAX_GTREE_HEIGHT];
- int idx;
- gboolean left_node;
+ GTreeNode *node, *parent;
+ gboolean is_leftchild;
g_return_val_if_fail (tree != NULL, FALSE);
if (!tree->root)
return FALSE;
- idx = 0;
- path[idx++] = NULL;
node = tree->root;
+ parent = NULL;
+ is_leftchild = FALSE;
while (1)
{
- int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
+ gint cmp = tree->key_compare (key, node->key, tree->key_compare_data);
if (cmp == 0)
break;
{
if (!node->left_child)
return FALSE;
-
- path[idx++] = node;
+
+ parent = node;
+ is_leftchild = TRUE;
node = node->left;
}
else
{
if (!node->right_child)
return FALSE;
-
- path[idx++] = node;
+
+ parent = node;
+ is_leftchild = FALSE;
node = node->right;
}
}
- /* the following code is almost equal to g_tree_remove_node,
- except that we do not have to call g_tree_node_parent. */
- balance = parent = path[--idx];
- g_assert (!parent || parent->left == node || parent->right == node);
- left_node = (parent && node == parent->left);
-
- if (!node->left_child)
+ /* rotate the node down the tree, maintaining the heap property */
+ while (node->left_child || node->right_child)
{
- if (!node->right_child)
+ if (!node->left_child ||
+ (node->right_child &&
+ g_tree_priority (node->left) > g_tree_priority (node->right)))
{
+ /* rotate the right child up */
if (!parent)
- tree->root = NULL;
- else if (left_node)
- {
- parent->left_child = FALSE;
- parent->left = node->left;
- parent->balance += 1;
- }
+ parent = tree->root = g_tree_node_rotate_left (node);
+ else if (is_leftchild)
+ parent = parent->left = g_tree_node_rotate_left (node);
else
- {
- parent->right_child = FALSE;
- parent->right = node->right;
- parent->balance -= 1;
- }
+ parent = parent->right = g_tree_node_rotate_left (node);
+ is_leftchild = TRUE;
}
- else /* node has a right child */
+ else
{
- GTreeNode *tmp = g_tree_node_next (node);
- tmp->left = node->left;
-
+ /* rotate the left child up */
if (!parent)
- tree->root = node->right;
- else if (left_node)
- {
- parent->left = node->right;
- parent->balance += 1;
- }
+ parent = tree->root = g_tree_node_rotate_right (node);
+ else if (is_leftchild)
+ parent = parent->left = g_tree_node_rotate_right (node);
else
- {
- parent->right = node->right;
- parent->balance -= 1;
- }
+ parent = parent->right = g_tree_node_rotate_right (node);
+ is_leftchild = FALSE;
}
}
- else /* node has a left child */
+
+ /* remove any pointers to the node in the treap */
+ if (!parent)
+ tree->root = NULL;
+ else if (is_leftchild)
{
- if (!node->right_child)
- {
- GTreeNode *tmp = g_tree_node_previous (node);
- tmp->right = node->right;
-
- if (parent == NULL)
- tree->root = node->left;
- else if (left_node)
- {
- parent->left = node->left;
- parent->balance += 1;
- }
- else
- {
- parent->right = node->left;
- parent->balance -= 1;
- }
- }
- else /* node has a both children (pant, pant!) */
- {
- GTreeNode *prev = node->left;
- GTreeNode *next = node->right;
- GTreeNode *nextp = node;
- int old_idx = idx + 1;
- idx++;
-
- /* path[idx] == parent */
- /* find the immediately next node (and its parent) */
- while (next->left_child)
- {
- path[++idx] = nextp = next;
- next = next->left;
- }
-
- path[old_idx] = next;
- balance = path[idx];
-
- /* remove 'next' from the tree */
- if (nextp != node)
- {
- if (next->right_child)
- nextp->left = next->right;
- else
- nextp->left_child = FALSE;
- nextp->balance += 1;
-
- next->right_child = TRUE;
- next->right = node->right;
- }
- else
- node->balance -= 1;
-
- /* set the prev to point to the right place */
- while (prev->right_child)
- prev = prev->right;
- prev->right = next;
-
- /* prepare 'next' to replace 'node' */
- next->left_child = TRUE;
- next->left = node->left;
- next->balance = node->balance;
-
- if (!parent)
- tree->root = next;
- else if (left_node)
- parent->left = next;
- else
- parent->right = next;
- }
+ parent->left_child = FALSE;
+ parent->left = node->left;
+ }
+ else
+ {
+ parent->right_child = FALSE;
+ parent->right = node->right;
}
-
- /* restore balance */
- if (balance)
- while (1)
- {
- GTreeNode *bparent = path[--idx];
- g_assert (!bparent || bparent->left == balance || bparent->right == balance);
- left_node = (bparent && balance == bparent->left);
-
- if(balance->balance < -1 || balance->balance > 1)
- {
- balance = g_tree_node_balance (balance);
- if (!bparent)
- tree->root = balance;
- else if (left_node)
- bparent->left = balance;
- else
- bparent->right = balance;
- }
-
- if (balance->balance != 0 || !bparent)
- break;
-
- if (left_node)
- bparent->balance += 1;
- else
- bparent->balance -= 1;
-
- balance = bparent;
- }
if (!steal)
{
return NULL;
}
+static gint
+g_tree_node_height(GTreeNode *node)
+{
+ gint l = 0, r = 0;
+ if (node == NULL) return 0;
+ if (node->left_child) l = g_tree_node_height (node->left);
+ if (node->right_child) r = g_tree_node_height (node->right);
+ return 1 + MAX(l, r);
+}
+
/**
* g_tree_height:
* @tree: a #GTree.
gint
g_tree_height (GTree *tree)
{
- GTreeNode *node;
- gint height;
-
g_return_val_if_fail (tree != NULL, 0);
- if (!tree->root)
- return 0;
-
- height = 0;
- node = tree->root;
-
- while (1)
- {
- height += 1 + MAX(node->balance, 0);
-
- if (!node->left_child)
- return height;
-
- node = node->left;
- }
+ return g_tree_node_height (tree->root);
}
/**
return tree->nnodes;
}
-static GTreeNode*
-g_tree_node_balance (GTreeNode *node)
-{
- if (node->balance < -1)
- {
- if (node->left->balance > 0)
- node->left = g_tree_node_rotate_left (node->left);
- node = g_tree_node_rotate_right (node);
- }
- else if (node->balance > 1)
- {
- if (node->right->balance < 0)
- node->right = g_tree_node_rotate_right (node->right);
- node = g_tree_node_rotate_left (node);
- }
-
- return node;
-}
-
static GTreeNode *
g_tree_find_node (GTree *tree,
gconstpointer key)
g_tree_node_rotate_left (GTreeNode *node)
{
GTreeNode *right;
- gint a_bal;
- gint b_bal;
right = node->right;
if (right->left_child)
- node->right = right->left;
+ {
+ node->right = right->left;
+ node->right->parent = node;
+ }
else
{
node->right_child = FALSE;
right->left_child = TRUE;
}
right->left = node;
-
- a_bal = node->balance;
- b_bal = right->balance;
-
- if (b_bal <= 0)
- {
- if (a_bal >= 1)
- right->balance = b_bal - 1;
- else
- right->balance = a_bal + b_bal - 2;
- node->balance = a_bal - 1;
- }
- else
- {
- if (a_bal <= b_bal)
- right->balance = a_bal - 2;
- else
- right->balance = b_bal - 1;
- node->balance = a_bal - b_bal - 1;
- }
+ right->parent = node->parent;
+ node->parent = right;
return right;
}
g_tree_node_rotate_right (GTreeNode *node)
{
GTreeNode *left;
- gint a_bal;
- gint b_bal;
left = node->left;
if (left->right_child)
- node->left = left->right;
+ {
+ node->left = left->right;
+ node->left->parent = node;
+ }
else
{
node->left_child = FALSE;
left->right_child = TRUE;
}
left->right = node;
-
- a_bal = node->balance;
- b_bal = left->balance;
-
- if (b_bal <= 0)
- {
- if (b_bal > a_bal)
- left->balance = b_bal + 1;
- else
- left->balance = a_bal + 2;
- node->balance = a_bal - b_bal + 1;
- }
- else
- {
- if (a_bal <= -1)
- left->balance = b_bal + 1;
- else
- left->balance = a_bal + b_bal + 2;
- node->balance = a_bal + 1;
- }
+ left->parent = node->parent;
+ node->parent = left;
return left;
}
#ifdef G_TREE_DEBUG
-static gint
-g_tree_node_height (GTreeNode *node)
-{
- gint left_height;
- gint right_height;
-
- if (node)
- {
- left_height = 0;
- right_height = 0;
-
- if (node->left_child)
- left_height = g_tree_node_height (node->left);
-
- if (node->right_child)
- right_height = g_tree_node_height (node->right);
-
- return MAX (left_height, right_height) + 1;
- }
-
- return 0;
-}
-
static void
g_tree_node_check (GTreeNode *node)
{
gint left_height;
gint right_height;
- gint balance;
GTreeNode *tmp;
if (node)
if (node->right_child)
right_height = g_tree_node_height (node->right);
- balance = right_height - left_height;
- g_assert (balance == node->balance);
-
if (node->left_child)
g_tree_node_check (node->left);
if (node->right_child)
destroyed_value = value;
}
+static gint preorder_i;
+static char *preorder;
+
+static gint
+traverse_preorder (gpointer key,
+ gpointer value,
+ gpointer data)
+{
+ char *ch = key;
+ preorder[preorder_i++] = *ch;
+ return FALSE;
+}
+
+static gint
+calc_height_recur(char *inorder, char *preorder, int l, int r)
+{
+ gint i, parentpos_in, left, right;
+ char parent;
+
+ if (r < l) return 0;
+
+ parent = preorder[l++];
+ parentpos_in = strchr(inorder, parent);
+
+ /* find the position of the right child in the preorder string */
+ right = 0;
+ for (i = l; i <= r; ++i)
+ if (strchr(inorder, preorder[i]) > parentpos_in) {
+ right = calc_height_recur(inorder, preorder, i, r);
+ r = i-1; /* exlcude the right subtree when looking at the left */
+ break;
+ }
+ left = calc_height_recur(inorder, preorder, l, r);
+ return 1 + MAX(left, right);
+}
+
+static gint
+calc_height(char *inorder, char *preorder, int n)
+{
+ return calc_height_recur(inorder, preorder, 0, n-1);
+}
+
+static gint traverse_num = 0;
static gint
my_traverse (gpointer key,
gpointer value,
{
char *ch = key;
g_assert ((*ch) > 0);
+ ++traverse_num;
return FALSE;
}
tree = g_tree_new (my_compare);
- for (i = 0; chars[i]; i++)
+ for (i = 0; chars[i]; i++) {
g_tree_insert (tree, &chars[i], &chars[i]);
+ }
+ g_assert(i == g_tree_nnodes(tree));
+ traverse_num = 0;
g_tree_foreach (tree, my_traverse, NULL);
+ g_assert(traverse_num == g_tree_nnodes(tree));
g_assert (g_tree_nnodes (tree) == strlen (chars));
- g_assert (g_tree_height (tree) == 6);
+ /*g_assert (g_tree_height (tree) == 6);*/
+
+ preorder = g_malloc(strlen(chars)+1);
+ preorder[strlen(chars)] = 0;
+ preorder_i = 0;
+ g_tree_traverse (tree, traverse_preorder, G_PRE_ORDER, NULL);
+ g_assert(traverse_num == g_tree_nnodes(tree));
+ g_assert(calc_height(chars, preorder, strlen(chars)) == g_tree_height(tree));
+ g_free(preorder);
p = chars;
g_tree_foreach (tree, check_order, &p);
removed = g_tree_remove (tree, &c);
g_assert (removed == FALSE);
+ traverse_num = 0;
g_tree_foreach (tree, my_traverse, NULL);
+ g_assert(traverse_num == g_tree_nnodes(tree));
g_assert (g_tree_nnodes (tree) == strlen (chars2));
- g_assert (g_tree_height (tree) == 6);
+ /*g_assert (g_tree_height (tree) == 6);*/
p = chars2;
g_tree_foreach (tree, check_order, &p);
projects / dana / cg-glib.git / commitdiff