[gtk+/wip/treeview: 4/6] treeview: Add _gtk_rbtree_find_index()

[Benjamin Otte <otte src gnome org>]

commit 2e6ab0366685fca8adb7e3607e73d03943bf33e2
Author: Benjamin Otte <otte redhat com>
Date:   Thu Jul 7 09:52:24 2011 +0200

    treeview: Add _gtk_rbtree_find_index()
    
    Uses the parity to do an O(log N) search for the nth element in the
    tree in display order of the treeview.

 gtk/gtkrbtree.c |   45 +++++++++++++++++++++++++++++++++++++++++++++
 gtk/gtkrbtree.h |    4 ++++
 2 files changed, 49 insertions(+), 0 deletions(-)
---
diff --git a/gtk/gtkrbtree.c b/gtk/gtkrbtree.c
index 54d7067..d601ac7 100644
--- a/gtk/gtkrbtree.c
+++ b/gtk/gtkrbtree.c
@@ -1104,6 +1104,51 @@ _gtk_rbtree_find_offset (GtkRBTree  *tree,
   return _gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
 }
 
+gboolean
+_gtk_rbtree_find_index (GtkRBTree  *tree,
+                        guint       index,
+                        GtkRBTree **new_tree,
+                        GtkRBNode **new_node)
+{
+  GtkRBNode *tmp_node;
+
+  g_assert (tree);
+
+  tmp_node = tree->root;
+  while (tmp_node != tree->nil)
+    {
+      if (tmp_node->left->parity > index)
+        {
+          tmp_node = tmp_node->left;
+        }
+      else if (tmp_node->parity - tmp_node->right->parity < index)
+        {
+          index -= tmp_node->parity - tmp_node->right->parity;
+          tmp_node = tmp_node->right;
+        }
+    }
+  if (tmp_node == tree->nil)
+    {
+      *new_tree = NULL;
+      *new_node = NULL;
+      return FALSE;
+    }
+
+  if (index > 0)
+    {
+      g_assert (tmp_node->children);
+
+      return _gtk_rbtree_find_index (tmp_node->children,
+                                     index - 1,
+                                     new_tree,
+                                     new_node);
+    }
+
+  *new_tree = tree;
+  *new_node = tmp_node;
+  return TRUE;
+}
+
 void
 _gtk_rbtree_remove_node (GtkRBTree *tree,
 			 GtkRBNode *node)
diff --git a/gtk/gtkrbtree.h b/gtk/gtkrbtree.h
index 22374f3..1f72603 100644
--- a/gtk/gtkrbtree.h
+++ b/gtk/gtkrbtree.h
@@ -139,6 +139,10 @@ gint       _gtk_rbtree_node_find_offset (GtkRBTree              *tree,
 					 GtkRBNode              *node);
 gint       _gtk_rbtree_node_find_parity (GtkRBTree              *tree,
 					 GtkRBNode              *node);
+gboolean   _gtk_rbtree_find_index       (GtkRBTree              *tree,
+					 guint                   index,
+					 GtkRBTree             **new_tree,
+					 GtkRBNode             **new_node);
 gint       _gtk_rbtree_find_offset      (GtkRBTree              *tree,
 					 gint                    offset,
 					 GtkRBTree             **new_tree,