be/src/kudu/util/sorted_disjoint_interval_list.h

// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.

#pragma once

#include <algorithm>
#include <cstdint>
#include <utility>
#include <vector>

#include <glog/logging.h>

#include "kudu/gutil/strings/substitute.h"
#include "kudu/util/status.h"

namespace kudu {

// Constructs a sorted disjoint interval list in-place given a list of intervals.
// The result is written back to the given 'intervals'.
//
// Returns an error if the list contains any invalid intervals.
//
// Sorted disjoint interval list is a data structure holding a group of sorted
// non-overlapping ranges. The operation to construct such one is O(nlg n + n)
// where 'n' is the number of intervals.
//
// For example, given the input interval list:
//
//   [------2-------)         [-----1-----)
//       [--3--)    [---5--)    [----4----)
//
// The output sorted disjoint interval list:
//
//   [----------1----------)  [-----2-----)
//
//
// This method assumes that all intervals are "half-open" intervals -- the
// intervals are inclusive of their start point and exclusive of end point,
// e.g., [3, 6). Note that interval with the same start and end point is
// considered to be valid in this implementation.
// It also assumes 'PointType' has a proper defined comparator.
template<typename PointType>
Status CoalesceIntervals(std::vector<std::pair<PointType, PointType>>* intervals) {
  if (intervals->empty()) return Status::OK();

  // Sort the intervals to prepare for coalescing overlapped ranges.
  for (const auto& interval : *intervals) {
    if (interval.first > interval.second) {
      return Status::InvalidArgument(strings::Substitute("invalid interval: [$0, $1)",
                                                         interval.first,
                                                         interval.second));
    }
  }
  std::sort(intervals->begin(), intervals->end());

  // Traverse the intervals to coalesce overlapped intervals. During the process,
  // uses 'head', 'tail' to track the start and end point of the current disjoint
  // interval.
  auto head = intervals->begin();
  auto tail = head;
  while (++tail != intervals->end()) {
    // If interval 'head' and 'tail' overlap with each other, coalesce them and move
    // to next. Otherwise, the two intervals are disjoint.
    if (head->second >= tail->first) {
      if (tail->second > head->second) head->second = std::move(tail->second);
    } else {
      // The two intervals are disjoint. If the 'head' previously already coalesced
      // some intervals, 'head' and 'tail' will not be adjacent. If so, move 'tail'
      // to the next 'head' to make sure we do not include any of the previously-coalesced
      // intervals.
      ++head;
      if (head != tail) *head = std::move(*tail);
    }
  }

  // Truncate the rest useless elements, if any.
  intervals->erase(++head, tail);
  return Status::OK();
}

} // namespace kudu