From 75375a8bc02893080745ab38768b7ee48f5c4153 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Kim=20Nguy=E1=BB=85n?= <kn@lri.fr>
Date: Wed, 7 Aug 2013 12:36:39 +0200
Subject: [PATCH] Implement reverse mapping from preorder to nodes.

---
 src/naive_tree.ml | 18 ++++++++++++++++--
 src/tree.ml       |  4 ++++
 2 files changed, 20 insertions(+), 2 deletions(-)

diff --git a/src/naive_tree.ml b/src/naive_tree.ml
index 6625be0..33c953d 100644
--- a/src/naive_tree.ml
+++ b/src/naive_tree.ml
@@ -50,6 +50,7 @@ let rec dummy = {
 type t = {
   root : node;
   size : int;
+  by_preorder : node array;
   (* TODO add other intersting stuff *)
 }
 
@@ -207,8 +208,19 @@ struct
        Expat.final psr;
        let root = List.hd ctx.stack in
        root.next_sibling <- nil;
+       let a = Array.create ctx.current_preorder nil in
+       let rec loop n =
+         if n != nil then
+           begin
+             a.(n.preorder) <- n;
+             loop n.first_child;
+             loop n.next_sibling;
+           end
+       in
+       loop root;
        { root = root;
-         size = ctx.current_preorder
+         size = ctx.current_preorder;
+         by_preorder = a
        }
     )
 
@@ -317,5 +329,7 @@ let tag _ n = n.tag
 let data _ n = n.data
 let kind _ n = n.kind
 let preorder _ n = n.preorder
-
+let by_preorder t i =
+ if i >= 0 && i < t.size then Array.unsafe_get t.by_preorder i
+ else let e = Invalid_argument "by_preorder" in raise e
 let print_node fmt n = Parser.debug_node fmt n
diff --git a/src/tree.ml b/src/tree.ml
index d44755e..97711dd 100644
--- a/src/tree.ml
+++ b/src/tree.ml
@@ -107,5 +107,9 @@ sig
   (** [preorder t n] returns the pre-order position of [n] in [t].
       [preodrder t (root t) == 0] and [preorder t nil < 0].
   *)
+
+  val by_preorder : t -> int -> node
+  (** [by_preorder t i] returns the node with preorder [i]
+  *)
   val print_node : Format.formatter -> node -> unit
 end
-- 
2.17.1