Mercurial > dedupe

view TestRBTree.cpp @ 115:404795616b1e default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added a lot of common files to ignore
author Tom Fredrik Blenning Klaussen <bfg@bfgconsult.no>
date Sat, 25 Mar 2017 17:43:57 +0100
parents 247adcbbaf8b
children
line wrap: on
line source

#include "RBTree.hpp"
#include "TestFramework.hpp"

BOOST_AUTO_TEST_CASE( TestInsertLeftHeavy )
{
  RBTree<QString> map;

  QString k1 = "9";
  QString k2 = "8";
  QString k3 = "7";
  QString k4 = "6";

  BOOST_REQUIRE(!map.find(k1));
  BOOST_REQUIRE_EQUAL(map.depth(), 0u);
  BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
  BOOST_REQUIRE_EQUAL(map.size(), 0u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
  map.insert(k1);
  BOOST_REQUIRE_EQUAL(map.depth(), 1u);
  BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
  BOOST_REQUIRE_EQUAL(map.size(), 1u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
  BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);

  BOOST_REQUIRE(!map.find(k3));
  map.insert(k2);
  BOOST_REQUIRE_EQUAL(map.depth(), 2u);
  BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
  BOOST_REQUIRE_EQUAL(map.size(), 2u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
  BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
  BOOST_REQUIRE(map.find(k2));
  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);

  BOOST_REQUIRE(!map.find(k3));
  map.insert(k3);
  BOOST_WARN_EQUAL(map.depth(), 2u);
  BOOST_WARN_EQUAL(map.total_depth(), 5u);
  BOOST_REQUIRE_EQUAL(map.size(), 3u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
  BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
  BOOST_REQUIRE(map.find(k2));
  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
  BOOST_REQUIRE(map.find(k3));
  BOOST_REQUIRE_EQUAL(*map.find(k3), k3);

  BOOST_REQUIRE(!map.find(k4));
  map.insert(k4);
  BOOST_WARN_EQUAL(map.depth(), 2u);
  BOOST_WARN_EQUAL(map.total_depth(), 8u);
  BOOST_REQUIRE_EQUAL(map.size(), 4u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
  BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
  BOOST_REQUIRE(map.find(k2));
  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
  BOOST_REQUIRE(map.find(k4));
  BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
}

BOOST_AUTO_TEST_CASE( TestInsertRightHeavy )
{
  RBTree<QString> map;

  QString k1 = "5";
  QString k2 = "6";
  QString k3 = "7";
  QString k4 = "8";

  BOOST_REQUIRE(!map.find(k1));
  BOOST_REQUIRE_EQUAL(map.depth(), 0u);
  BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
  BOOST_REQUIRE_EQUAL(map.size(), 0u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
  map.insert(k1);
  BOOST_REQUIRE_EQUAL(map.depth(), 1u);
  BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
  BOOST_REQUIRE_EQUAL(map.size(), 1u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
  BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);

  BOOST_REQUIRE(!map.find(k3));
  map.insert(k2);
  BOOST_REQUIRE_EQUAL(map.depth(), 2u);
  BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
  BOOST_REQUIRE_EQUAL(map.size(), 2u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
  BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
  BOOST_REQUIRE(map.find(k2));
  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);

  BOOST_REQUIRE(!map.find(k3));
  map.insert(k3);
  BOOST_WARN_EQUAL(map.depth(), 2u);
  BOOST_WARN_EQUAL(map.total_depth(), 5u);
  BOOST_REQUIRE_EQUAL(map.size(), 3u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
  BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
  BOOST_REQUIRE(map.find(k2));
  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
  BOOST_REQUIRE(map.find(k3));
  BOOST_REQUIRE_EQUAL(*map.find(k3), k3);

  BOOST_REQUIRE(!map.find(k4));
  map.insert(k4);
  BOOST_WARN_EQUAL(map.depth(), 2u);
  BOOST_WARN_EQUAL(map.total_depth(), 8u);
  BOOST_REQUIRE_EQUAL(map.size(), 4u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
  BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
  BOOST_REQUIRE(map.find(k2));
  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
  BOOST_REQUIRE(map.find(k4));
  BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
}

BOOST_AUTO_TEST_CASE( TestInsertBalanced )
{
  RBTree<QString> map;

  QString k1 = "8";
  QString k2 = "4";
  QString k3 = "12";
  QString k4 = "2";

  BOOST_REQUIRE(!map.find(k1));
  BOOST_REQUIRE_EQUAL(map.depth(), 0u);
  BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
  BOOST_REQUIRE_EQUAL(map.size(), 0u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
  map.insert(k1);
  BOOST_REQUIRE_EQUAL(map.depth(), 1u);
  BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
  BOOST_REQUIRE_EQUAL(map.size(), 1u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
  BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);

  BOOST_REQUIRE(!map.find(k3));
  map.insert(k2);
  BOOST_REQUIRE_EQUAL(map.depth(), 2u);
  BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
  BOOST_REQUIRE_EQUAL(map.size(), 2u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
  BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
  BOOST_REQUIRE(map.find(k2));
  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);

  BOOST_REQUIRE(!map.find(k3));
  map.insert(k3);
  BOOST_WARN_EQUAL(map.depth(), 2u);
  BOOST_WARN_EQUAL(map.total_depth(), 5u);
  BOOST_REQUIRE_EQUAL(map.size(), 3u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
  BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
  BOOST_REQUIRE(map.find(k2));
  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
  BOOST_REQUIRE(map.find(k3));
  BOOST_REQUIRE_EQUAL(*map.find(k3), k3);

  BOOST_REQUIRE(!map.find(k4));
  map.insert(k4);
  BOOST_WARN_EQUAL(map.depth(), 2u);
  BOOST_WARN_EQUAL(map.total_depth(), 8u);
  BOOST_REQUIRE_EQUAL(map.size(), 4u);
  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
  BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
  BOOST_REQUIRE(map.find(k1));
  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
  BOOST_REQUIRE(map.find(k2));
  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
  BOOST_REQUIRE(map.find(k4));
  BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
}