sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 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 | |
pbos@webrtc.org | 3f45c2e | 2013-08-05 16:22:53 +0000 | [diff] [blame] | 13 | #include <assert.h> |
| 14 | |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 15 | #include <algorithm> |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 16 | |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 17 | namespace webrtc { |
| 18 | |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 19 | DesktopRegion::RowSpan::RowSpan(int32_t left, int32_t right) |
| 20 | : left(left), right(right) { |
| 21 | } |
| 22 | |
| 23 | DesktopRegion::Row::Row(int32_t top, int32_t bottom) |
| 24 | : top(top), bottom(bottom) { |
| 25 | } |
| 26 | |
pbos@webrtc.org | 10b3664 | 2013-07-31 15:32:43 +0000 | [diff] [blame] | 27 | DesktopRegion::Row::~Row() {} |
| 28 | |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 29 | DesktopRegion::DesktopRegion() {} |
| 30 | |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 31 | DesktopRegion::DesktopRegion(const DesktopRect& rect) { |
| 32 | AddRect(rect); |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 33 | } |
| 34 | |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 35 | DesktopRegion::DesktopRegion(const DesktopRect* rects, int count) { |
| 36 | AddRects(rects, count); |
| 37 | } |
| 38 | |
| 39 | DesktopRegion::DesktopRegion(const DesktopRegion& other) { |
| 40 | *this = other; |
| 41 | } |
| 42 | |
| 43 | DesktopRegion::~DesktopRegion() { |
| 44 | Clear(); |
| 45 | } |
| 46 | |
| 47 | DesktopRegion& DesktopRegion::operator=(const DesktopRegion& other) { |
sergeyu@chromium.org | 31fad0b | 2013-06-05 19:24:42 +0000 | [diff] [blame] | 48 | Clear(); |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 49 | rows_ = other.rows_; |
| 50 | for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) { |
| 51 | // Copy each row. |
| 52 | Row* row = it->second; |
| 53 | it->second = new Row(*row); |
| 54 | } |
| 55 | return *this; |
| 56 | } |
| 57 | |
| 58 | bool DesktopRegion::Equals(const DesktopRegion& region) const { |
| 59 | // Iterate over rows of the tow regions and compare each row. |
| 60 | Rows::const_iterator it1 = rows_.begin(); |
| 61 | Rows::const_iterator it2 = region.rows_.begin(); |
| 62 | while (it1 != rows_.end()) { |
| 63 | if (it2 == region.rows_.end() || |
| 64 | it1->first != it2->first || |
| 65 | it1->second->top != it2->second->top || |
| 66 | it1->second->bottom != it2->second->bottom || |
| 67 | it1->second->spans != it2->second->spans) { |
| 68 | return false; |
| 69 | } |
| 70 | ++it1; |
| 71 | ++it2; |
| 72 | } |
| 73 | return it2 == region.rows_.end(); |
| 74 | } |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 75 | |
| 76 | void DesktopRegion::Clear() { |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 77 | for (Rows::iterator row = rows_.begin(); row != rows_.end(); ++row) { |
| 78 | delete row->second; |
| 79 | } |
| 80 | rows_.clear(); |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 81 | } |
| 82 | |
| 83 | void DesktopRegion::SetRect(const DesktopRect& rect) { |
| 84 | Clear(); |
| 85 | AddRect(rect); |
| 86 | } |
| 87 | |
| 88 | void DesktopRegion::AddRect(const DesktopRect& rect) { |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 89 | if (rect.is_empty()) |
| 90 | return; |
| 91 | |
| 92 | // Top of the part of the |rect| that hasn't been inserted yet. Increased as |
| 93 | // we iterate over the rows until it reaches |rect.bottom()|. |
| 94 | int top = rect.top(); |
| 95 | |
| 96 | // Iterate over all rows that may intersect with |rect| and add new rows when |
| 97 | // necessary. |
| 98 | Rows::iterator row = rows_.upper_bound(top); |
| 99 | while (top < rect.bottom()) { |
| 100 | if (row == rows_.end() || top < row->second->top) { |
| 101 | // If |top| is above the top of the current |row| then add a new row above |
| 102 | // the current one. |
| 103 | int32_t bottom = rect.bottom(); |
| 104 | if (row != rows_.end() && row->second->top < bottom) |
| 105 | bottom = row->second->top; |
| 106 | row = rows_.insert( |
| 107 | row, Rows::value_type(bottom, new Row(top, bottom))); |
| 108 | } else if (top > row->second->top) { |
| 109 | // If the |top| falls in the middle of the |row| then split |row| into |
sergeyu@chromium.org | 26251da | 2013-09-13 19:53:16 +0000 | [diff] [blame] | 110 | // two, at |top|, and leave |row| referring to the lower of the two, |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 111 | // ready to insert a new span into. |
| 112 | assert(top <= row->second->bottom); |
| 113 | Rows::iterator new_row = rows_.insert( |
| 114 | row, Rows::value_type(top, new Row(row->second->top, top))); |
| 115 | row->second->top = top; |
| 116 | new_row->second->spans = row->second->spans; |
| 117 | } |
| 118 | |
| 119 | if (rect.bottom() < row->second->bottom) { |
| 120 | // If the bottom of the |rect| falls in the middle of the |row| split |
| 121 | // |row| into two, at |top|, and leave |row| referring to the upper of |
| 122 | // the two, ready to insert a new span into. |
| 123 | Rows::iterator new_row = rows_.insert( |
| 124 | row, Rows::value_type(rect.bottom(), new Row(top, rect.bottom()))); |
| 125 | row->second->top = rect.bottom(); |
| 126 | new_row->second->spans = row->second->spans; |
| 127 | row = new_row; |
| 128 | } |
| 129 | |
| 130 | // Add a new span to the current row. |
| 131 | AddSpanToRow(row->second, rect.left(), rect.right()); |
| 132 | top = row->second->bottom; |
| 133 | |
| 134 | MergeWithPrecedingRow(row); |
| 135 | |
| 136 | // Move to the next row. |
sergeyu@chromium.org | d1fe828 | 2013-09-20 21:29:18 +0000 | [diff] [blame] | 137 | ++row; |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 138 | } |
| 139 | |
| 140 | if (row != rows_.end()) |
| 141 | MergeWithPrecedingRow(row); |
| 142 | } |
| 143 | |
| 144 | void DesktopRegion::AddRects(const DesktopRect* rects, int count) { |
| 145 | for (int i = 0; i < count; ++i) { |
| 146 | AddRect(rects[i]); |
| 147 | } |
| 148 | } |
| 149 | |
| 150 | void DesktopRegion::MergeWithPrecedingRow(Rows::iterator row) { |
| 151 | assert(row != rows_.end()); |
| 152 | |
| 153 | if (row != rows_.begin()) { |
| 154 | Rows::iterator previous_row = row; |
| 155 | previous_row--; |
| 156 | |
| 157 | // If |row| and |previous_row| are next to each other and contain the same |
| 158 | // set of spans then they can be merged. |
| 159 | if (previous_row->second->bottom == row->second->top && |
| 160 | previous_row->second->spans == row->second->spans) { |
| 161 | row->second->top = previous_row->second->top; |
| 162 | delete previous_row->second; |
| 163 | rows_.erase(previous_row); |
| 164 | } |
| 165 | } |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 166 | } |
| 167 | |
| 168 | void DesktopRegion::AddRegion(const DesktopRegion& region) { |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 169 | // TODO(sergeyu): This function is not optimized - potentially it can iterate |
| 170 | // over rows of the two regions similar to how it works in Intersect(). |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 171 | for (Iterator it(region); !it.IsAtEnd(); it.Advance()) { |
| 172 | AddRect(it.rect()); |
| 173 | } |
| 174 | } |
| 175 | |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 176 | void DesktopRegion::Intersect(const DesktopRegion& region1, |
| 177 | const DesktopRegion& region2) { |
| 178 | Clear(); |
| 179 | |
| 180 | Rows::const_iterator it1 = region1.rows_.begin(); |
| 181 | Rows::const_iterator end1 = region1.rows_.end(); |
| 182 | Rows::const_iterator it2 = region2.rows_.begin(); |
| 183 | Rows::const_iterator end2 = region2.rows_.end(); |
| 184 | if (it1 == end1 || it2 == end2) |
| 185 | return; |
| 186 | |
| 187 | while (it1 != end1 && it2 != end2) { |
| 188 | // Arrange for |it1| to always be the top-most of the rows. |
| 189 | if (it2->second->top < it1->second->top) { |
| 190 | std::swap(it1, it2); |
| 191 | std::swap(end1, end2); |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 192 | } |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 193 | |
| 194 | // Skip |it1| if it doesn't intersect |it2| at all. |
| 195 | if (it1->second->bottom <= it2->second->top) { |
| 196 | ++it1; |
| 197 | continue; |
| 198 | } |
| 199 | |
| 200 | // Top of the |it1| row is above the top of |it2|, so top of the |
| 201 | // intersection is always the top of |it2|. |
| 202 | int32_t top = it2->second->top; |
| 203 | int32_t bottom = std::min(it1->second->bottom, it2->second->bottom); |
| 204 | |
| 205 | Rows::iterator new_row = rows_.insert( |
| 206 | rows_.end(), Rows::value_type(bottom, new Row(top, bottom))); |
| 207 | IntersectRows(it1->second->spans, it2->second->spans, |
| 208 | &new_row->second->spans); |
| 209 | if (new_row->second->spans.empty()) { |
| 210 | delete new_row->second; |
| 211 | rows_.erase(new_row); |
sergeyu@chromium.org | c7df0aa | 2013-08-01 19:51:04 +0000 | [diff] [blame] | 212 | } else { |
| 213 | MergeWithPrecedingRow(new_row); |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 214 | } |
| 215 | |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 216 | // If |it1| was completely consumed, move to the next one. |
| 217 | if (it1->second->bottom == bottom) |
| 218 | ++it1; |
| 219 | // If |it2| was completely consumed, move to the next one. |
| 220 | if (it2->second->bottom == bottom) |
| 221 | ++it2; |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 222 | } |
| 223 | } |
| 224 | |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 225 | // static |
| 226 | void DesktopRegion::IntersectRows(const RowSpanSet& set1, |
| 227 | const RowSpanSet& set2, |
| 228 | RowSpanSet* output) { |
| 229 | RowSpanSet::const_iterator it1 = set1.begin(); |
| 230 | RowSpanSet::const_iterator end1 = set1.end(); |
| 231 | RowSpanSet::const_iterator it2 = set2.begin(); |
| 232 | RowSpanSet::const_iterator end2 = set2.end(); |
| 233 | assert(it1 != end1 && it2 != end2); |
| 234 | |
| 235 | do { |
| 236 | // Arrange for |it1| to always be the left-most of the spans. |
| 237 | if (it2->left < it1->left) { |
| 238 | std::swap(it1, it2); |
| 239 | std::swap(end1, end2); |
| 240 | } |
| 241 | |
| 242 | // Skip |it1| if it doesn't intersect |it2| at all. |
| 243 | if (it1->right <= it2->left) { |
| 244 | ++it1; |
| 245 | continue; |
| 246 | } |
| 247 | |
| 248 | int32_t left = it2->left; |
| 249 | int32_t right = std::min(it1->right, it2->right); |
| 250 | assert(left < right); |
| 251 | |
| 252 | output->push_back(RowSpan(left, right)); |
| 253 | |
| 254 | // If |it1| was completely consumed, move to the next one. |
| 255 | if (it1->right == right) |
| 256 | ++it1; |
| 257 | // If |it2| was completely consumed, move to the next one. |
| 258 | if (it2->right == right) |
| 259 | ++it2; |
| 260 | } while (it1 != end1 && it2 != end2); |
| 261 | } |
| 262 | |
| 263 | void DesktopRegion::IntersectWith(const DesktopRegion& region) { |
| 264 | DesktopRegion old_region; |
| 265 | Swap(&old_region); |
| 266 | Intersect(old_region, region); |
| 267 | } |
| 268 | |
| 269 | void DesktopRegion::IntersectWith(const DesktopRect& rect) { |
| 270 | DesktopRegion region; |
| 271 | region.AddRect(rect); |
| 272 | IntersectWith(region); |
| 273 | } |
| 274 | |
sergeyu@chromium.org | 26251da | 2013-09-13 19:53:16 +0000 | [diff] [blame] | 275 | void DesktopRegion::Subtract(const DesktopRegion& region) { |
| 276 | if (region.rows_.empty()) |
| 277 | return; |
| 278 | |
| 279 | // |row_b| refers to the current row being subtracted. |
| 280 | Rows::const_iterator row_b = region.rows_.begin(); |
| 281 | |
| 282 | // Current vertical position at which subtraction is happening. |
| 283 | int top = row_b->second->top; |
| 284 | |
| 285 | // |row_a| refers to the current row we are subtracting from. Skip all rows |
| 286 | // above |top|. |
| 287 | Rows::iterator row_a = rows_.upper_bound(top); |
| 288 | |
| 289 | // Step through rows of the both regions subtracting content of |row_b| from |
| 290 | // |row_a|. |
| 291 | while (row_a != rows_.end() && row_b != region.rows_.end()) { |
| 292 | // Skip |row_a| if it doesn't intersect with the |row_b|. |
| 293 | if (row_a->second->bottom <= top) { |
| 294 | // Each output row is merged with previously-processed rows before further |
| 295 | // rows are processed. |
| 296 | MergeWithPrecedingRow(row_a); |
| 297 | ++row_a; |
| 298 | continue; |
| 299 | } |
| 300 | |
| 301 | if (top > row_a->second->top) { |
| 302 | // If |top| falls in the middle of |row_a| then split |row_a| into two, at |
| 303 | // |top|, and leave |row_a| referring to the lower of the two, ready to |
| 304 | // subtract spans from. |
| 305 | assert(top <= row_a->second->bottom); |
| 306 | Rows::iterator new_row = rows_.insert( |
| 307 | row_a, Rows::value_type(top, new Row(row_a->second->top, top))); |
| 308 | row_a->second->top = top; |
| 309 | new_row->second->spans = row_a->second->spans; |
| 310 | } else if (top < row_a->second->top) { |
| 311 | // If the |top| is above |row_a| then skip the range between |top| and |
| 312 | // top of |row_a| because it's empty. |
| 313 | top = row_a->second->top; |
sergeyu@chromium.org | d1fe828 | 2013-09-20 21:29:18 +0000 | [diff] [blame] | 314 | if (top >= row_b->second->bottom) { |
| 315 | ++row_b; |
| 316 | if (row_b != region.rows_.end()) |
| 317 | top = row_b->second->top; |
| 318 | continue; |
| 319 | } |
sergeyu@chromium.org | 26251da | 2013-09-13 19:53:16 +0000 | [diff] [blame] | 320 | } |
| 321 | |
| 322 | if (row_b->second->bottom < row_a->second->bottom) { |
| 323 | // If the bottom of |row_b| falls in the middle of the |row_a| split |
| 324 | // |row_a| into two, at |top|, and leave |row_a| referring to the upper of |
| 325 | // the two, ready to subtract spans from. |
| 326 | int bottom = row_b->second->bottom; |
| 327 | Rows::iterator new_row = |
| 328 | rows_.insert(row_a, Rows::value_type(bottom, new Row(top, bottom))); |
| 329 | row_a->second->top = bottom; |
| 330 | new_row->second->spans = row_a->second->spans; |
| 331 | row_a = new_row; |
| 332 | } |
| 333 | |
| 334 | // At this point the vertical range covered by |row_a| lays within the |
| 335 | // range covered by |row_b|. Subtract |row_b| spans from |row_a|. |
| 336 | RowSpanSet new_spans; |
| 337 | SubtractRows(row_a->second->spans, row_b->second->spans, &new_spans); |
| 338 | new_spans.swap(row_a->second->spans); |
| 339 | top = row_a->second->bottom; |
| 340 | |
| 341 | if (top >= row_b->second->bottom) { |
sergeyu@chromium.org | d1fe828 | 2013-09-20 21:29:18 +0000 | [diff] [blame] | 342 | ++row_b; |
sergeyu@chromium.org | 26251da | 2013-09-13 19:53:16 +0000 | [diff] [blame] | 343 | if (row_b != region.rows_.end()) |
| 344 | top = row_b->second->top; |
| 345 | } |
| 346 | |
| 347 | // Check if the row is empty after subtraction and delete it. Otherwise move |
| 348 | // to the next one. |
| 349 | if (row_a->second->spans.empty()) { |
| 350 | Rows::iterator row_to_delete = row_a; |
| 351 | ++row_a; |
| 352 | delete row_to_delete->second; |
| 353 | rows_.erase(row_to_delete); |
| 354 | } else { |
| 355 | MergeWithPrecedingRow(row_a); |
sergeyu@chromium.org | d1fe828 | 2013-09-20 21:29:18 +0000 | [diff] [blame] | 356 | ++row_a; |
sergeyu@chromium.org | 26251da | 2013-09-13 19:53:16 +0000 | [diff] [blame] | 357 | } |
| 358 | } |
| 359 | |
| 360 | if (row_a != rows_.end()) |
| 361 | MergeWithPrecedingRow(row_a); |
| 362 | } |
| 363 | |
| 364 | void DesktopRegion::Subtract(const DesktopRect& rect) { |
| 365 | DesktopRegion region; |
| 366 | region.AddRect(rect); |
| 367 | Subtract(region); |
| 368 | } |
| 369 | |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 370 | void DesktopRegion::Translate(int32_t dx, int32_t dy) { |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 371 | Rows new_rows; |
| 372 | |
| 373 | for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) { |
| 374 | Row* row = it->second; |
| 375 | |
| 376 | row->top += dy; |
| 377 | row->bottom += dy; |
| 378 | |
| 379 | if (dx != 0) { |
| 380 | // Translate each span. |
| 381 | for (RowSpanSet::iterator span = row->spans.begin(); |
| 382 | span != row->spans.end(); ++span) { |
| 383 | span->left += dx; |
| 384 | span->right += dx; |
| 385 | } |
| 386 | } |
| 387 | |
| 388 | if (dy != 0) |
| 389 | new_rows.insert(new_rows.end(), Rows::value_type(row->bottom, row)); |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 390 | } |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 391 | |
| 392 | if (dy != 0) |
| 393 | new_rows.swap(rows_); |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 394 | } |
| 395 | |
| 396 | void DesktopRegion::Swap(DesktopRegion* region) { |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 397 | rows_.swap(region->rows_); |
| 398 | } |
| 399 | |
| 400 | // static |
| 401 | bool DesktopRegion::CompareSpanRight(const RowSpan& r, int32_t value) { |
| 402 | return r.right < value; |
| 403 | } |
| 404 | |
| 405 | // static |
| 406 | bool DesktopRegion::CompareSpanLeft(const RowSpan& r, int32_t value) { |
| 407 | return r.left < value; |
| 408 | } |
| 409 | |
| 410 | // static |
| 411 | void DesktopRegion::AddSpanToRow(Row* row, int left, int right) { |
| 412 | // First check if the new span is located to the right of all existing spans. |
| 413 | // This is an optimization to avoid binary search in the case when rectangles |
| 414 | // are inserted sequentially from left to right. |
| 415 | if (row->spans.empty() || left > row->spans.back().right) { |
| 416 | row->spans.push_back(RowSpan(left, right)); |
| 417 | return; |
| 418 | } |
| 419 | |
| 420 | // Find the first span that ends at or after |left|. |
| 421 | RowSpanSet::iterator start = |
| 422 | std::lower_bound(row->spans.begin(), row->spans.end(), left, |
| 423 | CompareSpanRight); |
| 424 | assert(start < row->spans.end()); |
| 425 | |
| 426 | // Find the first span that starts after |right|. |
| 427 | RowSpanSet::iterator end = |
| 428 | std::lower_bound(start, row->spans.end(), right + 1, CompareSpanLeft); |
| 429 | if (end == row->spans.begin()) { |
| 430 | // There are no overlaps. Just insert the new span at the beginning. |
| 431 | row->spans.insert(row->spans.begin(), RowSpan(left, right)); |
| 432 | return; |
| 433 | } |
| 434 | |
| 435 | // Move end to the left, so that it points the last span that ends at or |
| 436 | // before |right|. |
| 437 | end--; |
| 438 | |
| 439 | // At this point [start, end] is the range of spans that intersect with the |
| 440 | // new one. |
| 441 | if (end < start) { |
| 442 | // There are no overlaps. Just insert the new span at the correct position. |
| 443 | row->spans.insert(start, RowSpan(left, right)); |
| 444 | return; |
| 445 | } |
| 446 | |
| 447 | left = std::min(left, start->left); |
| 448 | right = std::max(right, end->right); |
| 449 | |
| 450 | // Replace range [start, end] with the new span. |
| 451 | *start = RowSpan(left, right); |
| 452 | ++start; |
| 453 | ++end; |
| 454 | if (start < end) |
| 455 | row->spans.erase(start, end); |
| 456 | } |
| 457 | |
| 458 | // static |
| 459 | bool DesktopRegion::IsSpanInRow(const Row& row, const RowSpan& span) { |
| 460 | // Find the first span that starts at or after |span.left| and then check if |
| 461 | // it's the same span. |
| 462 | RowSpanSet::const_iterator it = |
| 463 | std::lower_bound(row.spans.begin(), row.spans.end(), span.left, |
| 464 | CompareSpanLeft); |
| 465 | return it != row.spans.end() && *it == span; |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 466 | } |
| 467 | |
sergeyu@chromium.org | 26251da | 2013-09-13 19:53:16 +0000 | [diff] [blame] | 468 | // static |
| 469 | void DesktopRegion::SubtractRows(const RowSpanSet& set_a, |
| 470 | const RowSpanSet& set_b, |
| 471 | RowSpanSet* output) { |
| 472 | assert(!set_a.empty() && !set_b.empty()); |
| 473 | |
| 474 | RowSpanSet::const_iterator it_b = set_b.begin(); |
| 475 | |
| 476 | // Iterate over all spans in |set_a| adding parts of it that do not intersect |
| 477 | // with |set_b| to the |output|. |
| 478 | for (RowSpanSet::const_iterator it_a = set_a.begin(); it_a != set_a.end(); |
| 479 | ++it_a) { |
| 480 | // If there is no intersection then append the current span and continue. |
| 481 | if (it_b == set_b.end() || it_a->right < it_b->left) { |
| 482 | output->push_back(*it_a); |
sergeyu@chromium.org | 26251da | 2013-09-13 19:53:16 +0000 | [diff] [blame] | 483 | continue; |
| 484 | } |
| 485 | |
| 486 | // Iterate over |set_b| spans that may intersect with |it_a|. |
| 487 | int pos = it_a->left; |
| 488 | while (it_b != set_b.end() && it_b->left < it_a->right) { |
sergeyu@chromium.org | d1fe828 | 2013-09-20 21:29:18 +0000 | [diff] [blame] | 489 | if (it_b->left > pos) |
sergeyu@chromium.org | 26251da | 2013-09-13 19:53:16 +0000 | [diff] [blame] | 490 | output->push_back(RowSpan(pos, it_b->left)); |
sergeyu@chromium.org | d1fe828 | 2013-09-20 21:29:18 +0000 | [diff] [blame] | 491 | if (it_b->right > pos) { |
| 492 | pos = it_b->right; |
| 493 | if (pos >= it_a->right) |
| 494 | break; |
sergeyu@chromium.org | 26251da | 2013-09-13 19:53:16 +0000 | [diff] [blame] | 495 | } |
sergeyu@chromium.org | 26251da | 2013-09-13 19:53:16 +0000 | [diff] [blame] | 496 | ++it_b; |
| 497 | } |
| 498 | if (pos < it_a->right) |
| 499 | output->push_back(RowSpan(pos, it_a->right)); |
| 500 | } |
| 501 | } |
| 502 | |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 503 | DesktopRegion::Iterator::Iterator(const DesktopRegion& region) |
| 504 | : region_(region), |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 505 | row_(region.rows_.begin()), |
| 506 | previous_row_(region.rows_.end()) { |
| 507 | if (!IsAtEnd()) { |
| 508 | assert(row_->second->spans.size() > 0); |
| 509 | row_span_ = row_->second->spans.begin(); |
| 510 | UpdateCurrentRect(); |
| 511 | } |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 512 | } |
| 513 | |
| 514 | bool DesktopRegion::Iterator::IsAtEnd() const { |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 515 | return row_ == region_.rows_.end(); |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 516 | } |
| 517 | |
| 518 | void DesktopRegion::Iterator::Advance() { |
sergeyu@chromium.org | aec1bc8 | 2013-06-04 00:38:39 +0000 | [diff] [blame] | 519 | assert(!IsAtEnd()); |
| 520 | |
| 521 | while (true) { |
| 522 | ++row_span_; |
| 523 | if (row_span_ == row_->second->spans.end()) { |
| 524 | previous_row_ = row_; |
| 525 | ++row_; |
| 526 | if (row_ != region_.rows_.end()) { |
| 527 | assert(row_->second->spans.size() > 0); |
| 528 | row_span_ = row_->second->spans.begin(); |
| 529 | } |
| 530 | } |
| 531 | |
| 532 | if (IsAtEnd()) |
| 533 | return; |
| 534 | |
| 535 | // If the same span exists on the previous row then skip it, as we've |
| 536 | // already returned this span merged into the previous one, via |
| 537 | // UpdateCurrentRect(). |
| 538 | if (previous_row_ != region_.rows_.end() && |
| 539 | previous_row_->second->bottom == row_->second->top && |
| 540 | IsSpanInRow(*previous_row_->second, *row_span_)) { |
| 541 | continue; |
| 542 | } |
| 543 | |
| 544 | break; |
| 545 | } |
| 546 | |
| 547 | assert(!IsAtEnd()); |
| 548 | UpdateCurrentRect(); |
| 549 | } |
| 550 | |
| 551 | void DesktopRegion::Iterator::UpdateCurrentRect() { |
| 552 | // Merge the current rectangle with the matching spans from later rows. |
| 553 | int bottom; |
| 554 | Rows::const_iterator bottom_row = row_; |
| 555 | Rows::const_iterator previous; |
| 556 | do { |
| 557 | bottom = bottom_row->second->bottom; |
| 558 | previous = bottom_row; |
| 559 | ++bottom_row; |
| 560 | } while (bottom_row != region_.rows_.end() && |
| 561 | previous->second->bottom == bottom_row->second->top && |
| 562 | IsSpanInRow(*bottom_row->second, *row_span_)); |
| 563 | rect_ = DesktopRect::MakeLTRB(row_span_->left, row_->second->top, |
| 564 | row_span_->right, bottom); |
sergeyu@chromium.org | 85a1dab | 2013-04-29 20:10:57 +0000 | [diff] [blame] | 565 | } |
| 566 | |
| 567 | } // namespace webrtc |