test/etags/erl-src/lines.erl

   1 %%% The contents of this file are subject to the Erlang Public License,
   2 %%% Version 1.0, (the "License"); you may not use this file except in
   3 %%% compliance with the License. You may obtain a copy of the License at
   4 %%% http://www.erlang.org/license/EPL1_0.txt
   5 %%%
   6 %%% Software distributed under the License is distributed on an "AS IS"
   7 %%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
   8 %%% the License for the specific language governing rights and limitations
   9 %%% under the License.
  10 %%%
  11 %%% The Original Code is lines-1.0.
  12 %%%
  13 %%% The Initial Developer of the Original Code is Ericsson Telecom
  14 %%% AB. Portions created by Ericsson are Copyright (C), 1998, Ericsson
  15 %%% Telecom AB. All Rights Reserved.
  16 %%%
  17 %%% Contributor(s): ______________________________________.
  18
  19 %%%----------------------------------------------------------------------
  20 %%% #0.    BASIC INFORMATION
  21 %%%----------------------------------------------------------------------
  22 %%% File:       lines.erl
  23 %%% Author       : Ulf Wiger <ulf.wiger@ericsson.com>
  24 %%% Description  : Efficient array of lines (e.g. for text editor)
  25 %%%
  26 %%% Modules used : lists
  27 %%%
  28 %%%----------------------------------------------------------------------
  29 %%% Efficient array of lines (e.g. for text editor)
  30 %%% allows for append, as well as insert, replace, delete in any position
  31 %%% with reasonable access times.
  32 %%% Rough benchmarking indicates (on a 440MHz Ultra):
  33 %%%
  34 %%% NoOfLines   Append (uSec)   Read (uSec)     Delete (uSec)
  35 %%% 100         9               7               7
  36 %%% 1,000       14              10              11
  37 %%% 10,000      22              13              15
  38 %%% 100,000     30              16              18
  39 %%%
  40 %%% Comment on the benchmark: The times for Append and Delete are mean
  41 %%% times for "growing file" and "shrinking file", that is, starting from
  42 %%% an empty array and inserting 100,000 lines took ca 3 seconds; deleting
  43 %%% them took ca 1.8 seconds. The Read test involved accessing all lines
  44 %%% in the full array and calculating the mean time.
  45 %%%
  46 %%% The array doesn't care what goes into each position. In other words,
  47 %%% it can be used for any datatype -- not just lines of text.
  48 %%%----------------------------------------------------------------------
  49
  50 -module(lines).
  51 -vsn('1.0').
  52 -date('00-03-13').
  53 -author('ulf.wiger@ericsson.com').
  54
  55 -export([new/0,
  56          count/1,
  57          nth/2,
  58          append/2,
  59          replace/3,
  60          insert/3,
  61          insert_after/3,
  62          delete/2,
  63          convert_to_list/1,
  64          convert_from_list/1]).
  65
  66 -define(BREAK, 10).     % how many lines to store in each leaf
  67
  68 -define(dbg(Fmt, Args), ok=io:format("~p: " ++ Fmt, [?LINE|Args])).
  69 %% new() -> line_array()
  70 %%
  71 %% Creates a new line array.
  72 %%
  73 new() ->
  74     {0, []}.
  75
  76 %% line_count(line_array()) -> integer()
  77 %%
  78 %% Returns the number of lines stored in the array
  79 %%
  80 count({N, _}) ->
  81     N.
  82
  83 %% nth(LineNo : integer(), Array : line_array()) -> line()
  84 %%
  85 %% Returns the line in position LineNo
  86 %%
  87 nth(L, _) when L < 1 ->
  88     exit({out_of_range, L});
  89 nth(L, {LMax, _}) when L > LMax ->
  90     exit({out_of_range, L});
  91 nth(L, {LMax, List}) when list(List) ->
  92     lists:nth(L, List);
  93 nth(L, {LMax, {Left = {LL, _}, Right}}) when L > LL ->
  94     nth(L-LL, Right);
  95 nth(L, {_, {Left, _}}) ->
  96     nth(L, Left).
  97
  98 %% append(Line : line(), Array : line_array()) -> line_array().
  99 %%
 100 %% Appends Line to the end of Array.
 101 %% e.g. append(x, [1,2,3,4]) -> [1,2,3,4,x].
 102 %% Returns the modified array.
 103 %%
 104 append(Line, {L, List}) when list(List), L < ?BREAK ->
 105     {L+1, List ++ [Line]};
 106 append(Line, {L, List}) when list(List) ->
 107     {L+1, {{L, List}, {1, [Line]}}};
 108 append(Line, {L, {Left = {LL1, L1}, Right}}) ->
 109     NewRight = append(Line, Right),
 110     balance_left(L+1, Left, NewRight).
 111
 112 %% replace(LineNo : integer(), Array : line_array(), NewLine : line()) ->
 113 %%      line_array().
 114 %%
 115 %% Replaces the line in position LineNo with NewLine.
 116 %% e.g. replace(3, [1,2,3,4], x) -> [1,2,x,4].
 117 %% Returns the modified array.
 118 %%
 119 replace(Lno, _, _) when Lno < 1 ->
 120     exit({out_of_range, Lno});
 121 replace(Lno, {L, _}, NewLine) when Lno > L ->
 122     exit({out_of_range, Lno});
 123 replace(Lno, {L, List}, NewLine) when list(List) ->
 124     {L, replace_nth(Lno, List, NewLine)};
 125 replace(Lno, {L, {Left={LL1, L1}, Right={LL2, L2}}}, NewLine) when Lno > LL1 ->
 126     NewRight = replace(Lno-LL1, Right, NewLine),
 127     {L, Left, NewRight};
 128 replace(Lno, {L, {Left={LL1,L1}, Right={LL2,L2}}}, NewLine) ->
 129     NewLeft = replace(Lno, Left, NewLine),
 130     {L, NewLeft, Right}.
 131
 132 %% insert(LineNo : integer(), Array : line_array(), NewLine) -> line_array().
 133 %%
 134 %% Inserts NewLine *before* the line in position LineNo.
 135 %% e.g. insert(3, [1,2,3,4], x) -> [1,2,x,3,4].
 136 %% Returns the modified array.
 137 %%
 138 insert(Lno, _, _) when Lno < 1 ->
 139     exit({out_of_range, Lno});
 140 insert(Lno, {L, _}, NewLine) when Lno > L ->
 141     exit({out_of_range, Lno});
 142 insert(Lno, {L, List}, NewLine) when list(List) ->
 143     if L < ?BREAK ->
 144             {L+1, insert_nth(Lno, List, NewLine)};
 145        true ->
 146             NewList = insert_nth(Lno, List, NewLine),
 147             {L1, L2} = split_at(?BREAK, NewList),
 148             NewL = L+1,
 149             {NewL, {{?BREAK, L1}, {NewL-?BREAK, L2}}}
 150     end;
 151 insert(Lno, {L, {Left={LL,_}, Right}}, NewLine) when Lno > LL ->
 152     NewRight = insert(Lno-LL, Right, NewLine),
 153     balance_left(L+1, Left, NewRight);
 154 insert(Lno, {L, {Left, Right}}, NewLine) ->
 155     NewLeft = insert(Lno, Left, NewLine),
 156     balance_right(L+1, NewLeft, Right).
 157
 158 %% insert_after(LineNo : integer(), Array : line_array(), NewLine) ->
 159 %%      line_array().
 160 %%
 161 %% Inserts NewLine *after* the line in position LineNo.
 162 %% e.g. insert(3, [1,2,3,4], x) -> [1,2,3,x,4].
 163 %% Returns the modified array.
 164 %%
 165 insert_after(Lno, _, _) when Lno < 1 ->
 166     exit({out_of_range, Lno});
 167 insert_after(Lno, {L, _}, NewLine) when Lno > L ->
 168     exit({out_of_range, Lno});
 169 insert_after(Lno, {L, List}, NewLine) when list(List) ->
 170     if L < ?BREAK ->
 171             {L+1, insert_after_nth(Lno, List, NewLine)};
 172        true ->
 173             NewList = insert_after_nth(Lno, List, NewLine),
 174             {L1, L2} = split_at(?BREAK, NewList),
 175             NewL = L+1,
 176             {NewL, {{?BREAK, L1}, {NewL-?BREAK, L2}}}
 177     end;
 178 insert_after(Lno, {L, {Left={LL,_}, Right}}, NewLine) when Lno > LL ->
 179     NewRight = insert_after(Lno-LL, Right, NewLine),
 180     balance_left(L+1, Left, NewRight);
 181 insert_after(Lno, {L, {Left, Right}}, NewLine) ->
 182     NewLeft = insert_after(Lno, Left, NewLine),
 183     balance_right(L+1, NewLeft, Right).
 184
 185
 186 %% delete(LineNo : integer(), Array : line_array()) -> line_array().
 187 %%
 188 %% Deletes the line in position LineNo.
 189 %% e.g. delete(3, [1,2,3,4]) -> [1,2,4].
 190 %% Returns the modified array.
 191 %%
 192 delete(Lno, _) when Lno < 1 ->
 193     exit({out_of_range, Lno});
 194 delete(Lno, {N_Tot, _}) when Lno > N_Tot ->
 195     exit({out_of_range, Lno});
 196 delete(Lno, {N, List}) when list(List) ->
 197     {N-1, delete_nth(Lno, List)};
 198 delete(Lno, {N, {Left = {N_Left, _}, Right}}) when Lno > N_Left ->
 199     case delete(Lno-N_Left, Right) of
 200         {0, _} ->
 201             case N-1 of N_Left -> ok end,       % Assert
 202             Left;
 203         NewRight ->
 204             balance_right(N-1, Left, NewRight)
 205     end;
 206 delete(Lno, {N, {Left, Right = {N_Right,_}}}) ->
 207     case delete(Lno, Left) of
 208         {0, _} ->
 209             case N-1 of N_Right -> ok end,      % Assert
 210             Right;
 211         NewLeft ->
 212             balance_left(N-1, NewLeft, Right)
 213     end.
 214
 215 convert_to_list({_, List}) when list(List) ->
 216     List;
 217 convert_to_list({L, {Left, Right}}) ->
 218     convert_to_list(Left) ++ convert_to_list(Right).
 219
 220 convert_from_list(L) when list(L) ->
 221     lists:foldl(fun(Ln, Lsx) ->
 222                         append(Ln, Lsx)
 223                 end, new(), L).
 224
 225 %%% ===========================================================
 226 %%% internal functions
 227 %%% ===========================================================
 228
 229 replace_nth(1, [H|T], X) ->
 230     [X|T];
 231 replace_nth(N, [H|T], X) ->
 232     [H|replace_nth(N-1, T, X)].
 233
 234 insert_nth(1, L, X) ->
 235     [X|L];
 236 insert_nth(N, [H|T], X) ->
 237     [H|insert_nth(N-1, T, X)].
 238
 239 insert_after_nth(1, [H|T], X) ->
 240     [H,X|T];
 241 insert_after_nth(N, [H|T], X) ->
 242     [H|insert_after_nth(N-1, T, X)].
 243
 244 delete_nth(1, [H|T]) ->
 245     T;
 246 delete_nth(N, [H|T]) ->
 247     [H|delete_nth(N-1, T)].
 248
 249 %% split_at(Pos, List) -> {List1, List2}
 250 %%   split List into two after position Pos (List1 includes List[Pos])
 251 %%
 252 split_at(Pos, L) ->
 253     split_at(Pos, L, []).
 254
 255 split_at(0, L, Acc) ->
 256     {lists:reverse(Acc), L};
 257 split_at(Pos, [H|T], Acc) ->
 258     split_at(Pos-1, T, [H|Acc]).
 259
 260
 261 %% Balancing functions
 262 %% Since we know whether we inserted/deleted in the right or left subtree,
 263 %% we have explicit balancing functions for each case.
 264 %% We rebalance if the number of elements in one sub-subtree exceeds the
 265 %% sum of elements in the others.
 266
 267 balance_left(N_Tot,
 268              Left = {N_Left, _},
 269              Right = {N_Right, {RLeft = {N_RLeft, _},
 270                                 RRight = {N_RRight, _}}})  ->
 271     NewN_Left = N_Left + N_RLeft,
 272     if N_RRight > NewN_Left ->
 273             NewLeft = {NewN_Left, {Left, RLeft}},
 274             NewRight = RRight,
 275             {N_Tot, {NewLeft, NewRight}};
 276        true ->
 277             {N_Tot, {Left, Right}}
 278     end;
 279 balance_left(N_Tot, Left, Right) ->
 280     {N_Tot, {Left, Right}}.
 281
 282 balance_right(N_Tot,
 283              Left = {N_Left, {LLeft = {N_LLeft, _},
 284                               LRight = {N_LRight, _}}},
 285              Right = {N_Right, _})  ->
 286     NewN_Right = N_Right + N_LRight,
 287     if N_LLeft > NewN_Right ->
 288             NewLeft = LLeft,
 289             NewRight = {NewN_Right, {LRight, Right}},
 290             {N_Tot, {NewLeft, NewRight}};
 291        true ->
 292             {N_Tot, {Left, Right}}
 293     end;
 294 balance_right(N_Tot, Left, Right) ->
 295     {N_Tot, {Left, Right}}.
 296
 297