[pure-lang-svn] SF.net SVN: pure-lang: [336] pure/trunk/examples/array.pure
Status: Beta
Brought to you by:
agraef
Menu
▾
▴
[pure-lang-svn] SF.net SVN: pure-lang: [336] pure/trunk/examples/array.pure
|
From: <ag...@us...> - 2008-06-29 23:09:51
|
Revision: 336
http://pure-lang.svn.sourceforge.net/pure-lang/?rev=336&view=rev
Author: agraef
Date: 2008-06-29 16:10:00 -0700 (Sun, 29 Jun 2008)
Log Message:
-----------
Overhaul array module.
Modified Paths:
--------------
pure/trunk/examples/array.pure
Modified: pure/trunk/examples/array.pure
===================================================================
--- pure/trunk/examples/array.pure 2008-06-29 08:16:50 UTC (rev 335)
+++ pure/trunk/examples/array.pure 2008-06-29 23:10:00 UTC (rev 336)
@@ -1,3 +1,4 @@
+
/* array.pure: integer-indexed arrays implemented as size-balanced
binary trees. */
@@ -18,275 +19,199 @@
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
+/* 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. The implementation is
- based on the same ideas as in Frank Drewes' queue data structure.
-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
+ operations are carried out in logarithmic time. */
+/* Public operations: ******************************************************
-/*****************************************************************************/
-/* */
-/* DIFFERENCES VERSUS Q LANGUAGE */
-/* */
-/******************************************************************************
+ 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
- Views are not currently available in Pure and so the data structures are
- displayed as they really are. To view the data as lists you should call
- the function "members".
+ #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
-/*** some declarations ***/
+ *************************************************************************/
-using primitives;
-
-// empty tree constructor
+/* Empty tree constant, consider this private. */
nullary nil;
-
-/******************************************************************************/
-/* */
-/* PUBLIC FUNCTIONS */
-/* */
-/******************************************************************************/
-
-
-/*** The following functions represent the user's interface to the module ***/
-
-
// array type check
-isarray (tarray _) = 1;
-isarray _ = 0;
+arrayp (tarray _) = 1;
+arrayp _ = 0;
-
// create an empty array
emptyarray = tarray nil;
-
// create an array from a list
-array xs
- = tarray (foldl tarray_append nil xs)
- if listp xs;
+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
- = tarray (mkarray_ x n)
- with
- mkarray_ x n::int = nil if n <= 0;
- = tip x if n == 1;
- = tarray_mkbin (n mod 2)
- (mkarray_ x (n - n div 2))
- (mkarray_ x (n div 2))
- end;
+mkarray x n::int = tarray (mkarray x n)
+with
+ mkarray x n::int = nil if n <= 0;
+ = tip x if n == 1;
+ = tarray_mkbin (n mod 2)
+ (mkarray x (n - n div 2))
+ (mkarray x (n div 2));
+end;
-// create two-dimensional array of given dimensions filled with a constant value
+// 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
-#(tarray a)
- = size a
- with
- size nil = 0;
- size (tip _) = 1;
- size (bin 0 a1 _) = (size a1) * 2;
- size (bin 1 a1 _) = (size a1) * 2 - 1
- end;
+#(tarray a) = #a
+with
+ #nil = 0;
+ #(tip _) = 1;
+ #(bin 0 a1 _) = #a1 * 2;
+ #(bin 1 a1 _) = #a1 * 2 - 1;
+end;
-
// get value by index
-(tarray a)!i::int
- = ith a i
- with
- ith (tip x) 0 = x;
- ith (bin _ a1 a2) i::int
- = ith a1 (i div 2) if i mod 2 == 0;
- = ith a2 (i div 2) if i mod 2 == 1;
- ith _ _ = throw out_of_bounds
- end;
+(tarray 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@(tarray _)!(i::int, j::int) = (x!i)!j;
+x@(tarray _)!(i::int, j::int) = x!i!j;
-
// check for an empty array
null (tarray nil) = 1;
null (tarray _) = 0;
+// get all array members in list form
+members (tarray 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 array members in a list form
-members (tarray a)
- = members_ a
- with
- members_ nil = [];
- members_ (tip x) = [x];
- members_ (bin _ a1 a2)
- = tarray_merge (members_ a1)
- (members_ a2)
- end;
-
-
-// get all members of an two-dimensional array in a list form
+// get all members of an two-dimensional array in list form
members2 x@(tarray _) = map members (members x);
-
// get the first array member
-first (tarray a)
- = tarray_first a
- with
- first_ (tip x) = x;
- first_ (bin _ a1 _) = first_ a1
- end;
+first (tarray a) = first a
+with
+ first (tip x) = x;
+ first (bin _ a1 _) = first a1;
+end;
-
// get the last array member
-last (tarray a)
- = last_ a
- with
- last_ (tip x) = x;
- last_ (bin 0 _ a2) = last_ a2;
- last_ (bin 1 a1 _) = last_ a1
- end;
+last (tarray 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 (tarray a)
- = tarray (rmfirst_ a)
- with
- rmfirst_ (tip _) = nil;
- rmfirst_ (bin 0 a1 a2)
- = tarray_mkbin 1 a2 (rmfirst_ a1);
- rmfirst_ (bin 1 a1 a2)
- = tarray_mkbin 0 a2 (rmfirst_ a1)
- end;
+rmfirst (tarray a) = tarray (rmfirst a)
+with
+ rmfirst (tip _) = nil;
+ rmfirst (bin 0 a1 a2) = tarray_mkbin 1 a2 (rmfirst a1);
+ rmfirst (bin 1 a1 a2) = tarray_mkbin 0 a2 (rmfirst a1);
+end;
-
// remove the last member from an array
-rmlast (tarray a)
- = tarray (rmlast_ a)
- with
- rmlast_ (tip _) = nil;
- rmlast_ (bin 0 a1 a2)
- = tarray_mkbin 1 a1 (rmlast_ a2);
- rmlast_ (bin 1 a1 a2)
- = tarray_mkbin 0 (rmlast_ a1) a2
- end;
+rmlast (tarray a) = tarray (rmlast a)
+with
+ rmlast (tip _) = nil;
+ rmlast (bin 0 a1 a2) = tarray_mkbin 1 a1 (rmlast a2);
+ rmlast (bin 1 a1 a2) = tarray_mkbin 0 (rmlast a1) a2;
+end;
+// insert a new member at the beginning of an array
+insert (tarray a) y = tarray (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 = tarray_mkbin 1 (insert a2 y) a1;
+ insert (bin 1 a1 a2) y = tarray_mkbin 0 (insert a2 y) a1;
+end;
-// insert a new member at the array beginning
-insert (tarray a) y
- = tarray (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
- = tarray_mkbin 1 (insert_ a2 y) a1;
- insert_ (bin 1 a1 a2) y
- = tarray_mkbin 0 (insert_ a2 y) a1
- end;
+// append a new member at the end of an array
+append (tarray a) y = tarray (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 = tarray_mkbin 1 (append a1 y) a2;
+ append (bin 1 a1 a2) y = tarray_mkbin 0 a1 (append a2 y);
+end;
+// update a given array position with a new value
+update (tarray a) i::int y = tarray (update a i y)
+with
+ update (tip _) 0 y = tip y;
+ update (bin b 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;
-// append a new member at the array end
-append (tarray a) y
- = tarray (tarray_append a y);
-
-
-//update a given array position with a new value
-update (tarray a) i::int y
- = tarray (update_ a i y)
- with
- update_ (tip _) 0 y = tip y;
- update_ (bin b 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
+// update a given position of a two-dimensional array with a new value
update2 x@(tarray a) (i::int, j::int) y
= update x i (update (x!i) j y);
+// compare two arrays for equality
+tarray a == tarray b = a == b
+with
+ nil == nil = 1;
+ nil == tip _ = 0;
+ nil == bin _ _ _ = 0;
+ tip _ == nil = 0;
+ tip x == tip y = x == y;
+ tip _ == bin _ _ _ = 0;
+ bin _ _ _ == nil = 0;
+ bin _ _ _ == tip _ = 0;
+ bin b1 a1 a2 == bin b2 a3 a4 = b1 == b2 && a1 == a3 && a2 == a4;
+end;
-/* test for equality of two arrays */
-(tarray a) == (tarray 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 a1 a2) (bin b2 a3 a4)
- = if (b1 != b2)
- then 0
- else if (a1 != a3)
- then 0
- else (a2 == a4)
- end;
+// compare two arrays for inequality
+tarray a != tarray b = a != b
+with
+ nil != nil = 0;
+ nil != tip _ = 1;
+ nil != bin _ _ _ = 1;
+ tip _ != nil = 1;
+ tip x != tip y = x != y;
+ tip _ != bin _ _ _ = 1;
+ bin _ _ _ != nil = 1;
+ bin _ _ _ != tip _ = 1;
+ bin b1 a1 a2 != bin b2 a3 a4 = b1 != b2 || a1 != a3 || a2 != a4;
+end;
+/* Private functions, don't invoke these directly. */
-/* test for inequality of two arrays */
-(tarray a) != (tarray 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 a1 a2) (bin b2 a3 a4)
- = if (b1 != b2)
- then 1
- else if (a1 != a3)
- then 1
- else (a2 != a4)
- end;
-
-
-/******************************************************************************/
-/* */
-/* PRIVATE FUNCTIONS */
-/* */
-/******************************************************************************/
-
-/*** The following functions shouldn't be directly used by users ***/
-
-
// construct a binary array node
-
tarray_mkbin _ nil a2 = a2;
tarray_mkbin _ a1 nil = a1;
tarray_mkbin b a1 a2 = bin b a1 a2;
-
-
-// merge lists xs (even elements) and ys
-// (odd elements)
-
-tarray_merge [] ys = ys;
-tarray_merge (x:xs) ys = (x:tarray_merge ys xs);
-
-// append stuff - this is reused
-
-tarray_append nil y = tip y;
-tarray_append (tip x) y = bin 0 (tip x) (tip y);
-tarray_append (bin 0 a1 a2) y = tarray_mkbin 1 (tarray_append a1 y) a2;
-tarray_append (bin 1 a1 a2) y = tarray_mkbin 0 a1 (tarray_append a2 y);
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
