utility/tests/DisjointTreeForest_unittest.cpp

/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 **/

#include "utility/DisjointTreeForest.hpp"

#include <cstddef>
#include <string>
#include <vector>

#include "gtest/gtest.h"

namespace quickstep {

TEST(DisjointTreeForestTest, IntTest) {
  DisjointTreeForest<int> forest;
  for (int i = 10; i < 20; ++i) {
    forest.makeSet(i);
  }

  for (int i = 10; i < 20; i += 2) {
    EXPECT_NE(forest.find(i), forest.find(i+1));
    EXPECT_FALSE(forest.isConnected(i, i+1));

    forest.merge(i, i+1);
    EXPECT_EQ(forest.find(i), forest.find(i+1));
    EXPECT_TRUE(forest.isConnected(i, i+1));

    forest.merge(i+1, i);
    EXPECT_EQ(forest.find(i), forest.find(i+1));
    EXPECT_TRUE(forest.isConnected(i, i+1));
  }

  for (int i = 12; i < 20; i += 2) {
    EXPECT_NE(forest.find(i), forest.find(i-1));
    EXPECT_FALSE(forest.isConnected(i, i-1));
  }

  forest.merge(10, 17);
  forest.merge(11, 18);
  EXPECT_EQ(forest.find(11), forest.find(16));
  EXPECT_EQ(forest.find(10), forest.find(19));
  EXPECT_NE(forest.find(10), forest.find(12));
  EXPECT_NE(forest.find(15), forest.find(17));

  forest.merge(12, 14);
  forest.merge(15, 16);
  const std::size_t id = forest.find(10);
  for (int i = 10; i < 20; ++i) {
    EXPECT_EQ(forest.find(i), id);
  }
}

TEST(DisjointTreeForestTest, StringTest) {
  DisjointTreeForest<std::string> forest;
  const std::vector<std::string> elements = { "aaa", "bbb", "ccc", "ddd" };
  for (const std::string &element : elements) {
    forest.makeSet(element);
  }

  EXPECT_NE(forest.find("aaa"), forest.find("bbb"));
  forest.merge("aaa", "bbb");
  EXPECT_EQ(forest.find("aaa"), forest.find("bbb"));

  EXPECT_NE(forest.find("ccc"), forest.find("ddd"));
  forest.merge("ccc", "ddd");
  EXPECT_EQ(forest.find("ccc"), forest.find("ddd"));

  EXPECT_NE(forest.find("aaa"), forest.find("ccc"));
  EXPECT_NE(forest.find("aaa"), forest.find("ddd"));
  EXPECT_NE(forest.find("bbb"), forest.find("ccc"));
  EXPECT_NE(forest.find("bbb"), forest.find("ddd"));

  forest.merge("aaa", "ddd");
  for (const std::string &e1 : elements) {
    for (const std::string &e2 : elements) {
      EXPECT_EQ(forest.find(e1), forest.find(e2));
      EXPECT_TRUE(forest.isConnected(e1, e2));
    }
  }
}

}  // namespace quickstep