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 #include <array> 14 #include <iterator> 15 #include <type_traits> 16 17 #include <cstddef> 18 19 using namespace llvm; 20 21 namespace llvm { 22 23 TEST(BreadthFristIteratorTest, Basic) { 24 typedef bf_iterator<Graph<4>> BFIter; 25 26 Graph<4> G; 27 G.AddEdge(0, 1); 28 G.AddEdge(0, 2); 29 G.AddEdge(1, 3); 30 31 auto It = BFIter::begin(G); 32 auto End = BFIter::end(G); 33 EXPECT_EQ(It.getLevel(), 0U); 34 EXPECT_EQ(*It, G.AccessNode(0)); 35 ++It; 36 EXPECT_EQ(It.getLevel(), 1U); 37 EXPECT_EQ(*It, G.AccessNode(1)); 38 ++It; 39 EXPECT_EQ(It.getLevel(), 1U); 40 EXPECT_EQ(*It, G.AccessNode(2)); 41 ++It; 42 EXPECT_EQ(It.getLevel(), 2U); 43 EXPECT_EQ(*It, G.AccessNode(3)); 44 ++It; 45 EXPECT_EQ(It, End); 46 } 47 48 TEST(BreadthFristIteratorTest, Cycle) { 49 typedef bf_iterator<Graph<4>> BFIter; 50 51 Graph<4> G; 52 G.AddEdge(0, 1); 53 G.AddEdge(1, 0); 54 G.AddEdge(1, 2); 55 G.AddEdge(2, 1); 56 G.AddEdge(2, 1); 57 G.AddEdge(2, 3); 58 G.AddEdge(3, 2); 59 G.AddEdge(3, 1); 60 G.AddEdge(3, 0); 61 62 auto It = BFIter::begin(G); 63 auto End = BFIter::end(G); 64 EXPECT_EQ(It.getLevel(), 0U); 65 EXPECT_EQ(*It, G.AccessNode(0)); 66 ++It; 67 EXPECT_EQ(It.getLevel(), 1U); 68 EXPECT_EQ(*It, G.AccessNode(1)); 69 ++It; 70 EXPECT_EQ(It.getLevel(), 2U); 71 EXPECT_EQ(*It, G.AccessNode(2)); 72 ++It; 73 EXPECT_EQ(It.getLevel(), 3U); 74 EXPECT_EQ(*It, G.AccessNode(3)); 75 ++It; 76 EXPECT_EQ(It, End); 77 } 78 79 static_assert( 80 std::is_convertible_v<decltype(*std::declval<bf_iterator<Graph<3>>>()), 81 typename bf_iterator<Graph<3>>::reference>); 82 83 // bf_iterator should be (at-least) a forward-iterator 84 static_assert(std::is_base_of_v<std::forward_iterator_tag, 85 bf_iterator<Graph<4>>::iterator_category>); 86 87 TEST(BreadthFristIteratorTest, MultiPassSafeWithInternalSet) { 88 Graph<4> G; 89 G.AddEdge(0, 1); 90 G.AddEdge(1, 2); 91 G.AddEdge(1, 3); 92 93 std::array<decltype(G)::NodeType *, 4> NodesFirstPass, NodesSecondPass; 94 95 auto B = bf_begin(G), E = bf_end(G); 96 97 std::size_t I = 0; 98 for (auto It = B; It != E; ++It) 99 NodesFirstPass[I++] = *It; 100 101 I = 0; 102 for (auto It = B; It != E; ++It) 103 NodesSecondPass[I++] = *It; 104 105 EXPECT_EQ(NodesFirstPass, NodesSecondPass); 106 } 107 108 } // end namespace llvm 109