/* array.pure: integer-indexed arrays implemented as size-balanced
   binary trees. */

/* Copyright (c) 2008 by Albert Graef <Dr.Graef@t-online.de>.

   This file is part of the Pure programming language and system.

   Pure is free software: you can redistribute it and/or modify it under the
   terms of the GNU General Public License as published by the Free Software
   Foundation, either version 3 of the License, or (at your option) any later
   version.

   Pure is distributed in the hope that it will be useful, but WITHOUT ANY
   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
   details.

   You should have received a copy of the GNU General Public License along
   with this program.  If not, see <http://www.gnu.org/licenses/>. */

/* This script implements an efficient variable-sized array data structure
   which allows to access and update individual array members, as well as
   to add and remove elements at the beginning and end of an array. All these
   operations are carried out in logarithmic time. */

/* Public operations: ******************************************************

   emptyarray           return the empty array
   array xs             create an array from a list xs
   array2 xs            create a two-dimensional array from a list of lists
   mkarray x n          create an array consisting of n x's
   mkarray2 x (n,m)     create a 2D array of n*m x's
   arrayp x             check whether x is an array

   #a                   size of a
   a!i                  return ith member of a
   a!(i,j)              two-dimensional subscript

   null a               tests whether a is the empty array
   members a            list of values stored in a
   members2 a           list of members in a two-dimensional array

   first a, last a      first and last member of A
   rmfirst a, rmlast a  remove first and last member from a
   insert a x           insert x at the beginning of a
   append a x           append x to the end of a
   update a i x         replace the ith member of a by x
   update2 a (i,j) x    update two-dimensional array

   *************************************************************************/

/* Tree constructors. */
private nullary nil;
private tip bin;

private mkbin;

// array type check
arrayp (Array _)                = 1;
arrayp _                        = 0;

// create an empty array
emptyarray                      = Array nil;

// create an array from a list
array xs                        = foldl append emptyarray xs if listp xs;

// create a two-dimensional array from a two-dimensional list
array2 xs                       = array (map array xs);

// create an array of a given size filled with a constant value
mkarray x n::int                = Array (mkarray x n)
with
  mkarray x n::int              = nil if n <= 0;
                                = tip x if n == 1;
                                = mkbin (n mod 2)
                                  (mkarray x (n - n div 2))
                                  (mkarray x (n div 2));
end;

// create a 2D array of given dimensions filled with a constant value
mkarray2 x (n::int, m::int)     = mkarray (mkarray x m) n;

// get array size
#(Array a)                      = #a
with
  #nil                          = 0;
  #(tip _)                      = 1;
  #(bin 0 a1 _)                 = #a1 * 2;
  #(bin 1 a1 _)                 = #a1 * 2 - 1;
end;

// get value by index
(Array a)!i::int                = a!i
with
  (tip x)!0                     = x;
  (bin _ a1 a2)!i::int          = a1!(i div 2) if i mod 2 == 0;
                                = a2!(i div 2) if i mod 2 == 1;
  _ ! _                         = throw out_of_bounds;
end;

// get value by indices from two-dimensional array
x@(Array _)!(i::int, j::int)    = x!i!j;

// check for an empty array
null (Array nil)                = 1;
null (Array _)                  = 0;

// get all array members in list form
members (Array a)               = members a
with
  members nil                   = [];
  members (tip x)               = [x];
  members (bin _ a1 a2)         = merge (members a1) (members a2);
  // merge lists xs (even elements) and ys (odd elements)
  merge [] ys                   = ys;
  merge (x:xs) ys               = x:merge ys xs;
end;

// get all members of an two-dimensional array in list form
members2 x@(Array _)            = map members (members x);

// get the first array member
first (Array a)         = first a
with
  first (tip x)                 = x;
  first (bin _ a1 _)            = first a1;
end;

// get the last array member
last (Array a)                  = last a
with
  last (tip x)                  = x;
  last (bin 0 _ a2)             = last a2;
  last (bin 1 a1 _)             = last a1;
end;

// remove the first member from an array
rmfirst (Array a)               = Array (rmfirst a)
with
  rmfirst (tip _)               = nil;
  rmfirst (bin 0 a1 a2)         = mkbin 1 a2 (rmfirst a1);
  rmfirst (bin 1 a1 a2)         = mkbin 0 a2 (rmfirst a1);
end;

// remove the last member from an array
rmlast (Array a)                = Array (rmlast a)
with
  rmlast (tip _)                = nil;
  rmlast (bin 0 a1 a2)          = mkbin 1 a1 (rmlast a2);
  rmlast (bin 1 a1 a2)          = mkbin 0 (rmlast a1) a2;
end;

// insert a new member at the beginning of an array
insert (Array a) y              = Array (insert a y)
with
  insert nil y                  = tip y;
  insert (tip x) y              = bin 0 (tip y) (tip x);
  insert (bin 0 a1 a2) y        = mkbin 1 (insert a2 y) a1;
  insert (bin 1 a1 a2) y        = mkbin 0 (insert a2 y) a1;
end;

// append a new member at the end of an array
append (Array a) y              = Array (append a y)
with
  append nil y                  = tip y;
  append (tip x) y              = bin 0 (tip x) (tip y);
  append (bin 0 a1 a2) y        = mkbin 1 (append a1 y) a2;
  append (bin 1 a1 a2) y        = mkbin 0 a1 (append a2 y);
end;

// update a given array position with a new value
update (Array a) i::int y       = Array (update a i y)
with
  update (tip _) 0 y            = tip y;
  update (bin b::int a1 a2) i::int y
                                = bin b (update a1 (i div 2) y) a2
                                    if i mod 2 == 0;
                                = bin b a1 (update a2 (i div 2) y)
                                    if i mod 2 == 1;
end;

// update a given position of a two-dimensional array with a new value
update2 x@(Array a) (i::int, j::int) y
                                = update x i (update (x!i) j y);

// compare two arrays for equality
Array a == Array b              = eq a b
with
  eq nil nil                    = 1;
  eq nil (tip _)                = 0;
  eq nil (bin _ _ _)            = 0;
  eq (tip _) nil                = 0;
  eq (tip x) (tip y)            = x == y;
  eq (tip _) (bin _ _ _)        = 0;
  eq (bin _ _ _) nil            = 0;
  eq (bin _ _ _) (tip _)        = 0;
  eq (bin b1::int a1 a2) (bin b2::int a3 a4)
                                = b1 == b2 && eq a1 a3 && eq a2 a4;
end;

// compare two arrays for inequality
Array a != Array b              = neq a b
with
  neq nil nil                   = 0;
  neq nil (tip _)               = 1;
  neq nil (bin _ _ _)           = 1;
  neq (tip _) nil               = 1;
  neq (tip x) (tip y)           = x != y;
  neq (tip _) (bin _ _ _)       = 1;
  neq (bin _ _ _) nil           = 1;
  neq (bin _ _ _) (tip _)       = 1;
  neq (bin b1::int a1 a2) (bin b2::int a3 a4)
                                = b1 != b2 || neq a1 a3 || neq a2 a4;
end;

/* Private functions. */

// construct a binary array node
mkbin _ nil a2                  = a2;
mkbin _ a1 nil                  = a1;
mkbin b::int a1 a2              = bin b a1 a2;