autotroll.m4: Minor comment fixes.
[ttfautohint.git] / lib / numberset.c
blobbe1cc58dc1c4add92096386eb8e465b083f2ad35
1 /* numberset.c */
3 /*
4 * Copyright (C) 2012-2017 by Werner Lemberg.
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.
11 * The file `COPYING' mentioned in the previous paragraph is distributed
12 * with the ttfautohint library.
16 #include <config.h>
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <ctype.h>
22 #include <limits.h>
24 #include <sds.h>
25 #include <numberset.h>
28 number_range*
29 number_set_new(int start,
30 int end,
31 int min,
32 int max)
34 number_range* nr;
37 if (start > end)
39 int tmp;
42 tmp = start;
43 start = end;
44 end = tmp;
47 if (start < min || end > max)
48 return NUMBERSET_INVALID_RANGE;
50 nr = (number_range*)malloc(sizeof (number_range));
51 if (!nr)
52 return NUMBERSET_ALLOCATION_ERROR;
54 nr->start = start;
55 nr->end = end;
56 nr->next = NULL;
58 return nr;
62 number_range*
63 number_set_prepend(number_range* list,
64 number_range* element)
66 if (!element)
67 return list;
69 if (!list)
70 return element;
72 if (element->start <= list->end)
74 if (element->end < list->start)
75 return NUMBERSET_NOT_ASCENDING;
76 else
77 return NUMBERSET_OVERLAPPING_RANGES;
80 if (element->start == list->end + 1)
82 /* merge adjacent ranges */
83 list->end = element->end;
85 free(element);
87 return list;
90 element->next = list;
92 return element;
96 number_range*
97 number_set_insert(number_range* list,
98 number_range* element)
100 number_range* nr = list;
101 number_range* prev;
104 if (!element)
105 return list;
107 if (!list)
108 return element;
110 prev = NULL;
111 while (nr)
113 if (element->start <= nr->end
114 && element->end >= nr->start)
115 return NUMBERSET_OVERLAPPING_RANGES;
117 /* merge adjacent ranges */
118 if (element->start == nr->end + 1)
120 nr->end = element->end;
122 free(element);
124 return list;
126 if (element->end + 1 == nr->start)
128 nr->start = element->start;
130 free(element);
132 return list;
135 /* insert element */
136 if (element->start > nr->end)
138 if (prev)
139 prev->next = element;
140 element->next = nr;
142 return prev ? list : element;
145 prev = nr;
146 nr = nr->next;
149 /* append element */
150 prev->next = element;
151 element->next = NULL;
153 return list;
157 number_range*
158 number_set_normalize(number_range* list)
160 number_range* cur;
161 number_range* prev;
164 if (!list)
165 return NULL;
167 prev = list;
168 cur = list->next;
170 if (!cur)
171 return list; /* only a single element, nothing to do */
173 while (cur)
175 if (prev->end + 1 == cur->start)
177 number_range* tmp;
180 prev->end = cur->end;
182 tmp = cur;
183 cur = cur->next;
184 prev->next = cur;
186 free(tmp);
188 else
190 prev = cur;
191 cur = cur->next;
195 return list;
199 number_range*
200 number_set_reverse(number_range* list)
202 number_range* cur;
205 cur = list;
206 list = NULL;
208 while (cur)
210 number_range* tmp;
213 tmp = cur;
214 cur = cur->next;
215 tmp->next = list;
216 list = tmp;
219 return list;
223 const char*
224 number_set_parse(const char* s,
225 number_range** number_set,
226 int min,
227 int max)
229 number_range* cur = NULL;
230 number_range* new_range;
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;
239 if (!s)
240 return NULL;
242 if (min < 0)
243 min = 0;
244 if (max < 0)
245 max = INT_MAX;
246 if (min > max)
248 t = min;
249 min = max;
250 max = t;
253 for (;;)
255 int digit;
256 int n = -1;
257 int m = -1;
260 while (isspace(*s))
261 s++;
263 if (*s == ',')
265 s++;
266 continue;
268 else if (*s == '-')
270 last_pos = s;
271 n = min;
273 else if (isdigit(*s))
275 last_pos = s;
276 n = 0;
279 digit = *s - '0';
280 if (n > INT_MAX / 10
281 || (n == INT_MAX / 10 && digit > 5))
283 error_code = NUMBERSET_OVERFLOW;
284 break;
287 n = n * 10 + digit;
288 s++;
289 } while (isdigit(*s));
291 if (error_code)
292 break;
294 while (isspace(*s))
295 s++;
297 else if (*s == '\0')
298 break; /* end of data */
299 else
301 error_code = NUMBERSET_INVALID_CHARACTER;
302 break;
305 if (*s == '-')
307 s++;
309 while (isspace(*s))
310 s++;
312 if (isdigit(*s))
314 m = 0;
317 digit = *s - '0';
318 if (m > INT_MAX / 10
319 || (m == INT_MAX / 10 && digit > 5))
321 error_code = NUMBERSET_OVERFLOW;
322 break;
325 m = m * 10 + digit;
326 s++;
327 } while (isdigit(*s));
329 if (error_code)
330 break;
333 else
334 m = n;
336 if (m == -1)
337 m = max;
339 if (m < n)
341 t = n;
342 n = m;
343 m = t;
346 if (n < min || m > max)
348 error_code = NUMBERSET_INVALID_RANGE;
349 break;
352 if (last_end >= n)
354 if (last_start >= m)
355 error_code = NUMBERSET_NOT_ASCENDING;
356 else
357 error_code = NUMBERSET_OVERLAPPING_RANGES;
358 break;
361 if (cur
362 && last_end + 1 == n)
364 /* merge adjacent ranges */
365 cur->end = m;
367 else
369 if (number_set)
371 new_range = (number_range*)malloc(sizeof (number_range));
372 if (!new_range)
374 error_code = NUMBERSET_ALLOCATION_ERROR;
375 break;
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;
386 last_start = n;
387 last_end = m;
388 } /* end of loop */
390 if (error_code)
392 number_set_free(cur);
394 s = last_pos;
395 if (number_set)
396 *number_set = error_code;
398 else
400 /* success */
401 if (number_set)
402 *number_set = number_set_normalize(number_set_reverse(cur));
405 return s;
409 void
410 number_set_free(number_range* number_set)
412 number_range* nr = number_set;
415 while (nr)
417 number_range* tmp;
420 tmp = nr;
421 nr = nr->next;
422 free(tmp);
427 char*
428 number_set_show(number_range* number_set,
429 int min,
430 int max)
432 sds s;
433 size_t len;
434 char* res;
436 number_range* nr = number_set;
438 const char* comma;
441 if (min < 0)
442 min = 0;
443 if (max < 0)
444 max = INT_MAX;
445 if (min > max)
447 int t;
450 t = min;
451 min = max;
452 max = t;
455 s = sdsempty();
457 while (nr)
459 if (nr->start > max)
460 goto Exit;
461 if (nr->end < min)
462 goto Again;
464 comma = *s ? ", " : "";
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);
478 Again:
479 nr = nr->next;
482 Exit:
483 if (!s)
484 return NULL;
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);
493 sdsfree(s);
495 return res;
500 number_set_is_element(number_range* number_set,
501 int number)
503 number_range* nr = number_set;
506 while (nr)
508 if (number < nr->start)
509 return 0;
510 if (nr->start <= number
511 && number <= nr->end)
512 return 1;
513 nr = nr->next;
516 return 0;
521 number_set_get_first(number_set_iter* iter_p)
523 if (!iter_p || !iter_p->range)
524 return 0;
526 iter_p->val = iter_p->range->start;
528 return iter_p->val;
533 number_set_get_next(number_set_iter* iter_p)
535 if (!iter_p || !iter_p->range)
536 return 0;
538 iter_p->val++;
540 if (iter_p->val > iter_p->range->end)
542 iter_p->range = iter_p->range->next;
544 if (iter_p->range)
545 iter_p->val = iter_p->range->start;
548 return iter_p->val;
551 /* end of numberset.c */