1 //===- llvm/unittest/ADT/DeltaAlgorithmTest.cpp ---------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "gtest/gtest.h"
11 #include "llvm/ADT/DeltaAlgorithm.h"
16 std::ostream &operator<<(std::ostream &OS,
17 const std::set<unsigned> &S) {
19 for (std::set<unsigned>::const_iterator it = S.begin(),
20 ie = S.end(); it != ie; ++it) {
31 class FixedDeltaAlgorithm : public DeltaAlgorithm {
32 changeset_ty FailingSet;
36 virtual bool ExecuteOneTest(const changeset_ty &Changes) {
38 return std::includes(Changes.begin(), Changes.end(),
39 FailingSet.begin(), FailingSet.end());
43 FixedDeltaAlgorithm(const changeset_ty &_FailingSet)
44 : FailingSet(_FailingSet),
47 unsigned getNumTests() const { return NumTests; }
50 std::set<unsigned> fixed_set(unsigned N, ...) {
54 for (unsigned i = 0; i != N; ++i)
55 S.insert(va_arg(ap, unsigned));
60 std::set<unsigned> range(unsigned Start, unsigned End) {
67 std::set<unsigned> range(unsigned N) {
71 TEST(DeltaAlgorithmTest, Basic) {
73 // [0, 20) should minimize to {3,5,7} in a reasonable number of tests.
74 std::set<unsigned> Fails = fixed_set(3, 3, 5, 7);
75 FixedDeltaAlgorithm FDA(Fails);
76 EXPECT_EQ(fixed_set(3, 3, 5, 7), FDA.Run(range(20)));
77 EXPECT_GE(33U, FDA.getNumTests());
80 // [10, 20) should minimize to [10,20)
81 EXPECT_EQ(range(10,20), FDA.Run(range(10,20)));
84 // [0, 4) should minimize to [0,4) in 11 tests.
87 // {0}, {1}, {2}, {3},
88 // {1, 2, 3}, {0, 2, 3}, {0, 1, 3}, {0, 1, 2},
90 FDA = FixedDeltaAlgorithm(range(10));
91 EXPECT_EQ(range(4), FDA.Run(range(4)));
92 EXPECT_EQ(11U, FDA.getNumTests());