diglib/cindex.c

Go to the documentation of this file.

/*****************************************************************************
*
* MODULE:       Vector library 
*               
* AUTHOR(S):    Radim Blazek
*
* PURPOSE:      Lower level functions for reading/writing/manipulating vectors.
*
* COPYRIGHT:    (C) 2001 by the GRASS Development Team
*
*               This program is free software under the GNU General Public
*               License (>=v2). Read the file COPYING that comes with GRASS
*               for details.
*
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include <grass/vector.h>

/*! 
 * \brief Initialize Plus_head structure (cidx)
 *
 * \param Plus pointer to Plus_head structure
 *
 * \return 1 OK
 * \return 0 on error      
 */
int dig_cidx_init(struct Plus_head *Plus)
{
    G_debug(3, "dig_cidx_init()");

    Plus->n_cidx = 0;
    Plus->a_cidx = 5;
    Plus->cidx =
        (struct Cat_index *)G_malloc(Plus->a_cidx * sizeof(struct Cat_index));
    if (!Plus->cidx)
        return 0;
    Plus->cidx_up_to_date = 0;
    return 1;
}

/* Free category index */
void dig_cidx_free(struct Plus_head *Plus)
{
    int i;
    struct Cat_index *ci;

    G_debug(2, "dig_cidx_free()");
    for (i = 0; i < Plus->n_cidx; i++) {
        ci = &(Plus->cidx[i]);
        G_free(ci->cat);
        ci->cat = NULL;
        ci->field = ci->n_cats = ci->a_cats = ci->n_types = 0;
    }
    if (Plus->cidx) {
        G_free(Plus->cidx);
        Plus->cidx = NULL;
    }
    Plus->a_cidx = 0;
    Plus->n_cidx = 0;
    Plus->cidx_up_to_date = 0;
}

/* 
 *  dig_cidx_add_cat ()
 *  add new field - cat - line record, space is allocated if necessary 
 *
 *  returns 1 OK
 *          0 on error      
 */
int
dig_cidx_add_cat(struct Plus_head *Plus, int field, int cat, int line,
                 int type)
{
    int i, si, found;
    struct Cat_index *ci;

    G_debug(3, "dig_cidx_add_cat(): field = %d cat = %d line = %d type = %d",
            field, cat, line, type);

    /* Find field or add new */
    si = -1;
    for (i = 0; i < Plus->n_cidx; i++) {
        if (Plus->cidx[i].field == field) {
            si = i;
        }
    }
    if (si == -1) {             /* not found add new */
        if (Plus->n_cidx == Plus->a_cidx) {
            Plus->a_cidx += 10;
            Plus->cidx =
                (struct Cat_index *)G_realloc(Plus->cidx,
                                              Plus->a_cidx *
                                              sizeof(struct Cat_index));
            if (!Plus->cidx)
                return 0;
        }
        si = Plus->n_cidx;
        ci = &(Plus->cidx[si]);
        ci->field = field;
        ci->n_cats = ci->a_cats = 0;
        ci->cat = NULL;
        ci->n_types = 0;
        ci->offset = 0;
        Plus->n_cidx++;
    }

    /* Add new cat - line record */
    ci = &(Plus->cidx[si]);
    if (ci->n_cats == ci->a_cats) {
        ci->a_cats += 5000;
        ci->cat = G_realloc(ci->cat, ci->a_cats * 3 * sizeof(int));
    }

    ci->cat[ci->n_cats][0] = cat;
    ci->cat[ci->n_cats][1] = type;
    ci->cat[ci->n_cats][2] = line;
    ci->n_cats++;

    /* Add type */
    found = 0;
    for (i = 0; i < ci->n_types; i++) {
        if (ci->type[i][0] == type) {
            ci->type[i][1]++;
            found = 1;
        }
    }
    if (!found) {
        ci->type[ci->n_types][0] = type;
        ci->type[ci->n_types][1] = 1;
        ci->n_types++;
    }

    return 1;
}

/* Compare by cat, resolve ties by type, resolve ties by id */
static int cmp_cat(const void *pa, const void *pb)
{
    int *p1 = (int *)pa;
    int *p2 = (int *)pb;

    if (p1[0] < p2[0])
        return -1;
    if (p1[0] > p2[0])
        return 1;
    if (p1[1] < p2[1])
        return -1;
    if (p1[1] > p2[1])
        return 1;
    if (p1[2] < p2[2])
        return -1;
    if (p1[2] > p2[2])
        return 1;
    return 0;
}

/* Compare by field */
static int cmp_field(const void *pa, const void *pb)
{
    struct Cat_index *p1 = (struct Cat_index *)pa;
    struct Cat_index *p2 = (struct Cat_index *)pb;

    if (p1->field < p2->field)
        return -1;
    if (p1->field > p2->field)
        return 1;
    return 0;
}

/* 
 *  dig_cidx_add_cat_sorted ()
 *  add new field - cat - line record to sorted category index, space is allocated if necessary 
 *  
 *  returns 1 OK
 *          0 on error      
 */
