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 <assert.h>
14
15#include <algorithm>
16
17namespace webrtc {
18
19DesktopRegion::RowSpan::RowSpan(int32_t left, int32_t right)
20    : left(left), right(right) {
21}
22
23DesktopRegion::Row::Row(int32_t top, int32_t bottom)
24    : top(top), bottom(bottom) {
25}
26
27DesktopRegion::Row::~Row() {}
28
29DesktopRegion::DesktopRegion() {}
30
31DesktopRegion::DesktopRegion(const DesktopRect& rect) {
32  AddRect(rect);
33}
34
35DesktopRegion::DesktopRegion(const DesktopRect* rects, int count) {
36  AddRects(rects, count);
37}
38
39DesktopRegion::DesktopRegion(const DesktopRegion& other) {
40  *this = other;
41}
42
43DesktopRegion::~DesktopRegion() {
44  Clear();
45}
46
47DesktopRegion& DesktopRegion::operator=(const DesktopRegion& other) {
48  Clear();
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
58bool 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}
75
76void DesktopRegion::Clear() {
77  for (Rows::iterator row = rows_.begin(); row != rows_.end(); ++row) {
78    delete row->second;
79  }
80  rows_.clear();
81}
82
83void DesktopRegion::SetRect(const DesktopRect& rect) {
84  Clear();
85  AddRect(rect);
86}
87
88void DesktopRegion::AddRect(const DesktopRect& rect) {
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
110      // two, at |top|, and leave |row| referring to the lower of the two,
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.
137    ++row;
138  }
139
140  if (row != rows_.end())
141    MergeWithPrecedingRow(row);
142}
143
144void DesktopRegion::AddRects(const DesktopRect* rects, int count) {
145  for (int i = 0; i < count; ++i) {
146    AddRect(rects[i]);
147  }
148}
149
150void 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  }
166}
167
168void DesktopRegion::AddRegion(const DesktopRegion& region) {
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().
171  for (Iterator it(region); !it.IsAtEnd(); it.Advance()) {
172    AddRect(it.rect());
173  }
174}
175
176void 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);
192    }
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);
212    } else {
213      MergeWithPrecedingRow(new_row);
214    }
215
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;
222  }
223}
224
225// static
226void 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
263void DesktopRegion::IntersectWith(const DesktopRegion& region) {
264  DesktopRegion old_region;
265  Swap(&old_region);
266  Intersect(old_region, region);
267}
268
269void DesktopRegion::IntersectWith(const DesktopRect& rect) {
270  DesktopRegion region;
271  region.AddRect(rect);
272  IntersectWith(region);
273}
274
275void 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;
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      }
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) {
342      ++row_b;
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);
356      ++row_a;
357    }
358  }
359
360  if (row_a != rows_.end())
361    MergeWithPrecedingRow(row_a);
362}
363
364void DesktopRegion::Subtract(const DesktopRect& rect) {
365  DesktopRegion region;
366  region.AddRect(rect);
367  Subtract(region);
368}
369
370void DesktopRegion::Translate(int32_t dx, int32_t dy) {
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));
390  }
391
392  if (dy != 0)
393    new_rows.swap(rows_);
394}
395
396void DesktopRegion::Swap(DesktopRegion* region) {
397  rows_.swap(region->rows_);
398}
399
400// static
401bool DesktopRegion::CompareSpanRight(const RowSpan& r, int32_t value) {
402  return r.right < value;
403}
404
405// static
406bool DesktopRegion::CompareSpanLeft(const RowSpan& r, int32_t value) {
407  return r.left < value;
408}
409
410// static
411void 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
459bool 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;
466}
467
468// static
469void 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);
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) {
489      if (it_b->left > pos)
490        output->push_back(RowSpan(pos, it_b->left));
491      if (it_b->right > pos) {
492        pos = it_b->right;
493        if (pos >= it_a->right)
494          break;
495      }
496      ++it_b;
497    }
498    if (pos < it_a->right)
499      output->push_back(RowSpan(pos, it_a->right));
500  }
501}
502
503DesktopRegion::Iterator::Iterator(const DesktopRegion& region)
504    : region_(region),
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  }
512}
513
514DesktopRegion::Iterator::~Iterator() {}
515
516bool DesktopRegion::Iterator::IsAtEnd() const {
517  return row_ == region_.rows_.end();
518}
519
520void DesktopRegion::Iterator::Advance() {
521  assert(!IsAtEnd());
522
523  while (true) {
524    ++row_span_;
525    if (row_span_ == row_->second->spans.end()) {
526      previous_row_ = row_;
527      ++row_;
528      if (row_ != region_.rows_.end()) {
529        assert(row_->second->spans.size() > 0);
530        row_span_ = row_->second->spans.begin();
531      }
532    }
533
534    if (IsAtEnd())
535      return;
536
537    // If the same span exists on the previous row then skip it, as we've
538    // already returned this span merged into the previous one, via
539    // UpdateCurrentRect().
540    if (previous_row_ != region_.rows_.end() &&
541        previous_row_->second->bottom == row_->second->top &&
542        IsSpanInRow(*previous_row_->second, *row_span_)) {
543      continue;
544    }
545
546    break;
547  }
548
549  assert(!IsAtEnd());
550  UpdateCurrentRect();
551}
552
553void DesktopRegion::Iterator::UpdateCurrentRect() {
554  // Merge the current rectangle with the matching spans from later rows.
555  int bottom;
556  Rows::const_iterator bottom_row = row_;
557  Rows::const_iterator previous;
558  do {
559    bottom = bottom_row->second->bottom;
560    previous = bottom_row;
561    ++bottom_row;
562  } while (bottom_row != region_.rows_.end() &&
563           previous->second->bottom == bottom_row->second->top &&
564           IsSpanInRow(*bottom_row->second, *row_span_));
565  rect_ = DesktopRect::MakeLTRB(row_span_->left, row_->second->top,
566                                row_span_->right, bottom);
567}
568
569}  // namespace webrtc
570