115e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org/* 215e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org * Copyright (c) 2013 The WebRTC project authors. All Rights Reserved. 315e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org * 415e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org * Use of this source code is governed by a BSD-style license 515e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org * that can be found in the LICENSE file in the root of the source 615e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org * tree. An additional intellectual property rights grant can be found 715e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org * in the file PATENTS. All contributing project authors may 815e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org * be found in the AUTHORS file in the root of the source tree. 915e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org */ 1015e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 1115e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org#include "webrtc/modules/desktop_capture/desktop_region.h" 1215e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 1312dc1a38ca54a000e4fecfbc6d41138b895c9ca5pbos@webrtc.org#include <assert.h> 1412dc1a38ca54a000e4fecfbc6d41138b895c9ca5pbos@webrtc.org 153ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org#include <algorithm> 163ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1715e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.orgnamespace webrtc { 1815e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 193ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgDesktopRegion::RowSpan::RowSpan(int32_t left, int32_t right) 203ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org : left(left), right(right) { 213ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 223ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 233ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgDesktopRegion::Row::Row(int32_t top, int32_t bottom) 243ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org : top(top), bottom(bottom) { 253ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 263ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 27e72428442ded1d0b958d31ba4878f1c43bb3d1f0pbos@webrtc.orgDesktopRegion::Row::~Row() {} 28e72428442ded1d0b958d31ba4878f1c43bb3d1f0pbos@webrtc.org 2915e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.orgDesktopRegion::DesktopRegion() {} 3015e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 313ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgDesktopRegion::DesktopRegion(const DesktopRect& rect) { 323ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org AddRect(rect); 3315e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org} 3415e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 353ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgDesktopRegion::DesktopRegion(const DesktopRect* rects, int count) { 363ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org AddRects(rects, count); 373ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 383ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 393ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgDesktopRegion::DesktopRegion(const DesktopRegion& other) { 403ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org *this = other; 413ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 423ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 433ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgDesktopRegion::~DesktopRegion() { 443ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Clear(); 453ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 463ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 473ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgDesktopRegion& DesktopRegion::operator=(const DesktopRegion& other) { 48d9c46587567ab2637679b4e7463b082a342875edsergeyu@chromium.org Clear(); 493ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org rows_ = other.rows_; 503ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) { 513ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Copy each row. 523ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Row* row = it->second; 533ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org it->second = new Row(*row); 543ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 553ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return *this; 563ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 573ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 583ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgbool DesktopRegion::Equals(const DesktopRegion& region) const { 593ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Iterate over rows of the tow regions and compare each row. 603ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::const_iterator it1 = rows_.begin(); 613ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::const_iterator it2 = region.rows_.begin(); 623ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org while (it1 != rows_.end()) { 633ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (it2 == region.rows_.end() || 643ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org it1->first != it2->first || 653ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org it1->second->top != it2->second->top || 663ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org it1->second->bottom != it2->second->bottom || 673ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org it1->second->spans != it2->second->spans) { 683ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return false; 693ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 703ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++it1; 713ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++it2; 723ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 733ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return it2 == region.rows_.end(); 743ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 7515e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 7615e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.orgvoid DesktopRegion::Clear() { 773ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org for (Rows::iterator row = rows_.begin(); row != rows_.end(); ++row) { 783ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org delete row->second; 793ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 803ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org rows_.clear(); 8115e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org} 8215e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 8315e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.orgvoid DesktopRegion::SetRect(const DesktopRect& rect) { 8415e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org Clear(); 8515e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org AddRect(rect); 8615e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org} 8715e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 8815e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.orgvoid DesktopRegion::AddRect(const DesktopRect& rect) { 893ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (rect.is_empty()) 903ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return; 913ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 923ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Top of the part of the |rect| that hasn't been inserted yet. Increased as 933ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // we iterate over the rows until it reaches |rect.bottom()|. 943ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org int top = rect.top(); 953ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 963ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Iterate over all rows that may intersect with |rect| and add new rows when 973ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // necessary. 983ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::iterator row = rows_.upper_bound(top); 993ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org while (top < rect.bottom()) { 1003ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (row == rows_.end() || top < row->second->top) { 1013ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // If |top| is above the top of the current |row| then add a new row above 1023ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // the current one. 1033ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org int32_t bottom = rect.bottom(); 1043ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (row != rows_.end() && row->second->top < bottom) 1053ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org bottom = row->second->top; 1063ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row = rows_.insert( 1073ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row, Rows::value_type(bottom, new Row(top, bottom))); 1083ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } else if (top > row->second->top) { 1093ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // If the |top| falls in the middle of the |row| then split |row| into 1106ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // two, at |top|, and leave |row| referring to the lower of the two, 1113ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // ready to insert a new span into. 1123ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org assert(top <= row->second->bottom); 1133ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::iterator new_row = rows_.insert( 1143ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row, Rows::value_type(top, new Row(row->second->top, top))); 1153ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row->second->top = top; 1163ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org new_row->second->spans = row->second->spans; 1173ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 1183ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1193ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (rect.bottom() < row->second->bottom) { 1203ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // If the bottom of the |rect| falls in the middle of the |row| split 1213ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // |row| into two, at |top|, and leave |row| referring to the upper of 1223ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // the two, ready to insert a new span into. 1233ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::iterator new_row = rows_.insert( 1243ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row, Rows::value_type(rect.bottom(), new Row(top, rect.bottom()))); 1253ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row->second->top = rect.bottom(); 1263ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org new_row->second->spans = row->second->spans; 1273ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row = new_row; 1283ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 1293ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1303ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Add a new span to the current row. 1313ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org AddSpanToRow(row->second, rect.left(), rect.right()); 1323ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org top = row->second->bottom; 1333ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1343ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org MergeWithPrecedingRow(row); 1353ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1363ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Move to the next row. 1372edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org ++row; 1383ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 1393ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1403ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (row != rows_.end()) 1413ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org MergeWithPrecedingRow(row); 1423ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 1433ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1443ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgvoid DesktopRegion::AddRects(const DesktopRect* rects, int count) { 1453ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org for (int i = 0; i < count; ++i) { 1463ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org AddRect(rects[i]); 1473ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 1483ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 1493ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1503ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgvoid DesktopRegion::MergeWithPrecedingRow(Rows::iterator row) { 1513ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org assert(row != rows_.end()); 1523ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1533ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (row != rows_.begin()) { 1543ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::iterator previous_row = row; 1553ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org previous_row--; 1563ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1573ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // If |row| and |previous_row| are next to each other and contain the same 1583ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // set of spans then they can be merged. 1593ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (previous_row->second->bottom == row->second->top && 1603ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org previous_row->second->spans == row->second->spans) { 1613ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row->second->top = previous_row->second->top; 1623ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org delete previous_row->second; 1633ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org rows_.erase(previous_row); 1643ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 1653ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 16615e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org} 16715e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 16815e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.orgvoid DesktopRegion::AddRegion(const DesktopRegion& region) { 1693ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // TODO(sergeyu): This function is not optimized - potentially it can iterate 1703ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // over rows of the two regions similar to how it works in Intersect(). 17115e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org for (Iterator it(region); !it.IsAtEnd(); it.Advance()) { 17215e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org AddRect(it.rect()); 17315e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org } 17415e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org} 17515e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 1763ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgvoid DesktopRegion::Intersect(const DesktopRegion& region1, 1773ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org const DesktopRegion& region2) { 1783ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Clear(); 1793ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1803ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::const_iterator it1 = region1.rows_.begin(); 1813ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::const_iterator end1 = region1.rows_.end(); 1823ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::const_iterator it2 = region2.rows_.begin(); 1833ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::const_iterator end2 = region2.rows_.end(); 1843ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (it1 == end1 || it2 == end2) 1853ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return; 1863ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1873ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org while (it1 != end1 && it2 != end2) { 1883ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Arrange for |it1| to always be the top-most of the rows. 1893ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (it2->second->top < it1->second->top) { 1903ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org std::swap(it1, it2); 1913ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org std::swap(end1, end2); 19215e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org } 1933ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 1943ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Skip |it1| if it doesn't intersect |it2| at all. 1953ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (it1->second->bottom <= it2->second->top) { 1963ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++it1; 1973ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org continue; 1983ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 1993ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 2003ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Top of the |it1| row is above the top of |it2|, so top of the 2013ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // intersection is always the top of |it2|. 2023ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org int32_t top = it2->second->top; 2033ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org int32_t bottom = std::min(it1->second->bottom, it2->second->bottom); 2043ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 2053ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::iterator new_row = rows_.insert( 2063ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org rows_.end(), Rows::value_type(bottom, new Row(top, bottom))); 2073ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org IntersectRows(it1->second->spans, it2->second->spans, 2083ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org &new_row->second->spans); 2093ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (new_row->second->spans.empty()) { 2103ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org delete new_row->second; 2113ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org rows_.erase(new_row); 21217758e96c5e93ad38b54e2dcabe127fad146e202sergeyu@chromium.org } else { 21317758e96c5e93ad38b54e2dcabe127fad146e202sergeyu@chromium.org MergeWithPrecedingRow(new_row); 2143ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 2153ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 2163ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // If |it1| was completely consumed, move to the next one. 2173ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (it1->second->bottom == bottom) 2183ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++it1; 2193ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // If |it2| was completely consumed, move to the next one. 2203ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (it2->second->bottom == bottom) 2213ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++it2; 22215e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org } 22315e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org} 22415e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 2253ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org// static 2263ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgvoid DesktopRegion::IntersectRows(const RowSpanSet& set1, 2273ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org const RowSpanSet& set2, 2283ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org RowSpanSet* output) { 2293ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org RowSpanSet::const_iterator it1 = set1.begin(); 2303ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org RowSpanSet::const_iterator end1 = set1.end(); 2313ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org RowSpanSet::const_iterator it2 = set2.begin(); 2323ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org RowSpanSet::const_iterator end2 = set2.end(); 2333ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org assert(it1 != end1 && it2 != end2); 2343ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 2353ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org do { 2363ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Arrange for |it1| to always be the left-most of the spans. 2373ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (it2->left < it1->left) { 2383ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org std::swap(it1, it2); 2393ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org std::swap(end1, end2); 2403ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 2413ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 2423ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Skip |it1| if it doesn't intersect |it2| at all. 2433ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (it1->right <= it2->left) { 2443ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++it1; 2453ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org continue; 2463ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 2473ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 2483ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org int32_t left = it2->left; 2493ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org int32_t right = std::min(it1->right, it2->right); 2503ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org assert(left < right); 2513ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 2523ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org output->push_back(RowSpan(left, right)); 2533ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 2543ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // If |it1| was completely consumed, move to the next one. 2553ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (it1->right == right) 2563ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++it1; 2573ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // If |it2| was completely consumed, move to the next one. 2583ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (it2->right == right) 2593ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++it2; 2603ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } while (it1 != end1 && it2 != end2); 2613ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 2623ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 2633ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgvoid DesktopRegion::IntersectWith(const DesktopRegion& region) { 2643ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org DesktopRegion old_region; 2653ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Swap(&old_region); 2663ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Intersect(old_region, region); 2673ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 2683ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 2693ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgvoid DesktopRegion::IntersectWith(const DesktopRect& rect) { 2703ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org DesktopRegion region; 2713ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org region.AddRect(rect); 2723ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org IntersectWith(region); 2733ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 2743ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 2756ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.orgvoid DesktopRegion::Subtract(const DesktopRegion& region) { 2766ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org if (region.rows_.empty()) 2776ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org return; 2786ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 2796ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // |row_b| refers to the current row being subtracted. 2806ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org Rows::const_iterator row_b = region.rows_.begin(); 2816ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 2826ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // Current vertical position at which subtraction is happening. 2836ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org int top = row_b->second->top; 2846ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 2856ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // |row_a| refers to the current row we are subtracting from. Skip all rows 2866ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // above |top|. 2876ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org Rows::iterator row_a = rows_.upper_bound(top); 2886ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 2896ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // Step through rows of the both regions subtracting content of |row_b| from 2906ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // |row_a|. 2916ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org while (row_a != rows_.end() && row_b != region.rows_.end()) { 2926ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // Skip |row_a| if it doesn't intersect with the |row_b|. 2936ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org if (row_a->second->bottom <= top) { 2946ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // Each output row is merged with previously-processed rows before further 2956ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // rows are processed. 2966ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org MergeWithPrecedingRow(row_a); 2976ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org ++row_a; 2986ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org continue; 2996ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } 3006ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 3016ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org if (top > row_a->second->top) { 3026ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // If |top| falls in the middle of |row_a| then split |row_a| into two, at 3036ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // |top|, and leave |row_a| referring to the lower of the two, ready to 3046ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // subtract spans from. 3056ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org assert(top <= row_a->second->bottom); 3066ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org Rows::iterator new_row = rows_.insert( 3076ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org row_a, Rows::value_type(top, new Row(row_a->second->top, top))); 3086ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org row_a->second->top = top; 3096ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org new_row->second->spans = row_a->second->spans; 3106ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } else if (top < row_a->second->top) { 3116ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // If the |top| is above |row_a| then skip the range between |top| and 3126ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // top of |row_a| because it's empty. 3136ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org top = row_a->second->top; 3142edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org if (top >= row_b->second->bottom) { 3152edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org ++row_b; 3162edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org if (row_b != region.rows_.end()) 3172edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org top = row_b->second->top; 3182edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org continue; 3192edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org } 3206ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } 3216ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 3226ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org if (row_b->second->bottom < row_a->second->bottom) { 3236ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // If the bottom of |row_b| falls in the middle of the |row_a| split 3246ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // |row_a| into two, at |top|, and leave |row_a| referring to the upper of 3256ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // the two, ready to subtract spans from. 3266ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org int bottom = row_b->second->bottom; 3276ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org Rows::iterator new_row = 3286ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org rows_.insert(row_a, Rows::value_type(bottom, new Row(top, bottom))); 3296ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org row_a->second->top = bottom; 3306ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org new_row->second->spans = row_a->second->spans; 3316ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org row_a = new_row; 3326ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } 3336ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 3346ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // At this point the vertical range covered by |row_a| lays within the 3356ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // range covered by |row_b|. Subtract |row_b| spans from |row_a|. 3366ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org RowSpanSet new_spans; 3376ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org SubtractRows(row_a->second->spans, row_b->second->spans, &new_spans); 3386ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org new_spans.swap(row_a->second->spans); 3396ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org top = row_a->second->bottom; 3406ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 3416ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org if (top >= row_b->second->bottom) { 3422edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org ++row_b; 3436ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org if (row_b != region.rows_.end()) 3446ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org top = row_b->second->top; 3456ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } 3466ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 3476ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // Check if the row is empty after subtraction and delete it. Otherwise move 3486ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // to the next one. 3496ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org if (row_a->second->spans.empty()) { 3506ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org Rows::iterator row_to_delete = row_a; 3516ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org ++row_a; 3526ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org delete row_to_delete->second; 3536ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org rows_.erase(row_to_delete); 3546ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } else { 3556ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org MergeWithPrecedingRow(row_a); 3562edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org ++row_a; 3576ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } 3586ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } 3596ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 3606ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org if (row_a != rows_.end()) 3616ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org MergeWithPrecedingRow(row_a); 3626ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org} 3636ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 3646ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.orgvoid DesktopRegion::Subtract(const DesktopRect& rect) { 3656ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org DesktopRegion region; 3666ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org region.AddRect(rect); 3676ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org Subtract(region); 3686ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org} 3696ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 37015e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.orgvoid DesktopRegion::Translate(int32_t dx, int32_t dy) { 3713ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows new_rows; 3723ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 3733ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) { 3743ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Row* row = it->second; 3753ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 3763ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row->top += dy; 3773ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row->bottom += dy; 3783ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 3793ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (dx != 0) { 3803ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Translate each span. 3813ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org for (RowSpanSet::iterator span = row->spans.begin(); 3823ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org span != row->spans.end(); ++span) { 3833ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org span->left += dx; 3843ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org span->right += dx; 3853ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 3863ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 3873ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 3883ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (dy != 0) 3893ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org new_rows.insert(new_rows.end(), Rows::value_type(row->bottom, row)); 39015e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org } 3913ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 3923ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (dy != 0) 3933ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org new_rows.swap(rows_); 39415e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org} 39515e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 39615e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.orgvoid DesktopRegion::Swap(DesktopRegion* region) { 3973ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org rows_.swap(region->rows_); 3983ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 3993ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 4003ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org// static 4013ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgbool DesktopRegion::CompareSpanRight(const RowSpan& r, int32_t value) { 4023ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return r.right < value; 4033ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 4043ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 4053ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org// static 4063ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgbool DesktopRegion::CompareSpanLeft(const RowSpan& r, int32_t value) { 4073ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return r.left < value; 4083ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 4093ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 4103ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org// static 4113ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgvoid DesktopRegion::AddSpanToRow(Row* row, int left, int right) { 4123ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // First check if the new span is located to the right of all existing spans. 4133ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // This is an optimization to avoid binary search in the case when rectangles 4143ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // are inserted sequentially from left to right. 4153ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (row->spans.empty() || left > row->spans.back().right) { 4163ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row->spans.push_back(RowSpan(left, right)); 4173ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return; 4183ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 4193ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 4203ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Find the first span that ends at or after |left|. 4213ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org RowSpanSet::iterator start = 4223ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org std::lower_bound(row->spans.begin(), row->spans.end(), left, 4233ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org CompareSpanRight); 4243ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org assert(start < row->spans.end()); 4253ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 4263ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Find the first span that starts after |right|. 4273ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org RowSpanSet::iterator end = 4283ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org std::lower_bound(start, row->spans.end(), right + 1, CompareSpanLeft); 4293ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (end == row->spans.begin()) { 4303ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // There are no overlaps. Just insert the new span at the beginning. 4313ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row->spans.insert(row->spans.begin(), RowSpan(left, right)); 4323ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return; 4333ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 4343ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 4353ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Move end to the left, so that it points the last span that ends at or 4363ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // before |right|. 4373ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org end--; 4383ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 4393ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // At this point [start, end] is the range of spans that intersect with the 4403ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // new one. 4413ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (end < start) { 4423ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // There are no overlaps. Just insert the new span at the correct position. 4433ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row->spans.insert(start, RowSpan(left, right)); 4443ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return; 4453ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 4463ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 4473ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org left = std::min(left, start->left); 4483ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org right = std::max(right, end->right); 4493ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 4503ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Replace range [start, end] with the new span. 4513ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org *start = RowSpan(left, right); 4523ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++start; 4533ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++end; 4543ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (start < end) 4553ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row->spans.erase(start, end); 4563ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 4573ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 4583ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org// static 4593ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgbool DesktopRegion::IsSpanInRow(const Row& row, const RowSpan& span) { 4603ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Find the first span that starts at or after |span.left| and then check if 4613ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // it's the same span. 4623ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org RowSpanSet::const_iterator it = 4633ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org std::lower_bound(row.spans.begin(), row.spans.end(), span.left, 4643ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org CompareSpanLeft); 4653ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return it != row.spans.end() && *it == span; 46615e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org} 46715e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 4686ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org// static 4696ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.orgvoid DesktopRegion::SubtractRows(const RowSpanSet& set_a, 4706ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org const RowSpanSet& set_b, 4716ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org RowSpanSet* output) { 4726ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org assert(!set_a.empty() && !set_b.empty()); 4736ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 4746ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org RowSpanSet::const_iterator it_b = set_b.begin(); 4756ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 4766ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // Iterate over all spans in |set_a| adding parts of it that do not intersect 4776ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // with |set_b| to the |output|. 4786ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org for (RowSpanSet::const_iterator it_a = set_a.begin(); it_a != set_a.end(); 4796ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org ++it_a) { 4806ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // If there is no intersection then append the current span and continue. 4816ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org if (it_b == set_b.end() || it_a->right < it_b->left) { 4826ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org output->push_back(*it_a); 4836ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org continue; 4846ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } 4856ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 4866ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org // Iterate over |set_b| spans that may intersect with |it_a|. 4876ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org int pos = it_a->left; 4886ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org while (it_b != set_b.end() && it_b->left < it_a->right) { 4892edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org if (it_b->left > pos) 4906ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org output->push_back(RowSpan(pos, it_b->left)); 4912edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org if (it_b->right > pos) { 4922edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org pos = it_b->right; 4932edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org if (pos >= it_a->right) 4942edb642810659796968c7a562bfc2ea09d71cfebsergeyu@chromium.org break; 4956ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } 4966ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org ++it_b; 4976ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } 4986ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org if (pos < it_a->right) 4996ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org output->push_back(RowSpan(pos, it_a->right)); 5006ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org } 5016ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org} 5026ab45b9dab4611544c7f281da0d9a68f82621745sergeyu@chromium.org 50315e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.orgDesktopRegion::Iterator::Iterator(const DesktopRegion& region) 50415e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org : region_(region), 5053ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row_(region.rows_.begin()), 5063ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org previous_row_(region.rows_.end()) { 5073ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (!IsAtEnd()) { 5083ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org assert(row_->second->spans.size() > 0); 5093ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row_span_ = row_->second->spans.begin(); 5103ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org UpdateCurrentRect(); 5113ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 51215e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org} 51315e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 514098c1de578e08a67eb1684ede6154e5d6301d624Sergey UlanovDesktopRegion::Iterator::~Iterator() {} 515098c1de578e08a67eb1684ede6154e5d6301d624Sergey Ulanov 51615e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.orgbool DesktopRegion::Iterator::IsAtEnd() const { 5173ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return row_ == region_.rows_.end(); 51815e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org} 51915e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 52015e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.orgvoid DesktopRegion::Iterator::Advance() { 5213ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org assert(!IsAtEnd()); 5223ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 5233ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org while (true) { 5243ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++row_span_; 5253ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (row_span_ == row_->second->spans.end()) { 5263ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org previous_row_ = row_; 5273ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++row_; 5283ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (row_ != region_.rows_.end()) { 5293ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org assert(row_->second->spans.size() > 0); 5303ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row_span_ = row_->second->spans.begin(); 5313ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 5323ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 5333ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 5343ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (IsAtEnd()) 5353ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org return; 5363ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 5373ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // If the same span exists on the previous row then skip it, as we've 5383ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // already returned this span merged into the previous one, via 5393ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // UpdateCurrentRect(). 5403ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org if (previous_row_ != region_.rows_.end() && 5413ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org previous_row_->second->bottom == row_->second->top && 5423ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org IsSpanInRow(*previous_row_->second, *row_span_)) { 5433ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org continue; 5443ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 5453ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 5463ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org break; 5473ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } 5483ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org 5493ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org assert(!IsAtEnd()); 5503ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org UpdateCurrentRect(); 55115e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org} 55215e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 5533ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.orgvoid DesktopRegion::Iterator::UpdateCurrentRect() { 5543ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org // Merge the current rectangle with the matching spans from later rows. 5553ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org int bottom; 5563ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::const_iterator bottom_row = row_; 5573ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org Rows::const_iterator previous; 5583ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org do { 5593ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org bottom = bottom_row->second->bottom; 5603ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org previous = bottom_row; 5613ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org ++bottom_row; 5623ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org } while (bottom_row != region_.rows_.end() && 5633ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org previous->second->bottom == bottom_row->second->top && 5643ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org IsSpanInRow(*bottom_row->second, *row_span_)); 5653ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org rect_ = DesktopRect::MakeLTRB(row_span_->left, row_->second->top, 5663ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org row_span_->right, bottom); 5673ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} 56815e32ccd30992840f6a48c3e52cc979452eb5f0dsergeyu@chromium.org 5693ee13e4ac219338c861a5d08212ffba88001cdb1sergeyu@chromium.org} // namespace webrtc 570