1// Copyright 2013 The Flutter Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef FLUTTER_FLOW_RTREE_H_
6#define FLUTTER_FLOW_RTREE_H_
7
8#include <list>
9#include <map>
10
11#include "third_party/skia/include/core/SkBBHFactory.h"
12#include "third_party/skia/include/core/SkTypes.h"
13
14namespace flutter {
15/**
16 * An R-Tree implementation that forwards calls to an SkRTree.
17 *
18 * This implementation provides a searchNonOverlappingDrawnRects method,
19 * which can be used to query the rects for the operations recorded in the tree.
20 */
21class RTree : public SkBBoxHierarchy {
22 public:
23 RTree();
24
25 void insert(const SkRect[],
26 const SkBBoxHierarchy::Metadata[],
27 int N) override;
28 void insert(const SkRect[], int N) override;
29 void search(const SkRect& query, std::vector<int>* results) const override;
30 size_t bytesUsed() const override;
31
32 // Finds the rects in the tree that represent drawing operations and intersect
33 // with the query rect.
34 //
35 // When two rects intersect with each other, they are joined into a single
36 // rect which also intersects with the query rect. In other words, the bounds
37 // of each rect in the result list are mutually exclusive.
38 std::list<SkRect> searchNonOverlappingDrawnRects(const SkRect& query) const;
39
40 // Insertion count (not overall node count, which may be greater).
41 int getCount() const { return all_ops_count_; }
42
43 private:
44 // A map containing the draw operation rects keyed off the operation index
45 // in the insert call.
46 std::map<int, SkRect> draw_op_;
47 sk_sp<SkBBoxHierarchy> bbh_;
48 int all_ops_count_;
49};
50
51class RTreeFactory : public SkBBHFactory {
52 public:
53 RTreeFactory();
54
55 // Gets the instance to the R-tree.
56 sk_sp<RTree> getInstance();
57 sk_sp<SkBBoxHierarchy> operator()() const override;
58
59 private:
60 sk_sp<RTree> r_tree_;
61};
62
63} // namespace flutter
64
65#endif // FLUTTER_FLOW_RTREE_H_
66