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