Implement GTree wrapper

Also add some tests for the new class

3 files changed, 239 insertions, 0 deletions

diff --git a/tests/Makefile.am b/tests/Makefile.am
index 6be23469..af6ccb28 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -20,6 +20,7 @@ AUTOMAKE_OPTIONS = subdir-objects
 check_PROGRAMS =			\
 	giomm_ioerror/test		\
 	giomm_simple/test		\
+	glibmm_btree/test		\
 	glibmm_date/test		\
 	glibmm_nodetree/test		\
 	glibmm_ustring_compose/test	\
@@ -44,6 +45,7 @@ giomm_ioerror_test_LDADD   = $(giomm_ldadd)
 giomm_simple_test_SOURCES  = giomm_simple/main.cc
 giomm_simple_test_LDADD    = $(giomm_ldadd)
 
+glibmm_btree_test_SOURCES           = glibmm_btree/main.cc
 glibmm_date_test_SOURCES            = glibmm_date/main.cc
 glibmm_nodetree_test_SOURCES        = glibmm_nodetree/main.cc
 glibmm_ustring_compose_test_SOURCES = glibmm_ustring_compose/main.cc
diff --git a/tests/glibmm_btree/Makefile.am b/tests/glibmm_btree/Makefile.am
new file mode 100644
index 00000000..d0e58bd4
--- /dev/null
+++ b/tests/glibmm_btree/Makefile.am
@@ -0,0 +1,7 @@
+include $(top_srcdir)/tests/Makefile.am_fragment
+
+noinst_PROGRAMS = test
+test_SOURCES = main.cc
+
+
+
diff --git a/tests/glibmm_btree/main.cc b/tests/glibmm_btree/main.cc
new file mode 100644
index 00000000..6cf091a3
--- /dev/null
+++ b/tests/glibmm_btree/main.cc
@@ -0,0 +1,230 @@
+#include <glibmm.h>
+
+typedef Glib::ustring type_key_value;
+typedef type_key_value* type_p_key_value;
+
+static int
+my_search(const type_key_value& key_a, const type_key_value& key_b)
+{
+  return key_b.compare(key_a);
+}
+
+static bool
+my_traverse(const type_key_value& /*key*/, const type_key_value& value)
+{
+  g_assert(value.size() == 1 && value[0] > 0);
+  return false;
+} 
+
+const type_key_value str(
+  "0123456789"
+  "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+  "abcdefghijklmnopqrstuvwxyz");
+
+const type_key_value str2(
+  "0123456789"
+  "abcdefghijklmnopqrstuvwxyz");
+
+static bool
+check_order(const type_key_value& key,
+            const type_key_value& /*value*/,
+            type_key_value::const_iterator& i)
+{
+  g_assert(key == type_key_value(1, *(i++)));
+  return false;
+}
+
+static int
+my_p_search(const type_p_key_value& key_a, const type_p_key_value& key_b)
+{
+  return my_search(*key_a, *key_b);
+}
+
+static bool
+my_p_traverse(const type_p_key_value& key, const type_p_key_value& value)
+{
+  return my_traverse(*key, *value);
+} 
+
+
+std::vector<type_p_key_value> pstr;
+std::vector<type_p_key_value> pstr2;
+
+static bool
+check_p_order(const type_p_key_value& key,
+              const type_p_key_value& /*value*/,
+              std::vector<type_p_key_value>::const_iterator& i)
+{
+  g_assert(*key == **(i++));
+  return false;
+}
+
+static int
+my_p_key_compare(const type_p_key_value& key_a, const type_p_key_value& key_b)
+{
+  if(*key_a < *key_b)
+    return -1;
+
+  if(*key_a > *key_b)
+    return 1;
+
+  return 0;
+} 
+
+int
+main()
+{
+  type_key_value::const_iterator i;
+  Glib::RefPtr< Glib::BalancedTree<type_key_value, type_key_value> > tree = Glib::BalancedTree<type_key_value, type_key_value>::create();
+
+  for (type_key_value::size_type i = 0; i < str.size(); ++i)
+    tree->insert(str.substr(i, 1), str.substr(i, 1));
+
+  tree->foreach(sigc::ptr_fun(my_traverse));
+
+  g_assert(tree->nnodes() == gint(str.size()));
+  g_assert(tree->height() == 6);
+
+  tree->foreach(sigc::bind(sigc::ptr_fun(check_order), str.begin()));
+ 
+  for (type_key_value::size_type i = 0; i < 26; i++)
+    g_assert(tree->remove(str.substr(i + 10, 1)));
+
+  g_assert(!tree->remove(""));
+
+  tree->foreach(sigc::ptr_fun(my_traverse));
+
+  g_assert(tree->nnodes() == gint(str2.size()));
+  g_assert(tree->height() == 6);
+
+  tree->foreach(sigc::bind(sigc::ptr_fun(check_order), str2.begin()));
+
+  for (int i = 25; i >= 0; i--)
+    tree->insert(str.substr(i + 10, 1), str.substr(i + 10, 1));
+
+  tree->foreach(sigc::bind(sigc::ptr_fun(check_order), str.begin()));
+
+  type_key_value *value;
+
+  value = tree->lookup("0");
+  g_assert(value && *value == "0");
+  value = tree->lookup("A");
+  g_assert(value && *value == "A");
+  value = tree->lookup("a");
+  g_assert(value && *value == "a");
+  value = tree->lookup("z");
+  g_assert(value && *value == "z");
+
+  value = tree->lookup("!");
+  g_assert(value == NULL);
+  value = tree->lookup("=");
+  g_assert(value == NULL);
+  value = tree->lookup("|");
+  g_assert(value == NULL);
+
+  value = tree->search(sigc::ptr_fun(my_search), "0");
+  g_assert(value && *value == "0");
+  value = tree->search(sigc::ptr_fun(my_search), "A");
+  g_assert(value && *value == "A");
+  value = tree->search(sigc::ptr_fun(my_search), "a");
+  g_assert(value && *value == "a");
+  value = tree->search(sigc::ptr_fun(my_search), "z");
+  g_assert(value && *value == "z");
+
+  value = tree->search(sigc::ptr_fun(my_search), "!");
+  g_assert(value == NULL);
+  value = tree->search(sigc::ptr_fun(my_search), "=");
+  g_assert(value == NULL);
+  value = tree->search(sigc::ptr_fun(my_search), "|");
+  g_assert(value == NULL);
+
+  Glib::RefPtr< Glib::BalancedTree<type_p_key_value, type_p_key_value> > ptree = Glib::BalancedTree<type_p_key_value, type_p_key_value>::create(sigc::ptr_fun(my_p_key_compare));
+
+  for (type_key_value::size_type i = 0; i < str.size(); ++i)
+    pstr.push_back(new type_key_value(str.substr(i, 1)));
+  for (type_key_value::size_type i = 0; i < str2.size(); ++i)
+    pstr2.push_back(new type_key_value(str2.substr(i, 1)));
+
+  for (type_key_value::size_type i = 0; i < str.size(); ++i)
+    ptree->insert(pstr[i], pstr[i]);
+
+  ptree->foreach(sigc::ptr_fun(my_p_traverse));
+
+  g_assert(ptree->nnodes() == gint(pstr.size()));
+  g_assert(ptree->height() == 6);
+
+  std::vector<type_p_key_value>::const_iterator j = pstr.begin();
+  ptree->foreach(sigc::bind(sigc::ptr_fun(check_p_order), j));
+
+  g_assert(ptree->lookup(new Glib::ustring("l")));
+
+  for (std::vector<type_p_key_value>::size_type i = 0; i < 26; i++)
+    g_assert(ptree->remove(pstr[i + 10]));
+
+  Glib::ustring pstr3("");
+  g_assert(!ptree->remove(&pstr3));
+
+  ptree->foreach(sigc::ptr_fun(my_p_traverse));
+
+  g_assert(ptree->nnodes() == gint(str2.size()));
+  g_assert(ptree->height() == 6);
+
+  j = pstr2.begin();
+  ptree->foreach(sigc::bind(sigc::ptr_fun(check_p_order), j));
+
+  for (int i = 25; i >= 0; i--)
+    ptree->insert(pstr[i + 10], pstr[i + 10]);
+
+  j = pstr.begin();
+  ptree->foreach(sigc::bind(sigc::ptr_fun(check_p_order), j));
+
+  type_p_key_value *pvalue;
+
+  pstr3 = "0";
+  pvalue = ptree->lookup(&pstr3);
+  g_assert(pvalue && **pvalue == "0");
+  pstr3 = "A";
+  pvalue = ptree->lookup(&pstr3);
+  g_assert(pvalue && **pvalue == "A");
+  pstr3 = "a";
+  pvalue = ptree->lookup(&pstr3);
+  g_assert(pvalue && **pvalue == "a");
+  pstr3 = "z";
+  pvalue = ptree->lookup(&pstr3);
+  g_assert(pvalue && **pvalue == "z");
+
+  pstr3 = "!";
+  pvalue = ptree->lookup(&pstr3);
+  g_assert(pvalue == NULL);
+  pstr3 = "=";
+  pvalue = ptree->lookup(&pstr3);
+  g_assert(pvalue == NULL);
+  pstr3 = "|";
+  pvalue = ptree->lookup(&pstr3);
+  g_assert(pvalue == NULL);
+
+  pstr3 = "0";
+  pvalue = ptree->search(sigc::ptr_fun(my_p_search), &pstr3);
+  g_assert(pvalue && **pvalue == "0");
+  pstr3 = "A";
+  pvalue = ptree->search(sigc::ptr_fun(my_p_search), &pstr3);
+  g_assert(pvalue && **pvalue == "A");
+  pstr3 = "a";
+  pvalue = ptree->search(sigc::ptr_fun(my_p_search), &pstr3);
+  g_assert(pvalue && **pvalue == "a");
+  pstr3 = "z";
+  pvalue = ptree->search(sigc::ptr_fun(my_p_search), &pstr3);
+  g_assert(pvalue && **pvalue == "z");
+
+  pstr3 = "!";
+  pvalue = ptree->search(sigc::ptr_fun(my_p_search), &pstr3);
+  g_assert(pvalue == NULL);
+  pstr3 = "=";
+  pvalue = ptree->search(sigc::ptr_fun(my_p_search), &pstr3);
+  g_assert(pvalue == NULL);
+  pstr3 = "|";
+  pvalue = ptree->search(sigc::ptr_fun(my_p_search), &pstr3);
+  g_assert(pvalue == NULL);
+
+  return 0;
+}