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 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(0, 1);
  22   G.AddEdge(0, 2);
  23   G.AddEdge(1, 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(0, 1);
  47   G.AddEdge(1, 0);
  48   G.AddEdge(1, 2);
  49   G.AddEdge(2, 1);
  50   G.AddEdge(2, 1);
  51   G.AddEdge(2, 3);
  52   G.AddEdge(3, 2);
  53   G.AddEdge(3, 1);
  54   G.AddEdge(3, 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