1c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org/* 2c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * Copyright 2014 Google Inc. 3c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * 4c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * Use of this source code is governed by a BSD-style license that can be 5c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * found in the LICENSE file. 6c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org */ 7c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 8c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org#ifndef SkQuadTree_DEFINED 9c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org#define SkQuadTree_DEFINED 10c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 11c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org#include "SkRect.h" 12c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org#include "SkTDArray.h" 13c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org#include "SkBBoxHierarchy.h" 14949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#include "SkTInternalSList.h" 15949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#include "SkTObjectPool.h" 16c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 17c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org/** 18949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * A QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles 19c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * in which each internal node has exactly four children. 20c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * 21c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * For more details see: 22c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * 23c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * http://en.wikipedia.org/wiki/Quadtree 24c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org */ 25c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.orgclass SkQuadTree : public SkBBoxHierarchy { 26c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.orgpublic: 27c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org SK_DECLARE_INST_COUNT(SkQuadTree) 28c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 29c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org /** 30949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Quad tree constructor. 31949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * @param bounds The bounding box for the root of the quad tree. 32949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * giving the quad tree bounds that fall outside the root 33949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * bounds may result in pathological but correct behavior. 34c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org */ 35949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkQuadTree(const SkIRect& bounds); 36949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 37c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual ~SkQuadTree(); 38c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 39c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org /** 40c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately 41c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load 42c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * a large batch of nodes at once, which tends to be faster and produce a better tree). 43c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * @param data The data value 44c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * @param bounds The corresponding bounding box 45c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * @param defer Can this insert be deferred? (this may be ignored) 46c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org */ 47c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE; 48c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 49c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org /** 50c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * If any inserts have been deferred, this will add them into the tree 51c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org */ 52949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org virtual void flushDeferredInserts() SK_OVERRIDE; 53c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 54c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org /** 55c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * Given a query rectangle, populates the passed-in array with the elements it intersects 56c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org */ 57c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE; 58c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 59c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual void clear() SK_OVERRIDE; 60c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 61c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org /** 62c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * Gets the depth of the tree structure 63c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org */ 64c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual int getDepth() const SK_OVERRIDE; 65c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 66c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org /** 67c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * This gets the insertion count (rather than the node count) 68c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org */ 69a1dfa0cf05b06674175916e0226ba57be7eeadf4commit-bot@chromium.org virtual int getCount() const SK_OVERRIDE { 70a1dfa0cf05b06674175916e0226ba57be7eeadf4commit-bot@chromium.org return fEntryPool.allocated() - fEntryPool.available(); 71a1dfa0cf05b06674175916e0226ba57be7eeadf4commit-bot@chromium.org } 72c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 73c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual void rewindInserts() SK_OVERRIDE; 74c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 75c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.orgprivate: 76949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org struct Entry { 77949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org Entry() : fData(NULL) {} 78949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkIRect fBounds; 79949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org void* fData; 80949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SK_DECLARE_INTERNAL_SLIST_INTERFACE(Entry); 81949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org }; 82949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 83949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org static const int kChildCount = 4; 84949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 85949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org struct Node { 86949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org Node() { 87949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org for (int index=0; index<kChildCount; ++index) { 88949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org fChildren[index] = NULL; 89949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 90949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 91949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkTInternalSList<Entry> fEntries; 92949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkIRect fBounds; 93949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkIPoint fSplitPoint; // Only valid if the node has children. 94949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org Node* fChildren[kChildCount]; 95949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SK_DECLARE_INTERNAL_SLIST_ADAPTER(Node, fChildren[0]); 96949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org }; 97949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 98949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkTObjectPool<Entry> fEntryPool; 99949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkTObjectPool<Node> fNodePool; 100949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org Node* fRoot; 101a1dfa0cf05b06674175916e0226ba57be7eeadf4commit-bot@chromium.org SkIRect fRootBounds; 102949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkTInternalSList<Entry> fDeferred; 103949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 104949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org void insert(Node* node, Entry* entry); 105a1dfa0cf05b06674175916e0226ba57be7eeadf4commit-bot@chromium.org void split(Node* node); 106949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org void search(Node* node, const SkIRect& query, SkTDArray<void*>* results) const; 107949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org void clear(Node* node); 108949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org int getDepth(Node* node) const; 109c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 110c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org typedef SkBBoxHierarchy INHERITED; 111c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org}; 112c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 113c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org#endif 114