llvm/llvm/unittests/ADT/IntervalTreeTest.cpp

//===---- ADT/IntervalTreeTest.cpp - IntervalTree unit tests --------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/IntervalTree.h"
#include "gtest/gtest.h"

// The test cases for the IntervalTree implementation, follow the below steps:
// a) Insert a series of intervals with their associated mapped value.
// b) Create the interval tree.
// c) Query for specific interval point, covering points inside and outside
//    of any given intervals.
// d) Traversal for specific interval point, using the iterators.
//
// When querying for a set of intervals containing a given value, the query is
// done three times, by calling:
// 1) Intervals = getContaining(...).
// 2) Intervals = getContaining(...).
//    sortIntervals(Intervals, Sorting=Ascending).
// 3) Intervals = getContaining(...).
//    sortIntervals(Intervals, Sorting=Ascending).
//
// The returned intervals are:
// 1) In their location order within the tree.
// 2) Smaller intervals first.
// 3) Bigger intervals first.

usingnamespacellvm;

namespace {

// Helper function to test a specific item or iterator.
template <typename TPoint, typename TItem, typename TValue>
void checkItem(TPoint Point, TItem Item, TPoint Left, TPoint Right,
               TValue Value) { … }

// User class tree tests.
TEST(IntervalTreeTest, UserClass) { … }

UUPoint; // Interval endpoint type.
UUValue; // Mapped value type.

UUTree;
UUReferences;
UUData;
UUSorting;
UUPoint;
UUValue;
UUIter;
UUAlloc;

void checkData(UUPoint Point, const UUData *Data, UUPoint Left, UUPoint Right,
               UUValue Value) { … }

void checkData(UUPoint Point, UUIter Iter, UUPoint Left, UUPoint Right,
               UUValue Value) { … }

// Empty tree tests.
TEST(IntervalTreeTest, NoIntervals) { … }

// One item tree tests.
TEST(IntervalTreeTest, OneInterval) { … }

// Two items tree tests. No overlapping.
TEST(IntervalTreeTest, TwoIntervals) { … }

// Three items tree tests. No overlapping.
TEST(IntervalTreeTest, ThreeIntervals) { … }

// One item tree tests.
TEST(IntervalTreeTest, EmptyIntervals) { … }

// Simple overlapping tests.
TEST(IntervalTreeTest, SimpleIntervalsOverlapping) { … }

// Complex Overlapping.
TEST(IntervalTreeTest, ComplexIntervalsOverlapping) { … }

// Four items tree tests. Overlapping. Check mapped values and iterators.
TEST(IntervalTreeTest, MappedValuesIteratorsTree) { … }

} // namespace