[svn] r6018: nemerle/trunk/lib/rlist.n
d
svnadmin at nemerle.org
Sun Dec 18 22:33:45 CET 2005
Log:
Add comments, remove tabs, visually restructure code in rlist.n.
Author: d
Date: Sun Dec 18 22:33:43 2005
New Revision: 6018
Modified:
nemerle/trunk/lib/rlist.n
Modified: nemerle/trunk/lib/rlist.n
==============================================================================
--- nemerle/trunk/lib/rlist.n (original)
+++ nemerle/trunk/lib/rlist.n Sun Dec 18 22:33:43 2005
@@ -1,27 +1,105 @@
+/*
+ * Copyright (c) 2005 Wojciech Knapik
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 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
+ * 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,
+ * 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
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
namespace Nemerle.Collections {
+ /** An auxillary data-structure for RList used instead of a regular
+ tuple (which is a struct) for performance reasons.
+ */
[Record]
public class Pair ['a] {
public fst : 'a;
public snd : 'a;
}
+ /** RList is short for Random Access List. It is a purely functional
+ data-structure. This implementation is based on the SML sources
+ found in Chris Okasaki's "Purely Functional Data Structures"
+ (Cambridge University Press, 1999).
+ */
public variant RList ['a] {
| Nil
- | Zero { arg : RList [Pair ['a]] }
- | One { arg1 : 'a; arg2 : RList [Pair ['a]] }
+ | Zero {
+ arg : RList [Pair ['a]]
+ }
+ | One {
+ arg1 : 'a;
+ arg2 : RList [Pair ['a]]
+ }
+ /** Returns an empty RList.
+ Time complexity: O (1).
+ <returns>
+ An empty RList.
+ </returns>
+ */
public static Empty : RList ['a] = Nil ();
+ /** Checks, whether the RList [xs] is empty.
+ Time complexity: O (1).
+ <param name="xs">
+ The list to check for emptiness.
+ </param>
+ <returns>
+ true if the [xs] is empty,
+ false otherwise.
+ </returns>
+ */
public static IsEmpty (xs : RList ['a]) : bool {
| Nil => true
| _ => false
}
+ /** Checks, whether [this] is an empty RList.
+ Time complexity: O (1).
+ <returns>
+ true if [this] is an empty RList,
+ false otherwise.
+ </returns>
+ */
public IsEmpty () : bool {
IsEmpty (this)
}
+ /** Checks, whether two RLists are equal, by cheking if their
+ respective elements are equal.
+ Time complexity: O (min (|xs|, |ys|)).
+ <param name="xs">
+ The first compared RList.
+ </param>
+ <param name="ys">
+ The second compared RList.
+ </param>
+ <returns>
+ true if [xs] and [ys] are equal,
+ false otherwise.
+ </returns>
+ */
public static Equals (xs : RList ['a], ys : RList ['a]) : bool {
| (Nil, Nil) => true
| (Zero (ps), Zero (qs)) => Equals (ps, qs)
@@ -29,11 +107,34 @@
| _ => false
}
+ /** Checks, whether [this] and [ys] are equal RLists, by cheking if their
+ respective elements are equal.
+ Time complexity: O (min (|this|, |ys|)).
+ <param name="ys">
+ The RList [this] is compared to.
+ </param>
+ <returns>
+ true if [this] and [ys] are equal,
+ false otherwise.
+ </returns>
+ */
[Nemerle.OverrideObjectEquals]
public Equals (ys : RList ['a]) : bool {
Equals (this, ys)
}
+ /** Returns a new RList composed by adding [x], to the head of the RList [xs].
+ Time complexity: O (log (|xs|)).
+ <param name="x">
+ The element being added to the head of [xs].
+ </param>
+ <param name="xs">
+ The RList, to which head [x] is being added.
+ </param>
+ <returns>
+ A new RList composed of [x] as the new head and [xs] as the new tail.
+ </returns>
+ */
public static Cons (x : 'a, xs : RList ['a]) : RList ['a] {
match (xs) {
| Nil => One (x, Nil ())
@@ -42,10 +143,28 @@
}
}
+ /** Returns a new RList composed by adding [x], to the head of the RList [this].
+ Time complexity: O (log (|this|)).
+ <param name="x">
+ The element being added to the head of [this].
+ </param>
+ <returns>
+ A new RList composed of [x] as the new head and [this] as the new tail.
+ </returns>
+ */
public Cons (x : 'a) : RList ['a] {
Cons (x, this)
}
+ /** Separates and returns the head and tail of the RList [xs].
+ Time complexity: O (log (|xs|)).
+ <param name="xs">
+ The RList, which tail is going to be returned along with the separated head.
+ </param>
+ <returns>
+ The head and tail of [xs].
+ </returns>
+ */
public static UnCons (xs : RList ['a]) : 'a * RList ['a] {
| Nil => throw System.Exception ("Empty")
| One (x, Nil ()) => (x, Nil ())
@@ -54,45 +173,119 @@
(x, One (y, ps'))
}
+ /** Separates and returns the head and tail of the RList [this].
+ Time complexity: O (log (|this|)).
+ <returns>
+ The head and tail of [this].
+ </returns>
+ */
public UnCons () : 'a * RList ['a] {
UnCons (this)
}
+ /** Returns the head of the RList [xs].
+ Time complexity: O (log (|xs|)).
+ <param name="xs">
+ The RList, which head is going to be returned.
+ </param>
+ <returns>
+ The head of [xs].
+ </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
+ | Zero (ps) => def (x, _) = RList [Pair ['a]].Head (ps);
+ x
}
+ /** Returns the head of the RList [this].
+ Time complexity: O (log (|this|)).
+ <returns>
+ The head of [this].
+ </returns>
+ */
public Head () : 'a {
Head (this)
}
+ /** Returns the head of the RList [xs].
+ Time complexity: O (log (|xs|)).
+ An alias for Head.
+ <param name="xs">
+ The RList, which head is going to be returned.
+ </param>
+ <returns>
+ The head of [xs].
+ </returns>
+ */
public static Hd (xs : RList ['a]) : 'a {
Head (xs)
}
+ /** Returns the head of the RList [this].
+ Time complexity: O (log (|this|)).
+ An alias for Head.
+ <returns>
+ The head of [this].
+ </returns>
+ */
public Hd () : 'a {
this.Head ()
}
+ /** Returns the tail of the RList [xs].
+ Time complexity: O (log (|xs|)).
+ <param name="xs">
+ The RList, which tail is going to be returned.
+ </param>
+ <returns>
+ The tail of [xs].
+ </returns>
+ */
public static Tail (xs : RList ['a]) : RList ['a] {
def (_, xs') = UnCons (xs);
xs'
}
+ /** Returns the tail of the RList [this].
+ Time complexity: O (log (|this|)).
+ <returns>
+ The tail of [this].
+ </returns>
+ */
public Tail () : RList ['a] {
Tail (this)
}
+ /** Returns the tail of the RList [xs].
+ Time complexity: O (log (|xs|)).
+ An alias for Tail.
+ <param name="xs">
+ The RList, which tail is going to be returned.
+ </param>
+ <returns>
+ The tail of [xs].
+ </returns>
+ */
public static Tl (xs : RList ['a]) : RList ['a] {
Tail (xs)
}
+ /** Returns the tail of the RList [this].
+ Time complexity: O (log (|this|)).
+ An alias fot Tail.
+ <returns>
+ The tail of [this].
+ </returns>
+ */
public Tl () : RList ['a] {
this.Tail ()
}
+ /* 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 {
match (xs) {
| Nil => count :> int
@@ -101,12 +294,30 @@
}
}
+ /** Returns the length of the RList [this].
+ Time complexity: O (log (|this|)).
+ <returns>
+ The length of [this].
+ </returns>
+ */
public Length : int {
get {
_Length (this)
}
}
+ /** Returns the [i]-th element of the RList [xs].
+ Time complexity: O (log (|xs|)).
+ <param name="xs">
+ The RList, which [i]-th element is going to be returned.
+ </param>
+ <param name="i">
+ The index under which the return element is located in [xs].
+ </param>
+ <returns>
+ The [i]-th element of [xs].
+ </returns>
+ */
public static Nth (xs : RList ['a], i : int) : 'a {
match (xs) {
| Nil => throw System.Exception ("Subscript")
@@ -116,10 +327,22 @@
}
}
+ /** Returns the [i]-th element of the RList [this].
+ Time complexity: O (log (|this|)).
+ <param name="i">
+ The index under which the return element is located in [this].
+ </param>
+ <returns>
+ The [i]-th element of [this].
+ </returns>
+ */
public Nth (i : int) : 'a {
Nth (this, i)
}
+ /* A helper function used by update
+ Time complexity: O (log (|xs|)).
+ */
static FUpdate (f : 'a -> 'a, i : int, xs : RList ['a]) : RList ['a] {
match (xs) {
| Nil => throw System.Exception ("Subscript")
@@ -129,18 +352,57 @@
}
}
- _FUpdate (f : 'a -> 'a, i : int) : RList ['a] {
- FUpdate (f, i, this)
- }
-
+ /** Returns a new RList composed by substituting the [i]-th element
+ of the RList [xs], with [x].
+ Time complexity: O (log (|xs|)).
+ <param name="xs">
+ The RList used in composing the return value.
+ </param>
+ <param name="i">
+ The index under which the element to be substituted resides in [xs].
+ </param>
+ <returns>
+ A new RList composed by substituting the [i]-th element
+ of the RList [xs], with [x].
+ </returns>
+ */
public static Update (i : int, y : 'a, xs : RList ['a]) : RList ['a] {
FUpdate (fun (_) { y }, i, xs)
}
+ /** Returns a new RList composed by substituting the [i]-th element
+ of the RList [this], with [x].
+ Time complexity: O (log (|this|)).
+ <param name="i">
+ The index under which the element to be substituted resides in [this].
+ </param>
+ <returns>
+ A new RList composed by substituting the [i]-th element
+ of the RList [this], with [x].
+ </returns>
+ */
public Update (i : int, y : 'a) : RList ['a] {
Update (i, y, this)
}
+ /** Iterates over the RList [xs] from left to right, composing the return
+ value, by applying [f], to each of [xs]'s elements and the current [acc].
+ Time complexity: O (|xs|).
+ <param name="xs">
+ The RList over which FoldLeft is going to iterate.
+ </param>
+ <param name="acc">
+ The accumulator being updated on each level of recursion, to
+ finally become the return value of FoldLeft.
+ The supplied value will be used by [f] in the first step.
+ </param>
+ <param name="f">
+ The function being applied to ([RList-elem], [acc]) in each step.
+ </param>
+ <returns>
+ Acc in it's final state at the last step of recursion
+ </returns>
+ */
public static FoldLeft ['b] (xs : RList ['a], acc : 'b, f : 'a * 'b -> 'b) : 'b {
match (xs) {
| Nil => acc
@@ -150,10 +412,42 @@
}
}
+ /** Iterates over the RList [this] from left to right, composing the return
+ value, by applying [f], to each of [this]' elements and the current [acc].
+ Time complexity: O (|this|).
+ <param name="acc">
+ The accumulator being updated on each level of recursion, to
+ finally become the return value of FoldLeft.
+ The supplied value will be used by [f] in the first step.
+ </param>
+ <param name="f">
+ The function being applied to ([RList-elem], [acc]) in each step.
+ </param>
+ <returns>
+ Acc in it's final state at the last step of recursion
+ </returns>
+ */
public FoldLeft ['b] (acc : 'b, f : 'a * 'b -> 'b) : 'b {
FoldLeft (this, acc, f)
}
+ /** Iterates over the RList [xs] from right to left, composing the return
+ value, by applying [f], to each of [xs]'s elements and the current [acc].
+ Time complexity: O (|xs|).
+ <param name="xs">
+ The RList over which FoldRight is going to iterate.
+ </param>
+ <param name="acc">
+ The accumulator updated on each level of recursion and used by [f].
+ The supplied value will be used by [f] in the last step.
+ </param>
+ <param name="f">
+ The function being applied to ([RList-elem], [acc]) in each step.
+ </param>
+ <returns>
+ The result of applying [f] to each element of [xs] and the current [acc].
+ </returns>
+ */
public static FoldRight ['b] (xs : RList ['a], acc : 'b, f : 'a * 'b -> 'b) : 'b {
match (xs) {
| Nil => acc
@@ -163,30 +457,89 @@
}
}
+ /** Iterates over the RList [this] from right to left, composing the return
+ value, by applying [f], to each of [this]' elements and the current [acc].
+ Time complexity: O (|this|).
+ <param name="acc">
+ The accumulator updated on each level of recursion and used by [f].
+ The supplied value will be used by [f] in the last step.
+ </param>
+ <param name="f">
+ The function being applied to ([RList-elem], [acc]) in each step.
+ </param>
+ <returns>
+ The result of applying [f] to each element of [xs] and the current [acc].
+ </returns>
+ */
public FoldRight ['b] (acc : 'b, f : 'a * 'b -> 'b) : 'b {
FoldRight (this, acc, f)
}
+ /** Returns an RList composed by reversing [xs].
+ Time complexity: O (|xs|).
+ <param name="xs">
+ The RList used when composing the return value.
+ </param>
+ <returns>
+ An RList composed by reversing [xs].
+ </returns>
+ */
public static Rev (xs : RList ['a]) : RList ['a] {
FoldLeft (xs, Nil (), Cons)
}
+ /** Returns an RList composed by reversing [this].
+ Time complexity: O (|this|).
+ <returns>
+ An RList composed by reversing [this].
+ </returns>
+ */
public Rev () : RList ['a] {
Rev (this)
}
+ /** Returns a list of elements of the RList [xs] in the same order.
+ Time complexity: O (|xs|).
+ <param name="xs">
+ The RList used when composing the return value.
+ </param>
+ <returns>
+ A list of elements of the RList [xs] in the same order.
+ </returns>
+ */
public static ToList (xs : RList ['a]) : list ['a] {
Nemerle.Collections.List.Rev (FoldLeft (xs, [], fun (x, y) { x :: y }))
}
+ /** Returns a list of elements of the RList [this] in the same order.
+ Time complexity: O (|this|).
+ <returns>
+ A list of elements of the RList [this] in the same order.
+ </returns>
+ */
public ToList () : list ['a] {
ToList (this)
}
+ /** Returns a string representation of the RList [xs].
+ Time complexity: O (|xs|).
+ <param name="xs">
+ The RList used when composing the return value.
+ </param>
+ <returns>
+ A string representation of the RList [xs].
+ </returns>
+ */
public static ToString (xs : RList ['a]) : string {
xs.ToString ()
}
+ /** Returns a string representation of the RList [this].
+ Time complexity: O (|this|).
+ <returns>
+ A string representation of the RList [this].
+ </returns>
+ */
public override ToString () : string {
match (this) {
| Nil => "Nil"
More information about the svn
mailing list