lib/numberset.c

   1 /* numberset.c */
   2
   3 /*
   4  * Copyright (C) 2012-2014 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 (list
  81       && element->start == list->end + 1)
  82   {
  83     /* merge adjacent ranges */
  84     list->end = element->end;
  85
  86     free(element);
  87
  88     return list;
  89   }
  90
  91   element->next = list;
  92
  93   return element;
  94 }
  95
  96
  97 number_range*
  98 number_set_reverse(number_range* list)
  99 {
 100   number_range* cur;
 101
 102
 103   cur = list;
 104   list = NULL;
 105
 106   while (cur)
 107   {
 108     number_range* tmp;
 109
 110
 111     tmp = cur;
 112     cur = cur->next;
 113     tmp->next = list;
 114     list = tmp;
 115   }
 116
 117   return list;
 118 }
 119
 120
 121 const char*
 122 number_set_parse(const char* s,
 123                  number_range** number_set,
 124                  int min,
 125                  int max)
 126 {
 127   number_range* cur = NULL;
 128   number_range* new_range;
 129   number_range* tmp;
 130
 131   const char* last_pos = s;
 132   int last_start = -1;
 133   int last_end = -1;
 134   int t;
 135   number_range* error_code = NULL;
 136
 137
 138   if (!s)
 139     return NULL;
 140
 141   if (min < 0)
 142     min = 0;
 143   if (max < 0)
 144     max = INT_MAX;
 145   if (min > max)
 146   {
 147     t = min;
 148     min = max;
 149     max = t;
 150   }
 151
 152   for (;;)
 153   {
 154     int digit;
 155     int n = -1;
 156     int m = -1;
 157
 158
 159     while (isspace(*s))
 160       s++;
 161
 162     if (*s == ',')
 163     {
 164       s++;
 165       continue;
 166     }
 167     else if (*s == '-')
 168     {
 169       last_pos = s;
 170       n = min;
 171     }
 172     else if (isdigit(*s))
 173     {
 174       last_pos = s;
 175       n = 0;
 176       do
 177       {
 178         digit = *s - '0';
 179         if (n > INT_MAX / 10
 180             || (n == INT_MAX / 10 && digit > 5))
 181         {
 182           error_code = NUMBERSET_OVERFLOW;
 183           break;
 184         }
 185
 186         n = n * 10 + digit;
 187         s++;
 188       } while (isdigit(*s));
 189
 190       if (error_code)
 191         break;
 192
 193       while (isspace(*s))
 194         s++;
 195     }
 196     else if (*s == '\0')
 197       break; /* end of data */
 198     else
 199     {
 200       error_code = NUMBERSET_INVALID_CHARACTER;
 201       break;
 202     }
 203
 204     if (*s == '-')
 205     {
 206       s++;
 207
 208       while (isspace(*s))
 209         s++;
 210
 211       if (isdigit(*s))
 212       {
 213         m = 0;
 214         do
 215         {
 216           digit = *s - '0';
 217           if (m > INT_MAX / 10
 218               || (m == INT_MAX / 10 && digit > 5))
 219           {
 220             error_code = NUMBERSET_OVERFLOW;
 221             break;
 222           }
 223
 224           m = m * 10 + digit;
 225           s++;
 226         } while (isdigit(*s));
 227
 228         if (error_code)
 229           break;
 230       }
 231     }
 232     else
 233       m = n;
 234
 235     if (m == -1)
 236       m = max;
 237
 238     if (m < n)
 239     {
 240       t = n;
 241       n = m;
 242       m = t;
 243     }
 244
 245     if (n < min || m > max)
 246     {
 247       error_code = NUMBERSET_INVALID_RANGE;
 248       break;
 249     }
 250
 251     if (last_end >= n)
 252     {
 253       if (last_start >= m)
 254         error_code = NUMBERSET_NOT_ASCENDING;
 255       else
 256         error_code = NUMBERSET_OVERLAPPING_RANGES;
 257       break;
 258     }
 259
 260     if (cur
 261         && last_end + 1 == n)
 262     {
 263       /* merge adjacent ranges */
 264       cur->end = m;
 265     }
 266     else
 267     {
 268       if (number_set)
 269       {
 270         new_range = (number_range*)malloc(sizeof (number_range));
 271         if (!new_range)
 272         {
 273           error_code = NUMBERSET_ALLOCATION_ERROR;
 274           break;
 275         }
 276
 277         /* prepend new range to list */
 278         new_range->start = n;
 279         new_range->end = m;
 280         new_range->next = cur;
 281         cur = new_range;
 282       }
 283     }
 284
 285     last_start = n;
 286     last_end = m;
 287   } /* end of loop */
 288
 289   if (error_code)
 290   {
 291     number_set_free(cur);
 292
 293     s = last_pos;
 294     if (number_set)
 295       *number_set = error_code;
 296   }
 297   else
 298   {
 299     /* success; now reverse list to have elements in ascending order */
 300     number_range* list = NULL;
 301
 302
 303     while (cur)
 304     {
 305       tmp = cur;
 306       cur = cur->next;
 307       tmp->next = list;
 308       list = tmp;
 309     }
 310
 311     if (number_set)
 312       *number_set = list;
 313   }
 314
 315   return s;
 316 }
 317
 318
 319 void
 320 number_set_free(number_range* number_set)
 321 {
 322   number_range* nr = number_set;
 323
 324
 325   while (nr)
 326   {
 327     number_range* tmp;
 328
 329
 330     tmp = nr;
 331     nr = nr->next;
 332     free(tmp);
 333   }
 334 }
 335
 336
 337 char*
 338 number_set_show(number_range* number_set,
 339                 int min,
 340                 int max)
 341 {
 342   sds s;
 343   size_t len;
 344   char* res;
 345
 346   number_range* nr = number_set;
 347
 348   const char *comma;
 349
 350
 351   if (min < 0)
 352     min = 0;
 353   if (max < 0)
 354     max = INT_MAX;
 355   if (min > max)
 356   {
 357     int t;
 358
 359
 360     t = min;
 361     min = max;
 362     max = t;
 363   }
 364
 365   s = sdsempty();
 366
 367   while (nr)
 368   {
 369     if (nr->start > max)
 370       goto Exit;
 371     if (nr->end < min)
 372       goto Again;
 373
 374     comma = *s ? ", " : "";
 375
 376     if (nr->start == nr->end)
 377       s = sdscatprintf(s, "%s%i", comma, nr->start);
 378     else if (nr->start <= min
 379              && nr->end >= max)
 380       s = sdscatprintf(s, "-");
 381     else if (nr->start <= min)
 382       s = sdscatprintf(s, "-%i", nr->end);
 383     else if (nr->end >= max)
 384       s = sdscatprintf(s, "%s%i-", comma, nr->start);
 385     else
 386       s = sdscatprintf(s, "%s%i-%i", comma, nr->start, nr->end);
 387
 388   Again:
 389     nr = nr->next;
 390   }
 391
 392 Exit:
 393   if (!s)
 394     return NULL;
 395
 396   /* we return an empty string for an empty number set */
 397   /* (this is, number_set == NULL or unsuitable `min' and `max' values) */
 398   len = sdslen(s) + 1;
 399   res = (char*)malloc(len);
 400   if (res)
 401     memcpy(res, s, len);
 402
 403   sdsfree(s);
 404
 405   return res;
 406 }
 407
 408
 409 int
 410 number_set_is_element(number_range* number_set,
 411                       int number)
 412 {
 413   number_range* nr = number_set;
 414
 415
 416   while (nr)
 417   {
 418     if (number < nr->start)
 419       return 0;
 420     if (nr->start <= number
 421         && number <= nr->end)
 422       return 1;
 423     nr = nr->next;
 424   }
 425
 426   return 0;
 427 }
 428
 429
 430 int
 431 number_set_get_first(number_set_iter* iter_p)
 432 {
 433   if (!iter_p || !iter_p->range)
 434     return 0;
 435
 436   iter_p->val = iter_p->range->start;
 437
 438   return iter_p->val;
 439 }
 440
 441
 442 int
 443 number_set_get_next(number_set_iter* iter_p)
 444 {
 445   if (!iter_p || !iter_p->range)
 446     return 0;
 447
 448   iter_p->val++;
 449
 450   if (iter_p->val > iter_p->range->end)
 451   {
 452     iter_p->range = iter_p->range->next;
 453
 454     if (iter_p->range)
 455       iter_p->val = iter_p->range->start;
 456   }
 457
 458   return iter_p->val;
 459 }
 460
 461 /* end of numberset.c */