test/api/test-set.c

   1 /*
   2  * Copyright © 2013  Google, Inc.
   3  *
   4  *  This is part of HarfBuzz, a text shaping library.
   5  *
   6  * Permission is hereby granted, without written agreement and without
   7  * license or royalty fees, to use, copy, modify, and distribute this
   8  * software and its documentation for any purpose, provided that the
   9  * above copyright notice and the following two paragraphs appear in
  10  * all copies of this software.
  11  *
  12  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
  13  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
  14  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
  15  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
  16  * DAMAGE.
  17  *
  18  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
  19  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  20  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  21  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
  22  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  23  *
  24  * Google Author(s): Behdad Esfahbod
  25  */
  26
  27 #include "hb-test.h"
  28
  29 /* Unit tests for hb-set.h */
  30
  31
  32 static void
  33 test_empty (hb_set_t *s)
  34 {
  35   hb_codepoint_t next;
  36   g_assert_cmpint (hb_set_get_population (s), ==, 0);
  37   g_assert_cmpint (hb_set_get_min (s), ==, HB_SET_VALUE_INVALID);
  38   g_assert_cmpint (hb_set_get_max (s), ==, HB_SET_VALUE_INVALID);
  39   g_assert (!hb_set_has (s, 13));
  40   next = 53043;
  41   g_assert (!hb_set_next (s, &next));
  42   g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
  43   next = 07734;
  44   g_assert (!hb_set_previous (s, &next));
  45   g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
  46   g_assert (hb_set_is_empty (s));
  47 }
  48
  49 static void
  50 test_not_empty (hb_set_t *s)
  51 {
  52   hb_codepoint_t next;
  53   g_assert_cmpint (hb_set_get_population (s), !=, 0);
  54   g_assert_cmpint (hb_set_get_min (s), !=, HB_SET_VALUE_INVALID);
  55   g_assert_cmpint (hb_set_get_max (s), !=, HB_SET_VALUE_INVALID);
  56   next = HB_SET_VALUE_INVALID;
  57   g_assert (hb_set_next (s, &next));
  58   g_assert_cmpint (next, !=, HB_SET_VALUE_INVALID);
  59   next = HB_SET_VALUE_INVALID;
  60   g_assert (hb_set_previous (s, &next));
  61   g_assert_cmpint (next, !=, HB_SET_VALUE_INVALID);
  62 }
  63
  64 static void
  65 test_set_basic (void)
  66 {
  67   hb_set_t *s = hb_set_create ();
  68
  69   test_empty (s);
  70   hb_set_add (s, 13);
  71   test_not_empty (s);
  72
  73   hb_set_clear (s);
  74   test_empty (s);
  75
  76   hb_set_add (s, 33000);
  77   test_not_empty (s);
  78   hb_set_clear (s);
  79
  80   hb_set_add_range (s, 10, 29);
  81   test_not_empty (s);
  82   g_assert (hb_set_has (s, 13));
  83   g_assert_cmpint (hb_set_get_population (s), ==, 20);
  84   g_assert_cmpint (hb_set_get_min (s), ==, 10);
  85   g_assert_cmpint (hb_set_get_max (s), ==, 29);
  86
  87   test_not_empty (s);
  88   g_assert (hb_set_has (s, 13));
  89   g_assert_cmpint (hb_set_get_population (s), ==, 20);
  90   g_assert_cmpint (hb_set_get_min (s), ==, 10);
  91   g_assert_cmpint (hb_set_get_max (s), ==, 29);
  92
  93   hb_set_del_range (s, 10, 18);
  94   test_not_empty (s);
  95   g_assert (!hb_set_has (s, 13));
  96
  97   hb_set_add_range (s, 200, 800);
  98   test_not_empty (s);
  99   g_assert (!hb_set_has (s, 100));
 100   g_assert (!hb_set_has (s, 199));
 101   g_assert (hb_set_has (s, 200));
 102   g_assert (hb_set_has (s, 201));
 103   g_assert (hb_set_has (s, 243));
 104   g_assert (hb_set_has (s, 254));
 105   g_assert (hb_set_has (s, 255));
 106   g_assert (hb_set_has (s, 256));
 107   g_assert (hb_set_has (s, 257));
 108   g_assert (hb_set_has (s, 511));
 109   g_assert (hb_set_has (s, 512));
 110   g_assert (hb_set_has (s, 600));
 111   g_assert (hb_set_has (s, 767));
 112   g_assert (hb_set_has (s, 768));
 113   g_assert (hb_set_has (s, 769));
 114   g_assert (hb_set_has (s, 782));
 115   g_assert (hb_set_has (s, 798));
 116   g_assert (hb_set_has (s, 799));
 117   g_assert (hb_set_has (s, 800));
 118   g_assert (!hb_set_has (s, 801));
 119   g_assert (!hb_set_has (s, 802));
 120
 121   hb_set_del (s, 800);
 122   g_assert (!hb_set_has (s, 800));
 123
 124   g_assert_cmpint (hb_set_get_max (s), ==, 799);
 125
 126   hb_set_del_range (s, 0, 799);
 127   g_assert_cmpint (hb_set_get_max (s), ==, HB_SET_VALUE_INVALID);
 128
 129   hb_set_destroy (s);
 130 }
 131
 132
 133 // static inline void
 134 // print_set (hb_set_t *s)
 135 // {
 136 //   hb_codepoint_t next;
 137 //   printf ("{");
 138 //   for (next = HB_SET_VALUE_INVALID; hb_set_next (s, &next); )
 139 //     printf ("%d, ", next);
 140 //   printf ("}\n");
 141 // }
 142
 143 static void test_set_intersect_empty (void)
 144 {
 145   hb_set_t* a = hb_set_create ();
 146   hb_set_add (a, 3585);
 147   hb_set_add (a, 21333);
 148   hb_set_add (a, 24405);
 149
 150   hb_set_t* b = hb_set_create();
 151   hb_set_add (b, 21483);
 152   hb_set_add (b, 24064);
 153
 154   hb_set_intersect (a, b);
 155   g_assert (hb_set_is_empty (a));
 156
 157   hb_set_destroy (a);
 158   hb_set_destroy (b);
 159
 160
 161   a = hb_set_create ();
 162   hb_set_add (a, 16777216);
 163
 164   b = hb_set_create();
 165   hb_set_add (b, 0);
 166
 167   hb_set_intersect (a, b);
 168   g_assert (hb_set_is_empty (a));
 169
 170   hb_set_destroy (a);
 171   hb_set_destroy (b);
 172 }
 173
 174 static void test_set_intersect_page_reduction (void)
 175 {
 176   hb_set_t* a = hb_set_create ();
 177   hb_set_add (a, 3585);
 178   hb_set_add (a, 21333);
 179   hb_set_add (a, 24405);
 180
 181   hb_set_t* b = hb_set_create();
 182   hb_set_add (b, 3585);
 183   hb_set_add (b, 24405);
 184
 185   hb_set_intersect(a, b);
 186   g_assert (hb_set_is_equal (a, b));
 187
 188   hb_set_destroy (a);
 189   hb_set_destroy (b);
 190 }
 191
 192 static void test_set_union (void)
 193 {
 194   hb_set_t* a = hb_set_create();
 195   hb_set_add (a, 3585);
 196   hb_set_add (a, 21333);
 197   hb_set_add (a, 24405);
 198
 199   hb_set_t* b = hb_set_create();
 200   hb_set_add (b, 21483);
 201   hb_set_add (b, 24064);
 202
 203   hb_set_t* u = hb_set_create ();
 204   hb_set_add (u, 3585);
 205   hb_set_add (u, 21333);
 206   hb_set_add (u, 21483);
 207   hb_set_add (u, 24064);
 208   hb_set_add (u, 24405);
 209
 210   hb_set_union(b, a);
 211   g_assert (hb_set_is_equal (u, b));
 212
 213   hb_set_destroy (a);
 214   hb_set_destroy (b);
 215   hb_set_destroy (u);
 216 }
 217
 218 static void
 219 test_set_subsets (void)
 220 {
 221   hb_set_t *s = hb_set_create ();
 222   hb_set_t *l = hb_set_create ();
 223
 224   hb_set_add (l, 0x0FFFF);
 225   hb_set_add (s, 0x1FFFF);
 226   g_assert (!hb_set_is_subset (s, l));
 227   hb_set_clear (s);
 228
 229   hb_set_add (s, 0x0FFF0);
 230   g_assert (!hb_set_is_subset (s, l));
 231   hb_set_clear (s);
 232
 233   hb_set_add (s, 0x0AFFF);
 234   g_assert (!hb_set_is_subset (s, l));
 235
 236   hb_set_clear (s);
 237   g_assert (hb_set_is_subset (s, l));
 238
 239   hb_set_clear (l);
 240   g_assert (hb_set_is_subset (s, l));
 241
 242   hb_set_add (s, 0x1FFFF);
 243   g_assert (!hb_set_is_subset (s, l));
 244   hb_set_clear (s);
 245
 246   hb_set_add (s, 0xFF);
 247   hb_set_add (s, 0x1FFFF);
 248   hb_set_add (s, 0x2FFFF);
 249
 250   hb_set_add (l, 0xFF);
 251   hb_set_add (l, 0x1FFFF);
 252   hb_set_add (l, 0x2FFFF);
 253
 254   g_assert (hb_set_is_subset (s, l));
 255   hb_set_del (l, 0xFF);
 256   g_assert (!hb_set_is_subset (s, l));
 257   hb_set_add (l, 0xFF);
 258
 259   hb_set_del (l, 0x2FFFF);
 260   g_assert (!hb_set_is_subset (s, l));
 261   hb_set_add (l, 0x2FFFF);
 262
 263   hb_set_del (l, 0x1FFFF);
 264   g_assert (!hb_set_is_subset (s, l));
 265
 266   hb_set_destroy (s);
 267   hb_set_destroy (l);
 268 }
 269
 270 static void
 271 test_set_algebra (void)
 272 {
 273   hb_set_t *s = hb_set_create ();
 274   hb_set_t *o = hb_set_create ();
 275   hb_set_t *o2 = hb_set_create ();
 276
 277   hb_set_add (o, 13);
 278   hb_set_add (o, 19);
 279
 280   hb_set_add (o2, 0x660E);
 281
 282   test_empty (s);
 283   g_assert (!hb_set_is_equal (s, o));
 284   g_assert (hb_set_is_subset (s, o));
 285   g_assert (!hb_set_is_subset (o, s));
 286   hb_set_set (s, o);
 287   g_assert (hb_set_is_equal (s, o));
 288   g_assert (hb_set_is_subset (s, o));
 289   g_assert (hb_set_is_subset (o, s));
 290   test_not_empty (s);
 291   g_assert_cmpint (hb_set_get_population (s), ==, 2);
 292
 293   hb_set_clear (s);
 294   test_empty (s);
 295   hb_set_add (s, 10);
 296   g_assert_cmpint (hb_set_get_population (s), ==, 1);
 297   hb_set_union (s, o);
 298   g_assert_cmpint (hb_set_get_population (s), ==, 3);
 299   g_assert (hb_set_has (s, 10));
 300   g_assert (hb_set_has (s, 13));
 301
 302   hb_set_clear (s);
 303   test_empty (s);
 304   g_assert_cmpint (hb_set_get_population (s), ==, 0);
 305   hb_set_union (s, o2);
 306   g_assert_cmpint (hb_set_get_population (s), ==, 1);
 307   g_assert (hb_set_has (s, 0x660E));
 308
 309   hb_set_clear (s);
 310   test_empty (s);
 311   hb_set_add_range (s, 10, 17);
 312   g_assert (!hb_set_is_equal (s, o));
 313   hb_set_intersect (s, o);
 314   g_assert (!hb_set_is_equal (s, o));
 315   test_not_empty (s);
 316   g_assert_cmpint (hb_set_get_population (s), ==, 1);
 317   g_assert (!hb_set_has (s, 10));
 318   g_assert (hb_set_has (s, 13));
 319
 320   hb_set_clear (s);
 321   test_empty (s);
 322   hb_set_add_range (s, 10, 17);
 323   g_assert (!hb_set_is_equal (s, o));
 324   hb_set_subtract (s, o);
 325   g_assert (!hb_set_is_equal (s, o));
 326   test_not_empty (s);
 327   g_assert_cmpint (hb_set_get_population (s), ==, 7);
 328   g_assert (hb_set_has (s, 12));
 329   g_assert (!hb_set_has (s, 13));
 330   g_assert (!hb_set_has (s, 19));
 331
 332   hb_set_clear (s);
 333   test_empty (s);
 334   hb_set_add_range (s, 10, 17);
 335   g_assert (!hb_set_is_equal (s, o));
 336   hb_set_symmetric_difference (s, o);
 337   g_assert (!hb_set_is_equal (s, o));
 338   test_not_empty (s);
 339   g_assert_cmpint (hb_set_get_population (s), ==, 8);
 340   g_assert (hb_set_has (s, 12));
 341   g_assert (!hb_set_has (s, 13));
 342   g_assert (hb_set_has (s, 19));
 343
 344   /* https://github.com/harfbuzz/harfbuzz/issues/579 */
 345   hb_set_clear (s);
 346   test_empty (s);
 347   hb_set_add_range (s, 886, 895);
 348   hb_set_add (s, 1024);
 349   hb_set_add (s, 1152);
 350   hb_set_clear (o);
 351   test_empty (o);
 352   hb_set_add (o, 889);
 353   hb_set_add (o, 1024);
 354   g_assert (!hb_set_is_equal (s, o));
 355   hb_set_intersect (o, s);
 356   test_not_empty (o);
 357   g_assert (!hb_set_is_equal (s, o));
 358   g_assert_cmpint (hb_set_get_population (o), ==, 2);
 359   g_assert (hb_set_has (o, 889));
 360   g_assert (hb_set_has (o, 1024));
 361   hb_set_clear (o);
 362   test_empty (o);
 363   hb_set_add_range (o, 887, 889);
 364   hb_set_add (o, 1121);
 365   g_assert (!hb_set_is_equal (s, o));
 366   hb_set_intersect (o, s);
 367   test_not_empty (o);
 368   g_assert (!hb_set_is_equal (s, o));
 369   g_assert_cmpint (hb_set_get_population (o), ==, 3);
 370   g_assert (hb_set_has (o, 887));
 371   g_assert (hb_set_has (o, 888));
 372   g_assert (hb_set_has (o, 889));
 373
 374   hb_set_clear (s);
 375   test_empty (s);
 376   hb_set_add_range (s, 886, 895);
 377   hb_set_add (s, 1014);
 378   hb_set_add (s, 1017);
 379   hb_set_add (s, 1024);
 380   hb_set_add (s, 1113);
 381   hb_set_add (s, 1121);
 382   g_assert_cmpint (hb_set_get_population (s), ==, 15);
 383
 384   hb_set_clear (o);
 385   test_empty (o);
 386   hb_set_add (o, 889);
 387   g_assert_cmpint (hb_set_get_population (o), ==, 1);
 388   hb_set_intersect (o, s);
 389   g_assert_cmpint (hb_set_get_population (o), ==, 1);
 390   g_assert (hb_set_has (o, 889));
 391
 392   hb_set_add (o, 511);
 393   g_assert_cmpint (hb_set_get_population (o), ==, 2);
 394   hb_set_intersect (o, s);
 395   g_assert_cmpint (hb_set_get_population (o), ==, 1);
 396   g_assert (hb_set_has (o, 889));
 397
 398   hb_set_destroy (s);
 399   hb_set_destroy (o);
 400   hb_set_destroy (o2);
 401 }
 402
 403 static void
 404 test_set_iter (void)
 405 {
 406   hb_codepoint_t next, first, last;
 407   hb_set_t *s = hb_set_create ();
 408
 409   hb_set_add (s, 13);
 410   hb_set_add_range (s, 6, 6);
 411   hb_set_add_range (s, 10, 15);
 412   hb_set_add (s, 1100);
 413   hb_set_add (s, 1200);
 414   hb_set_add (s, 20005);
 415
 416   test_not_empty (s);
 417
 418   next = HB_SET_VALUE_INVALID;
 419   g_assert (hb_set_next (s, &next));
 420   g_assert_cmpint (next, ==, 6);
 421   g_assert (hb_set_next (s, &next));
 422   g_assert_cmpint (next, ==, 10);
 423   g_assert (hb_set_next (s, &next));
 424   g_assert (hb_set_next (s, &next));
 425   g_assert (hb_set_next (s, &next));
 426   g_assert_cmpint (next, ==, 13);
 427   g_assert (hb_set_next (s, &next));
 428   g_assert (hb_set_next (s, &next));
 429   g_assert_cmpint (next, ==, 15);
 430   g_assert (hb_set_next (s, &next));
 431   g_assert_cmpint (next, ==, 1100);
 432   g_assert (hb_set_next (s, &next));
 433   g_assert_cmpint (next, ==, 1200);
 434   g_assert (hb_set_next (s, &next));
 435   g_assert_cmpint (next, ==, 20005);
 436   g_assert (!hb_set_next (s, &next));
 437   g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
 438
 439   next = HB_SET_VALUE_INVALID;
 440   g_assert (hb_set_previous (s, &next));
 441   g_assert_cmpint (next, ==, 20005);
 442   g_assert (hb_set_previous (s, &next));
 443   g_assert_cmpint (next, ==, 1200);
 444   g_assert (hb_set_previous (s, &next));
 445   g_assert_cmpint (next, ==, 1100);
 446   g_assert (hb_set_previous (s, &next));
 447   g_assert_cmpint (next, ==, 15);
 448   g_assert (hb_set_previous (s, &next));
 449   g_assert (hb_set_previous (s, &next));
 450   g_assert_cmpint (next, ==, 13);
 451   g_assert (hb_set_previous (s, &next));
 452   g_assert (hb_set_previous (s, &next));
 453   g_assert (hb_set_previous (s, &next));
 454   g_assert_cmpint (next, ==, 10);
 455   g_assert (hb_set_previous (s, &next));
 456   g_assert_cmpint (next, ==, 6);
 457   g_assert (!hb_set_previous (s, &next));
 458   g_assert_cmpint (next, ==, HB_SET_VALUE_INVALID);
 459
 460   first = last = HB_SET_VALUE_INVALID;
 461   g_assert (hb_set_next_range (s, &first, &last));
 462   g_assert_cmpint (first, ==, 6);
 463   g_assert_cmpint (last,  ==, 6);
 464   g_assert (hb_set_next_range (s, &first, &last));
 465   g_assert_cmpint (first, ==, 10);
 466   g_assert_cmpint (last,  ==, 15);
 467   g_assert (hb_set_next_range (s, &first, &last));
 468   g_assert_cmpint (first, ==, 1100);
 469   g_assert_cmpint (last,  ==, 1100);
 470   g_assert (hb_set_next_range (s, &first, &last));
 471   g_assert_cmpint (first, ==, 1200);
 472   g_assert_cmpint (last,  ==, 1200);
 473   g_assert (hb_set_next_range (s, &first, &last));
 474   g_assert_cmpint (first, ==, 20005);
 475   g_assert_cmpint (last,  ==, 20005);
 476   g_assert (!hb_set_next_range (s, &first, &last));
 477   g_assert_cmpint (first, ==, HB_SET_VALUE_INVALID);
 478   g_assert_cmpint (last,  ==, HB_SET_VALUE_INVALID);
 479
 480   first = last = HB_SET_VALUE_INVALID;
 481   g_assert (hb_set_previous_range (s, &first, &last));
 482   g_assert_cmpint (first, ==, 20005);
 483   g_assert_cmpint (last,  ==, 20005);
 484   g_assert (hb_set_previous_range (s, &first, &last));
 485   g_assert_cmpint (first, ==, 1200);
 486   g_assert_cmpint (last,  ==, 1200);
 487   g_assert (hb_set_previous_range (s, &first, &last));
 488   g_assert_cmpint (first, ==, 1100);
 489   g_assert_cmpint (last,  ==, 1100);
 490   g_assert (hb_set_previous_range (s, &first, &last));
 491   g_assert_cmpint (first, ==, 10);
 492   g_assert_cmpint (last,  ==, 15);
 493   g_assert (hb_set_previous_range (s, &first, &last));
 494   g_assert_cmpint (first, ==, 6);
 495   g_assert_cmpint (last,  ==, 6);
 496   g_assert (!hb_set_previous_range (s, &first, &last));
 497   g_assert_cmpint (first, ==, HB_SET_VALUE_INVALID);
 498   g_assert_cmpint (last,  ==, HB_SET_VALUE_INVALID);
 499
 500   hb_set_destroy (s);
 501 }
 502
 503 static void
 504 test_set_empty (void)
 505 {
 506   hb_set_t *b = hb_set_get_empty ();
 507
 508   g_assert (hb_set_get_empty ());
 509   g_assert (hb_set_get_empty () == b);
 510
 511   g_assert (!hb_set_allocation_successful (b));
 512
 513   test_empty (b);
 514
 515   hb_set_add (b, 13);
 516
 517   test_empty (b);
 518
 519   g_assert (!hb_set_allocation_successful (b));
 520
 521   hb_set_clear (b);
 522
 523   test_empty (b);
 524
 525   g_assert (!hb_set_allocation_successful (b));
 526
 527   hb_set_destroy (b);
 528 }
 529
 530 static void
 531 test_set_delrange (void)
 532 {
 533   const unsigned P = 512;       /* Page size. */
 534   struct { unsigned b, e; } ranges[] = {
 535     { 35, P-15 },               /* From page middle thru middle. */
 536     { P, P+100 },               /* From page start thru middle. */
 537     { P+300, P*2-1 },           /* From page middle thru end. */
 538     { P*3, P*4+100 },           /* From page start thru next page middle. */
 539     { P*4+300, P*6-1 },         /* From page middle thru next page end. */
 540     { P*6+200,P*8+100 },        /* From page middle covering one page thru page middle. */
 541     { P*9, P*10+105 },          /* From page start covering one page thru page middle. */
 542     { P*10+305, P*12-1 },       /* From page middle covering one page thru page end. */
 543     { P*13, P*15-1 },           /* From page start covering two pages thru page end. */
 544     { P*15+100, P*18+100 }      /* From page middle covering two pages thru page middle. */
 545   };
 546   unsigned n = sizeof (ranges) / sizeof(ranges[0]);
 547
 548   hb_set_t *s = hb_set_create ();
 549
 550   test_empty (s);
 551   for (unsigned int g = 0; g < ranges[n - 1].e + P; g += 2)
 552     hb_set_add (s, g);
 553
 554   hb_set_add (s, P*2-1);
 555   hb_set_add (s, P*6-1);
 556   hb_set_add (s, P*12-1);
 557   hb_set_add (s, P*15-1);
 558
 559   for (unsigned i = 0; i < n; i++)
 560     hb_set_del_range (s, ranges[i].b, ranges[i].e);
 561
 562   hb_set_del_range (s, P*13+5, P*15-10);        /* Deletion from deleted pages. */
 563
 564   for (unsigned i = 0; i < n; i++)
 565   {
 566     unsigned b = ranges[i].b;
 567     unsigned e = ranges[i].e;
 568     g_assert (hb_set_has (s, (b-2)&~1));
 569     while (b <= e)
 570       g_assert (!hb_set_has (s, b++));
 571     g_assert (hb_set_has (s, (e+2)&~1));
 572   }
 573
 574   hb_set_destroy (s);
 575 }
 576
 577 static const unsigned max_set_elements = -1;
 578
 579 static void
 580 test_set_inverted_basics (void)
 581 {
 582   // Tests:
 583   // add, del, has, get_population, is_empty, get_min, get_max
 584   // for inverted sets.
 585   hb_set_t *s = hb_set_create ();
 586   hb_set_invert (s);
 587
 588   g_assert_cmpint (hb_set_get_population (s), ==, max_set_elements);
 589   g_assert (hb_set_has (s, 0));
 590   g_assert (hb_set_has (s, 13));
 591   g_assert (hb_set_has (s, max_set_elements - 1));
 592   g_assert (!hb_set_is_empty (s));
 593   g_assert_cmpint (hb_set_get_min (s), ==, 0);
 594   g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 1);
 595
 596   hb_set_del (s, 13);
 597   g_assert (!hb_set_has (s, 13));
 598   g_assert_cmpint (hb_set_get_population (s), ==, max_set_elements - 1);
 599   g_assert_cmpint (hb_set_get_min (s), ==, 0);
 600   g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 1);
 601
 602   hb_set_add (s, 13);
 603   g_assert (hb_set_has (s, 13));
 604   g_assert_cmpint (hb_set_get_population (s), ==, max_set_elements);
 605
 606   hb_set_del (s, 0);
 607   hb_set_del (s, max_set_elements - 1);
 608   g_assert (!hb_set_has (s, 0));
 609   g_assert (hb_set_has (s, 13));
 610   g_assert (!hb_set_has (s, max_set_elements - 1));
 611   g_assert (!hb_set_is_empty (s));
 612   g_assert_cmpint (hb_set_get_population (s), ==, max_set_elements - 2);
 613   g_assert_cmpint (hb_set_get_min (s), ==, 1);
 614   g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 2);
 615
 616   hb_set_destroy (s);
 617 }
 618
 619 static void
 620 test_set_inverted_ranges (void)
 621 {
 622   // Tests:
 623   // add_range, del_range, has, get_population, is_empty, get_min, get_max
 624   // for inverted sets.
 625   hb_set_t *s = hb_set_create ();
 626   hb_set_invert (s);
 627
 628   hb_set_del_range (s, 41, 4000);
 629   hb_set_add_range (s, 78, 601);
 630
 631   g_assert (hb_set_has (s, 40));
 632   g_assert (!hb_set_has (s, 41));
 633   g_assert (!hb_set_has (s, 64));
 634   g_assert (!hb_set_has (s, 77));
 635   g_assert (hb_set_has (s, 78));
 636   g_assert (hb_set_has (s, 300));
 637   g_assert (hb_set_has (s, 601));
 638   g_assert (!hb_set_has (s, 602));
 639   g_assert (!hb_set_has (s, 3000));
 640   g_assert (!hb_set_has (s, 4000));
 641   g_assert (hb_set_has (s, 4001));
 642
 643   g_assert (!hb_set_is_empty (s));
 644   g_assert_cmpint (hb_set_get_population (s), ==, max_set_elements - 3436);
 645   g_assert_cmpint (hb_set_get_min (s), ==, 0);
 646   g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 1);
 647
 648   hb_set_del_range (s, 0, 37);
 649   g_assert (!hb_set_has (s, 0));
 650   g_assert (!hb_set_has (s, 37));
 651   g_assert (hb_set_has (s, 38));
 652   g_assert (!hb_set_is_empty (s));
 653   g_assert_cmpint (hb_set_get_population (s), ==,
 654                    max_set_elements - 3436 - 38);
 655   g_assert_cmpint (hb_set_get_min (s), ==, 38);
 656   g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 1);
 657
 658   hb_set_del_range (s, max_set_elements - 13, max_set_elements - 1);
 659   g_assert (!hb_set_has (s, max_set_elements - 1));
 660   g_assert (!hb_set_has (s, max_set_elements - 13));
 661   g_assert (hb_set_has (s, max_set_elements - 14));
 662
 663   g_assert (!hb_set_is_empty (s));
 664   g_assert_cmpint (hb_set_get_population (s), ==,
 665                    max_set_elements - 3436 - 38 - 13);
 666   g_assert_cmpint (hb_set_get_min (s), ==, 38);
 667   g_assert_cmpint (hb_set_get_max (s), ==, max_set_elements - 14);
 668
 669   hb_set_destroy (s);
 670 }
 671
 672 static void
 673 test_set_inverted_iteration_next (void)
 674 {
 675   // Tests:
 676   // next, next_range
 677   hb_set_t *s = hb_set_create ();
 678   hb_set_invert (s);
 679
 680   hb_set_del_range (s, 41, 4000);
 681   hb_set_add_range (s, 78, 601);
 682
 683   hb_codepoint_t cp = HB_SET_VALUE_INVALID;
 684   hb_codepoint_t start = 0;
 685   hb_codepoint_t end = 0;
 686   g_assert (hb_set_next (s, &cp));
 687   g_assert_cmpint (cp, ==, 0);
 688   g_assert (hb_set_next (s, &cp));
 689   g_assert_cmpint (cp, ==, 1);
 690
 691   g_assert (hb_set_next_range (s, &start, &end));
 692   g_assert_cmpint (start, ==, 1);
 693   g_assert_cmpint (end, ==, 40);
 694
 695   start = 40;
 696   end = 40;
 697   g_assert (hb_set_next_range (s, &start, &end));
 698   g_assert_cmpint (start, ==, 78);
 699   g_assert_cmpint (end, ==, 601);
 700
 701   start = 40;
 702   end = 57;
 703   g_assert (hb_set_next_range (s, &start, &end));
 704   g_assert_cmpint (start, ==, 78);
 705   g_assert_cmpint (end, ==, 601);
 706
 707   cp = 39;
 708   g_assert (hb_set_next (s, &cp));
 709   g_assert_cmpint (cp, ==, 40);
 710
 711   g_assert (hb_set_next (s, &cp));
 712   g_assert_cmpint (cp, ==, 78);
 713
 714   cp = 56;
 715   g_assert (hb_set_next (s, &cp));
 716   g_assert_cmpint (cp, ==, 78);
 717
 718   cp = 78;
 719   g_assert (hb_set_next (s, &cp));
 720   g_assert_cmpint (cp, ==, 79);
 721
 722   cp = 601;
 723   g_assert (hb_set_next (s, &cp));
 724   g_assert_cmpint (cp, ==, 4001);
 725
 726   cp = HB_SET_VALUE_INVALID;
 727   hb_set_del (s, 0);
 728   g_assert (hb_set_next (s, &cp));
 729   g_assert_cmpint (cp, ==, 1);
 730
 731   start = 0;
 732   end = 0;
 733   g_assert (hb_set_next_range (s, &start, &end));
 734   g_assert_cmpint (start, ==, 1);
 735   g_assert_cmpint (end, ==, 40);
 736
 737   cp = max_set_elements - 1;
 738   g_assert (!hb_set_next (s, &cp));
 739   g_assert_cmpint (cp, ==, HB_SET_VALUE_INVALID);
 740
 741   start = 4000;
 742   end = 4000;
 743   g_assert (hb_set_next_range (s, &start, &end));
 744   g_assert_cmpint (start, ==, 4001);
 745   g_assert_cmpint (end, ==, max_set_elements - 1);
 746
 747   start = max_set_elements - 1;
 748   end = max_set_elements - 1;
 749   g_assert (!hb_set_next_range (s, &start, &end));
 750   g_assert_cmpint (start, ==, HB_SET_VALUE_INVALID);
 751   g_assert_cmpint (end, ==, HB_SET_VALUE_INVALID);
 752
 753   cp = max_set_elements - 3;
 754   hb_set_del (s, max_set_elements - 1);
 755   g_assert (hb_set_next (s, &cp));
 756   g_assert_cmpint (cp, ==, max_set_elements - 2);
 757   g_assert (!hb_set_next (s, &cp));
 758   g_assert_cmpint (cp, ==, HB_SET_VALUE_INVALID);
 759
 760
 761   start = max_set_elements - 2;
 762   end = max_set_elements - 2;
 763   g_assert (!hb_set_next_range (s, &start, &end));
 764   g_assert_cmpint (start, ==, HB_SET_VALUE_INVALID);
 765   g_assert_cmpint (end, ==, HB_SET_VALUE_INVALID);
 766
 767   start = max_set_elements - 3;
 768   end = max_set_elements - 3;
 769   g_assert (hb_set_next_range (s, &start, &end));
 770   g_assert_cmpint (start, ==, max_set_elements - 2);
 771   g_assert_cmpint (end, ==, max_set_elements - 2);
 772
 773   hb_set_destroy (s);
 774 }
 775
 776 static void
 777 test_set_inverted_iteration_prev (void)
 778 {
 779   // Tests:
 780   // previous, previous_range
 781   hb_set_t *s = hb_set_create ();
 782   hb_set_invert (s);
 783
 784   hb_set_del_range (s, 41, 4000);
 785   hb_set_add_range (s, 78, 601);
 786
 787   hb_codepoint_t cp = HB_SET_VALUE_INVALID;
 788   hb_codepoint_t start = max_set_elements - 1;
 789   hb_codepoint_t end = max_set_elements - 1;
 790   g_assert (hb_set_previous (s, &cp));
 791   g_assert_cmpint (cp, ==, max_set_elements - 1);
 792   g_assert (hb_set_previous (s, &cp));
 793   g_assert_cmpint (cp, ==, max_set_elements - 2);
 794
 795   g_assert (hb_set_previous_range (s, &start, &end));
 796   g_assert_cmpint (start, ==, 4001);
 797   g_assert_cmpint (end, ==, max_set_elements - 2);
 798
 799   start = 4001;
 800   end = 4001;
 801   g_assert (hb_set_previous_range (s, &start, &end));
 802   g_assert_cmpint (start, ==, 78);
 803   g_assert_cmpint (end, ==, 601);
 804
 805   start = 2500;
 806   end = 3000;
 807   g_assert (hb_set_previous_range (s, &start, &end));
 808   g_assert_cmpint (start, ==, 78);
 809   g_assert_cmpint (end, ==, 601);
 810
 811   cp = 4002;
 812   g_assert (hb_set_previous (s, &cp));
 813   g_assert_cmpint (cp, ==, 4001);
 814
 815   g_assert (hb_set_previous (s, &cp));
 816   g_assert_cmpint (cp, ==, 601);
 817
 818   cp = 3500;
 819   g_assert (hb_set_previous (s, &cp));
 820   g_assert_cmpint (cp, ==, 601);
 821
 822   cp = 601;
 823   g_assert (hb_set_previous (s, &cp));
 824   g_assert_cmpint (cp, ==, 600);
 825
 826   cp = 78;
 827   g_assert (hb_set_previous (s, &cp));
 828   g_assert_cmpint (cp, ==, 40);
 829
 830   cp = HB_SET_VALUE_INVALID;
 831   hb_set_del (s, max_set_elements - 1);
 832   g_assert (hb_set_previous (s, &cp));
 833   g_assert_cmpint (cp, ==, max_set_elements - 2);
 834
 835   start = max_set_elements - 1;
 836   end = max_set_elements - 1;
 837   g_assert (hb_set_previous_range (s, &start, &end));
 838   g_assert_cmpint (start, ==, 4001);
 839   g_assert_cmpint (end, ==, max_set_elements - 2);
 840
 841   cp = 0;
 842   g_assert (!hb_set_previous (s, &cp));
 843   g_assert_cmpint (cp, ==, HB_SET_VALUE_INVALID);
 844
 845   cp = 40;
 846   g_assert (hb_set_previous (s, &cp));
 847   g_assert_cmpint (cp, ==, 39);
 848
 849   start = 40;
 850   end = 40;
 851   g_assert (hb_set_previous_range (s, &start, &end));
 852   g_assert_cmpint (start, ==, 0);
 853   g_assert_cmpint (end, ==, 39);
 854
 855   start = 0;
 856   end = 0;
 857   g_assert (!hb_set_previous_range (s, &start, &end));
 858   g_assert_cmpint (start, ==, HB_SET_VALUE_INVALID);
 859   g_assert_cmpint (end, ==, HB_SET_VALUE_INVALID);
 860
 861
 862   cp = 2;
 863   hb_set_del (s, 0);
 864   g_assert (hb_set_previous (s, &cp));
 865   g_assert_cmpint (cp, ==, 1);
 866   g_assert (!hb_set_previous (s, &cp));
 867   g_assert_cmpint (cp, ==, HB_SET_VALUE_INVALID);
 868
 869   start = 1;
 870   end = 1;
 871   g_assert (!hb_set_previous_range (s, &start, &end));
 872   g_assert_cmpint (start, ==, HB_SET_VALUE_INVALID);
 873   g_assert_cmpint (end, ==, HB_SET_VALUE_INVALID);
 874
 875   start = 2;
 876   end = 2;
 877   g_assert (hb_set_previous_range (s, &start, &end));
 878   g_assert_cmpint (start, ==, 1);
 879   g_assert_cmpint (end, ==, 1);
 880
 881   hb_set_destroy (s);
 882 }
 883
 884
 885 static void
 886 test_set_inverted_equality (void)
 887 {
 888   hb_set_t *a = hb_set_create ();
 889   hb_set_t *b = hb_set_create ();
 890   hb_set_invert (a);
 891   hb_set_invert (b);
 892
 893   g_assert (hb_set_is_equal (a, b));
 894   g_assert (hb_set_is_equal (b, a));
 895
 896   hb_set_add (a, 10);
 897   g_assert (hb_set_is_equal (a, b));
 898   g_assert (hb_set_is_equal (b, a));
 899
 900   hb_set_del (a, 42);
 901   g_assert (!hb_set_is_equal (a, b));
 902   g_assert (!hb_set_is_equal (b, a));
 903
 904   hb_set_del (b, 42);
 905   g_assert (hb_set_is_equal (a, b));
 906   g_assert (hb_set_is_equal (b, a));
 907
 908   hb_set_del_range (a, 43, 50);
 909   hb_set_del_range (a, 51, 76);
 910   hb_set_del_range (b, 43, 76);
 911   g_assert (hb_set_is_equal (a, b));
 912   g_assert (hb_set_is_equal (b, a));
 913
 914   hb_set_del (a, 0);
 915   g_assert (!hb_set_is_equal (a, b));
 916   g_assert (!hb_set_is_equal (b, a));
 917
 918   hb_set_del (b, 0);
 919   g_assert (hb_set_is_equal (a, b));
 920   g_assert (hb_set_is_equal (b, a));
 921
 922   hb_set_del (a, max_set_elements - 1);
 923   g_assert (!hb_set_is_equal (a, b));
 924   g_assert (!hb_set_is_equal (b, a));
 925
 926   hb_set_del (b, max_set_elements - 1);
 927   g_assert (hb_set_is_equal (a, b));
 928   g_assert (hb_set_is_equal (b, a));
 929
 930   hb_set_invert (a);
 931   g_assert (!hb_set_is_equal (a, b));
 932   g_assert (!hb_set_is_equal (b, a));
 933
 934   hb_set_invert (b);
 935   g_assert (hb_set_is_equal (a, b));
 936   g_assert (hb_set_is_equal (b, a));
 937
 938   hb_set_destroy (a);
 939   hb_set_destroy (b);
 940 }
 941
 942 typedef enum {
 943   UNION = 0,
 944   INTERSECT,
 945   SUBTRACT,
 946   SYM_DIFF,
 947   LAST,
 948 } set_operation;
 949
 950 static hb_set_t* prepare_set(hb_bool_t has_x,
 951                              hb_bool_t inverted,
 952                              hb_bool_t has_page,
 953                              hb_bool_t is_null)
 954 {
 955   static const hb_codepoint_t x = 13;
 956   if (is_null)
 957     return hb_set_get_empty ();
 958
 959   hb_set_t* s = hb_set_create ();
 960   if (inverted) hb_set_invert (s);
 961   if (has_page)
 962   {
 963     // Ensure a page exists for x.
 964     inverted ? hb_set_del (s, x) : hb_set_add (s, x);
 965   }
 966   if (has_x)
 967     hb_set_add (s, x);
 968   else
 969     hb_set_del (s, x);
 970
 971   return s;
 972 }
 973
 974 static hb_bool_t
 975 check_set_operations(hb_bool_t a_has_x,
 976                      hb_bool_t a_inverted,
 977                      hb_bool_t a_has_page,
 978                      hb_bool_t a_is_null,
 979                      hb_bool_t b_has_x,
 980                      hb_bool_t b_inverted,
 981                      hb_bool_t b_has_page,
 982                      hb_bool_t b_is_null,
 983                      set_operation op)
 984 {
 985   hb_codepoint_t x = 13;
 986   hb_set_t* a = prepare_set (a_has_x, a_inverted, a_has_page, a_is_null);
 987   hb_set_t* b = prepare_set (b_has_x, b_inverted, b_has_page, b_is_null);
 988
 989   const char* op_name;
 990   hb_bool_t has_expected;
 991   hb_bool_t should_have_x;
 992   switch (op) {
 993   default:
 994   case LAST:
 995   case UNION:
 996     op_name = "union";
 997     should_have_x = (a_has_x || b_has_x) && !a_is_null;
 998     hb_set_union (a, b);
 999     has_expected = (hb_set_has (a, x) == should_have_x);
1000     break;
1001   case INTERSECT:
1002     op_name = "intersect";
1003     should_have_x = (a_has_x && b_has_x) && !a_is_null;
1004     hb_set_intersect (a, b);
1005     has_expected = (hb_set_has (a, x) == should_have_x);
1006     break;
1007   case SUBTRACT:
1008     op_name = "subtract";
1009     should_have_x = (a_has_x && !b_has_x) && !a_is_null;
1010     hb_set_subtract (a, b);
1011     has_expected = (hb_set_has (a, x) == should_have_x);
1012     break;
1013   case SYM_DIFF:
1014     op_name = "sym_diff";
1015     should_have_x = (a_has_x ^ b_has_x) && !a_is_null;
1016     hb_set_symmetric_difference (a, b);
1017     has_expected = (hb_set_has (a, x) == should_have_x);
1018     break;
1019   }
1020
1021   printf ("%s%s%s%s %-9s %s%s%s%s == %s  [%s]\n",
1022           a_inverted ? "i" : " ",
1023           a_has_page ? "p" : " ",
1024           a_is_null ? "n" : " ",
1025           a_has_x ? "{13}" : "{}  ",
1026           op_name,
1027           b_inverted ? "i" : " ",
1028           b_has_page ? "p" : " ",
1029           b_is_null ? "n" : " ",
1030           b_has_x ? "{13}" : "{}  ",
1031           should_have_x ? "{13}" : "{}  ",
1032           has_expected ? "succeeded" : "failed");
1033
1034   hb_set_destroy (a);
1035   hb_set_destroy (b);
1036
1037   return has_expected;
1038 }
1039
1040 static void
1041 test_set_inverted_operations (void)
1042 {
1043   hb_bool_t all_succeeded = 1;
1044   for (hb_bool_t a_has_x = 0; a_has_x <= 1; a_has_x++) {
1045     for (hb_bool_t a_inverted = 0; a_inverted <= 1; a_inverted++) {
1046       for (hb_bool_t b_has_x = 0; b_has_x <= 1; b_has_x++) {
1047         for (hb_bool_t b_inverted = 0; b_inverted <= 1; b_inverted++) {
1048           for (hb_bool_t a_has_page = 0; a_has_page <= !(a_has_x ^ a_inverted); a_has_page++) {
1049             for (hb_bool_t b_has_page = 0; b_has_page <= !(b_has_x ^ b_inverted); b_has_page++) {
1050               for (hb_bool_t a_is_null = 0; a_is_null <= (!a_has_x && !a_has_page && !a_inverted); a_is_null++) {
1051                 for (hb_bool_t b_is_null = 0; b_is_null <= (!b_has_x && !b_has_page && !b_inverted); b_is_null++) {
1052                   for (set_operation op = UNION; op < LAST; op++) {
1053                     all_succeeded = check_set_operations (a_has_x, a_inverted, a_has_page, a_is_null,
1054                                                           b_has_x, b_inverted, b_has_page, b_is_null,
1055                                                           op)
1056                                     && all_succeeded;
1057                   }
1058                 }
1059               }
1060             }
1061           }
1062         }
1063       }
1064     }
1065   }
1066
1067   g_assert (all_succeeded);
1068 }
1069
1070 int
1071 main (int argc, char **argv)
1072 {
1073   hb_test_init (&argc, &argv);
1074
1075   hb_test_add (test_set_basic);
1076   hb_test_add (test_set_subsets);
1077   hb_test_add (test_set_algebra);
1078   hb_test_add (test_set_iter);
1079   hb_test_add (test_set_empty);
1080   hb_test_add (test_set_delrange);
1081
1082   hb_test_add (test_set_intersect_empty);
1083   hb_test_add (test_set_intersect_page_reduction);
1084   hb_test_add (test_set_union);
1085
1086   hb_test_add (test_set_inverted_basics);
1087   hb_test_add (test_set_inverted_ranges);
1088   hb_test_add (test_set_inverted_iteration_next);
1089   hb_test_add (test_set_inverted_iteration_prev);
1090   hb_test_add (test_set_inverted_equality);
1091   hb_test_add (test_set_inverted_operations);
1092
1093   return hb_test_run();
1094 }