src/core/SkRTree.cpp

/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "SkRTree.h"
#include "SkTSort.h"

static inline uint32_t get_area(const SkIRect& rect);
static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2);
static inline uint32_t get_margin(const SkIRect& rect);
static inline uint32_t get_overlap_increase(const SkIRect& rect1, const SkIRect& rect2,
                                            SkIRect expandBy);
static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2);
static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out);

///////////////////////////////////////////////////////////////////////////////////////////////////

SkRTree* SkRTree::Create(int minChildren, int maxChildren) {
    if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren &&
        minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) {
        return new SkRTree(minChildren, maxChildren);
    }
    return NULL;
}

SkRTree::SkRTree(int minChildren, int maxChildren)
    : fMinChildren(minChildren)
    , fMaxChildren(maxChildren)
    , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren)
    , fCount(0)
    , fNodes(fNodeSize * 256) {
    SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
             static_cast<int>(SK_MaxU16));
    SkASSERT((maxChildren + 1) / 2 >= minChildren);
    this->validate();
}

SkRTree::~SkRTree() {
    this->clear();
}

void SkRTree::insert(void* data, const SkIRect& bounds, bool defer) {
    this->validate();
    if (bounds.isEmpty()) {
        SkASSERT(false);
        return;
    }
    Branch newBranch;
    newBranch.fBounds = bounds;
    newBranch.fChild.data = data;
    if (this->isEmpty()) {
        // since a bulk-load into an existing tree is as of yet unimplemented (and arguably not
        // of vital importance right now), we only batch up inserts if the tree is empty.
        if (defer) {
            fDeferredInserts.push(newBranch);
            return;
        } else {
            fRoot.fChild.subtree = allocateNode(0);
            fRoot.fChild.subtree->fNumChildren = 0;
        }
    }

    Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch);
    fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);

    if (NULL != newSibling) {
        Node* oldRoot = fRoot.fChild.subtree;
        Node* newRoot = this->allocateNode(oldRoot->fLevel + 1);
        newRoot->fNumChildren = 2;
        *newRoot->child(0) = fRoot;
        *newRoot->child(1) = *newSibling;
        fRoot.fChild.subtree = newRoot;
        fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
    }

    ++fCount;
    this->validate();
}

void SkRTree::flushDeferredInserts() {
    this->validate();
    if (this->isEmpty() && fDeferredInserts.count() > 0) {
        fCount = fDeferredInserts.count();
        if (1 == fCount) {
            fRoot.fChild.subtree = allocateNode(0);
            fRoot.fChild.subtree->fNumChildren = 0;
            this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]);
            fRoot.fBounds = fDeferredInserts[0].fBounds;
        } else {
            fRoot = this->bulkLoad(&fDeferredInserts);
        }
    } else {
        // TODO: some algorithm for bulk loading into an already populated tree
        SkASSERT(0 == fDeferredInserts.count());
    }
    fDeferredInserts.rewind();
    this->validate();
}

void SkRTree::search(const SkIRect& query, SkTDArray<void*>* results) {
    this->validate();
    if (0 != fDeferredInserts.count()) {
        this->flushDeferredInserts();
    }
    if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) {
        this->search(fRoot.fChild.subtree, query, results);
    }
    this->validate();
}

void SkRTree::clear() {
    this->validate();
    fNodes.reset();
    fDeferredInserts.rewind();
    fCount = 0;
    this->validate();
}

SkRTree::Node* SkRTree::allocateNode(uint16_t level) {
    Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize));
    out->fNumChildren = 0;
    out->fLevel = level;
    return out;
}

SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) {
    Branch* toInsert = branch;
    if (root->fLevel != level) {
        int childIndex = this->chooseSubtree(root, branch);
        toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level);
        root->child(childIndex)->fBounds = this->computeBounds(
            root->child(childIndex)->fChild.subtree);
    }
    if (NULL != toInsert) {
        if (root->fNumChildren == fMaxChildren) {
            // handle overflow by splitting. TODO: opportunistic reinsertion

            // decide on a distribution to divide with
            Node* newSibling = this->allocateNode(root->fLevel);
            Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1);
            for (int i = 0; i < fMaxChildren; ++i) {
                toDivide[i] = *root->child(i);
            }
            toDivide[fMaxChildren] = *toInsert;
            int splitIndex = this->distributeChildren(toDivide);

            // divide up the branches
            root->fNumChildren = splitIndex;
            newSibling->fNumChildren = fMaxChildren + 1 - splitIndex;
            for (int i = 0; i < splitIndex; ++i) {
                *root->child(i) = toDivide[i];
            }
            for (int i = splitIndex; i < fMaxChildren + 1; ++i) {
                *newSibling->child(i - splitIndex) = toDivide[i];
            }
            SkDELETE_ARRAY(toDivide);

            // pass the new sibling branch up to the parent
            branch->fChild.subtree = newSibling;
            branch->fBounds = this->computeBounds(newSibling);
            return branch;
        } else {
            *root->child(root->fNumChildren) = *toInsert;
            ++root->fNumChildren;
            return NULL;
        }
    }
    return NULL;
}

