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

[d]

Log:
Add O (n) complexity Append and Rev commented-out (they need benchmarks, but a bug in mono prevents them). Also some minor tweaks.

Author: d
Date: Tue May 16 19:43:28 2006
New Revision: 6296

Modified:
   nemerle/trunk/lib/rlist.n

Modified: nemerle/trunk/lib/rlist.n
==============================================================================
--- nemerle/trunk/lib/rlist.n	(original)
+++ nemerle/trunk/lib/rlist.n	Tue May 16 19:43:28 2006
@@ -137,6 +137,7 @@
      */
     [Nemerle.OverrideObjectEquals]
     public Equals (ys : RList ['a]) : bool {
+      //PERFORMANCE: maybe it would be worth checking lenghts first ?
       Equals (this, ys)
     }
 
@@ -248,7 +249,7 @@
         </returns>
      */
     public Hd () : 'a {
-      this.Head ()
+      Head (this)
     }  
   
     /** Returns the tail of the RList [xs].
@@ -297,7 +298,7 @@
         </returns>
      */
     public Tl () : RList ['a] {
-      this.Tail ()
+      Tail (this)
     }
 
     /* An auxillary function used by the Length property. 
@@ -367,11 +368,11 @@
     /* A helper function used by update 
        Time complexity: O (log (|xs|)).
      */
-    static FUpdate (f : 'a -> 'a, i : int, xs : RList ['a]) : RList ['a] {
+    static _Update (f : 'a -> 'a, i : int, xs : RList ['a]) : RList ['a] {
       match (xs) {
         | Zero (ps) => def f' (p) { match (p) { | Pair where (fst = x, snd = y) => if (i % 2 == 0) Pair (f (x), y) else Pair (x, f (y)) } }
-                       Zero (RList [Pair ['a]].FUpdate (f', i / 2, ps))
-        | One (x, ps) => if (i == 0) One (f (x), ps) else Cons (x, FUpdate (f, i - 1, Zero (ps)))
+                       Zero (RList [Pair ['a]]._Update (f', i / 2, ps))
+        | One (x, ps) => if (i == 0) One (f (x), ps) else Cons (x, _Update (f, i - 1, Zero (ps)))
         | Nil => throw Exception ("Subscript")
       }
     }
@@ -391,7 +392,7 @@
         </returns>
      */
     public static Update (i : int, y : 'a, xs : RList ['a]) : RList ['a] {
-      FUpdate (fun (_) { y }, i, xs)
+      _Update (fun (_) { y }, i, xs)
     }
   
     /** Returns a new RList composed by substituting the [i]-th element 
@@ -514,6 +515,11 @@
       FoldLeft (xs, Nil (), Cons)
     }
 
+//    PERFORMANCE: O (n) complexity - gotta benchmark if it's faster, than the above  
+//    public static Rev_2 (xs : RList ['a]) : RList ['a] {
+//      FromList (FoldLeft (xs, [], _ :: _))
+//    }
+ 
     /** Returns an RList composed by reversing [this].
         Time complexity: O (|this| * log (|this|)).
         <returns>
@@ -541,8 +547,8 @@
       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] {
+//    PERFORMANCE: O (n) complexity - gotta benchmark if it's faster, than the above  
+//    public static Append_2 (xs : RList ['a], ys : RList ['a]) : RList ['a] {
 //      FromList (FoldRight (xs, ToList (ys), _ :: _))
 //    }