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