michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #include "SkRTree.h"
michael@0: #include "SkTSort.h"
michael@0: 
michael@0: static inline uint32_t get_area(const SkIRect& rect);
michael@0: static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2);
michael@0: static inline uint32_t get_margin(const SkIRect& rect);
michael@0: static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2);
michael@0: static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out);
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio,
michael@0:             bool sortWhenBulkLoading) {
michael@0:     if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren &&
michael@0:         minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) {
michael@0:         return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLoading);
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio,
michael@0:         bool sortWhenBulkLoading)
michael@0:     : fMinChildren(minChildren)
michael@0:     , fMaxChildren(maxChildren)
michael@0:     , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren)
michael@0:     , fCount(0)
michael@0:     , fNodes(fNodeSize * 256)
michael@0:     , fAspectRatio(aspectRatio)
michael@0:     , fSortWhenBulkLoading(sortWhenBulkLoading) {
michael@0:     SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
michael@0:              static_cast<int>(SK_MaxU16));
michael@0:     SkASSERT((maxChildren + 1) / 2 >= minChildren);
michael@0:     this->validate();
michael@0: }
michael@0: 
michael@0: SkRTree::~SkRTree() {
michael@0:     this->clear();
michael@0: }
michael@0: 
michael@0: void SkRTree::insert(void* data, const SkIRect& bounds, bool defer) {
michael@0:     this->validate();
michael@0:     if (bounds.isEmpty()) {
michael@0:         SkASSERT(false);
michael@0:         return;
michael@0:     }
michael@0:     Branch newBranch;
michael@0:     newBranch.fBounds = bounds;
michael@0:     newBranch.fChild.data = data;
michael@0:     if (this->isEmpty()) {
michael@0:         // since a bulk-load into an existing tree is as of yet unimplemented (and arguably not
michael@0:         // of vital importance right now), we only batch up inserts if the tree is empty.
michael@0:         if (defer) {
michael@0:             fDeferredInserts.push(newBranch);
michael@0:             return;
michael@0:         } else {
michael@0:             fRoot.fChild.subtree = allocateNode(0);
michael@0:             fRoot.fChild.subtree->fNumChildren = 0;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch);
michael@0:     fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
michael@0: 
michael@0:     if (NULL != newSibling) {
michael@0:         Node* oldRoot = fRoot.fChild.subtree;
michael@0:         Node* newRoot = this->allocateNode(oldRoot->fLevel + 1);
michael@0:         newRoot->fNumChildren = 2;
michael@0:         *newRoot->child(0) = fRoot;
michael@0:         *newRoot->child(1) = *newSibling;
michael@0:         fRoot.fChild.subtree = newRoot;
michael@0:         fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
michael@0:     }
michael@0: 
michael@0:     ++fCount;
michael@0:     this->validate();
michael@0: }
michael@0: 
michael@0: void SkRTree::flushDeferredInserts() {
michael@0:     this->validate();
michael@0:     if (this->isEmpty() && fDeferredInserts.count() > 0) {
michael@0:         fCount = fDeferredInserts.count();
michael@0:         if (1 == fCount) {
michael@0:             fRoot.fChild.subtree = allocateNode(0);
michael@0:             fRoot.fChild.subtree->fNumChildren = 0;
michael@0:             this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]);
michael@0:             fRoot.fBounds = fDeferredInserts[0].fBounds;
michael@0:         } else {
michael@0:             fRoot = this->bulkLoad(&fDeferredInserts);
michael@0:         }
michael@0:     } else {
michael@0:         // TODO: some algorithm for bulk loading into an already populated tree
michael@0:         SkASSERT(0 == fDeferredInserts.count());
michael@0:     }
michael@0:     fDeferredInserts.rewind();
michael@0:     this->validate();
michael@0: }
michael@0: 
michael@0: void SkRTree::search(const SkIRect& query, SkTDArray<void*>* results) {
michael@0:     this->validate();
michael@0:     if (0 != fDeferredInserts.count()) {
michael@0:         this->flushDeferredInserts();
michael@0:     }
michael@0:     if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) {
michael@0:         this->search(fRoot.fChild.subtree, query, results);
michael@0:     }
michael@0:     this->validate();
michael@0: }
michael@0: 
michael@0: void SkRTree::clear() {
michael@0:     this->validate();
michael@0:     fNodes.reset();
michael@0:     fDeferredInserts.rewind();
michael@0:     fCount = 0;
michael@0:     this->validate();
michael@0: }
michael@0: 
michael@0: SkRTree::Node* SkRTree::allocateNode(uint16_t level) {
michael@0:     Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize));
michael@0:     out->fNumChildren = 0;
michael@0:     out->fLevel = level;
michael@0:     return out;
michael@0: }
michael@0: 
michael@0: SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) {
michael@0:     Branch* toInsert = branch;
michael@0:     if (root->fLevel != level) {
michael@0:         int childIndex = this->chooseSubtree(root, branch);
michael@0:         toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level);
michael@0:         root->child(childIndex)->fBounds = this->computeBounds(
michael@0:             root->child(childIndex)->fChild.subtree);
michael@0:     }
michael@0:     if (NULL != toInsert) {
michael@0:         if (root->fNumChildren == fMaxChildren) {
michael@0:             // handle overflow by splitting. TODO: opportunistic reinsertion
michael@0: 
michael@0:             // decide on a distribution to divide with
michael@0:             Node* newSibling = this->allocateNode(root->fLevel);
michael@0:             Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1);
michael@0:             for (int i = 0; i < fMaxChildren; ++i) {
michael@0:                 toDivide[i] = *root->child(i);
michael@0:             }
michael@0:             toDivide[fMaxChildren] = *toInsert;
michael@0:             int splitIndex = this->distributeChildren(toDivide);
michael@0: 
michael@0:             // divide up the branches
michael@0:             root->fNumChildren = splitIndex;
michael@0:             newSibling->fNumChildren = fMaxChildren + 1 - splitIndex;
michael@0:             for (int i = 0; i < splitIndex; ++i) {
michael@0:                 *root->child(i) = toDivide[i];
michael@0:             }
michael@0:             for (int i = splitIndex; i < fMaxChildren + 1; ++i) {
michael@0:                 *newSibling->child(i - splitIndex) = toDivide[i];
michael@0:             }
michael@0:             SkDELETE_ARRAY(toDivide);
michael@0: 
michael@0:             // pass the new sibling branch up to the parent
michael@0:             branch->fChild.subtree = newSibling;
michael@0:             branch->fBounds = this->computeBounds(newSibling);
michael@0:             return branch;
michael@0:         } else {
michael@0:             *root->child(root->fNumChildren) = *toInsert;
michael@0:             ++root->fNumChildren;
michael@0:             return NULL;
michael@0:         }
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: int SkRTree::chooseSubtree(Node* root, Branch* branch) {
michael@0:     SkASSERT(!root->isLeaf());
michael@0:     if (1 < root->fLevel) {
michael@0:         // root's child pointers do not point to leaves, so minimize area increase
michael@0:         int32_t minAreaIncrease = SK_MaxS32;
michael@0:         int32_t minArea         = SK_MaxS32;
michael@0:         int32_t bestSubtree     = -1;
michael@0:         for (int i = 0; i < root->fNumChildren; ++i) {
michael@0:             const SkIRect& subtreeBounds = root->child(i)->fBounds;
michael@0:             int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBounds);
michael@0:             // break ties in favor of subtree with smallest area
michael@0:             if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrease &&
michael@0:                 static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) {
michael@0:                 minAreaIncrease = areaIncrease;
michael@0:                 minArea = get_area(subtreeBounds);
michael@0:                 bestSubtree = i;
michael@0:             }
michael@0:         }
michael@0:         SkASSERT(-1 != bestSubtree);
michael@0:         return bestSubtree;
michael@0:     } else if (1 == root->fLevel) {
michael@0:         // root's child pointers do point to leaves, so minimize overlap increase
michael@0:         int32_t minOverlapIncrease = SK_MaxS32;
michael@0:         int32_t minAreaIncrease    = SK_MaxS32;
michael@0:         int32_t bestSubtree = -1;
michael@0:         for (int32_t i = 0; i < root->fNumChildren; ++i) {
michael@0:             const SkIRect& subtreeBounds = root->child(i)->fBounds;
michael@0:             SkIRect expandedBounds = subtreeBounds;
michael@0:             join_no_empty_check(branch->fBounds, &expandedBounds);
michael@0:             int32_t overlap = 0;
michael@0:             for (int32_t j = 0; j < root->fNumChildren; ++j) {
michael@0:                 if (j == i) continue;
michael@0:                 // Note: this would be more correct if we subtracted the original pre-expanded
michael@0:                 // overlap, but computing overlaps is expensive and omitting it doesn't seem to
michael@0:                 // hurt query performance. See get_overlap_increase()
michael@0:                 overlap += get_overlap(expandedBounds, root->child(j)->fBounds);
michael@0:             }
michael@0:             // break ties with lowest area increase
michael@0:             if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease &&
michael@0:                 static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) <
michael@0:                 minAreaIncrease)) {
michael@0:                 minOverlapIncrease = overlap;
michael@0:                 minAreaIncrease = get_area_increase(branch->fBounds, subtreeBounds);
michael@0:                 bestSubtree = i;
michael@0:             }
michael@0:         }
michael@0:         return bestSubtree;
michael@0:     } else {
michael@0:         SkASSERT(false);
michael@0:         return 0;
michael@0:     }
michael@0: }
michael@0: 
michael@0: SkIRect SkRTree::computeBounds(Node* n) {
michael@0:     SkIRect r = n->child(0)->fBounds;
michael@0:     for (int i = 1; i < n->fNumChildren; ++i) {
michael@0:         join_no_empty_check(n->child(i)->fBounds, &r);
michael@0:     }
michael@0:     return r;
michael@0: }
michael@0: 
michael@0: int SkRTree::distributeChildren(Branch* children) {
michael@0:     // We have two sides to sort by on each of two axes:
michael@0:     const static SortSide sorts[2][2] = {
michael@0:         {&SkIRect::fLeft, &SkIRect::fRight},
michael@0:         {&SkIRect::fTop, &SkIRect::fBottom}
michael@0:     };
michael@0: 
michael@0:     // We want to choose an axis to split on, then a distribution along that axis; we'll need
michael@0:     // three pieces of info: the split axis, the side to sort by on that axis, and the index
michael@0:     // to split the sorted array on.
michael@0:     int32_t sortSide = -1;
michael@0:     int32_t k        = -1;
michael@0:     int32_t axis     = -1;
michael@0:     int32_t bestS    = SK_MaxS32;
michael@0: 
michael@0:     // Evaluate each axis, we want the min summed margin-value (s) over all distributions
michael@0:     for (int i = 0; i < 2; ++i) {
michael@0:         int32_t minOverlap   = SK_MaxS32;
michael@0:         int32_t minArea      = SK_MaxS32;
michael@0:         int32_t axisBestK    = 0;
michael@0:         int32_t axisBestSide = 0;
michael@0:         int32_t s = 0;
michael@0: 
michael@0:         // Evaluate each sort
michael@0:         for (int j = 0; j < 2; ++j) {
michael@0:             SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j]));
michael@0: 
michael@0:             // Evaluate each split index
michael@0:             for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) {
michael@0:                 SkIRect r1 = children[0].fBounds;
michael@0:                 SkIRect r2 = children[fMinChildren + k - 1].fBounds;
michael@0:                 for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) {
michael@0:                     join_no_empty_check(children[l].fBounds, &r1);
michael@0:                 }
michael@0:                 for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) {
michael@0:                     join_no_empty_check(children[l].fBounds, &r2);
michael@0:                 }
michael@0: 
michael@0:                 int32_t area = get_area(r1) + get_area(r2);
michael@0:                 int32_t overlap = get_overlap(r1, r2);
michael@0:                 s += get_margin(r1) + get_margin(r2);
michael@0: 
michael@0:                 if (overlap < minOverlap || (overlap == minOverlap && area < minArea)) {
michael@0:                     minOverlap = overlap;
michael@0:                     minArea = area;
michael@0:                     axisBestSide = j;
michael@0:                     axisBestK = k;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         if (s < bestS) {
michael@0:             bestS = s;
michael@0:             axis = i;
michael@0:             sortSide = axisBestSide;
michael@0:             k = axisBestK;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // replicate the sort of the winning distribution, (we can skip this if the last
michael@0:     // sort ended up being best)
michael@0:     if (!(axis == 1 && sortSide == 1)) {
michael@0:         SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide]));
michael@0:     }
michael@0: 
michael@0:     return fMinChildren - 1 + k;
michael@0: }
michael@0: 
michael@0: void SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* results) const {
michael@0:     for (int i = 0; i < root->fNumChildren; ++i) {
michael@0:         if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) {
michael@0:             if (root->isLeaf()) {
michael@0:                 results->push(root->child(i)->fChild.data);
michael@0:             } else {
michael@0:                 this->search(root->child(i)->fChild.subtree, query, results);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
michael@0:     if (branches->count() == 1) {
michael@0:         // Only one branch: it will be the root
michael@0:         Branch out = (*branches)[0];
michael@0:         branches->rewind();
michael@0:         return out;
michael@0:     } else {
michael@0:         // We sort the whole list by y coordinates, if we are told to do so.
michael@0:         //
michael@0:         // We expect Webkit / Blink to give us a reasonable x,y order.
michael@0:         // Avoiding this call resulted in a 17% win for recording with
michael@0:         // negligible difference in playback speed.
michael@0:         if (fSortWhenBulkLoading) {
michael@0:             SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
michael@0:         }
michael@0: 
michael@0:         int numBranches = branches->count() / fMaxChildren;
michael@0:         int remainder = branches->count() % fMaxChildren;
michael@0:         int newBranches = 0;
michael@0: 
michael@0:         if (0 != remainder) {
michael@0:             ++numBranches;
michael@0:             // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to
michael@0:             // some other branches to make up for it
michael@0:             if (remainder >= fMinChildren) {
michael@0:                 remainder = 0;
michael@0:             } else {
michael@0:                 remainder = fMinChildren - remainder;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) *
michael@0:                                      SkScalarInvert(fAspectRatio)));
michael@0:         int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) /
michael@0:                                     SkIntToScalar(numStrips));
michael@0:         int currentBranch = 0;
michael@0: 
michael@0:         for (int i = 0; i < numStrips; ++i) {
michael@0:             // Once again, if we are told to do so, we sort by x.
michael@0:             if (fSortWhenBulkLoading) {
michael@0:                 int begin = currentBranch;
michael@0:                 int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder,
michael@0:                         (fMaxChildren - fMinChildren) * numTiles);
michael@0:                 if (end > branches->count()) {
michael@0:                     end = branches->count();
michael@0:                 }
michael@0: 
michael@0:                 // Now we sort horizontal strips of rectangles by their x coords
michael@0:                 SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX());
michael@0:             }
michael@0: 
michael@0:             for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
michael@0:                 int incrementBy = fMaxChildren;
michael@0:                 if (remainder != 0) {
michael@0:                     // if need be, omit some nodes to make up for remainder
michael@0:                     if (remainder <= fMaxChildren - fMinChildren) {
michael@0:                         incrementBy -= remainder;
michael@0:                         remainder = 0;
michael@0:                     } else {
michael@0:                         incrementBy = fMinChildren;
michael@0:                         remainder -= fMaxChildren - fMinChildren;
michael@0:                     }
michael@0:                 }
michael@0:                 Node* n = allocateNode(level);
michael@0:                 n->fNumChildren = 1;
michael@0:                 *n->child(0) = (*branches)[currentBranch];
michael@0:                 Branch b;
michael@0:                 b.fBounds = (*branches)[currentBranch].fBounds;
michael@0:                 b.fChild.subtree = n;
michael@0:                 ++currentBranch;
michael@0:                 for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
michael@0:                     b.fBounds.join((*branches)[currentBranch].fBounds);
michael@0:                     *n->child(k) = (*branches)[currentBranch];
michael@0:                     ++n->fNumChildren;
michael@0:                     ++currentBranch;
michael@0:                 }
michael@0:                 (*branches)[newBranches] = b;
michael@0:                 ++newBranches;
michael@0:             }
michael@0:         }
michael@0:         branches->setCount(newBranches);
michael@0:         return this->bulkLoad(branches, level + 1);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkRTree::validate() {
michael@0: #ifdef SK_DEBUG
michael@0:     if (this->isEmpty()) {
michael@0:         return;
michael@0:     }
michael@0:     SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true));
michael@0: #endif
michael@0: }
michael@0: 
michael@0: int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) {
michael@0:     // make sure the pointer is pointing to a valid place
michael@0:     SkASSERT(fNodes.contains(static_cast<void*>(root)));
michael@0: 
michael@0:     if (isRoot) {
michael@0:         // If the root of this subtree is the overall root, we have looser standards:
michael@0:         if (root->isLeaf()) {
michael@0:             SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildren);
michael@0:         } else {
michael@0:             SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren);
michael@0:         }
michael@0:     } else {
michael@0:         SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren);
michael@0:     }
michael@0: 
michael@0:     for (int i = 0; i < root->fNumChildren; ++i) {
michael@0:         SkASSERT(bounds.contains(root->child(i)->fBounds));
michael@0:     }
michael@0: 
michael@0:     if (root->isLeaf()) {
michael@0:         SkASSERT(0 == root->fLevel);
michael@0:         return root->fNumChildren;
michael@0:     } else {
michael@0:         int childCount = 0;
michael@0:         for (int i = 0; i < root->fNumChildren; ++i) {
michael@0:             SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1);
michael@0:             childCount += this->validateSubtree(root->child(i)->fChild.subtree,
michael@0:                                                 root->child(i)->fBounds);
michael@0:         }
michael@0:         return childCount;
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkRTree::rewindInserts() {
michael@0:     SkASSERT(this->isEmpty()); // Currently only supports deferred inserts
michael@0:     while (!fDeferredInserts.isEmpty() &&
michael@0:            fClient->shouldRewind(fDeferredInserts.top().fChild.data)) {
michael@0:         fDeferredInserts.pop();
michael@0:     }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static inline uint32_t get_area(const SkIRect& rect) {
michael@0:     return rect.width() * rect.height();
michael@0: }
michael@0: 
michael@0: static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) {
michael@0:     // I suspect there's a more efficient way of computing this...
michael@0:     return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) *
michael@0:            SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop, rect2.fTop));
michael@0: }
michael@0: 
michael@0: // Get the margin (aka perimeter)
michael@0: static inline uint32_t get_margin(const SkIRect& rect) {
michael@0:     return 2 * (rect.width() + rect.height());
michael@0: }
michael@0: 
michael@0: static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) {
michael@0:     join_no_empty_check(rect1, &rect2);
michael@0:     return get_area(rect2) - get_area(rect1);
michael@0: }
michael@0: 
michael@0: // Expand 'out' to include 'joinWith'
michael@0: static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) {
michael@0:     // since we check for empty bounds on insert, we know we'll never have empty rects
michael@0:     // and we can save the empty check that SkIRect::join requires
michael@0:     if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; }
michael@0:     if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; }
michael@0:     if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; }
michael@0:     if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; }
michael@0: }