11f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 21f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com/* 31f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Copyright 2012 Google Inc. 41f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * 51f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Use of this source code is governed by a BSD-style license that can be 61f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * found in the LICENSE file. 71f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 81f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 91f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#ifndef SkBBoxHierarchy_DEFINED 101f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#define SkBBoxHierarchy_DEFINED 111f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 121f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#include "SkRect.h" 131f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#include "SkTDArray.h" 144813458d89fb276680168848bd861b307cf83f51rileya@google.com#include "SkRefCnt.h" 151f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 161f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com/** 174b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org * Interface for a client class that implements utility methods needed 18ac2c82c8528ae45bcdac1f7c4b578aff1d9bbb7eskia.committer@gmail.com * by SkBBoxHierarchy that require intrinsic knowledge of the data 194b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org * object type that is stored in the bounding box hierarchy. 204b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org */ 214b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.orgclass SkBBoxHierarchyClient { 224b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.orgpublic: 234b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org virtual ~SkBBoxHierarchyClient() {} 244b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org 254b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org /** 264b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org * Implements a rewind stop condition used by rewindInserts 274b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org * Must returns true if 'data' points to an object that should be re-wound 284b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org * by rewinfInserts. 294b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org */ 304b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org virtual bool shouldRewind(void* data) = 0; 314b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org}; 324b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org 334b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org/** 341f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Interface for a spatial data structure that associates user data pointers with axis-aligned 351f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * bounding boxes, and allows efficient retrieval of intersections with query rectangles. 361f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 374813458d89fb276680168848bd861b307cf83f51rileya@google.comclass SkBBoxHierarchy : public SkRefCnt { 381f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.compublic: 394813458d89fb276680168848bd861b307cf83f51rileya@google.com SK_DECLARE_INST_COUNT(SkBBoxHierarchy) 401f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 414b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org SkBBoxHierarchy() : fClient(NULL) {} 424b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org 431f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 441f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Insert a data pointer and corresponding bounding box 451f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * @param data The data pointer, may be NULL 461f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * @param bounds The bounding box, should not be empty 471f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * @param defer Whether or not it is acceptable to delay insertion of this element (building up 481f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * an entire spatial data structure at once is often faster and produces better 491f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * structures than repeated inserts) until flushDeferredInserts is called or the first 501f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * search. 511f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 521f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com virtual void insert(void* data, const SkIRect& bounds, bool defer = false) = 0; 531f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 541f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 551f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * If any insertions have been deferred, this forces them to be inserted 561f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 571f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com virtual void flushDeferredInserts() = 0; 581f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 591f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 601f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query' 611f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 621f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com virtual void search(const SkIRect& query, SkTDArray<void*>* results) = 0; 631f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 641f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com virtual void clear() = 0; 651f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 661f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com /** 67c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * Gets the number of insertions actually made (does not include deferred insertions) 681f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 691f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com virtual int getCount() const = 0; 704813458d89fb276680168848bd861b307cf83f51rileya@google.com 714b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org /** 72c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * Returns the depth of the currently allocated tree. The root node counts for 1 level, 73c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * so it should be 1 or more if there's a root node. This information provides details 74c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * about the underlying structure, which is useful mainly for testing purposes. 75c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * 76c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * Returns 0 if there are currently no nodes in the tree. 77c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org * Returns -1 if the structure isn't a tree. 78c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org */ 79c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org virtual int getDepth() const = 0; 80c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org 81c22d1398089fdb95480fb3459b23e4931e4f5280commit-bot@chromium.org /** 824b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org * Rewinds all the most recently inserted data elements until an element 834b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org * is encountered for which client->shouldRewind(data) returns false. May 844b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org * not rewind elements that were inserted prior to the last call to 854b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org * flushDeferredInserts. 864b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org */ 874b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org virtual void rewindInserts() = 0; 884b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org 894b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org void setClient(SkBBoxHierarchyClient* client) { fClient = client; } 904b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org 914b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.orgprotected: 924b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org SkBBoxHierarchyClient* fClient; 934b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org 944813458d89fb276680168848bd861b307cf83f51rileya@google.comprivate: 954813458d89fb276680168848bd861b307cf83f51rileya@google.com typedef SkRefCnt INHERITED; 961f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com}; 971f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 981f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#endif 99