%%% -*- 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).