% File : LOGARR.PL % Author : Mostly David H.D.Warren, some changes by Fernando Pereira % Updated: 24 September 1984 % Purpose: Extendable arrays with logarithmic access time. /* LOGARITHMIC ARRAYS. An array extends from 0 to 2**Size - 1, where Size is a multiple of 2. Note that 2**Size = 1<>N /\ 3, array_item(Subindex, N, Index, Array, Item). array_to_list(array(\$(A0,A1,A2,A3),Size), L0) :- N is Size-2, subarray_to_list(0, N, 0, A0, L0, L1), subarray_to_list(1, N, 0, A1, L1, L2), subarray_to_list(2, N, 0, A2, L2, L3), subarray_to_list(3, N, 0, A3, L3, []). arefa(Index, array(Array,Size), Item) :- check_int(Index), Index < 1<>N /\ 3, array_item(Subindex, N, Index, Array, Item), !. arefa(_, _, Item) :- new_array(Item). arefl(Index, array(Array,Size), Item) :- check_int(Index), Index < 1<>N /\ 3, array_item(Subindex, N, Index, Array, Item), !. arefl(_, _, []). aset(Index, array(Array0,Size0), Item, array(Array,Size)) :- check_int(Index), enlarge_array(Index, Size0, Array0, Size, Array1), update_array_item(Size, Index, Array1, Item, Array). check_int(I) :- integer(I), !. check_int(X) :- write('Array index not integer: '), write(X), nl, trace, fail. % Guts enlarge_array(I, Size, Array, Size, Array) :- I < 1<> N1 /\ 3, array_item(Subindex, N1, Index, Array, Item). array_item(1, 0, _, \$(_,Item,_,_), Item) :- !, not_undef(Item). array_item(1, N, Index, \$(_,Array,_,_), Item) :- N1 is N-2, Subindex is Index >> N1 /\ 3, array_item(Subindex, N1, Index, Array, Item). array_item(2, 0, _, \$(_,_,Item,_), Item) :- !, not_undef(Item). array_item(2, N, Index, \$(_,_,Array,_), Item) :- N1 is N-2, Subindex is Index >> N1 /\ 3, array_item(Subindex, N1, Index, Array, Item). array_item(3, 0, _, \$(_,_,_,Item), Item) :- !, not_undef(Item). array_item(3, N, Index, \$(_,_,_,Array), Item) :- N1 is N-2, Subindex is Index >> N1 /\ 3, array_item(Subindex, N1, Index, Array, Item). not_undef(\$) :- !, fail. not_undef(_). %% [BEFORE OPEN-CODING 'subarray'] %% %% array_item(0,Index,Item,Item) :- !, %% not_undef(Item). %% array_item(N,Index,Array,Item) :- %% N1 is N-2, %% Subindex is Index >> N1 /\ 3, %% subarray(Subindex,Array,Array1), %% array_item(N1,Index,Array1,Item). %% %% subarray(0,\$(X,_,_,_),X). %% subarray(1,\$(_,X,_,_),X). %% subarray(2,\$(_,_,X,_),X). %% subarray(3,\$(_,_,_,X),X). update_array_item(0, _, _, NewItem, NewItem) :- !. update_array_item(N, Index, Array, NewItem, NewArray) :- N1 is N-2, Subindex is Index >> N1 /\ 3, update_subarray(Subindex, Array, Array1, NewArray1, NewArray), update_array_item(N1, Index, Array1, NewItem, NewArray1). update_subarray(I, \$, X, X1, Array) :- !, update_subarray(I, \$(\$,\$,\$,\$), X, X1, Array). update_subarray(0, \$(W,X,Y,Z), W, W1, \$(W1,X,Y,Z)). update_subarray(1, \$(W,X,Y,Z), X, X1, \$(W,X1,Y,Z)). update_subarray(2, \$(W,X,Y,Z), Y, Y1, \$(W,X,Y1,Z)). update_subarray(3, \$(W,X,Y,Z), Z, Z1, \$(W,X,Y,Z1)). subarray_to_list(K, 0, M, Item, [N-Item|L], L) :- not_undef(Item), !, N is K+M. subarray_to_list(K, N, M, \$(A0,A1,A2,A3), L0, L) :- N > 0, !, N1 is N-2, M1 is (K+M) << 2, subarray_to_list(0, N1, M1, A0, L0, L1), subarray_to_list(1, N1, M1, A1, L1, L2), subarray_to_list(2, N1, M1, A2, L2, L3), subarray_to_list(3, N1, M1, A3, L3, L). subarray_to_list(_, _, _, _, L, L).