split.q.c

Go to the documentation of this file.

/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: Details at https://graphviz.org
 *************************************************************************/
 
#include <inttypes.h>
#include <label/index.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <assert.h>
#include <label/split.q.h>
#include <stdbool.h>
 
/* Forward declarations */
static void MethodZero(RTree_t * rtp);
static void InitPVars(RTree_t * rtp);
static void LoadNodes(RTree_t *rtp, Node_t *n, Node_t *q);
static void Classify(RTree_t * rtp, int i, int group);
static void PickSeeds(RTree_t * rtp);
static void GetBranches(RTree_t * rtp, Node_t * n, Branch_t * b);
 
/*-----------------------------------------------------------------------------
| Split a node.
| Divides the nodes branches and the extra one between two nodes.
| Old node is one of the new ones, and one really new one is created.
| Tries more than one method for choosing a partition, uses best result.
-----------------------------------------------------------------------------*/
void SplitNode(RTree_t * rtp, Node_t * n, Branch_t * b, Node_t ** nn)
{
    assert(n);
    assert(b);
 
#ifdef RTDEBUG
    fprintf(stderr, "Splitting:\n");
    PrintNode(n);
    fprintf(stderr, "new branch:\n");
    PrintBranch(-1, b);
#endif
 
    /* load all the branches into a buffer, initialize old node */
    int level = n->level;
    GetBranches(rtp, n, b);
 
#ifdef RTDEBUG
    {
        /* Indicate that a split is about to take place */
        for (size_t i = 0; i < NODECARD + 1; i++) {
            PrintRect(&rtp->split.BranchBuf[i].rect);
        }
        PrintRect(&rtp->split.CoverSplit);
    }
#endif
 
    /* find partition */
#ifdef RTDEBUG
    struct PartitionVars *p = &rtp->split.Partitions[0];
#endif
    MethodZero(rtp);
 
    /* put branches from buffer into 2 nodes according to chosen partition */
    *nn = RTreeNewNode();
    (*nn)->level = n->level = level;
    LoadNodes(rtp, n, *nn);
    assert(n->count + (*nn)->count == NODECARD + 1);
 
#ifdef RTDEBUG
    PrintPVars(p);
    fprintf(stderr, "group 0:\n");
    PrintNode(n);
    fprintf(stderr, "group 1:\n");
    PrintNode(*nn);
    fprintf(stderr, "\n");
#endif
 
}
 
/*-----------------------------------------------------------------------------
| Load branch buffer with branches from full node plus the extra branch.
-----------------------------------------------------------------------------*/
static void GetBranches(RTree_t * rtp, Node_t * n, Branch_t * b)
{
    assert(n);
    assert(b);
 
    /* load the branch buffer */
    for (size_t i = 0; i < NODECARD; i++) {
        assert(n->branch[i].child);     /* node should have every entry full */
        rtp->split.BranchBuf[i] = n->branch[i];
    }
    rtp->split.BranchBuf[NODECARD] = *b;
 
    /* calculate rect containing all in the set */
    rtp->split.CoverSplit = rtp->split.BranchBuf[0].rect;
    for (size_t i = 1; i < NODECARD + 1; i++) {
        rtp->split.CoverSplit = CombineRect(&rtp->split.CoverSplit,
                                            &rtp->split.BranchBuf[i].rect);
    }
    rtp->split.CoverSplitArea = RectArea(&rtp->split.CoverSplit);
 
    InitNode(n);
}
 
