projects
/
tatoo.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
d9e3bea
)
Implement reverse mapping from preorder to nodes.
author
Kim Nguyễn
<kn@lri.fr>
Wed, 7 Aug 2013 10:36:39 +0000
(12:36 +0200)
committer
Kim Nguyễn
<kn@lri.fr>
Wed, 7 Aug 2013 10:36:39 +0000
(12:36 +0200)
src/naive_tree.ml
patch
|
blob
|
history
src/tree.ml
patch
|
blob
|
history
diff --git
a/src/naive_tree.ml
b/src/naive_tree.ml
index
6625be0
..
33c953d
100644
(file)
--- a/
src/naive_tree.ml
+++ b/
src/naive_tree.ml
@@
-50,6
+50,7
@@
let rec dummy = {
type t = {
root : node;
size : int;
type t = {
root : node;
size : int;
+ by_preorder : node array;
(* TODO add other intersting stuff *)
}
(* TODO add other intersting stuff *)
}
@@
-207,8
+208,19
@@
struct
Expat.final psr;
let root = List.hd ctx.stack in
root.next_sibling <- nil;
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;
{ 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 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
let print_node fmt n = Parser.debug_node fmt n
diff --git
a/src/tree.ml
b/src/tree.ml
index
d44755e
..
97711dd
100644
(file)
--- 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].
*)
(** [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
val print_node : Format.formatter -> node -> unit
end