open Base

(** Linear zippers.

    A zipper represents {b a paused traversal} of a certain data
    structure. A linear zipper of type ['a zipper] represents a zipper
    over a sequence 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, and can be moved back and forth with [left] and [right].

    Elements can be added or removed at the cursor's position with
    [push] and [pop] operations. Variants are available, e.g., to act
    before the cursor, with suffix [_before], or after the cursor, with
    suffix [_after]. *)

type !+'a zipper
(** A zipper is represented as a {b pair} of sequences of type ['a]. The
    focus of the zipper is the element at the head of the second
    sequence, if any.

    Note that the first sequence is reversed. Given a sequence
    [[1; 2; 3; 4; {5}; 6; 7]], where we represent the cursor using
    curly braces [{_}], its representation as a zipper is
    [([4; 3; 2; 1], [5; 6; 7])]. *)

type !+'a t = 'a zipper
(** An alias for the ['a zipper] type. *)

val empty : 'a zipper
(** Return an empty zipper *)

val before : 'a zipper -> 'a Sequence.t
(** Return the sequence before the cursor *)

val after : 'a zipper -> 'a Sequence.t
(** Return the sequence after the cursor *)

val focus : 'a zipper -> 'a option
(** Return the focus of the zipper, if any. *)

val focus_or : 'a zipper -> default:'a -> 'a
(** Return the focus of the zipper, or a user-provided default, otherwise. *)

val history : 'a zipper -> 'a Sequence.t
(** Returns the sequence of elements [pop]ped so far from the zipper. *)

val is_far_left : 'a zipper -> bool
(** Return whether the cursor is at the beginning of the zipper. *)

val is_far_right : 'a zipper -> bool
(** Return whether the cursor is at the end of the zipper. *)

val is_empty : 'a zipper -> bool
(** Return whether the zipper is empty. *)

val left_length : 'a zipper -> int
(** Return the number of elements before the cursor. *)

val right_length : 'a zipper -> int
(** Return the number of elements  after the cursor. *)

val length : 'a zipper -> int
(** Return the length of the zipper. *)

(** {1 Moving the cursor} *)

val left : 'a zipper -> 'a zipper
(** Move the cursor one step to the left, if possible.
    Calling [left z],

        - if [z] is [([3; 2; 1], [4; 5])], the result is [([2; 1], [3; 4; 5])], 
        - if [z] is [([], [1; 2; 3])], the result is [([], [1; 2; 3])].
    *)

val left_while : ('a -> bool) -> 'a zipper -> 'a zipper
(** [left_while f z] moves the cursor in [z] to the left as long as the
    predicate [f] is [true] when applied to the focus, or the left end
    of the zipper is reached. *)

val far_left : 'a zipper -> 'a zipper
(** Move the cursor to the left, as much as possible. *)

val right : 'a zipper -> 'a zipper
(** Move the cursor one step to the right, if possible.
    Calling [right z],

        - if [z] is [([3; 2; 1], [4; 5])], the result is [([4; 3; 2; 1], [5])], 
        - if [z] is [([1; 2; 3], [])], the result is [([1; 2; 3], [])].
    *)

val right_while : ('a -> bool) -> 'a zipper -> 'a zipper
(** [right_while f z] moves the cursor in [z] to the right as long as
    the predicate [f] is [true] when applied to the focus, or the right
    end of the zipper is reached. *)

val far_right : 'a zipper -> 'a zipper
(** Move the cursor to the right, as much as possible. *)

val goto : int -> 'a zipper -> 'a zipper
(** Move the cursor to a specific (absolute) position in the zipper.
    Depending on the current position, it either moves the cursor
    forward or backwards, without crossing the zipper boundaries. *)

(** {1 Changes at the cursor} *)

(** Zippers provide [O(1)] operations performed at the cursor position.
    This involve [push]ing and [pop]ping elements before and after the
    cursor. *)

val pop_after : 'a zipper -> 'a zipper
(** Remove the element at the cursor position, if any, and return the
    modified zipper. Calling [pop_after z],

        - if [z] is [([3; 2; 1], [4; 5])], the result is [([3; 2; 1], [5])], 
        - if [z] is [([1; 2; 3], [])], the result is [([1; 2; 3], [])].
    *)

val pop_before : 'a zipper -> 'a zipper
(** Remove the element before the cursor, if any, and return the
    modified zipper. Calling [pop_before z],

        - if [z] is [([3; 2; 1], [4; 5])], the result is [([2; 1], [4, 5])], 
        - if [z] is [([], [1; 2; 3])], the result is [([], [1; 2; 3])].
    *)

val pop : 'a zipper -> 'a zipper
(** [pop] is an alias for [pop_before]. *)

val push_after : 'a -> 'a zipper -> 'a zipper
(** Insert an element after the cursor.
    Calling [push_after 0 z], if [z] is [([3; 2; 1], [4; 5])],
    the result is [([3; 2; 1], [0; 4, 5]))], *)

val push_before : 'a -> 'a zipper -> 'a zipper
(** Insert an element before the cursor. Return the modified zipper.
    Calling [push_before 0 z], if [z] is [([3; 2; 1], [4; 5])],
    the result is [([0; 3; 2; 1], [4, 5]))]. *)

val push : 'a -> 'a zipper -> 'a zipper
(** [push] is an alias for [push_before]. *)

val split : 'a zipper -> 'a zipper * 'a zipper
(** [split z] splits the zipper in two. [([3; 2; 1], [4; 5])] becomes
    [([3; 2; 1], []), ([], [4; 5])]. *)

val join : 'a zipper -> 'a zipper -> 'a zipper
(** [join z1 z2] creates a new zipper using [before z1] and [after z2].
    [([3; 2; 1], []) ([4; 2], [4; 5])] becomes [([3; 2; 1], [4; 5])]. *)

(** {1 Consuming zippers} *)

(** Since zippers are based on sequences, iterating over zippers
    terminates only when both sequences are finite.
    Unless otherwise stated, these functions will iterate on the
    elements before the cursor, first. *)

val iter_before : ('a -> unit) -> 'a zipper -> unit
(** [iter_before f z] will call [f x] for all [x], elements before the
    cursor in [z].*)

val iter_after : ('a -> unit) -> 'a zipper -> unit
(** [iter_after f z] will call [f x] for all [x], elements after the
    cursor in [z].*)

val iter : ('a -> unit) -> 'a zipper -> unit
(** [iter f z] is equivalent to [iter_before f z; iter_after f z] *)

val for_all : ('a -> bool) -> 'a zipper -> bool
(** [for_all p z] tests whether a predicate [p] is [true] for all
    elements in a zipper. *)

val exists : ('a -> bool) -> 'a zipper -> bool
(** [exists p z] tests whether at least one element in the zipper is
    [true] according to the predicate [p]. *)

val find_before : ('a -> bool) -> 'a zipper -> 'a option
(** [find_before p z] will return the first element before the cursor in
    [z] satisfying the predicate [p], if any. *)

val find_after : ('a -> bool) -> 'a zipper -> 'a option
(** [find_after p z] will return the first element after the cursor in
    [z] satisfying the predicate [p], if any. *)

(** {1 Transforming zippers} *)

(** Since zippers are based on sequences, the functions in this section
    are lazy; i.e., resulting elements of the zipper are computed only
    when demanded. *)

val map_before : ('a -> 'a) -> 'a zipper -> 'a zipper
(** Map a function over all elements before the cursor. *)

val map_after : ('a -> 'a) -> 'a zipper -> 'a zipper
(** Map a function over all elements after the cursor. *)

val map_focus : ('a -> 'a) -> 'a zipper -> 'a zipper
(** Map a function over the element focused by the cursor, if any. *)

val map_focus_or : default:'a -> ('a -> 'a) -> 'a zipper -> 'a zipper
(** Map a function over the element focused by the cursor. Push
    [default] if no element is focused. *)

val map : ('a -> 'a) -> 'a zipper -> 'a zipper
(** Map a function over all elements of a zipper. *)

val mapi_before : (int -> 'a -> 'a) -> 'a zipper -> 'a zipper
(** [mapi_before] is analogous to {!Zipper.map_before}, but the function
    takes an index and an element.
    The index indicates the distance of an element from the cursor. *)

val mapi_after : (int -> 'a -> 'a) -> 'a zipper -> 'a zipper
(** [mapi_after] is analogous to {!Zipper.map_after}, but the function
    takes an index and an element.
    The index indicates the distance of an element from the cursor. *)

val mapi : (int -> 'a -> 'a) -> 'a zipper -> 'a zipper
(** [mapi] is analogous to {!Zipper.map}, but the function takes an
    index and an element.
    The index indicates the distance of an element from the cursor. *)

val filter_before : ('a -> bool) -> 'a zipper -> 'a zipper
(** [filter_before p z] filters the elements before the cursor in a
    zipper [z] according to a predicate [p], i.e., keeping the elements
    that satisfy the predicate. *)

val filter_after : ('a -> bool) -> 'a zipper -> 'a zipper
(** [filter_after p z] filters the elements after the cursor in a
    zipper [z] according to a predicate [p], i.e., keeping the elements
    that satisfy the predicate. *)

val filter : ('a -> bool) -> 'a zipper -> 'a zipper
(** [filter p z] filters the elements of the zipper [z] according to a
    predicate [p], i.e., keeping the elements that satisfy the
    predicate. *)

val context_before : int -> 'a zipper -> 'a zipper
(** [context_before n z] will limit the zipper [z] to [n] elements before
    the cursor. *)

val context_after : int -> 'a zipper -> 'a zipper
(** [context_after n z] will limit the zipper [z] to [n] elements after
    the cursor. *)

val context : b:int -> ?a:int -> 'a zipper -> 'a zipper
(** [context ~b ~a z] will limit the zipper [z] to [b] elements before
    the cursor and [a] elements after the cursor. When [a] is not
    provided, it defaults to [b]. *)

val clear_history : 'a zipper -> 'a zipper
(** Clear the history of the zipper. See {!Zipper.history}. *)

(** {1 Zippers and sequences} *)

val of_seq : 'a Sequence.t -> 'a zipper
(** Turn a sequence into a zipper with the cursor at the beginning. *)

val to_seq : 'a zipper -> 'a Sequence.t
(** Return the zipper as a sequence.
    Calling [to_seq z], with [z] being [([3; 2; 1], [4; 5])], results in
    [[1; 2; 3; 4; 5]]. *)

val window : from:int -> len:int -> 'a zipper -> 'a Sequence.t
(** [windows from len z] returns a sequence containing [len] elements
    starting from [from]. *)