lib/numberset.c

   1 /* numberset.c */
   2
   3 /*
   4  * Copyright (C) 2012-2021 by Werner Lemberg.
   5  *
   6  * This file is part of the ttfautohint library, and may only be used,
   7  * modified, and distributed under the terms given in `COPYING'.  By
   8  * continuing to use, modify, or distribute this file you indicate that you
   9  * have read `COPYING' and understand and accept it fully.
  10  *
  11  * The file `COPYING' mentioned in the previous paragraph is distributed
  12  * with the ttfautohint library.
  13  */
  14
  15
  16 #include <config.h>
  17
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <ctype.h>
  22 #include <limits.h>
  23
  24 #include <sds.h>
  25 #include <numberset.h>
  26
  27
  28 number_range*
  29 number_set_new(int start,
  30                int end,
  31                int min,
  32                int max)
  33 {
  34   number_range* nr;
  35   int tmp;
  36
  37
  38   if (min < 0)
  39     min = 0;
  40   if (max < 0)
  41     max = INT_MAX;
  42   if (min > max)
  43   {
  44     tmp = min;
  45     min = max;
  46     max = tmp;
  47   }
  48
  49   if (start > end)
  50   {
  51     tmp = start;
  52     start = end;
  53     end = tmp;
  54   }
  55
  56   if (start < min || end > max)
  57     return NUMBERSET_INVALID_RANGE;
  58
  59   nr = (number_range*)malloc(sizeof (number_range));
  60   if (!nr)
  61     return NUMBERSET_ALLOCATION_ERROR;
  62
  63   nr->start = start;
  64   nr->end = end;
  65   nr->base = 0;
  66   nr->wrap = 0;
  67   nr->next = NULL;
  68
  69   return nr;
  70 }
  71
  72
  73 int
  74 wrap_range_check_wraps(size_t num_wraps,
  75                        int* wraps)
  76 {
  77   size_t i;
  78
  79
  80   /* `wraps' must have at least two elements */
  81   if (!wraps || num_wraps < 2)
  82     return 1;
  83
  84   /* first `wraps' element must be larger than or equal to -1 */
  85   if (wraps[0] < -1)
  86     return 1;
  87
  88   /* check that all elements of `wraps' are strictly ascending */
  89   for (i = 1; i < num_wraps; i++)
  90     if (wraps[i] <= wraps[i - 1])
  91       return 1;
  92
  93   return 0;
  94 }
  95
  96
  97 number_range*
  98 wrap_range_new(int start,
  99                int end,
 100                size_t num_wraps,
 101                int* wraps)
 102 {
 103   number_range* nr;
 104   size_t i;
 105   int s, e;
 106
 107
 108   if (num_wraps < 2)
 109     return NUMBERSET_INVALID_WRAP_RANGE;
 110
 111   if (start > end)
 112   {
 113     s = end;
 114     e = start;
 115   }
 116   else
 117   {
 118     s = start;
 119     e = end;
 120   }
 121
 122   /* search fitting interval in `wraps' */
 123   for (i = 1; i < num_wraps; i++)
 124   {
 125     if (s > wraps[i - 1] && e <= wraps[i])
 126       break;
 127   }
 128   if (i == num_wraps)
 129     return NUMBERSET_INVALID_WRAP_RANGE;
 130
 131   nr = (number_range*)malloc(sizeof (number_range));
 132   if (!nr)
 133     return NUMBERSET_ALLOCATION_ERROR;
 134
 135   nr->start = start;
 136   nr->end = end;
 137   nr->base = wraps[i - 1] + 1;
 138   nr->wrap = wraps[i];
 139   nr->next = NULL;
 140
 141   return nr;
 142 }
 143
 144
 145 number_range*
 146 number_set_prepend(number_range* list,
 147                    number_range* element)
 148 {
 149   if (!element)
 150     return list;
 151
 152   if (!list)
 153     return element;
 154
 155   /* `list' and `element' must both be normal integer ranges */
 156   if (list->base != list->wrap || element->base != element->wrap)
 157     return NUMBERSET_INVALID_RANGE;
 158
 159   if (element->start <= list->end)
 160   {
 161     if (element->end < list->start)
 162       return NUMBERSET_NOT_ASCENDING;
 163     else
 164       return NUMBERSET_OVERLAPPING_RANGES;
 165   }
 166
 167   if (element->start == list->end + 1)
 168   {
 169     /* merge adjacent ranges */
 170     list->end = element->end;
 171
 172     free(element);
 173
 174     return list;
 175   }
 176
 177   element->next = list;
 178
 179   return element;
 180 }
 181
 182
 183 number_range*
 184 number_set_prepend_unsorted(number_range* list,
 185                             number_range* element)
 186 {
 187   if (!element)
 188     return list;
 189
 190   if (!list)
 191     return element;
 192
 193   /* `list' and `element' must both be normal integer ranges */
 194   if (list->base != list->wrap || element->base != element->wrap)
 195     return NUMBERSET_INVALID_RANGE;
 196
 197   element->next = list;
 198
 199   return element;
 200 }
 201
 202
 203 number_range*
 204 wrap_range_prepend(number_range* list,
 205                    number_range* element)
 206 {
 207   if (!element)
 208     return list;
 209
 210   if (!list)
 211     return element;
 212
 213   /* `list' and `element' must both be wrap-around ranges */
 214   if (list->base == list->wrap || element->base == element->wrap)
 215     return NUMBERSET_INVALID_RANGE;
 216
 217   /* we explicitly assume that the [base;wrap] intervals */
 218   /* of `list' and `element' either don't overlap ... */
 219   if (element->base < list->base)
 220     return NUMBERSET_NOT_ASCENDING;
 221   if (element->base > list->base)
 222     goto prepend;
 223
 224   /* ... or are exactly the same; */
 225   /* in this case, we can't append if the list's range really wraps around */
 226   if (list->start > list->end)
 227     return NUMBERSET_OVERLAPPING_RANGES;
 228
 229   if (element->start <= list->end)
 230   {
 231     if (element->end < list->start)
 232       return NUMBERSET_NOT_ASCENDING;
 233     else
 234       return NUMBERSET_OVERLAPPING_RANGES;
 235   }
 236
 237   if (element->start > element->end)
 238   {
 239     number_range* nr = list->next;
 240
 241
 242     /* we must search backwards to check */
 243     /* whether the wrapped part of the range overlaps */
 244     /* with an already existing range */
 245     /* (in the same [base;wrap] interval) */
 246     while (nr)
 247     {
 248       if (element->base != nr->base)
 249         break;
 250       if (element->end > nr->start)
 251         return NUMBERSET_OVERLAPPING_RANGES;
 252
 253       nr = nr->next;
 254     }
 255   }
 256
 257 prepend:
 258   element->next = list;
 259
 260   return element;
 261 }
 262
 263
 264 number_range*
 265 number_set_insert(number_range* list,
 266                   number_range* element)
 267 {
 268   number_range* nr = list;
 269   number_range* prev;
 270
 271
 272   if (!element)
 273     return list;
 274
 275   if (!list)
 276     return element;
 277
 278   /* `list' and `element' must both be normal integer ranges */
 279   if (list->base != list->wrap || element->base != element->wrap)
 280     return NUMBERSET_INVALID_RANGE;
 281
 282   prev = NULL;
 283   while (nr)
 284   {
 285     if (element->start <= nr->end
 286         && element->end >= nr->start)
 287       return NUMBERSET_OVERLAPPING_RANGES;
 288
 289     /* merge adjacent ranges */
 290     if (element->end + 1 == nr->start)
 291     {
 292       nr->start = element->start;
 293
 294       free(element);
 295
 296       if (nr->next
 297           && nr->next->end + 1 == nr->start)
 298       {
 299         element = nr->next;
 300         element->end = nr->end;
 301         free(nr);
 302         return element;
 303       }
 304
 305       return list;
 306     }
 307
 308     /* insert element */
 309     if (element->start > nr->end)
 310     {
 311       /* merge adjacent ranges */
 312       if (nr->end + 1 == element->start)
 313       {
 314         nr->end = element->end;
 315         free(element);
 316         return list;
 317       }
 318
 319       if (prev)
 320         prev->next = element;
 321       element->next = nr;
 322
 323       return prev ? list : element;
 324     }
 325
 326     prev = nr;
 327     nr = nr->next;
 328   }
 329
 330   /* prepend element */
 331   prev->next = element;
 332   element->next = NULL;
 333
 334   return list;
 335 }
 336
 337
 338 number_range*
 339 wrap_range_insert(number_range* list,
 340                   number_range* element)
 341 {
 342   number_range* nr = list;
 343   number_range* prev;
 344
 345
 346   if (!element)
 347     return list;
 348
 349   if (!list)
 350     return element;
 351
 352   /* `list' and `element' must both be wrap-around ranges */
 353   if (list->base == list->wrap || element->base == element->wrap)
 354     return NUMBERSET_INVALID_RANGE;
 355
 356   prev = NULL;
 357   while (nr)
 358   {
 359     /* we explicitly assume that the [base;wrap] intervals */
 360     /* of `list' and `element' either don't overlap ... */
 361     if (element->base < nr->base)
 362       goto next;
 363     if (element->base > nr->base)
 364       goto insert;
 365
 366     /* ... or are exactly the same */
 367
 368     if (nr->start > nr->end)
 369     {
 370       /* range really wraps around */
 371       if (element->start > element->end)
 372         return NUMBERSET_OVERLAPPING_RANGES;
 373
 374       if (element->start <= nr->end
 375           || element->end >= nr->start)
 376         return NUMBERSET_OVERLAPPING_RANGES;
 377     }
 378     else
 379     {
 380       /* normal range */
 381       if (element->start <= nr->end
 382           && element->end >= nr->start)
 383         return NUMBERSET_OVERLAPPING_RANGES;
 384
 385       /* insert element */
 386       if (element->start > nr->end)
 387       {
 388       insert:
 389         if (prev)
 390           prev->next = element;
 391         element->next = nr;
 392
 393         return prev ? list : element;
 394       }
 395     }
 396
 397   next:
 398     prev = nr;
 399     nr = nr->next;
 400   }
 401
 402   /* prepend element */
 403   prev->next = element;
 404   element->next = NULL;
 405
 406   return list;
 407 }
 408
 409
 410 number_range*
 411 number_set_reverse(number_range* list)
 412 {
 413   number_range* cur;
 414
 415
 416   cur = list;
 417   list = NULL;
 418
 419   while (cur)
 420   {
 421     number_range* tmp;
 422
 423
 424     tmp = cur;
 425     cur = cur->next;
 426     tmp->next = list;
 427     list = tmp;
 428   }
 429
 430   return list;
 431 }
 432
 433
 434 const char*
 435 number_set_parse(const char* s,
 436                  number_range** number_set,
 437                  int min,
 438                  int max)
 439 {
 440   number_range* cur = NULL;
 441   number_range* new_range;
 442
 443   const char* last_pos = s;
 444   int last_start = -1;
 445   int last_end = -1;
 446   int t;
 447   number_range* error_code = NULL;
 448
 449
 450   if (!s)
 451     return NULL;
 452
 453   if (min < 0)
 454     min = 0;
 455   if (max < 0)
 456     max = INT_MAX;
 457   if (min > max)
 458   {
 459     t = min;
 460     min = max;
 461     max = t;
 462   }
 463
 464   for (;;)
 465   {
 466     int digit;
 467     int n = -1;
 468     int m = -1;
 469
 470
 471     while (isspace(*s))
 472       s++;
 473
 474     if (*s == ',')
 475     {
 476       s++;
 477       continue;
 478     }
 479     else if (*s == '-')
 480     {
 481       last_pos = s;
 482       n = min;
 483     }
 484     else if (isdigit(*s))
 485     {
 486       last_pos = s;
 487       n = 0;
 488       do
 489       {
 490         digit = *s - '0';
 491         if (n > INT_MAX / 10
 492             || (n == INT_MAX / 10 && digit > 5))
 493         {
 494           error_code = NUMBERSET_OVERFLOW;
 495           break;
 496         }
 497
 498         n = n * 10 + digit;
 499         s++;
 500       } while (isdigit(*s));
 501
 502       if (error_code)
 503         break;
 504
 505       while (isspace(*s))
 506         s++;
 507     }
 508     else if (*s == '\0')
 509       break; /* end of data */
 510     else
 511     {
 512       error_code = NUMBERSET_INVALID_CHARACTER;
 513       break;
 514     }
 515
 516     if (*s == '-')
 517     {
 518       s++;
 519
 520       while (isspace(*s))
 521         s++;
 522
 523       if (isdigit(*s))
 524       {
 525         m = 0;
 526         do
 527         {
 528           digit = *s - '0';
 529           if (m > INT_MAX / 10
 530               || (m == INT_MAX / 10 && digit > 5))
 531           {
 532             error_code = NUMBERSET_OVERFLOW;
 533             break;
 534           }
 535
 536           m = m * 10 + digit;
 537           s++;
 538         } while (isdigit(*s));
 539
 540         if (error_code)
 541           break;
 542       }
 543     }
 544     else
 545       m = n;
 546
 547     if (m == -1)
 548       m = max;
 549
 550     if (m < n)
 551     {
 552       t = n;
 553       n = m;
 554       m = t;
 555     }
 556
 557     if (n < min || m > max)
 558     {
 559       error_code = NUMBERSET_INVALID_RANGE;
 560       break;
 561     }
 562
 563     if (last_end >= n)
 564     {
 565       if (last_start >= m)
 566         error_code = NUMBERSET_NOT_ASCENDING;
 567       else
 568         error_code = NUMBERSET_OVERLAPPING_RANGES;
 569       break;
 570     }
 571
 572     if (cur
 573         && last_end + 1 == n)
 574     {
 575       /* merge adjacent ranges */
 576       cur->end = m;
 577     }
 578     else
 579     {
 580       if (number_set)
 581       {
 582         new_range = (number_range*)malloc(sizeof (number_range));
 583         if (!new_range)
 584         {
 585           error_code = NUMBERSET_ALLOCATION_ERROR;
 586           break;
 587         }
 588
 589         /* prepend new range to list */
 590         new_range->start = n;
 591         new_range->end = m;
 592         new_range->base = 0;
 593         new_range->wrap = 0;
 594         new_range->next = cur;
 595         cur = new_range;
 596       }
 597     }
 598
 599     last_start = n;
 600     last_end = m;
 601   } /* end of loop */
 602
 603   if (error_code)
 604   {
 605     number_set_free(cur);
 606
 607     s = last_pos;
 608     if (number_set)
 609       *number_set = error_code;
 610   }
 611   else
 612   {
 613     /* success */
 614     if (number_set)
 615       *number_set = number_set_reverse(cur);
 616   }
 617
 618   return s;
 619 }
 620
 621
 622 void
 623 number_set_free(number_range* number_set)
 624 {
 625   number_range* nr = number_set;
 626
 627
 628   while (nr)
 629   {
 630     number_range* tmp;
 631
 632
 633     tmp = nr;
 634     nr = nr->next;
 635     free(tmp);
 636   }
 637 }
 638
 639
 640 char*
 641 number_set_show(number_range* number_set,
 642                 int min,
 643                 int max)
 644 {
 645   sds s;
 646   size_t len;
 647   char* res;
 648
 649   number_range* nr = number_set;
 650
 651   const char* comma;
 652
 653
 654   if (nr && nr->base == nr->wrap)
 655   {
 656     if (min < 0)
 657       min = 0;
 658     if (max < 0)
 659       max = INT_MAX;
 660     if (min > max)
 661     {
 662       int t;
 663
 664
 665       t = min;
 666       min = max;
 667       max = t;
 668     }
 669   }
 670   else
 671   {
 672     /* `min' and `max' are meaningless for wrap-around ranges */
 673     min = INT_MIN;
 674     max = INT_MAX;
 675   }
 676
 677   s = sdsempty();
 678
 679   while (nr)
 680   {
 681     if (nr->start > max)
 682       goto Exit;
 683     if (nr->end < min)
 684       goto Again;
 685
 686     comma = *s ? ", " : "";
 687
 688     if (nr->start == nr->end)
 689       s = sdscatprintf(s, "%s%i", comma, nr->start);
 690     else if (nr->start <= min
 691              && nr->end >= max)
 692       s = sdscatprintf(s, "-");
 693     else if (nr->start <= min)
 694       s = sdscatprintf(s, "-%i", nr->end);
 695     else if (nr->end >= max)
 696       s = sdscatprintf(s, "%s%i-", comma, nr->start);
 697     else
 698       s = sdscatprintf(s, "%s%i-%i", comma, nr->start, nr->end);
 699
 700   Again:
 701     nr = nr->next;
 702   }
 703
 704 Exit:
 705   if (!s)
 706     return NULL;
 707
 708   /* we return an empty string for an empty number set */
 709   /* (this is, number_set == NULL or unsuitable `min' and `max' values) */
 710   len = sdslen(s) + 1;
 711   res = (char*)malloc(len);
 712   if (res)
 713     memcpy(res, s, len);
 714
 715   sdsfree(s);
 716
 717   return res;
 718 }
 719
 720
 721 int
 722 number_set_is_element(number_range* number_set,
 723                       int number)
 724 {
 725   number_range* nr = number_set;
 726
 727
 728   while (nr)
 729   {
 730     if (nr->start > nr->end)
 731     {
 732       if (number < nr->base)
 733         return 0;
 734       if (number <= nr->end)
 735         return 1;
 736       if ( number < nr->start)
 737         return 0;
 738       if (number <= nr->wrap)
 739         return 1;
 740     }
 741     else
 742     {
 743       if (number < nr->start)
 744         return 0;
 745       if (number <= nr->end)
 746         return 1;
 747     }
 748
 749     nr = nr->next;
 750   }
 751
 752   return 0;
 753 }
 754
 755
 756 int
 757 number_set_get_first(number_set_iter* iter_p)
 758 {
 759   if (!iter_p || !iter_p->range)
 760     return -1;
 761
 762   iter_p->val = iter_p->range->start;
 763
 764   return iter_p->val;
 765 }
 766
 767
 768 int
 769 number_set_get_next(number_set_iter* iter_p)
 770 {
 771   if (!iter_p || !iter_p->range)
 772     return -1;
 773
 774   iter_p->val++;
 775
 776   if (iter_p->range->start > iter_p->range->end)
 777   {
 778     /* range really wraps around */
 779     if (iter_p->val > iter_p->range->wrap)
 780       iter_p->val = iter_p->range->base;
 781     else if (iter_p->val < iter_p->range->start
 782              && iter_p->val > iter_p->range->end)
 783     {
 784       iter_p->range = iter_p->range->next;
 785
 786       if (iter_p->range)
 787         iter_p->val = iter_p->range->start;
 788       else
 789         return -1;
 790     }
 791   }
 792   else
 793   {
 794     if (iter_p->val > iter_p->range->end)
 795     {
 796       iter_p->range = iter_p->range->next;
 797
 798       if (iter_p->range)
 799         iter_p->val = iter_p->range->start;
 800       else
 801         return -1;
 802     }
 803   }
 804
 805   return iter_p->val;
 806 }
 807
 808 /* end of numberset.c */