1 // Copyright 2017 PDFium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "testing/range_set.h" 6 7 #include <algorithm> 8 9 #include "core/fxcrt/fx_system.h" 10 11 RangeSet::RangeSet() {} 12 RangeSet::~RangeSet() {} 13 14 bool RangeSet::Contains(const Range& range) const { 15 if (IsEmptyRange(range)) 16 return false; 17 18 const Range fixed_range = FixDirection(range); 19 auto it = ranges().upper_bound(fixed_range); 20 21 if (it == ranges().begin()) 22 return false; // No ranges includes range.first. 23 24 --it; // Now it starts equal or before range.first. 25 return it->second >= fixed_range.second; 26 } 27 28 void RangeSet::Union(const Range& range) { 29 if (IsEmptyRange(range)) 30 return; 31 32 Range fixed_range = FixDirection(range); 33 if (IsEmpty()) { 34 ranges_.insert(fixed_range); 35 return; 36 } 37 38 auto start = ranges_.upper_bound(fixed_range); 39 if (start != ranges_.begin()) 40 --start; // start now points to the key equal or lower than offset. 41 42 if (start->second < fixed_range.first) 43 ++start; // start element is entirely before current range, skip it. 44 45 auto end = ranges_.upper_bound(Range(fixed_range.second, fixed_range.second)); 46 47 if (start == end) { // No ranges to merge. 48 ranges_.insert(fixed_range); 49 return; 50 } 51 52 --end; 53 54 const int new_start = std::min<size_t>(start->first, fixed_range.first); 55 const int new_end = std::max(end->second, fixed_range.second); 56 57 ranges_.erase(start, ++end); 58 ranges_.insert(Range(new_start, new_end)); 59 } 60 61 void RangeSet::Union(const RangeSet& range_set) { 62 ASSERT(&range_set != this); 63 for (const auto& it : range_set.ranges()) 64 Union(it); 65 } 66 67 RangeSet::Range RangeSet::FixDirection(const Range& range) const { 68 return range.first <= range.second ? range 69 : Range(range.second + 1, range.first + 1); 70 } 71 72 bool RangeSet::IsEmptyRange(const Range& range) const { 73 return range.first == range.second; 74 } 75