/*-----------------------------------------------------------------------------
| Method #0 for choosing a partition:
| As the seeds for the two groups, pick the two rects that would waste the
| most area if covered by a single rectangle, i.e. evidently the worst pair
| to have in the same group.
| Of the remaining, one at a time is chosen to be put in one of the two groups.
| The one chosen is the one with the greatest difference in area expansion
| depending on which group - the rect most strongly attracted to one group
| and repelled from the other.
| If one group gets too full (more would force other group to violate min
| fill requirement) then other group gets the rest.
| These last are the ones that can go in either group most easily.
-----------------------------------------------------------------------------*/
static void MethodZero(RTree_t * rtp)
{
    int group, chosen = 0, betterGroup = 0;
 
    InitPVars(rtp);
    PickSeeds(rtp);
 
    while (rtp->split.Partitions[0].count[0] +
           rtp->split.Partitions[0].count[1] < NODECARD + 1 &&
           rtp->split.Partitions[0].count[0] < NODECARD + 1
           && rtp->split.Partitions[0].count[1] < NODECARD + 1) {
        bool biggestDiffSet = false;
        uint64_t biggestDiff = 0;
        for (int i = 0; i < NODECARD + 1; i++) {
            if (!rtp->split.Partitions[0].taken[i]) {
                Rect_t *r = &rtp->split.BranchBuf[i].rect;
                Rect_t rect = CombineRect(r, &rtp->split.Partitions[0].cover[0]);
                uint64_t growth0 = RectArea(&rect) - rtp->split.Partitions[0].area[0];
                rect = CombineRect(r, &rtp->split.Partitions[0].cover[1]);
                uint64_t growth1 = RectArea(&rect) - rtp->split.Partitions[0].area[1];
                uint64_t diff;
                if (growth1 >= growth0) {
                    diff = growth1 - growth0;
                    group = 0;
                } else {
                    diff = growth0 - growth1;
                    group = 1;
                }
 
                if (!biggestDiffSet || diff > biggestDiff) {
                    biggestDiff = diff;
                    biggestDiffSet = true;
                    chosen = i;
                    betterGroup = group;
                } else if (diff == biggestDiff &&
                           rtp->split.Partitions[0].count[group] <
                           rtp->split.Partitions[0].count[betterGroup]) {
                    chosen = i;
                    betterGroup = group;
                }
            }
        }
        Classify(rtp, chosen, betterGroup);
    }
 
    /* if one group too full, put remaining rects in the other */
    if (rtp->split.Partitions[0].count[0] +
        rtp->split.Partitions[0].count[1] < NODECARD + 1) {
        group = 0;
        if (rtp->split.Partitions[0].count[0] >= NODECARD + 1)
            group = 1;
        for (int i = 0; i < NODECARD + 1; i++) {
            if (!rtp->split.Partitions[0].taken[i])
                Classify(rtp, i, group);
        }
    }
 
    assert(rtp->split.Partitions[0].count[0] +
           rtp->split.Partitions[0].count[1] == NODECARD + 1);
    assert(rtp->split.Partitions[0].count[0] >= 0
           && rtp->split.Partitions[0].count[1] >= 0);
}
 
/*-----------------------------------------------------------------------------
| Pick two rects from set to be the first elements of the two groups.
| Pick the two that waste the most area if covered by a single rectangle.
-----------------------------------------------------------------------------*/
static void PickSeeds(RTree_t * rtp)
{
  int seed0 = 0, seed1 = 0;
  uint64_t area[NODECARD + 1];
 
    for (int i = 0; i < NODECARD + 1; i++)
        area[i] = RectArea(&rtp->split.BranchBuf[i].rect);
 
    uint64_t worst=0;
    for (int i = 0; i < NODECARD; i++) {
        for (int j = i + 1; j < NODECARD + 1; j++) {
            Rect_t rect = CombineRect(&rtp->split.BranchBuf[i].rect,
                                      &rtp->split.BranchBuf[j].rect);
            uint64_t waste = RectArea(&rect) - area[i] - area[j];
            if (waste > worst) {
                worst = waste;
                seed0 = i;
                seed1 = j;
            }
        }
    }
    Classify(rtp, seed0, 0);
    Classify(rtp, seed1, 1);
}
 
/*-----------------------------------------------------------------------------
| Put a branch in one of the groups.
-----------------------------------------------------------------------------*/
static void Classify(RTree_t * rtp, int i, int group)
{
 
    assert(!rtp->split.Partitions[0].taken[i]);
 
    rtp->split.Partitions[0].partition[i] = group;
    rtp->split.Partitions[0].taken[i] = true;
 
    if (rtp->split.Partitions[0].count[group] == 0)
        rtp->split.Partitions[0].cover[group] =
            rtp->split.BranchBuf[i].rect;
    else
        rtp->split.Partitions[0].cover[group] =
            CombineRect(&rtp->split.BranchBuf[i].rect,
                        &rtp->split.Partitions[0].cover[group]);
    rtp->split.Partitions[0].area[group] =
        RectArea(&rtp->split.Partitions[0].cover[group]);
    rtp->split.Partitions[0].count[group]++;
 
#       ifdef RTDEBUG
    {
        /* redraw entire group and its cover */
        int j;
        MFBSetColor(WHITE);     /* cover is white */
        PrintRect(&rtp->split.Partitions[0].cover[group]);
        MFBSetColor(group + 3); /* group 0 green, group 1 blue */
        for (j = 0; j < NODECARD + 1; j++) {
            if (rtp->split.Partitions[0].taken[j] &&
                rtp->split.Partitions[0].partition[j] == group)
                PrintRect(&rtrtp->split.Partitions[0].BranchBuf[j].rect);
        }
        GraphChar();
    }
#       endif
}
 
