% Author: Markus Triska
% E-mail: triska@gmx.at
% Public domain code.

:- module(rope, [
                 rope_append/3,
                 subrope/4,
                 empty_rope/1,
                 rope_nth0/3,
                 rope_length/2,
                 rope_to_list/2,
                 list_to_rope/2,
                 rope_take/3,
                 rope_drop/3
                ]).

/** <module> Rope data type

This library provides the data type _rope_. Ropes are scalable lists:
Appending two ropes and accessing a subrope are efficient operations
in space and time. A possible use-case is an editor that uses a rope
to store its buffer contents, allowing for fast copy and paste.

Internally, a rope is implemented as a tree. Using list_to_rope/2
always creates a balanced rope. rope_length/2 and rope_append/3 always
take constant time and space. With a balanced rope, rope_nth0/3,
rope_take/3 and subrope/4 take at most logarithmic time.

@author Markus Triska
*/

/*
  A rope is a term of the form:

  r           ... empty rope
  t(T)        ... terminal T
  r(N,R1,R2)  ... R1 and R2 are ropes, with N terminals in total
*/


%% list_to_rope(+List, -Rope) is det.
%
%  Rope is the rope corresponding to List.

list_to_rope(Ls0, R) :- all_terminals(Ls0, Ls1), pairs_fixpoint(Ls1, R).

all_terminals([], []).
all_terminals([L|Ls], [t(L)|TLs]) :- all_terminals(Ls, TLs).

% concatenate pairs of ropes until only one rope is left

pairs_fixpoint([], r).
pairs_fixpoint([R0|Rs], R) :- pairs_fixpoint(Rs, R0, R).

pairs_fixpoint([], R, R).
pairs_fixpoint([R1|Rs], R0, R) :-
        stitch_pairs([R0,R1|Rs], Rs1),
        pairs_fixpoint(Rs1, R).

stitch_pairs([], []).
stitch_pairs([R0|Rs], Ps) :- stitch_pairs(Rs, R0, Ps).

stitch_pairs([], R, [R]).
stitch_pairs([R0|Rs], Prev, [Pair|Ps]) :-
        rope_append(Prev, R0, Pair),
        stitch_pairs(Rs, Ps).

%?- list_to_rope([a,b,c], P).
%?- list_to_rope([], P).

%?- length(Ls, 1000), maplist(=(a), Ls), time(list_to_rope(Ls, R)).

%% empty_rope(?Rope)
%
%  True if Rope is the empty rope.

empty_rope(r).

%?- list_to_rope([a,b,c,d,e,f,g], R).

%% rope_to_list(+Rope, -List) is det.
%
%  List is the list corresponding to Rope.

rope_to_list(R, Ls) :- rope_list(R, Ls, []).

rope_list(r)               --> [].
rope_list(t(E))            --> [E].
rope_list(r(_,Left,Right)) --> rope_list(Left), rope_list(Right).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% rope_length(+Rope, -Length) is det.
%
%  True if Rope contains Length elements.

rope_length(r, 0).
rope_length(t(_), 1).
rope_length(r(L,_,_), L).

%% rope_append(?Rope1, ?Rope2, -Result) is det.
%
% Unify Result with the concatenation of Rope1 and Rope2.

rope_append(R1, R2, r(L,R1,R2)) :-
        rope_length(R1, L1),
        rope_length(R2, L2),
        L is L1 + L2.

%% rope_drop(+Rope, +N, -Result) is det.
%
% Result is Rope with the first N elements removed. If Rope contains
% less than N elements, Result is the empty rope.

rope_drop(r, _, r)                :- !.
rope_drop(R0, 0, R)               :- !, R = R0.
rope_drop(t(_), _, R)             :- !, R = r.
rope_drop(r(Len0,L0,R0), N, Rope) :- !,
        (   N >= Len0 -> Rope = r
        ;   rope_length(L0, LenL0),
            (   N >= LenL0 ->
                N1 is N - LenL0,
                rope_drop(R0, N1, Rope)
            ;   rope_drop(L0, N, L1),
                rope_length(L1, LenL1),
                rope_length(R0, LenR0),
                Len1 is LenL1 + LenR0,
                Rope = r(Len1,L1,R0)
            )
        ).

%?-  rope_take(r(4, r(2, t(c), t(i)), r(2, t(i), t(c))), 3, _L210).

%% rope_take(+Rope, +N, -Result) is det.
%
%  Result contains the first N elements of Rope. If Rope has less than
%  N elements, Result is Rope.


rope_take(r, _, r)                :- !.
rope_take(_, 0, R)                :- !, R = r.
rope_take(t(T), _, R)             :- !, R = t(T).
rope_take(r(Len0,L0,R0), N, Rope) :- !,
        (   N >= Len0 -> Rope = r(Len0,L0,R0)
        ;   rope_length(L0, LenL0),
            (   N =< LenL0 ->
                rope_take(L0, N, Rope)
            ;   N1 is N - LenL0,
                rope_take(R0, N1, R1),
                rope_length(R1, LenR1),
                Len1 is LenL0 + LenR1,
                Rope = r(Len1,L0,R1)
            )
        ).


%?- list_to_rope([a,b,c], R0), rope_drop(R0, 2, R1).

%% subrope(+Rope, +From, +Length, -Result) is det.
%
%  Equivalent to first dropping From elements from Rope and then
%  taking Length elements from that.

subrope(Rope0, From, Length, Rope) :-
        rope_drop(Rope0, From, Rope1),
        rope_take(Rope1, Length, Rope).

%?- R = r(4, r(2, t(c), t(f)), r(2, t(p), t(c))), subrope(R,0,2,R1).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%?- list_to_rope([a,b,c], R), rope_leftmost(R, L).

rope_leftmost(t(E), E).
rope_leftmost(r(_,L0,R0), E) :-
        (   rope_leftmost(L0, X) -> X = E
        ;   rope_leftmost(R0, E)
        ).

%% rope_nth0(+N, +Rope, -Element) is semidet.
%
%  Element is the element at index N of Rope. Indexing starts at 0.


rope_nth0(0, Rope, Element) :- !, rope_leftmost(Rope, Element).
rope_nth0(N0, r(Len0,L1,R1), Element) :-
        N0 >= 0,
        N0 < Len0,
        rope_length(L1, LenL1),
        (   N0 < LenL1 ->
            rope_nth0(N0, L1, Element)
        ;   N1 is N0 - LenL1,
            rope_nth0(N1, R1, Element)
        ).

%?- list_to_rope([a,b,c,d], R0), rope_nth0(2, R0, N0), subrope(R0, 2, 2, R1).