+let is_below_right t1 t2 =
+ match (t1.node,t2.node) with
+ | Nil,_ | _,Nil -> false
+ | Node(i1), Node(i2) ->
+ tree_is_ancestor t1.doc (tree_parent t1.doc i1) i2
+ && not (tree_is_ancestor t1.doc i1 i2)
+ | Text(_,i1),Node(i2) -> i1 == i2 ||
+ (tree_is_ancestor t1.doc (tree_parent t1.doc i1) i2 && i1 < i2)
+ | Text(_,i1),Text(i,_) ->
+ let x,y = tree_doc_ids t1.doc i1 in
+ i >= x && i <= y
+ | Node(i1), Text(i,_) ->
+ let i2 = tree_next_sibling t1.doc i1 in
+ let x,y = tree_doc_ids t1.doc i2 in
+ i >= x && i <= y
+
+let parent n =
+ let node' =
+ match n.node with (* inlined parent *)
+ | Node(t) when (int_of_node t)== 0 -> Nil
+ | Node(t) ->
+ let txt = tree_prev_text n.doc t in
+ if text_is_empty n.doc txt then
+ let ps = tree_prev_sibling n.doc t in
+ if tree_is_nil ps
+ then
+ Node(tree_parent n.doc t)
+ else Node(ps)
+ else
+ Text(txt,t)
+ | Text(i,t) ->
+ let ps = tree_prev_doc n.doc i in
+ if tree_is_nil ps
+ then Node (tree_parent_doc n.doc i)
+ else Node(ps)
+ | _ -> failwith "parent"
+ in
+ { n with node = node' }
+
+let node_child n =
+ match n.node with
+ | Node i -> { n with node= norm(tree_first_child n.doc i) }
+ | _ -> { n with node = Nil }
+
+let node_sibling n =
+ match n.node with
+ | Node i -> { n with node= norm(tree_next_sibling n.doc i) }
+ | _ -> { n with node = Nil }
+
+let node_sibling_ctx n _ =
+ match n.node with
+ | Node i -> { n with node= norm(tree_next_sibling n.doc i) }
+ | _ -> { n with node = Nil }
+
+
+let first_child n =
+ let node' =
+ match n.node with
+ | Node (t) ->
+ let fs = tree_first_child n.doc t in
+ if equal_node nil fs
+ then
+ let txt = tree_my_text n.doc t in
+ if equal_node nil txt
+ then Nil
+ else Text(txt,nil)
+ else
+ let txt = tree_prev_text n.doc fs in
+ if equal_node nil txt
+ then Node(fs)
+ else Text(txt, fs)
+ | Text(_,_) -> Nil
+ | Nil -> failwith "first_child"
+ in
+ { n with node = node'}
+
+let next_sibling n =
+ let node' =
+ match n.node with
+ | Text (_,ns) -> norm ns
+ | Node(t) ->
+ let ns = tree_next_sibling n.doc t in
+ let txt = tree_next_text n.doc t in
+ if equal_node nil txt
+ then norm ns
+ else Text(txt, ns)
+ | Nil -> failwith "next_sibling"
+ in
+ { n with node = node'}
+
+let next_sibling_ctx n _ = next_sibling n
+
+let left = first_child
+let right = next_sibling