lib/numberset.c

   1 /* numberset.c */
   2
   3 /*
   4  * Copyright (C) 2012-2016 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
  36
  37   if (start > end)
  38   {
  39     int tmp;
  40
  41
  42     tmp = start;
  43     start = end;
  44     end = tmp;
  45   }
  46
  47   if (start < min || end > max)
  48     return NUMBERSET_INVALID_RANGE;
  49
  50   nr = (number_range*)malloc(sizeof (number_range));
  51   if (!nr)
  52     return NUMBERSET_ALLOCATION_ERROR;
  53
  54   nr->start = start;
  55   nr->end = end;
  56   nr->next = NULL;
  57
  58   return nr;
  59 }
  60
  61
  62 number_range*
  63 number_set_prepend(number_range* list,
  64                    number_range* element)
  65 {
  66   if (!element)
  67     return list;
  68
  69   if (!list)
  70     return element;
  71
  72   if (element->start <= list->end)
  73   {
  74     if (element->end < list->start)
  75       return NUMBERSET_NOT_ASCENDING;
  76     else
  77       return NUMBERSET_OVERLAPPING_RANGES;
  78   }
  79
  80   if (element->start == list->end + 1)
  81   {
  82     /* merge adjacent ranges */
  83     list->end = element->end;
  84
  85     free(element);
  86
  87     return list;
  88   }
  89
  90   element->next = list;
  91
  92   return element;
  93 }
  94
  95
  96 number_range*
  97 number_set_insert(number_range* list,
  98                   number_range* element)
  99 {
 100   number_range* nr = list;
 101   number_range* prev;
 102
 103
 104   if (!element)
 105     return list;
 106
 107   if (!list)
 108     return element;
 109
 110   prev = NULL;
 111   while (nr)
 112   {
 113     if (element->start <= nr->end
 114         && element->end >= nr->start)
 115       return NUMBERSET_OVERLAPPING_RANGES;
 116
 117     /* merge adjacent ranges */
 118     if (element->start == nr->end + 1)
 119     {
 120       nr->end = element->end;
 121
 122       free(element);
 123
 124       return list;
 125     }
 126     if (element->end + 1 == nr->start)
 127     {
 128       nr->start = element->start;
 129
 130       free(element);
 131
 132       return list;
 133     }
 134
 135     /* insert element */
 136     if (element->start > nr->end)
 137     {
 138       if (prev)
 139         prev->next = element;
 140       element->next = nr;
 141
 142       return prev ? list : element;
 143     }
 144
 145     prev = nr;
 146     nr = nr->next;
 147   }
 148
 149   /* append element */
 150   prev->next = element;
 151   element->next = NULL;
 152
 153   return list;
 154 }
 155
 156
 157 number_range*
 158 number_set_normalize(number_range* list)
 159 {
 160   number_range* cur;
 161   number_range* prev;
 162
 163
 164   if (!list)
 165     return NULL;
 166
 167   prev = list;
 168   cur = list->next;
 169
 170   if (!cur)
 171     return list; /* only a single element, nothing to do */
 172
 173   while (cur)
 174   {
 175     if (prev->end + 1 == cur->start)
 176     {
 177       number_range* tmp;
 178
 179
 180       prev->end = cur->end;
 181
 182       tmp = cur;
 183       cur = cur->next;
 184       prev->next = cur;
 185
 186       free(tmp);
 187     }
 188     else
 189     {
 190       prev = cur;
 191       cur = cur->next;
 192     }
 193   }
 194
 195   return list;
 196 }
 197
 198
 199 number_range*
 200 number_set_reverse(number_range* list)
 201 {
 202   number_range* cur;
 203
 204
 205   cur = list;
 206   list = NULL;
 207
 208   while (cur)
 209   {
 210     number_range* tmp;
 211
 212
 213     tmp = cur;
 214     cur = cur->next;
 215     tmp->next = list;
 216     list = tmp;
 217   }
 218
 219   return list;
 220 }
 221
 222
 223 const char*
 224 number_set_parse(const char* s,
 225                  number_range** number_set,
 226                  int min,
 227                  int max)
 228 {
 229   number_range* cur = NULL;
 230   number_range* new_range;
 231
 232   const char* last_pos = s;
 233   int last_start = -1;
 234   int last_end = -1;
 235   int t;
 236   number_range* error_code = NULL;
 237
 238
 239   if (!s)
 240     return NULL;
 241
 242   if (min < 0)
 243     min = 0;
 244   if (max < 0)
 245     max = INT_MAX;
 246   if (min > max)
 247   {
 248     t = min;
 249     min = max;
 250     max = t;
 251   }
 252
 253   for (;;)
 254   {
 255     int digit;
 256     int n = -1;
 257     int m = -1;
 258
 259
 260     while (isspace(*s))
 261       s++;
 262
 263     if (*s == ',')
 264     {
 265       s++;
 266       continue;
 267     }
 268     else if (*s == '-')
 269     {
 270       last_pos = s;
 271       n = min;
 272     }
 273     else if (isdigit(*s))
 274     {
 275       last_pos = s;
 276       n = 0;
 277       do
 278       {
 279         digit = *s - '0';
 280         if (n > INT_MAX / 10
 281             || (n == INT_MAX / 10 && digit > 5))
 282         {
 283           error_code = NUMBERSET_OVERFLOW;
 284           break;
 285         }
 286
 287         n = n * 10 + digit;
 288         s++;
 289       } while (isdigit(*s));
 290
 291       if (error_code)
 292         break;
 293
 294       while (isspace(*s))
 295         s++;
 296     }
 297     else if (*s == '\0')
 298       break; /* end of data */
 299     else
 300     {
 301       error_code = NUMBERSET_INVALID_CHARACTER;
 302       break;
 303     }
 304
 305     if (*s == '-')
 306     {
 307       s++;
 308
 309       while (isspace(*s))
 310         s++;
 311
 312       if (isdigit(*s))
 313       {
 314         m = 0;
 315         do
 316         {
 317           digit = *s - '0';
 318           if (m > INT_MAX / 10
 319               || (m == INT_MAX / 10 && digit > 5))
 320           {
 321             error_code = NUMBERSET_OVERFLOW;
 322             break;
 323           }
 324
 325           m = m * 10 + digit;
 326           s++;
 327         } while (isdigit(*s));
 328
 329         if (error_code)
 330           break;
 331       }
 332     }
 333     else
 334       m = n;
 335
 336     if (m == -1)
 337       m = max;
 338
 339     if (m < n)
 340     {
 341       t = n;
 342       n = m;
 343       m = t;
 344     }
 345
 346     if (n < min || m > max)
 347     {
 348       error_code = NUMBERSET_INVALID_RANGE;
 349       break;
 350     }
 351
 352     if (last_end >= n)
 353     {
 354       if (last_start >= m)
 355         error_code = NUMBERSET_NOT_ASCENDING;
 356       else
 357         error_code = NUMBERSET_OVERLAPPING_RANGES;
 358       break;
 359     }
 360
 361     if (cur
 362         && last_end + 1 == n)
 363     {
 364       /* merge adjacent ranges */
 365       cur->end = m;
 366     }
 367     else
 368     {
 369       if (number_set)
 370       {
 371         new_range = (number_range*)malloc(sizeof (number_range));
 372         if (!new_range)
 373         {
 374           error_code = NUMBERSET_ALLOCATION_ERROR;
 375           break;
 376         }
 377
 378         /* prepend new range to list */
 379         new_range->start = n;
 380         new_range->end = m;
 381         new_range->next = cur;
 382         cur = new_range;
 383       }
 384     }
 385
 386     last_start = n;
 387     last_end = m;
 388   } /* end of loop */
 389
 390   if (error_code)
 391   {
 392     number_set_free(cur);
 393
 394     s = last_pos;
 395     if (number_set)
 396       *number_set = error_code;
 397   }
 398   else
 399   {
 400     /* success */
 401     if (number_set)
 402       *number_set = number_set_normalize(number_set_reverse(cur));
 403   }
 404
 405   return s;
 406 }
 407
 408
 409 void
 410 number_set_free(number_range* number_set)
 411 {
 412   number_range* nr = number_set;
 413
 414
 415   while (nr)
 416   {
 417     number_range* tmp;
 418
 419
 420     tmp = nr;
 421     nr = nr->next;
 422     free(tmp);
 423   }
 424 }
 425
 426
 427 char*
 428 number_set_show(number_range* number_set,
 429                 int min,
 430                 int max)
 431 {
 432   sds s;
 433   size_t len;
 434   char* res;
 435
 436   number_range* nr = number_set;
 437
 438   const char* comma;
 439
 440
 441   if (min < 0)
 442     min = 0;
 443   if (max < 0)
 444     max = INT_MAX;
 445   if (min > max)
 446   {
 447     int t;
 448
 449
 450     t = min;
 451     min = max;
 452     max = t;
 453   }
 454
 455   s = sdsempty();
 456
 457   while (nr)
 458   {
 459     if (nr->start > max)
 460       goto Exit;
 461     if (nr->end < min)
 462       goto Again;
 463
 464     comma = *s ? ", " : "";
 465
 466     if (nr->start == nr->end)
 467       s = sdscatprintf(s, "%s%i", comma, nr->start);
 468     else if (nr->start <= min
 469              && nr->end >= max)
 470       s = sdscatprintf(s, "-");
 471     else if (nr->start <= min)
 472       s = sdscatprintf(s, "-%i", nr->end);
 473     else if (nr->end >= max)
 474       s = sdscatprintf(s, "%s%i-", comma, nr->start);
 475     else
 476       s = sdscatprintf(s, "%s%i-%i", comma, nr->start, nr->end);
 477
 478   Again:
 479     nr = nr->next;
 480   }
 481
 482 Exit:
 483   if (!s)
 484     return NULL;
 485
 486   /* we return an empty string for an empty number set */
 487   /* (this is, number_set == NULL or unsuitable `min' and `max' values) */
 488   len = sdslen(s) + 1;
 489   res = (char*)malloc(len);
 490   if (res)
 491     memcpy(res, s, len);
 492
 493   sdsfree(s);
 494
 495   return res;
 496 }
 497
 498
 499 int
 500 number_set_is_element(number_range* number_set,
 501                       int number)
 502 {
 503   number_range* nr = number_set;
 504
 505
 506   while (nr)
 507   {
 508     if (number < nr->start)
 509       return 0;
 510     if (nr->start <= number
 511         && number <= nr->end)
 512       return 1;
 513     nr = nr->next;
 514   }
 515
 516   return 0;
 517 }
 518
 519
 520 int
 521 number_set_get_first(number_set_iter* iter_p)
 522 {
 523   if (!iter_p || !iter_p->range)
 524     return 0;
 525
 526   iter_p->val = iter_p->range->start;
 527
 528   return iter_p->val;
 529 }
 530
 531
 532 int
 533 number_set_get_next(number_set_iter* iter_p)
 534 {
 535   if (!iter_p || !iter_p->range)
 536     return 0;
 537
 538   iter_p->val++;
 539
 540   if (iter_p->val > iter_p->range->end)
 541   {
 542     iter_p->range = iter_p->range->next;
 543
 544     if (iter_p->range)
 545       iter_p->val = iter_p->range->start;
 546   }
 547
 548   return iter_p->val;
 549 }
 550
 551 /* end of numberset.c */