unittests/ADT/BreadthFirstIteratorTest.cpp

   1 //=== llvm/unittest/ADT/BreadthFirstIteratorTest.cpp - BFS iterator tests -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/ADT/BreadthFirstIterator.h"
  11 #include "TestGraph.h"
  12 #include "gtest/gtest.h"
  13
  14 using namespace llvm;
  15
  16 namespace llvm {
  17
  18 TEST(BreadthFristIteratorTest, Basic) {
  19   typedef bf_iterator<Graph<4>> BFIter;
  20
  21   Graph<4> G;
  22   G.AddEdge(0, 1);
  23   G.AddEdge(0, 2);
  24   G.AddEdge(1, 3);
  25
  26   auto It = BFIter::begin(G);
  27   auto End = BFIter::end(G);
  28   EXPECT_EQ(It.getLevel(), 0U);
  29   EXPECT_EQ(*It, G.AccessNode(0));
  30   ++It;
  31   EXPECT_EQ(It.getLevel(), 1U);
  32   EXPECT_EQ(*It, G.AccessNode(1));
  33   ++It;
  34   EXPECT_EQ(It.getLevel(), 1U);
  35   EXPECT_EQ(*It, G.AccessNode(2));
  36   ++It;
  37   EXPECT_EQ(It.getLevel(), 2U);
  38   EXPECT_EQ(*It, G.AccessNode(3));
  39   ++It;
  40   EXPECT_EQ(It, End);
  41 }
  42
  43 TEST(BreadthFristIteratorTest, Cycle) {
  44   typedef bf_iterator<Graph<4>> BFIter;
  45
  46   Graph<4> G;
  47   G.AddEdge(0, 1);
  48   G.AddEdge(1, 0);
  49   G.AddEdge(1, 2);
  50   G.AddEdge(2, 1);
  51   G.AddEdge(2, 1);
  52   G.AddEdge(2, 3);
  53   G.AddEdge(3, 2);
  54   G.AddEdge(3, 1);
  55   G.AddEdge(3, 0);
  56
  57   auto It = BFIter::begin(G);
  58   auto End = BFIter::end(G);
  59   EXPECT_EQ(It.getLevel(), 0U);
  60   EXPECT_EQ(*It, G.AccessNode(0));
  61   ++It;
  62   EXPECT_EQ(It.getLevel(), 1U);
  63   EXPECT_EQ(*It, G.AccessNode(1));
  64   ++It;
  65   EXPECT_EQ(It.getLevel(), 2U);
  66   EXPECT_EQ(*It, G.AccessNode(2));
  67   ++It;
  68   EXPECT_EQ(It.getLevel(), 3U);
  69   EXPECT_EQ(*It, G.AccessNode(3));
  70   ++It;
  71   EXPECT_EQ(It, End);
  72 }
  73
  74 } // end namespace llvm