1 // Copyright 2017 The PDFium Authors 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 #include "third_party/base/check.h" 11 12 RangeSet::RangeSet() = default; 13 14 RangeSet::~RangeSet() = default; 15 Contains(const Range & range) const16bool RangeSet::Contains(const Range& range) const { 17 if (IsEmptyRange(range)) 18 return false; 19 20 const Range fixed_range = FixDirection(range); 21 auto it = ranges().upper_bound(fixed_range); 22 23 if (it == ranges().begin()) 24 return false; // No ranges includes range.first. 25 26 --it; // Now it starts equal or before range.first. 27 return it->second >= fixed_range.second; 28 } 29 Union(const Range & range)30void RangeSet::Union(const Range& range) { 31 if (IsEmptyRange(range)) 32 return; 33 34 Range fixed_range = FixDirection(range); 35 if (IsEmpty()) { 36 ranges_.insert(fixed_range); 37 return; 38 } 39 40 auto start = ranges_.upper_bound(fixed_range); 41 if (start != ranges_.begin()) 42 --start; // start now points to the key equal or lower than offset. 43 44 if (start->second < fixed_range.first) 45 ++start; // start element is entirely before current range, skip it. 46 47 auto end = ranges_.upper_bound(Range(fixed_range.second, fixed_range.second)); 48 49 if (start == end) { // No ranges to merge. 50 ranges_.insert(fixed_range); 51 return; 52 } 53 54 --end; 55 56 const size_t new_start = std::min(start->first, fixed_range.first); 57 const size_t new_end = std::max(end->second, fixed_range.second); 58 ranges_.erase(start, ++end); 59 ranges_.insert(Range(new_start, new_end)); 60 } 61 Union(const RangeSet & range_set)62void RangeSet::Union(const RangeSet& range_set) { 63 DCHECK(&range_set != this); 64 for (const auto& it : range_set.ranges()) 65 Union(it); 66 } 67 FixDirection(const Range & range) const68RangeSet::Range RangeSet::FixDirection(const Range& range) const { 69 return range.first <= range.second ? range 70 : Range(range.second + 1, range.first + 1); 71 } 72 IsEmptyRange(const Range & range) const73bool RangeSet::IsEmptyRange(const Range& range) const { 74 return range.first == range.second; 75 } 76