michael@0: /*
michael@0:  * Copyright 2014 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 "SkQuadTree.h"
michael@0: #include "SkTSort.h"
michael@0: #include <stdio.h>
michael@0: #include <vector>
michael@0: 
michael@0: static const int kSplitThreshold = 8;
michael@0: static const int kMinDimensions = 128;
michael@0: 
michael@0: SkQuadTree::SkQuadTree(const SkIRect& bounds)
michael@0:     : fEntryCount(0)
michael@0:     , fRoot(NULL) {
michael@0:     SkASSERT((bounds.width() * bounds.height()) > 0);
michael@0:     fRoot = fNodePool.acquire();
michael@0:     fRoot->fBounds = bounds;
michael@0: }
michael@0: 
michael@0: SkQuadTree::~SkQuadTree() {
michael@0: }
michael@0: 
michael@0: SkQuadTree::Node* SkQuadTree::pickChild(Node* node,
michael@0:                                         const SkIRect& bounds) const {
michael@0:     // is it entirely to the left?
michael@0:     int index = 0;
michael@0:     if (bounds.fRight < node->fSplitPoint.fX) {
michael@0:         // Inside the left side
michael@0:     } else if(bounds.fLeft >= node->fSplitPoint.fX) {
michael@0:         // Inside the right side
michael@0:         index |= 1;
michael@0:     } else {
michael@0:         // Not inside any children
michael@0:         return NULL;
michael@0:     }
michael@0:     if (bounds.fBottom < node->fSplitPoint.fY) {
michael@0:         // Inside the top side
michael@0:     } else if(bounds.fTop >= node->fSplitPoint.fY) {
michael@0:         // Inside the bottom side
michael@0:         index |= 2;
michael@0:     } else {
michael@0:         // Not inside any children
michael@0:         return NULL;
michael@0:     }
michael@0:     return node->fChildren[index];
michael@0: }
michael@0: 
michael@0: void SkQuadTree::insert(Node* node, Entry* entry) {
michael@0:     // does it belong in a child?
michael@0:     if (NULL != node->fChildren[0]) {
michael@0:         Node* child = pickChild(node, entry->fBounds);
michael@0:         if (NULL != child) {
michael@0:             insert(child, entry);
michael@0:         } else {
michael@0:             node->fEntries.push(entry);
michael@0:         }
michael@0:         return;
michael@0:     }
michael@0:     // No children yet, add to this node
michael@0:     node->fEntries.push(entry);
michael@0:     // should I split?
michael@0:     if (node->fEntries.getCount() < kSplitThreshold) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     if ((node->fBounds.width() < kMinDimensions) ||
michael@0:         (node->fBounds.height() < kMinDimensions)) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     // Build all the children
michael@0:     node->fSplitPoint = SkIPoint::Make(node->fBounds.centerX(),
michael@0:                                        node->fBounds.centerY());
michael@0:     for(int index=0; index<kChildCount; ++index) {
michael@0:         node->fChildren[index] = fNodePool.acquire();
michael@0:     }
michael@0:     node->fChildren[0]->fBounds = SkIRect::MakeLTRB(
michael@0:         node->fBounds.fLeft,    node->fBounds.fTop,
michael@0:         node->fSplitPoint.fX,   node->fSplitPoint.fY);
michael@0:     node->fChildren[1]->fBounds = SkIRect::MakeLTRB(
michael@0:         node->fSplitPoint.fX,   node->fBounds.fTop,
michael@0:         node->fBounds.fRight,   node->fSplitPoint.fY);
michael@0:     node->fChildren[2]->fBounds = SkIRect::MakeLTRB(
michael@0:         node->fBounds.fLeft,    node->fSplitPoint.fY,
michael@0:         node->fSplitPoint.fX,   node->fBounds.fBottom);
michael@0:     node->fChildren[3]->fBounds = SkIRect::MakeLTRB(
michael@0:         node->fSplitPoint.fX,   node->fSplitPoint.fY,
michael@0:         node->fBounds.fRight,   node->fBounds.fBottom);
michael@0:     // reinsert all the entries of this node to allow child trickle
michael@0:     SkTInternalSList<Entry> entries;
michael@0:     entries.pushAll(&node->fEntries);
michael@0:     while(!entries.isEmpty()) {
michael@0:         insert(node, entries.pop());
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkQuadTree::search(Node* node, const SkIRect& query,
michael@0:                         SkTDArray<void*>* results) const {
michael@0:     for (Entry* entry = node->fEntries.head(); NULL != entry;
michael@0:         entry = entry->getSListNext()) {
michael@0:         if (SkIRect::IntersectsNoEmptyCheck(entry->fBounds, query)) {
michael@0:             results->push(entry->fData);
michael@0:         }
michael@0:     }
michael@0:     if (NULL == node->fChildren[0]) {
michael@0:         return;
michael@0:     }
michael@0:     // fast quadrant test
michael@0:     bool left = true;
michael@0:     bool right = true;
michael@0:     if (query.fRight < node->fSplitPoint.fX) {
michael@0:         right = false;
michael@0:     } else if(query.fLeft >= node->fSplitPoint.fX) {
michael@0:         left = false;
michael@0:     }
michael@0:     bool top = true;
michael@0:     bool bottom = true;
michael@0:     if (query.fBottom < node->fSplitPoint.fY) {
michael@0:         bottom = false;
michael@0:     } else if(query.fTop >= node->fSplitPoint.fY) {
michael@0:         top = false;
michael@0:     }
michael@0:     // search all the active quadrants
michael@0:     if (top && left) {
michael@0:         search(node->fChildren[0], query, results);
michael@0:     }
michael@0:     if (top && right) {
michael@0:         search(node->fChildren[1], query, results);
michael@0:     }
michael@0:     if (bottom && left) {
michael@0:         search(node->fChildren[2], query, results);
michael@0:     }
michael@0:     if (bottom && right) {
michael@0:         search(node->fChildren[3], query, results);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkQuadTree::clear(Node* node) {
michael@0:     // first clear the entries of this node
michael@0:     fEntryPool.releaseAll(&node->fEntries);
michael@0:     // recurse into and clear all child nodes
michael@0:     for(int index=0; index<kChildCount; ++index) {
michael@0:         Node* child = node->fChildren[index];
michael@0:         node->fChildren[index] = NULL;
michael@0:         if (NULL != child) {
michael@0:             clear(child);
michael@0:             fNodePool.release(child);
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: int SkQuadTree::getDepth(Node* node) const {
michael@0:     int maxDepth = 0;
michael@0:     if (NULL != node->fChildren[0]) {
michael@0:         for(int index=0; index<kChildCount; ++index) {
michael@0:             maxDepth = SkMax32(maxDepth, getDepth(node->fChildren[index]));
michael@0:         }
michael@0:     }
michael@0:     return maxDepth + 1;
michael@0: }
michael@0: 
michael@0: void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
michael@0:     if (bounds.isEmpty()) {
michael@0:         SkASSERT(false);
michael@0:         return;
michael@0:     }
michael@0:     Entry* entry = fEntryPool.acquire();
michael@0:     entry->fData = data;
michael@0:     entry->fBounds = bounds;
michael@0:     ++fEntryCount;
michael@0:     if (fRoot->fEntries.isEmpty() && (NULL == fRoot->fChildren[0])) {
michael@0:         fDeferred.push(entry);
michael@0:     } else {
michael@0:         insert(fRoot, entry);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
michael@0:     SkASSERT(fDeferred.isEmpty());
michael@0:     SkASSERT(NULL != results);
michael@0:     if (SkIRect::Intersects(fRoot->fBounds, query)) {
michael@0:         search(fRoot, query, results);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkQuadTree::clear() {
michael@0:     fEntryCount = 0;
michael@0:     clear(fRoot);
michael@0: }
michael@0: 
michael@0: int SkQuadTree::getDepth() const {
michael@0:     return getDepth(fRoot);
michael@0: }
michael@0: 
michael@0: void SkQuadTree::rewindInserts() {
michael@0:     SkASSERT(fClient);
michael@0:      // Currently only supports deferred inserts
michael@0:     SkASSERT(fRoot->fEntries.isEmpty() && fRoot->fChildren[0] == NULL);
michael@0:     SkTInternalSList<Entry> entries;
michael@0:     entries.pushAll(&fDeferred);
michael@0:     while(!entries.isEmpty()) {
michael@0:         Entry* entry = entries.pop();
michael@0:         if (fClient->shouldRewind(entry->fData)) {
michael@0:             entry->fData = NULL;
michael@0:             fEntryPool.release(entry);
michael@0:             --fEntryCount;
michael@0:         } else {
michael@0:             fDeferred.push(entry);
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkQuadTree::flushDeferredInserts() {
michael@0:     while(!fDeferred.isEmpty()) {
michael@0:         insert(fRoot, fDeferred.pop());
michael@0:     }
michael@0: }