DisjointSetTests.cpp

Go to the documentation of this file.

/*
 * Copyright 2020 Nico Reißmann <nico.reissmann@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#include <gtest/gtest.h>
 
#include <jlm/util/disjointset.hpp>
 
static void
print(const jlm::util::DisjointSet<int>::Set & set)
{
  std::cout << "{";
  for (auto & member : set)
    std::cout << member << " ";
  std::cout << "}";
}
 
static void
print(const jlm::util::DisjointSet<int> & djset)
{
  for (auto & set : djset)
    print(set);
 
  std::cout << "\n";
}
 
TEST(DisjointSetTests, test)
{
  using namespace jlm;
 
  jlm::util::DisjointSet<int> djset({ 1, 2, 3, 4, 5 });
  print(djset);
  assert(djset.nvalues() == 5 && djset.nsets() == 5);
 
  auto s1 = djset.find_or_insert(6);
  auto s2 = djset.find(6);
  print(djset);
  EXPECT_EQ(s1, s2);
  EXPECT_EQ(djset.nvalues(), 6u);
  EXPECT_EQ(djset.nsets(), 6u);
 
  auto root = djset.merge(1, 2);
  print(djset);
  EXPECT_TRUE(root->is_root());
  EXPECT_EQ(root->nmembers(), 2u);
  EXPECT_EQ(djset.nvalues(), 6u);
  EXPECT_EQ(djset.nsets(), 5u);
 
  root = djset.merge(6, 5);
  print(djset);
  EXPECT_TRUE(root->is_root());
  EXPECT_EQ(root->nmembers(), 2u);
  EXPECT_EQ(djset.nvalues(), 6u);
  EXPECT_EQ(djset.nsets(), 4u);
 
  root = djset.merge(1, 6);
  print(djset);
  EXPECT_TRUE(root->is_root());
  EXPECT_EQ(root->nmembers(), 4u);
  EXPECT_EQ(djset.nvalues(), 6u);
  EXPECT_EQ(djset.nsets(), 3u);
  EXPECT_EQ(djset.find(2), djset.find(5));
 
  djset.clear();
  print(djset);
  EXPECT_EQ(djset.nvalues(), 0u);
  EXPECT_EQ(djset.nsets(), 0u);
}