diff options
| -rw-r--r-- | .gitignore | 2 | ||||
| -rwxr-xr-x | MSVC_Net2005/glibmm/glibmm.vcproj | 8 | ||||
| -rw-r--r-- | MSVC_Net2008/glibmm/glibmm.vcproj | 8 | ||||
| -rw-r--r-- | glib/glibmm.h | 1 | ||||
| -rw-r--r-- | glib/src/btree.ccg | 1 | ||||
| -rw-r--r-- | glib/src/btree.hg | 335 | ||||
| -rw-r--r-- | glib/src/filelist.am | 1 | ||||
| -rw-r--r-- | tests/Makefile.am | 2 | ||||
| -rw-r--r-- | tests/glibmm_btree/Makefile.am | 7 | ||||
| -rw-r--r-- | tests/glibmm_btree/main.cc | 230 |
10 files changed, 595 insertions, 0 deletions
@@ -84,6 +84,8 @@ giommconfig.h # glib/ /glib/glibmm-*.pc +/glib/glibmm/btree.cc +/glib/glibmm/btree.h /glib/glibmm/checksum.cc /glib/glibmm/checksum.h /glib/glibmm/convert.cc diff --git a/MSVC_Net2005/glibmm/glibmm.vcproj b/MSVC_Net2005/glibmm/glibmm.vcproj index 20a7dbda..2d175fb4 100755 --- a/MSVC_Net2005/glibmm/glibmm.vcproj +++ b/MSVC_Net2005/glibmm/glibmm.vcproj @@ -191,6 +191,10 @@ >
</File>
<File
+ RelativePath="..\..\glib\glibmm\btree.cc"
+ >
+ </File>
+ <File
RelativePath="..\..\glib\glibmm\checksum.cc"
>
</File>
@@ -409,6 +413,10 @@ >
</File>
<File
+ RelativePath="..\..\glib\glibmm\btree.h"
+ >
+ </File>
+ <File
RelativePath="..\..\glib\glibmm\checksum.h"
>
</File>
diff --git a/MSVC_Net2008/glibmm/glibmm.vcproj b/MSVC_Net2008/glibmm/glibmm.vcproj index a25f2cf3..f2df9ba8 100644 --- a/MSVC_Net2008/glibmm/glibmm.vcproj +++ b/MSVC_Net2008/glibmm/glibmm.vcproj @@ -190,6 +190,10 @@ >
</File>
<File
+ RelativePath="..\..\glib\glibmm\btree.cc"
+ >
+ </File>
+ <File
RelativePath="..\..\glib\glibmm\checksum.cc"
>
</File>
@@ -408,6 +412,10 @@ >
</File>
<File
+ RelativePath="..\..\glib\glibmm\btree.h"
+ >
+ </File>
+ <File
RelativePath="..\..\glib\glibmm\checksum.h"
>
</File>
diff --git a/glib/glibmm.h b/glib/glibmm.h index fa5f57fa..bb8066e2 100644 --- a/glib/glibmm.h +++ b/glib/glibmm.h @@ -25,6 +25,7 @@ #include <glibmmconfig.h> //#include <glibmm/i18n.h> //This must be included by the application, after system headers such as <iostream>. #include <glibmm/arrayhandle.h> +#include <glibmm/btree.h> #include <glibmm/checksum.h> #include <glibmm/class.h> #include <glibmm/containerhandle_shared.h> diff --git a/glib/src/btree.ccg b/glib/src/btree.ccg new file mode 100644 index 00000000..c1553e64 --- /dev/null +++ b/glib/src/btree.ccg @@ -0,0 +1 @@ +#include <glibmm/btree.h> diff --git a/glib/src/btree.hg b/glib/src/btree.hg new file mode 100644 index 00000000..a815ae19 --- /dev/null +++ b/glib/src/btree.hg @@ -0,0 +1,335 @@ +/* Copyright (C) 2007 glibmm development team + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with this library; if not, write to the Free + * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + +_DEFS(glibmm,glib) + +#include <glibmm/refptr.h> +#include <glibmm/ustring.h> +#include <glibmm/error.h> +#include <glibmm/arrayhandle.h> +#include <glib/gtree.h> + +namespace Glib +{ +/** N-ary Trees — trees of data with any number of branches + * The BalancedTree class and its associated functions provide a balancedctree data structure, in which trees in the tree can contain arbitrary data. + * + * @newin2p24 + */ +template <typename K, typename V> +class BalancedTree +{ + _CLASS_GENERIC(BalancedTree, GTree) +public: + typedef sigc::slot<bool, const K&, const V&> TraverseFunc; + typedef sigc::slot<int, const K&, const K&> CompareFunc; + + BalancedTree() : + key_compare_slot(sigc::ptr_fun(key_compare)) + { + gobject_ = g_tree_new_full(on_compare_tree, &key_compare_slot, on_destroy_key, on_destroy_value); + } + + BalancedTree(const CompareFunc &key_compare_slot_) : + key_compare_slot(key_compare_slot_) + { + gobject_ = g_tree_new_full(on_compare_tree, &key_compare_slot, on_destroy_key, on_destroy_value); + } + + ~BalancedTree() + { + g_tree_destroy(gobject_); + } + _IGNORE(g_tree_destroy) + + /// Provides access to the underlying C GObject. + inline GTree* gobj() + { + return gobject_; + } + + /// Provides access to the underlying C GObject. + inline const GTree* gobj() const + { + return gobject_; + } + +/** + * insert: + * @key: the key to insert. + * @value: the value corresponding to the key. + * + * Inserts a key/value pair into a #GTree. If the given key already exists + * in the #GTree its corresponding value is set to the new value. If you + * supplied a value_destroy_func when creating the #GTree, the old value is + * freed using that function. If you supplied a @key_destroy_func when + * creating the #GTree, the passed key is freed using that function. + * + * The tree is automatically 'balanced' as new key/value pairs are added, + * so that the distance from the root to every leaf is as small as possible. + **/ + void insert(const K &key, const V &value) + { + g_tree_insert(gobj(), reinterpret_cast<void *>(new K(key)), reinterpret_cast<void *>(new V(value))); + } + _IGNORE(g_tree_insert) + +/** + * replace: + * @key: the key to insert. + * @value: the value corresponding to the key. + * + * Inserts a new key and value into a #GTree similar to g_tree_insert(). + * The difference is that if the key already exists in the #GTree, it gets + * replaced by the new key. If you supplied a @value_destroy_func when + * creating the #GTree, the old value is freed using that function. If you + * supplied a @key_destroy_func when creating the #GTree, the old key is + * freed using that function. + * + * The tree is automatically 'balanced' as new key/value pairs are added, + * so that the distance from the root to every leaf is as small as possible. + **/ + void replace(const K &key, const V &value) + { + g_tree_replace(gobj(), new K(key), new V(value)); + } + _IGNORE(g_tree_replace) + +/** + * remove: + * @key: the key to remove. + * + * Removes a key/value pair from a #GTree. + * + * If the #GTree was created using g_tree_new_full(), the key and value + * are freed using the supplied destroy functions, otherwise you have to + * make sure that any dynamically allocated values are freed yourself. + * If the key does not exist in the #GTree, the function does nothing. + * + * Returns: %TRUE if the key was found (prior to 2.8, this function returned + * nothing) + **/ + bool remove(const K &key) + { + return g_tree_remove(const_cast<GTree*>(gobj()), &key); + } + _IGNORE(g_tree_remove) + +/** + * steal: + * @key: the key to remove. + * + * Removes a key and its associated value from a #GTree without calling + * the key and value destroy functions. + * + * If the key does not exist in the #GTree, the function does nothing. + * + * Returns: %TRUE if the key was found (prior to 2.8, this function returned + * nothing) + **/ + bool steal(const K &key) + { + return g_tree_steal(gobj(), &key); + } + _IGNORE(g_tree_steal) + +/** + * lookup: + * @key: the key to look up. + * + * Gets the value corresponding to the given key. Since a #GTree is + * automatically balanced as key/value pairs are added, key lookup is very + * fast. + * + * Return value: the value corresponding to the key, or %NULL if the key was + * not found. + **/ + V* lookup(const K &key) + { + return reinterpret_cast<V *>(g_tree_lookup(gobj(), &key)); + } + _IGNORE(g_tree_lookup) + + const V* lookup(const K &key) const + { + return reinterpret_cast<const V *>(g_tree_lookup(gobj(), &key)); + } + _IGNORE(g_tree_lookup) + +/** + * height: + * + * Gets the height of a #GTree. + * + * If the #GTree contains no nodes, the height is 0. + * If the #GTree contains only one root node the height is 1. + * If the root node has children the height is 2, etc. + * + * Return value: the height of the #GTree. + **/ + gint height() const + { + return g_tree_height(const_cast<GTree*>(gobj())); + } + _IGNORE(g_tree_height) + +/** + * nnodes: + * + * Gets the number of nodes in a #GTree. + * + * Return value: the number of nodes in the #GTree. + **/ + gint nnodes() const + { + return g_tree_nnodes(const_cast<GTree*>(gobj())); + } + _IGNORE(g_tree_nnodes) + +/** + * foreach: + * @func: the function to call for each node visited. If this function + * returns true, the traversal is stopped. + * + * Calls the given function for each of the key/value pairs in the #GTree. + * The function is passed the key and value of each pair. The tree is + * traversed in sorted order. + * + * The tree may not be modified while iterating over it (you can't + * add/remove items). To remove all items matching a predicate, you need + * to add each item to a list in your #TraverseFunc as you walk over + * the tree, then walk the list and remove each item. + **/ + void foreach(const TraverseFunc& func) + { + TraverseFunc func_copy = func; + g_tree_foreach(gobj(), c_callback_traverse, reinterpret_cast<gpointer>(&func_copy)); + } + _IGNORE(g_tree_foreach); + +/** + * search: + * @search_func: a function used to search the #GTree. + * @user_data: the data passed as the second argument to the @search_func + * function. + * + * Searches a #GTree using @search_func. + * + * The @search_func is called with a pointer to the key of a key/value pair in + * the tree, and the passed in @user_data. If @search_func returns 0 for a + * key/value pair, then g_tree_search_func() will return the value of that + * pair. If @search_func returns -1, searching will proceed among the + * key/value pairs that have a smaller key; if @search_func returns 1, + * searching will proceed among the key/value pairs that have a larger key. + * + * Return value: the value corresponding to the found key, or %NULL if the key + * was not found. + **/ + V* search(const CompareFunc &func, const K& key) + { + sigc::slot<int, const K&, const CompareFunc&, const K&> real_slot = sigc::ptr_fun(on_compare_key); + sigc::slot<int, const K&> bound_slot = sigc::bind(real_slot, func, key); + gpointer value = g_tree_search(gobj(), c_callback_search, reinterpret_cast<gconstpointer>(&bound_slot)); + + return reinterpret_cast<V*>(value); + } + + /** + * search: + * @search_func: a function used to search the #GTree. + * @user_data: the data passed as the second argument to the @search_func + * function. + * + * Searches a #GTree using @search_func. + * + * The @search_func is called with a pointer to the key of a key/value pair in + * the tree, and the passed in @user_data. If @search_func returns 0 for a + * key/value pair, then g_tree_search_func() will return the value of that + * pair. If @search_func returns -1, searching will proceed among the + * key/value pairs that have a smaller key; if @search_func returns 1, + * searching will proceed among the key/value pairs that have a larger key. + * + * Return value: the value corresponding to the found key, or %NULL if the key + * was not found. + **/ + const V* search(const CompareFunc &func, const K& key) const + { + return const_cast<BalancedTree<K, V>*>(this)->search(func, key); + } + +private: + /// Method for comparing keys by func (Internal use). + static gint on_compare_key(const K& key_a, const CompareFunc& func, const K& key_b) + { + return func(key_a, key_b); + } + + /// Wrapper for invoking GCompareFunc. + static gint c_callback_search(gconstpointer a, gconstpointer b) + { + const sigc::slot<int, const K&>* slot = reinterpret_cast<const sigc::slot<int, const K&> *>(b); + return (*slot)(*reinterpret_cast<const K*>(a)); + } + + /// Wrapper for invoking GTraverseFunc. + static gboolean c_callback_traverse(gpointer key, gpointer value, gpointer slot) + { + const TraverseFunc* tf = reinterpret_cast<const TraverseFunc*>(slot); + return (*tf)(*reinterpret_cast<const K*>(key), *reinterpret_cast<const V*>(value)); + } + + /// Method for comparing key values (Internal use). + static gint on_compare_tree(gconstpointer a, gconstpointer b, gpointer data) + { + const K& key_a = *reinterpret_cast<const K*>(a); + const K& key_b = *reinterpret_cast<const K*>(b); + const CompareFunc& func = *reinterpret_cast<const CompareFunc*>(data); + + return func(key_a, key_b); + } + + /// Method for destroying keys (Internal use). + static void on_destroy_key(gpointer data) + { + K* key = reinterpret_cast<K*>(data); + delete key; + } + + /// Method for destroying values (Internal use). + static void on_destroy_value(gpointer data) + { + V* value = reinterpret_cast<V*>(data); + delete value; + } + + /// Key compare function when it is not by the user (Internal use). + static int key_compare(const K& key_a, const K& key_b) + { + if(key_a < key_b) + return -1; + + if(key_a > key_b) + return 1; + + return 0; + } + + GTree* gobject_; + CompareFunc key_compare_slot; +}; + +} // namespace Glib diff --git a/glib/src/filelist.am b/glib/src/filelist.am index bb99ab99..fdf9ea40 100644 --- a/glib/src/filelist.am +++ b/glib/src/filelist.am @@ -13,6 +13,7 @@ glibmm_files_defs = \ glib_docs_override.xml glibmm_files_hg = \ + btree.hg \ checksum.hg \ convert.hg \ date.hg \ 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; +} |