Glib::BalancedTree< K, V > Class Template Reference

Balanced Binary Trees — a sorted collection of key/value pairs optimized for searching and traversing in order. More...

`#include <glibmm/balancedtree.h>`

List of all members.

## Public Types

typedef sigc::slot< bool, const K&, const V& > | TraverseFunc
typedef sigc::slot< int, const K&, const K& > | CompareFunc

## Public Member Functions

| ~BalancedTree ()
GTree* | gobj ()
| Provides access to the underlying C GObject.
const GTree* | gobj () const
| Provides access to the underlying C GObject.
void | reference ()
| Increments the reference count of tree by one.
void | unreference ()
| Decrements the reference count of tree by one.
void | insert (const K& key, const V&value)
| Inserts a key/value pair into a BalancedTree.
bool | remove (const K& key)
| Removes a key/value pair from a BalancedTree.
V* | lookup (const K& key)
| Gets the value corresponding to the given key.
const V* | lookup (const K& key) const
gint | height () const
| Gets the height of a BalancedTree.
gint | nnodes () const
| Gets the number of nodes in a BalancedTree.
void | foreach (const TraverseFunc& func) const
| Calls the given function for each of the key/value pairs in the BalancedTree.
V* | search (const CompareFunc& search_func, const K& key)
| Searches a BalancedTree using search_func.
const V* | search (const CompareFunc& search_func, const K& key) const
| Searches a BalancedTree using search_func.

## Static Public Member Functions

static Glib::RefPtr < BalancedTree< K, V > > | create ()
static Glib::RefPtr < BalancedTree< K, V > > | create (const CompareFunc& key_compare_slot)

## Protected Member Functions

| BalancedTree ()
| BalancedTree (const CompareFunc& key_compare_slot_)

## Detailed Description

### template<typename K, typename V>
class Glib::BalancedTree< K, V >

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 contructors.

Type of key to be used with this template must implement:

- less than operator
- greater than operator

## Member Typedef Documentation

template <typename K , typename V >

typedef sigc::slot<int, const K&, const K&> Glib::BalancedTree< K, V >::CompareFunc

template <typename K , typename V >

typedef sigc::slot<bool, const K&, const V&> Glib::BalancedTree< K, V >::TraverseFunc

## Constructor & Destructor Documentation

template <typename K , typename V >

Glib::BalancedTree< K, V >::BalancedTree | ( |  | ) | `[inline, protected]`

template <typename K , typename V >

Glib::BalancedTree< K, V >::BalancedTree | ( | const CompareFunc& | key_compare_slot_ | ) | `[inline, protected]`

template <typename K , typename V >

Glib::BalancedTree< K, V >::~BalancedTree | ( |  | ) | `[inline]`

## Member Function Documentation

template <typename K , typename V >

static Glib::RefPtr< BalancedTree<K, V> > Glib::BalancedTree< K, V >::create | ( |  | ) | `[inline, static]`

template <typename K , typename V >

static Glib::RefPtr< BalancedTree<K, V> > Glib::BalancedTree< K, V >::create | ( | const CompareFunc& | key_compare_slot | ) | `[inline, static]`

template <typename K , typename V >

void Glib::BalancedTree< K, V >::foreach | ( | const TraverseFunc& | func | ) | const`[inline]`

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.

Parameters:

  func | The function to call for each node visited. If this function returns true, the traversal is stopped.

template <typename K , typename V >

const GTree* Glib::BalancedTree< K, V >::gobj | ( |  | ) | const`[inline]`

Provides access to the underlying C GObject.

template <typename K , typename V >

GTree* Glib::BalancedTree< K, V >::gobj | ( |  | ) | `[inline]`

Provides access to the underlying C GObject.

template <typename K , typename V >

gint Glib::BalancedTree< K, V >::height | ( |  | ) | const`[inline]`

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.

Returns:
  the height of the BalancedTree.

template <typename K , typename V >

void Glib::BalancedTree< K, V >::insert | ( | const K & | key,
|  | const V & | value
| ) |  | `[inline]`

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.

Parameters:

  key | The key to insert.
  value | The value corresponding to the key.

template <typename K , typename V >

V* Glib::BalancedTree< K, V >::lookup | ( | const K & | key | ) | `[inline]`

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.

Parameters:

  key | The key to look up.

Returns:
  The value corresponding to the key, or 0 if the key was not found.

template <typename K , typename V >

const V* Glib::BalancedTree< K, V >::lookup | ( | const K & | key | ) | const`[inline]`

template <typename K , typename V >

gint Glib::BalancedTree< K, V >::nnodes | ( |  | ) | const`[inline]`

Gets the number of nodes in a BalancedTree.

Returns:
  the number of nodes in the BalancedTree.

template <typename K , typename V >

void Glib::BalancedTree< K, V >::reference | ( |  | ) | `[inline]`

Increments the reference count of tree by one.

It is safe to call this function from any thread.

template <typename K , typename V >

bool Glib::BalancedTree< K, V >::remove | ( | const K & | key | ) | `[inline]`

Removes a key/value pair from a BalancedTree.

If the key does not exist in the BalancedTree, the function does nothing.

Parameters:

  key | The key to remove.

Returns:
  true if the key was found (prior to 2.8, this function returned nothing)

template <typename K , typename V >

V* Glib::BalancedTree< K, V >::search | ( | const CompareFunc& | search_func,
|  | const K & | key
| ) |  | `[inline]`

Searches a BalancedTree using search_func.

The search_func is called with a reference to the key of a key/value pair in the tree. If search_func returns 0 for a key/value pair, then search() 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.

Parameters:

  search_func | A function used to search the BalancedTree.

Returns:
  the value corresponding to the found key, or NULL if the key was not found.

template <typename K , typename V >

const V* Glib::BalancedTree< K, V >::search | ( | const CompareFunc& | search_func,
|  | const K & | key
| ) |  | const`[inline]`

Searches a BalancedTree using search_func.

The search_func is called with a reference to the key of a key/value pair in the tree. If search_func returns 0 for a key/value pair, then search() 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.

Parameters:

  search_func | A function used to search the BalancedTree.

Returns:
  the value corresponding to the found key, or NULL if the key was not found.

template <typename K , typename V >

void Glib::BalancedTree< K, V >::unreference | ( |  | ) | `[inline]`

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.