lib/numberset.h

   1 /* numberset.h */
   2
   3 /*
   4  * Copyright (C) 2012-2017 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 a range or wrap-around range of non-negative
  25  * integers, to be used as a linked list.  It gets allocated by a successful
  26  * call to `number_set_parse', `number_set_new', and `wrap_range_new'.  Use
  27  * `number_set_free' to deallocate it.
  28  *
  29  * If `base' and `wrap' are not equal, we have a `wrap-around range'.  These
  30  * two values define a frame which encloses `start' and `end'; `start' can
  31  * be larger than `end' to indicate wrapping at `wrap', starting again with
  32  * value `base'.  Example:
  33  *
  34  *   start=17, end=14,
  35  *   base=13, wrap=18  -->  17, 18, 13, 14
  36  *
  37  * Normal integer ranges can be merged.  For example, the ranges 3-6 and 7-8
  38  * can be merged into 3-8, and functions like `number_set_prepend' do this
  39  * automatically.
  40  *
  41  * Wrap-around ranges will not be merged; this is by design to reflect the
  42  * intended usage of this library (namely to represent groups of
  43  * horizontally aligned points on a closed glyph outline contour).
  44  * Additionally, for a given [base;wrap] interval there can only be a single
  45  * wrap-around range that actually does wrapping; it gets sorted after the
  46  * other non-wrapping ranges for the same [base;wrap] interval.
  47  */
  48
  49 typedef struct number_range_
  50 {
  51   /* all values are >= 0 */
  52   int start;
  53   int end;
  54   int base;
  55   int wrap;
  56
  57   struct number_range_* next;
  58 } number_range;
  59
  60
  61 /*
  62  * Create and initialize a `number_range' object, holding a normal integer
  63  * range.  In case of an allocation error, return
  64  * NUMBERSET_ALLOCATION_ERROR.
  65  *
  66  * A negative value for `min' is replaced with zero, and a negative value
  67  * for `max' with the largest representable integer, INT_MAX.
  68  *
  69  * If either `start' or `end' exceeds the range [min;max], return
  70  * NUMBERSET_INVALID_RANGE.
  71  */
  72
  73 number_range*
  74 number_set_new(int start,
  75                int end,
  76                int min,
  77                int max);
  78
  79
  80 /*
  81  * Create and initialize a wrap-around range.  In case of an allocation
  82  * error, return NUMBERSET_ALLOCATION_ERROR.
  83  *
  84  * `wraps' specifies an array of at least two `wrap points', in strictly
  85  * ascending order, with `num_wraps' elements.  For creating a valid
  86  * wrap-around range, there must exist a pair of adjacent elements in the
  87  * `wraps' array that enclose `start' and `end'.  To be more precise, if
  88  * `wA=wraps[n]' and `wB=wraps[n+1]' denote the two adjacent elements of
  89  * `wraps', both `start' and `end' must be in the range ]wA;wB].  If this
  90  * constraint is not met, return NUMBERSET_INVALID_RANGE.
  91  *
  92  * A corollary of the definitions of `wraps' and `number_range' is that the
  93  * elements of `wraps' must be all different and non-negative except the
  94  * first element, which can be -1.
  95  *
  96  * For convenience, normal integer ranges and wrap-around ranges use the
  97  * same data structure (`number_range').  However, calls to `number_set_new'
  98  * and `wrap_range_new' can't be mixed: Either use the former function for
  99  * all calls, or you use the latter; you will get an NUMBERSET_INVALID_RANGE
 100  * error otherwise.
 101  *
 102  * Here are some examples that demonstrate the resulting elements of
 103  * wrap-around ranges for a given `wraps' array and various `start' and
 104  * `end' values.
 105  *
 106  *   wraps = {-1, 4, 9}
 107  *
 108  *     range     elements
 109  *    -------------------------------------------------
 110  *      4-0      4, 0
 111  *      6-8      6, 7, 8
 112  *      8-6      8, 9, 5, 6
 113  *      3-6      invalid, crossing wrap point 4
 114  *     10-11     invalid, outside of wrap points array
 115  *
 116  * Note that you get undefined results if the elements of `wraps' change
 117  * between calls to this function.
 118  */
 119
 120 number_range*
 121 wrap_range_new(int start,
 122                int end,
 123                size_t num_wraps,
 124                int* wraps);
 125
 126
 127 /*
 128  * Return 0 if the setup of `wraps', as described above, is valid,
 129  * and 1 otherwise.
 130  */
 131
 132 int
 133 wrap_range_check_wraps(size_t num_wraps,
 134                        int* wraps);
 135
 136
 137 /*
 138  * Prepend a single `number_range' object `element' to `list' of
 139  * `number_range' objects, which might be NULL.  `list' is expected to be
 140  * stored in reversed order; consequently, the range in `element' must be
 141  * larger than the first element of `list', otherwise an error is returned.
 142  * If possible, the ranges of `element' and the first element of `list' are
 143  * merged, in which case `element' gets deallocated.
 144  *
 145  * If `element' is NULL, return `list'.
 146  */
 147
 148 number_range*
 149 number_set_prepend(number_range* list,
 150                    number_range* element);
 151
 152
 153 /*
 154  * Prepend a single `number_range' object `element' to `list' of
 155  * `number_range' objects, which might be NULL.  `list' is expected to be
 156  * stored in reversed order.  By design, there is no range merging.
 157  *
 158  * If `element' is NULL, return `list'.
 159  */
 160
 161 number_range*
 162 number_set_prepend_unsorted(number_range* list,
 163                             number_range* element);
 164
 165
 166 /*
 167  * Prepend a single wrap-around `number_range' object `element' to `list' of
 168  * (wrap-around) `number_range' objects, which might be NULL.  `list' is
 169  * expected to be stored in reversed order; consequently, the range in
 170  * `element' must be larger than the first element of `list', otherwise an
 171  * error is returned.
 172  *
 173  * If `element' is NULL, return `list'.
 174  */
 175
 176 number_range*
 177 wrap_range_prepend(number_range* list,
 178                    number_range* element);
 179
 180
 181 /*
 182  * Insert a single `number_range' object `element' into `list' of
 183  * `number_range' objects, which might be NULL.  `list' is expected to be
 184  * stored in reversed order.  If possible, the ranges of `element' and
 185  * `list' are merged, in which case `element' gets deallocated.
 186  *
 187  * Don't use this function for unsorted lists (i.e., lists created with
 188  * `number_set_prepend_unsorted'); you will get undefined behaviour
 189  * otherwise.
 190  *
 191  * If `element' is NULL, return `list'.
 192  */
 193
 194 number_range*
 195 number_set_insert(number_range* list,
 196                   number_range* element);
 197
 198
 199 /*
 200  * Insert a single wrap-around `number_range' object `element' into `list'
 201  * of (wrap-around) `number_range' objects, which might be NULL.  `list' is
 202  * expected to be stored in reversed order.
 203  *
 204  * If `element' is NULL, return `list'.
 205  */
 206
 207 number_range*
 208 wrap_range_insert(number_range* list,
 209                   number_range* element);
 210
 211
 212 /*
 213  * Reverse a list of `number_range' objects.
 214  */
 215
 216 number_range*
 217 number_set_reverse(number_range* list);
 218
 219
 220 /*
 221  * Parse a description in string `s' for a set of non-negative integers
 222  * within the limits given by the input parameters `min' and `max', and
 223  * which consists of the following ranges, separated by commas (`n' and `m'
 224  * are non-negative integers):
 225  *
 226  *   -n       min <= x <= n
 227  *   n        x = n; this is a shorthand for `n-n'
 228  *   n-m      n <= x <= m (or  m <= x <= n  if  m < n)
 229  *   m-       m <= x <= max
 230  *   -        min <= x <= max
 231  *
 232  * Superfluous commas are ignored, as is whitespace around numbers, dashes,
 233  * and commas.  The ranges must be ordered, without overlaps.  As a
 234  * consequence, `-n' and `m-' can occur at most once and must be then the
 235  * first and last range, respectively; similarly, `-' cannot be paired with
 236  * any other range.
 237  *
 238  * In the following examples, `min' is 4 and `max' is 12:
 239  *
 240  *   -                ->    4, 5, 6, 7, 8, 9, 10, 11, 12
 241  *   -3, 5-           ->    invalid first range
 242  *   4, 6-8, 10-      ->    4, 6, 7, 8, 10, 11, 12
 243  *   4-8, 6-10        ->    invalid overlapping ranges
 244  *
 245  * In case of success (this is, the number set description in `s' is valid)
 246  * the return value is a pointer to the final zero byte in string `s'.  In
 247  * case of an error, the return value is a pointer to the beginning position
 248  * of the offending range in string `s'.
 249  *
 250  * If s is NULL, the function exits immediately with NULL as the return
 251  * value.
 252  *
 253  * If the user provides a non-NULL `number_set' value, `number_set_parse'
 254  * stores a linked list of ordered number ranges in `*number_set', allocated
 255  * with `malloc'.  If there is no range at all (for example, an empty string
 256  * or whitespace and commas only) no data gets allocated, and `*number_set'
 257  * is set to NULL.  In case of error, `*number_set' returns an error code;
 258  * you should use the following macros to compare with.
 259  *
 260  *   NUMBERSET_INVALID_CHARACTER   invalid character in description string
 261  *   NUMBERSET_OVERFLOW            numerical overflow
 262  *   NUMBERSET_INVALID_RANGE       invalid range, exceeding `min' or `max'
 263  *   NUMBERSET_OVERLAPPING_RANGES  overlapping ranges
 264  *   NUMBERSET_NOT_ASCENDING       not ascending ranges or values
 265  *   NUMBERSET_ALLOCATION_ERROR    allocation error
 266  *
 267  * Note that a negative value for `min' is replaced with zero, and a
 268  * negative value for `max' with the largest representable integer, INT_MAX.
 269  *
 270  * `number_set_parse' is not suited to create wrap-around ranges; this only
 271  * works with `wrap_range_new'.
 272  */
 273
 274 #define NUMBERSET_INVALID_CHARACTER (number_range*)-1
 275 #define NUMBERSET_OVERFLOW (number_range*)-2
 276 #define NUMBERSET_INVALID_RANGE (number_range*)-3
 277 #define NUMBERSET_OVERLAPPING_RANGES (number_range*)-4
 278 #define NUMBERSET_NOT_ASCENDING (number_range*)-5
 279 #define NUMBERSET_ALLOCATION_ERROR (number_range*)-6
 280
 281 /*
 282  * `wrap_range_new' can return an additional error code in case no valid
 283  * interval could be found.
 284  */
 285 #define NUMBERSET_INVALID_WRAP_RANGE (number_range*)-7
 286
 287 const char*
 288 number_set_parse(const char* s,
 289                  number_range** number_set,
 290                  int min,
 291                  int max);
 292
 293
 294 /*
 295  * Free the allocated data in `number_set'.
 296  */
 297
 298 void
 299 number_set_free(number_range* number_set);
 300
 301
 302 /*
 303  * Return a string representation of `number_set', viewed through a
 304  * `window', so to say, spanned up by the parameters `min' and `max'.  After
 305  * use, the string should be deallocated with a call to `free'.  In case of
 306  * an allocation error, the return value is NULL.
 307  *
 308  * Note that a negative value for `min' is replaced with zero, and a
 309  * negative value for `max' with the largest representable integer, INT_MAX.
 310  *
 311  * If `number_set' represents wrap-around ranges, `min' and `max' are
 312  * ignored.
 313  */
 314
 315 char*
 316 number_set_show(number_range* number_set,
 317                 int min,
 318                 int max);
 319
 320
 321 /*
 322  * Return value 1 if `number' is element of `number_set', zero otherwise.
 323  */
 324
 325 int
 326 number_set_is_element(number_range* number_set,
 327                       int number);
 328
 329
 330 /*
 331  * A structure used to iterate over a number set.
 332  */
 333
 334 typedef struct number_set_iter_
 335 {
 336   number_range* range;
 337   int val;
 338 } number_set_iter;
 339
 340
 341 /*
 342  * Get first element of a number set.  `iter_p' must be initialized with the
 343  * `number_range' structure to iterate over.  After the call, `iter_p' is
 344  * ready to be used in a call to `number_set_get_next'.
 345  *
 346  * If there is no valid first element, return -1.
 347  */
 348
 349 int
 350 number_set_get_first(number_set_iter* iter_p);
 351
 352
 353 /*
 354  * Get next element of a number set, using `iter_p' from a previous call to
 355  * `number_set_get_first' or `number_set_get_next'.  If there is no next
 356  * valid element, return -1.
 357  */
 358
 359 int
 360 number_set_get_next(number_set_iter* iter_p);
 361
 362 #ifdef __cplusplus
 363 } /* extern "C" */
 364 #endif
 365
 366 #endif /* NUMBERSET_H_ */
 367
 368 /* end of numberset.h */