1
2:- module(arrays).			% SEPIA header
3:- export
4	array_length/2,
5	array_to_list/2,
6	fetch/3,
7	list_to_array/2,
8	store/4.
9
10
11%   File   : ARRAYS.PL
12%   Author : R.A.O'Keefe
13%   Updated: 8 November 1983
14%   Purpose: Updatable arrays in Prolog.
15
16%   In this package an array is represented in the following notation
17%   {1,2,3} is shown initially as
18%   array([1|_1],[2|_2],[3|_3])+0
19%   where the [1|_1] etc. are lists in which the most recent value for
20%   the element comes last, and the +0 is a zero updates count.
21%   Updating the 2nd element to a 5 for example would make the array into
22%   array([1|_1],[2,5|_2],[3|_3])+1
23%   Function "list_to_array" converts list e.g. [1,2,3,4] to array in
24%   this format, "array_to_list" converts back.
25%   fetch(+N,+A,-Elem)      Fetches Nth element
26%   store(+N,+A,+Elem,+NewA)    Stores Elem at Nth element of A giving NewA
27
28/*  These operations are fully described in
29    "Updatable Arrays in Prolog", R.A.O'Keefe, DAI Working Paper 150.
30    Note that store(Index, Old, Elem, New) sometimes side-effects Old and
31    sometimes doesn't; you cannot rely on Old remaining unchanged.
32    (i.e. uninstantiated arguments in Old may become instantiated.)
33    This is NOT an example of logic programming.  For a logic programming
34    solution (with cost O(lgN) rather O(1)) see Trees.Pl.
35*/
36
37array_length(Array+_, Length) :-
38    functor(Array, array, Length).
39
40
41array_to_list(Array+_, List) :-
42    Array =.. [array|Wrapped],
43    un_wrap(Wrapped, List).
44
45un_wrap([History|Histories], [Element|Elements]) :-
46    get_last(History, Element),
47    !,
48    un_wrap(Histories, Elements).
49
50un_wrap([], []).
51
52
53fetch(Index, Array+_, Element) :-
54    arg(Index, Array, History),
55    get_last(History, Element).
56
57get_last([Head|Tail], Element) :-
58    var(Tail),
59    !,
60    Element = Head.
61
62get_last([_|Tail], Element) :-
63    get_last(Tail, Element).
64
65
66list_to_array(List, Array+0) :-
67    wrap_up(List, Wrapped),
68    Array =.. [array|Wrapped].
69
70wrap_up([Element|Elements], [[Element|_]|Wrapped]) :- !,
71    wrap_up(Elements, Wrapped).
72
73wrap_up([], []).
74
75
76store(Index, Array+Updates, Element, NewArray+NewUpdates) :-
77    functor(Array, array, Length),
78    arg(Index, Array, History),
79    put_last(History, Element),
80    K is Updates+1,
81    !,
82    store(Length, K, NewUpdates, Array, NewArray).
83
84store(N, N, 0, Old, New) :- !,
85    Old =.. [array|OldList],
86    un_wrap(OldList, MidList),
87    !,
88    wrap_up(MidList, NewList),
89    New =.. [array|NewList].
90
91store(_, U, U, Array, Array).
92
93put_last(History, Element) :-
94    var(History),
95    !,
96    History = [Element|_].
97put_last([_|History], Element) :-
98    put_last(History, Element).
99
100