blob: f2a82882c48b253459a38d9d5303fce2c866dc49 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
open Base
(** Tree zippers.
A zipper represents {b a paused traversal} of a certain data
structure. A tree zipper of type ['a tipper] represents a zipper
over a generic tree of ['a] elements.
One can access the {b focused element} of the zipper with [focus].
The focus of a zipper is also known as the the {b cursor} of the
zipper. The cursor can be moved [up] to the parent node, if any, or
[down] to one of the selected children; [left] and [right] can be
used to select adjacent children. To select the right (resp. left)
sibling of the current cursor, for example, one should go [up], move
[right] (resp. [left]) and [down] again.
Elements can be added to the children of the current cursor with
[push] and removed with [pop].
In this particular implementation, there is no such thing as an {b
empty} tree zipper. *)
type !+'a tipper
(** A zipper is represented as an element of type ['a], a parent ['a
tipper] (with a hole) and a sequences of ['a tipper] children. *)
type !+'a t = 'a tipper
(** An alias for the ['a tipper] type. *)
val create : 'a -> 'a tipper
(** [create a] returns a new tipper with a single node containing [a]. *)
val focus : 'a tipper -> 'a
(** Returns the element pointed by the cursor *)
val is_root : 'a tipper -> bool
(** Returns whether the cursor is at the root of the tree. *)
val is_leaf : 'a tipper -> bool
(** Returns whether the cursor is pointing to a leaf (a node with no
children). *)
val is_far_left : 'a tipper -> bool
(** Returns whether the leftmost child is selected. *)
val is_far_right : 'a tipper -> bool
(** Returns whether the rightmost child is selected. *)
(** {1 Moving the cursor} *)
val left : 'a tipper -> 'a tipper
(** Select the children on the left. *)
val far_left : 'a tipper -> 'a tipper
(** Select the children on the far left. *)
val right : 'a tipper -> 'a tipper
(** Select the children on the right. *)
val far_right : 'a tipper -> 'a tipper
(** Select the children on the far right. *)
val up : 'a tipper -> 'a tipper
(** Move cursor to the parent node, if any. *)
val up_while : f:('a tipper -> bool) -> 'a tipper -> 'a tipper
(** [up_while ~f t] moves the cursor in [t] up while the predicate [f]
is satisfied. *)
val root : 'a tipper -> 'a tipper
(** Move the cursor up to the root of the tree. *)
val down : 'a tipper -> 'a tipper
(** Move cursor to the selected child node, if any. *)
(** {1 Modifying the tree zipper} *)
val set_focus : 'a -> 'a tipper -> 'a tipper
(** [set_focus a t] sets the element at the cursor position in [t] to
[a]. *)
val push : 'a tipper -> 'a tipper -> 'a tipper
(** [push t1 t2] adds [t1] as a subtree child of the node in [t2]
pointed by the cursor, so that [t1] is the newly selected child. *)
val pop : 'a tipper -> 'a tipper option * 'a tipper
(** [pop t] removes the subtree associated with the selected child.
Returns the subtree as a first element and the modified [t] as the
second. *)
(** {1 Consuming the tree zipper} *)
val fold : a:'a -> f:('a -> 'b tipper -> 'a) -> 'b tipper -> 'a
|
