g_tree_lookup_range
- From: Soeren Sandmann <sandmann daimi au dk>
- To: gtk-devel-list redhat com
- Subject: g_tree_lookup_range
- Date: 02 Aug 1999 23:58:25 +0200
I am writing a program in which I need to extract ranges of data from
a GTree. Unfortunately, this is currently not possible (at least not
efficiently). Therefore, I propose adding
GSList *
g_tree_lookup_range (GTree *tree, gpointer from_key, gpointer to_key);
This function returns all entries with keys ranging from from_key to
to_key.
The following patch implements the function and also a slightly
faster, non-recursive version of g_tree_lookup.
--- gtree.c.den_originale Mon Aug 2 20:42:56 1999
+++ gtree.c Mon Aug 2 23:22:34 1999
@@ -71,6 +71,11 @@
static gpointer g_tree_node_lookup (GTreeNode *node,
GCompareFunc compare,
gpointer key);
+static void g_tree_node_lookup_range (GTreeNode *node,
+ GCompareFunc compare,
+ gpointer from_key,
+ gpointer to_key,
+ GSList **result);
static gint g_tree_node_count (GTreeNode *node);
static gint g_tree_node_pre_order (GTreeNode *node,
GTraverseFunc traverse_func,
@@ -213,6 +218,28 @@
return g_tree_node_lookup (rtree->root, rtree->key_compare, key);
}
+GSList *
+g_tree_lookup_range (GTree *tree,
+ gpointer from_key,
+ gpointer to_key)
+{
+ GRealTree *rtree;
+ GSList *result;
+
+ g_return_val_if_fail (tree != NULL, NULL);
+
+ rtree = (GRealTree*) tree;
+
+ g_return_val_if_fail ((* rtree->key_compare)(from_key, to_key) <= 0, NULL);
+
+ result = NULL;
+
+ g_tree_node_lookup_range (rtree->root, rtree->key_compare,
+ from_key, to_key, &result);
+
+ return result;
+}
+
void
g_tree_traverse (GTree *tree,
GTraverseFunc traverse_func,
@@ -499,22 +526,44 @@
if (!node)
return NULL;
- cmp = (* compare) (key, node->key);
- if (cmp == 0)
- return node->value;
-
- if (cmp < 0)
- {
- if (node->left)
- return g_tree_node_lookup (node->left, compare, key);
- }
- else if (cmp > 0)
- {
- if (node->right)
- return g_tree_node_lookup (node->right, compare, key);
- }
+ do {
+ cmp = (* compare) (key, node->key);
+ if (cmp == 0)
+ return node->value;
+ if (cmp < 0)
+ node = node->left;
+ else if (cmp > 0)
+ node = node->right;
+ } while (node && (cmp != 0));
return NULL;
+}
+
+static void
+g_tree_node_lookup_range (GTreeNode *node,
+ GCompareFunc compare,
+ gpointer from_key,
+ gpointer to_key,
+ GSList **result)
+{
+ gint from_cmp, to_cmp;
+
+ if (!node)
+ return;
+
+ from_cmp = (* compare)(from_key, node->key);
+ to_cmp = (* compare)(to_key, node->key);
+
+ if (from_cmp <= 0 && to_cmp >= 0)
+ {
+ g_tree_node_lookup_range (node->right, compare, from_key, to_key, result);
+ *result = g_slist_prepend (*result, node->value);
+ g_tree_node_lookup_range (node->left, compare, from_key, to_key, result);
+ }
+ else if (from_cmp > 0)
+ g_tree_node_lookup_range (node->right, compare, from_key, to_key, result);
+ else if (to_cmp < 0)
+ g_tree_node_lookup_range (node->left, compare, from_key, to_key, result);
}
static gint
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]