%%% -*- Erlang -*- %%%------------------------------------------------------------------- %%% $Id: ral.erl,v 1.7 2001/01/03 09:22:52 lon Exp $ %%% %%% Author: Lon Willett <Lon.Willett@sse.ie> %%% Description: Skew-binary Random Access Lists, ala Chris Okasaki [Oka95] %%% %%% This module provides a structure ("random-access list", or %%% "ralist") which has list-like behaviour (O(1) head, tail, cons), %%% and array/tree-like behaviour (O(log(N) access to elements by %%% position, replacement of elements, searching of sorted data). It %%% implements the basic operations, a fair number of general support %%% functions (iterators and such), some miscellaneous extras, and a %%% nearly complete version of the "lists" module functions, rewritten %%% to use ralists. %%% %%% The emphasis here is the "lists plus more" approach, i.e. more %%% code is devoted to providing clones of the "lists" module %%% functions, even though most of them can't take advantage of the %%% ralist structure, than is devoted to providing convenient %%% interfaces to algorithms that do take full advantage of the ralist %%% structure. Hopefully this makes it easy to replace list-based %%% implementations with ralist based ones, when it turns out that the %%% ralist functionality is needed. %%% %%% I have tried to provide a reasonable amount of fundamental %%% algorithm support, i.e. iterators and search functions and such, %%% so that one can write functions which take advantage of the ralist %%% structure without needing to get into the internals of this %%% implementation. But these functions tend to be inconvenient to %%% use, so you'll often want to put wrappers around them. %%% %%% Reference: %%% %%% [Oka95] Chris Okasaki, Purely functional random-acess lists. In %%% "Conference on Functional Programming Languages and Computer %%% Architecture", pages 86-95, June 1995. (Try his home page too, %%% URL???) %%% %%%------------------------------------------------------------------- -module(ral). -vsn('1.0'). -author('Lon.Willett@sse.ie'). %%% The structure is: %%% %%% ral() = [{height(),tree()}] %%% height() = int() % Height > 0 %%% tree() = element() % Height == 1 %%% | {element(),tree(),tree()} % Height > 1 %%% element() = term() %%% %%% Notes: %%% %%% The sequence of the elements is as they appear lexically (i.e. it %%% is the pre-order sequence for binary trees). %%% %%% The empty RAL is just "[]". However new/0 and is_empty/1 are %%% provided, in case you want to keep your code fully abstracted from %%% the implementation. (I myself just use "[]"; it's nicely %%% intuitive). %%% %%% The structure is deterministic, i.e. you can use "==", "=:=", %%% "/=", and "=/=" between ralists. In addition, "<" and friends %%% give the expected results between ralists of the same size, but %%% the order is rather arbitrary for lists of differing lengths. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Basic list operations (O(1)): %%% %%% new() -- return the empty ral: [] %%% is_empty(RAL) -- test RAL == [] %%% cons(X,RAL) -- insert an element at head of RAL %%% head(RAL) -- first element in RAL %%% tail(RAL) -- RAL with first element removed -export([new/0, is_empty/1, cons/2, head/1, tail/1]). %%% Array operations (fast, i.e. O(log(N))): %%% %%% sz(RAL), len(RAL) -- size of RAL %%% elt(N,RAL), nth(N,RAL) -- Nth element of RAL %%% last(RAL) -- last element of RAL %%% drop(N,RAL), nthtail(N,RAL) -- RAL with first N elts removed %%% setelt(N,RAL,Y) -- RAL with Nth element replaced by Y %%% update(N,RAL,Fun) -- RAL with Nth element replaced by Fun(NthElement) -export([sz/1, len/1, elt/2, nth/2, last/1, nthtail/2, setelt/3, update/3]). %%% Other index based operations (slow, i.e. O(N)): %%% %%% delnth(N,RAL) -- RAL with Nth element removed %%% insnth(N,RAL,Y) -- RAL with Y inserted before Nth element %%% locate(X,RAL) -- return index of first occurrence of X in RAL, %%% or false if X is not an element of RAL. %%% take(N,RAL) -- ralist consisting of first N elts of RAL %%% split(N,RAL) -- {take(N,RAL),drop(N,RAL)} -export([delnth/2, insnth/3, locate/2, take/2, split/2]). %%% Miscellaneous: %%% %%% to_list(RAL) -- convert an ralist to an ordinary list %%% from_list(List) -- convert an ordinary list to an ralist %%% from_list(List,N) -- convert the first N elements of List to an ralist %%% from_list_reversed(List) -- convert List to an ralist, reversing the %%% order of the elements. %%% from_list_reversed(List,RAL) -- more efficient version of: %%% ral:append(ral:from_list_reversed(List),RAL) %%% %%% seq(From,To), seq(From,To,Incr) -- like lists:seq %%% %%% duplicate(N,X) -- construct an ralist consisting of X %%% duplicated N times (only requires O(log(N)) space, %%% as long as you keep the structure sharing intact). %%% %%% split(RAL) -- split RAL into 2 ralists of roughly the same size %%% (more efficient than split/2, but still not %%% O(log(N)). See the comments in the code for the %%% precise details and meaning of "roughly". -export([to_list/1, from_list/1, from_list/2, from_list_reversed/1, from_list_reversed/2, seq/2, seq/3, duplicate/2, split/1]). %%% Working with sorted ralists: %%% %%% sort(RAL), sort(Compare,RAL) -- sort an ralist (like lists:sort). %%% %%% merge(RAL1,RAL2), merge(Compare,RAL1,RAL2) -- merge two sorted %%% ralists (like lists:merge). %%% %%% s_member(Elt,RAL), s_member(Compare,Elt,RAL) -- %%% search the _sorted_ ralist RAL for an element X such that %%% Compare(Elt,X) and Compare(X,Elt) are both true. Returns %%% true if such an element is found, false otherwise. %%% Compare is as for sort/merge (defaults to '=<'). %%% %%% s_locate(Elt,RAL), s_locate(Compare,Elt,RAL) -- %%% like s_member, but the return value when Elt is %%% found is {true,Index}, where Index is the index of the %%% element in the list, and the return value when Elt is %%% not found is {false,Count}, where Count is the number %%% of elements in the list that compare less than Elt. -export([sort/1, sort/2, merge/2, merge/3, s_member/2, s_member/3, s_locate/2, s_locate/3]). %%% Keyed tuple-list operations: %%% %%% "lists" module clones: %%% %%% keymember(Key,N,Tuples) keysearch(Key,N,Tuples) %%% keydelete(Key,N,Tuples) keyreplace(Key,N,Tuples,NewTuple) %%% keysort(N,Tuples) keymerge(N,Tuples1,Tuples2) %%% %%% Other: %%% %%% keylocate(Key,N,Tuples) -- like keysearch, but returns the tuple %%% {value,Index,Tuple} (instead of {value,Tuple}), where %%% Index is the index of Tuple in the ralist. %%% %%% s_keysearch(Key,N,Tuples) -- like "keysearch", but Tuples must %%% be sorted by key. %%% %%% s_keylocate(Key,N,Tuples) -- like "keylocate", but Tuples must %%% be sorted by key, and the return value when Key is not %%% found is the number of elements in the list with keys %%% ordered before Key. %%% %%% s_keydelete(Key,N,Tuples) -- like "keydelete", but Tuples must %%% be sorted by key. %%% %%% s_keyenter(N,Tuples,NewTuple) -- add NewTuple to Tuples, which must %%% be sorted by key, replacing an existing element with the %%% same key if there is one. More precisely, if no element %%% of Tuples has the same key as NewTuple, then this is %%% the same as "keymerge(N,Tuples,[NewTuple])". If some %%% element of Tuples does have the same key as NewTuple, %%% then this has the same effect as %%% "keyreplace(element(N,NewTuple),N,Tuples,NewTuple)". -export([keymember/3, keysearch/3, keylocate/3, keydelete/3, keyreplace/4, keysort/2, keymerge/3, s_keysearch/3, s_keylocate/3, s_keydelete/3, s_keyenter/3]). %%% Map, fold, and other iterators and functional interfaces: %%% %%% foreach(Fun,RAL) %%% map(Fun,RAL) %%% flatmap(Fun,RAL) %%% mapfoldl(Fun,Acc,RAL) %%% mapfoldr(Fun,Acc,RAL) %%% %%% -- like in the "lists" module. %%% %%% foldl(Fun,Acc,RAL) foldr(Fun,Acc,RAL), %%% foldl(Fun,Acc,RAL,Start) foldr(Fun,Acc,RAL,Start), %%% foldl(Fun,Acc,RAL,Start,Len) foldr(Fun,Acc,RAL,Start,Len) %%% -- foldl/3 and foldr/3 are as usual. Optionally, %%% a starting offset and length may be given, to restrict %%% the folding to a range of elements. Start is based at %%% one, i.e. the folded sequence is exactly %%% sublist(RAL,Start,Len). Note that Start and Len must %%% be in range, i.e. %%% 1 =< Start =< len(RAL)+1 %%% 0 =< Len =< len(RAL)+1-Start %%% %%% cfoldl(Cond,Fun,Acc,RAL) %%% cfoldr(Cond,Fun,Acc,RAL) %%% -- these are generalisations of foldl/foldr that allow %%% early termination of the iteration ("conditional %%% foldx"). Before folding an element into Acc, %%% Cond(Acc) is evaluated. If it returns true, then the %%% element is folded in and the iteration continues. If %%% it returns false, then the iteration is halted with %%% Acc as its value. Note that when Cond(Acc) returns %%% false, it may then be called multiple times for the %%% same accumulator (and all the calls should, of course, %%% return false). Therefore it should be cheap and %%% side-effect free (typically it is just a pattern match %%% test). %%% %%% linear_search(Pred,RAL) -- linearly search from the start of RAL %%% for an element for which Pred returns something other than %%% false. The return value of Pred is used as the return %%% value of linear_search(). 'false' is returned if no such %%% element was found. %%% %%% linear_search(Pred,RAL,I) -- like linear_search/2, except that %%% Pred is passed a second argument, which is I+Offset, %%% where Offset is the offset of the element in ralist %%% (e.g. call with I=1 to make the second argument the %%% position of the element in the list). %%% %%% binary_search(Pred,RAL) -- does a binary search on RAL for the %%% last element for which Pred(Element) returns true, assuming %%% that Pred returns true for some initial elements of RAL, %%% and false for the rest. Returns the tuple {true,Element}, %%% or returns false if Pred(ral:head(RAL)) is false. %%% %%% As a variant, if Pred returns a non-boolean value %%% Other, then the search is terminated, and {Other,Element} %%% is the return value (useful when you want to use a 3-way %%% comparison function). %%% %%% binary_search(Pred,RAL,I) -- variant on binary_search when you %%% are interested in the offset of the element in the %%% list. The args to Pred are (Element, I+Offset). The %%% return value is one of: %%% %%% false -- Pred(head(RAL),I) returned false. %%% %%% {true,I+Offset,Element} -- the last element %%% for which Pred returned true is Element, which %%% is located at offset Offset from the start %%% of the list. %%% %%% {Other,I+Offset,Element} -- Pred(Element,I+Offset) %%% returned the value Other (which is non-boolean). -export([foreach/2, map/2, flatmap/2, mapfoldl/3, mapfoldr/3, foldl/3, foldl/4, foldl/5, foldr/3, foldr/4, foldr/5, cfoldl/4, cfoldr/4, linear_search/2, linear_search/3, binary_search/2, binary_search/3]). %%% Other clones of "lists" module functions: %%% %%% append(RAL1,RAL2) append(ListOfRALs) %%% reverse(RAL) reverse(RAL,RALTail) %%% sublist(RAL,Len) sublist(RAL,Start,Len) %%% member(Element,RAL) %%% delete(Element,RAL) subtract(RAL1,RAL2) %%% all(Pred,RAL) any(Pred,RAL) %%% dropwhile(Pred,RAL) takewhile(Pred,RAL) %%% splitwith(Pred,RAL) %%% filter(Pred,RAL) %%% min(RAL) max(RAL) %%% sum(RAL) -export([append/2, append/1, reverse/1, reverse/2, sublist/2, sublist/3, member/2, delete/2, subtract/2, all/2, any/2, dropwhile/2, takewhile/2, splitwith/2, filter/2, min/1, max/1, sum/1]). %%% NB: The "lists" module documentation is mostly applicable here, %%% modulo the list to ralist change, but note the following: %%% %%% The following functions from the "lists" module do _not_ %%% have implementations here: %%% %%% concat/1 prefix/2 suffix/2 %%% flatten/1 flatten/2 flatlength/1 %%% %%% The "lists" module has a number of undocumented functions %%% for backward compatibility with previous versions. Naturally %%% I haven't implemented any of them. %%% %%% lists:sublist allows the Length argument to extend past the %%% end of the list. ral:sublist does not. %%% %%% lists:filter applies the predicate to the list elements in %%% a left-to-right manner. ral:filter does it in a right-to-left %%% manner. %%% %%% ral:flatmap/2 applies the function to the ralist elements in a %%% right-to-left manner. lists:flatmap/2 does it in a %%% left-to-right manner. %%% %%% ral:flatmap/2 expects to receive a normal list back from the %%% the function calls, _not_ an ralist. It then constructs %%% an ralist from the results. %%% %%% The argument to ral:append/1 is a _list_ of ralists, _not_ an %%% ralist of ralists. %%% %%% ral:subtract has a naive implementation; it will have terrible %%% efficiency for many cases. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Simple support functions/macros %%% tree size (2^Height - 1) and tree size plus one (2^Height) -define(tsize_plus_one(Height),(1 bsl (Height))). -define(tsize(Height),(1 bsl (Height) - 1)). %%% log2(X) -> floor(log(X)/log(2)), for positive integral X. %%% (This really should be a builtin bit-operation). log2(X) when integer(X), X > 0 -> log2_loop(X, 1, 2). log2_loop(X,_,ExpB) when X < ExpB -> 0; log2_loop(X,B,ExpB) -> %% B is a power of two (counting up from 1), and ExpB = 2^B = 1 bsl B, %% so 2^(2*B) = ExpB*ExpB = ExpB bsl B = 1 bsl (2*B) Y = log2_loop(X, 2*B, ExpB bsl B), %% And set bit B in the result, if it's needed if X bsr Y < ExpB -> Y; true -> Y+B end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Basics new() -> []. is_empty([]) -> true; is_empty(_) -> false. cons(X,[{Height,Tree1},{Height,Tree2}|Rest]) -> [{Height+1,{X,Tree1,Tree2}}|Rest]; cons(X,RAL) -> [{1,X}|RAL]. head([{1,X}|_]) -> X; head([{_,{X,_,_}}|_]) -> X. tail([{1,_}|Rest]) -> Rest; tail([{Height,{_,Tree1,Tree2}}|Rest]) -> [{Height-1,Tree1},{Height-1,Tree2}|Rest]. %%% sz(RAL), len(RAL) -- the length of the list len(RAL) -> sz(RAL). sz(RAL) -> SumTreeSize = fun({Height,_},Sum) -> Sum+?tsize(Height) end, lists:foldl(SumTreeSize, 0, RAL). %%% elt(N,RAL), nth(N,RAL) -- Nth elt nth(N,RAL) -> elt(N,RAL). elt(N,[{Height,Tree}|Rest]) -> Size=?tsize(Height), if N =< Size -> tree_elt(N,Height,Tree); true -> elt(N-Size,Rest) end. tree_elt(1,1,X) -> X; tree_elt(1,_,{X,_,_}) -> X; tree_elt(N,Height,{_,Tree1,Tree2}) -> Size1 = ?tsize_plus_one(Height-1), if N =< Size1 -> tree_elt(N-1,Height-1,Tree1); true -> tree_elt(N-Size1,Height-1,Tree2) end. %%% last(RAL) -- last element of list last(RAL) -> {Height,Tree} = lists:last(RAL), tree_last(Height,Tree). tree_last(1,X) -> X; tree_last(Height,{_,_,Tree2}) -> tree_last(Height-1,Tree2). %%% drop(N,RAL), nthtail(N,RAL) -- remove first N elts from RAL nthtail(N,RAL) -> drop(N,RAL). drop(0,RAL) -> RAL; drop(N,[{Height,Tree}|Rest]) -> Size = ?tsize(Height), if N < Size -> tree_drop(N,Height,Tree,Rest); true -> drop(N-Size,Rest) end. tree_drop(0,Height,Tree,Rest) -> [{Height,Tree}|Rest]; tree_drop(N,Height,{_,Tree1,Tree2},Rest) -> Size1 = ?tsize_plus_one(Height-1), if N < Size1 -> tree_drop(N-1,Height-1,Tree1,[{Height-1,Tree2}|Rest]); true -> tree_drop(N-Size1,Height-1,Tree2,Rest) end. %%% setelt(N,RAL,Y) -- replace Nth element of list setelt(N,[HTree|Rest],Y) -> {Height,Tree} = HTree, Size = ?tsize(Height), if N =< Size -> [{Height,tree_setelt(N,Height,Tree,Y)}|Rest]; true -> [HTree|setelt(N-Size,Rest,Y)] end. tree_setelt(N,Height,{X,Tree1,Tree2},Y) when N > 1 -> Size1 = ?tsize_plus_one(Height-1), if N =< Size1 -> {X,tree_setelt(N-1,Height-1,Tree1,Y),Tree2}; true -> {X,Tree1,tree_setelt(N-Size1,Height-1,Tree2,Y)} end; tree_setelt(1,1,_,Y) -> Y; tree_setelt(1,_,{_,Tree1,Tree2},Y) -> {Y,Tree1,Tree2}. %%% update(N,RAL,Fun) -- replace Nth element of list with Fun(OldValue). update(N,[HTree|Rest],Fun) -> {Height,Tree} = HTree, Size = ?tsize(Height), if N =< Size -> [{Height,tree_update(N,Height,Tree,Fun)}|Rest]; true -> [HTree|update(N-Size,Rest,Fun)] end. tree_update(N,Height,{X,Tree1,Tree2},Fun) when N > 1 -> Size1 = ?tsize_plus_one(Height-1), if N =< Size1 -> {X,tree_update(N-1,Height-1,Tree1,Fun),Tree2}; true -> {X,Tree1,tree_update(N-Size1,Height-1,Tree2,Fun)} end; tree_update(1,1,X,Fun) -> Fun(X); tree_update(1,_,{X,Tree1,Tree2},Fun) -> {Fun(X),Tree1,Tree2}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% delnth, insnth -- ugly and slow, yet useful. %%% locate, take, split/2 -- just slow (wrappers around other functions) %%% delnth(N,RAL) -- delete the Nth element from the RAL delnth(N,RAL) when N > 1 -> delnth_loop(N-1,head(RAL),tail(RAL)); delnth(1,RAL) -> tail(RAL). %%% delnth_loop(N,Y,RAL) -- delete the Nth element of RAL, and insert Y %%% at the head of the resulting list. delnth_loop(1,Y,RAL) -> case RAL of [{1,_}|Rest] -> [{1,Y}|Rest]; [{Height,{_,Tree1,Tree2}}|Rest] -> [{Height,{Y,Tree1,Tree2}}|Rest] end; delnth_loop(N,Y,[{Height,Tree}|Rest]) -> Size = ?tsize(Height), if N =< Size -> [{Height,tree_delnth_loop(N,Y,Height,Tree)}|Rest]; true -> {Y1,Tree1} = tree_shift_right(Y,Height,Tree), [{Height,Tree1}|delnth_loop(N-Size,Y1,Rest)] end. tree_delnth_loop(N,Y,Height,{X,Tree1,Tree2}) when N > 1 -> Size1 = ?tsize_plus_one(Height-1), if N =< Size1 -> {Y,tree_delnth_loop(N-1,X,Height-1,Tree1),Tree2}; true -> {X1,NewTree1} = tree_shift_right(X,Height-1,Tree1), {Y,NewTree1,tree_delnth_loop(N-Size1,X1,Height-1,Tree2)} end; tree_delnth_loop(1,Y,1,_) -> Y; tree_delnth_loop(1,Y,_,{_,Tree1,Tree2}) -> {Y,Tree1,Tree2}. %%% tree_shift_right -- shift the elements of a tree to the right, shifting %%% in the value Y, and return the pair {X,ShiftedTree}, where X is the %%% element that was shifted out. tree_shift_right(Y,1,X) -> {X,Y}; tree_shift_right(Y,Height,{X,Tree1,Tree2}) -> {X1,NewTree1} = tree_shift_right(X,Height-1,Tree1), {X2,NewTree2} = tree_shift_right(X1,Height-1,Tree2), {X2,{Y,NewTree1,NewTree2}}. %%% insnth(N,RAL,Y) -- insert elt into RAL at specified position insnth(1,RAL,Y) -> cons(Y,RAL); insnth(N,RAL,Y) -> cons(head(RAL),insnth_loop(N-1,RAL,Y)). %%% insnth_loop(N,RAL,Y) -- delete the first element of RAL, and insert %%% Y at the Nth position in the resulting list. insnth_loop(N,[{Height,Tree}|Rest],Y) -> Size = ?tsize(Height), if N =< Size -> Tree1 = tree_insnth_loop(N,Height,Tree,Y), [{Height,Tree1}|Rest]; true -> Tree1 = tree_shift_left(Height,Tree,head(Rest)), [{Height,Tree1}|insnth_loop(N-Size, Rest, Y)] end. tree_insnth_loop(N,Height,{_,Tree1,Tree2},Y) when N > 1, Height > 2 -> Size1 = ?tsize_plus_one(Height-1), {X1,_,_} = Tree1, if N =< Size1 -> {X1,tree_insnth_loop(N-1,Height-1,Tree1,Y),Tree2}; true -> {X2,_,_} = Tree2, {X1, tree_shift_left(Height-1,Tree1,X2), tree_insnth_loop(N-Size1,Height-1,Tree2,Y)} end; tree_insnth_loop(1,1,_,Y) -> Y; tree_insnth_loop(N,_Height,{_,X1,X2},Y) -> %% NB: ((N > 1 and Height == 2) or (N == 1 and Height >= 2)), case N of 1 -> {Y,X1,X2}; 2 -> {X1,Y,X2}; 3 -> {X1,X2,Y} end. tree_shift_left(Height,{_,Tree1,Tree2},Y) when Height > 2 -> {X1,_,_} = Tree1, {X2,_,_} = Tree2, {X1,tree_shift_left(Height-1,Tree1,X2),tree_shift_left(Height-1,Tree2,Y)}; tree_shift_left(2,{_,X1,X2},Y) -> {X1,X2,Y}; tree_shift_left(1,_,Y) -> Y. %%% locate(X,RAL) -- returns the position of the first occurrence %%% of X in RAL, or "false" if X is not in the list. locate(X,RAL) -> Fun = fun(Y,Index) when Y =:= X -> Index; (_,_) -> false end, linear_search(Fun,RAL,1). %%% take(N,RAL) -- return the ralist consisting of first N elts of RAL %%% (involves copying that portion of the structure). take(N,RAL) -> foldr(fun cons/2, [], RAL, 1, N). %%% split(N,RAL) split(N,RAL) -> {take(N,RAL),drop(N,RAL)}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% to_list is very straightforward. to_list(RAL) -> foldr(fun(X,List) -> [X|List] end, [], RAL). %%% from_list_reversed: convert List -> Ralist, reversing the elements. %%% Optional 2nd arg is tail (a RAL) to append. from_list_reversed(List) -> from_list_reversed(List,[]). from_list_reversed(List,RAL) -> lists:foldl(fun cons/2, RAL, List). %%% from_list/1: convert List -> Ralist from_list(List) -> from_list_loop(List,tree_heights(length(List))). %%% from_list/2: convert first Len elts of List into a Ralist. from_list(List,Len) when integer(Len), Len >= 0 -> from_list_loop(List,tree_heights(Len)). from_list_loop(_,[]) -> []; from_list_loop(Xs,[Height|Heights]) -> [Tree|Xs1] = tree_from_list(Xs,Height), [{Height,Tree}|from_list_loop(Xs1,Heights)]. %%% tree_from_list(List,Height) makes a tree of height Height from the %%% initial elements in List, and returns the value [Tree|RemainderOfList]. tree_from_list(List,1) -> List; tree_from_list([X|Xs],Height) -> [Tree1|Xs1] = tree_from_list(Xs,Height-1), [Tree2|Xs2] = tree_from_list(Xs1,Height-1), [{X,Tree1,Tree2}|Xs2]. %%% seq/2, seq/3 seq(From,To) -> seq_loop(From,1,tree_heights(To-From+1)). seq(From,To,Incr) -> Steps = (To - From) div Incr, seq_loop(From,Incr,tree_heights(Steps+1)). seq_loop(_,_,[]) -> []; seq_loop(From,Incr,[Height|Heights]) -> [{Height,tree_seq(From,Incr,Height)} | seq_loop(From+Incr*?tsize(Height),Incr,Heights)]. tree_seq(From,_,1) -> From; tree_seq(From,Incr,Height) -> {From, tree_seq(From+Incr,Incr,Height-1), tree_seq(From+Incr*?tsize_plus_one(Height-1),Incr,Height-1)}. %%% tree_heights(N) makes a list of the tree heights in a RAL of size N. tree_heights(N) when N < 0 -> []; tree_heights(N) -> build_decomposition(N,log2(N+1),[]). build_decomposition(0, _, List) -> List; build_decomposition(N, Height, List) -> Size = ?tsize(Height), if N < Size -> build_decomposition(N, Height-1, List); true -> build_decomposition(N-Size, Height, [Height|List]) end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% duplicate(Size,Elem) -- create an ralist containing the element Elem %%% duplicated Size times. duplicate(0,_) -> []; duplicate(N,X) when integer(N), N > 0 -> build_trees_loop(N,X,1,X,[]). build_trees_loop(N,X,Height,Tree,HTrees) -> Size = ?tsize(Height+1), if N >= Size -> build_trees_loop(N,X,Height+1,{X,Tree,Tree}, [{Height,Tree}|HTrees]); true -> HTree={Height,Tree}, select_trees_loop(N-?tsize(Height),[HTree|HTrees],[HTree]) end. select_trees_loop(0,_,RAL) -> RAL; select_trees_loop(N,HTrees,RAL) -> [HTree|Rest] = HTrees, {Height,_} = HTree, Size=?tsize(Height), if N < Size -> select_trees_loop(N,Rest,RAL); true -> select_trees_loop(N-Size,HTrees,[HTree|RAL]) end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% split(RAL) -- splits an into two parts, avoiding excessive copying. %%% The return value is {RAL1,RAL2}, where: %%% RAL = append(RAL1,RAL2) %%% 3*len(RAL1)+1 >= len(RAL) %%% 3*len(RAL2) >= len(RAL) %%% len(RAL2)+1 is a power of two split([]) -> {[],[]}; split(RAL) -> split(RAL,0,[]). split([HTree|Rest], _, Acc) when Rest /= [] -> {Height,_} = HTree, split(Rest,Height,[HTree|Acc]); split([{H1,{X,Tree1,Tree2}}], H0, Acc) when H1 > H0+1 -> %% Put Tree2 in RAL2. Everthing else goes into RAL1 (the trees in %% Acc will need to be copied, but they should be less than 1/3 of %% the total number of elements). RAL1 = lists:foldl(fun({H,T},RALAcc) -> tree_foldr(fun cons/2,RALAcc,H,T) end, [{1,X},{H1-1,Tree1}], Acc), RAL2 = [{H1-1,Tree2}], {RAL1,RAL2}; split(RAL, _, Acc) -> %% No need to copy the trees at all; the leading trees %% make up a significant enough percentage of the total %% on their own. So all the initial trees go into RAL1, and %% the final tree goes in RAL2. {lists:reverse(Acc),RAL}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% sort simply uses lists:sort, together with from_list and to_list sort(RAL) -> Len = len(RAL), from_list(lists:sort(to_list(RAL)),Len). sort(Compare,RAL) -> Len = len(RAL), from_list(lists:sort(Compare,to_list(RAL)),Len). %%% merge: collect the merged elements in reverse order in a regular list, %%% and then use from_list_reversed/2 to produce the final result. merge(RAL1,[]) -> RAL1; merge(RAL1,RAL2) -> merge_loop(RAL1, head(RAL2), RAL2, []). merge_loop([], _, RAL2, List) -> from_list_reversed(List,RAL2); merge_loop(RAL1, H2, RAL2, List) -> H1 = head(RAL1), if H1 =< H2 -> merge_loop(tail(RAL1), H2, RAL2, [H1|List]); true -> merge_loop(tail(RAL2), H1, RAL1, [H2|List]) end. merge(_Compare, RAL1, []) -> RAL1; merge(Compare, RAL1, RAL2) -> merge_loop(Compare, RAL1, head(RAL2), RAL2, []). merge_loop(_Compare, [], _, RAL2, List) -> from_list_reversed(List,RAL2); merge_loop(Compare, RAL1, H2, RAL2, List) -> H1 = head(RAL1), case Compare(H1, H2) of true -> merge_loop(Compare, tail(RAL1), H2, RAL2, [H1|List]); false -> merge_loop(Compare, tail(RAL2), H1, RAL1, [H2|List]) end. %%% s_member -- test for element in a sorted ralist s_member(Elt,RAL) -> Pred = fun(X) -> X =< Elt end, case binary_search(Pred,RAL) of false -> false; {true, X1} -> Elt =< X1 end. s_member(Compare, Elt, RAL) -> Pred = fun(X) -> Compare(X, Elt) end, case binary_search(Pred,RAL) of false -> false; {true, Value} -> case Compare(Elt,Value) of false -> false; true -> true end end. %%% s_locate -- find location of element in a sorted ralist s_locate(Elt,RAL) -> Pred = fun(X,_) -> X =< Elt end, case binary_search(Pred,RAL,1) of false -> {false, 0}; {true, I, XI} -> {Elt =< XI, I} end. s_locate(Compare,Elt,RAL) -> Pred = fun(X,_) -> Compare(X,Elt) end, case binary_search(Pred,RAL,1) of false -> {false, 0}; {true, I, Value} -> case Compare(Elt,Value) of false -> {false, I}; true -> {true, I} end end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Keyed tuple-list operations keymember(Key,N,Tuples) when integer(N), N > 0 -> Fun = fun(Tuple) -> element(N,Tuple) == Key end, linear_search(Fun,Tuples). keysearch(Key,N,Tuples) when integer(N), N > 0 -> Fun = fun(Tuple) when element(N,Tuple) == Key -> {value,Tuple}; (_) -> false end, linear_search(Fun,Tuples). %%% keylocate -- like keysearch, but returns {value,Pos,Tuple} when %%% the key is found, where Pos is the index of Tuple in the ralist. keylocate(Key,N,Tuples) when integer(N), N > 0 -> Fun = fun(Tuple,Pos) when element(N,Tuple) == Key -> {value,Pos,Tuple}; (_,_) -> false end, linear_search(Fun,Tuples,1). keydelete(Key,N,Tuples) -> case keylocate(Key,N,Tuples) of false -> Tuples; {value,Pos,_} -> delnth(Pos,Tuples) end. keyreplace(Key,N,Tuples,NewTuple) -> case keylocate(Key,N,Tuples) of false -> Tuples; {value,Pos,_} -> setelt(Pos,Tuples,NewTuple) end. keysort(N,Tuples) -> Compare = fun(T1,T2) -> element(N,T1) =< element(N,T2) end, sort(Compare, Tuples). keymerge(N,Tuples1,Tuples2) -> Compare = fun(T1,T2) -> element(N,T1) =< element(N,T2) end, merge(Compare, Tuples1, Tuples2). %%% s_keysearch -- like keysearch, but works on tuple %%% ralists which are sorted by key. s_keysearch(Key,N,Tuples) -> Pred = fun(T) -> element(N,T) =< Key end, case binary_search(Pred, Tuples) of false -> false; {true, Tuple} -> if element(N,Tuple) < Key -> false; true -> {value,Tuple} end end. %%% s_keylocate -- similar to keylocate, but works on tuple %%% ralists which are sorted by key, and has a different %%% return value when the key is not found. s_keylocate(Key,N,Tuples) -> Pred = fun(T,_) -> element(N,T) =< Key end, case binary_search(Pred, Tuples, 1) of false -> 0; {true, Pos, Tuple} -> if element(N,Tuple) < Key -> Pos; true -> {value,Pos,Tuple} end end. %%% s_keydelete -- like keydelete, but works with tuple ralists %%% which are sorted by key s_keydelete(Key,N,Tuples) -> case s_keylocate(Key,N,Tuples) of {value,Pos,_} -> %% Delete it delnth(Pos,Tuples); _Count -> %% Key not found Tuples end. %%% s_keyenter -- add or replace tuple in sorted tuple ralist s_keyenter(N,Tuples,NewTuple) -> case s_keylocate(element(N,NewTuple),N,Tuples) of {value,Pos,_} -> %% Replace with NewTuple setelt(Pos,Tuples,NewTuple); Count -> %% Insert NewTuple insnth(Count+1,Tuples,NewTuple) end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Standard list iterators: foreach/2 map/2 mapfoldl/3 mapfoldr/3 foreach(_Fun,[]) -> ok; foreach(Fun,[{Height,Tree}|Rest]) -> tree_foreach(Fun,Height,Tree), foreach(Fun,Rest). tree_foreach(Fun,1,X) -> Fun(X); tree_foreach(Fun,Height,{X,Tree1,Tree2}) -> Fun(X), tree_foreach(Fun,Height-1,Tree1), tree_foreach(Fun,Height-1,Tree2). map(_Fun,[]) -> []; map(Fun,[{Height,Tree}|Rest]) -> [{Height,tree_map(Fun,Height,Tree)} | map(Fun,Rest)]. tree_map(Fun,1,X) -> Fun(X); tree_map(Fun,Height,{X,Tree1,Tree2}) -> {Fun(X), tree_map(Fun,Height-1,Tree1), tree_map(Fun,Height-1,Tree2)}. flatmap(_Fun,[]) -> []; flatmap(Fun,[{Height,Tree}|Rest]) -> tree_flatmap(Fun,Height,Tree,flatmap(Fun,Rest)). tree_flatmap(Fun,1,X,Tail) -> lists:foldr(fun cons/2,Tail,Fun(X)); tree_flatmap(Fun,Height,{X,Tree1,Tree2},Tail) -> Tail1 = tree_flatmap(Fun,Height-1,Tree2,Tail), Tail2 = tree_flatmap(Fun,Height-1,Tree1,Tail1), lists:foldr(fun cons/2, Tail2, Fun(X)). mapfoldl(_Fun,Acc,[]) -> {[], Acc}; mapfoldl(Fun,Acc,[{Height,Tree}|Rest]) -> {NewTree,Acc1} = tree_mapfoldl(Fun,Acc,Height,Tree), {NewRest,Acc2} = mapfoldl(Fun,Acc1,Rest), {[{Height,NewTree}|NewRest], Acc2}. tree_mapfoldl(Fun,Acc,1,X) -> Fun(X,Acc); tree_mapfoldl(Fun,Acc,Height,{X,Tree1,Tree2}) -> {NewX,Acc1} = Fun(X,Acc), {NewTree1,Acc2} = tree_mapfoldl(Fun,Acc1,Height-1,Tree1), {NewTree2,Acc3} = tree_mapfoldl(Fun,Acc2,Height-1,Tree2), {{NewX,NewTree1,NewTree2},Acc3}. mapfoldr(_Fun,Acc,[]) -> {[], Acc}; mapfoldr(Fun,Acc,[{Height,Tree}|Rest]) -> {NewRest,Acc1} = mapfoldr(Fun,Acc,Rest), {NewTree,Acc2} = tree_mapfoldr(Fun,Acc1,Height,Tree), {[{Height,NewTree}|NewRest], Acc2}. tree_mapfoldr(Fun,Acc,1,X) -> Fun(X,Acc); tree_mapfoldr(Fun,Acc,Height,{X,Tree1,Tree2}) -> {NewTree2, Acc1} = tree_mapfoldr(Fun,Acc,Height-1,Tree2), {NewTree1, Acc2} = tree_mapfoldr(Fun,Acc1,Height-1,Tree1), {NewX, Acc3} = Fun(X,Acc2), {{NewX,NewTree1,NewTree2}, Acc3}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% foldl -- in addition to the standard version, optional %%% "Start" and "Length" parameters may be provided. These restrict %%% the range of elements which are "folded" into the value. %%% %%% NB: "Start" is based at 1, and "Length" defaults to the whole list, %%% e.g. ral:foldl(Fun,Acc0,RAL,Start,Len) is equivalent to %%% ral:foldl(Fun,Acc0,ral:sublist(RAL,Start,Len)), but doesn't do %%% the extra copying implicit in the "sublist" operation (and actually %%% sublist is implemented using foldr/5). foldl(Fun,Acc,RAL,Start) -> foldl_s(Fun,Acc,RAL,Start). foldl(Fun,Acc,RAL,Start,Len) -> foldl_sl(Fun,Acc,RAL,Start,Len). foldl(_Fun,Acc,[]) -> Acc; foldl(Fun,Acc,[{Height,Tree}|Rest]) -> Acc1 = tree_foldl(Fun,Acc,Height,Tree), foldl(Fun,Acc1,Rest). foldl_s(Fun,Acc,RAL,1) -> foldl(Fun,Acc,RAL); foldl_s(Fun,Acc,[{Height,Tree}|Rest],Start) -> Size = ?tsize(Height), if Start > Size -> foldl_s(Fun,Acc,Rest,Start-Size); true -> Acc1 = tree_foldl_s(Fun,Acc,Height,Tree,Start), foldl(Fun,Acc1,Rest) end. foldl_l(_Fun,Acc,_,0) -> Acc; foldl_l(Fun,Acc,[{Height,Tree}|Rest],Len) -> Size = ?tsize(Height), if Len < Size -> tree_foldl_l(Fun,Acc,Height,Tree,Len); true -> Acc1 = tree_foldl(Fun,Acc,Height,Tree), foldl_l(Fun,Acc1,Rest,Len-Size) end. foldl_sl(Fun,Acc,RAL,1,Len) -> foldl_l(Fun,Acc,RAL,Len); foldl_sl(Fun,Acc,[{Height,Tree}|Rest],Start,Len) -> Size = ?tsize(Height), if Start > Size -> foldl_sl(Fun,Acc,Rest,Start-Size,Len); Start+Len-1 =< Size -> tree_foldl_sl(Fun,Acc,Height,Tree,Start,Len); true -> Acc1 = tree_foldl_s(Fun,Acc,Height,Tree,Start), foldl_l(Fun,Acc1,Rest,Start+Len-Size-1) end. tree_foldl(Fun,Acc,1,X) -> Fun(X,Acc); tree_foldl(Fun,Acc,Height,{X,Tree1,Tree2}) -> Acc1 = Fun(X,Acc), Acc2 = tree_foldl(Fun,Acc1,Height-1,Tree1), tree_foldl(Fun,Acc2,Height-1,Tree2). tree_foldl_s(Fun,Acc,Height,Tree,1) -> tree_foldl(Fun,Acc,Height,Tree); tree_foldl_s(Fun,Acc,Height,{_,Tree1,Tree2},Start) -> Size1 = ?tsize_plus_one(Height-1), if Start > Size1 -> tree_foldl_s(Fun,Acc,Height-1,Tree2,Start-Size1); true -> Acc1 = tree_foldl_s(Fun,Acc,Height-1,Tree1,Start-1), tree_foldl(Fun,Acc1,Height-1,Tree2) end. tree_foldl_l(_Fun,Acc,_,_,0) -> Acc; tree_foldl_l(Fun,Acc,1,X,1) -> Fun(X,Acc); tree_foldl_l(Fun,Acc,Height,{X,Tree1,Tree2},Len) -> Acc1 = Fun(X,Acc), Size1 = ?tsize_plus_one(Height-1), if Len < Size1 -> tree_foldl_l(Fun,Acc1,Height-1,Tree1,Len-1); true -> Acc2 = tree_foldl(Fun,Acc1,Height-1,Tree1), tree_foldl_l(Fun,Acc2,Height-1,Tree2,Len-Size1) end. tree_foldl_sl(Fun,Acc,Height,Tree,1,Len) -> tree_foldl_l(Fun,Acc,Height,Tree,Len); tree_foldl_sl(Fun,Acc,Height,{_,Tree1,Tree2},Start,Len) -> Size1 = ?tsize_plus_one(Height-1), if Start > Size1 -> tree_foldl_sl(Fun,Acc,Height-1,Tree2,Start-Size1,Len); Start+Len-1 =< Size1 -> tree_foldl_sl(Fun,Acc,Height-1,Tree1,Start-1,Len); true -> Acc1 = tree_foldl_s(Fun,Acc,Height-1,Tree1,Start-1), tree_foldl_l(Fun,Acc1,Height-1,Tree2,Start+Len-1-Size1) end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% foldr -- see the remarks pertaining to foldl (just the same) foldr(Fun,Acc,RAL,Start) -> foldr_s(Fun,Acc,RAL,Start). foldr(Fun,Acc,RAL,Start,Len) -> foldr_sl(Fun,Acc,RAL,Start,Len). foldr(_Fun,Acc,[]) -> Acc; foldr(Fun,Acc,[{Height,Tree}|Rest]) -> Acc1 = foldr(Fun,Acc,Rest), tree_foldr(Fun,Acc1,Height,Tree). foldr_s(Fun,Acc,RAL,1) -> foldr(Fun,Acc,RAL); foldr_s(Fun,Acc,[{Height,Tree}|Rest],Start) -> Size = ?tsize(Height), if Start > Size -> foldr_s(Fun,Acc,Rest,Start-Size); true -> Acc1 = foldr(Fun,Acc,Rest), tree_foldr_s(Fun,Acc1,Height,Tree,Start) end. foldr_l(_Fun,Acc,_,0) -> Acc; foldr_l(Fun,Acc,[{Height,Tree}|Rest],Len) -> Size = ?tsize(Height), if Len < Size -> tree_foldr_l(Fun,Acc,Height,Tree,Len); true -> Acc1 = foldr_l(Fun,Acc,Rest,Len-Size), tree_foldr(Fun,Acc1,Height,Tree) end. foldr_sl(Fun,Acc,RAL,1,Len) -> foldr_l(Fun,Acc,RAL,Len); foldr_sl(Fun,Acc,[{Height,Tree}|Rest],Start,Len) -> Size = ?tsize(Height), if Start > Size -> foldr_sl(Fun,Acc,Rest,Start-Size,Len); Start+Len-1 =< Size -> tree_foldr_sl(Fun,Acc,Height,Tree,Start,Len); true -> Acc1 = foldr_l(Fun,Acc,Rest,Start+Len-Size-1), tree_foldr_s(Fun,Acc1,Height,Tree,Start) end. tree_foldr(Fun,Acc,1,X) -> Fun(X,Acc); tree_foldr(Fun,Acc,Height,{X,Tree1,Tree2}) -> Acc1 = tree_foldr(Fun,Acc,Height-1,Tree2), Acc2 = tree_foldr(Fun,Acc1,Height-1,Tree1), Fun(X,Acc2). tree_foldr_s(Fun,Acc,Height,Tree,1) -> tree_foldr(Fun,Acc,Height,Tree); tree_foldr_s(Fun,Acc,Height,{_,Tree1,Tree2},Start) -> Size1 = ?tsize_plus_one(Height-1), if Start > Size1 -> tree_foldr_s(Fun,Acc,Height-1,Tree2,Start-Size1); true -> Acc1 = tree_foldr(Fun,Acc,Height-1,Tree2), tree_foldr_s(Fun,Acc1,Height-1,Tree1,Start-1) end. tree_foldr_l(_Fun,Acc,_,_,0) -> Acc; tree_foldr_l(Fun,Acc,1,X,1) -> Fun(X,Acc); tree_foldr_l(Fun,Acc,Height,{X,Tree1,Tree2},Len) -> Size1 = ?tsize_plus_one(Height-1), if Len < Size1 -> Acc1 = tree_foldr_l(Fun,Acc,Height-1,Tree1,Len-1), Fun(X,Acc1); true -> Acc1 = tree_foldr_l(Fun,Acc,Height-1,Tree2,Len-Size1), Acc2 = tree_foldr(Fun,Acc1,Height-1,Tree1), Fun(X,Acc2) end. tree_foldr_sl(Fun,Acc,Height,Tree,1,Len) -> tree_foldr_l(Fun,Acc,Height,Tree,Len); tree_foldr_sl(Fun,Acc,Height,{_,Tree1,Tree2},Start,Len) -> Size1 = ?tsize_plus_one(Height-1), if Start > Size1 -> tree_foldr_sl(Fun,Acc,Height-1,Tree2,Start-Size1,Len); Start+Len-1 =< Size1 -> tree_foldr_sl(Fun,Acc,Height-1,Tree1,Start-1,Len); true -> Acc1 = tree_foldr_l(Fun,Acc,Height-1,Tree2,Start+Len-1-Size1), tree_foldr_s(Fun,Acc1,Height-1,Tree1,Start-1) end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% cfoldl, cfoldr -- generalised foldl/foldr that allow early %%% termination of the iteration, via a condition applied to the %%% "accumulator". Note that the condition may be called multiple %%% times for the same accumulator, if it returns false. So the %%% "Cond" function should be cheap and side-effect free (typically %%% it is just a pattern match test). cfoldl(_Cond,_Fun,Acc,[]) -> Acc; cfoldl(Cond,Fun,Acc,[{Height,Tree}|Rest]) -> case Cond(Acc) of false -> Acc; true -> Acc1 = tree_cfoldl(Cond,Fun,Acc,Height,Tree), cfoldl(Cond,Fun,Acc1,Rest) end. tree_cfoldl(_Cond,Fun,Acc,1,X) -> Fun(X,Acc); tree_cfoldl(Cond,Fun,Acc,Height,{X,Tree1,Tree2}) -> Acc1 = Fun(X,Acc), case Cond(Acc1) of false -> Acc1; true -> Acc2 = tree_cfoldl(Cond,Fun,Acc1,Height-1,Tree1), case Cond(Acc2) of false -> Acc2; true -> tree_cfoldl(Cond,Fun,Acc2,Height-1,Tree2) end end. cfoldr(_Cond,_Fun,Acc,[]) -> Acc; cfoldr(Cond,Fun,Acc,[{Height,Tree}|Rest]) -> Acc1 = cfoldr(Cond,Fun,Acc,Rest), case Cond(Acc1) of false -> Acc1; true -> tree_cfoldr(Cond,Fun,Acc1,Height,Tree) end. tree_cfoldr(_Cond,Fun,Acc,1,X) -> Fun(X,Acc); tree_cfoldr(Cond,Fun,Acc,Height,{X,Tree1,Tree2}) -> Acc1 = tree_cfoldr(Cond,Fun,Acc,Height-1,Tree2), case Cond(Acc1) of false -> Acc1; true -> Acc2 = tree_cfoldr(Cond,Fun,Acc1,Height-1,Tree1), case Cond(Acc2) of false -> Acc2; true -> Fun(X,Acc2) end end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% linear_search(Pred,RAL) -- search (linearly) for an element %%% satisfying "Pred". Pred needn't be a proper predicate; if it %%% returns any value other than "false", then the search is halted %%% with that as its value. linear_search(_,[]) -> false; linear_search(Pred,[{Height,Tree}|Rest]) -> case tree_linear_search(Pred, Height, Tree) of false -> linear_search(Pred,Rest); OtherValue -> OtherValue end. tree_linear_search(Pred,1,X) -> Pred(X); tree_linear_search(Pred,Height,{X,Tree1,Tree2}) -> case Pred(X) of false -> case tree_linear_search(Pred,Height-1,Tree1) of false -> tree_linear_search(Pred,Height-1,Tree2); OtherValue -> OtherValue end; OtherValue -> OtherValue end. %%% linear_search(Pred,RAL,I) -- like linear_search, but passes in %%% the value I+Offset as a second argument to Pred, where offset %%% is the offset from the start of the ralist of the element being %%% tested. linear_search(_,[],_) -> false; linear_search(Pred,[{Height,Tree}|Rest],I) -> case tree_linear_search(Pred, Height, Tree, I) of false -> linear_search(Pred,Rest,I+?tsize(Height)); OtherValue -> OtherValue end. tree_linear_search(Pred,1,X,I) -> Pred(X,I); tree_linear_search(Pred,Height,{X,Tree1,Tree2},I) -> case Pred(X,I) of false -> case tree_linear_search(Pred,Height-1,Tree1,I+1) of false -> tree_linear_search(Pred,Height-1,Tree2, I+?tsize_plus_one(Height-1)); OtherValue -> OtherValue end; OtherValue -> OtherValue end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% binary_search(Pred,RAL) -- find the last elt in RAL for which Pred %%% is true, where RAL is "sorted" wrt Pred, i.e. some (possibly empty) %%% initial set of elts satisfy Pred, and the rest don't. binary_search(_Pred, []) -> false; binary_search(Pred, [{Height,Tree}|Rest]) -> %% Most of the elements (at least half) are in the last tree, so start %% the search there, and move back to the first tree. case binary_search(Pred,Rest) of false -> tree_bsearch_r(Pred,Height,Tree); Value -> Value end. tree_bsearch_r(Pred,1,X) -> %% Singleton trees are easy case Pred(X) of false -> false; Other -> {Other, X} end; tree_bsearch_r(Pred,Height,{X,Tree1,Tree2}) -> %% Start by checking the initial (smallest) element first; if it %% doesn't pass, then we can skip the whole tree. case Pred(X) of false -> false; true -> %% Skip to Tree2 (you don't want a linear search, do you?) case tree_bsearch_r(Pred,Height-1,Tree2) of false -> %% Need to recurse into Tree1 case tree_bsearch_l(Pred,Height-1,Tree1) of false -> %% X is the element we're looking for {true,X}; Value -> Value end; Value -> Value end; Other -> %% Non-boolean return values terminate the search {Other, X} end. %%% tree_bsearch_l is functionally identical to tree_bsearch_r, but it %%% defers the check on the initial element (to reduce the number of %%% compares needed, on average). tree_bsearch_l(Pred,1,X) -> case Pred(X) of false -> false; Other -> {Other, X} end; tree_bsearch_l(Pred,Height,{X,Tree1,Tree2}) -> case tree_bsearch_r(Pred,Height-1,Tree2) of false -> case tree_bsearch_l(Pred,Height-1,Tree1) of false -> case Pred(X) of false -> false; Other -> {Other, X} end; Value -> Value end; Value -> Value end. %%% binary_search/3 -- just like binary_search/2, but takes a base "index" %%% value, which is incremented by the offset of the element in the list %%% and passed as a second argument to the predicate. Also, the "I" %%% value is included in the return value (when it is not false). binary_search(_Pred, [], _) -> false; binary_search(Pred, [{Height,Tree}|Rest], I) -> case binary_search(Pred,Rest,I+?tsize(Height)) of false -> tree_bsearch_r(Pred,Height,Tree,I); Value -> Value end. tree_bsearch_r(Pred,1,X,I) -> case Pred(X,I) of false -> false; Other -> {Other, I, X} end; tree_bsearch_r(Pred,Height,{X,Tree1,Tree2},I) -> case Pred(X,I) of false -> false; true -> case tree_bsearch_r(Pred,Height-1,Tree2, I+?tsize_plus_one(Height-1)) of false -> case tree_bsearch_l(Pred,Height-1,Tree1,I+1) of false -> {true,I,X}; Value -> Value end; Value -> Value end; Other -> {Other, I, X} end. tree_bsearch_l(Pred,1,X,I) -> case Pred(X,I) of false -> false; Other -> {Other, I, X} end; tree_bsearch_l(Pred,Height,{X,Tree1,Tree2},I) -> case tree_bsearch_r(Pred,Height-1,Tree2, I+?tsize_plus_one(Height-1)) of false -> case tree_bsearch_l(Pred,Height-1,Tree1,I+1) of false -> case Pred(X,I) of false -> false; Other -> {Other,I,X} end; Value -> Value end; Value -> Value end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Other functions, ala the "lists" module. append(RAL1,[]) -> RAL1; append(RAL1,RAL2) -> foldr(fun cons/2, RAL2, RAL1). %%% NB: append/1 takes a _list_ of ralists, _not_ an ralist of ralists. append(RALs) -> lists:foldr(fun append/2, [], RALs). reverse(RAL) -> reverse(RAL, []). reverse(RAL1,RAL2) -> foldl(fun cons/2, RAL2, RAL1). sublist(RAL,Len) -> sublist(RAL,1,Len). sublist(RAL,Start,Len) -> foldr(fun cons/2, [], RAL, Start, Len). member(X,RAL) -> linear_search(fun(Y) -> Y =:= X end, RAL). any(Pred,RAL) -> %% NB: The case is to generate an error when Pred returns a non-boolean case linear_search(Pred,RAL) of false -> false; true -> true end. all(Pred,RAL) -> not linear_search(fun(X) -> not Pred(X) end, RAL). sum(RAL) -> foldl(fun(X,Sum) -> Sum+X end, 0, RAL). min(RAL) -> foldl(fun(X,Min) when X < Min -> X; (_,Min) -> Min end, head(RAL), RAL, 2). max(RAL) -> foldl(fun(X,Max) when X > Max -> X; (_,Max) -> Max end, head(RAL), RAL, 2). delete(Y,RAL) -> case locate(Y,RAL) of false -> RAL; Pos -> delnth(Pos,RAL) end. %%% WARNING: this implementation of subtract can be _very_ inefficient. subtract(RAL1,RAL2) -> foldl(fun delete/2, RAL1, RAL2). locate_split(Pred,RAL) -> Fun = fun(X,Offset) -> case Pred(X) of true -> false; false -> Offset end end, linear_search(Fun,RAL,0). takewhile(Pred,RAL) -> case locate_split(Pred,RAL) of false -> RAL; N -> take(N,RAL) end. dropwhile(Pred,RAL) -> case locate_split(Pred,RAL) of false -> []; N -> drop(N,RAL) end. splitwith(Pred,RAL) -> case locate_split(Pred,RAL) of false -> {RAL,[]}; N -> split(N,RAL) end. filter(Pred,RAL) -> %% NB: The order of evaluation may not be what you expect! Fun = fun(X,Acc) -> case Pred(X) of true -> cons(X,Acc); false -> Acc end end, foldr(Fun,[],RAL).