llvm/unittests/ADT/BreadthFirstIteratorTest.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-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