Update gnulib.
[ttfautohint.git] / lib / numberset.c
blob00db7c6f4089667311d0608280dd14e2cac63b74
1 /* numberset.c */
3 /*
4 * Copyright (C) 2012-2021 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;
35 int tmp;
38 if (min < 0)
39 min = 0;
40 if (max < 0)
41 max = INT_MAX;
42 if (min > max)
44 tmp = min;
45 min = max;
46 max = tmp;
49 if (start > end)
51 tmp = start;
52 start = end;
53 end = tmp;
56 if (start < min || end > max)
57 return NUMBERSET_INVALID_RANGE;
59 nr = (number_range*)malloc(sizeof (number_range));
60 if (!nr)
61 return NUMBERSET_ALLOCATION_ERROR;
63 nr->start = start;
64 nr->end = end;
65 nr->base = 0;
66 nr->wrap = 0;
67 nr->next = NULL;
69 return nr;
73 int
74 wrap_range_check_wraps(size_t num_wraps,
75 int* wraps)
77 size_t i;
80 /* `wraps' must have at least two elements */
81 if (!wraps || num_wraps < 2)
82 return 1;
84 /* first `wraps' element must be larger than or equal to -1 */
85 if (wraps[0] < -1)
86 return 1;
88 /* check that all elements of `wraps' are strictly ascending */
89 for (i = 1; i < num_wraps; i++)
90 if (wraps[i] <= wraps[i - 1])
91 return 1;
93 return 0;
97 number_range*
98 wrap_range_new(int start,
99 int end,
100 size_t num_wraps,
101 int* wraps)
103 number_range* nr;
104 size_t i;
105 int s, e;
108 if (num_wraps < 2)
109 return NUMBERSET_INVALID_WRAP_RANGE;
111 if (start > end)
113 s = end;
114 e = start;
116 else
118 s = start;
119 e = end;
122 /* search fitting interval in `wraps' */
123 for (i = 1; i < num_wraps; i++)
125 if (s > wraps[i - 1] && e <= wraps[i])
126 break;
128 if (i == num_wraps)
129 return NUMBERSET_INVALID_WRAP_RANGE;
131 nr = (number_range*)malloc(sizeof (number_range));
132 if (!nr)
133 return NUMBERSET_ALLOCATION_ERROR;
135 nr->start = start;
136 nr->end = end;
137 nr->base = wraps[i - 1] + 1;
138 nr->wrap = wraps[i];
139 nr->next = NULL;
141 return nr;
145 number_range*
146 number_set_prepend(number_range* list,
147 number_range* element)
149 if (!element)
150 return list;
152 if (!list)
153 return element;
155 /* `list' and `element' must both be normal integer ranges */
156 if (list->base != list->wrap || element->base != element->wrap)
157 return NUMBERSET_INVALID_RANGE;
159 if (element->start <= list->end)
161 if (element->end < list->start)
162 return NUMBERSET_NOT_ASCENDING;
163 else
164 return NUMBERSET_OVERLAPPING_RANGES;
167 if (element->start == list->end + 1)
169 /* merge adjacent ranges */
170 list->end = element->end;
172 free(element);
174 return list;
177 element->next = list;
179 return element;
183 number_range*
184 number_set_prepend_unsorted(number_range* list,
185 number_range* element)
187 if (!element)
188 return list;
190 if (!list)
191 return element;
193 /* `list' and `element' must both be normal integer ranges */
194 if (list->base != list->wrap || element->base != element->wrap)
195 return NUMBERSET_INVALID_RANGE;
197 element->next = list;
199 return element;
203 number_range*
204 wrap_range_prepend(number_range* list,
205 number_range* element)
207 if (!element)
208 return list;
210 if (!list)
211 return element;
213 /* `list' and `element' must both be wrap-around ranges */
214 if (list->base == list->wrap || element->base == element->wrap)
215 return NUMBERSET_INVALID_RANGE;
217 /* we explicitly assume that the [base;wrap] intervals */
218 /* of `list' and `element' either don't overlap ... */
219 if (element->base < list->base)
220 return NUMBERSET_NOT_ASCENDING;
221 if (element->base > list->base)
222 goto prepend;
224 /* ... or are exactly the same; */
225 /* in this case, we can't append if the list's range really wraps around */
226 if (list->start > list->end)
227 return NUMBERSET_OVERLAPPING_RANGES;
229 if (element->start <= list->end)
231 if (element->end < list->start)
232 return NUMBERSET_NOT_ASCENDING;
233 else
234 return NUMBERSET_OVERLAPPING_RANGES;
237 if (element->start > element->end)
239 number_range* nr = list->next;
242 /* we must search backwards to check */
243 /* whether the wrapped part of the range overlaps */
244 /* with an already existing range */
245 /* (in the same [base;wrap] interval) */
246 while (nr)
248 if (element->base != nr->base)
249 break;
250 if (element->end > nr->start)
251 return NUMBERSET_OVERLAPPING_RANGES;
253 nr = nr->next;
257 prepend:
258 element->next = list;
260 return element;
264 number_range*
265 number_set_insert(number_range* list,
266 number_range* element)
268 number_range* nr = list;
269 number_range* prev;
272 if (!element)
273 return list;
275 if (!list)
276 return element;
278 /* `list' and `element' must both be normal integer ranges */
279 if (list->base != list->wrap || element->base != element->wrap)
280 return NUMBERSET_INVALID_RANGE;
282 prev = NULL;
283 while (nr)
285 if (element->start <= nr->end
286 && element->end >= nr->start)
287 return NUMBERSET_OVERLAPPING_RANGES;
289 /* merge adjacent ranges */
290 if (element->end + 1 == nr->start)
292 nr->start = element->start;
294 free(element);
296 if (nr->next
297 && nr->next->end + 1 == nr->start)
299 element = nr->next;
300 element->end = nr->end;
301 free(nr);
302 return element;
305 return list;
308 /* insert element */
309 if (element->start > nr->end)
311 /* merge adjacent ranges */
312 if (nr->end + 1 == element->start)
314 nr->end = element->end;
315 free(element);
316 return list;
319 if (prev)
320 prev->next = element;
321 element->next = nr;
323 return prev ? list : element;
326 prev = nr;
327 nr = nr->next;
330 /* prepend element */
331 prev->next = element;
332 element->next = NULL;
334 return list;
338 number_range*
339 wrap_range_insert(number_range* list,
340 number_range* element)
342 number_range* nr = list;
343 number_range* prev;
346 if (!element)
347 return list;
349 if (!list)
350 return element;
352 /* `list' and `element' must both be wrap-around ranges */
353 if (list->base == list->wrap || element->base == element->wrap)
354 return NUMBERSET_INVALID_RANGE;
356 prev = NULL;
357 while (nr)
359 /* we explicitly assume that the [base;wrap] intervals */
360 /* of `list' and `element' either don't overlap ... */
361 if (element->base < nr->base)
362 goto next;
363 if (element->base > nr->base)
364 goto insert;
366 /* ... or are exactly the same */
368 if (nr->start > nr->end)
370 /* range really wraps around */
371 if (element->start > element->end)
372 return NUMBERSET_OVERLAPPING_RANGES;
374 if (element->start <= nr->end
375 || element->end >= nr->start)
376 return NUMBERSET_OVERLAPPING_RANGES;
378 else
380 /* normal range */
381 if (element->start <= nr->end
382 && element->end >= nr->start)
383 return NUMBERSET_OVERLAPPING_RANGES;
385 /* insert element */
386 if (element->start > nr->end)
388 insert:
389 if (prev)
390 prev->next = element;
391 element->next = nr;
393 return prev ? list : element;
397 next:
398 prev = nr;
399 nr = nr->next;
402 /* prepend element */
403 prev->next = element;
404 element->next = NULL;
406 return list;
410 number_range*
411 number_set_reverse(number_range* list)
413 number_range* cur;
416 cur = list;
417 list = NULL;
419 while (cur)
421 number_range* tmp;
424 tmp = cur;
425 cur = cur->next;
426 tmp->next = list;
427 list = tmp;
430 return list;
434 const char*
435 number_set_parse(const char* s,
436 number_range** number_set,
437 int min,
438 int max)
440 number_range* cur = NULL;
441 number_range* new_range;
443 const char* last_pos = s;
444 int last_start = -1;
445 int last_end = -1;
446 int t;
447 number_range* error_code = NULL;
450 if (!s)
451 return NULL;
453 if (min < 0)
454 min = 0;
455 if (max < 0)
456 max = INT_MAX;
457 if (min > max)
459 t = min;
460 min = max;
461 max = t;
464 for (;;)
466 int digit;
467 int n = -1;
468 int m = -1;
471 while (isspace(*s))
472 s++;
474 if (*s == ',')
476 s++;
477 continue;
479 else if (*s == '-')
481 last_pos = s;
482 n = min;
484 else if (isdigit(*s))
486 last_pos = s;
487 n = 0;
490 digit = *s - '0';
491 if (n > INT_MAX / 10
492 || (n == INT_MAX / 10 && digit > 5))
494 error_code = NUMBERSET_OVERFLOW;
495 break;
498 n = n * 10 + digit;
499 s++;
500 } while (isdigit(*s));
502 if (error_code)
503 break;
505 while (isspace(*s))
506 s++;
508 else if (*s == '\0')
509 break; /* end of data */
510 else
512 error_code = NUMBERSET_INVALID_CHARACTER;
513 break;
516 if (*s == '-')
518 s++;
520 while (isspace(*s))
521 s++;
523 if (isdigit(*s))
525 m = 0;
528 digit = *s - '0';
529 if (m > INT_MAX / 10
530 || (m == INT_MAX / 10 && digit > 5))
532 error_code = NUMBERSET_OVERFLOW;
533 break;
536 m = m * 10 + digit;
537 s++;
538 } while (isdigit(*s));
540 if (error_code)
541 break;
544 else
545 m = n;
547 if (m == -1)
548 m = max;
550 if (m < n)
552 t = n;
553 n = m;
554 m = t;
557 if (n < min || m > max)
559 error_code = NUMBERSET_INVALID_RANGE;
560 break;
563 if (last_end >= n)
565 if (last_start >= m)
566 error_code = NUMBERSET_NOT_ASCENDING;
567 else
568 error_code = NUMBERSET_OVERLAPPING_RANGES;
569 break;
572 if (cur
573 && last_end + 1 == n)
575 /* merge adjacent ranges */
576 cur->end = m;
578 else
580 if (number_set)
582 new_range = (number_range*)malloc(sizeof (number_range));
583 if (!new_range)
585 error_code = NUMBERSET_ALLOCATION_ERROR;
586 break;
589 /* prepend new range to list */
590 new_range->start = n;
591 new_range->end = m;
592 new_range->base = 0;
593 new_range->wrap = 0;
594 new_range->next = cur;
595 cur = new_range;
599 last_start = n;
600 last_end = m;
601 } /* end of loop */
603 if (error_code)
605 number_set_free(cur);
607 s = last_pos;
608 if (number_set)
609 *number_set = error_code;
611 else
613 /* success */
614 if (number_set)
615 *number_set = number_set_reverse(cur);
618 return s;
622 void
623 number_set_free(number_range* number_set)
625 number_range* nr = number_set;
628 while (nr)
630 number_range* tmp;
633 tmp = nr;
634 nr = nr->next;
635 free(tmp);
640 char*
641 number_set_show(number_range* number_set,
642 int min,
643 int max)
645 sds s;
646 size_t len;
647 char* res;
649 number_range* nr = number_set;
651 const char* comma;
654 if (nr && nr->base == nr->wrap)
656 if (min < 0)
657 min = 0;
658 if (max < 0)
659 max = INT_MAX;
660 if (min > max)
662 int t;
665 t = min;
666 min = max;
667 max = t;
670 else
672 /* `min' and `max' are meaningless for wrap-around ranges */
673 min = INT_MIN;
674 max = INT_MAX;
677 s = sdsempty();
679 while (nr)
681 if (nr->start > max)
682 goto Exit;
683 if (nr->end < min)
684 goto Again;
686 comma = *s ? ", " : "";
688 if (nr->start == nr->end)
689 s = sdscatprintf(s, "%s%i", comma, nr->start);
690 else if (nr->start <= min
691 && nr->end >= max)
692 s = sdscatprintf(s, "-");
693 else if (nr->start <= min)
694 s = sdscatprintf(s, "-%i", nr->end);
695 else if (nr->end >= max)
696 s = sdscatprintf(s, "%s%i-", comma, nr->start);
697 else
698 s = sdscatprintf(s, "%s%i-%i", comma, nr->start, nr->end);
700 Again:
701 nr = nr->next;
704 Exit:
705 if (!s)
706 return NULL;
708 /* we return an empty string for an empty number set */
709 /* (this is, number_set == NULL or unsuitable `min' and `max' values) */
710 len = sdslen(s) + 1;
711 res = (char*)malloc(len);
712 if (res)
713 memcpy(res, s, len);
715 sdsfree(s);
717 return res;
722 number_set_is_element(number_range* number_set,
723 int number)
725 number_range* nr = number_set;
728 while (nr)
730 if (nr->start > nr->end)
732 if (number < nr->base)
733 return 0;
734 if (number <= nr->end)
735 return 1;
736 if ( number < nr->start)
737 return 0;
738 if (number <= nr->wrap)
739 return 1;
741 else
743 if (number < nr->start)
744 return 0;
745 if (number <= nr->end)
746 return 1;
749 nr = nr->next;
752 return 0;
757 number_set_get_first(number_set_iter* iter_p)
759 if (!iter_p || !iter_p->range)
760 return -1;
762 iter_p->val = iter_p->range->start;
764 return iter_p->val;
769 number_set_get_next(number_set_iter* iter_p)
771 if (!iter_p || !iter_p->range)
772 return -1;
774 iter_p->val++;
776 if (iter_p->range->start > iter_p->range->end)
778 /* range really wraps around */
779 if (iter_p->val > iter_p->range->wrap)
780 iter_p->val = iter_p->range->base;
781 else if (iter_p->val < iter_p->range->start
782 && iter_p->val > iter_p->range->end)
784 iter_p->range = iter_p->range->next;
786 if (iter_p->range)
787 iter_p->val = iter_p->range->start;
788 else
789 return -1;
792 else
794 if (iter_p->val > iter_p->range->end)
796 iter_p->range = iter_p->range->next;
798 if (iter_p->range)
799 iter_p->val = iter_p->range->start;
800 else
801 return -1;
805 return iter_p->val;
808 /* end of numberset.c */