|
121
|
1 //=== llvm/unittest/ADT/BreadthFirstIteratorTest.cpp - BFS iterator tests -===//
|
|
|
2 //
|
|
147
|
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
|
4 // See https://llvm.org/LICENSE.txt for license information.
|
|
|
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
121
|
6 //
|
|
|
7 //===----------------------------------------------------------------------===//
|
|
|
8
|
|
|
9 #include "llvm/ADT/BreadthFirstIterator.h"
|
|
|
10 #include "TestGraph.h"
|
|
|
11 #include "gtest/gtest.h"
|
|
|
12
|
|
|
13 using namespace llvm;
|
|
|
14
|
|
|
15 namespace llvm {
|
|
|
16
|
|
|
17 TEST(BreadthFristIteratorTest, Basic) {
|
|
|
18 typedef bf_iterator<Graph<4>> BFIter;
|
|
|
19
|
|
|
20 Graph<4> G;
|
|
|
21 G.AddEdge(0, 1);
|
|
|
22 G.AddEdge(0, 2);
|
|
|
23 G.AddEdge(1, 3);
|
|
|
24
|
|
|
25 auto It = BFIter::begin(G);
|
|
|
26 auto End = BFIter::end(G);
|
|
|
27 EXPECT_EQ(It.getLevel(), 0U);
|
|
|
28 EXPECT_EQ(*It, G.AccessNode(0));
|
|
|
29 ++It;
|
|
|
30 EXPECT_EQ(It.getLevel(), 1U);
|
|
|
31 EXPECT_EQ(*It, G.AccessNode(1));
|
|
|
32 ++It;
|
|
|
33 EXPECT_EQ(It.getLevel(), 1U);
|
|
|
34 EXPECT_EQ(*It, G.AccessNode(2));
|
|
|
35 ++It;
|
|
|
36 EXPECT_EQ(It.getLevel(), 2U);
|
|
|
37 EXPECT_EQ(*It, G.AccessNode(3));
|
|
|
38 ++It;
|
|
|
39 EXPECT_EQ(It, End);
|
|
|
40 }
|
|
|
41
|
|
|
42 TEST(BreadthFristIteratorTest, Cycle) {
|
|
|
43 typedef bf_iterator<Graph<4>> BFIter;
|
|
|
44
|
|
|
45 Graph<4> G;
|
|
|
46 G.AddEdge(0, 1);
|
|
|
47 G.AddEdge(1, 0);
|
|
|
48 G.AddEdge(1, 2);
|
|
|
49 G.AddEdge(2, 1);
|
|
|
50 G.AddEdge(2, 1);
|
|
|
51 G.AddEdge(2, 3);
|
|
|
52 G.AddEdge(3, 2);
|
|
|
53 G.AddEdge(3, 1);
|
|
|
54 G.AddEdge(3, 0);
|
|
|
55
|
|
|
56 auto It = BFIter::begin(G);
|
|
|
57 auto End = BFIter::end(G);
|
|
|
58 EXPECT_EQ(It.getLevel(), 0U);
|
|
|
59 EXPECT_EQ(*It, G.AccessNode(0));
|
|
|
60 ++It;
|
|
|
61 EXPECT_EQ(It.getLevel(), 1U);
|
|
|
62 EXPECT_EQ(*It, G.AccessNode(1));
|
|
|
63 ++It;
|
|
|
64 EXPECT_EQ(It.getLevel(), 2U);
|
|
|
65 EXPECT_EQ(*It, G.AccessNode(2));
|
|
|
66 ++It;
|
|
|
67 EXPECT_EQ(It.getLevel(), 3U);
|
|
|
68 EXPECT_EQ(*It, G.AccessNode(3));
|
|
|
69 ++It;
|
|
|
70 EXPECT_EQ(It, End);
|
|
|
71 }
|
|
|
72
|
|
|
73 } // end namespace llvm
|
