llvm/ADT/IntervalTree.h

//===-- IntervalTree.h ------------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements an interval tree.
//
// Further information:
// https://en.wikipedia.org/wiki/Interval_tree
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_INTERVALTREE_H
#define LLVM_ADT_INTERVALTREE_H

#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>

// IntervalTree is a light tree data structure to hold intervals. It allows
// finding all intervals that overlap with any given point. At this time,
// it does not support any deletion or rebalancing operations.
//
// The IntervalTree is designed to be set up once, and then queried without
// any further additions.
//
// Synopsis:
//   Closed intervals delimited by PointT objects are mapped to ValueT objects.
//
// Restrictions:
//   PointT must be a fundamental type.
//   ValueT must be a fundamental or pointer type.
//
// template <typename PointT, typename ValueT, typename DataT>
// class IntervalTree {
// public:
//
//   IntervalTree();
//   ~IntervalTree():
//
//   using IntervalReferences = SmallVector<IntervalData *>;
//
//   void create();
//   void insert(PointT Left, PointT Right, ValueT Value);
//
//   IntervalReferences getContaining(PointT Point);
//   static void sortIntervals(IntervalReferences &Intervals, Sorting Sort);
//
//   find_iterator begin(PointType Point) const;
//   find_iterator end() const;
//
//   bool empty() const;
//   void clear();
//
//   void print(raw_ostream &OS, bool HexFormat = true);
// };
//
//===----------------------------------------------------------------------===//
//
// In the below given dataset
//
//   [a, b] <- (x)
//
// 'a' and 'b' describe a range and 'x' the value for that interval.
//
// The following data are purely for illustrative purposes:
//
// [30, 35] <- (3035),    [39, 50] <- (3950),    [55, 61] <- (5561),
// [31, 56] <- (3156),    [12, 21] <- (1221),    [25, 41] <- (2541),
// [49, 65] <- (4965),    [71, 79] <- (7179),    [11, 16] <- (1116),
// [20, 30] <- (2030),    [36, 54] <- (3654),    [60, 70] <- (6070),
// [74, 80] <- (7480),    [15, 40] <- (1540),    [43, 43] <- (4343),
// [50, 75] <- (5075),    [10, 85] <- (1085)
//
// The data represents a set of overlapping intervals:
//
//                    30--35  39------------50  55----61
//                      31------------------------56
//     12--------21 25------------41      49-------------65   71-----79
//   11----16  20-----30    36----------------54    60------70  74---- 80
//       15---------------------40  43--43  50--------------------75
// 10----------------------------------------------------------------------85
//
// The items are stored in a binary tree with each node storing:
//
// MP: A middle point.
// IL: All intervals whose left value are completely to the left of the middle
//     point. They are sorted in ascending order by their beginning point.
// IR: All intervals whose right value are completely to the right of the
//     middle point. They are sorted in descending order by their ending point.
// LS: Left subtree.
// RS: Right subtree.
//
// As IL and IR will contain the same intervals, in order to optimize space,
// instead of storing intervals on each node, we use two vectors that will
// contain the intervals described by IL and IR. Each node will contain an
// index into that vector (global bucket), to indicate the beginning of the
// intervals assigned to the node.
//
// The following is the output from print():
//
// 0: MP:43 IR [10,85] [31,56] [36,54] [39,50] [43,43]
// 0: MP:43 IL [10,85] [31,56] [36,54] [39,50] [43,43]
// 1:   MP:25 IR [25,41] [15,40] [20,30]
// 1:   MP:25 IL [15,40] [20,30] [25,41]
// 2:     MP:15 IR [12,21] [11,16]
// 2:     MP:15 IL [11,16] [12,21]
// 2:     MP:36 IR []
// 2:     MP:36 IL []
// 3:       MP:31 IR [30,35]
// 3:       MP:31 IL [30,35]
// 1:   MP:61 IR [50,75] [60,70] [49,65] [55,61]
// 1:   MP:61 IL [49,65] [50,75] [55,61] [60,70]
// 2:     MP:74 IR [74,80] [71,79]
// 2:     MP:74 IL [71,79] [74,80]
//
// with:
//    0: Root Node.
//   MP: Middle point.
//   IL: Intervals to the left (in ascending order by beginning point).
//   IR: Intervals to the right (in descending order by ending point).
//
//                                    Root
//                                      |
//                                      V
//                       +------------MP:43------------+
//                       |            IL IR            |
//                       |       [10,85] [10,85]       |
//                    LS |       [31,56] [31,56]       | RS
//                       |       [36,54] [36,54]       |
//                       |       [39,50] [39,50]       |
//                       |       [43,43] [43,43]       |
//                       V                             V
//        +------------MP:25------------+            MP:61------------+
//        |            IL IR            |            IL IR            |
//        |       [15,40] [25,41]       |       [49,65] [50,75]       |
//     LS |       [20,30] [15,40]       | RS    [50,75] [60,70]       | RS
//        |       [25,41] [20,30]       |       [55,61] [49,65]       |
//        |                             |       [60,70] [55,61]       |
//        V                             V                             V
//      MP:15                 +-------MP:36                         MP:74
//      IL IR                 |       IL IR                         IL IR
// [11,16] [12,21]         LS |       [] []                    [71,79] [74,80]
// [12,21] [11,16]            |                                [74,80] [71,79]
//                            V
//                          MP:31
//                          IL IR
//                     [30,35] [30,35]
//
// The creation of an interval tree is done in 2 steps:
// 1) Insert the interval items by calling
//    void insert(PointT Left, PointT Right, ValueT Value);
//    Left, Right: the interval left and right limits.
//    Value: the data associated with that specific interval.
//
// 2) Create the interval tree by calling
//    void create();
//
// Once the tree is created, it is switched to query mode.
// Query the tree by using iterators or container.
//
// a) Iterators over intervals overlapping the given point with very weak
//    ordering guarantees.
//    find_iterator begin(PointType Point) const;
//    find_iterator end() const;
//    Point: a target point to be tested for inclusion in any interval.
//
// b) Container:
//    IntervalReferences getContaining(PointT Point);
//    Point: a target point to be tested for inclusion in any interval.
//    Returns vector with all the intervals containing the target point.
//
// The returned intervals are in their natural tree location. They can
// be sorted:
//
// static void sortIntervals(IntervalReferences &Intervals, Sorting Sort);
//
// Ability to print the constructed interval tree:
//   void print(raw_ostream &OS, bool HexFormat = true);
// Display the associated data in hexadecimal format.

