1//===- llvm/unittest/ADT/DeltaAlgorithmTest.cpp ---------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "gtest/gtest.h"
11#include "llvm/ADT/DeltaAlgorithm.h"
12#include <algorithm>
13#include <cstdarg>
14using namespace llvm;
15
16namespace std {
17
18std::ostream &operator<<(std::ostream &OS,
19                         const std::set<unsigned> &S) {
20  OS << "{";
21  for (std::set<unsigned>::const_iterator it = S.begin(),
22         ie = S.end(); it != ie; ++it) {
23    if (it != S.begin())
24      OS << ",";
25    OS << *it;
26  }
27  OS << "}";
28  return OS;
29}
30
31}
32
33namespace {
34
35class FixedDeltaAlgorithm : public DeltaAlgorithm {
36  changeset_ty FailingSet;
37  unsigned NumTests;
38
39protected:
40  virtual bool ExecuteOneTest(const changeset_ty &Changes) {
41    ++NumTests;
42    return std::includes(Changes.begin(), Changes.end(),
43                         FailingSet.begin(), FailingSet.end());
44  }
45
46public:
47  FixedDeltaAlgorithm(const changeset_ty &_FailingSet)
48    : FailingSet(_FailingSet),
49      NumTests(0) {}
50
51  unsigned getNumTests() const { return NumTests; }
52};
53
54std::set<unsigned> fixed_set(unsigned N, ...) {
55  std::set<unsigned> S;
56  va_list ap;
57  va_start(ap, N);
58  for (unsigned i = 0; i != N; ++i)
59    S.insert(va_arg(ap, unsigned));
60  va_end(ap);
61  return S;
62}
63
64std::set<unsigned> range(unsigned Start, unsigned End) {
65  std::set<unsigned> S;
66  while (Start != End)
67    S.insert(Start++);
68  return S;
69}
70
71std::set<unsigned> range(unsigned N) {
72  return range(0, N);
73}
74
75TEST(DeltaAlgorithmTest, Basic) {
76  // P = {3,5,7} \in S
77  //   [0, 20) should minimize to {3,5,7} in a reasonable number of tests.
78  std::set<unsigned> Fails = fixed_set(3, 3, 5, 7);
79  FixedDeltaAlgorithm FDA(Fails);
80  EXPECT_EQ(fixed_set(3, 3, 5, 7), FDA.Run(range(20)));
81  EXPECT_GE(33U, FDA.getNumTests());
82
83  // P = {3,5,7} \in S
84  //   [10, 20) should minimize to [10,20)
85  EXPECT_EQ(range(10,20), FDA.Run(range(10,20)));
86
87  // P = [0,4) \in S
88  //   [0, 4) should minimize to [0,4) in 11 tests.
89  //
90  // 11 = |{ {},
91  //         {0}, {1}, {2}, {3},
92  //         {1, 2, 3}, {0, 2, 3}, {0, 1, 3}, {0, 1, 2},
93  //         {0, 1}, {2, 3} }|
94  FDA = FixedDeltaAlgorithm(range(10));
95  EXPECT_EQ(range(4), FDA.Run(range(4)));
96  EXPECT_EQ(11U, FDA.getNumTests());
97}
98
99}
100
101