1 /*!
2 * \file lib/vector/Vlib/cats.c
3 *
4 * \brief Vector library - Category management
5 *
6 * Higher level functions for reading/writing/manipulating vectors.
7 *
8 * (C) 2001-2012 by the GRASS Development Team
9 *
10 * This program is free software under the GNU General Public License
11 * (>=v2). Read the file COPYING that comes with GRASS for details.
12 *
13 * \author Original author CERL, probably Dave Gerdes or Mike Higgins
14 * \author Update to GRASS 5.7 Radim Blazek and David D. Gray.
15 * \author Various updates by Martin Landa <landa.martin gmail.com>
16 * \author Various updates by Markus Metz
17 */
18
19 #include <stdlib.h>
20 #include <string.h>
21 #include <grass/vector.h>
22 #include <grass/dbmi.h>
23 #include <grass/glocale.h>
24
25 static int cmp(const void *pa, const void *pb);
26 static struct line_cats *Vect__new_cats_struct(void);
27
28
29 /*!
30 \brief Creates and initializes line_cats structure.
31
32 This structure is used for reading and writing vector cats. The
33 library routines handle all memory allocation.
34
35 To free allocated memory call Vect_destroy_cats_struct().
36
37 \return struct line_cats *
38 \return NULL on error
39 */
Vect_new_cats_struct()40 struct line_cats *Vect_new_cats_struct()
41 {
42 struct line_cats *p;
43
44 if (NULL == (p = Vect__new_cats_struct()))
45 G_fatal_error(_("Vect_new_cats_struct(): Out of memory"));
46
47 return p;
48 }
49
50 /*!
51 \brief Creates and initializes line_cats structure (lower level fn)
52
53 This structure is used for reading and writing vector cats. The
54 library routines handle all memory allocation.
55
56 \return struct line_cats *
57 */
Vect__new_cats_struct()58 static struct line_cats *Vect__new_cats_struct()
59 {
60 struct line_cats *p;
61
62 p = (struct line_cats *)G_malloc(sizeof(struct line_cats));
63
64 /* n_cats MUST be initialized to zero */
65 if (p)
66 p->n_cats = 0;
67
68 if (p)
69 p->alloc_cats = 0;
70
71 return p;
72 }
73
74 /*!
75 \brief Frees all memory associated with line_cats structure,
76 including the struct itself.
77
78 \param p line_cats structure
79 */
Vect_destroy_cats_struct(struct line_cats * p)80 void Vect_destroy_cats_struct(struct line_cats *p)
81 {
82 if (p) { /* probably a moot test */
83 if (p->n_cats) {
84 G_free((void *)p->field);
85 G_free((void *)p->cat);
86 }
87 G_free((void *)p);
88 }
89 }
90
91 /*!
92 \brief Add new field/cat to category structure if doesn't exist
93 yet.
94
95 \param[in,out] Cats line_cats structure
96 \param[in] field layer number
97 \param[in] cat category number
98
99 \return number of categories
100 \return 0 if no space for new category in structure, n_cats would be > GV_NCATS_MAX
101 \return -1 on out of memory
102 \return -2 if field out of range: 1 - GV_FIELD_MAX or cat out of range: 1 - GV_CAT_MAX
103 */
Vect_cat_set(struct line_cats * Cats,int field,int cat)104 int Vect_cat_set(struct line_cats *Cats, int field, int cat)
105 {
106 register int n;
107
108 /* check input values */
109 /* compiler may warn:
110 * comparison is always 0 due to limited range of data type
111 * but remember that limit is set to portable data type length
112 * and machine native size may be longer */
113 /*
114 if (field < 1 || field > GV_FIELD_MAX || cat < 0 || cat > GV_CAT_MAX)
115 return (-2);
116 */
117
118 /* go through old cats and find if field/category exists */
119 for (n = 0; n < Cats->n_cats; n++) {
120 if (Cats->field[n] == field && Cats->cat[n] == cat)
121 return (1);
122 }
123
124 /* field was not found so we shall append new cat */
125 /* test if space exist */
126 if (n >= GV_NCATS_MAX) {
127 G_fatal_error(_("Too many categories (%d), unable to set cat %d (layer %d)"),
128 Cats->n_cats, cat, field);
129 }
130
131 if (Cats->n_cats == Cats->alloc_cats) {
132 if (0 > dig_alloc_cats(Cats, Cats->n_cats + 100))
133 return (-1);
134 }
135
136 n = Cats->n_cats;
137 Cats->field[n] = field;
138 Cats->cat[n] = cat;
139 Cats->n_cats++;
140 return (1);
141 }
142
143 /*!
144 \brief Get first found category of given field.
145
146 <em>cat</em> is set to first category found or -1 if field was not
147 found
148
149 \param Cats pointer line_cats structure
150 \param field layer number
151 \param[out] cat pointer to variable where cat will be written (can be NULL)
152
153 \return number of found cats for given field (first reported)
154 \return 0 layer does not exist
155 */
Vect_cat_get(const struct line_cats * Cats,int field,int * cat)156 int Vect_cat_get(const struct line_cats *Cats, int field, int *cat)
157 {
158 int n, ret;
159
160 /* field was not found */
161 ret = 0;
162 if (cat)
163 *cat = -1;
164
165 /* check input value */
166 if (field < 1 || field > GV_FIELD_MAX)
167 return (0);
168
169 /* go through cats and find if field exist */
170 for (n = 0; n < Cats->n_cats; n++) {
171 if (Cats->field[n] == field) {
172 if (cat && ret == 0) {
173 *cat = Cats->cat[n];
174 }
175 ret++;
176 }
177 }
178
179 return ret;
180 }
181
182 /*!
183 \brief Get list of categories of given field.
184
185 \param Cats line_cats structure
186 \param field layer number
187 \param[out] cats pointer to list where cats will be written
188
189 \return number of found categories
190 \return -1 on invalid field
191 */
Vect_field_cat_get(const struct line_cats * Cats,int field,struct ilist * cats)192 int Vect_field_cat_get(const struct line_cats *Cats, int field, struct ilist *cats)
193 {
194 int n;
195
196 /* reset list of categories */
197 Vect_reset_list(cats);
198
199 /* check input value */
200 if (field < 1 || field > GV_FIELD_MAX)
201 return -1;
202
203 /* go through cats and find if field exist */
204 for (n = 0; n < Cats->n_cats; n++) {
205 if (Cats->field[n] == field)
206 Vect_list_append(cats, Cats->cat[n]);
207 }
208
209 return cats->n_values;
210 }
211
212 /*!
213 \brief Delete all categories of given layer
214
215 \param[in,out] Cats line_cats structure
216 \param field layer number
217
218 \return number of categories deleted
219 \return 0 layer does not exist
220 */
Vect_cat_del(struct line_cats * Cats,int field)221 int Vect_cat_del(struct line_cats *Cats, int field)
222 {
223 int n, m, found;
224
225 /* check input value */
226 /*
227 if (field < 1 || field > GV_FIELD_MAX)
228 return (0);
229 */
230
231 /* go through cats and find if field exist */
232 m = 0;
233 for (n = 0; n < Cats->n_cats; n++) {
234 if (Cats->field[n] != field) {
235 Cats->field[m] = Cats->field[n];
236 Cats->cat[m] = Cats->cat[n];
237 m++;
238 }
239 }
240 found = Cats->n_cats - m;
241 Cats->n_cats = m;
242
243 return (found);
244 }
245
246 /*!
247 \brief Delete field/cat from line_cats structure
248
249 \param[in,out] Cats line_cats structure
250 \param field layer number
251 \param cat category to be deleted or -1 to delete all cats of given field
252
253 \return number of categories deleted
254 \return 0 field/category number does not exist
255 */
Vect_field_cat_del(struct line_cats * Cats,int field,int cat)256 int Vect_field_cat_del(struct line_cats *Cats, int field, int cat)
257 {
258 register int n, m, found;
259
260 /* check input value */
261 /*
262 if (field < 1 || field > GV_FIELD_MAX)
263 return (0);
264 */
265
266 if (cat == -1)
267 return Vect_cat_del(Cats, field);
268
269 /* go through cats and find if field exist */
270 m = 0;
271 for (n = 0; n < Cats->n_cats; n++) {
272 if (Cats->field[n] != field || Cats->cat[n] != cat) {
273 Cats->field[m] = Cats->field[n];
274 Cats->cat[m] = Cats->cat[n];
275 m++;
276 }
277 }
278 found = Cats->n_cats - m;
279 Cats->n_cats = m;
280
281 return (found);
282 }
283
284 /*!
285 \brief Reset category structure to make sure cats structure is clean to be re-used.
286
287 I.e. it has no cats associated with it. Cats must have
288 previously been created with Vect_new_cats_struct()
289
290 \param[out] Cats line_cats structure
291
292 \return 0
293 */
Vect_reset_cats(struct line_cats * Cats)294 int Vect_reset_cats(struct line_cats *Cats)
295 {
296 Cats->n_cats = 0;
297
298 return 0;
299 }
300
301 /*!
302 \brief Allocate memory for cat_list structure.
303
304 \return pointer to allocated structure
305 \return NULL if out of memory
306 */
Vect_new_cat_list()307 struct cat_list *Vect_new_cat_list()
308 {
309 struct cat_list *p;
310
311 p = (struct cat_list *)G_malloc(sizeof(struct cat_list));
312
313 /* n_ranges MUST be initialized to zero */
314 if (p)
315 G_zero(p, sizeof(struct cat_list));
316
317 return p;
318 }
319
320
321 /*!
322 \brief Frees allocated cat_list memory.
323
324 \param p pointer to line_cats structure
325 */
Vect_destroy_cat_list(struct cat_list * p)326 void Vect_destroy_cat_list(struct cat_list *p)
327 {
328 if (p) { /* probably a moot test */
329 if (p->n_ranges) {
330 G_free((void *)p->min);
331 G_free((void *)p->max);
332 }
333 G_free((void *)p);
334 }
335 }
336
337
338 /*!
339 \brief Converts string of categories and cat ranges separated by commas to cat_list.
340
341 \par Examples of string:
342 \verbatim
343 5,6,7
344 3-9
345 2,3,5-9,20\endverbatim
346
347 \par Example:
348 \code
349 ...
350 str = "2,3,5-9,20"
351 cat_list = Vect_new_cat_list()
352
353 Vect_str_to_cat_list(str, cat_list)
354 \endcode
355 \verbatim
356 cat_list->field = 0
357 cat_list->n_ranges = 4
358 cat_list->min = {2, 3, 5, 20}
359 cat_list->max = {2, 3, 9, 20}
360 \endverbatim
361
362 \param str category list as a string
363 \param[in,out] list pointer to cat_list structure
364
365 \return number of errors in ranges
366 */
Vect_str_to_cat_list(const char * str,struct cat_list * list)367 int Vect_str_to_cat_list(const char *str, struct cat_list *list)
368 {
369 int i, nr, l, err = 0;
370 const char *s, *e;
371 char buf[100];
372 int min, max;
373
374 G_debug(3, "Vect_str_to_cat_list(): str = %s", str);
375
376 list->n_ranges = 0;
377 l = strlen(str);
378
379 /* find number of ranges */
380 nr = 1; /* one range */
381 for (i = 0; i < l; i++)
382 if (str[i] == ',')
383 nr++;
384
385 /* allocate space */
386 if (list->alloc_ranges == 0) {
387 list->min = (int *)G_malloc(nr * sizeof(int));
388 list->max = (int *)G_malloc(nr * sizeof(int));
389 }
390 else if (nr > list->alloc_ranges) {
391 list->min = (int *)G_realloc((void *)list->min, nr * sizeof(int));
392 list->max = (int *)G_realloc((void *)list->max, nr * sizeof(int));
393 }
394
395 /* go through string and read ranges */
396 i = 0;
397 s = str;
398
399 while (s) {
400 e = (char *)strchr(s, ','); /* first comma */
401 if (e) {
402 l = e - s;
403 strncpy(buf, s, l);
404 buf[l] = '\0';
405 s = e + 1;
406 }
407 else {
408 strcpy(buf, s);
409 s = NULL;
410 }
411
412 G_debug(3, " buf = %s", buf);
413 if (sscanf(buf, "%d-%d", &min, &max) == 2) {
414 }
415 else if (sscanf(buf, "%d", &min) == 1)
416 max = min;
417 else { /* error */
418
419 G_warning(_("Unable to convert category string '%s' (from '%s') to category range"),
420 buf, str);
421 err++;
422 continue;
423 }
424
425 list->min[i] = min;
426 list->max[i] = max;
427 i++;
428 }
429
430 list->n_ranges = i;
431
432 return (err);
433 }
434
435 /*!
436 \brief Convert ordered array of integers to cat_list structure.
437
438 \param vals array of integers
439 \param nvals number of values
440 \param[in,out] list pointer to cat_list structure
441
442 \return number of ranges
443 */
Vect_array_to_cat_list(const int * vals,int nvals,struct cat_list * list)444 int Vect_array_to_cat_list(const int *vals, int nvals, struct cat_list *list)
445 {
446 int i, range;
447
448 G_debug(1, "Vect_array_to_cat_list()");
449 range = -1;
450 for (i = 0; i < nvals; i++) {
451 if (i == 0 || (vals[i] - list->max[range]) > 1) {
452 range++;
453 if (range == list->alloc_ranges) {
454 list->alloc_ranges += 1000;
455 list->min = (int *)G_realloc((void *)list->min,
456 list->alloc_ranges *
457 sizeof(int));
458 list->max =
459 (int *)G_realloc((void *)list->max,
460 list->alloc_ranges * sizeof(int));
461 }
462 list->min[range] = vals[i];
463 list->max[range] = vals[i];
464 }
465 else {
466 list->max[range] = vals[i];
467 }
468 }
469
470 list->n_ranges = range + 1;
471
472 return (list->n_ranges);
473 }
474
475 /*!
476 \brief Convert cat_list struct to ordered array of unique integers.
477
478 Output array do not contain duplicate items.
479
480 Allocated array should be freed by G_free().
481
482 \param cat_list pointer to cat_list struct
483 \param[out] vals array of integers
484 \param[out] nvals number of values
485
486 \return 0 on success
487 \return -1 on failure
488 */
Vect_cat_list_to_array(const struct cat_list * list,int ** vals,int * nvals)489 int Vect_cat_list_to_array(const struct cat_list *list, int **vals, int *nvals)
490 {
491 int i, j, k, n, n_cats, n_ucats, last_cat;
492 int *cats, *ucats;
493
494 G_debug(1, "Vect_cat_list_to_array()");
495
496 *nvals = n_cats = 0;
497 cats = NULL;
498 for (i = 0; i < list->n_ranges; i++) {
499 n = list->max[i] - list->min[i] + 1;
500 if (n < 1)
501 return -1;
502
503 /* realloc array */
504 cats = (int *) G_realloc(cats, sizeof(int) * (n_cats + n));
505
506 for (j = n_cats, k = 0; j < n_cats + n; j++, k++) {
507 cats[j] = list->min[i] + k;
508 }
509 n_cats += n;
510 }
511
512 /* sort array */
513 qsort(cats, n_cats, sizeof(int), cmp);
514
515 /* skip duplicated values */
516 ucats = G_malloc(sizeof(int) * n_cats);
517 last_cat = ucats[0] = cats[0];
518 n_ucats = 1;
519 for (i = 1; i < n_cats; i++) {
520 if (last_cat == cats[i])
521 continue;
522 last_cat = ucats[n_ucats++] = cats[i];
523 }
524 G_free(cats);
525
526 /* reallocate array for unique values */
527 ucats = (int *) G_realloc(ucats, sizeof(int) * n_ucats);
528
529 *nvals = n_ucats;
530 *vals = ucats;
531
532 return 0;
533 }
534
535 /*!
536 \brief Check if category number is in list.
537
538 \param cat category number
539 \param list cat_list structure
540
541 \return TRUE if cat is in list
542 \return FALSE if not
543 */
Vect_cat_in_cat_list(int cat,const struct cat_list * list)544 int Vect_cat_in_cat_list(int cat, const struct cat_list *list)
545 {
546 int i;
547
548 for (i = 0; i < list->n_ranges; i++)
549 if (cat >= list->min[i] && cat <= list->max[i])
550 return (TRUE);
551
552 return (FALSE);
553 }
554
555 /*!
556 \brief Set category constraints using 'where' or 'cats' option and layer number.
557
558 \param Map pointer to Map_info structure
559 \param layer layer number
560 \param where where statement
561 \param catstr category list as string
562
563 \return pointer to cat_list structure or NULL
564 */
Vect_cats_set_constraint(struct Map_info * Map,int layer,char * where,char * catstr)565 struct cat_list *Vect_cats_set_constraint(struct Map_info *Map, int layer,
566 char *where, char *catstr)
567 {
568 struct cat_list *list = NULL;
569 int ret;
570
571 if (layer < 1) {
572 G_warning(_("Layer number must be > 0 for category constraints"));
573 /* no valid constraints, all categories qualify */
574 return list;
575 }
576
577 /* where has precedence over cats */
578 if (where) {
579 struct field_info *Fi = NULL;
580 dbDriver *driver = NULL;
581 int ncats, *cats = NULL;
582 int i, j;
583
584 if (catstr)
585 G_warning(_("'%s' and '%s' parameters were supplied, cats will be ignored"), "where", "cats");
586
587 Fi = Vect_get_field(Map, layer);
588 if (!Fi) {
589 G_fatal_error(_("Database connection not defined for layer %d"),
590 layer);
591 }
592
593 G_verbose_message(_("Loading categories from table <%s>..."), Fi->table);
594
595 driver = db_start_driver_open_database(Fi->driver, Fi->database);
596 if (driver == NULL)
597 G_fatal_error(_("Unable to open database <%s> by driver <%s>"),
598 Fi->database, Fi->driver);
599
600 ncats = db_select_int(driver, Fi->table, Fi->key, where,
601 &cats);
602 if (ncats == -1)
603 G_fatal_error(_("Unable select records from table <%s>"),
604 Fi->table);
605 G_verbose_message(n_("One category loaded", "%d categories loaded", ncats), ncats);
606
607 db_close_database_shutdown_driver(driver);
608
609 /* sort */
610 qsort(cats, ncats, sizeof(int), cmp);
611
612 /* remove duplicates */
613 j = 1;
614 for (i = 1; i < ncats; i++) {
615 if (cats[i] != cats[j - 1]) {
616 cats[j] = cats[i];
617 j++;
618 }
619 }
620 ncats = j;
621
622 /* convert to cat list */
623 list = Vect_new_cat_list();
624
625 ret = Vect_array_to_cat_list(cats, ncats, list);
626 if (ret == 0)
627 G_warning(_("No categories selected with '%s' option"), "where");
628
629 if (cats)
630 G_free(cats);
631 }
632 else if (catstr) {
633 list = Vect_new_cat_list();
634
635 ret = Vect_str_to_cat_list(catstr, list);
636 if (ret > 0)
637 G_warning(_("%d errors in '%s' option"), ret, "cats");
638 }
639
640 if (list) {
641 if (list->n_ranges < 1) {
642 Vect_destroy_cat_list(list);
643 list = NULL;
644 }
645 else
646 list->field = layer;
647 }
648
649 return list;
650 }
651
652 /*!
653 \brief Check if categories match with category constraints.
654
655 \param Cats line_cats structure
656 \param layer layer number
657 \param list cat_list structure
658
659 \return 0 no match, categories are outside constraints
660 \return 1 match, categories are inside constraints
661 */
662 /* TODO:
663 * for GRASS 8, change return type:
664 * return a list of all category numbers that match the constraints
665 * return NULL if no category number matches the constraints
666 */
Vect_cats_in_constraint(struct line_cats * Cats,int layer,struct cat_list * list)667 int Vect_cats_in_constraint(struct line_cats *Cats, int layer,
668 struct cat_list *list)
669 {
670 int i;
671
672 if (layer < 1) {
673 G_warning(_("Layer number must be > 0 for category constraints"));
674 /* no valid constraint, all categories qualify */
675 return 1;
676 }
677
678 if (list) {
679 for (i = 0; i < Cats->n_cats; i++) {
680 if (Cats->field[i] == layer &&
681 Vect_cat_in_cat_list(Cats->cat[i], list)) {
682 return 1;
683 }
684 }
685 return 0;
686 }
687
688 for (i = 0; i < Cats->n_cats; i++) {
689 if (Cats->field[i] == layer)
690 return 1;
691 }
692
693 return 0;
694 }
695
696
697 /*!
698 \brief Check if category is in ordered array of integers.
699
700 \param cat category number
701 \param array ordered array of integers
702 \param ncats number of categories in array
703
704 \return TRUE if cat is in list
705 \return FALSE if it is not
706 */
Vect_cat_in_array(int cat,const int * array,int ncats)707 int Vect_cat_in_array(int cat, const int *array, int ncats)
708 {
709 int *i;
710
711 i = bsearch((void *)&cat, (void *)array, (size_t) ncats,
712 sizeof(int), cmp);
713
714 return (i != NULL);
715 }
716
717 /* return -1 if *p1 < *p2
718 * return 1 if *p1 > *p2
719 * return 0 if *p1 == *p2 */
cmp(const void * pa,const void * pb)720 static int cmp(const void *pa, const void *pb)
721 {
722 int *p1 = (int *)pa;
723 int *p2 = (int *)pb;
724
725 if (*p1 < *p2)
726 return -1;
727 return (*p1 > *p2);
728 }
729