1 //=== llvm/unittest/ADT/BreadthFirstIteratorTest.cpp - BFS iterator tests -===//
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 "llvm/ADT/BreadthFirstIterator.h"
11 #include "TestGraph.h"
12 #include "gtest/gtest.h"
13
14 using namespace llvm;
15
16 namespace llvm {
17
TEST(BreadthFristIteratorTest,Basic)18 TEST(BreadthFristIteratorTest, Basic) {
19 typedef bf_iterator<Graph<4>> BFIter;
20
21 Graph<4> G;
22 G.AddEdge(0, 1);
23 G.AddEdge(0, 2);
24 G.AddEdge(1, 3);
25
26 auto It = BFIter::begin(G);
27 auto End = BFIter::end(G);
28 EXPECT_EQ(It.getLevel(), 0U);
29 EXPECT_EQ(*It, G.AccessNode(0));
30 ++It;
31 EXPECT_EQ(It.getLevel(), 1U);
32 EXPECT_EQ(*It, G.AccessNode(1));
33 ++It;
34 EXPECT_EQ(It.getLevel(), 1U);
35 EXPECT_EQ(*It, G.AccessNode(2));
36 ++It;
37 EXPECT_EQ(It.getLevel(), 2U);
38 EXPECT_EQ(*It, G.AccessNode(3));
39 ++It;
40 EXPECT_EQ(It, End);
41 }
42
TEST(BreadthFristIteratorTest,Cycle)43 TEST(BreadthFristIteratorTest, Cycle) {
44 typedef bf_iterator<Graph<4>> BFIter;
45
46 Graph<4> G;
47 G.AddEdge(0, 1);
48 G.AddEdge(1, 0);
49 G.AddEdge(1, 2);
50 G.AddEdge(2, 1);
51 G.AddEdge(2, 1);
52 G.AddEdge(2, 3);
53 G.AddEdge(3, 2);
54 G.AddEdge(3, 1);
55 G.AddEdge(3, 0);
56
57 auto It = BFIter::begin(G);
58 auto End = BFIter::end(G);
59 EXPECT_EQ(It.getLevel(), 0U);
60 EXPECT_EQ(*It, G.AccessNode(0));
61 ++It;
62 EXPECT_EQ(It.getLevel(), 1U);
63 EXPECT_EQ(*It, G.AccessNode(1));
64 ++It;
65 EXPECT_EQ(It.getLevel(), 2U);
66 EXPECT_EQ(*It, G.AccessNode(2));
67 ++It;
68 EXPECT_EQ(It.getLevel(), 3U);
69 EXPECT_EQ(*It, G.AccessNode(3));
70 ++It;
71 EXPECT_EQ(It, End);
72 }
73
74 } // end namespace llvm
75