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 (and including) the cursor *)

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

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

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

val is_far_right : ?by_one:bool -> 'a zipper -> bool
(** Return whether the cursor is at the end of the zipper.
    If [by_one] is [true], the cursor is considered at the far right
    even when pointing {b to} the last element of the sequence. *)

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 : ?by_one:bool -> 'a zipper -> 'a zipper
(** Move the cursor one step to the right, if possible. If [by_one] is
    [true], the cursor won't move past the last element.
    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 : ?by_one:bool -> ('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. If [by_one] is [true], the cursor won't
    move past the last element. *)

val far_right : ?by_one:bool -> 'a zipper -> 'a zipper
(** Move the cursor to the right, as much as possible. If [by_one] is
    [true], the cursor won't move past the last element.*)

val goto : ?by_one:bool -> 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. If
    [by_one] is [true], the cursor won't move past the last element. *)

(** {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 : ?n:int -> 'a zipper -> 'a Sequence.t * 'a zipper
(** Remove [n] elements at the cursor position (1 by default), if any,
    and return them alongside the modified zipper. *)

val pop_before : ?n:int -> 'a zipper -> 'a Sequence.t * 'a zipper
(** Remove [n] elements before the cursor (1 by default), if any, and
    return them alongside the modified zipper. *)

val pop_after : ?n:int -> 'a zipper -> 'a Sequence.t * 'a zipper
(** Remove [n] elements after (and {b not} including) the cursor
    (1 by default), if any, and return them alongside the modified
    zipper. *)

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

val push_seq : 'a Sequence.t -> 'a zipper -> 'a zipper
(** Like {!Zipper.push}, but inserts a sequence of elements at the cursor
    position. *)

val push_after : 'a -> 'a zipper -> 'a zipper
(** Insert an element after the cursor. Behaves like {!Zipper.push} if
    the cursor is at the far right of the zipper.
    Calling [push_after 0 z], if [z] is [([3; 2; 1], [4; 5])],
    the result is [([3; 2; 1], [4; 0; 5]))], *)

val push_after_seq : 'a Sequence.t -> 'a zipper -> 'a zipper
(** Like {!Zipper.push_after}, but inserts a sequence of elements after
    the cursor. *)

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_before_seq : 'a Sequence.t -> 'a zipper -> 'a zipper
(** Like {!Zipper.push_before}, but inserts a sequence of elements
    before the cursor. *)

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 -> z2:'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_left : ('a -> unit) -> 'a zipper -> unit
(** [iter_left f z] will call [f x] for all [x], elements before the
    cursor in [z].*)

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

val iter : ('a -> unit) -> 'a zipper -> unit
(** [iter f z] is equivalent to [iter_left f z; iter_right 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_left : ('a -> bool) -> 'a zipper -> 'a option
(** [find_left p z] will return the first element before the cursor in
    [z] satisfying the predicate [p], if any. *)

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

val apply_focus : ('a -> 'b) -> 'a zipper -> 'b option
(** [apply focus f z] applies f to the current focus, if any, and
    returns its result *)

val apply_focus_or : default:'b -> ('a -> 'b) -> 'a zipper -> 'b
(** [apply focus f z] applies f to the current focus and returns its
    result. Return a default value if no element is in focus. *)

(** {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_left : ('a -> 'a) -> 'a zipper -> 'a zipper
(** Map a function over all elements before the cursor. *)

val map_right : ('a -> 'a) -> 'a zipper -> 'a zipper
(** Map a function over all elements after (and including) 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 -> 'b) -> 'a zipper -> 'b zipper
(** Map a function over all elements of a zipper. *)

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

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

val mapi : (int -> 'a -> 'b) -> 'a zipper -> 'b 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_left : ('a -> bool) -> 'a zipper -> 'a zipper
(** [filter_left 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_right : ('a -> bool) -> 'a zipper -> 'a zipper
(** [filter_right 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_left : int -> 'a zipper -> 'a zipper
(** [context_left n z] will limit the zipper [z] to [n] elements before
    the cursor. *)

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

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

val swap_focus : 'a -> 'a zipper -> 'a zipper
(** Swap the element in focus with a newly provided element. Nothing
    happens if no element is in focus. *)

(** {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]. *)