int SkRTree::chooseSubtree(Node* root, Branch* branch) {
    SkASSERT(!root->isLeaf());
    if (1 < root->fLevel) {
        // root's child pointers do not point to leaves, so minimize area increase
        int32_t minAreaIncrease = SK_MaxS32;
        int32_t minArea         = SK_MaxS32;
        int32_t bestSubtree     = -1;
        for (int i = 0; i < root->fNumChildren; ++i) {
            const SkIRect& subtreeBounds = root->child(i)->fBounds;
            int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBounds);
            // break ties in favor of subtree with smallest area
            if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrease &&
                static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) {
                minAreaIncrease = areaIncrease;
                minArea = get_area(subtreeBounds);
                bestSubtree = i;
            }
        }
        SkASSERT(-1 != bestSubtree);
        return bestSubtree;
    } else if (1 == root->fLevel) {
        // root's child pointers do point to leaves, so minimize overlap increase
        int32_t minOverlapIncrease = SK_MaxS32;
        int32_t minAreaIncrease    = SK_MaxS32;
        int32_t bestSubtree = -1;
        for (int32_t i = 0; i < root->fNumChildren; ++i) {
            const SkIRect& subtreeBounds = root->child(i)->fBounds;
            SkIRect expandedBounds = subtreeBounds;
            join_no_empty_check(branch->fBounds, &expandedBounds);
            int32_t overlap = 0;
            for (int32_t j = 0; j < root->fNumChildren; ++j) {
                if (j == i) continue;
                // Note: this would be more correct if we subtracted the original pre-expanded
                // overlap, but computing overlaps is expensive and omitting it doesn't seem to
                // hurt query performance. See get_overlap_increase()
                overlap += get_overlap(expandedBounds, root->child(j)->fBounds);
            }
            // break ties with lowest area increase
            if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease &&
                static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) <
                minAreaIncrease)) {
                minOverlapIncrease = overlap;
                minAreaIncrease = get_area_increase(branch->fBounds, subtreeBounds);
                bestSubtree = i;
            }
        }
        return bestSubtree;
    } else {
        SkASSERT(false);
        return 0;
    }
}

SkIRect SkRTree::computeBounds(Node* n) {
    SkIRect r = n->child(0)->fBounds;
    for (int i = 1; i < n->fNumChildren; ++i) {
        join_no_empty_check(n->child(i)->fBounds, &r);
    }
    return r;
}

int SkRTree::distributeChildren(Branch* children) {
    // We have two sides to sort by on each of two axes:
    const static SortSide sorts[2][2] = {
        {&SkIRect::fLeft, &SkIRect::fRight},
        {&SkIRect::fTop, &SkIRect::fBottom}
    };

    // We want to choose an axis to split on, then a distribution along that axis; we'll need
    // three pieces of info: the split axis, the side to sort by on that axis, and the index
    // to split the sorted array on.
    int32_t sortSide = -1;
    int32_t k        = -1;
    int32_t axis     = -1;
    int32_t bestS    = SK_MaxS32;

    // Evaluate each axis, we want the min summed margin-value (s) over all distributions
    for (int i = 0; i < 2; ++i) {
        int32_t minOverlap   = SK_MaxS32;
        int32_t minArea      = SK_MaxS32;
        int32_t axisBestK    = 0;
        int32_t axisBestSide = 0;
        int32_t s = 0;

        // Evaluate each sort
        for (int j = 0; j < 2; ++j) {

            SkQSort(sorts[i][j], children, children + fMaxChildren, &RectLessThan);

            // Evaluate each split index
            for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) {
                SkIRect r1 = children[0].fBounds;
                SkIRect r2 = children[fMinChildren + k - 1].fBounds;
                for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) {
                    join_no_empty_check(children[l].fBounds, &r1);
                }
                for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) {
                    join_no_empty_check(children[l].fBounds, &r2);
                }

                int32_t area = get_area(r1) + get_area(r2);
                int32_t overlap = get_overlap(r1, r2);
                s += get_margin(r1) + get_margin(r2);

                if (overlap < minOverlap || (overlap == minOverlap && area < minArea)) {
                    minOverlap = overlap;
                    minArea = area;
                    axisBestSide = j;
                    axisBestK = k;
                }
            }
        }

        if (s < bestS) {
            bestS = s;
            axis = i;
            sortSide = axisBestSide;
            k = axisBestK;
        }
    }

    // replicate the sort of the winning distribution, (we can skip this if the last
    // sort ended up being best)
    if (!(axis == 1 && sortSide == 1)) {
        SkQSort(sorts[axis][sortSide], children, children + fMaxChildren, &RectLessThan);
    }

    return fMinChildren - 1 + k;
}

void SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* results) const {
    for (int i = 0; i < root->fNumChildren; ++i) {
        if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) {
            if (root->isLeaf()) {
                results->push(root->child(i)->fChild.data);
            } else {
                this->search(root->child(i)->fChild.subtree, query, results);
            }
        }
    }
}

SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
    if (branches->count() == 1) {
        // Only one branch: it will be the root
        Branch out = (*branches)[0];
        branches->rewind();
        return out;
    } else {
        // First we sort the whole list by y coordinates
        SkQSort<int, Branch>(level, branches->begin(), branches->end() - 1, &RectLessY);

        int numBranches = branches->count() / fMaxChildren;
        int remainder = branches->count() % fMaxChildren;
        int newBranches = 0;

        if (0 != remainder) {
            ++numBranches;
            // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to
            // some other branches to make up for it
            if (remainder >= fMinChildren) {
                remainder = 0;
            } else {
                remainder = fMinChildren - remainder;
            }
        }

        int numStrips = SkScalarCeil(SkScalarSqrt(SkIntToScalar(numBranches)));
        int currentBranch = 0;

        for (int i = 0; i < numStrips; ++i) {
            int begin = currentBranch;
            int end = currentBranch + numStrips * fMaxChildren - SkMin32(remainder,
                      (fMaxChildren - fMinChildren) * numStrips);
            if (end > branches->count()) {
                end = branches->count();
            }

            // Now we sort horizontal strips of rectangles by their x coords
            SkQSort<int, Branch>(level, branches->begin() + begin, branches->begin() + end - 1,
                                 &RectLessX);

            for (int j = 0; j < numStrips && currentBranch < branches->count(); ++j) {
                int incrementBy = fMaxChildren;
                if (remainder != 0) {
                    // if need be, omit some nodes to make up for remainder
                    if (remainder <= fMaxChildren - fMinChildren) {
                        incrementBy -= remainder;
                        remainder = 0;
                    } else {
                        incrementBy = fMinChildren;
                        remainder -= fMaxChildren - fMinChildren;
                    }
                }
                Node* n = allocateNode(level);
                n->fNumChildren = 1;
                *n->child(0) = (*branches)[currentBranch];
                Branch b;
                b.fBounds = (*branches)[currentBranch].fBounds;
                b.fChild.subtree = n;
                ++currentBranch;
                for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
                    b.fBounds.join((*branches)[currentBranch].fBounds);
                    *n->child(k) = (*branches)[currentBranch];
                    ++n->fNumChildren;
                    ++currentBranch;
                }
                (*branches)[newBranches] = b;
                ++newBranches;
            }
        }
        branches->setCount(newBranches);
        return this->bulkLoad(branches, level + 1);
    }
}

void SkRTree::validate() {
#ifdef SK_DEBUG
    if (this->isEmpty()) {
        return;
    }
    SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true));
#endif
}

int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) {
    // make sure the pointer is pointing to a valid place
    SkASSERT(fNodes.contains(static_cast<void*>(root)));

    if (isRoot) {
        // If the root of this subtree is the overall root, we have looser standards:
        if (root->isLeaf()) {
            SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildren);
        } else {
            SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren);
        }
    } else {
        SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren);
    }

    for (int i = 0; i < root->fNumChildren; ++i) {
        SkASSERT(bounds.contains(root->child(i)->fBounds));
    }

    if (root->isLeaf()) {
        SkASSERT(0 == root->fLevel);
        return root->fNumChildren;
    } else {
        int childCount = 0;
        for (int i = 0; i < root->fNumChildren; ++i) {
            SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1);
            childCount += this->validateSubtree(root->child(i)->fChild.subtree,
                                                root->child(i)->fBounds);
        }
        return childCount;
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////////

static inline uint32_t get_area(const SkIRect& rect) {
    return rect.width() * rect.height();
}

static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) {
    // I suspect there's a more efficient way of computing this...
    return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) *
           SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop, rect2.fTop));
}

// Get the margin (aka perimeter)
static inline uint32_t get_margin(const SkIRect& rect) {
    return 2 * (rect.width() + rect.height());
}

static inline uint32_t get_overlap_increase(const SkIRect& rect1, const SkIRect& rect2,
                                          SkIRect expandBy) {
    join_no_empty_check(rect1, &expandBy);
    return get_overlap(expandBy, rect2) - get_overlap(rect1, rect2);
}

static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) {
    join_no_empty_check(rect1, &rect2);
    return get_area(rect2) - get_area(rect1);
}

// Expand 'out' to include 'joinWith'
static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) {
    // since we check for empty bounds on insert, we know we'll never have empty rects
    // and we can save the empty check that SkIRect::join requires
    if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; }
    if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; }
    if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; }
    if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; }
}