3 * Copyright 2012 Google Inc.
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
9 #ifndef SkBBoxHierarchy_DEFINED
10 #define SkBBoxHierarchy_DEFINED
13 #include "SkTDArray.h"
17 * Interface for a client class that implements utility methods needed
18 * by SkBBoxHierarchy that require intrinsic knowledge of the data
19 * object type that is stored in the bounding box hierarchy.
21 class SkBBoxHierarchyClient {
23 virtual ~SkBBoxHierarchyClient() {}
26 * Implements a rewind stop condition used by rewindInserts
27 * Must returns true if 'data' points to an object that should be re-wound
30 virtual bool shouldRewind(void* data) = 0;
34 * Interface for a spatial data structure that associates user data pointers with axis-aligned
35 * bounding boxes, and allows efficient retrieval of intersections with query rectangles.
37 class SkBBoxHierarchy : public SkRefCnt {
39 SK_DECLARE_INST_COUNT(SkBBoxHierarchy)
41 SkBBoxHierarchy() : fClient(NULL) {}
44 * Insert a data pointer and corresponding bounding box
45 * @param data The data pointer, may be NULL
46 * @param bounds The bounding box, should not be empty
47 * @param defer Whether or not it is acceptable to delay insertion of this element (building up
48 * an entire spatial data structure at once is often faster and produces better
49 * structures than repeated inserts) until flushDeferredInserts is called or the first
52 virtual void insert(void* data, const SkRect& bounds, bool defer = false) = 0;
55 * If any insertions have been deferred, this forces them to be inserted
57 virtual void flushDeferredInserts() = 0;
60 * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query'
62 virtual void search(const SkRect& query, SkTDArray<void*>* results) const = 0;
64 virtual void clear() = 0;
67 * Gets the number of insertions actually made (does not include deferred insertions)
69 virtual int getCount() const = 0;
72 * Returns the depth of the currently allocated tree. The root node counts for 1 level,
73 * so it should be 1 or more if there's a root node. This information provides details
74 * about the underlying structure, which is useful mainly for testing purposes.
76 * Returns 0 if there are currently no nodes in the tree.
77 * Returns -1 if the structure isn't a tree.
79 virtual int getDepth() const = 0;
82 * Rewinds all the most recently inserted data elements until an element
83 * is encountered for which client->shouldRewind(data) returns false. May
84 * not rewind elements that were inserted prior to the last call to
85 * flushDeferredInserts.
87 virtual void rewindInserts() = 0;
89 void setClient(SkBBoxHierarchyClient* client) { fClient = client; }
92 SkBBoxHierarchyClient* fClient;
95 typedef SkRefCnt INHERITED;