src/third_party/webrtc/modules/desktop_capture/desktop_region_unittest.cc

   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