|
121
|
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
|
|
|
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
|
|
|
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
|
