[svn] r6292: nemerle/trunk/lib/rlist.n

[d]

Log:
Minor fixes.

Author: d
Date: Mon May 15 14:37:07 2006
New Revision: 6292

Modified:
   nemerle/trunk/lib/rlist.n

Modified: nemerle/trunk/lib/rlist.n
==============================================================================
--- nemerle/trunk/lib/rlist.n	(original)
+++ nemerle/trunk/lib/rlist.n	Mon May 15 14:37:07 2006
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2005 Wojciech Knapik
+ * Copyright (c) 2005-2006 Wojciech Knapik
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -10,14 +10,14 @@
  *    2. Redistributions in binary form must reproduce the above copyright
  *       notice, this list of conditions and the following disclaimer in the
  *       documentation and/or other materials provided with the distribution.
- *    3. The name of the University may not be used to endorse or promote
+ *    3. The name of Wojciech Knapik may not be used to endorse or promote
  *       products derived from this software without specific prior
  *       written permission.
  * 
  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
- * NO EVENT SHALL THE UNIVERSITY BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
@@ -185,7 +185,7 @@
     public static UnCons (xs : RList ['a]) : 'a * RList ['a] {
       | Zero (ps) => def ((x, y), ps') = RList [Pair ['a]].UnCons (ps);
                      (x, One (y, ps'))
-      | One (x, Nil ()) => (x, Nil ())
+      | One (x, Nil) => (x, Nil ())
       | One (x, ps) => (x, Zero (ps))
       | Nil => throw Exception ("Empty")
     }
@@ -526,7 +526,7 @@
 
     /** Returns an a new RList composed by appending [ys]
         at the end of [xs].
-        Time complexity: O (|xs| * log (|xs|)).
+        Time complexity: roughly O (|xs| * log (|ys| + |xs|)).
         <param name="xs">
           The RList, which elements come first in the resulting RList.
         </param>
@@ -534,16 +534,21 @@
           The RList, which elements come second in the resulting RList.
         </param>
         <returns>
-          An RListcomposed by appending [ys] at the end of [xs]. 
+          An RList composed by appending [ys] at the end of [xs]. 
         </returns>
      */
     public static Append (xs : RList ['a], ys : RList ['a]) : RList ['a] {
       FoldRight (xs, ys, Cons)
     }   
 
+//    O (n) complexity - gotta benchmark if it's faster, than the above  
+//    public static _Append (xs : RList ['a], ys : RList ['a]) : RList ['a] {
+//      FromList (FoldRight (xs, ToList (ys), _ :: _))
+//    }
+
     /** Returns an a new RList composed by appending [ys]
         at the end of [this].
-        Time complexity: O (|this| * log (|this|)).
+        Time complexity: roughly O (|this| * log (|this| + |ys|)).
         <param name="ys">
           The RList, which elements come second in the resulting RList.
         </param>
@@ -552,7 +557,7 @@
         </returns>
      */
     public Append (ys : RList ['a]) : RList ['a] {
-      FoldRight (this, ys, Cons)
+      Append (this, ys)
     }   
 
     /** Returns an RList composed of the elements of list [xs].
@@ -569,6 +574,23 @@
       FromList (xs, xs.Length)
     }
 
+    /** Returns an RList composed of the elements of list [xs], of 
+        length [i].
+        Time complexity: O (|xs|).
+        <param name="xs">
+          The list used when composing the return value.
+        </param>
+        <param name="i">
+          The length of [xs] and therefore of the return value as well.
+        </param>
+        <returns>
+          An RList composed of the elements of [xs].
+        </returns>
+     */
+    public static FromList (xs : list ['a], i : int) : RList ['a] {
+      _FromList (xs, i, fun (l) { match (l) { | x :: tl => (x, tl) | [] => throw Exception ("Empty") } })  
+    }
+
     /* An auxillary function used by FromList (xs, i).
        Time complexity: O (|xs|).
      */
@@ -589,23 +611,6 @@
           Zero (RList [Pair ['a]]._FromList (xs, i / 2, f'))
     }
 
-    /** Returns an RList composed of the elements of list [xs], of 
-        length [i].
-        Time complexity: O (|xs|).
-        <param name="xs">
-          The list used when composing the return value.
-        </param>
-        <param name="i">
-          The length of [xs] and therefore of the return value as well.
-        </param>
-        <returns>
-          An RList composed of the elements of [xs].
-        </returns>
-     */
-    public static FromList (xs : list ['a], i : int) : RList ['a] {
-      _FromList (xs, i, fun (l) { match (l) { | x :: tl => (x, tl) | [] => throw Exception ("Empty") } })  
-    }
-
     /** Returns a list of elements of the RList [xs] in the same order.
         Time complexity: O (|xs|).
         <param name="xs">