namespace llvm {

//===----------------------------------------------------------------------===//
//---                          IntervalData                               ----//
//===----------------------------------------------------------------------===//
/// An interval data composed by a \a Left and \a Right points and an
/// associated \a Value.
/// \a PointT corresponds to the interval endpoints type.
/// \a ValueT corresponds to the interval value type.
template <typename PointT, typename ValueT> class IntervalData {
protected:
  using PointType = PointT;
  using ValueType = ValueT;

private:
  PointType Left;
  PointType Right;
  ValueType Value;

public:
  IntervalData() = delete;
  IntervalData(PointType Left, PointType Right, ValueType Value)
      : Left(Left), Right(Right), Value(Value) {
    assert(Left <= Right && "'Left' must be less or equal to 'Right'");
  }
  virtual ~IntervalData() = default;
  PointType left() const { return Left; }
  PointType right() const { return Right; }
  ValueType value() const { return Value; }

  /// Return true if \a Point is inside the left bound of closed interval \a
  /// [Left;Right]. This is Left <= Point for closed intervals.
  bool left(const PointType &Point) const { return left() <= Point; }

  /// Return true if \a Point is inside the right bound of closed interval \a
  /// [Left;Right]. This is Point <= Right for closed intervals.
  bool right(const PointType &Point) const { return Point <= right(); }

  /// Return true when \a Point is contained in interval \a [Left;Right].
  /// This is Left <= Point <= Right for closed intervals.
  bool contains(const PointType &Point) const {
    return left(Point) && right(Point);
  }
};

//===----------------------------------------------------------------------===//
//---                          IntervalTree                               ----//
//===----------------------------------------------------------------------===//
// Helper class template that is used by the IntervalTree to ensure that one
// does instantiate using only fundamental and/or pointer types.
template <typename T>
using PointTypeIsValid = std::bool_constant<std::is_fundamental<T>::value>;

template <typename T>
using ValueTypeIsValid = std::bool_constant<std::is_fundamental<T>::value ||
                                            std::is_pointer<T>::value>;

template <typename PointT, typename ValueT,
          typename DataT = IntervalData<PointT, ValueT>>
class IntervalTree {
  static_assert(PointTypeIsValid<PointT>::value,
                "PointT must be a fundamental type");
  static_assert(ValueTypeIsValid<ValueT>::value,
                "ValueT must be a fundamental or pointer type");

public:
  using PointType = PointT;
  using ValueType = ValueT;
  using DataType = DataT;
  using Allocator = BumpPtrAllocator;

