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