src/core/SkQuadTree.h - Issue 500373005: Remove SkQuadTree.

Side by Side Diff: src/core/SkQuadTree.h

Issue 500373005: Remove SkQuadTree. (Closed) Base URL: https://skia.googlesource.com/skia.git@master

Patch Set: Created 6 years, 3 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

OLD	NEW
	(Empty)
1 /*

2 * Copyright 2014 Google Inc.

3 *

4 * Use of this source code is governed by a BSD-style license that can be

5 * found in the LICENSE file.

6 */

7

8 #ifndef SkQuadTree_DEFINED

9 #define SkQuadTree_DEFINED

10

11 #include "SkRect.h"

12 #include "SkTDArray.h"

13 #include "SkBBoxHierarchy.h"

14 #include "SkTInternalSList.h"

15 #include "SkTObjectPool.h"

16

17 /**

18 * A QuadTree implementation. In short, it is a tree containing a hierarchy of b ounding rectangles

19 * in which each internal node has exactly four children.

20 *

21 * For more details see:

22 *

23 * http://en.wikipedia.org/wiki/Quadtree

24 */

25 class SkQuadTree : public SkBBoxHierarchy {

26 public:

27 SK_DECLARE_INST_COUNT(SkQuadTree)

28

29 /**

30 * Quad tree constructor.

31 * @param bounds The bounding box for the root of the quad tree.

32 * giving the quad tree bounds that fall outside the root

33 * bounds may result in pathological but correct behavior.

34 */

35 SkQuadTree(const SkIRect& bounds);

36

37 virtual ~SkQuadTree();

38

39 /**

40 * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately

41 * need to use the tree; we may allow the insert to be deferred (this can al low us to bulk-load

42 * a large batch of nodes at once, which tends to be faster and produce a be tter tree).

43 * @param data The data value

44 * @param bounds The corresponding bounding box

45 * @param defer Can this insert be deferred? (this may be ignored)

46 */

47 virtual void insert(void* data, const SkIRect& bounds, bool defer = false) S K_OVERRIDE;

48

49 /**

50 * If any inserts have been deferred, this will add them into the tree

51 */

52 virtual void flushDeferredInserts() SK_OVERRIDE;

53

54 /**

55 * Given a query rectangle, populates the passed-in array with the elements it intersects

56 */

57 virtual void search(const SkIRect& query, SkTDArray<void> results) const S K_OVERRIDE;

58

59 virtual void clear() SK_OVERRIDE;

60

61 /**

62 * Gets the depth of the tree structure

63 */

64 virtual int getDepth() const SK_OVERRIDE;

65

66 /**

67 * This gets the insertion count (rather than the node count)

68 */

69 virtual int getCount() const SK_OVERRIDE {

70 return fEntryPool.allocated() - fEntryPool.available();

71 }

72

73 virtual void rewindInserts() SK_OVERRIDE;

74

75 private:

76 struct Entry {

77 Entry() : fData(NULL) {}

78 SkIRect fBounds;

79 void* fData;

80 SK_DECLARE_INTERNAL_SLIST_INTERFACE(Entry);

81 };

82

83 static const int kChildCount = 4;

84

85 struct Node {

86 Node() {

87 for (int index=0; index<kChildCount; ++index) {

88 fChildren[index] = NULL;

89 }

90 }

91 SkTInternalSList<Entry> fEntries;

92 SkIRect fBounds;

93 SkIPoint fSplitPoint; // Only valid if the node has children.

94 Node* fChildren[kChildCount];

95 SK_DECLARE_INTERNAL_SLIST_ADAPTER(Node, fChildren[0]);

96 };

97

98 SkTObjectPool<Entry> fEntryPool;

99 SkTObjectPool<Node> fNodePool;

100 Node* fRoot;

101 SkIRect fRootBounds;

102 SkTInternalSList<Entry> fDeferred;

103

104 void insert(Node* node, Entry* entry);

105 void split(Node* node);

106 void search(Node* node, const SkIRect& query, SkTDArray<void> results) con st;

107 void clear(Node* node);

108 int getDepth(Node* node) const;

109

110 typedef SkBBoxHierarchy INHERITED;

111 };

112

113 #endif

OLD	NEW

« no previous file with comments | « src/core/SkBBHFactory.cpp ('k') | src/core/SkQuadTree.cpp » ('j') | no next file with comments »