/* 

  Port of R.A.O'Keefe' Prolog arrays.pl package in Picat v3.

  From http://www.picat-lang.org/bprolog/publib/arrays.html
  """
  File   : ARRAYS.PL
  Author : R.A.O'Keefe
  Updated: 8 November 1983
  Purpose: Updatable arrays in Prolog.

  In this package an array is represented in the following notation
	{1,2,3} is shown initially as
	array([1|_1],[2|_2],[3|_3])+0
  where the [1|_1] etc. are lists in which the most recent value for
  the element comes last, and the +0 is a zero updates count.
  Updating the 2nd element to a 5 for example would make the array into
	array([1|_1],[2,5|_2],[3|_3])+1
  Function "list_to_array" converts list e.g. [1,2,3,4] to array in
  this format, "array_to_list" converts back.
  fetch(+N,+A,-Elem)		Fetches Nth element
  store(+N,+A,+Elem,+NewA)	Stores Elem at Nth element of A giving NewA
  """

  This model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import v3_utils.

test ?=>
  A = $array([1|_1],[2|_2],[3|_3])+0,
  portray_clause(A),
  
  array_length(A,ArrayLength),
  println(array_length=ArrayLength),

  array_to_list(A,ArrayToList),
  println(array_to_list=ArrayToList),

  list_to_array(10..-1..1,ListToArray),
  portray_clause(list_to_array=ListToArray),

  fetch(3,ListToArray,Element3),
  println(fetch_3=Element3),

  % Note: store42At3=array([1|_],[2|_],[3,42|_])+1.
  store(3,A,42,Store42At3),
  portray_clause(store42At3=Store42At3),

  % Note: store42At3AsList=[1,2,42]
  array_to_list(Store42At3,Store42At3AsList),
  portray_clause(store42At3AsList=Store42At3AsList),


  nl.
test => true.


%   File   : ARRAYS.PL
%   Author : R.A.O'Keefe
%   Updated: 8 November 1983
%   Purpose: Updatable arrays in Prolog.

%   In this package an array is represented in the following notation
%	{1,2,3} is shown initially as
%	array([1|_1],[2|_2],[3|_3])+0
%   where the [1|_1] etc. are lists in which the most recent value for
%   the element comes last, and the +0 is a zero updates count.
%   Updating the 2nd element to a 5 for example would make the array into
%	array([1|_1],[2,5|_2],[3|_3])+1
%   Function "list_to_array" converts list e.g. [1,2,3,4] to array in
%   this format, "array_to_list" converts back.
%   fetch(+N,+A,-Elem)		Fetches Nth element
%   store(+N,+A,+Elem,+NewA)	Stores Elem at Nth element of A giving NewA

/*  These operations are fully described in
	"Updatable Arrays in Prolog", R.A.O'Keefe, DAI Working Paper 150.
    Note that store(Index, Old, Elem, New) sometimes side-effects Old and
    sometimes doesn't; you cannot rely on Old remaining unchanged.
    (i.e. uninstantiated arguments in Old may become instantiated.)
    This is NOT an example of logic programming.  For a logic programming
    solution (with cost O(lgN) rather O(1)) see Trees.Pl.
*/

array_length(Array+_, Length) :-
	functor(Array, array, Length).


array_to_list(Array+_, List) :-
	Array =.. [array|Wrapped],
	un_wrap(Wrapped, List).

un_wrap([History|Histories], [Element|Elements]) :-
	get_last(History, Element),
	!,
	un_wrap(Histories, Elements).

un_wrap([], []).


fetch(Index, Array+_, Element) :-
	arg(Index, Array, History),
	get_last(History, Element).

get_last([Head|Tail], Element) :-
	var(Tail),
	!,
	Element = Head.

get_last([_|Tail], Element) :-
	get_last(Tail, Element).


list_to_array(List, Array+0) :-
	wrap_up(List, Wrapped),
	Array =.. [array|Wrapped].

wrap_up([Element|Elements], [[Element|_]|Wrapped]) :- !,
	wrap_up(Elements, Wrapped).

wrap_up([], []).


store(Index, Array+Updates, Element, NewArray+NewUpdates) :-
	functor(Array, array, Length),
	arg(Index, Array, History),
	put_last(History, Element),
	K is Updates+1,
	!,
	store(Length, K, NewUpdates, Array, NewArray).

store(N, N, 0, Old, New) :- !,
	Old =.. [array|OldList],
	un_wrap(OldList, MidList),
	!,
	wrap_up(MidList, NewList),
	New =.. [array|NewList].

store(_, U, U, Array, Array).

put_last(History, Element) :-
	var(History),
	!,
	History = [Element|_].
put_last([_|History], Element) :-
	put_last(History, Element).