Home | History | Annotate | Download | only in desktop_capture 
      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 
     17 namespace webrtc {
     18 
     19 namespace {
     20 
     21 int RadmonInt(int max) {
     22   return (rand() / 256) % max;
     23 }
     24 
     25 void 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.
     44 TEST(DesktopRegionTest, Empty) {
     45   DesktopRegion r;
     46   CompareRegion(r, NULL, 0);
     47 }
     48 
     49 // Verify that empty rectangles are ignored.
     50 TEST(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.
     58 TEST(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.
     66 TEST(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 
    110 TEST(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.
    217 TEST(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 
    262 TEST(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 
    313 TEST(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 
    373 TEST(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 
    402 TEST(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 
    447 TEST(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.
    549 TEST(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.
    620 TEST(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 
    690 TEST(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