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
13using namespace llvm;
14
15namespace llvm {
16
17TEST(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
42TEST(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
73static_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

source code of llvm/unittests/ADT/BreadthFirstIteratorTest.cpp