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