g_tree_lookup_range

[Soeren Sandmann <sandmann daimi au dk>]

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