range_set.cpp

Go to the documentation of this file.

// Copyright 2017 The PDFium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
 
#include "testing/range_set.h"
 
#include <algorithm>
 
#include "core/fxcrt/check.h"
#include "core/fxcrt/fx_system.h"
 
RangeSet::RangeSet() = default;
 
RangeSet::~RangeSet() = default;
 
bool RangeSet::Contains(const Range& range) const {
  if (IsEmptyRange(range))
    return false;
 
  const Range fixed_range = FixDirection(range);
  auto it = ranges().upper_bound(fixed_range);
 
  if (it == ranges().begin())
    return false;  // No ranges includes range.first.
 
  --it;  // Now it starts equal or before range.first.
  return it->second >= fixed_range.second;
}
 
void RangeSet::Union(const Range& range) {
  if (IsEmptyRange(range))
    return;
 
  Range fixed_range = FixDirection(range);
  if (IsEmpty()) {
    ranges_.insert(fixed_range);
    return;
  }
 
  auto start = ranges_.upper_bound(fixed_range);
  if (start != ranges_.begin())
    --start;  // start now points to the key equal or lower than offset.
 
  if (start->second < fixed_range.first)
    ++start;  // start element is entirely before current range, skip it.
 
  auto end = ranges_.upper_bound(Range(fixed_range.second, fixed_range.second));
 
  if (start == end) {  // No ranges to merge.
    ranges_.insert(fixed_range);
    return;
  }
 
  --end;
 
  const size_t new_start = std::min(start->first, fixed_range.first);
  const size_t new_end = std::max(end->second, fixed_range.second);
  ranges_.erase(start, ++end);
  ranges_.insert(Range(new_start, new_end));
}
 
void RangeSet::Union(const RangeSet& range_set) {
  DCHECK(&range_set != this);
  for (const auto& it : range_set.ranges())
    Union(it);
}
 
RangeSet::Range RangeSet::FixDirection(const Range& range) const {
  return range.first <= range.second ? range
                                     : Range(range.second + 1, range.first + 1);
}
 
bool RangeSet::IsEmptyRange(const Range& range) const {
  return range.first == range.second;
}