lib/numberset.c

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