/*-----------------------------------------------------------------------------
| Copy branches from the buffer into two nodes according to the partition.
-----------------------------------------------------------------------------*/
static void LoadNodes(RTree_t *rtp, Node_t *n, Node_t *q) {
    assert(n);
    assert(q);
 
    for (size_t i = 0; i < NODECARD + 1; i++) {
        assert(rtp->split.Partitions[0].partition[i] == 0 ||
               rtp->split.Partitions[0].partition[i] == 1);
        if (rtp->split.Partitions[0].partition[i] == 0)
            AddBranch(rtp, &rtp->split.BranchBuf[i], n, NULL);
        else if (rtp->split.Partitions[0].partition[i] == 1)
            AddBranch(rtp, &rtp->split.BranchBuf[i], q, NULL);
    }
}
 
/*-----------------------------------------------------------------------------
| Initialize a PartitionVars structure.
-----------------------------------------------------------------------------*/
static void InitPVars(RTree_t * rtp)
{
    rtp->split.Partitions[0].count[0] = rtp->split.Partitions[0].count[1] =
        0;
    rtp->split.Partitions[0].cover[0] = rtp->split.Partitions[0].cover[1] =
        NullRect();
    rtp->split.Partitions[0].area[0] = rtp->split.Partitions[0].area[1] =
        0;
    for (size_t i = 0; i < NODECARD + 1; i++) {
        rtp->split.Partitions[0].taken[i] = false;
        rtp->split.Partitions[0].partition[i] = -1;
    }
}
 
#ifdef RTDEBUG
 
/*-----------------------------------------------------------------------------
| Print out data for a partition from PartitionVars struct.
-----------------------------------------------------------------------------*/
PrintPVars(RTree_t * rtp)
{
    fprintf(stderr, "\npartition:\n");
    for (size_t i = 0; i < NODECARD + 1; i++) {
        fprintf(stderr, "%3zu\t", i);
    }
    fprintf(stderr, "\n");
    for (size_t i = 0; i < NODECARD + 1; i++) {
        if (rtp->split.Partitions[0].taken[i])
            fprintf(stderr, "  t\t");
        else
            fprintf(stderr, "\t");
    }
    fprintf(stderr, "\n");
    for (size_t i = 0; i < NODECARD + 1; i++) {
        fprintf(stderr, "%3d\t", rtp->split.Partitions[0].partition[i]);
    }
    fprintf(stderr, "\n");
 
    fprintf(stderr, "count[0] = %d  area = %" PRIu64 "\n",
            rtp->split.Partitions[0].count[0],
            rtp->split.Partitions[0].area[0]);
    fprintf(stderr, "count[1] = %d  area = %" PRIu64 "\n",
            rtp->split.Partitions[0].count[1],
            rtp->split.Partitions[0].area[1]);
    if (rtp->split.Partitions[0].area[0] +
        rtp->split.Partitions[0].area[1] > 0) {
        fprintf(stderr, "total area = %" PRIu64 "  effectiveness = %3.2f\n",
                rtp->split.Partitions[0].area[0] +
                rtp->split.Partitions[0].area[1],
                (float) rtp->split.CoverSplitArea /
                (rtp->split.Partitions[0].area[0] +
                 rtp->split.Partitions[0].area[1]));
    }
    fprintf(stderr, "cover[0]:\n");
    PrintRect(&rtp->split.Partitions[0].cover[0]);
 
    fprintf(stderr, "cover[1]:\n");
    PrintRect(&rtp->split.Partitions[0].cover[1]);
}
#endif