  enum class Sorting { Ascending, Descending };
  using IntervalReferences = SmallVector<const DataType *, 4>;

private:
  using IntervalVector = SmallVector<DataType, 4>;
  using PointsVector = SmallVector<PointType, 4>;

  class IntervalNode {
    PointType MiddlePoint;             // MP - Middle point.
    IntervalNode *Left = nullptr;      // LS - Left subtree.
    IntervalNode *Right = nullptr;     // RS - Right subtree.
    unsigned BucketIntervalsStart = 0; // Starting index in global bucket.
    unsigned BucketIntervalsSize = 0;  // Size of bucket.

  public:
    PointType middle() const { return MiddlePoint; }
    unsigned start() const { return BucketIntervalsStart; }
    unsigned size() const { return BucketIntervalsSize; }

    IntervalNode(PointType Point, unsigned Start)
        : MiddlePoint(Point), BucketIntervalsStart(Start) {}

    friend IntervalTree;
  };

  Allocator &NodeAllocator;     // Allocator used for creating interval nodes.
  IntervalNode *Root = nullptr; // Interval tree root.
  IntervalVector Intervals; // Storage for each interval and all of the fields
                            // point back into it.
  PointsVector EndPoints; // Sorted left and right points of all the intervals.

  // These vectors provide storage that nodes carve buckets of overlapping
  // intervals out of. All intervals are recorded on each vector.
  // The bucket with the intervals associated to a node, is determined by
  // the fields 'BucketIntervalStart' and 'BucketIntervalSize' in the node.
  // The buckets in the first vector are sorted in ascending order using
  // the left value and the buckets in the second vector are sorted in
  // descending order using the right value. Every interval in a bucket
  // contains the middle point for the node.
  IntervalReferences IntervalsLeft;  // Intervals to the left of middle point.
  IntervalReferences IntervalsRight; // Intervals to the right of middle point.

  // Working vector used during the tree creation to sort the intervals. It is
  // cleared once the tree is created.
  IntervalReferences References;

  /// Recursively delete the constructed tree.
  void deleteTree(IntervalNode *Node) {
    if (Node) {
      deleteTree(Node->Left);
      deleteTree(Node->Right);
      Node->~IntervalNode();
      NodeAllocator.Deallocate(Node);
    }
  }

  /// Print the interval list (left and right) for a given \a Node.
  static void printList(raw_ostream &OS, IntervalReferences &IntervalSet,
                        unsigned Start, unsigned Size, bool HexFormat = true) {
    assert(Start + Size <= IntervalSet.size() &&
           "Start + Size must be in bounds of the IntervalSet");
    const char *Format = HexFormat ? "[0x%08x,0x%08x] " : "[%2d,%2d] ";
    if (Size) {
      for (unsigned Position = Start; Position < Start + Size; ++Position)
        OS << format(Format, IntervalSet[Position]->left(),
                     IntervalSet[Position]->right());
    } else {
      OS << "[]";
    }
    OS << "\n";
  }

  /// Print an interval tree \a Node.
  void printNode(raw_ostream &OS, unsigned Level, IntervalNode *Node,
                 bool HexFormat = true) {
    const char *Format = HexFormat ? "MP:0x%08x " : "MP:%2d ";
    auto PrintNodeData = [&](StringRef Text, IntervalReferences &IntervalSet) {
      OS << format("%5d: ", Level);
      OS.indent(Level * 2);
      OS << format(Format, Node->middle()) << Text << " ";
      printList(OS, IntervalSet, Node->start(), Node->size(), HexFormat);
    };

    PrintNodeData("IR", IntervalsRight);
    PrintNodeData("IL", IntervalsLeft);
  }

