Function VerifyFindIntersectingInterval

be/src/kudu/util/interval_tree-test.cc:219–265

Verify that IntervalTree::FindIntersectingInterval yields the same results as the naive brute-force O(n) algorithm.

// Verify that IntervalTree::FindIntersectingInterval yields the same results as the naive
// brute-force O(n) algorithm.
static void VerifyFindIntersectingInterval(const vector<IntInterval>& all_intervals,
                                           const IntervalTree<IntTraits>& tree,
                                           const IntInterval& query_interval) {
  const auto& Process = [&] (const optional<int>& lower,
                             const optional<int>& upper) {
    vector<IntInterval> results;
    tree.FindIntersectingInterval(lower, upper, &results);
    std::sort(results.begin(), results.end(), CompareIntervals);

    vector<IntInterval> brute_force;
    FindIntersectingBruteForce(all_intervals, lower, upper, &brute_force);
    std::sort(brute_force.begin(), brute_force.end(), CompareIntervals);
    EXPECT_EQ(Stringify(brute_force), Stringify(results));
  };

  {
    // [lower, upper)
    optional<int> lower = query_interval.left;
    optional<int> upper = query_interval.right;
    SCOPED_TRACE(Stringify(all_intervals) + StringPrintf(" {q=[%d, %d)}", *lower, *upper));
    Process(lower, upper);
  }

  {
    // [-OO, upper)
    optional<int> lower = nullopt;
    optional<int> upper = query_interval.right;
    SCOPED_TRACE(Stringify(all_intervals) + StringPrintf(" {q=[-OO, %d)}", *upper));
    Process(lower, upper);
  }

  {
    // [lower, +OO)
    optional<int> lower = query_interval.left;
    optional<int> upper = nullopt;
    SCOPED_TRACE(Stringify(all_intervals) + StringPrintf(" {q=[%d, +OO)}", *lower));
    Process(lower, upper);
  }

  {
    // [-OO, +OO)
    optional<int> lower = query_interval.left;
    optional<int> upper = nullopt;
    SCOPED_TRACE(Stringify(all_intervals) + StringPrintf(" {q=[-OO, +OO)}"));
    Process(lower, upper);
  }
}

static vector<IntInterval> CreateRandomIntervals(int n = 100) {
  vector<IntInterval> intervals;