itree_merge_nodes()

static uint32_t itree_merge_nodes ( IntervalTree *  itree, uint32_t  nodes_remaining  )

static

Definition at line 116 of file intervaltree.c.

 {
        /*
         * store the starting state of the tree which gives
         * us the array of nodes we are going to have to merge
         */
        uint32_t end_node = itree->numNodes;
        uint32_t start_node = end_node - nodes_remaining;
 
        /*
         * one parent for every ITREE_MAX_NODES children
         * plus one for the remainder
         */
        uint32_t num_parents = nodes_remaining / ITREE_MAX_NODES;
        num_parents += ((nodes_remaining % ITREE_MAX_NODES) > 0);
 
        /*
         * each parent is composed by merging four adjacent children
         * this generates a useful index structure in O(n) time
         * because the edges are from a ring, and thus are
         * spatially autocorrelated, so the pre-sorting step of
         * building a packed index is already done for us before we even start
         */
        for (uint32_t i = 0; i < num_parents; i++)
        {
                uint32_t children_start = start_node + i * ITREE_MAX_NODES;
                uint32_t children_end = start_node + (i+1) * ITREE_MAX_NODES;
                children_end = children_end > end_node ? end_node : children_end;
 
                /*
                 * put pointers to the children we are merging onto
                 * the new parent node
                 */
                IntervalTreeNode *parent_node = itree_new_node(itree);
                for (uint32_t j = children_start; j < children_end; j++)
                {
                        IntervalTreeNode *child_node = &(itree->nodes[j]);
                        parent_node->min = FP_MIN(child_node->min, parent_node->min);
                        parent_node->max = FP_MAX(child_node->max, parent_node->max);
                        parent_node->edgeIndex = FP_MIN(child_node->edgeIndex, parent_node->edgeIndex);
                        parent_node->children[parent_node->numChildren++] = child_node;
                }
        }
 
        /*
         * keep going until num_parents gets down to one and
         * we are at the root of the tree
         */
        return num_parents;
}

References IntervalTreeNode::children, IntervalTreeNode::edgeIndex, FP_MAX, FP_MIN, ITREE_MAX_NODES, itree_new_node(), IntervalTreeNode::max, IntervalTreeNode::min, IntervalTree::nodes, IntervalTreeNode::numChildren, and IntervalTree::numNodes.

Referenced by itree_add_pointarray().

Here is the call graph for this function:

Here is the caller graph for this function: