1/*
2 *  Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.
3 *
4 *  Use of this source code is governed by a BSD-style license
5 *  that can be found in the LICENSE file in the root of the source
6 *  tree. An additional intellectual property rights grant can be found
7 *  in the file PATENTS.  All contributing project authors may
8 *  be found in the AUTHORS file in the root of the source tree.
9 */
10
11#ifndef WEBRTC_MODULES_DESKTOP_CAPTURE_DESKTOP_REGION_H_
12#define WEBRTC_MODULES_DESKTOP_CAPTURE_DESKTOP_REGION_H_
13
14#include <map>
15#include <vector>
16
17#include "webrtc/base/constructormagic.h"
18#include "webrtc/modules/desktop_capture/desktop_geometry.h"
19#include "webrtc/typedefs.h"
20
21namespace webrtc {
22
23// DesktopRegion represents a region of the screen or window.
24//
25// Internally each region is stored as a set of rows where each row contains one
26// or more rectangles aligned vertically.
27class DesktopRegion {
28 private:
29  // The following private types need to be declared first because they are used
30  // in the public Iterator.
31
32  // RowSpan represents a horizontal span withing a single row.
33  struct RowSpan {
34    RowSpan(int32_t left, int32_t right);
35
36    // Used by std::vector<>.
37    bool operator==(const RowSpan& that) const {
38      return left == that.left && right == that.right;
39    }
40
41    int32_t left;
42    int32_t right;
43  };
44
45  typedef std::vector<RowSpan> RowSpanSet;
46
47  // Row represents a single row of a region. A row is set of rectangles that
48  // have the same vertical position.
49  struct Row {
50    Row(int32_t top, int32_t bottom);
51    ~Row();
52
53    int32_t top;
54    int32_t bottom;
55
56    RowSpanSet spans;
57  };
58
59  // Type used to store list of rows in the region. The bottom position of row
60  // is used as the key so that rows are always ordered by their position. The
61  // map stores pointers to make Translate() more efficient.
62  typedef std::map<int, Row*> Rows;
63
64 public:
65  // Iterator that can be used to iterate over rectangles of a DesktopRegion.
66  // The region must not be mutated while the iterator is used.
67  class Iterator {
68   public:
69    explicit Iterator(const DesktopRegion& target);
70    ~Iterator();
71
72    bool IsAtEnd() const;
73    void Advance();
74
75    const DesktopRect& rect() const { return rect_; }
76
77   private:
78    const DesktopRegion& region_;
79
80    // Updates |rect_| based on the current |row_| and |row_span_|. If
81    // |row_span_| matches spans on consecutive rows then they are also merged
82    // into |rect_|, to generate more efficient output.
83    void UpdateCurrentRect();
84
85    Rows::const_iterator row_;
86    Rows::const_iterator previous_row_;
87    RowSpanSet::const_iterator row_span_;
88    DesktopRect rect_;
89  };
90
91  DesktopRegion();
92  explicit DesktopRegion(const DesktopRect& rect);
93  DesktopRegion(const DesktopRect* rects, int count);
94  DesktopRegion(const DesktopRegion& other);
95  ~DesktopRegion();
96
97  DesktopRegion& operator=(const DesktopRegion& other);
98
99  bool is_empty() const { return rows_.empty(); }
100
101  bool Equals(const DesktopRegion& region) const;
102
103  // Reset the region to be empty.
104  void Clear();
105
106  // Reset region to contain just |rect|.
107  void SetRect(const DesktopRect& rect);
108
109  // Adds specified rect(s) or region to the region.
110  void AddRect(const DesktopRect& rect);
111  void AddRects(const DesktopRect* rects, int count);
112  void AddRegion(const DesktopRegion& region);
113
114  // Finds intersection of two regions and stores them in the current region.
115  void Intersect(const DesktopRegion& region1, const DesktopRegion& region2);
116
117  // Same as above but intersects content of the current region with |region|.
118  void IntersectWith(const DesktopRegion& region);
119
120  // Clips the region by the |rect|.
121  void IntersectWith(const DesktopRect& rect);
122
123  // Subtracts |region| from the current content of the region.
124  void Subtract(const DesktopRegion& region);
125
126  // Subtracts |rect| from the current content of the region.
127  void Subtract(const DesktopRect& rect);
128
129  // Adds (dx, dy) to the position of the region.
130  void Translate(int32_t dx, int32_t dy);
131
132  void Swap(DesktopRegion* region);
133
134 private:
135  // Comparison functions used for std::lower_bound(). Compare left or right
136  // edges withs a given |value|.
137  static bool CompareSpanLeft(const RowSpan& r, int32_t value);
138  static bool CompareSpanRight(const RowSpan& r, int32_t value);
139
140  // Adds a new span to the row, coalescing spans if necessary.
141  static void AddSpanToRow(Row* row, int32_t left, int32_t right);
142
143  // Returns true if the |span| exists in the given |row|.
144  static bool IsSpanInRow(const Row& row, const RowSpan& rect);
145
146  // Calculates the intersection of two sets of spans.
147  static void IntersectRows(const RowSpanSet& set1,
148                            const RowSpanSet& set2,
149                            RowSpanSet* output);
150
151  static void SubtractRows(const RowSpanSet& set_a,
152                           const RowSpanSet& set_b,
153                           RowSpanSet* output);
154
155  // Merges |row| with the row above it if they contain the same spans. Doesn't
156  // do anything if called with |row| set to rows_.begin() (i.e. first row of
157  // the region). If the rows were merged |row| remains a valid iterator to the
158  // merged row.
159  void MergeWithPrecedingRow(Rows::iterator row);
160
161  Rows rows_;
162};
163
164}  // namespace webrtc
165
166#endif  // WEBRTC_MODULES_DESKTOP_CAPTURE_DESKTOP_REGION_H_
167
168