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 
RangeSet()11 RangeSet::RangeSet() {}
~RangeSet()12 RangeSet::~RangeSet() {}
13 
Contains(const Range & range) const14 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 
Union(const Range & range)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 
Union(const RangeSet & range_set)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 
FixDirection(const Range & range) const67 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 
IsEmptyRange(const Range & range) const72 bool RangeSet::IsEmptyRange(const Range& range) const {
73   return range.first == range.second;
74 }
75