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
75