  /// Recursively print all the interval nodes.
  void printTree(raw_ostream &OS, unsigned Level, IntervalNode *Node,
                 bool HexFormat = true) {
    if (Node) {
      printNode(OS, Level, Node, HexFormat);
      ++Level;
      printTree(OS, Level, Node->Left, HexFormat);
      printTree(OS, Level, Node->Right, HexFormat);
    }
  }

  /// Recursively construct the interval tree.
  /// IntervalsSize: Number of intervals that have been processed and it will
  /// be used as the start for the intervals bucket for a node.
  /// PointsBeginIndex, PointsEndIndex: Determine the range into the EndPoints
  /// vector of end points to be processed.
  /// ReferencesBeginIndex, ReferencesSize: Determine the range into the
  /// intervals being processed.
  IntervalNode *createTree(unsigned &IntervalsSize, int PointsBeginIndex,
                           int PointsEndIndex, int ReferencesBeginIndex,
                           int ReferencesSize) {
    // We start by taking the entire range of all the intervals and dividing
    // it in half at x_middle (in practice, x_middle should be picked to keep
    // the tree relatively balanced).
    // This gives three sets of intervals, those completely to the left of
    // x_middle which we'll call S_left, those completely to the right of
    // x_middle which we'll call S_right, and those overlapping x_middle
    // which we'll call S_middle.
    // The intervals in S_left and S_right are recursively divided in the
    // same manner until there are no intervals remaining.

    if (PointsBeginIndex > PointsEndIndex ||
        ReferencesBeginIndex >= ReferencesSize)
      return nullptr;

    int MiddleIndex = (PointsBeginIndex + PointsEndIndex) / 2;
    PointType MiddlePoint = EndPoints[MiddleIndex];

    unsigned NewBucketStart = IntervalsSize;
    unsigned NewBucketSize = 0;
    int ReferencesRightIndex = ReferencesSize;

    IntervalNode *Root =
        new (NodeAllocator) IntervalNode(MiddlePoint, NewBucketStart);

    // A quicksort implementation where all the intervals that overlap
    // with the pivot are put into the "bucket", and "References" is the
    // partition space where we recursively sort the remaining intervals.
    for (int Index = ReferencesBeginIndex; Index < ReferencesRightIndex;) {

      // Current interval contains the middle point.
      if (References[Index]->contains(MiddlePoint)) {
        IntervalsLeft[IntervalsSize] = References[Index];
        IntervalsRight[IntervalsSize] = References[Index];
        ++IntervalsSize;
        Root->BucketIntervalsSize = ++NewBucketSize;

        if (Index < --ReferencesRightIndex)
          std::swap(References[Index], References[ReferencesRightIndex]);
        if (ReferencesRightIndex < --ReferencesSize)
          std::swap(References[ReferencesRightIndex],
                    References[ReferencesSize]);
        continue;
      }

      if (References[Index]->left() > MiddlePoint) {
        if (Index < --ReferencesRightIndex)
          std::swap(References[Index], References[ReferencesRightIndex]);
        continue;
      }
      ++Index;
    }

    // Sort intervals on the left and right of the middle point.
    if (NewBucketSize > 1) {
      // Sort the intervals in ascending order by their beginning point.
      std::stable_sort(IntervalsLeft.begin() + NewBucketStart,
                       IntervalsLeft.begin() + NewBucketStart + NewBucketSize,
                       [](const DataType *LHS, const DataType *RHS) {
                         return LHS->left() < RHS->left();
                       });
      // Sort the intervals in descending order by their ending point.
      std::stable_sort(IntervalsRight.begin() + NewBucketStart,
                       IntervalsRight.begin() + NewBucketStart + NewBucketSize,
                       [](const DataType *LHS, const DataType *RHS) {
                         return LHS->right() > RHS->right();
                       });
    }

    if (PointsBeginIndex <= MiddleIndex - 1) {
      Root->Left = createTree(IntervalsSize, PointsBeginIndex, MiddleIndex - 1,
                              ReferencesBeginIndex, ReferencesRightIndex);
    }

    if (MiddleIndex + 1 <= PointsEndIndex) {
      Root->Right = createTree(IntervalsSize, MiddleIndex + 1, PointsEndIndex,
                               ReferencesRightIndex, ReferencesSize);
    }

    return Root;
  }

public:
  class find_iterator {
  public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = DataType;
    using difference_type = DataType;
    using pointer = DataType *;
    using reference = DataType &;

