Mercurial > dedupe

diff TestRBTree.cpp @ 16:06166d6c083b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add configuration processing. Cache DB values Add a custom RBTree to save space. Track multiple DB connections properly. More testing. Add ValueExistsException.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Tue, 28 Aug 2012 18:58:02 +0200
parents
children 247adcbbaf8b
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/TestRBTree.cpp	Tue Aug 28 18:58:02 2012 +0200
@@ -0,0 +1,196 @@
+#include "RBTree.hpp"
+#include "TestFramework.hpp"
+
+#include <QtCore/QString>
+
+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);
+}