1:- module(
    2       ropes,
    3       [
    4           string_rope/2,
    5           rope_string/2,
    6           rope_codes/2,
    7           rope_split/4,
    8           rope_concat/3,
    9           rope_report/4,
   10           rope_edit/5
   11       ]
   12   ).

 string_rope(+String:string, -Rope:rope) is det

True when Rope is a rope leaf holding the string String

   26string_rope(S , leaf(L, S)) :- string(S), string_length(S, L).

 rope_string(+Rope:rope, -String:string) is det

True when Rope represents the accumulated string String

   33rope_string(leaf(_, S)         , S ).
   34rope_string(node(_, _, _, A, B), S ) :-
   35    rope_string(A, AS),
   36    rope_string(B, BS),
   37    string_concat(AS, BS, S).

 rope_codes(+Rope:rope, -Codes:codes) is det

True when Rope represents the accumulated list of codes in Codes

   44rope_codes(R, C) :- phrase(rope_codes(R), C).
   45
   46rope_codes(leaf(_, S)         ) --> {   string_codes(S, Cs)   }, Cs.
   47rope_codes(node(_, _, _, A, B)) --> rope_codes(A), rope_codes(B).

 rope_split(+Rope:rope, +At:nonneg, -Left:rope, -Right:rope) is det

True when spliting Rope at underlying offset At yields ropes Left and Right

   54rope_split(leaf(_, String), At, leaf(At, Left), leaf(RLen, Right)) :-
   55    sub_string(String, At, RLen, 0, Right),
   56    !,
   57    sub_string(String, 0 , At  , _, Left).
   58rope_split(node(W, _, _, A, B), At, L, BB) :-
   59    W =< At,
   60    !,
   61    At1 is At - W,
   62    rope_split(B, At1, BA, BB),
   63    rope_concat(A, BA, L).
   64rope_split(node(_, _, _, A, B), At, L, R) :-
   65    rope_split(A, At, L, AB),
   66    rope_concat(AB, B, R).
   67
   68
   69rope_depth(leaf(_, _         ), 0).
   70rope_depth(node(_, _, D, _, _), D).
   71
   72
   73rope_length(leaf(L, _         ), L).
   74rope_length(node(_, L, _, _, _), L).

 rope_concat(+Left:rope, +Right:rope, -Rope:rope) is det

True when Rope is the concatenation of Left and Right

   81rope_concat(A, B, C) :-
   82    rope_concat_(A, B, C0),
   83    (   rope_balanced(C0)
   84    ->  C = C0
   85    ;   rope_balance(C0, C)
   86    ).
   87
   88rope_concat_(A, leaf(0, _), A) :- !.
   89rope_concat_(leaf(0, _), B, B) :- !.
   90rope_concat_(A, B, node(W, L, D, A, B)) :-
   91    rope_length(A, W ), rope_length(B, LB), L is W + LB,
   92    rope_depth( A, DA), rope_depth( B, DB), D is max(DA, DB) + 1.
   93
   94rope_balanced(R) :-
   95    rope_length(R, L),
   96    rope_depth(R, D0),
   97    D is D0 + 2,
   98    fib(D, F),
   99    F =< L.
  100
  101fib(0, 1) :- !.
  102fib(1, 1) :- !.
  103fib(N, F) :-
  104        fib(1,1,1,N,F).
  105
  106fib(_F, F1, N, N, F1) :- !.
  107fib(F0, F1, I, N, F)  :-
  108        F2 is F0+F1,
  109        I2 is I + 1,
  110        fib(F1, F2, I2, N, F).
  111
  112bif(M, N) :- bif(M, 1, 1, 0, N).
  113
  114bif(M, _ , F1, N , N) :- M =< F1, !.
  115bif(M, F0, F1, N0, N) :-
  116    F2 is F0 + F1,
  117    N1 is N0 + 1,
  118    bif(M, F1, F2, N1, N).
  119
  120
  121rope_balance(leaf(L, S), leaf(L, S)).
  122rope_balance(node(_, _, _, A, B), C) :-
  123    rope_balance(A, []    , Slots0),
  124    rope_balance(B, Slots0, Slots),
  125    pairs_values(Slots, Ropes),
  126    foldl(rope_concat_, Ropes, leaf(0, ""), C).
  127
  128rope_balance(leaf(L, S), D0, D) :-
  129    bif(L, I),
  130    partition({I}/[J-R]>>(J=<I), D0, D1, D2),
  131    pairs_values(D1, Rs0),
  132    reverse(Rs0, Rs),
  133    foldl(rope_concat_, Rs, leaf(0, ""), R0),
  134    rope_concat_(R0, leaf(L, S), R),
  135    rope_balance_(R, 0, D2, D).
  136rope_balance(node(_, _, _, A, B), D0, D) :-
  137    rope_balance(A, D0, D1),
  138    rope_balance(B, D1, D).
  139
  140rope_balance_(R0, J0, D0, D) :-
  141    select(J0-O, D0, D1),
  142    !,
  143    rope_concat_(O, R0, R),
  144    J is J0 + 1,
  145    rope_balance_(R, J, D1, D).
  146rope_balance_(R, J, D0, D) :-
  147    rope_length(R, L),
  148    bif(L, I),
  149    (   I =< J
  150    ->  ord_add_element(D0, I-R, D)
  151    ;   J1 is J + 1,
  152        rope_balance_(R, J1, D0, D)
  153    ).

 rope_report(+Rope:rope, +Offset:integer, +Length:integer, -String:string) is det

True when String is unified with the sub string in offset Offset and length Length of the underlying string of rope Rope

  160rope_report(leaf(_, S), O, N, R) :-
  161    sub_string(S, O, N, _, R).
  162rope_report(node(W, _, _, A, _), O, N, R) :-
  163    O + N =< W,
  164    !,
  165    rope_report(A, O, N, R).
  166rope_report(node(W, _, _, A, B), O, N, R) :-
  167    NA is W - O,
  168    0 < NA,
  169    !,
  170    rope_report(A, O, NA, RA),
  171    NB is O + N - W,
  172    rope_report(B, 0, NB, RB),
  173    string_concat(RA, RB, R).
  174rope_report(node(W, _, _, _, B), O, N, R) :-
  175    OB is O - W,
  176    rope_report(B, OB, N, R).

 rope_edit(+RopeIn:rope, +Offset:integer, +Length:integer, +Content:string, -RopeOut:rope) is det

Unify RopeOut with a rope obtained by replacing Content with the portion of RopeIn starting from offset Offset and spanning Length characters.

  184rope_edit(RopeIn, Offset, Length, Content, RopeOut) :-
  185    string_rope(Content, RopeContent),
  186    rope_split(RopeIn, Offset, Lope1, Rope1),
  187    rope_split(Rope1, Length, _, Rope2),
  188    rope_concat(Lope1, RopeContent, Lope2),
  189    rope_concat(Lope2, Rope2, RopeOut).
  190
  191
  192
  193:- begin_tests(ropes).  194
  195test(edit) :-
  196    string_rope("Hello, World!"  , HW),
  197    rope_edit(HW, 7, 5, "dragons", HD),
  198    rope_string(HD, HF),
  199    assertion(HF == "Hello, dragons!").
  200
  201test(report) :-
  202    string_rope("foobarbaz", R),
  203    rope_split(R, 6, FB, BZ),
  204    rope_split(FB, 3, F, BR),
  205    rope_concat(F, BR, FBB),
  206    rope_concat(FBB, BZ, FBZ),
  207    rope_report(FBZ, 2, 5, S),
  208    assertion(S == "obarb").
  209
  210:- end_tests(ropes).