% Random access list.


% Random access lists (ral) is a functional (immutable) data
% structure which are better (in speed) both from normal lists,
% and from balanced binary search trees.


% Time complexity of various basic operations
%
% Operation    RAL      List   BST
%  head        O(1)     O(1)   O(log n)
%  tail        O(1)     O(1)   O(log n)
%  cons        O(1)     O(1)   O(log n)
%  nth         O(log n) O(n)   O(log n)
%  nthtail     O(log n) O(n)   O(log n)
%
% in some situations nth or nthtail can be faster in RAL. O(log n) is worst case complexity.
% for some values it is faster.


%%%%% API


% O(1)
RAList = ral:empty(). % it is just [], and will be, you can use it in pattern matching


% O(1)
NewRAList = ral:cons(something, RAList).


% O(1)
something = ral:head(NewRAList).


% O(1)
[] = ral:tail(NewRAList).


% O(n)
RAList2 = ral:from_list([b,c,d,e,f,g,h,i,j]).


% O(1)
RAList2b = ral:tail(RAList2).
[c,d,e,f,g,h,i,j] = ral:to_list(RAList2b).


% O(log n) - worst case
e = ral:nth(4, RAList2).


% O(log n) - worst case
RAList3 = ral:nthtail(4, RAList2).
[f,g,h,i,j] = ral:to_list(RAList3).


% O(log_2 n)
9 = ral:length(RAList2).


% O(1)
true = ral:is_empty(RAList).
false = ral:is_empty(NewRAList).


% O(1)
RAList4 = ral:cons(a, RAList2).


% O(n) + O(2 * log_2 n) of additional stack space
[a,b,c,d,e,f,g,h,i,j] = ral:to_list(RAList4).


% O(2 * log_2 n)
j = ral:last(RAList4).


% O(n)
% ral:foldl/3, ral:foldr/3, ral:map/2, ral:foreach/2, ral:mapfoldl/3, ral:mapfoldl/3, ral:dropwhile/2
% all similar like functions in lists:*
% Note: foldr should be more effective than lists:foldl (will only use O(log n) additional stack space)


% O(n)
RAList6 =  ral:from_list([44,12,16,1,6,6,1,7,9,22,41,5,31]).
{stop, {9,102}} = ral:foldl_cancelable(fun(Elem, {Pos,Acc}) -> if Acc > 100 -> {stop, {Pos,Acc}}; true -> {next, {Pos+1,Elem+Acc}} end end, {0,0}, RAList6).


% there is no filter/2, min/1, max/1, and other function which are not more efficient than just foldl


% there are also from_list_reversed/1, to_list_reversed/1 which are slightly more efficient

RAList7 = ral:from_list_reversed([a,b,c,d,e,f,g,h]).
h = ral:head(RAList7).
[j,i,h,g,f,e,d,c,b,a] = ral:to_list_reversed(RAList4)).


% there are also reverse_list/2, which prepends elements to current list, similar to lists:reverse/2

RAList8 = ral:reverse_list([x,y,z], RAList4).
[z,y,x,a,b,c,d,e,f,g,h,i,j] = ral:to_list(RAList8).


% replaceing element in ral is also O(log n), so it is provided
% ral:replace/3 have time complexity O(log n)
[a,b,c,d,e,f,g,h,i,j] = ral:to_list(RAList4).
[a,b,c,d,x,f,g,h,i,j] = ral:to_list(ral:replace(5, x, RAList4)).
[x,b,c,d,e,f,g,h,i,j] = ral:to_list(ral:replace(1, x, RAList4)).
[a,b,c,d,e,f,g,h,i,x] = ral:to_list(ral:replace(10, x, RAList4)).


% reverse/1 is also provided.
% Its time complexity is O(n)
% It is only provided for completnes.
% If you really needs it, this means that in fact you probably need other data structure.

%%%%%% Benchmarks:


L = lists:seq(100,10000).
RAL = ral:from_list(L).

% 49044 = size(term_to_binary(L)).
% 68883 = size(term_to_binary(RAL)).

% 20757 = size(term_to_binary(L, [compressed])).
% 22931 = size(term_to_binary(RAL, [compressed])).

timer:tc(erlang, length, [L]).
{70, 9901}.
timer:tc(ral, length, [RAL]).
{5, 9901}.                                   % <----

timer:tc(erlang, hd, [L]).
{2, 100}.
timer:tc(ral, head, [RAL]).
{3, 100}.

timer:tc(erlang, tl, [L]).
%{2, ...}.
timer:tc(ral, tail, [RAL]).
%{3, ...}.

timer:tc(lists, nth, [30, L]).
{6,129}.
timer:tc(ral, nth, [30, RAL]).
{4,129}.

timer:tc(lists, nth, [3000, L]).
{151,3099}
timer:tc(ral, nth, [3000, RAL]).
{7,3099}                                   % <----

timer:tc(lists, nth, [9000, L]).
{427,9099}.
timer:tc(ral, nth, [9000, RAL]).
{8,9099}.                                   % <----


element(1, timer:tc(lists, nthtail, [9000, L])).
427.
element(1, timer:tc(ral, nthtail, [9000, RAL])).
7.                                          % <----

element(1, timer:tc(lists, map, [fun(X) -> 2*X end, L])).
41000.
element(1, timer:tc(ral, map, [fun(X) -> 2*X end, RAL])).
42000.

element(1, timer:tc(lists, foldl, [fun(X,Acc) -> Acc+2*X end, 0, L])).
86000.
element(1, timer:tc(ral, foldl, [fun(X,Acc) -> Acc+2*X end, 0, RAL])).
81000.


element(1, timer:tc(lists, foldr, [fun(X,Acc) -> Acc+2*X end, 0, L])).
97000.
element(1, timer:tc(ral, foldr, [fun(X,Acc) -> Acc+2*X end, 0, RAL])).
82000.                                      % <--- slightly faster



% all iterating function have similar times.


%%%%%% Internals:

% let lists:reverse([a,b,c,d,e,f,g]) be a list
% let convert it to ral element by element:
%
% empty       []
% 1 elements  [{1, {a}}]            % one binary tree with 1 element
% 2 elements  [{1, {b}}, {1, {a}}]  % two same-size trees
% 3 elements  [{3, {c, {b}, {a}}}]  % one (complete) binary tree with 3 elements
% 4 elements  [{1, {d}},
%              {3, {c, {b}, {a}}}] 
% 5 elements  [{1, {e}}, {1, {d}},
%              {3, {c, {b}, {a}}}]
% 6 elements  [{3, {f, {e}, {d}}},
%              {3, {c, {b}, {a}}}]]
% 7 elements  [{7, {g, {f, {e}, {d}}, {c, {b}, {a}}}}]
% ...
% ...
% - constructed trees are always complete binary trees,
% - they have sizes 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, ...
% - they are placed in growing size in the list
% - There can be at most one tree of each size, with the exception of
%   that the first 2, which can be of the same size (like in 6-element or 2-element case above)
%
% - there is some overhead (so use it only for big lists, and when values are bigger
%   than just numer), but it is better than this:
%        [{7, {g, {f, {e, nil, nil}, {d, nil, nil}}, {c, {b, nil, nil}, {a, nil, nil}}}}]
%      - we just have speciall case for leaf's as single element tuples
%      - TODO: in the future it could be even changed to
%        [{7, {g, {f, e, d}, {c, b, a}}}]
%        becuase we know what is the height of tree
%
% for more information look at http://pl.wikipedia.org/wiki/Skośny_system_dwójkowy  (in polish)