path: root/glib/src/balancedtree.hg

/* Copyright (C) 2010 Szilárd Pfeiffer <mailbox@pfeifferszilard.hu>
 *
 * 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, see <http://www.gnu.org/licenses/>.
 */

_DEFS(glibmm,glib)

_IS_DEPRECATED // This whole file is deprecated.

#include <glibmm/refptr.h>
#include <glibmm/ustring.h>
#include <glibmm/error.h>
#include <glibmm/arrayhandle.h>
#include <glib.h>

namespace Glib
{

/** Balanced Binary Trees — a sorted collection of key/value pairs optimized for searching and traversing in order.
 * The BalancedTree structure and its associated functions provide a sorted
 * collection of key/value pairs optimized for searching and traversing in
 * order.
 *
 * To insert a key/value pair into a BalancedTree use insert().
 *
 * To lookup the value corresponding to a given key, use lookup().
 *
 * To find out the number of nodes in a BalancedTree, use nnodes(). To get the height of a BalancedTree, use height().
 *
 * To traverse a BalancedTree, calling a function for each node visited in the traversal, use foreach().
 *
 * To remove a key/value pair use remove().
 *
 * Any type to be used with this template must implement copy constructor.
 * Compiler-generated implementations are OK, provided they do the right
 * thing for the type. Both keys and values are stored in the balanced binary
 * tree as copies, created by copy constructors.
 *
 * Type of key to be used with this template must implement:
 * - less than operator
 * - greater than operator
 *
 * @deprecated Use std::map or std::unordered_map instead.
 *
 * @newin{2,24}
 */
template <typename K, typename V>
class BalancedTree
{
  _CLASS_GENERIC(BalancedTree, GTree)
public:
  using TraverseFunc = sigc::slot<bool, const K&, const V&>;
  using CompareFunc = sigc::slot<int, const K&, const K&>;

protected:
  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);
  }

  //TODO: Add move operations, being careful of universal references and overload resolution.

public:
  static Glib::RefPtr< BalancedTree<K, V> > create()
  {
    return Glib::RefPtr< BalancedTree<K, V> >(new BalancedTree());
  }

  static Glib::RefPtr< BalancedTree<K, V> > create(const CompareFunc &key_compare_slot)
  {
    return Glib::RefPtr< BalancedTree<K, V> >(new BalancedTree(key_compare_slot));
  }

  ~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_;
  }

  /** Increments the reference count of tree by one.  It is safe to call
   * this function from any thread.
   */
  void reference()
  {
    g_tree_ref(gobject_);
  }
  _IGNORE(g_tree_ref)

  /** Decrements the reference count of tree by one. If the reference count
   * drops to 0, all keys and values will be destroyed and all memory allocated
   * by tree will be released.
   *
   * It is safe to call this function from any thread.
   */
  void unreference()
  {
    g_tree_unref(gobject_);
  }
  _IGNORE(g_tree_unref)

  /** Inserts a key/value pair into a BalancedTree. If the given key already
   * exists in the BalancedTree its corresponding value is set to the new
   * value.
   *
   * 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.
   *
   * @param key The key to insert.
   * @param value The value corresponding to the key.
   */
  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)

  /** Removes a key/value pair from a BalancedTree.
   *
   * If the key does not exist in the BalancedTree, the function does nothing.
   *
   * @param key The key to remove.
   * @result 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)

  /** Gets the value corresponding to the given key. Since a BalancedTree is
   * automatically balanced as key/value pairs are added, key lookup is very
   * fast.
   *
   * @param key The key to look up.
   * @result The value corresponding to the key, or <tt>nullptr</tt> 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)

  /** Gets the height of a BalancedTree.
   *
   * If the BalancedTree contains no nodes, the height is 0.
   * If the BalancedTree contains only one root node the height is 1.
   * If the root node has children the height is 2, etc.
   *
   * @result the height of the BalancedTree.
   */
  gint height() const
  {
    return g_tree_height(const_cast<GTree*>(gobj()));
  }
  _IGNORE(g_tree_height)

  /** Gets the number of nodes in a BalancedTree.
   *
   * @result the number of nodes in the BalancedTree.
   */
  gint nnodes() const
  {
    return g_tree_nnodes(const_cast<GTree*>(gobj()));
  }
  _IGNORE(g_tree_nnodes)

  /** Calls the given function for each of the key/value pairs in the
   * BalancedTree.
   * 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.
   *
   * @param func The function to call for each node visited. If this function
   *   returns true, the traversal is stopped.
   */
  void foreach(const TraverseFunc& func) const
  {
    TraverseFunc func_copy = func;
    g_tree_foreach(const_cast<GTree*>(gobj()), c_callback_traverse, reinterpret_cast<gpointer>(&func_copy));
  }
  _IGNORE(g_tree_foreach);

  /** Searches a BalancedTree using @a search_func.
   *
   * The @a search_func is called with a reference to the key of a key/value pair
   * in the tree. If @a search_func returns 0 for a key/value pair, then search()
   * will return the value of that pair. If @a search_func returns -1,  searching
   * will proceed among the key/value pairs that have a smaller key; if
   * @a search_func returns 1, searching will proceed among the key/value pairs
   * that have a larger key.
   *
   * @param search_func A function used to search the BalancedTree.
   * @param key The key to search for.
   * @result The value corresponding to the found key, or <tt>nullptr</tt> if the key
   * was not found.
   */
  V* search(const CompareFunc &search_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, search_func, key);
    gpointer value = g_tree_search(gobj(), c_callback_search, reinterpret_cast<gconstpointer>(&bound_slot));

    return reinterpret_cast<V*>(value);
  }

  /** Searches a BalancedTree using @a search_func.
   *
   * The @a search_func is called with a reference to the key of a key/value pair
   * in the tree. If @a search_func returns 0 for a key/value pair, then search()
   * will return the value of that pair. If @a search_func returns -1,  searching
   * will proceed among the key/value pairs that have a smaller key; if
   * @a search_func returns 1, searching will proceed among the key/value pairs
   * that have a larger key.
   *
   * @param search_func A function used to search the BalancedTree.
   * @param key The key to search for.
   * @result The value corresponding to the found key, or <tt>nullptr</tt> if the key
   * was not found.
   */
  const V* search(const CompareFunc &search_func, const K& key) const
  {
    return const_cast<BalancedTree<K, V>*>(this)->search(search_func, key);
  }
  _IGNORE(g_tree_search)

  // The following functions don't make sense for the C++ wrapper.
  _IGNORE(g_tree_steal)
  _IGNORE(g_tree_lookup_extended)
  _IGNORE(g_tree_replace)
  _IGNORE(g_tree_traverse)

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