gchar *r;
r = g_tree_lookup_related (tree, &chars[i],
- G_TREE_SEARCH_SUCCESSOR);
+ G_TREE_SEARCH_SUCCESSOR, 0);
g_assert((i == n-1 && r == NULL) || (r && *r == chars[i+1]));
g_tree_insert (tree, &chars[i], &chars[i]);
r = g_tree_lookup_related (tree, &chars[i],
- G_TREE_SEARCH_PREDECESSOR);
+ G_TREE_SEARCH_PREDECESSOR, 0);
g_assert(r && *r == chars[i]);
r = g_tree_lookup_related (tree, &chars[i],
- G_TREE_SEARCH_SUCCESSOR);
+ G_TREE_SEARCH_SUCCESSOR, 0);
g_assert(r && *r == chars[i]);
}
g_assert(n == g_tree_nnodes(tree));
- g_tree_unref (tree);
- tree = g_tree_new (my_compare);
-
- for (i = 0; chars[i]; i++) {
- gchar *r;
-
- r = g_tree_lookup_related (tree, &chars[i],
- G_TREE_SEARCH_PREDECESSOR);
- g_assert((i == 0 && r == NULL) || (r && *r == chars[i-1]));
-
- g_tree_insert (tree, &chars[i], &chars[i]);
-
- r = g_tree_lookup_related (tree, &chars[i],
- G_TREE_SEARCH_PREDECESSOR);
- g_assert(r && *r == chars[i]);
- r = g_tree_lookup_related (tree, &chars[i],
- G_TREE_SEARCH_SUCCESSOR);
- g_assert(r && *r == 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);*/
-
- 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);
-
for (i = 0; i < 26; i++)
{
removed = g_tree_remove (tree, &chars[i + 10]);
g_assert (removed);
}
+ g_assert (g_tree_nnodes (tree) == strlen (chars2));
c = '\0';
removed = g_tree_remove (tree, &c);
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);*/
-
p = chars2;
g_tree_foreach (tree, check_order, &p);
p = g_tree_search (tree, my_search, &c);
g_assert (p == NULL);
+ g_tree_unref (tree);
+ tree = g_tree_new (my_compare);
+
+ for (i = 0; chars[i]; i++) {
+ gchar *r;
+ gint j;
+
+ r = g_tree_lookup_related (tree, &chars[i],
+ G_TREE_SEARCH_PREDECESSOR, i);
+ g_assert((i == 0 && r == NULL) || (r && *r == chars[i-1]));
+
+ if (i > 0)
+ {
+ r = g_tree_lookup_related (tree, &chars[i],
+ G_TREE_SEARCH_PREDECESSOR, i-1);
+ g_assert((i == 1 && r == NULL) || (r && *r == chars[i-2]));
+ }
+
+ g_tree_next_version (tree);
+ g_tree_insert (tree, &chars[i], &chars[i]);
+
+ r = g_tree_lookup_related (tree, &chars[i],
+ G_TREE_SEARCH_PREDECESSOR, i+1);
+ g_assert(r && *r == chars[i]);
+ r = g_tree_lookup_related (tree, &chars[i],
+ G_TREE_SEARCH_SUCCESSOR, i+1);
+ g_assert(r && *r == chars[i]);
+
+ for (j = 0; j <= i+1; ++j)
+ {
+ r = g_tree_lookup_related (tree, &chars[i],
+ G_TREE_SEARCH_PREDECESSOR, j);
+ g_assert((j == 0 && r == NULL) || (r && *r == chars[j-1]));
+ }
+ }
+ 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));
+
+ 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);
+
+ for (i = 0; i < 26; i++)
+ {
+ g_tree_next_version (tree);
+ removed = g_tree_remove (tree, &chars[i + 10]);
+ g_assert (removed == FALSE);
+ }
+ g_assert (g_tree_nnodes (tree) == strlen (chars2));
+
+ g_tree_next_version (tree);
+ removed = g_tree_remove (tree, &chars[36]);
+ g_assert (removed == FALSE);
+ removed = g_tree_remove (tree, &chars[37]);
+ g_assert (removed == FALSE);
+ removed = g_tree_remove (tree, &chars[38]);
+ g_assert (removed == FALSE);
+
+ n = strlen(chars);
+ for (i = 0; i <= n+26+1; ++i)
+ {
+ gchar *r;
+ gint j;
+
+ for (j = 0; chars[j]; ++j)
+ {
+ r = g_tree_lookup_related (tree, &chars[j],
+ G_TREE_SEARCH_PREDECESSOR, i);
+
+ if (i == 0) /* the tree was empty */
+ g_assert (r == NULL);
+ else if (i <= n) /* items were being inserted */
+ {
+ if (j < i)
+ g_assert (r && *r == chars[j]);
+ else
+ g_assert (r && *r == chars[i-1]);
+ }
+ else /* some items have been removed */
+ {
+ if (j < 10)
+ g_assert (r && *r == chars[j]);
+ else if (i == n+26+1 && j >= 36 && j <= 38)
+ g_assert (r && *r == chars[9]);
+ else if (j > 10+i-(n+1)) /* last char that has been removed in
+ version i */
+ g_assert (r && *r == chars[j]);
+ else
+ g_assert (r && *r == chars[9]);
+ }
+ }
+ }
g_tree_destroy (tree);
+ /* test destroying a versioned tree */
+ tree = g_tree_new (my_compare);
+
+ for (i = 0; chars[i]; i++) {
+ g_tree_next_version (tree);
+ g_tree_insert (tree, &chars[i], &chars[i]);
+ }
+
+ g_tree_unref (tree);
+
tree = g_tree_new_full ((GCompareDataFunc)my_compare, NULL,
my_key_destroy,
my_value_destroy);
g_assert (destroyed_key == NULL);
g_assert (destroyed_value == NULL);
+ g_tree_unref (tree);
+
return 0;
}