Geografic-Information-System/lib/vector/rtree/node.c

/****************************************************************************
* MODULE:       R-Tree library 
*              
* AUTHOR(S):    Antonin Guttman - original code
*               Daniel Green (green@superliminal.com) - major clean-up
*                               and implementation of bounding spheres
*               
* PURPOSE:      Multidimensional index
*
* 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 <stdio.h>
#include <stdlib.h>
#include "assert.h"
#include "index.h"
#include "card.h"

/* Initialize one branch cell in a node. */
static void RTreeInitBranch(struct Branch *b)
{
    RTreeInitRect(&(b->rect));
    b->child = NULL;
}

/* Initialize a Node structure. */
void RTreeInitNode(struct Node *N)
{
    register struct Node *n = N;
    register int i;

    n->count = 0;
    n->level = -1;
    for (i = 0; i < MAXCARD; i++)
	RTreeInitBranch(&(n->branch[i]));
}

/* Make a new node and initialize to have all branch cells empty. */
struct Node *RTreeNewNode(void)
{
    register struct Node *n;

    /* n = new Node; */
    n = (struct Node *)malloc(sizeof(struct Node));
    assert(n);
    RTreeInitNode(n);
    return n;
}

void RTreeFreeNode(struct Node *p)
{
    assert(p);
    /* delete p; */
    free(p);
}

static void RTreePrintBranch(struct Branch *b, int depth)
{
    RTreePrintRect(&(b->rect), depth);
    RTreePrintNode(b->child, depth);
}

extern void RTreeTabIn(int depth)
{
    int i;

    for (i = 0; i < depth; i++)
	putchar('\t');
}

/* Print out the data in a node. */
void RTreePrintNode(struct Node *n, int depth)
{
    int i;

    assert(n);

    RTreeTabIn(depth);
    fprintf(stdout, "node");
    if (n->level == 0)
	fprintf(stdout, " LEAF");
    else if (n->level > 0)
	fprintf(stdout, " NONLEAF");
    else
	fprintf(stdout, " TYPE=?");
    fprintf(stdout, "  level=%d  count=%d  address=%o\n", n->level, n->count,
	    (unsigned)n);

    for (i = 0; i < n->count; i++) {
	if (n->level == 0) {
	    /* RTreeTabIn(depth); */
	    /* fprintf (stdout, "\t%d: data = %d\n", i, n->branch[i].child); */
	}
	else {
	    RTreeTabIn(depth);
	    fprintf(stdout, "branch %d\n", i);
	    RTreePrintBranch(&n->branch[i], depth + 1);
	}
    }
}

/*
 * Find the smallest rectangle that includes all rectangles in
 * branches of a node.
 */
struct Rect RTreeNodeCover(struct Node *N)
{
    register struct Node *n = N;
    register int i, first_time = 1;
    struct Rect r;

    assert(n);

    RTreeInitRect(&r);
    for (i = 0; i < MAXKIDS(n); i++)
	if (n->branch[i].child) {
	    if (first_time) {
		r = n->branch[i].rect;
		first_time = 0;
	    }
	    else
		r = RTreeCombineRect(&r, &(n->branch[i].rect));
	}
    return r;
}

/*
 * Pick a branch.  Pick the one that will need the smallest increase
 * in area to accomodate the new rectangle.  This will result in the
 * least total area for the covering rectangles in the current node.
 * In case of a tie, pick the one which was smaller before, to get
 * the best resolution when searching.
 */
int RTreePickBranch(struct Rect *R, struct Node *N)
{
    register struct Rect *r = R;
    register struct Node *n = N;
    register struct Rect *rr;
    register int i, first_time = 1;
    RectReal increase, bestIncr = (RectReal) - 1, area, bestArea = 0;
    int best = 0;
    struct Rect tmp_rect;

    assert(r && n);

    for (i = 0; i < MAXKIDS(n); i++) {
	if (n->branch[i].child) {
	    rr = &n->branch[i].rect;
	    area = RTreeRectSphericalVolume(rr);
	    tmp_rect = RTreeCombineRect(r, rr);
	    increase = RTreeRectSphericalVolume(&tmp_rect) - area;
	    if (increase < bestIncr || first_time) {
		best = i;
		bestArea = area;
		bestIncr = increase;
		first_time = 0;
	    }
	    else if (increase == bestIncr && area < bestArea) {
		best = i;
		bestArea = area;
		bestIncr = increase;
	    }
	}
    }
    return best;
}

/*
 * Add a branch to a node.  Split the node if necessary.
 * Returns 0 if node not split.  Old node updated.
 * Returns 1 if node split, sets *new_node to address of new node.
 * Old node updated, becomes one of two.
 */
int RTreeAddBranch(struct Branch *B, struct Node *N, struct Node **New_node)
{
    register struct Branch *b = B;
    register struct Node *n = N;
    register struct Node **new_node = New_node;
    register int i;

    assert(b);
    assert(n);

    if (n->count < MAXKIDS(n)) {	/* split won't be necessary */
	for (i = 0; i < MAXKIDS(n); i++) {	/* find empty branch */
	    if (n->branch[i].child == NULL) {
		n->branch[i] = *b;
		n->count++;
		break;
	    }
	}
	return 0;
    }
    else {
	assert(new_node);
	RTreeSplitNode(n, b, new_node);
	return 1;
    }
}

/* Disconnect a dependent node. */
void RTreeDisconnectBranch(struct Node *n, int i)
{
    assert(n && i >= 0 && i < MAXKIDS(n));
    assert(n->branch[i].child);

    RTreeInitBranch(&(n->branch[i]));
    n->count--;
}

/* Destroy (free) node recursively. */
void RTreeDestroyNode(struct Node *n)
{
    int i;

    if (n->level > 0) {		/* it is not leaf -> destroy childs */
	for (i = 0; i < NODECARD; i++) {
	    if (n->branch[i].child) {
		RTreeDestroyNode(n->branch[i].child);
	    }
	}
    }

    /* Free this node */
    RTreeFreeNode(n);
}