109 lines · cpp
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-exception6//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 19using namespace llvm;20 21namespace llvm {22 23TEST(BreadthFristIteratorTest, Basic) {24 using BFIter = bf_iterator<Graph<4>>;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 48TEST(BreadthFristIteratorTest, Cycle) {49 using BFIter = bf_iterator<Graph<4>>;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 79static_assert(80 std::is_convertible_v<decltype(*std::declval<bf_iterator<Graph<3>>>()),81 bf_iterator<Graph<3>>::reference>);82 83// bf_iterator should be (at-least) a forward-iterator84static_assert(std::is_base_of_v<std::forward_iterator_tag,85 bf_iterator<Graph<4>>::iterator_category>);86 87TEST(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 llvm109