1 | //=== llvm/unittest/ADT/BreadthFirstIteratorTest.cpp - BFS iterator tests -===// |
2 | // |
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 |
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(FromIdx: 0, ToIdx: 1); |
22 | G.AddEdge(FromIdx: 0, ToIdx: 2); |
23 | G.AddEdge(FromIdx: 1, ToIdx: 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(FromIdx: 0, ToIdx: 1); |
47 | G.AddEdge(FromIdx: 1, ToIdx: 0); |
48 | G.AddEdge(FromIdx: 1, ToIdx: 2); |
49 | G.AddEdge(FromIdx: 2, ToIdx: 1); |
50 | G.AddEdge(FromIdx: 2, ToIdx: 1); |
51 | G.AddEdge(FromIdx: 2, ToIdx: 3); |
52 | G.AddEdge(FromIdx: 3, ToIdx: 2); |
53 | G.AddEdge(FromIdx: 3, ToIdx: 1); |
54 | G.AddEdge(FromIdx: 3, ToIdx: 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 | static_assert( |
74 | std::is_convertible_v<decltype(*std::declval<bf_iterator<Graph<3>>>()), |
75 | typename bf_iterator<Graph<3>>::reference>); |
76 | |
77 | } // end namespace llvm |
78 | |