  private:
    const IntervalReferences *AscendingBuckets = nullptr;
    const IntervalReferences *DescendingBuckets = nullptr;

    // Current node and index while traversing the intervals that contain
    // the reference point.
    IntervalNode *Node = nullptr;
    PointType Point = {};
    unsigned Index = 0;

    // For the current node, check if we have intervals that contain the
    // reference point. We return when the node does have intervals that
    // contain such point. Otherwise we keep descending on that branch.
    void initNode() {
      Index = 0;
      while (Node) {
        // Return if the reference point is the same as the middle point or
        // the current node doesn't have any intervals at all.
        if (Point == Node->middle()) {
          if (Node->size() == 0) {
            // No intervals that contain the reference point.
            Node = nullptr;
          }
          return;
        }

        if (Point < Node->middle()) {
          // The reference point can be at the left or right of the middle
          // point. Return if the current node has intervals that contain the
          // reference point; otherwise descend on the respective branch.
          if (Node->size() && (*AscendingBuckets)[Node->start()]->left(Point)) {
            return;
          }
          Node = Node->Left;
        } else {
          if (Node->size() &&
              (*DescendingBuckets)[Node->start()]->right(Point)) {
            return;
          }
          Node = Node->Right;
        }
      }
    }

    // Given the current node (which was initialized by initNode), move to
    // the next interval in the list of intervals that contain the reference
    // point. Otherwise move to the next node, as the intervals contained
    // in that node, can contain the reference point.
    void nextInterval() {
      // If there are available intervals that contain the reference point,
      // traverse them; otherwise move to the left or right node, depending
      // on the middle point value.
      if (++Index < Node->size()) {
        if (Node->middle() == Point)
          return;
        if (Point < Node->middle()) {
          // Reference point is on the left.
          if (!(*AscendingBuckets)[Node->start() + Index]->left(Point)) {
            // The intervals don't contain the reference point. Move to the
            // next node, preserving the descending order.
            Node = Node->Left;
            initNode();
          }
        } else {
          // Reference point is on the right.
          if (!(*DescendingBuckets)[Node->start() + Index]->right(Point)) {
            // The intervals don't contain the reference point. Move to the
            // next node, preserving the ascending order.
            Node = Node->Right;
            initNode();
          }
        }
      } else {
        // We have traversed all the intervals in the current node.
        if (Point == Node->middle()) {
          Node = nullptr;
          Index = 0;
          return;
        }
        // Select a branch based on the middle point.
        Node = Point < Node->middle() ? Node->Left : Node->Right;
        initNode();
      }
    }

    find_iterator() = default;
    explicit find_iterator(const IntervalReferences *Left,
                           const IntervalReferences *Right, IntervalNode *Node,
                           PointType Point)
        : AscendingBuckets(Left), DescendingBuckets(Right), Node(Node),
          Point(Point), Index(0) {
      initNode();
    }

    const DataType *current() const {
      return (Point <= Node->middle())
                 ? (*AscendingBuckets)[Node->start() + Index]
                 : (*DescendingBuckets)[Node->start() + Index];
    }

  public:
    find_iterator &operator++() {
      nextInterval();
      return *this;
    }

    find_iterator operator++(int) {
      find_iterator Iter(*this);
      nextInterval();
      return Iter;
    }

    /// Dereference operators.
    const DataType *operator->() const { return current(); }
    const DataType &operator*() const { return *(current()); }

