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#include "webrtc/modules/desktop_capture/desktop_region.h"
12
13#include <algorithm>
14
15#include "testing/gtest/include/gtest/gtest.h"
16
17namespace webrtc {
18
19namespace {
20
21int RadmonInt(int max) {
22  return (rand() / 256) % max;
23}
24
25void CompareRegion(const DesktopRegion& region,
26                   const DesktopRect rects[], int rects_size) {
27  DesktopRegion::Iterator it(region);
28  for (int i = 0; i < rects_size; ++i) {
29    SCOPED_TRACE(i);
30    ASSERT_FALSE(it.IsAtEnd());
31    EXPECT_TRUE(it.rect().equals(rects[i]))
32        << it.rect().left() << "-" << it.rect().right() << "."
33        << it.rect().top() << "-" << it.rect().bottom() << " "
34        << rects[i].left() << "-" << rects[i].right() << "."
35        << rects[i].top() << "-" << rects[i].bottom();
36    it.Advance();
37  }
38  EXPECT_TRUE(it.IsAtEnd());
39}
40
41}  // namespace
42
43// Verify that regions are empty when created.
44TEST(DesktopRegionTest, Empty) {
45  DesktopRegion r;
46  CompareRegion(r, NULL, 0);
47}
48
49// Verify that empty rectangles are ignored.
50TEST(DesktopRegionTest, AddEmpty) {
51  DesktopRegion r;
52  DesktopRect rect = DesktopRect::MakeXYWH(1, 2, 0, 0);
53  r.AddRect(rect);
54  CompareRegion(r, NULL, 0);
55}
56
57// Verify that regions with a single rectangles are handled properly.
58TEST(DesktopRegionTest, SingleRect) {
59  DesktopRegion r;
60  DesktopRect rect = DesktopRect::MakeXYWH(1, 2, 3, 4);
61  r.AddRect(rect);
62  CompareRegion(r, &rect, 1);
63}
64
65// Verify that non-overlapping rectangles are not merged.
66TEST(DesktopRegionTest, NonOverlappingRects) {
67  struct Case {
68    int count;
69    DesktopRect rects[4];
70  } cases[] = {
71    { 1, { DesktopRect::MakeXYWH(10, 10, 10, 10) } },
72    { 2, { DesktopRect::MakeXYWH(10, 10, 10, 10),
73           DesktopRect::MakeXYWH(30, 10, 10, 15) } },
74    { 2, { DesktopRect::MakeXYWH(10, 10, 10, 10),
75           DesktopRect::MakeXYWH(10, 30, 10, 5) } },
76    { 3, { DesktopRect::MakeXYWH(10, 10, 10, 9),
77           DesktopRect::MakeXYWH(30, 10, 15, 10),
78           DesktopRect::MakeXYWH(10, 30, 8, 10) } },
79    { 4, { DesktopRect::MakeXYWH(0, 0, 30, 10),
80           DesktopRect::MakeXYWH(40, 0, 10, 30),
81           DesktopRect::MakeXYWH(0, 20, 10, 30),
82           DesktopRect::MakeXYWH(20, 40, 30, 10) } },
83    { 4, { DesktopRect::MakeXYWH(0, 0, 10, 100),
84           DesktopRect::MakeXYWH(20, 10, 30, 10),
85           DesktopRect::MakeXYWH(20, 30, 30, 10),
86           DesktopRect::MakeXYWH(20, 50, 30, 10) } },
87  };
88
89  for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
90    SCOPED_TRACE(i);
91
92    DesktopRegion r;
93
94    for (int j = 0; j < cases[i].count; ++j) {
95      r.AddRect(cases[i].rects[j]);
96    }
97    CompareRegion(r, cases[i].rects, cases[i].count);
98
99    SCOPED_TRACE("Reverse");
100
101    // Try inserting rects in reverse order.
102    r.Clear();
103    for (int j = cases[i].count - 1; j >= 0; --j) {
104      r.AddRect(cases[i].rects[j]);
105    }
106    CompareRegion(r, cases[i].rects, cases[i].count);
107  }
108}
109
110TEST(DesktopRegionTest, TwoRects) {
111  struct Case {
112    DesktopRect input_rect1;
113    DesktopRect input_rect2;
114    int expected_count;
115    DesktopRect expected_rects[3];
116  } cases[] = {
117    // Touching rectangles that merge into one.
118    { DesktopRect::MakeLTRB(100, 100, 200, 200),
119      DesktopRect::MakeLTRB(0, 100, 100, 200),
120      1, { DesktopRect::MakeLTRB(0, 100, 200, 200) } },
121    { DesktopRect::MakeLTRB(100, 100, 200, 200),
122      DesktopRect::MakeLTRB(100, 0, 200, 100),
123      1, { DesktopRect::MakeLTRB(100, 0, 200, 200) } },
124
125    // Rectangles touching on the vertical edge.
126    { DesktopRect::MakeLTRB(100, 100, 200, 200),
127      DesktopRect::MakeLTRB(0, 150, 100, 250),
128      3, { DesktopRect::MakeLTRB(100, 100, 200, 150),
129           DesktopRect::MakeLTRB(0, 150, 200, 200),
130           DesktopRect::MakeLTRB(0, 200, 100, 250) } },
131    { DesktopRect::MakeLTRB(100, 100, 200, 200),
132      DesktopRect::MakeLTRB(0, 50, 100, 150),
133      3, { DesktopRect::MakeLTRB(0, 50, 100, 100),
134           DesktopRect::MakeLTRB(0, 100, 200, 150),
135           DesktopRect::MakeLTRB(100, 150, 200, 200) } },
136    { DesktopRect::MakeLTRB(100, 100, 200, 200),
137      DesktopRect::MakeLTRB(0, 120, 100, 180),
138      3, { DesktopRect::MakeLTRB(100, 100, 200, 120),
139           DesktopRect::MakeLTRB(0, 120, 200, 180),
140           DesktopRect::MakeLTRB(100, 180, 200, 200) } },
141
142    // Rectangles touching on the horizontal edge.
143    { DesktopRect::MakeLTRB(100, 100, 200, 200),
144      DesktopRect::MakeLTRB(150, 0, 250, 100),
145      2, { DesktopRect::MakeLTRB(150, 0, 250, 100),
146           DesktopRect::MakeLTRB(100, 100, 200, 200) } },
147    { DesktopRect::MakeLTRB(100, 100, 200, 200),
148      DesktopRect::MakeLTRB(50, 0, 150, 100),
149      2, { DesktopRect::MakeLTRB(50, 0, 150, 100),
150           DesktopRect::MakeLTRB(100, 100, 200, 200) } },
151    { DesktopRect::MakeLTRB(100, 100, 200, 200),
152      DesktopRect::MakeLTRB(120, 0, 180, 100),
153      2, { DesktopRect::MakeLTRB(120, 0, 180, 100),
154           DesktopRect::MakeLTRB(100, 100, 200, 200) } },
155
156    // Overlapping rectangles.
157    { DesktopRect::MakeLTRB(100, 100, 200, 200),
158      DesktopRect::MakeLTRB(50, 50, 150, 150),
159      3, { DesktopRect::MakeLTRB(50, 50, 150, 100),
160           DesktopRect::MakeLTRB(50, 100, 200, 150),
161           DesktopRect::MakeLTRB(100, 150, 200, 200) } },
162    { DesktopRect::MakeLTRB(100, 100, 200, 200),
163      DesktopRect::MakeLTRB(150, 50, 250, 150),
164      3, { DesktopRect::MakeLTRB(150, 50, 250, 100),
165           DesktopRect::MakeLTRB(100, 100, 250, 150),
166           DesktopRect::MakeLTRB(100, 150, 200, 200) } },
167    { DesktopRect::MakeLTRB(100, 100, 200, 200),
168      DesktopRect::MakeLTRB(0, 120, 150, 180),
169      3, { DesktopRect::MakeLTRB(100, 100, 200, 120),
170           DesktopRect::MakeLTRB(0, 120, 200, 180),
171           DesktopRect::MakeLTRB(100, 180, 200, 200) } },
172    { DesktopRect::MakeLTRB(100, 100, 200, 200),
173      DesktopRect::MakeLTRB(120, 0, 180, 150),
174      2, { DesktopRect::MakeLTRB(120, 0, 180, 100),
175           DesktopRect::MakeLTRB(100, 100, 200, 200) } },
176    { DesktopRect::MakeLTRB(100, 0, 200, 300),
177      DesktopRect::MakeLTRB(0, 100, 300, 200),
178      3, { DesktopRect::MakeLTRB(100, 0, 200, 100),
179           DesktopRect::MakeLTRB(0, 100, 300, 200),
180           DesktopRect::MakeLTRB(100, 200, 200, 300)} },
181
182    // One rectangle enclosing another.
183    { DesktopRect::MakeLTRB(100, 100, 200, 200),
184      DesktopRect::MakeLTRB(150, 150, 180, 180),
185      1, { DesktopRect::MakeLTRB(100, 100, 200, 200) } },
186    { DesktopRect::MakeLTRB(100, 100, 200, 200),
187      DesktopRect::MakeLTRB(100, 100, 180, 180),
188      1, { DesktopRect::MakeLTRB(100, 100, 200, 200) } },
189    { DesktopRect::MakeLTRB(100, 100, 200, 200),
190      DesktopRect::MakeLTRB(150, 150, 200, 200),
191      1, { DesktopRect::MakeLTRB(100, 100, 200, 200) } },
192  };
193
194  for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
195    SCOPED_TRACE(i);
196
197    DesktopRegion r;
198
199    r.AddRect(cases[i].input_rect1);
200    r.AddRect(cases[i].input_rect2);
201    CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
202
203    SCOPED_TRACE("Reverse");
204
205    // Run the same test with rectangles inserted in reverse order.
206    r.Clear();
207    r.AddRect(cases[i].input_rect2);
208    r.AddRect(cases[i].input_rect1);
209    CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
210  }
211}
212
213// Verify that DesktopRegion::AddRectToRow() works correctly by creating a row
214// of not overlapping rectangles and insert an overlapping rectangle into the
215// row at different positions. Result is verified by building a map of the
216// region in an array and comparing it with the expected values.
217TEST(DesktopRegionTest, SameRow) {
218  const int kMapWidth = 50;
219  const int kLastRectSizes[] = {3, 27};
220
221  DesktopRegion base_region;
222  bool base_map[kMapWidth] = { false, };
223
224  base_region.AddRect(DesktopRect::MakeXYWH(5, 0, 5, 1));
225  std::fill_n(base_map + 5, 5, true);
226  base_region.AddRect(DesktopRect::MakeXYWH(15, 0, 5, 1));
227  std::fill_n(base_map + 15, 5, true);
228  base_region.AddRect(DesktopRect::MakeXYWH(25, 0, 5, 1));
229  std::fill_n(base_map + 25, 5, true);
230  base_region.AddRect(DesktopRect::MakeXYWH(35, 0, 5, 1));
231  std::fill_n(base_map + 35, 5, true);
232  base_region.AddRect(DesktopRect::MakeXYWH(45, 0, 5, 1));
233  std::fill_n(base_map + 45, 5, true);
234
235  for (size_t i = 0; i < sizeof(kLastRectSizes) / sizeof(kLastRectSizes[0]);
236       i++) {
237    int last_rect_size = kLastRectSizes[i];
238    for (int x = 0; x < kMapWidth - last_rect_size; x++) {
239      SCOPED_TRACE(x);
240
241      DesktopRegion r = base_region;
242      r.AddRect(DesktopRect::MakeXYWH(x, 0,  last_rect_size, 1));
243
244      bool expected_map[kMapWidth];
245      std::copy(base_map, base_map + kMapWidth, expected_map);
246      std::fill_n(expected_map + x, last_rect_size, true);
247
248      bool map[kMapWidth] = { false, };
249
250      int pos = -1;
251      for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
252        EXPECT_GT(it.rect().left(), pos);
253        pos = it.rect().right();
254        std::fill_n(map + it.rect().left(), it.rect().width(), true);
255      }
256
257      EXPECT_TRUE(std::equal(map, map + kMapWidth, expected_map));
258    }
259  }
260}
261
262TEST(DesktopRegionTest, ComplexRegions) {
263  struct Case {
264    int input_count;
265    DesktopRect input_rects[4];
266    int expected_count;
267    DesktopRect expected_rects[6];
268  } cases[] = {
269    { 3, { DesktopRect::MakeLTRB(100, 100, 200, 200),
270           DesktopRect::MakeLTRB(0, 100, 100, 200),
271           DesktopRect::MakeLTRB(310, 110, 320, 120), },
272      2, { DesktopRect::MakeLTRB(0, 100, 200, 200),
273           DesktopRect::MakeLTRB(310, 110, 320, 120) } },
274    { 3, { DesktopRect::MakeLTRB(100, 100, 200, 200),
275           DesktopRect::MakeLTRB(50, 50, 150, 150),
276           DesktopRect::MakeLTRB(300, 125, 350, 175) },
277      4, { DesktopRect::MakeLTRB(50, 50, 150, 100),
278           DesktopRect::MakeLTRB(50, 100, 200, 150),
279           DesktopRect::MakeLTRB(300, 125, 350, 175),
280           DesktopRect::MakeLTRB(100, 150, 200, 200) } },
281    { 4, { DesktopRect::MakeLTRB(0, 0, 30, 30),
282           DesktopRect::MakeLTRB(10, 10, 40, 40),
283           DesktopRect::MakeLTRB(20, 20, 50, 50),
284           DesktopRect::MakeLTRB(50, 0, 65, 15) },
285      6, { DesktopRect::MakeLTRB(0, 0, 30, 10),
286           DesktopRect::MakeLTRB(50, 0, 65, 15),
287           DesktopRect::MakeLTRB(0, 10, 40, 20),
288           DesktopRect::MakeLTRB(0, 20, 50, 30),
289           DesktopRect::MakeLTRB(10, 30, 50, 40),
290           DesktopRect::MakeLTRB(20, 40, 50, 50) } },
291    { 3, { DesktopRect::MakeLTRB(10, 10, 40, 20),
292           DesktopRect::MakeLTRB(10, 30, 40, 40),
293           DesktopRect::MakeLTRB(10, 20, 40, 30) },
294      1, { DesktopRect::MakeLTRB(10, 10, 40, 40) } },
295  };
296
297  for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
298    SCOPED_TRACE(i);
299
300    DesktopRegion r;
301    r.AddRects(cases[i].input_rects, cases[i].input_count);
302    CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
303
304    // Try inserting rectangles in reverse order.
305    r.Clear();
306    for (int j = cases[i].input_count - 1; j >= 0; --j) {
307      r.AddRect(cases[i].input_rects[j]);
308    }
309    CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
310  }
311}
312
313TEST(DesktopRegionTest, Equals) {
314  struct Region {
315    int count;
316    DesktopRect rects[4];
317    int id;
318  } regions[] = {
319    // Same region with one of the rectangles 1 pixel wider/taller.
320    { 2, { DesktopRect::MakeLTRB(0, 100, 200, 200),
321           DesktopRect::MakeLTRB(310, 110, 320, 120) }, 0 },
322    { 2, { DesktopRect::MakeLTRB(0, 100, 201, 200),
323           DesktopRect::MakeLTRB(310, 110, 320, 120) }, 1 },
324    { 2, { DesktopRect::MakeLTRB(0, 100, 200, 201),
325           DesktopRect::MakeLTRB(310, 110, 320, 120) }, 2 },
326
327    // Same region with one of the rectangles shifted horizontally and
328    // vertically.
329    { 4, { DesktopRect::MakeLTRB(0, 0, 30, 30),
330           DesktopRect::MakeLTRB(10, 10, 40, 40),
331           DesktopRect::MakeLTRB(20, 20, 50, 50),
332           DesktopRect::MakeLTRB(50, 0, 65, 15) }, 3 },
333    { 4, { DesktopRect::MakeLTRB(0, 0, 30, 30),
334           DesktopRect::MakeLTRB(10, 10, 40, 40),
335           DesktopRect::MakeLTRB(20, 20, 50, 50),
336           DesktopRect::MakeLTRB(50, 1, 65, 16) }, 4 },
337    { 4, { DesktopRect::MakeLTRB(0, 0, 30, 30),
338           DesktopRect::MakeLTRB(10, 10, 40, 40),
339           DesktopRect::MakeLTRB(20, 20, 50, 50),
340           DesktopRect::MakeLTRB(51, 0, 66, 15) }, 5 },
341
342    // Same region defined by a different set of rectangles - one of the
343    // rectangle is split horizontally into two.
344    { 3, { DesktopRect::MakeLTRB(100, 100, 200, 200),
345           DesktopRect::MakeLTRB(50, 50, 150, 150),
346           DesktopRect::MakeLTRB(300, 125, 350, 175) }, 6 },
347    { 4, { DesktopRect::MakeLTRB(100, 100, 200, 200),
348           DesktopRect::MakeLTRB(50, 50, 100, 150),
349           DesktopRect::MakeLTRB(100, 50, 150, 150),
350           DesktopRect::MakeLTRB(300, 125, 350, 175) }, 6 },
351
352    // Rectangle region defined by a set of rectangles that merge into one.
353    { 3, { DesktopRect::MakeLTRB(10, 10, 40, 20),
354           DesktopRect::MakeLTRB(10, 30, 40, 40),
355           DesktopRect::MakeLTRB(10, 20, 40, 30) }, 7 },
356    { 1, { DesktopRect::MakeLTRB(10, 10, 40, 40) }, 7 },
357  };
358  int kTotalRegions = sizeof(regions) / sizeof(Region);
359
360  for (int i = 0; i < kTotalRegions; ++i) {
361    SCOPED_TRACE(i);
362
363    DesktopRegion r1(regions[i].rects, regions[i].count);
364    for (int j = 0; j < kTotalRegions; ++j) {
365      SCOPED_TRACE(j);
366
367      DesktopRegion r2(regions[j].rects, regions[j].count);
368      EXPECT_EQ(regions[i].id == regions[j].id, r1.Equals(r2));
369    }
370  }
371}
372
373TEST(DesktopRegionTest, Translate) {
374  struct Case {
375    int input_count;
376    DesktopRect input_rects[4];
377    int dx;
378    int dy;
379    int expected_count;
380    DesktopRect expected_rects[5];
381  } cases[] = {
382    { 3, { DesktopRect::MakeLTRB(0, 0, 30, 30),
383           DesktopRect::MakeLTRB(10, 10, 40, 40),
384           DesktopRect::MakeLTRB(20, 20, 50, 50) },
385      3, 5,
386      5, { DesktopRect::MakeLTRB(3, 5, 33, 15),
387           DesktopRect::MakeLTRB(3, 15, 43, 25),
388           DesktopRect::MakeLTRB(3, 25, 53, 35),
389           DesktopRect::MakeLTRB(13, 35, 53, 45),
390           DesktopRect::MakeLTRB(23, 45, 53, 55) } },
391  };
392
393  for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
394    SCOPED_TRACE(i);
395
396    DesktopRegion r(cases[i].input_rects, cases[i].input_count);
397    r.Translate(cases[i].dx, cases[i].dy);
398    CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
399  }
400}
401
402TEST(DesktopRegionTest, Intersect) {
403  struct Case {
404    int input1_count;
405    DesktopRect input1_rects[4];
406    int input2_count;
407    DesktopRect input2_rects[4];
408    int expected_count;
409    DesktopRect expected_rects[5];
410  } cases[] = {
411    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
412      1, { DesktopRect::MakeLTRB(50, 50, 150, 150) },
413      1, { DesktopRect::MakeLTRB(50, 50, 100, 100) } },
414
415    { 1, { DesktopRect::MakeLTRB(100, 0, 200, 300) },
416      1, { DesktopRect::MakeLTRB(0, 100, 300, 200) },
417      1, { DesktopRect::MakeLTRB(100, 100, 200, 200) } },
418
419    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
420      2, { DesktopRect::MakeLTRB(50, 10, 150, 30),
421           DesktopRect::MakeLTRB(50, 30, 160, 50) },
422      1, { DesktopRect::MakeLTRB(50, 10, 100, 50) } },
423
424    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
425      2, { DesktopRect::MakeLTRB(50, 10, 150, 30),
426           DesktopRect::MakeLTRB(50, 30,  90, 50) },
427      2, { DesktopRect::MakeLTRB(50, 10, 100, 30),
428           DesktopRect::MakeLTRB(50, 30, 90, 50) } },
429    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
430      1, { DesktopRect::MakeLTRB(100, 50, 200, 200) },
431      0, {} },
432  };
433
434  for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
435    SCOPED_TRACE(i);
436
437    DesktopRegion r1(cases[i].input1_rects, cases[i].input1_count);
438    DesktopRegion r2(cases[i].input2_rects, cases[i].input2_count);
439
440    DesktopRegion r;
441    r.Intersect(r1, r2);
442
443    CompareRegion(r, cases[i].expected_rects, cases[i].expected_count);
444  }
445}
446
447TEST(DesktopRegionTest, Subtract) {
448  struct Case {
449    int input1_count;
450    DesktopRect input1_rects[4];
451    int input2_count;
452    DesktopRect input2_rects[4];
453    int expected_count;
454    DesktopRect expected_rects[5];
455  } cases[] = {
456    // Subtract one rect from another.
457    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
458      1, { DesktopRect::MakeLTRB(50, 50, 150, 150) },
459      2, { DesktopRect::MakeLTRB(0, 0, 100, 50),
460           DesktopRect::MakeLTRB(0, 50, 50, 100)  } },
461
462    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
463      1, { DesktopRect::MakeLTRB(-50, -50, 50, 50) },
464      2, { DesktopRect::MakeLTRB(50, 0, 100, 50),
465           DesktopRect::MakeLTRB(0, 50, 100, 100)  } },
466
467    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
468      1, { DesktopRect::MakeLTRB(-50, 50, 50, 150) },
469      2, { DesktopRect::MakeLTRB(0, 0, 100, 50),
470           DesktopRect::MakeLTRB(50, 50, 100, 100)  } },
471
472    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
473      1, { DesktopRect::MakeLTRB(50, 50, 150, 70) },
474      3, { DesktopRect::MakeLTRB(0, 0, 100, 50),
475           DesktopRect::MakeLTRB(0, 50, 50, 70),
476           DesktopRect::MakeLTRB(0, 70, 100, 100) } },
477
478    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
479      1, { DesktopRect::MakeLTRB(50, 50, 70, 70) },
480      4, { DesktopRect::MakeLTRB(0, 0, 100, 50),
481           DesktopRect::MakeLTRB(0, 50, 50, 70),
482           DesktopRect::MakeLTRB(70, 50, 100, 70),
483           DesktopRect::MakeLTRB(0, 70, 100, 100) } },
484
485    // Empty result.
486    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
487      1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
488      0, {} },
489
490    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
491      1, { DesktopRect::MakeLTRB(-10, -10, 110, 110) },
492      0, {} },
493
494    { 2, { DesktopRect::MakeLTRB(0, 0, 100, 100),
495           DesktopRect::MakeLTRB(50, 50, 150, 150) },
496      2, { DesktopRect::MakeLTRB(0, 0, 100, 100),
497           DesktopRect::MakeLTRB(50, 50, 150, 150) },
498      0, {} },
499
500    // One rect out of disjoint set.
501    { 3, { DesktopRect::MakeLTRB(0, 0, 10, 10),
502           DesktopRect::MakeLTRB(20, 20, 30, 30),
503           DesktopRect::MakeLTRB(40, 0, 50, 10) },
504      1, { DesktopRect::MakeLTRB(20, 20, 30, 30) },
505      2, { DesktopRect::MakeLTRB(0, 0, 10, 10),
506           DesktopRect::MakeLTRB(40, 0, 50, 10) } },
507
508    // Row merging.
509    { 3, { DesktopRect::MakeLTRB(0, 0, 100, 50),
510           DesktopRect::MakeLTRB(0, 50, 150, 70),
511           DesktopRect::MakeLTRB(0, 70, 100, 100) },
512      1, { DesktopRect::MakeLTRB(100, 50, 150, 70) },
513      1, { DesktopRect::MakeLTRB(0, 0, 100, 100) } },
514
515    // No-op subtraction.
516    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
517      1, { DesktopRect::MakeLTRB(100, 0, 200, 100) },
518      1, { DesktopRect::MakeLTRB(0, 0, 100, 100) } },
519
520    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
521      1, { DesktopRect::MakeLTRB(-100, 0, 0, 100) },
522      1, { DesktopRect::MakeLTRB(0, 0, 100, 100) } },
523
524    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
525      1, { DesktopRect::MakeLTRB(0, 100, 0, 200) },
526      1, { DesktopRect::MakeLTRB(0, 0, 100, 100) } },
527
528    { 1, { DesktopRect::MakeLTRB(0, 0, 100, 100) },
529      1, { DesktopRect::MakeLTRB(0, -100, 100, 0) },
530      1, { DesktopRect::MakeLTRB(0, 0, 100, 100) } },
531  };
532
533  for (size_t i = 0; i < (sizeof(cases) / sizeof(Case)); ++i) {
534    SCOPED_TRACE(i);
535
536    DesktopRegion r1(cases[i].input1_rects, cases[i].input1_count);
537    DesktopRegion r2(cases[i].input2_rects, cases[i].input2_count);
538
539    r1.Subtract(r2);
540
541    CompareRegion(r1, cases[i].expected_rects, cases[i].expected_count);
542  }
543}
544
545// Verify that DesktopRegion::SubtractRows() works correctly by creating a row
546// of not overlapping rectangles and subtracting a set of rectangle. Result
547// is verified by building a map of the region in an array and comparing it with
548// the expected values.
549TEST(DesktopRegionTest, SubtractRectOnSameRow) {
550  const int kMapWidth = 50;
551
552  struct SpanSet {
553    int count;
554    struct Range {
555     int start;
556     int end;
557    } spans[3];
558  } span_sets[] = {
559    {1, { {0, 3} } },
560    {1, { {0, 5} } },
561    {1, { {0, 7} } },
562    {1, { {0, 12} } },
563    {2, { {0, 3}, {4, 5}, {6, 16} } },
564  };
565
566  DesktopRegion base_region;
567  bool base_map[kMapWidth] = { false, };
568
569  base_region.AddRect(DesktopRect::MakeXYWH(5, 0, 5, 1));
570  std::fill_n(base_map + 5, 5, true);
571  base_region.AddRect(DesktopRect::MakeXYWH(15, 0, 5, 1));
572  std::fill_n(base_map + 15, 5, true);
573  base_region.AddRect(DesktopRect::MakeXYWH(25, 0, 5, 1));
574  std::fill_n(base_map + 25, 5, true);
575  base_region.AddRect(DesktopRect::MakeXYWH(35, 0, 5, 1));
576  std::fill_n(base_map + 35, 5, true);
577  base_region.AddRect(DesktopRect::MakeXYWH(45, 0, 5, 1));
578  std::fill_n(base_map + 45, 5, true);
579
580  for (size_t i = 0; i < sizeof(span_sets) / sizeof(span_sets[0]); i++) {
581    SCOPED_TRACE(i);
582    SpanSet& span_set = span_sets[i];
583    int span_set_end = span_set.spans[span_set.count - 1].end;
584    for (int x = 0; x < kMapWidth - span_set_end; ++x) {
585      SCOPED_TRACE(x);
586
587      DesktopRegion r = base_region;
588
589      bool expected_map[kMapWidth];
590      std::copy(base_map, base_map + kMapWidth, expected_map);
591
592      DesktopRegion region2;
593      for (int span = 0; span < span_set.count; span++) {
594        std::fill_n(x + expected_map + span_set.spans[span].start,
595                    span_set.spans[span].end - span_set.spans[span].start,
596                    false);
597        region2.AddRect(DesktopRect::MakeLTRB(x + span_set.spans[span].start, 0,
598                                              x + span_set.spans[span].end, 1));
599      }
600      r.Subtract(region2);
601
602      bool map[kMapWidth] = { false, };
603
604      int pos = -1;
605      for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
606        EXPECT_GT(it.rect().left(), pos);
607        pos = it.rect().right();
608        std::fill_n(map + it.rect().left(), it.rect().width(), true);
609      }
610
611      EXPECT_TRUE(std::equal(map, map + kMapWidth, expected_map));
612    }
613  }
614}
615
616// Verify that DesktopRegion::Subtract() works correctly by creating a column of
617// not overlapping rectangles and subtracting a set of rectangle on the same
618// column. Result is verified by building a map of the region in an array and
619// comparing it with the expected values.
620TEST(DesktopRegionTest, SubtractRectOnSameCol) {
621  const int kMapHeight = 50;
622
623  struct SpanSet {
624    int count;
625    struct Range {
626     int start;
627     int end;
628    } spans[3];
629  } span_sets[] = {
630    {1, { {0, 3} } },
631    {1, { {0, 5} } },
632    {1, { {0, 7} } },
633    {1, { {0, 12} } },
634    {2, { {0, 3}, {4, 5}, {6, 16} } },
635  };
636
637  DesktopRegion base_region;
638  bool base_map[kMapHeight] = { false, };
639
640  base_region.AddRect(DesktopRect::MakeXYWH(0, 5, 1, 5));
641  std::fill_n(base_map + 5, 5, true);
642  base_region.AddRect(DesktopRect::MakeXYWH(0, 15, 1, 5));
643  std::fill_n(base_map + 15, 5, true);
644  base_region.AddRect(DesktopRect::MakeXYWH(0, 25, 1, 5));
645  std::fill_n(base_map + 25, 5, true);
646  base_region.AddRect(DesktopRect::MakeXYWH(0, 35, 1, 5));
647  std::fill_n(base_map + 35, 5, true);
648  base_region.AddRect(DesktopRect::MakeXYWH(0, 45, 1, 5));
649  std::fill_n(base_map + 45, 5, true);
650
651  for (size_t i = 0; i < sizeof(span_sets) / sizeof(span_sets[0]); i++) {
652    SCOPED_TRACE(i);
653    SpanSet& span_set = span_sets[i];
654    int span_set_end = span_set.spans[span_set.count - 1].end;
655    for (int y = 0; y < kMapHeight - span_set_end; ++y) {
656      SCOPED_TRACE(y);
657
658      DesktopRegion r = base_region;
659
660      bool expected_map[kMapHeight];
661      std::copy(base_map, base_map + kMapHeight, expected_map);
662
663      DesktopRegion region2;
664      for (int span = 0; span < span_set.count; span++) {
665        std::fill_n(y + expected_map + span_set.spans[span].start,
666                    span_set.spans[span].end - span_set.spans[span].start,
667                    false);
668        region2.AddRect(DesktopRect::MakeLTRB(0, y + span_set.spans[span].start,
669                                              1, y + span_set.spans[span].end));
670      }
671      r.Subtract(region2);
672
673      bool map[kMapHeight] = { false, };
674
675      int pos = -1;
676      for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
677        EXPECT_GT(it.rect().top(), pos);
678        pos = it.rect().bottom();
679        std::fill_n(map + it.rect().top(), it.rect().height(), true);
680      }
681
682      for (int j = 0; j < kMapHeight; j++) {
683        EXPECT_EQ(expected_map[j], map[j]) << "j = " << j;
684      }
685    }
686  }
687}
688
689
690TEST(DesktopRegionTest, DISABLED_Performance) {
691  for (int c = 0; c < 1000; ++c) {
692    DesktopRegion r;
693    for (int i = 0; i < 10; ++i) {
694      r.AddRect(DesktopRect::MakeXYWH(
695          RadmonInt(1000), RadmonInt(1000), 200, 200));
696    }
697
698    for (int i = 0; i < 1000; ++i) {
699      r.AddRect(DesktopRect::MakeXYWH(
700          RadmonInt(1000), RadmonInt(1000),
701          5 + RadmonInt(10) * 5, 5 + RadmonInt(10) * 5));
702    }
703
704    // Iterate over the rectangles.
705    for (DesktopRegion::Iterator it(r); !it.IsAtEnd(); it.Advance()) {
706    }
707  }
708}
709
710}  // namespace webrtc
711