int
dig_cidx_add_cat_sorted(struct Plus_head *Plus, int field, int cat, int line,
                        int type)
{
    int i, si, found, position;
    struct Cat_index *ci;

    G_debug(3,
            "dig_cidx_add_cat_sorted(): field = %d cat = %d line = %d type = %d",
            field, cat, line, type);

    /* Find field or add new */
    si = -1;
    for (i = 0; i < Plus->n_cidx; i++) {
        if (Plus->cidx[i].field == field) {
            si = i;
        }
    }
    if (si == -1) {             /* not found add new */
        if (Plus->n_cidx == Plus->a_cidx) {
            Plus->a_cidx += 10;
            Plus->cidx =
                (struct Cat_index *)G_realloc(Plus->cidx,
                                              Plus->a_cidx *
                                              sizeof(struct Cat_index));
            if (!Plus->cidx)
                return 0;
        }
        si = Plus->n_cidx;
        ci = &(Plus->cidx[si]);
        ci->field = field;
        ci->n_cats = ci->a_cats = 0;
        ci->cat = NULL;
        ci->n_types = 0;
        ci->offset = 0;
        Plus->n_cidx++;
    }

    /* Add new cat - line record */
    ci = &(Plus->cidx[si]);
    if (ci->n_cats == ci->a_cats) {
        ci->a_cats += 5000;
        ci->cat = G_realloc(ci->cat, ci->a_cats * 3 * sizeof(int));
    }

    /* Find position and move on the way */
    for (position = ci->n_cats; position > 0; position--) {
        if (ci->cat[position - 1][0] < cat ||
           (ci->cat[position - 1][0] == cat && ci->cat[position - 1][1] <= type)) {
               break;
        }
        ci->cat[position][0] = ci->cat[position - 1][0];
        ci->cat[position][1] = ci->cat[position - 1][1];
        ci->cat[position][2] = ci->cat[position - 1][2];
    }

    G_debug(4, "position = %d", position);

    ci->cat[position][0] = cat;
    ci->cat[position][1] = type;
    ci->cat[position][2] = line;
    ci->n_cats++;

    /* Add type */
    found = 0;
    for (i = 0; i < ci->n_types; i++) {
        if (ci->type[i][0] == type) {
            ci->type[i][1]++;
            found = 1;
        }
    }
    if (!found) {
        ci->type[ci->n_types][0] = type;
        ci->type[ci->n_types][1] = 1;
        ci->n_types++;
    }

    /* Sort by field */
    qsort(Plus->cidx, Plus->n_cidx, sizeof(struct Cat_index), cmp_field);

    G_debug(3, "Added new category to index");

    return 1;
}

/* 
 *  dig_cidx_del_cat ()
 *  delete old field - cat - line record from _sorted_ category index
 *
 *  returns 1 OK
 *          0 on error      
 */
int
dig_cidx_del_cat(struct Plus_head *Plus, int field, int cat, int line,
                 int type)
{
    int i, position;
    struct Cat_index *ci;

    G_debug(3, "dig_cidx_del_cat(): field = %d cat = %d line = %d", field,
            cat, line);

    /* Find field or add new */
    ci = NULL;
    for (i = 0; i < Plus->n_cidx; i++) {
        if (Plus->cidx[i].field == field) {
            ci = &(Plus->cidx[i]);
        }
    }
    if (ci == NULL) {           /* should not happen */
        G_warning("BUG: Category index not found for field %d.", field);
        return 0;
    }

    /* Find position */
    G_debug(3, "n_cats = %d", ci->n_cats);
    for (position = 0; position < ci->n_cats; position++) {
        if (ci->cat[position][0] == cat && ci->cat[position][1] == type &&
            ci->cat[position][2] == line) {
            break;
        }
    }

    G_debug(4, "position = %d", position);

    if (position == ci->n_cats) {
        G_warning("BUG: Category not found in category index.");
        return 0;
    }

    /* Delete */
    for (i = position; i < ci->n_cats - 1; i++) {
        ci->cat[i][0] = ci->cat[i + 1][0];
        ci->cat[i][1] = ci->cat[i + 1][1];
        ci->cat[i][2] = ci->cat[i + 1][2];
    }

    ci->n_cats--;

    for (i = 0; i < ci->n_types; i++) {
        if (ci->type[i][0] == type) {
            ci->type[i][1]--;
        }
    }

    G_debug(3, "Deleted from category index");
    return 1;
}

/* 
 *  dig_cidx_sort ()
 *  sort all records in cat index  
 *
 */
void dig_cidx_sort(struct Plus_head *Plus)
{
    int f;
    struct Cat_index *ci;

    G_debug(2, "dig_cidx_sort()");

    for (f = 0; f < Plus->n_cidx; f++) {
        int c, nucats = 0;

        ci = &(Plus->cidx[f]);

        /* Sort by 1. category, 2. type, 3. line id */
        qsort(ci->cat, ci->n_cats, 3 * sizeof(int), cmp_cat);

        /* Calculate number of unique cats */
        if (ci->n_cats > 0)
            nucats++;
        for (c = 1; c < ci->n_cats; c++) {
            if (ci->cat[c][0] != ci->cat[c - 1][0])
                nucats++;
        }
        ci->n_ucats = nucats;
    }

    /* Sort by field */
    qsort(Plus->cidx, Plus->n_cidx, sizeof(struct Cat_index), cmp_field);
}