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

[d]

Log:
Fix Equals, add FromList (xs, i) with O (|xs|) time complexity.


Author: d
Date: Sun Jan 29 19:15:13 2006
New Revision: 6093

Modified:
   nemerle/trunk/lib/rlist.n

Modified: nemerle/trunk/lib/rlist.n
==============================================================================
--- nemerle/trunk/lib/rlist.n	(original)
+++ nemerle/trunk/lib/rlist.n	Sun Jan 29 19:15:13 2006
@@ -26,6 +26,7 @@
  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
+using System;
 using SCG = System.Collections.Generic;
 
 namespace Nemerle.Collections {
@@ -38,6 +39,11 @@
     public fst : 'a; 
     public snd : 'a; 
 
+    [Nemerle.OverrideObjectEquals]
+    public Equals (p : Pair ['a]) : bool {
+      this.fst.Equals (p.fst) && this.snd.Equals (p.snd)
+    }
+
     public override ToString () : string {
       $"($(this.fst), $(this.snd))"
     }
@@ -112,8 +118,8 @@
         </returns>
      */
     public static Equals (xs : RList ['a], ys : RList ['a]) : bool {
-      | (Zero (ps), Zero (qs)) => Equals (ps, qs)
-      | (One (x, ps), One (y, qs)) when x.Equals (y) => Equals (ps, qs)
+      | (Zero (ps), Zero (qs)) => RList [Pair ['a]].Equals (ps, qs)
+      | (One (x, ps), One (y, qs)) when x.Equals (y) => RList [Pair ['a]].Equals (ps, qs)
       | (Nil, Nil) => true
       | _ => false
     }  
@@ -181,7 +187,7 @@
                      (x, One (y, ps'))
       | One (x, Nil ()) => (x, Nil ())
       | One (x, ps) => (x, Zero (ps))
-      | Nil => throw System.Exception ("Empty")
+      | Nil => throw Exception ("Empty")
     }
     
     /** Separates and returns the head and tail of the RList [this].
@@ -207,7 +213,7 @@
       | Zero (ps) => def (x, _) = RList [Pair ['a]].Head (ps); 
                      x
       | One (x, _) => x
-      | Nil => throw System.Exception ("Empty")
+      | Nil => throw Exception ("Empty")
     }
 
     /** Returns the head of the RList [this].
@@ -294,7 +300,7 @@
       this.Tail ()
     }
 
-    /* A helper function used by the Length property 
+    /* An auxillary function used by the Length property. 
        Time complexity: O (log (|xs|)).
      */
     static _Length (xs : RList ['a], tmp = 1, count = 0) : int {
@@ -341,7 +347,7 @@
             if (i % 2 != 0) x 
             else y 
           }
-        | Nil => throw System.Exception ("Subscript")
+        | Nil => throw Exception ("Subscript")
       }
     }
 
@@ -366,7 +372,7 @@
         | 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")
+        | Nil => throw Exception ("Subscript")
       }
     }
   
@@ -531,6 +537,43 @@
       List.FoldLeft (List.Rev (xs), Nil (), Cons)
     }
 
+    /* An auxillary function used by FromList (xs, i).
+       Time complexity: O (|xs|).
+     */
+    static _FromList ['b] (xs : list ['b], i : int, f : list ['b] -> 'a * list ['b]) : RList ['a] {
+      def f' (l) { 
+        def (elem1, rest1) = f (l); 
+        def (elem2, rest2) = f (rest1);
+        (Pair (elem1, elem2), rest2)
+      }
+      if (i % 2 == 1) {
+        def (elem, rest) = f (xs);
+        One (elem, RList [Pair ['a]]._FromList (rest, i / 2, f'))
+      } 
+      else 
+        if (i == 0)
+          Nil ()
+        else
+          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 + 1, 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">