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

[d]

Log:
Some optimizations and minor fixes.

Author: d
Date: Sat Jan 28 20:16:52 2006
New Revision: 6089

Modified:
   nemerle/trunk/lib/rlist.n

Modified: nemerle/trunk/lib/rlist.n
==============================================================================
--- nemerle/trunk/lib/rlist.n	(original)
+++ nemerle/trunk/lib/rlist.n	Sat Jan 28 20:16:52 2006
@@ -35,6 +35,10 @@
   public class Pair ['a] { 
     public fst : 'a; 
     public snd : 'a; 
+
+    public override ToString () : string {
+      $"($(this.fst), $(this.snd))"
+    }
   }
   
   /** RList is short for Random Access List. It is a purely functional
@@ -101,9 +105,9 @@
         </returns>
      */
     public static Equals (xs : RList ['a], ys : RList ['a]) : bool {
-      | (Nil, Nil) => true
       | (Zero (ps), Zero (qs)) => Equals (ps, qs)
       | (One (x, ps), One (y, qs)) when x.Equals (y) => Equals (ps, qs)
+      | (Nil, Nil) => true
       | _ => false
     }  
   
@@ -137,9 +141,9 @@
      */
     public static Cons (x : 'a, xs : RList ['a]) : RList ['a] {
       match (xs) {
-        | Nil => One (x, Nil ())
-        | Zero (ps) => One (x, ps)
         | One (y, ps) => Zero (RList [Pair ['a]].Cons (Pair (x, y), ps))
+        | Zero (ps) => One (x, ps)
+        | Nil => One (x, Nil ())
       }
     }
 
@@ -166,11 +170,11 @@
         </returns>
      */
     public static UnCons (xs : RList ['a]) : 'a * RList ['a] {
-      | Nil => throw System.Exception ("Empty")
-      | One (x, Nil ()) => (x, Nil ())
-      | One (x, ps) => (x, Zero (ps))
       | Zero (ps) => def ((x, y), ps') = RList [Pair ['a]].UnCons (ps);
                      (x, One (y, ps'))
+      | One (x, Nil ()) => (x, Nil ())
+      | One (x, ps) => (x, Zero (ps))
+      | Nil => throw System.Exception ("Empty")
     }
     
     /** Separates and returns the head and tail of the RList [this].
@@ -193,10 +197,10 @@
         </returns>
      */
     public static Head (xs : RList ['a]) : 'a {
-      | Nil => throw System.Exception ("Empty")
-      | One (x, _) => x
       | Zero (ps) => def (x, _) = RList [Pair ['a]].Head (ps); 
                      x
+      | One (x, _) => x
+      | Nil => throw System.Exception ("Empty")
     }
 
     /** Returns the head of the RList [this].
@@ -286,11 +290,11 @@
     /* A helper function used by the Length property 
        Time complexity: O (log (|xs|)).
      */
-    static _Length (xs : RList ['a], pow = 0.0, count = 0.0) : int {
+    static _Length (xs : RList ['a], tmp = 1, count = 0) : int {
       match (xs) {
-        | Nil => count :> int
-        | Zero (ps) => RList [Pair ['a]]._Length (ps, pow + 1.0, count)
-        | One (_, ps) => _Length (Zero (ps), pow, count + System.Math.Pow (2, pow))
+        | Zero (ps) => RList [Pair ['a]]._Length (ps, tmp * 2, count)
+        | One (_, ps) => _Length (Zero (ps), tmp, count + tmp)
+        | Nil => count
       }        
     }
     
@@ -320,10 +324,10 @@
      */
     public static Nth (xs : RList ['a], i : int) : 'a {
       match (xs) {
-        | Nil => throw System.Exception ("Subscript")
-        | One (x, ps) => if (i == 0) x else Nth (Zero (ps), i - 1)
         | Zero (ps) => def (x, y) = RList [Pair ['a]].Nth (ps, i / 2);
                        if (i % 2 == 0) x else y
+        | One (x, ps) => if (i == 0) x else Nth (Zero (ps), i - 1)
+        | Nil => throw System.Exception ("Subscript")
       }
     }
 
@@ -345,10 +349,10 @@
      */
     static FUpdate (f : 'a -> 'a, i : int, xs : RList ['a]) : RList ['a] {
       match (xs) {
-        | Nil => throw System.Exception ("Subscript")
-        | One (x, ps) => if (i == 0) One (f (x), ps) else Cons (x, FUpdate (f, i - 1, Zero (ps)))
         | 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)))
+        | Nil => throw System.Exception ("Subscript")
       }
     }
   
@@ -405,10 +409,10 @@
      */
     public static FoldLeft ['b] (xs : RList ['a], acc : 'b, f : 'a * 'b -> 'b) : 'b {
       match (xs) {
-        | Nil => acc
         | Zero (ps) => def f' (a, b) { f (a.snd, f (a.fst, b)) }
                        RList [Pair ['a]].FoldLeft (ps, acc, f')
         | One (x, ps) => FoldLeft (Zero (ps), f (x, acc), f)
+        | Nil => acc
       }
     }    
 
@@ -450,10 +454,10 @@
      */
     public static FoldRight ['b] (xs : RList ['a], acc : 'b, f : 'a * 'b -> 'b) : 'b {
       match (xs) {
-        | Nil => acc
         | Zero (ps) => def f' (a, b) { f (a.fst, f (a.snd, b)) }
                        RList [Pair ['a]].FoldRight (ps, acc, f')
         | One (x, ps) => f (x, FoldRight (Zero (ps), acc, f))
+        | Nil => acc
       }
     }
     
@@ -508,7 +512,7 @@
         </returns>
      */
     public static ToList (xs : RList ['a]) : list ['a] {
-      Nemerle.Collections.List.Rev (FoldLeft (xs, [], fun (x, y) { x :: y }))
+      Nemerle.Collections.List.Rev (FoldLeft (xs, [], _ :: _))
     }
 
     /** Returns a list of elements of the RList [this] in the same order.
@@ -542,9 +546,9 @@
      */
     public override ToString () : string {
       match (this) {
+        | Zero (ps) => $"Zero ($ps)"
+        | One (x, ps) => $"One ($x, $ps)"
         | Nil => "Nil"
-        | One (x, ps) => "One (" + x.ToString () + ", " + ps.ToString () + ")"
-        | Zero (ps) => "Zero (" + ps.ToString () + ")"
       }
     }
   }