tests/tree-test.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 /*
  21  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  22  * file for a list of people on the GLib Team.  See the ChangeLog
  23  * files for a list of changes.  These files are distributed with
  24  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  25  */
  26
  27 #undef G_DISABLE_ASSERT
  28 #undef G_LOG_DOMAIN
  29
  30 #include <stdio.h>
  31 #include <string.h>
  32 #include "glib.h"
  33
  34
  35 static gint
  36 my_compare (gconstpointer a,
  37             gconstpointer b)
  38 {
  39   const char *cha = a;
  40   const char *chb = b;
  41
  42   return *cha - *chb;
  43 }
  44
  45 static gint
  46 my_search (gconstpointer a,
  47            gconstpointer b)
  48 {
  49   return my_compare (b, a);
  50 }
  51
  52 static gpointer destroyed_key = NULL;
  53 static gpointer destroyed_value = NULL;
  54
  55 static void
  56 my_key_destroy (gpointer key)
  57 {
  58   destroyed_key = key;
  59 }
  60
  61 static void
  62 my_value_destroy (gpointer value)
  63 {
  64   destroyed_value = value;
  65 }
  66
  67 static gint preorder_i;
  68 static char *preorder;
  69
  70 static gint
  71 traverse_preorder (gpointer key,
  72                    gpointer value,
  73                    gpointer data)
  74 {
  75   char *ch = key;
  76   preorder[preorder_i++] = *ch;
  77   return FALSE;
  78 }
  79
  80 static gint
  81 calc_height_recur(char *inorder, char *preorder, int l, int r)
  82 {
  83   gint i, left, right;
  84   char *parentpos_in;
  85   char parent;
  86
  87   if (r < l) return 0;
  88
  89   parent = preorder[l++];
  90   parentpos_in = strchr(inorder, parent);
  91
  92   /* find the position of the right child in the preorder string */
  93   right = 0;
  94   for (i = l; i <= r; ++i)
  95     if (strchr(inorder, preorder[i]) > parentpos_in) {
  96       right = calc_height_recur(inorder, preorder, i, r);
  97       r = i-1; /* exlcude the right subtree when looking at the left */
  98       break;
  99     }
 100   left = calc_height_recur(inorder, preorder, l, r);
 101   return 1 + MAX(left, right);
 102 }
 103
 104 static gint
 105 calc_height(char *inorder, char *preorder, int n)
 106 {
 107   return calc_height_recur(inorder, preorder, 0, n-1);
 108 }
 109
 110 static gint traverse_num = 0;
 111 static gint
 112 my_traverse (gpointer key,
 113              gpointer value,
 114              gpointer data)
 115 {
 116   char *ch = key;
 117   g_assert ((*ch) > 0);
 118   ++traverse_num;
 119   return FALSE;
 120 }
 121
 122 char chars[] =
 123   "0123456789"
 124   "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 125   "abcdefghijklmnopqrstuvwxyz";
 126
 127 char chars2[] =
 128   "0123456789"
 129   "abcdefghijklmnopqrstuvwxyz";
 130
 131 static gint
 132 check_order (gpointer key,
 133              gpointer value,
 134              gpointer data)
 135 {
 136   char **p = data;
 137   char *ch = key;
 138
 139   g_assert (**p == *ch);
 140
 141   (*p)++;
 142
 143   return FALSE;
 144 }
 145
 146
 147
 148 int
 149 main (int   argc,
 150       char *argv[])
 151 {
 152   gint i, n;
 153   GTree *tree;
 154   gboolean removed;
 155   char c, d;
 156   char *p;
 157
 158   tree = g_tree_new (my_compare);
 159
 160   n = strlen(chars);
 161   for (i = n-1; i >= 0; i--) {
 162     gchar *r;
 163
 164     r = g_tree_lookup_related (tree, &chars[i],
 165                                G_TREE_SEARCH_SUCCESSOR, 0);
 166     g_assert((i == n-1 && r == NULL) || (r && *r == chars[i+1]));
 167
 168     g_tree_insert (tree, &chars[i], &chars[i]);
 169
 170     r = g_tree_lookup_related (tree, &chars[i],
 171                                G_TREE_SEARCH_PREDECESSOR, 0);
 172     g_assert(r && *r == chars[i]);
 173     r = g_tree_lookup_related (tree, &chars[i],
 174                                G_TREE_SEARCH_SUCCESSOR, 0);
 175     g_assert(r && *r == chars[i]);
 176   }
 177   g_assert(n == g_tree_nnodes(tree));
 178
 179   for (i = 0; i < 26; i++)
 180     {
 181       removed = g_tree_remove (tree, &chars[i + 10]);
 182       g_assert (removed);
 183     }
 184   g_assert (g_tree_nnodes (tree) == strlen (chars2));
 185
 186   c = '\0';
 187   removed = g_tree_remove (tree, &c);
 188   g_assert (removed == FALSE);
 189
 190   traverse_num = 0;
 191   g_tree_foreach (tree, my_traverse, NULL);
 192   g_assert(traverse_num == g_tree_nnodes(tree));
 193
 194   p = chars2;
 195   g_tree_foreach (tree, check_order, &p);
 196
 197   for (i = 25; i >= 0; i--)
 198     g_tree_insert (tree, &chars[i + 10], &chars[i + 10]);
 199
 200   p = chars;
 201   g_tree_foreach (tree, check_order, &p);
 202
 203   c = '0';
 204   p = g_tree_lookup (tree, &c);
 205   g_assert (p && *p == c);
 206
 207   c = 'A';
 208   p = g_tree_lookup (tree, &c);
 209   g_assert (p && *p == c);
 210
 211   c = 'a';
 212   p = g_tree_lookup (tree, &c);
 213   g_assert (p && *p == c);
 214
 215   c = 'z';
 216   p = g_tree_lookup (tree, &c);
 217   g_assert (p && *p == c);
 218
 219   c = '!';
 220   p = g_tree_lookup (tree, &c);
 221   g_assert (p == NULL);
 222
 223   c = '=';
 224   p = g_tree_lookup (tree, &c);
 225   g_assert (p == NULL);
 226
 227   c = '|';
 228   p = g_tree_lookup (tree, &c);
 229   g_assert (p == NULL);
 230
 231   c = '0';
 232   p = g_tree_search (tree, my_search, &c);
 233   g_assert (p && *p == c);
 234
 235   c = 'A';
 236   p = g_tree_search (tree, my_search, &c);
 237   g_assert (p && *p == c);
 238
 239   c = 'a';
 240   p = g_tree_search (tree, my_search, &c);
 241   g_assert (p &&*p == c);
 242
 243   c = 'z';
 244   p = g_tree_search (tree, my_search, &c);
 245   g_assert (p && *p == c);
 246
 247   c = '!';
 248   p = g_tree_search (tree, my_search, &c);
 249   g_assert (p == NULL);
 250
 251   c = '=';
 252   p = g_tree_search (tree, my_search, &c);
 253   g_assert (p == NULL);
 254
 255   c = '|';
 256   p = g_tree_search (tree, my_search, &c);
 257   g_assert (p == NULL);
 258
 259   g_tree_unref (tree);
 260
 261   /* test adding and removing items in a versioned tree */
 262   tree = g_tree_new (my_compare);
 263
 264   for (i = 0; chars[i]; i++) {
 265     gchar *r;
 266     gint j;
 267
 268     r = g_tree_lookup_related (tree, &chars[i],
 269                                G_TREE_SEARCH_PREDECESSOR, i);
 270     g_assert((i == 0 && r == NULL) || (r && *r == chars[i-1]));
 271
 272     if (i > 0)
 273       {
 274         r = g_tree_lookup_related (tree, &chars[i],
 275                                    G_TREE_SEARCH_PREDECESSOR, i-1);
 276         g_assert((i == 1 && r == NULL) || (r && *r == chars[i-2]));
 277       }
 278
 279     g_tree_next_version (tree);
 280     g_tree_insert (tree, &chars[i], &chars[i]);
 281
 282     r = g_tree_lookup_related (tree, &chars[i],
 283                                G_TREE_SEARCH_PREDECESSOR, i+1);
 284     g_assert(r && *r == chars[i]);
 285     r = g_tree_lookup_related (tree, &chars[i],
 286                                G_TREE_SEARCH_SUCCESSOR, i+1);
 287     g_assert(r && *r == chars[i]);
 288
 289     for (j = 0; j <= i+1; ++j)
 290       {
 291         r = g_tree_lookup_related (tree, &chars[i],
 292                                    G_TREE_SEARCH_PREDECESSOR, j);
 293         g_assert((j == 0 && r == NULL) || (r && *r == chars[j-1]));
 294       }
 295   }
 296   g_assert(i == g_tree_nnodes(tree));
 297
 298   traverse_num = 0;
 299   g_tree_foreach (tree, my_traverse, NULL);
 300   g_assert(traverse_num == g_tree_nnodes(tree));
 301
 302   g_assert (g_tree_nnodes (tree) == strlen (chars));
 303
 304   preorder = g_malloc(strlen(chars)+1);
 305   preorder[strlen(chars)] = 0;
 306   preorder_i = 0;
 307   g_tree_traverse (tree, traverse_preorder, G_PRE_ORDER, NULL);
 308   g_assert(traverse_num == g_tree_nnodes(tree));
 309   g_assert(calc_height(chars, preorder, strlen(chars)) == g_tree_height(tree));
 310   g_free(preorder);
 311
 312   p = chars;
 313   g_tree_foreach (tree, check_order, &p);
 314
 315   for (i = 0; i < 26; i++)
 316     {
 317       g_tree_next_version (tree);
 318       removed = g_tree_remove (tree, &chars[i + 10]);
 319       g_assert (removed == FALSE);
 320     }
 321   g_assert (g_tree_nnodes (tree) == strlen (chars2));
 322
 323   g_tree_next_version (tree);
 324   removed = g_tree_remove (tree, &chars[36]);
 325   g_assert (removed == FALSE);
 326   removed = g_tree_remove (tree, &chars[37]);
 327   g_assert (removed == FALSE);
 328   removed = g_tree_remove (tree, &chars[38]);
 329   g_assert (removed == FALSE);
 330
 331   n = strlen(chars);
 332   for (i = 0; i <= n+26+1; ++i)
 333     {
 334       gchar *r;
 335       gint j;
 336
 337       for (j = 0; chars[j]; ++j)
 338         {
 339           r = g_tree_lookup_related (tree, &chars[j],
 340                                      G_TREE_SEARCH_PREDECESSOR, i);
 341
 342           if (i == 0) /* the tree was empty */
 343             g_assert (r == NULL);
 344           else if (i <= n) /* items were being inserted */
 345             {
 346               if (j < i)
 347                 g_assert (r && *r == chars[j]);
 348               else
 349                 g_assert (r && *r == chars[i-1]);
 350             }
 351           else /* some items have been removed */
 352             {
 353               if (j < 10)
 354                 g_assert (r && *r == chars[j]);
 355               else if (i == n+26+1 && j >= 36 && j <= 38)
 356                 g_assert (r && *r == chars[9]);
 357               else if (j > 10+i-(n+1)) /* last char that has been removed in
 358                                           version i */
 359                 g_assert (r && *r == chars[j]);
 360               else
 361                 g_assert (r && *r == chars[9]);
 362             }
 363         }
 364     }
 365
 366   g_tree_unref (tree);
 367
 368   /* test removing versions from a tree */
 369   tree = g_tree_new (my_compare);
 370
 371   for (i = 0; i < chars[i]; i++) {
 372     g_tree_insert (tree, &chars[i], &chars[i]);
 373     g_tree_next_version (tree);
 374   }
 375   g_assert(i == g_tree_nnodes(tree));
 376
 377   /* remove everything from the last version */
 378   for (i = 0; chars[i]; i++)
 379     g_tree_remove (tree, &chars[i]);
 380   g_assert(g_tree_nnodes(tree) == 0);
 381
 382   g_assert (g_tree_current_version (tree) == i);
 383
 384   for (i = 0; i < g_tree_current_version (tree); ++i)
 385     {
 386       char *r;
 387       int j;
 388
 389       for (j = 0; chars[j]; j++)
 390         {
 391           r = g_tree_lookup_related (tree, &chars[j],
 392                                      G_TREE_SEARCH_PREDECESSOR, i);
 393           g_assert (r && *r == chars[MIN(j,i)]);
 394         }
 395     }
 396
 397   for (i = 0; i < g_tree_current_version (tree); ++i)
 398     {
 399       guint k;
 400       if (i%2==0)
 401         g_tree_delete_versions (tree, i);
 402
 403       for (k = 0; k < g_tree_current_version (tree); ++k)
 404         {
 405           char *r;
 406           int j;
 407
 408           for (j = 0; chars[j]; j++)
 409             {
 410               r = g_tree_lookup_related (tree, &chars[j],
 411                                          G_TREE_SEARCH_PREDECESSOR, k);
 412               g_assert ((k <= i/2*2 && r == NULL) ||
 413                         (k > i/2*2 && r && *r == chars[MIN(j,k)]));
 414             }
 415         }
 416     }
 417
 418   g_tree_delete_versions (tree, g_tree_current_version (tree)-1);
 419
 420   for (i = 0; i < g_tree_current_version (tree); ++i)
 421     {
 422       char *r;
 423       int j;
 424
 425       for (j = 0; chars[j]; j++)
 426         {
 427           r = g_tree_lookup_related (tree, &chars[j],
 428                                      G_TREE_SEARCH_PREDECESSOR, i);
 429           g_assert (r == NULL);
 430         }
 431     }
 432
 433   g_tree_unref (tree);
 434
 435   /* test destroying a versioned tree */
 436   tree = g_tree_new (my_compare);
 437
 438   for (i = 0; chars[i]; i++) {
 439     g_tree_next_version (tree);
 440     g_tree_insert (tree, &chars[i], &chars[i]);
 441   }
 442
 443   g_tree_unref (tree);
 444
 445   tree = g_tree_new_full ((GCompareDataFunc)my_compare, NULL,
 446                           my_key_destroy,
 447                           my_value_destroy);
 448
 449   for (i = 0; chars[i]; i++)
 450     g_tree_insert (tree, &chars[i], &chars[i]);
 451
 452   c = '0';
 453   g_tree_insert (tree, &c, &c);
 454   g_assert (destroyed_key == &c);
 455   g_assert (destroyed_value == &chars[0]);
 456   destroyed_key = NULL;
 457   destroyed_value = NULL;
 458
 459   d = '1';
 460   g_tree_replace (tree, &d, &d);
 461   g_assert (destroyed_key == &chars[1]);
 462   g_assert (destroyed_value == &chars[1]);
 463   destroyed_key = NULL;
 464   destroyed_value = NULL;
 465
 466   c = '2';
 467   removed = g_tree_remove (tree, &c);
 468   g_assert (removed);
 469   g_assert (destroyed_key == &chars[2]);
 470   g_assert (destroyed_value == &chars[2]);
 471   destroyed_key = NULL;
 472   destroyed_value = NULL;
 473
 474   c = '3';
 475   removed = g_tree_steal (tree, &c);
 476   g_assert (removed);
 477   g_assert (destroyed_key == NULL);
 478   g_assert (destroyed_value == NULL);
 479
 480   g_tree_unref (tree);
 481
 482   return 0;
 483 }
 484