lib/numberset.h

   1 /* numberset.h */
   2
   3 /*
   4  * Copyright (C) 2012-2015 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 #ifndef __NUMBERSET_H__
  17 #define __NUMBERSET_H__
  18
  19 #ifdef __cplusplus
  20 extern "C" {
  21 #endif
  22
  23 /*
  24  * A structure defining an integer range, to be used as a linked list.  It
  25  * gets allocated by a successful call to `number_set_parse'.  Use
  26  * `number_set_free' to deallocate it.
  27  */
  28
  29 typedef struct number_range_
  30 {
  31   int start;
  32   int end;
  33
  34   struct number_range_* next;
  35 } number_range;
  36
  37
  38 /*
  39  * Create and initialize a `number_range' object.  In case of an allocation
  40  * error, return NUMBERSET_ALLOCATION_ERROR.  If either `start' or `end'
  41  * exceeds the range [min;max], return NUMBERSET_INVALID_RANGE.
  42  */
  43
  44 number_range*
  45 number_set_new(int start,
  46                int end,
  47                int min,
  48                int max);
  49
  50
  51 /*
  52  * Prepend a single `number_range' object `element' to `list' of
  53  * `number_range' objects, which might be NULL.  `list' is expected to be
  54  * stored in reversed order; consequently, the range in `element' must be
  55  * larger than the first element of `list', otherwise an error is returned.
  56  * If possible, the ranges of `element' and the first element of `list' are
  57  * merged, in which case `element' gets deallocated.
  58  *
  59  * If `element' is NULL, return `list'.
  60  */
  61
  62 number_range*
  63 number_set_prepend(number_range* list,
  64                    number_range* element);
  65
  66
  67 /*
  68  * Insert a single `number_range' object `element' into `list' of
  69  * `number_range' objects, which might be NULL.  `list' is expected to be
  70  * stored in reversed order.  If possible, the ranges of `element' and
  71  * `list' are merged, in which case `element' gets deallocated.
  72  *
  73  * If `element' is NULL, return `list'.
  74  */
  75
  76 number_range*
  77 number_set_insert(number_range* list,
  78                   number_range* element);
  79
  80
  81 /*
  82  * Merge adjacent ranges in a list of `number_range' objects (which must be
  83  * in normal order), deallocating list elements where appropriate.
  84  */
  85
  86 number_range*
  87 number_set_normalize(number_range* list);
  88
  89
  90 /*
  91  * Reverse a list of `number_range' objects.
  92  */
  93
  94 number_range*
  95 number_set_reverse(number_range* list);
  96
  97
  98 /*
  99  * Parse a description in string `s' for a set of non-negative integers
 100  * within the limits given by the input parameters `min' and `max', and
 101  * which consists of the following ranges, separated by commas (`n' and `m'
 102  * are non-negative integers):
 103  *
 104  *   -n       min <= x <= n
 105  *   n        x = n; this is a shorthand for `n-n'
 106  *   n-m      n <= x <= m (or  m <= x <= n  if  m < n)
 107  *   m-       m <= x <= max
 108  *   -        min <= x <= max
 109  *
 110  * Superfluous commas are ignored, as is whitespace around numbers, dashes,
 111  * and commas.  The ranges must be ordered, without overlaps.  As a
 112  * consequence, `-n' and `m-' can occur at most once and must be then the
 113  * first and last range, respectively; similarly, `-' cannot be paired with
 114  * any other range.
 115  *
 116  * In the following examples, `min' is 4 and `max' is 12:
 117  *
 118  *   -                ->    4, 5, 6, 7, 8, 9, 10, 11, 12
 119  *   -3, 5-           ->    invalid first range
 120  *   4, 6-8, 10-      ->    4, 6, 7, 8, 10, 11, 12
 121  *   4-8, 6-10        ->    invalid overlapping ranges
 122  *
 123  * In case of success (this is, the number set description in `s' is valid)
 124  * the return value is a pointer to the final zero byte in string `s'.  In
 125  * case of an error, the return value is a pointer to the beginning position
 126  * of the offending range in string `s'.
 127  *
 128  * If s is NULL, the function exits immediately with NULL as the return
 129  * value.
 130  *
 131  * If the user provides a non-NULL `number_set' value, `number_set_parse'
 132  * stores a linked list of ordered number ranges in `*number_set', allocated
 133  * with `malloc'.  If there is no range at all (for example, an empty string
 134  * or whitespace and commas only) no data gets allocated, and `*number_set'
 135  * is set to NULL.  In case of error, `*number_set' returns an error code;
 136  * you should use the following macros to compare with.
 137  *
 138  *   NUMBERSET_INVALID_CHARACTER   invalid character in description string
 139  *   NUMBERSET_OVERFLOW            numerical overflow
 140  *   NUMBERSET_INVALID_RANGE       invalid range, exceeding `min' or `max'
 141  *   NUMBERSET_OVERLAPPING_RANGES  overlapping ranges
 142  *   NUMBERSET_NOT_ASCENDING       not ascending ranges or values
 143  *   NUMBERSET_ALLOCATION_ERROR    allocation error
 144  *
 145  * Note that a negative value for `min' is replaced with zero, and a
 146  * negative value for `max' with the largest representable integer, INT_MAX.
 147  */
 148
 149 #define NUMBERSET_INVALID_CHARACTER (number_range*)-1
 150 #define NUMBERSET_OVERFLOW (number_range*)-2
 151 #define NUMBERSET_INVALID_RANGE (number_range*)-3
 152 #define NUMBERSET_OVERLAPPING_RANGES (number_range*)-4
 153 #define NUMBERSET_NOT_ASCENDING (number_range*)-5
 154 #define NUMBERSET_ALLOCATION_ERROR (number_range*)-6
 155
 156 const char*
 157 number_set_parse(const char* s,
 158                  number_range** number_set,
 159                  int min,
 160                  int max);
 161
 162
 163 /*
 164  * Free the allocated data in `number_set'.
 165  */
 166
 167 void
 168 number_set_free(number_range* number_set);
 169
 170
 171 /*
 172  * Return a string representation of `number_set', viewed through a
 173  * `window', so to say, spanned up by the parameters `min' and `max'.  After
 174  * use, the string should be deallocated with a call to `free'.  In case of
 175  * an allocation error, the return value is NULL.
 176  *
 177  * Note that a negative value for `min' is replaced with zero, and a
 178  * negative value for `max' with the largest representable integer, INT_MAX.
 179  */
 180
 181 char*
 182 number_set_show(number_range* number_set,
 183                 int min,
 184                 int max);
 185
 186
 187 /*
 188  * Return value 1 if `number' is element of `number_set', zero otherwise.
 189  */
 190
 191 int
 192 number_set_is_element(number_range* number_set,
 193                       int number);
 194
 195
 196 /*
 197  * A structure used to iterate over a number set.
 198  */
 199
 200 typedef struct number_set_iter_
 201 {
 202   number_range* range;
 203   int val;
 204 } number_set_iter;
 205
 206
 207 /*
 208  * Get first element of a number set.  `iter_p' must be initialized with the
 209  * `number_range' structure to iterate over.  After the call, `iter_p' is
 210  * ready to be used in a call to `number_set_get_next'.
 211  */
 212
 213 int
 214 number_set_get_first(number_set_iter* iter_p);
 215
 216
 217 /*
 218  * Get next element of a number set, using `iter_p' from a previous call to
 219  * `number_set_get_first' or `number_set_get_next'.  If `iter_p->range' is
 220  * NULL after the call, there is no next element, and the return value is
 221  * undefined.
 222  */
 223
 224 int
 225 number_set_get_next(number_set_iter* iter_p);
 226
 227 #ifdef __cplusplus
 228 } /* extern "C" */
 229 #endif
 230
 231 #endif /* __NUMBERSET_H__ */
 232
 233 /* end of numberset.h */