    /// Comparison operators.
    friend bool operator==(const find_iterator &LHS, const find_iterator &RHS) {
      return (!LHS.Node && !RHS.Node && !LHS.Index && !RHS.Index) ||
             (LHS.Point == RHS.Point && LHS.Node == RHS.Node &&
              LHS.Index == RHS.Index);
    }
    friend bool operator!=(const find_iterator &LHS, const find_iterator &RHS) {
      return !(LHS == RHS);
    }

    friend IntervalTree;
  };

private:
  find_iterator End;

public:
  explicit IntervalTree(Allocator &NodeAllocator)
      : NodeAllocator(NodeAllocator) {}
  ~IntervalTree() { clear(); }

  /// Return true when no intervals are mapped.
  bool empty() const { return Root == nullptr; }

  /// Remove all entries.
  void clear() {
    deleteTree(Root);
    Root = nullptr;
    Intervals.clear();
    IntervalsLeft.clear();
    IntervalsRight.clear();
    EndPoints.clear();
  }

  /// Add a mapping of [Left;Right] to \a Value.
  void insert(PointType Left, PointType Right, ValueType Value) {
    assert(empty() && "Invalid insertion. Interval tree already constructed.");
    Intervals.emplace_back(Left, Right, Value);
  }

  /// Return all the intervals in their natural tree location, that
  /// contain the given point.
  IntervalReferences getContaining(PointType Point) const {
    assert(!empty() && "Interval tree it is not constructed.");
    IntervalReferences IntervalSet;
    for (find_iterator Iter = find(Point), E = find_end(); Iter != E; ++Iter)
      IntervalSet.push_back(const_cast<DataType *>(&(*Iter)));
    return IntervalSet;
  }

  /// Sort the given intervals using the following sort options:
  /// Ascending: return the intervals with the smallest at the front.
  /// Descending: return the intervals with the biggest at the front.
  static void sortIntervals(IntervalReferences &IntervalSet, Sorting Sort) {
    std::stable_sort(IntervalSet.begin(), IntervalSet.end(),
                     [Sort](const DataType *RHS, const DataType *LHS) {
                       return Sort == Sorting::Ascending
                                  ? (LHS->right() - LHS->left()) >
                                        (RHS->right() - RHS->left())
                                  : (LHS->right() - LHS->left()) <
                                        (RHS->right() - RHS->left());
                     });
  }

  /// Print the interval tree.
  /// When \a HexFormat is true, the interval tree interval ranges and
  /// associated values are printed in hexadecimal format.
  void print(raw_ostream &OS, bool HexFormat = true) {
    printTree(OS, 0, Root, HexFormat);
  }

  /// Create the interval tree.
  void create() {
    assert(empty() && "Interval tree already constructed.");
    // Sorted vector of unique end points values of all the intervals.
    // Records references to the collected intervals.
    SmallVector<PointType, 4> Points;
    for (const DataType &Data : Intervals) {
      Points.push_back(Data.left());
      Points.push_back(Data.right());
      References.push_back(std::addressof(Data));
    }
    std::stable_sort(Points.begin(), Points.end());
    auto Last = std::unique(Points.begin(), Points.end());
    Points.erase(Last, Points.end());

    EndPoints.assign(Points.begin(), Points.end());

    IntervalsLeft.resize(Intervals.size());
    IntervalsRight.resize(Intervals.size());

    // Given a set of n intervals, construct a data structure so that
    // we can efficiently retrieve all intervals overlapping another
    // interval or point.
    unsigned IntervalsSize = 0;
    Root =
        createTree(IntervalsSize, /*PointsBeginIndex=*/0, EndPoints.size() - 1,
                   /*ReferencesBeginIndex=*/0, References.size());

    // Save to clear this storage, as it used only to sort the intervals.
    References.clear();
  }

  /// Iterator to start a find operation; it returns find_end() if the
  /// tree has not been built.
  /// There is no support to iterate over all the elements of the tree.
  find_iterator find(PointType Point) const {
    return empty()
               ? find_end()
               : find_iterator(&IntervalsLeft, &IntervalsRight, Root, Point);
  }

  /// Iterator to end find operation.
  find_iterator find_end() const { return End; }
};

} // namespace llvm

#endif // LLVM_ADT_INTERVALTREE_H