diff options
author | michelou <michelou@epfl.ch> | 2006-08-31 13:52:34 +0000 |
---|---|---|
committer | michelou <michelou@epfl.ch> | 2006-08-31 13:52:34 +0000 |
commit | 5a8391bb88f3dd65458a77539a1475eaa84cc434 (patch) | |
tree | c872432cac89bbf51a6aa70e51812c85ff80e5e9 | |
parent | 33637d5c2f9c10c027ec16e8be31c36fb0f2c9ff (diff) | |
download | scala-5a8391bb88f3dd65458a77539a1475eaa84cc434.tar.gz scala-5a8391bb88f3dd65458a77539a1475eaa84cc434.tar.bz2 scala-5a8391bb88f3dd65458a77539a1475eaa84cc434.zip |
cleaned up code in library/scala/**/*.scala
36 files changed, 2112 insertions, 1968 deletions
diff --git a/src/library/scala/Application.scala b/src/library/scala/Application.scala index 2437a5ffaa..c2be7c9f54 100644 --- a/src/library/scala/Application.scala +++ b/src/library/scala/Application.scala @@ -9,7 +9,7 @@ // $Id$ -package scala; +package scala /** The <code>Application</code> class can be used to quickly turn objects @@ -38,16 +38,16 @@ package scala; trait Application { - /** The time when execution of this program started. - */ - val executionStart: Long = java.lang.System.currentTimeMillis(); - - /** The default main method. - */ - def main(args: Array[String]) = { - if (java.lang.System.getProperty("scala.time") != null) - java.lang.System.out.println("[total " + - (java.lang.System.currentTimeMillis() - - executionStart) + "ms]"); + /** The time when execution of this program started. + */ + val executionStart: Long = java.lang.System.currentTimeMillis() + + /** The default main method. + */ + def main(args: Array[String]) = { + if (java.lang.System.getProperty("scala.time") != null) { + val total = java.lang.System.currentTimeMillis() - executionStart + java.lang.System.out.println("[total " + total + "ms]") } + } } diff --git a/src/library/scala/Array.scala b/src/library/scala/Array.scala index 5564b6312b..d78b3ac08f 100644 --- a/src/library/scala/Array.scala +++ b/src/library/scala/Array.scala @@ -8,31 +8,41 @@ // $Id$ +package scala -package scala; - - -import runtime._ - +/** This object ... + * + * @author Martin Odersky + * @version 1.0 + */ object Array { - /** Copy one array to another - * Equaivalent to System.arraycopy(src, srcPos, dest, destPos, length), - * except that this works also for plymorphic and boxed arrays + /** Copy one array to another. + * Equivalent to + * <code>System.arraycopy(src, srcPos, dest, destPos, length)</code>, + * except that this works also for polymorphic and boxed arrays. + * + * @param src ... + * @param srcPos ... + * @param dest ... + * @param destPos ... + * @param length ... */ def copy(src: AnyRef, srcPos: Int, dest: AnyRef, destPos: Int, length: Int): Unit = src match { - case xs: BoxedArray => + case xs: runtime.BoxedArray => xs.copyTo(srcPos, dest, destPos, length) case _ => dest match { - case xs: BoxedArray => + case xs: runtime.BoxedArray => xs.copyFrom(src, srcPos, destPos, length) case _ => System.arraycopy(src, srcPos, dest, destPos, length) } } - /** Concatenate all argument arrays into a single array + /** Concatenate all argument arrays into a single array. + * + * @param xs ... */ def concat[T](xs: Array[T]*) = { var len = 0 @@ -55,22 +65,27 @@ object Array { * @return the sorted array of all integers in range [from;end). */ def range(start: Int, end: Int): Array[Int] = { - val result = new Array[Int](end - start); - for (val i <- Iterator.range(start, end)) result(i - start) = i + val result = new Array[Int](end - start) + for (val i <- start until end) result(i - start) = i result } } +/** This class ... + * + * @author Martin Odersky + * @version 1.0 + */ [cloneable,serializable] final class Array[a](_length: Int) extends Seq[a] { - def length: Int = throw new Error(); - def apply(i: Int): a = throw new Error(); - def update(i: Int, x: a): Unit = throw new Error(); - def elements: Iterator[a] = throw new Error(); - def subArray(from: Int, end: Int): Array[a] = throw new Error(); - def filter(p: a => Boolean): Array[a] = throw new Error(); - def map[b](f: a => b): Array[b] = throw new Error(); - def flatMap[b](f: a => Array[b]): Array[b] = throw new Error(); - def zip[b](that: Array[b]): Array[Tuple2[a,b]] = throw new Error(); - def zipWithIndex: Array[Tuple2[a,Int]] = throw new Error(); + def length: Int = throw new Error() + def apply(i: Int): a = throw new Error() + def update(i: Int, x: a): Unit = throw new Error() + def elements: Iterator[a] = throw new Error() + def subArray(from: Int, end: Int): Array[a] = throw new Error() + def filter(p: a => Boolean): Array[a] = throw new Error() + def map[b](f: a => b): Array[b] = throw new Error() + def flatMap[b](f: a => Array[b]): Array[b] = throw new Error() + def zip[b](that: Array[b]): Array[Tuple2[a,b]] = throw new Error() + def zipWithIndex: Array[Tuple2[a,Int]] = throw new Error() } diff --git a/src/library/scala/BufferedIterator.scala b/src/library/scala/BufferedIterator.scala index 6b85f3563b..b4ce24d16a 100644 --- a/src/library/scala/BufferedIterator.scala +++ b/src/library/scala/BufferedIterator.scala @@ -9,7 +9,7 @@ // $Id$ -package scala; +package scala /** Buffered iterators are iterators which llow to inspect the next @@ -20,11 +20,11 @@ package scala; */ trait BufferedIterator[+A] extends Iterator[A] { - /** Checks what the next available element is. - * - * @return the current element - */ - def head: A; + /** Checks what the next available element is. + * + * @return the current element + */ + def head: A - override def buffered: BufferedIterator[A] = this; + override def buffered: BufferedIterator[A] = this } diff --git a/src/library/scala/CaseClass.scala b/src/library/scala/CaseClass.scala index d50220f737..9ef03e8799 100644 --- a/src/library/scala/CaseClass.scala +++ b/src/library/scala/CaseClass.scala @@ -9,28 +9,33 @@ // $Id$ -package scala; +package scala /** defines an access function for instances of case classes * * @author Burak Emir + * @version 1.0 */ trait CaseClass extends AnyRef { /** for a case class A(x_0,...,x_(k-1)), returns x_i for 0 <= i < k, - ** null otherwise - */ - def caseElement(n: Int): Any ; + * <code>null</code> otherwise. + * + * @param n ... + */ + def caseElement(n: Int): Any /** need also, for reflection def setCaseElement(n: Int, v: Any): unit */ /** for a case class A(x_0,...,x_(k-1)), returns k - */ - def caseArity: Int ; + */ + def caseArity: Int - def caseName: String ; + /** + */ + def caseName: String } diff --git a/src/library/scala/Cell.scala b/src/library/scala/Cell.scala index a8eb431b5d..b9e3ed7a7e 100644 --- a/src/library/scala/Cell.scala +++ b/src/library/scala/Cell.scala @@ -9,7 +9,7 @@ // $Id$ -package scala; +package scala /** A <code>Cell</code> is a generic wrapper which completely @@ -19,4 +19,4 @@ package scala; * @author Martin Odersky * @version 1.0, 08/08/2003 */ -case class Cell[+T](elem: T); +case class Cell[+T](elem: T) diff --git a/src/library/scala/Console.scala b/src/library/scala/Console.scala index 007b805d1c..8a9a54173c 100644 --- a/src/library/scala/Console.scala +++ b/src/library/scala/Console.scala @@ -9,8 +9,9 @@ // $Id$ -package scala; -import scala.util.Fluid; +package scala + +import scala.util.Fluid /** The <code>Console</code> object implements functionality for @@ -22,283 +23,285 @@ import scala.util.Fluid; * @version 1.0, 03/09/2003 */ object Console { - import java.io._; - import java.text._; - - // ANSI colors foreground - final val BLACK = "\033[30m"; - final val RED = "\033[31m"; - final val GREEN = "\033[32m"; - final val YELLOW = "\033[33m"; - final val BLUE = "\033[34m"; - final val MAGENTA = "\033[35m"; - final val CYAN = "\033[36m"; - final val WHITE = "\033[37m"; - - // ANSI colors background - final val BLACK_B = "\033[40m"; - final val RED_B = "\033[41m"; - final val GREEN_B = "\033[42m"; - final val YELLOW_B = "\033[43m"; - final val BLUE_B = "\033[44m"; - final val MAGENTA_B = "\033[45m"; - final val CYAN_B = "\033[46m"; - final val WHITE_B = "\033[47m"; - - // ANSI styles - final val RESET = "\033[0m"; - final val BOLD = "\033[1m"; - final val UNDERLINED = "\033[4m"; - final val BLINK = "\033[5m"; - final val REVERSED = "\033[7m"; - final val INVISIBLE = "\033[8m"; - - private val outFluid = new Fluid[PrintStream](java.lang.System.out); - private val inFluid = new Fluid[BufferedReader]( - new BufferedReader(new InputStreamReader(java.lang.System.in))); - - private def out = outFluid.value - private def in = inFluid.value - - /** Set the default output stream. - * - * @param out the new output stream. - */ - def setOut(out: PrintStream): Unit = outFluid.value = out - - /** Set the default output stream for the duration - * of execution of one thunk. - * - * @param out the new output stream. - * @param thunk the code to execute with - * the new output stream active - */ - def withOut[T](out: PrintStream)(thunk: =>T): T = - outFluid.withValue(out)(thunk) - - /** Set the default output stream. - * - * @param@ out the new output stream. - */ - def setOut(out: OutputStream): Unit = - setOut(new PrintStream(out)) - - /** Set the default output stream for the duration - * of execution of one thunk. - * - * @param out the new output stream. - * @param thunk the code to execute with - * the new output stream active - */ - def withOut[T](out: OutputStream)(thunk: =>T): T = - withOut(new PrintStream(out))(thunk) - - - /** Set the default input stream. - * - * @param reader specifies the new input stream. - */ - def setIn(reader: Reader): Unit = { - inFluid.value = new BufferedReader(reader) - } - - /** Set the default input stream for the duration - * of execution of one thunk. - * - * @param in the new input stream. - * @param thunk the code to execute with - * the new input stream active - */ + import java.io._ + import java.text._ + + // ANSI colors foreground + final val BLACK = "\033[30m" + final val RED = "\033[31m" + final val GREEN = "\033[32m" + final val YELLOW = "\033[33m" + final val BLUE = "\033[34m" + final val MAGENTA = "\033[35m" + final val CYAN = "\033[36m" + final val WHITE = "\033[37m" + + // ANSI colors background + final val BLACK_B = "\033[40m" + final val RED_B = "\033[41m" + final val GREEN_B = "\033[42m" + final val YELLOW_B = "\033[43m" + final val BLUE_B = "\033[44m" + final val MAGENTA_B = "\033[45m" + final val CYAN_B = "\033[46m" + final val WHITE_B = "\033[47m" + + // ANSI styles + final val RESET = "\033[0m" + final val BOLD = "\033[1m" + final val UNDERLINED = "\033[4m" + final val BLINK = "\033[5m" + final val REVERSED = "\033[7m" + final val INVISIBLE = "\033[8m" + + private val outFluid = new Fluid[PrintStream](java.lang.System.out) + private val inFluid = new Fluid[BufferedReader]( + new BufferedReader(new InputStreamReader(java.lang.System.in))) + + private def out = outFluid.value + private def in = inFluid.value + + /** Set the default output stream. + * + * @param out the new output stream. + */ + def setOut(out: PrintStream): Unit = outFluid.value = out + + /** Set the default output stream for the duration + * of execution of one thunk. + * + * @param out the new output stream. + * @param thunk the code to execute with + * the new output stream active + * @return ... + */ + def withOut[T](out: PrintStream)(thunk: =>T): T = + outFluid.withValue(out)(thunk) + + /** Set the default output stream. + * + * @param@ out the new output stream. + */ + def setOut(out: OutputStream): Unit = + setOut(new PrintStream(out)) + + /** Set the default output stream for the duration + * of execution of one thunk. + * + * @param out the new output stream. + * @param thunk the code to execute with + * the new output stream active + * @return ... + */ + def withOut[T](out: OutputStream)(thunk: =>T): T = + withOut(new PrintStream(out))(thunk) + + + /** Set the default input stream. + * + * @param reader specifies the new input stream. + */ + def setIn(reader: Reader): Unit = { + inFluid.value = new BufferedReader(reader) + } + + /** Set the default input stream for the duration + * of execution of one thunk. + * + * @param in the new input stream. + * @param thunk the code to execute with + * the new input stream active + */ def withIn[T](reader: Reader)(thunk: =>T): T = inFluid.withValue(new BufferedReader(reader))(thunk) - /** Set the default input stream. - * - * @param in the new input stream. - */ - def setIn(in: InputStream): Unit = - setIn(new InputStreamReader(in)) - - /** Set the default input stream for the duration - * of execution of one thunk. - * - * @param in the new input stream. - * @param thunk the code to execute with - * the new input stream active - */ - def withIn[T](in: InputStream)(thunk: =>T): T = - withIn(new InputStreamReader(in))(thunk) - - /** Print an object on the terminal. - * - * @param obj the object to print. - */ - def print(obj: Any): Unit = { - if (obj == null) - out.print("null"); - else - out.print(obj.toString()); - } - - /** Flush the output stream. This function is required when partial - * output (i.e. output not terminated by a new line character) has - * to be made visible on the terminal. - */ - def flush: Unit = out.flush(); - - /** Print a new line character on the terminal. - */ - def println: Unit = { - out.println(); - } - - /** Print out an object followed by a new line character. - * - * @param x the object to print. - */ - def println(x: Any): Unit = { - out.println(x); - } - - /** Format and print out some text (in a fashion similar to printf in C). - * The format of the text to print is specified by the parameter - * <code>text</code>. The arguments that are inserted into specific - * locations in <code>text</code> are provided with parameter - * <code>args</code>. See class <code>java.text.MessageFormat</code> - * for a full specification of the format syntax. - * - * @param text the format of the text to print out. - * @param args the parameters used to instantiate the format. - */ - def printf(text: String)(args: Any*): Unit = { - // todo: Uncurry - if (text == null) - out.print("null"); - else - out.print(MessageFormat.format(text, textParams(args))); + /** Set the default input stream. + * + * @param in the new input stream. + */ + def setIn(in: InputStream): Unit = + setIn(new InputStreamReader(in)) + + /** Set the default input stream for the duration + * of execution of one thunk. + * + * @param in the new input stream. + * @param thunk the code to execute with + * the new input stream active + */ + def withIn[T](in: InputStream)(thunk: =>T): T = + withIn(new InputStreamReader(in))(thunk) + + /** Print an object on the terminal. + * + * @param obj the object to print. + */ + def print(obj: Any): Unit = + out.print(if (obj == null) "null" else obj.toString()) + + /** Flush the output stream. This function is required when partial + * output (i.e. output not terminated by a new line character) has + * to be made visible on the terminal. + */ + def flush: Unit = out.flush() + + /** Print a new line character on the terminal. + */ + def println: Unit = out.println() + + /** Print out an object followed by a new line character. + * + * @param x the object to print. + */ + def println(x: Any): Unit = out.println(x) + + /** Format and print out some text (in a fashion similar to printf in C). + * The format of the text to print is specified by the parameter + * <code>text</code>. The arguments that are inserted into specific + * locations in <code>text</code> are provided with parameter + * <code>args</code>. See class <code>java.text.MessageFormat</code> + * for a full specification of the format syntax. + * + * @param text the format of the text to print out. + * @param args the parameters used to instantiate the format. + */ + // todo: Uncurry + def printf(text: String)(args: Any*): Unit = + out.print( + if (text == null) "null" + else MessageFormat.format(text, textParams(args)) + ) + + /** Read a full line from the terminal. + * + * @return the string read from the terminal. + */ + def readLine: String = in.readLine() + + /** Read a boolean value from the terminal. + * + * @return the boolean value read from the terminal. + */ + def readBoolean: Boolean = in.readLine().toLowerCase() match { + case "true" => true + case "t" => true + case "yes" => true + case "y" => true + case _ => false + } + + /** Read a byte value from the terminal. + */ + def readByte: Byte = java.lang.Byte.decode(in.readLine()).byteValue() + + /** Read a short value from the terminal. + */ + def readShort: Short = java.lang.Short.decode(in.readLine()).shortValue() + + /** Read a char value from the terminal. + */ + def readChar: Char = in.readLine().charAt(0) + + /** Read an int value from the terminal. + */ + def readInt: Int = java.lang.Integer.decode(in.readLine()).intValue() + + /** Read a float value from the terminal. + */ + def readFloat: Float = + scala.runtime.compat.Platform.parseFloat(in.readLine()) + + /** Read a double value from the terminal. + */ + def readDouble: Double = + scala.runtime.compat.Platform.parseDouble(in.readLine()) + + /** Read in some structured input, specified by a format specifier. + * See class <code>java.text.MessageFormat</code> for details of + * the format specification. + * + * @param format the format of the input. + * @return a list of all extracted values. + */ + def readf(format: String): List[Any] = + textComponents(new MessageFormat(format).parse(in.readLine())) + + /** Read in some structured input, specified by a format specifier. + * Opposed to <code>readf</code>, this function only returns the + * first value extracted from the input according to the format + * specification. + * + * @param format ... + * @return ... + */ + def readf1(format: String): Any = readf(format).head + + /** Read in some structured input, specified by a format specifier. + * Opposed to <code>readf</code>, this function only returns the + * first two values extracted from the input according to the format + * specification. + * + * @param format ... + * @return ... + */ + def readf2(format: String): Pair[Any, Any] = { + val res = readf(format) + Pair(res.head, res.tail.head) + } + + /** Read in some structured input, specified by a format specifier. + * Opposed to <code>readf</code>, this function only returns the + * first three values extracted from the input according to the format + * specification. + * + * @param format ... + * @return ... + */ + def readf3(format: String): Triple[Any, Any, Any] = { + val res = readf(format) + Triple(res.head, res.tail.head, res.tail.tail.head) + } + + private def textComponents(a: Array[AnyRef]): List[Any] = { + var i: Int = a.length - 1 + var res: List[Any] = Nil + while (i >= 0) { + res = (a(i) match { + case x: java.lang.Boolean => x.booleanValue() + case x: java.lang.Byte => x.byteValue() + case x: java.lang.Short => x.shortValue() + case x: java.lang.Character => x.charValue() + case x: java.lang.Integer => x.intValue() + case x: java.lang.Long => x.longValue() + case x: java.lang.Float => x.floatValue() + case x: java.lang.Double => x.doubleValue() + case x => x + }) :: res; + i = i - 1 } - - /** Read a full line from the terminal. - * - * @return the string read from the terminal. - */ - def readLine: String = in.readLine(); - - /** Read a boolean value from the terminal. - * - * @return the boolean value read from the terminal. - */ - def readBoolean: Boolean = in.readLine().toLowerCase() match { - case "true" => true - case "t" => true - case "yes" => true - case "y" => true - case _ => false - } - - /** Read a byte value from the terminal. - */ - def readByte: Byte = java.lang.Byte.decode(in.readLine()).byteValue(); - - /** Read a short value from the terminal. - */ - def readShort: Short = java.lang.Short.decode(in.readLine()).shortValue(); - - /** Read a char value from the terminal. - */ - def readChar: Char = in.readLine().charAt(0); - - /** Read an int value from the terminal. - */ - def readInt: Int = java.lang.Integer.decode(in.readLine()).intValue(); - - /** Read a float value from the terminal. - */ - def readFloat: Float = - scala.runtime.compat.Platform.parseFloat(in.readLine()); - - /** Read a double value from the terminal. - */ - def readDouble: Double = - scala.runtime.compat.Platform.parseDouble(in.readLine()); - - /** Read in some structured input, specified by a format specifier. - * See class <code>java.text.MessageFormat</code> for details of - * the format specification. - * - * @param format the format of the input. - * @return a list of all extracted values. - */ - def readf(format: String): List[Any] = - textComponents(new MessageFormat(format).parse(in.readLine())); - - /** Read in some structured input, specified by a format specifier. - * Opposed to <code>readf</code>, this function only returns the - * first value extracted from the input according to the format - * specification. - */ - def readf1(format: String): Any = readf(format).head; - - /** Read in some structured input, specified by a format specifier. - * Opposed to <code>readf</code>, this function only returns the - * first two values extracted from the input according to the format - * specification. - */ - def readf2(format: String): Pair[Any, Any] = { - val res = readf(format); - Pair(res.head, res.tail.head) - } - - /** Read in some structured input, specified by a format specifier. - * Opposed to <code>readf</code>, this function only returns the - * first three values extracted from the input according to the format - * specification. - */ - def readf3(format: String): Triple[Any, Any, Any] = { - val res = readf(format); - Triple(res.head, res.tail.head, res.tail.tail.head) - } - - private def textComponents(a: Array[AnyRef]): List[Any] = { - var i: Int = a.length - 1; - var res: List[Any] = Nil; - while (i >= 0) { - res = (a(i) match { - case x: java.lang.Boolean => x.booleanValue() - case x: java.lang.Byte => x.byteValue() - case x: java.lang.Short => x.shortValue() - case x: java.lang.Character => x.charValue() - case x: java.lang.Integer => x.intValue() - case x: java.lang.Long => x.longValue() - case x: java.lang.Float => x.floatValue() - case x: java.lang.Double => x.doubleValue() - case x => x - }) :: res; - i = i - 1; - } - res - } - - private def textParams(s: Seq[Any]): Array[AnyRef] = { - val res = new Array[AnyRef](s.length); - var i: Int = 0; - val iter = s.elements; - while (iter.hasNext) { - res(i) = iter.next match { - case x: Boolean => new java.lang.Boolean(x); - case x: Byte => new java.lang.Byte(x); - case x: Short => new java.lang.Short(x); - case x: Char => new java.lang.Character(x); - case x: Int => new java.lang.Integer(x); - case x: Long => new java.lang.Long(x); - case x: Float => new java.lang.Float(x); - case x: Double => new java.lang.Double(x); - case x: Unit => "()"; - case x: AnyRef => x; - } - i = i + 1; - } - res + res + } + + private def textParams(s: Seq[Any]): Array[AnyRef] = { + val res = new Array[AnyRef](s.length); + var i: Int = 0; + val iter = s.elements; + while (iter.hasNext) { + res(i) = iter.next match { + case x: Boolean => new java.lang.Boolean(x) + case x: Byte => new java.lang.Byte(x) + case x: Short => new java.lang.Short(x) + case x: Char => new java.lang.Character(x) + case x: Int => new java.lang.Integer(x) + case x: Long => new java.lang.Long(x) + case x: Float => new java.lang.Float(x) + case x: Double => new java.lang.Double(x) + case x: Unit => "()" + case x: AnyRef => x + } + i = i + 1 } + res + } } diff --git a/src/library/scala/Enumeration.scala b/src/library/scala/Enumeration.scala index c484c5dc6a..031609e577 100644 --- a/src/library/scala/Enumeration.scala +++ b/src/library/scala/Enumeration.scala @@ -9,10 +9,10 @@ // $Id$ -package scala; +package scala -import scala.collection.mutable._; +import scala.collection.mutable._ /** * <p>The class <code>Enumeration</code> provides the same functionality as the @@ -40,100 +40,99 @@ import scala.collection.mutable._; */ abstract class Enumeration(initial: Int, names: String*) { - def this() = this(0, null); + def this() = this(0, null) - def this(names: String*) = this(0, names: _*); + def this(names: String*) = this(0, names: _*) - def name = { - val cname = scala.runtime.compat.Platform.getClassName(this); - if (cname.endsWith("$")) - cname.substring(0, cname.length() - 1); - else if (cname.endsWith("$class")) - cname.substring(0, cname.length() - 6); - else - cname; - } + def name = { + val cname = scala.runtime.compat.Platform.getClassName(this) + if (cname.endsWith("$")) + cname.substring(0, cname.length() - 1) + else if (cname.endsWith("$class")) + cname.substring(0, cname.length() - 6) + else + cname + } - /** - * A mapping between the enumeration value id and the enumeration - * object. - */ - private var values: Map[Int, Value] = new HashMap; + /** + * A mapping between the enumeration value id and the enumeration + * object. + */ + private var values: Map[Int, Value] = new HashMap - /** - * A cache listing all values of this enumeration. - */ - private var vcache: List[Value] = null; + /** + * A cache listing all values of this enumeration. + */ + private var vcache: List[Value] = null - private def updateCache: List[Value] = - if (vcache == null) { - vcache = values.values.toList.sort((p1, p2) => p1.id < p2.id); - vcache - } else - vcache; + private def updateCache: List[Value] = + if (vcache == null) { + vcache = values.values.toList.sort((p1, p2) => p1.id < p2.id); + vcache + } else + vcache; - protected var nextId = initial; + protected var nextId = initial - protected var nextName = names.elements; + protected var nextName = names.elements - private var topId = initial; + private var topId = initial - final def maxId = topId; + final def maxId = topId - /** - * Returns the enumeration value for the given id. - */ - final def apply(x: Int): Value = values(x); + /** + * Returns the enumeration value for the given id. + */ + final def apply(x: Int): Value = values(x) - /** - * Returns all values of this enumeration. - */ - final def elements: Iterator[Value] = updateCache.elements; + /** + * Returns all values of this enumeration. + */ + final def elements: Iterator[Value] = updateCache.elements - def foreach(f: Value => Unit): Unit = elements foreach f; + def foreach(f: Value => Unit): Unit = elements foreach f - def forall(p: Value => Boolean): Boolean = elements forall p; + def forall(p: Value => Boolean): Boolean = elements forall p - def exists(p: Value => Boolean): Boolean = elements exists p; + def exists(p: Value => Boolean): Boolean = elements exists p - def map[b](f: Value => b): Iterator[b] = elements map f; + def map[b](f: Value => b): Iterator[b] = elements map f - def flatMap[b](f: Value => Iterator[b]): Iterator[b] = elements flatMap f; + def flatMap[b](f: Value => Iterator[b]): Iterator[b] = elements flatMap f - def filter(p: Value => Boolean): Iterator[Value] = elements filter p; + def filter(p: Value => Boolean): Iterator[Value] = elements filter p - override def toString(): String = updateCache.mkString("{", ", ", "}"); + override def toString(): String = updateCache.mkString("{", ", ", "}") - protected final def Value: Value = - new Val(nextId, if (nextName.hasNext) nextName.next else null); + protected final def Value: Value = + new Val(nextId, if (nextName.hasNext) nextName.next else null) - protected final def Value(i: Int): Value = - new Val(i, if (nextName.hasNext) nextName.next else null); + protected final def Value(i: Int): Value = + new Val(i, if (nextName.hasNext) nextName.next else null) - protected final def Value(name: String): Value = new Val(nextId, name); + protected final def Value(name: String): Value = new Val(nextId, name) - protected final def Value(i: Int, name: String): Value = new Val(i, name); + protected final def Value(i: Int, name: String): Value = new Val(i, name) - abstract class Value extends Ordered[Value] { - def id: Int; - override def compare(that: Value): Int = this.id - that.id - } + abstract class Value extends Ordered[Value] { + def id: Int + override def compare(that: Value): Int = this.id - that.id + } - protected class Val(i: Int, name: String) extends Value { - def this(i: Int) = - this(i, if (nextName.hasNext) nextName.next else i.toString()); - def this(name: String) = this(nextId, name); - def this() = - this(nextId, if (nextName.hasNext) nextName.next else nextId.toString()); - assert(!values.isDefinedAt(i)); - values(i) = this; - nextId = i + 1; - if (nextId > topId) - topId = nextId; - def id = i; - override def toString() = if (name == null) - Enumeration.this.name + "(" + i + ")"; - else - name; - } + protected class Val(i: Int, name: String) extends Value { + def this(i: Int) = + this(i, if (nextName.hasNext) nextName.next else i.toString()) + def this(name: String) = this(nextId, name) + def this() = + this(nextId, if (nextName.hasNext) nextName.next else nextId.toString()) + assert(!values.isDefinedAt(i)) + values(i) = this + nextId = i + 1 + if (nextId > topId) + topId = nextId + def id = i + override def toString() = + if (name == null) Enumeration.this.name + "(" + i + ")" + else name + } } diff --git a/src/library/scala/Iterable.scala b/src/library/scala/Iterable.scala index 2a61ceaee4..0cc8ac3533 100644 --- a/src/library/scala/Iterable.scala +++ b/src/library/scala/Iterable.scala @@ -9,10 +9,14 @@ // $Id$ -package scala; +package scala -import Predef.error; +/** This object ... + * + * @author Matthias Zenger + * @version 1.1, 04/02/2004 + */ object Iterable { /* implicit def view[A <% Ordered[A]](x: Iterable[A]): Ordered[Iterable[A]] = @@ -35,11 +39,11 @@ object Iterable { */ /** The minimum element of a non-empty sequence of ordered elements */ def min[A <% Ordered[A]](seq: Iterable[A]): A = { - val xs = seq.elements; + val xs = seq.elements if (!xs.hasNext) error("min(<empty>)"); - var min = xs.next; + var min = xs.next while (xs.hasNext) { - val x = xs.next; + val x = xs.next if (x < min) min = x; } min @@ -47,11 +51,11 @@ object Iterable { /** The maximum element of a non-empty sequence of ordered elements */ def max[A <% Ordered[A]](seq: Iterable[A]): A = { - val xs = seq.elements; + val xs = seq.elements if (!xs.hasNext) error("max(<empty>)"); - var max = xs.next; + var max = xs.next while (xs.hasNext) { - val x = xs.next; + val x = xs.next if (max < x) max = x; } max @@ -68,95 +72,95 @@ object Iterable { */ trait Iterable[+A] { - /** Creates a new iterator over all elements contained in this - * object. - * - * @return the new iterator - */ - def elements: Iterator[A]; - - /** Concatenates two iterable objects - * - * @return the new iterable object - * @author buraq - */ - def concat[B >: A](that:Iterable[B]): Iterable[B] = new Iterable[B] { - def elements: Iterator[B] = Iterable.this.elements.append(that.elements); - } + /** Creates a new iterator over all elements contained in this + * object. + * + * @return the new iterator + */ + def elements: Iterator[A] + + /** Concatenates two iterable objects + * + * @return the new iterable object + * @author buraq + */ + def concat[B >: A](that: Iterable[B]): Iterable[B] = new Iterable[B] { + def elements: Iterator[B] = Iterable.this.elements.append(that.elements) + } - /** Apply a function <code>f</code> to all elements of this - * iterable object. - * - * @param f a function that is applied to every element. - */ - def foreach(f: A => Unit): Unit = elements.foreach(f); - - /** Apply a predicate <code>p</code> to all elements of this - * iterable object and return true, iff the predicate yields - * true for all elements. - * - * @param p the predicate - * @returns true, iff the predicate yields true for all elements. - */ - def forall(p: A => Boolean): Boolean = elements.forall(p); - - /** Apply a predicate <code>p</code> to all elements of this - * iterable object and return true, iff there is at least one - * element for which <code>p</code> yields true. - * - * @param p the predicate - * @returns true, iff the predicate yields true for at least one element. - */ - def exists(p: A => Boolean): Boolean = elements.exists(p); - - /** Find and return the first element of the iterable object satisfying a - * predicate, if any. - * - * @param p the predicate - * @return the first element in the iterable object satisfying <code>p</code>, - * or <code>None</code> if none exists. - */ - def find(p: A => Boolean): Option[A] = elements.find(p); - - /** Combines the elements of this list together using the binary - * operator <code>op</code>, from left to right, and starting with - * the value <code>z</code>. - * @return <code>op(... (op(op(z,a0),a1) ...), an)</code> if the list - * is <code>List(a0, a1, ..., an)</code>. - */ - def foldLeft[B](z: B)(op: (B, A) => B): B = elements.foldLeft(z)(op); - - /** Combines the elements of this list together using the binary - * operator <code>op</code>, from rigth to left, and starting with - * the value <code>z</code>. - * @return <code>a0 op (... op (an op z)...)</code> if the list - * is <code>[a0, a1, ..., an]</code>. - */ - def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op); - - /** Similar to <code>foldLeft</code> but can be used as - * an operator with the order of list and zero arguments reversed. - * That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code> - */ - def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f); - - /** An alias for <code>foldRight</code>. - * That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code> - */ - def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f); - - /** Checks if the other iterable object contains the same elements. - * - * @param that the other iterable object - * @return true, iff both iterable objects contain the same elements. - */ - def sameElements[B >: A](that: Iterable[B]): Boolean = { - val ita = this.elements; - val itb = that.elements; - var res = true; - while (res && ita.hasNext && itb.hasNext) { - res = (ita.next == itb.next); - } - !ita.hasNext && !itb.hasNext && res + /** Apply a function <code>f</code> to all elements of this + * iterable object. + * + * @param f a function that is applied to every element. + */ + def foreach(f: A => Unit): Unit = elements.foreach(f) + + /** Apply a predicate <code>p</code> to all elements of this + * iterable object and return true, iff the predicate yields + * true for all elements. + * + * @param p the predicate + * @returns true, iff the predicate yields true for all elements. + */ + def forall(p: A => Boolean): Boolean = elements.forall(p) + + /** Apply a predicate <code>p</code> to all elements of this + * iterable object and return true, iff there is at least one + * element for which <code>p</code> yields true. + * + * @param p the predicate + * @returns true, iff the predicate yields true for at least one element. + */ + def exists(p: A => Boolean): Boolean = elements.exists(p) + + /** Find and return the first element of the iterable object satisfying a + * predicate, if any. + * + * @param p the predicate + * @return the first element in the iterable object satisfying <code>p</code>, + * or <code>None</code> if none exists. + */ + def find(p: A => Boolean): Option[A] = elements.find(p) + + /** Combines the elements of this list together using the binary + * operator <code>op</code>, from left to right, and starting with + * the value <code>z</code>. + * @return <code>op(... (op(op(z,a0),a1) ...), an)</code> if the list + * is <code>List(a0, a1, ..., an)</code>. + */ + def foldLeft[B](z: B)(op: (B, A) => B): B = elements.foldLeft(z)(op) + + /** Combines the elements of this list together using the binary + * operator <code>op</code>, from rigth to left, and starting with + * the value <code>z</code>. + * @return <code>a0 op (... op (an op z)...)</code> if the list + * is <code>[a0, a1, ..., an]</code>. + */ + def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op) + + /** Similar to <code>foldLeft</code> but can be used as + * an operator with the order of list and zero arguments reversed. + * That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code> + */ + def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f) + + /** An alias for <code>foldRight</code>. + * That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code> + */ + def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f) + + /** Checks if the other iterable object contains the same elements. + * + * @param that the other iterable object + * @return true, iff both iterable objects contain the same elements. + */ + def sameElements[B >: A](that: Iterable[B]): Boolean = { + val ita = this.elements + val itb = that.elements + var res = true + while (res && ita.hasNext && itb.hasNext) { + res = (ita.next == itb.next) } + !ita.hasNext && !itb.hasNext && res + } } diff --git a/src/library/scala/IterableProxy.scala b/src/library/scala/IterableProxy.scala index 0b8ddc88df..188e06c6ef 100644 --- a/src/library/scala/IterableProxy.scala +++ b/src/library/scala/IterableProxy.scala @@ -9,7 +9,7 @@ // $Id$ -package scala; +package scala /** This class implements a proxy for iterable objects. It forwards @@ -20,80 +20,85 @@ package scala; */ trait IterableProxy[+A] extends Iterable[A] with Proxy { - def self: Iterable[A]; - - /** Creates a new iterator over all elements contained in this - * object. - * - * @return the new iterator - */ - def elements: Iterator[A] = self.elements; - - /** Apply a function <code>f</code> to all elements of this - * iterable object. - * - * @param f a function that is applied to every element. - */ - override def foreach(f: A => Unit): Unit = self.foreach(f); - - /** Apply a predicate <code>p</code> to all elements of this - * iterable object and return true, iff the predicate yields - * true for all elements. - * - * @param p the predicate - * @returns true, iff the predicate yields true for all elements. - */ - override def forall(p: A => Boolean): Boolean = self.forall(p); - - /** Apply a predicate <code>p</code> to all elements of this - * iterable object and return true, iff there is at least one - * element for which <code>p</code> yields true. - * - * @param p the predicate - * @returns true, iff the predicate yields true for at least one element. - */ - override def exists(p: A => Boolean): Boolean = self.exists(p); - - /** Find and return the first element of the iterable object satisfying a - * predicate, if any. - * - * @param p the predicate - * @return the first element in the iterable object satisfying <code>p</code>, - * or <code>None</code> if none exists. - */ - override def find(p: A => Boolean): Option[A] = self.find(p); - - /** Combines the elements of this list together using the binary - * operator <code>op</code>, from left to right, and starting with - * the value <code>z</code>. - * @return <code>op(... (op(op(z,a0),a1) ...), an)</code> if the list - * is <code>List(a0, a1, ..., an)</code>. - */ - override def foldLeft[B](z: B)(op: (B, A) => B): B = self.foldLeft(z)(op); - - /** Combines the elements of this list together using the binary - * operator <code>op</code>, from rigth to left, and starting with - * the value <code>z</code>. - * @return <code>a0 op (... op (an op z)...)</code> if the list - * is <code>[a0, a1, ..., an]</code>. - */ - override def foldRight[B](z: B)(op: (A, B) => B): B = self.foldRight(z)(op); - - /** Similar to <code>foldLeft</code> but can be used as - * an operator with the order of list and zero arguments reversed. - * That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code> - */ - override def /:[B](z: B)(f: (B, A) => B): B = self./:(z)(f); - - /** An alias for <code>foldRight</code>. - * That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code> - */ - override def :\[B](z: B)(f: (A, B) => B): B = self.:\(z)(f); - - /** Checks if the other iterable object contains the same elements. - * - * @param that the other iterable object - * @return true, iff both iterable objects contain the same elements. - */ - override def sameElements[B >: A](that: Iterable[B]): Boolean = self.sameElements(that); + def self: Iterable[A] + + /** Creates a new iterator over all elements contained in this + * object. + * + * @return the new iterator + */ + def elements: Iterator[A] = self.elements + + /** Apply a function <code>f</code> to all elements of this + * iterable object. + * + * @param f a function that is applied to every element. + */ + override def foreach(f: A => Unit): Unit = self.foreach(f) + + /** Apply a predicate <code>p</code> to all elements of this + * iterable object and return true, iff the predicate yields + * true for all elements. + * + * @param p the predicate + * @returns true, iff the predicate yields true for all elements. + */ + override def forall(p: A => Boolean): Boolean = self.forall(p) + + /** Apply a predicate <code>p</code> to all elements of this + * iterable object and return true, iff there is at least one + * element for which <code>p</code> yields true. + * + * @param p the predicate + * @returns true, iff the predicate yields true for at least one element. + */ + override def exists(p: A => Boolean): Boolean = self.exists(p) + + /** Find and return the first element of the iterable object satisfying a + * predicate, if any. + * + * @param p the predicate + * @return the first element in the iterable object satisfying <code>p</code>, + * or <code>None</code> if none exists. + */ + override def find(p: A => Boolean): Option[A] = self.find(p) + + /** Combines the elements of this list together using the binary + * operator <code>op</code>, from left to right, and starting with + * the value <code>z</code>. + * @return <code>op(... (op(op(z,a0),a1) ...), an)</code> if the list + * is <code>List(a0, a1, ..., an)</code>. + */ + override def foldLeft[B](z: B)(op: (B, A) => B): B = self.foldLeft(z)(op) + + /** Combines the elements of this list together using the binary + * operator <code>op</code>, from rigth to left, and starting with + * the value <code>z</code>. + * @return <code>a0 op (... op (an op z)...)</code> if the list + * is <code>[a0, a1, ..., an]</code>. + */ + override def foldRight[B](z: B)(op: (A, B) => B): B = self.foldRight(z)(op) + + /** Similar to <code>foldLeft</code> but can be used as + * an operator with the order of list and zero arguments reversed. + * That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code> + */ + override def /:[B](z: B)(f: (B, A) => B): B = self./:(z)(f) + + /** An alias for <code>foldRight</code>. + * That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code> + * + * @param z ... + * @param f ... + * @return ... + */ + override def :\[B](z: B)(f: (A, B) => B): B = self.:\(z)(f) + + /** Checks if the other iterable object contains the same elements. + * + * @param that the other iterable object + * @return true, iff both iterable objects contain the same elements. + */ + override def sameElements[B >: A](that: Iterable[B]): Boolean = + self.sameElements(that) } diff --git a/src/library/scala/Iterator.scala b/src/library/scala/Iterator.scala index 8d6de4871e..60774e9a05 100644 --- a/src/library/scala/Iterator.scala +++ b/src/library/scala/Iterator.scala @@ -9,10 +9,10 @@ // $Id$ -package scala; +package scala -import Predef._; +import Predef._ /** The <code>Iterator</code> object provides various functions for * creating specialized iterators. @@ -24,45 +24,53 @@ import Predef._; object Iterator { def empty[a] = new Iterator[a] { - def hasNext: Boolean = false; - def next: a = Predef.error("next on empty iterator"); + def hasNext: Boolean = false + def next: a = Predef.error("next on empty iterator") } def single[a](x: a) = new Iterator[a] { - private var hasnext = true; - def hasNext: Boolean = hasnext; - def next: a = if (hasnext) { hasnext = false; x } else Predef.error("next on empty iterator"); + private var hasnext = true + def hasNext: Boolean = hasnext + def next: a = + if (hasnext) { hasnext = false; x } + else Predef.error("next on empty iterator") } - def fromValues[a](xs: a*) = xs.elements; + def fromValues[a](xs: a*) = xs.elements def fromArray[a](xs: Array[a]): Iterator[a] = - fromArray(xs, 0, xs.length); + fromArray(xs, 0, xs.length) + /** + * @param xs ... + * @param start ... + * @param length ... + * @return ... + */ def fromArray[a](xs: Array[a], start: Int, length: Int): Iterator[a] = new BufferedIterator[a] { - private var i = start; - val end = if ((start + length) < xs.length) start else xs.length; - def hasNext: Boolean = i < end; + private var i = start + val end = if ((start + length) < xs.length) start else xs.length + def hasNext: Boolean = i < end def next: a = if (hasNext) { val x = xs(i) ; i = i + 1 ; x } - else Predef.error("next on empty iterator"); + else Predef.error("next on empty iterator") def head: a = if (hasNext) xs(i); - else Predef.error("head on empty iterator"); + else Predef.error("head on empty iterator") } def fromString(str: String): Iterator[Char] = new BufferedIterator[Char] { - private var i = 0; - private val len = str.length(); - def hasNext = i < len; - def next = { val c = str charAt i; i = i + 1; c }; - def head = str charAt i; + private var i = 0 + private val len = str.length() + def hasNext = i < len + def next = { val c = str charAt i; i = i + 1; c } + def head = str charAt i } def fromCaseClass(n:CaseClass): Iterator[Any] = new Iterator[Any] { - private var c:Int = 0; - private val cmax = n.caseArity; - def hasNext = c < cmax; + private var c: Int = 0 + private val cmax = n.caseArity + def hasNext = c < cmax def next = { val a = n caseElement c; c = c + 1; a } } @@ -76,7 +84,7 @@ object Iterator { * @return the iterator with values in range [lo;end). */ def range(lo: Int, end: Int): Iterator[Int] = - range(lo, end, 1); + range(lo, end, 1) /** Create an iterator with elements * <code>e<sub>n+1</sub> = e<sub>n</sub> + step</code> @@ -89,14 +97,16 @@ object Iterator { * @return the iterator with values in range [lo;end). */ def range(lo: Int, end: Int, step: Int): Iterator[Int] = { - assert(step != 0); + assert(step != 0) new BufferedIterator[Int] { - private var i = lo; - def hasNext: Boolean = if (step > 0) i < end else i > end; + private var i = lo + def hasNext: Boolean = if (step > 0) i < end else i > end def next: Int = - if (hasNext) { val j = i; i = i + step; j } else Predef.error("next on empty iterator"); + if (hasNext) { val j = i; i = i + step; j } + else Predef.error("next on empty iterator") def head: Int = - if (hasNext) i else Predef.error("head on empty iterator"); + if (hasNext) i + else Predef.error("head on empty iterator") } } @@ -112,12 +122,14 @@ object Iterator { */ def range(lo: Int, end: Int, step: Int => Int): Iterator[Int] = new BufferedIterator[Int] { - private var i = lo; - def hasNext: Boolean = i < end; + private var i = lo + def hasNext: Boolean = i < end def next: Int = - if (i < end) { val j = i; i = step(i); j } else Predef.error("next on empty iterator"); + if (i < end) { val j = i; i = step(i); j } + else Predef.error("next on empty iterator") def head: Int = - if (i < end) i else Predef.error("head on empty iterator"); + if (i < end) i + else Predef.error("head on empty iterator") } /** Create an iterator with elements @@ -128,7 +140,7 @@ object Iterator { * @return the iterator starting at value <code>lo</code>. */ def from(lo: Int): Iterator[Int] = - from(lo, 1); + from(lo, 1) /** Create an iterator with elements * <code>e<sub>n+1</sub> = e<sub>n</sub> + step</code> @@ -140,10 +152,10 @@ object Iterator { */ def from(lo: Int, step: Int): Iterator[Int] = new BufferedIterator[Int] { - private var i = lo; - def hasNext: Boolean = true; + private var i = lo + def hasNext: Boolean = true def next: Int = { val j = i; i = i + step; j } - def head: Int = i; + def head: Int = i } /** Create an iterator with elements @@ -156,10 +168,10 @@ object Iterator { */ def from(lo: Int, step: Int => Int): Iterator[Int] = new BufferedIterator[Int] { - private var i = lo; - def hasNext: Boolean = true; + private var i = lo + def hasNext: Boolean = true def next: Int = { val j = i; i = step(i); j } - def head: Int = i; + def head: Int = i } } @@ -177,33 +189,33 @@ trait Iterator[+A] { /** Does this iterator provide another element? */ - def hasNext: Boolean; + def hasNext: Boolean /** Returns the next element. */ - def next: A; + def next: A /** Returns a new iterator that iterates only over the first <code>n</code> * elements. */ def take(n: Int) = new Iterator[A] { - var remaining = n; - def hasNext = remaining > 0 && Iterator.this.hasNext; + var remaining = n + def hasNext = remaining > 0 && Iterator.this.hasNext def next: A = if (hasNext) { remaining = remaining - 1; Iterator.this.next } - else error("next on empty iterator"); + else error("next on empty iterator") } /** Removes the first <code>n</code> elements from this iterator. */ def drop(n: Int): Iterator[A] = - if (n > 0) { next; drop(n - 1) } else this; + if (n > 0) { next; drop(n - 1) } else this /** Returns a new iterator that maps all elements of this iterator * to new elements using function <code>f</code>. */ def map[B](f: A => B): Iterator[B] = new Iterator[B] { - def hasNext = Iterator.this.hasNext; + def hasNext = Iterator.this.hasNext def next = f(Iterator.this.next) } @@ -211,8 +223,8 @@ trait Iterator[+A] { * iterator followed by the elements provided by iterator <code>that</code>. */ def append[B >: A](that: Iterator[B]) = new Iterator[B] { - def hasNext = Iterator.this.hasNext || that.hasNext; - def next = if (Iterator.this.hasNext) Iterator.this.next else that.next; + def hasNext = Iterator.this.hasNext || that.hasNext + def next = if (Iterator.this.hasNext) Iterator.this.next else that.next } /** Applies the given function <code>f</code> to each element of @@ -223,19 +235,19 @@ trait Iterator[+A] { * yields the elements <code>a0, ..., an</code>. */ def flatMap[B](f: A => Iterator[B]): Iterator[B] = new Iterator[B] { - private var cur: Iterator[B] = Iterator.empty; + private var cur: Iterator[B] = Iterator.empty def hasNext: Boolean = if (cur.hasNext) true else if (Iterator.this.hasNext) { - cur = f(Iterator.this.next); + cur = f(Iterator.this.next) hasNext - } else false; + } else false def next: B = if (cur.hasNext) cur.next else if (Iterator.this.hasNext) { - cur = f(Iterator.this.next); + cur = f(Iterator.this.next) next - } else Predef.error("next on empty iterator"); + } else Predef.error("next on empty iterator") } /** Returns an iterator over all the elements of this iterator that @@ -246,13 +258,13 @@ trait Iterator[+A] { * @return the elements of this iterator satisfying <code>p</code>. */ def filter(p: A => Boolean): Iterator[A] = new BufferedIterator[A] { - private var hd: A = _; - private var ahead: Boolean = false; - private var hasMore = Iterator.this.hasNext; + private var hd: A = _ + private var ahead: Boolean = false + private var hasMore = Iterator.this.hasNext private def skip: Unit = while (!ahead && hasMore) { - hd = Iterator.this.next; - hasMore = Iterator.this.hasNext; + hd = Iterator.this.next + hasMore = Iterator.this.hasNext ahead = p(hd) } def hasNext: Boolean = { skip; ahead || hasMore } @@ -273,8 +285,8 @@ trait Iterator[+A] { * <code>bi</code> are the elements from iterator <code>that</code>. */ def zip[B](that: Iterator[B]) = new Iterator[Pair[A, B]] { - def hasNext = Iterator.this.hasNext && that.hasNext; - def next = Pair(Iterator.this.next, that.next); + def hasNext = Iterator.this.hasNext && that.hasNext + def next = Pair(Iterator.this.next, that.next) } @@ -301,7 +313,7 @@ trait Iterator[+A] { * * @param f a function that is applied to every element. */ - def foreach(f: A => Unit): Unit = while (hasNext) { f(next) }; + def foreach(f: A => Unit): Unit = while (hasNext) { f(next) } /** Apply a predicate <code>p</code> to all elements of this * iterable object and return true, iff the predicate yields @@ -311,7 +323,7 @@ trait Iterator[+A] { * @returns true, iff the predicate yields true for all elements. */ def forall(p: A => Boolean): Boolean = { - var res = true; + var res = true while (res && hasNext) { res = p(next) } res } @@ -324,7 +336,7 @@ trait Iterator[+A] { * @returns true, iff the predicate yields true for at least one element. */ def exists(p: A => Boolean): Boolean = { - var res = false; + var res = false while (!res && hasNext) { res = p(next) } res } @@ -335,132 +347,135 @@ trait Iterator[+A] { * @return True iff there is an element of this list which is * equal (w.r.t. <code>==</code>) to <code>elem</code>. */ - def contains(elem: Any): Boolean = exists { x => x == elem }; - - /** Find and return the first element of the iterable object satisfying a - * predicate, if any. - * - * @param p the predicate - * @return the first element in the iterable object satisfying <code>p</code>, - * or <code>None</code> if none exists. - */ - def find(p: A => Boolean): Option[A] = { - var res: Option[A] = None; - while (res.isEmpty && hasNext) { - val e = next; - if (p(e)) res = Some(e); - } - res - } + def contains(elem: Any): Boolean = exists { x => x == elem } - /** Combines the elements of this list together using the binary - * operator <code>op</code>, from left to right, and starting with - * the value <code>z</code>. - * @return <code>op(... (op(op(z,a0),a1) ...), an)</code> if the list - * is <code>List(a0, a1, ..., an)</code>. - */ - def foldLeft[B](z: B)(op: (B, A) => B): B = { - var acc = z; - while (hasNext) { acc = op(acc, next) } - acc + /** Find and return the first element of the iterable object satisfying a + * predicate, if any. + * + * @param p the predicate + * @return the first element in the iterable object satisfying <code>p</code>, + * or <code>None</code> if none exists. + */ + def find(p: A => Boolean): Option[A] = { + var res: Option[A] = None + while (res.isEmpty && hasNext) { + val e = next + if (p(e)) res = Some(e); } + res + } - /** Combines the elements of this list together using the binary - * operator <code>op</code>, from rigth to left, and starting with - * the value <code>z</code>. - * @return <code>a0 op (... op (an op z)...)</code> if the list - * is <code>[a0, a1, ..., an]</code>. - */ - def foldRight[B](z: B)(op: (A, B) => B): B = { - def fold(z: B): B = - if (hasNext) op(next, fold(z)) else z; - fold(z) - } + /** Combines the elements of this list together using the binary + * operator <code>op</code>, from left to right, and starting with + * the value <code>z</code>. + * @return <code>op(... (op(op(z,a0),a1) ...), an)</code> if the list + * is <code>List(a0, a1, ..., an)</code>. + */ + def foldLeft[B](z: B)(op: (B, A) => B): B = { + var acc = z + while (hasNext) { acc = op(acc, next) } + acc + } - /** Similar to <code>foldLeft</code> but can be used as - * an operator with the order of list and zero arguments reversed. - * That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code> - */ - def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f); - - /** An alias for <code>foldRight</code>. - * That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code> - */ - def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f); - - /** Returns a buffered iterator from this iterator. - */ - def buffered: BufferedIterator[A] = new BufferedIterator[A] { - private var hd: A = _; - private var ahead: Boolean = false; - def head: A = { - if (!ahead) { - hd = Iterator.this.next; - ahead = true - } - hd - } - def next: A = - if (ahead) { ahead = false; hd } else head; - def hasNext: Boolean = ahead || Iterator.this.hasNext; - } + /** Combines the elements of this list together using the binary + * operator <code>op</code>, from rigth to left, and starting with + * the value <code>z</code>. + * @return <code>a0 op (... op (an op z)...)</code> if the list + * is <code>[a0, a1, ..., an]</code>. + */ + def foldRight[B](z: B)(op: (A, B) => B): B = { + def fold(z: B): B = + if (hasNext) op(next, fold(z)) else z; + fold(z) + } - /** Returns a counted iterator from this iterator. - */ - def counted = new CountedIterator[A] { - private var cnt = -1; - def count = cnt; - def hasNext: Boolean = Iterator.this.hasNext; - def next: A = { cnt = cnt + 1; Iterator.this.next } + /** Similar to <code>foldLeft</code> but can be used as + * an operator with the order of list and zero arguments reversed. + * That is, <code>z /: xs</code> is the same as <code>xs foldLeft z</code> + */ + def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f) + + /** An alias for <code>foldRight</code>. + * That is, <code>xs :\ z</code> is the same as <code>xs foldRight z</code> + */ + def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f) + + /** Returns a buffered iterator from this iterator. + */ + def buffered: BufferedIterator[A] = new BufferedIterator[A] { + private var hd: A = _ + private var ahead: Boolean = false + def head: A = { + if (!ahead) { + hd = Iterator.this.next; + ahead = true + } + hd } + def next: A = + if (ahead) { ahead = false; hd } else head; + def hasNext: Boolean = ahead || Iterator.this.hasNext + } + + /** Returns a counted iterator from this iterator. + */ + def counted = new CountedIterator[A] { + private var cnt = -1 + def count = cnt + def hasNext: Boolean = Iterator.this.hasNext + def next: A = { cnt = cnt + 1; Iterator.this.next } + } - /** Creates two new iterators that both iterate over the same elements - * than this iterator (in the same order). - */ - def duplicate: Pair[Iterator[A], Iterator[A]] = { - var xs: List[A] = Nil; - var ahead: Iterator[A] = null; - class Partner extends Iterator[A] { - var ys: List[A] = Nil; - def hasNext: Boolean = Iterator.this.synchronized ( - ((this == ahead) && Iterator.this.hasNext) || - ((this != ahead) && (!xs.isEmpty || !ys.isEmpty || Iterator.this.hasNext)) - ); - def next: A = Iterator.this.synchronized { - if (this == ahead) { - val e = Iterator.this.next; - xs = e :: xs; e - } else { - if (ys.isEmpty) { - ys = xs.reverse; - xs = Nil; - } - ys match { - case Nil => val e = Iterator.this.next; - ahead = this; - xs = e :: xs; e - case z :: zs => ys = zs; z - } - } - } + /** Creates two new iterators that both iterate over the same elements + * than this iterator (in the same order). + */ + def duplicate: Pair[Iterator[A], Iterator[A]] = { + var xs: List[A] = Nil + var ahead: Iterator[A] = null + class Partner extends Iterator[A] { + var ys: List[A] = Nil + def hasNext: Boolean = Iterator.this.synchronized ( + ((this == ahead) && Iterator.this.hasNext) || + ((this != ahead) && (!xs.isEmpty || !ys.isEmpty || Iterator.this.hasNext)) + ) + def next: A = Iterator.this.synchronized { + if (this == ahead) { + val e = Iterator.this.next + xs = e :: xs; e + } else { + if (ys.isEmpty) { + ys = xs.reverse + xs = Nil + } + ys match { + case Nil => + val e = Iterator.this.next + ahead = this + xs = e :: xs; e + case z :: zs => + ys = zs; z + } } - ahead = new Partner; - Pair(ahead, new Partner) + } } + ahead = new Partner + Pair(ahead, new Partner) + } /** Fills the given array <code>xs</code> with the elements of * this sequence starting at position <code>start</code>. * * @param xs the array to fill. * @param start starting index. - * @return the given array <code>xs</code> filled with the elements of this iterator. + * @return the given array <code>xs</code> filled with the elements of + * this iterator. * @pre The array must be large enough to hold all elements. */ def copyToArray[B >: A](xs: Array[B], start: Int): Array[B] = { - var i = start; + var i = start while (hasNext) { - xs(i) = next; - i = i + 1; + xs(i) = next + i = i + 1 } xs } @@ -470,9 +485,9 @@ trait Iterator[+A] { * @return a list which enumerates all elements of this iterator. */ def toList: List[A] = { - val res = new collection.mutable.ListBuffer[A]; + val res = new collection.mutable.ListBuffer[A] while (hasNext) { - res += next; + res += next } res.toList } diff --git a/src/library/scala/MatchError.scala b/src/library/scala/MatchError.scala index 6f2c3ea95e..a26c5087ce 100644 --- a/src/library/scala/MatchError.scala +++ b/src/library/scala/MatchError.scala @@ -9,7 +9,7 @@ // $Id$ -package scala; +package scala import Predef._ @@ -24,7 +24,8 @@ import Predef._ object MatchError { // todo: change pattern matcher so that dummy type parameter T can be removed. - def fail[T](source: String, line: Int): Nothing = throw new MatchError(source, line); + def fail[T](source: String, line: Int): Nothing = + throw new MatchError(source, line) def report(source: String, line: Int, obj: Any) = try { @@ -36,11 +37,12 @@ object MatchError { } final class MatchError(msg: String) extends Error(msg) { - def this(source: String, line: Int) = - this(" in '" + source + "' at line " + line); - def this(source: String, line: Int, obj: String) = - this("for object " + obj + " in '" + source + "' at line " + line); + def this(source: String, line: Int) = + this(" in '" + source + "' at line " + line) - def this(ob:Any) = - this(ob.toString()); + def this(source: String, line: Int, obj: String) = + this("for object " + obj + " in '" + source + "' at line " + line) + + def this(ob: Any) = + this(ob.toString()) } diff --git a/src/library/scala/Proxy.scala b/src/library/scala/Proxy.scala index 64e2a333f8..b32c53b12d 100644 --- a/src/library/scala/Proxy.scala +++ b/src/library/scala/Proxy.scala @@ -9,7 +9,7 @@ // $Id$ -package scala; +package scala /** This class implements a simple proxy that forwards all calls to @@ -21,8 +21,8 @@ package scala; * @version 1.0, 26/04/2004 */ trait Proxy { - def self: Any; - override def hashCode(): Int = self.hashCode(); - override def equals(y: Any): Boolean = self.equals(y); - override def toString(): String = self.toString(); + def self: Any + override def hashCode(): Int = self.hashCode() + override def equals(y: Any): Boolean = self.equals(y) + override def toString(): String = self.toString() } diff --git a/src/library/scala/Responder.scala b/src/library/scala/Responder.scala index 7bd4967059..050caa342e 100644 --- a/src/library/scala/Responder.scala +++ b/src/library/scala/Responder.scala @@ -1,18 +1,40 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2005-2006, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id$ + package scala -/** contains utility methods to build responders +/** This object contains utility methods to build responders. + * + * @author Burak Emir + * @version 1.0 + * * @see class Responder * @since revision 6897 (will be 2.1.1) */ object Responder { - /** creates a responder that answer continuations with the constant a */ + /** Creates a responder that answer continuations with the constant + * <code>a</code>. + * + * @param x ... + * @return ... + */ def constant[a](x: a) = new Responder[a] { def respond(k: a => unit) = k(x) } - /** executes x and returns true, useful as syntactic convenience in - * for comprehensions + /** Executes <code>x</code> and returns <code>true</code>, useful + * as syntactic convenience in for comprehensions. + * + * @param x ... + * @return ... */ def exec[a](x: => unit): boolean = { x; true } @@ -38,6 +60,10 @@ object Responder { * in for comprehensions, one can embed domain-specific languages in * Scala while giving the impression that programs in these DSLs are * written in direct style. + * + * @author Burak Emir + * @version 1.0 + * * @since revision 6897 (will be 2.1.1) */ abstract class Responder[+a] { diff --git a/src/library/scala/Seq.scala b/src/library/scala/Seq.scala index 5c04001c87..7eec547b36 100644 --- a/src/library/scala/Seq.scala +++ b/src/library/scala/Seq.scala @@ -9,20 +9,20 @@ // $Id$ -package scala; +package scala -import scala.runtime.compat.StringBuilder; +import scala.runtime.compat.StringBuilder object Seq { /** builds a singleton sequence * @author buraq */ - def single[A](x:A) = new Seq[A] { - def length = 1; - def elements = Iterator.single(x); - override def isDefinedAt(x: Int): Boolean = (x == 0); - def apply(i:Int) = x; // caller's responsibility to check isDefinedAt + def single[A](x: A) = new Seq[A] { + def length = 1 + def elements = Iterator.single(x) + override def isDefinedAt(x: Int): Boolean = (x == 0) + def apply(i: Int) = x // caller's responsibility to check isDefinedAt } /* implicit def view[A <% Ordered[A]](xs: Seq[A]): Ordered[Seq[A]] = @@ -55,63 +55,60 @@ object Seq { trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Iterable[A] { /** Returns the length of the sequence. - * - * @return the sequence length. - */ - def length: Int; + * + * @return the sequence length. + */ + def length: Int /** Returns the concatenation of two sequences. * * @return concatenation of this sequence with argument * @author buraq */ - def concat[B >: A](that:Seq[B]): Seq[B] = new Seq[B] { - def length = Seq.this.length + that.length; - def elements: Iterator[B] = Seq.this.elements.append(that.elements); - def apply(i:Int) = { - if(Seq.this.isDefinedAt(i)) - Seq.this.apply(i) - else - that.apply(i - Seq.this.length); - } + def concat[B >: A](that: Seq[B]): Seq[B] = new Seq[B] { + def length = Seq.this.length + that.length + def elements: Iterator[B] = Seq.this.elements.append(that.elements) + def apply(i: Int) = + if (Seq.this.isDefinedAt(i)) Seq.this.apply(i) + else that.apply(i - Seq.this.length) } /** Is this partial function defined for the index <code>x</code>? - * - * @return true, iff <code>x</code> is a legal sequence index. - */ - def isDefinedAt(x: Int): Boolean = (x >= 0) && (x < length); + * + * @return true, iff <code>x</code> is a legal sequence index. + */ + def isDefinedAt(x: Int): Boolean = (x >= 0) && (x < length) /** Returns the index of the first occurence of the specified - * object in this sequence. - * - * @param elem element to search for. - * @return the index in this sequence of the first occurence of the specified - * element, or -1 if the sequence does not contain this element. - */ + * object in this sequence. + * + * @param elem element to search for. + * @return the index in this sequence of the first occurence of the + * specified element, or -1 if the sequence does not contain + * this element. + */ def indexOf[B >: A](elem: B): Int = { - val it = elements; - var i = 0; - var found = false; + val it = elements + var i = 0 + var found = false while (!found && it.hasNext) { if (it.next == elem) { - found = true; + found = true } else { i = i + 1 } } - if (found) i else -1; + if (found) i else -1 } - /** Returns the index of the last occurence of the specified - * element in this sequence, or -1 if the sequence does not - * contain this element. - * - * @param elem element to search for. - * @return the index in this sequence of the last occurence of the - * specified element, or -1 if the sequence does not contain - * this element. - */ + /** Returns the index of the last occurence of the specified element + * in this sequence, or -1 if the sequence does not contain this element. + * + * @param elem element to search for. + * @return the index in this sequence of the last occurence of the + * specified element, or -1 if the sequence does not contain + * this element. + */ def lastIndexOf[B >: A](elem: B): Int = { var i = length; var found = false; @@ -125,13 +122,17 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Iterable[A] { } /** Returns the sub-sequence starting from index <code>n</code>. - */ - def take(n: Int): Seq[A] = subseq(0, n); + * + * @param n ... + */ + def take(n: Int): Seq[A] = subseq(0, n) /** Returns a new sub-sequence that drops the first <code>n</code> - * elements of this sequence. - */ - def drop(n: Int): Seq[A] = subseq(n, length - n); + * elements of this sequence. + * + * @param n ... + */ + def drop(n: Int): Seq[A] = subseq(n, length - n) /** Returns a subsequence starting from index <code>from</code> * consisting of <code>len</code> elements. @@ -153,28 +154,29 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Iterable[A] { Predef.error("cannot create subsequence"); /** Transform this sequence into a list of all elements. - * - * @return a list which enumerates all elements of this sequence. - */ - def toList: List[A] = elements.toList; + * + * @return a list which enumerates all elements of this sequence. + */ + def toList: List[A] = elements.toList /** Converts this sequence to a fresh Array */ - def toArray[B >: A]: Array[B] = elements.copyToArray(new Array[B](length), 0); + def toArray[B >: A]: Array[B] = + elements.copyToArray(new Array[B](length), 0) /** Fills the given array <code>xs</code> with the elements of - * this sequence starting at position <code>start</code>. - * - * @param xs the array to fill. - * @param start starting index. - * @return the given array <code>xs</code> filled with this list. - */ + * this sequence starting at position <code>start</code>. + * + * @param xs the array to fill. + * @param start starting index. + * @return the given array <code>xs</code> filled with this list. + */ def copyToArray[B >: A](xs: Array[B], start: Int): Array[B] = - elements.copyToArray(xs, start); + elements.copyToArray(xs, start) /** Customizes the <code>toString</code> method. - * - * @return a string representation of this sequence. - */ + * + * @return a string representation of this sequence. + */ override def toString() = mkString(stringPrefix+"(", ",", ")") /** Returns a string representation of this sequence. The resulting string @@ -204,7 +206,7 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Iterable[A] { } /** Defines the prefix of the string representation. - */ - protected def stringPrefix: String = "Seq"; + */ + protected def stringPrefix: String = "Seq" } diff --git a/src/library/scala/SeqProxy.scala b/src/library/scala/SeqProxy.scala index 0828349deb..b83894b3d6 100644 --- a/src/library/scala/SeqProxy.scala +++ b/src/library/scala/SeqProxy.scala @@ -9,7 +9,7 @@ // $Id$ -package scala; +package scala /** Class <code>Seq[A]</code> represents finite sequences of elements @@ -21,73 +21,84 @@ package scala; */ trait SeqProxy[+A] extends Seq[A] with IterableProxy[A] { - def self: Seq[A]; - - /** Returns the length of the sequence. - * - * @return the sequence length. - */ - def length: Int = self.length; - - /** Access element number <code>n</code>. - * - * @return the element at index <code>n</code>. - */ - def apply(n: Int): A = self.apply(n); - - /** Is this partial function defined for the index <code>x</code>? - * - * @return true, iff <code>x</code> is a legal sequence index. - */ - override def isDefinedAt(y: Int): Boolean = self.isDefinedAt(y); - - /** Returns the index of the first occurence of the specified - * object in this sequence. - * - * @param elem element to search for. - * @return the index in this sequence of the first occurence of the specified - * element, or -1 if the sequence does not contain this element. - */ - override def indexOf[B >: A](elem: B): Int = self.indexOf(elem); - - /** Returns the index of the last occurence of the specified - * element in this sequence, or -1 if the sequence does not - * contain this element. - * - * @param elem element to search for. - * @return the index in this sequence of the last occurence of the - * specified element, or -1 if the sequence does not contain - * this element. - */ - override def lastIndexOf[B >: A](elem: B): Int = self.lastIndexOf(elem); - - /** Returns the sub-sequence starting from index <code>n</code>. - */ - override def take(n: Int): Seq[A] = self.take(n); - - /** Returns a new sub-sequence that drops the first <code>n</code> - * elements of this sequence. - */ - override def drop(n: Int): Seq[A] = self.drop(n); - - /** Returns a subsequence starting from index <code>from</code> - * consisting of <code>len</code> elements. - */ - override def subseq(from: Int, len: Int): Seq[A] = self.subseq(from, len); - - /** Fills the given array <code>xs</code> with the elements of - * this sequence starting at position <code>start</code>. - * - * @param xs the array to fill. - * @param start starting index. - * @return the given array <code>xs</code> filled with the elements - * of this sequence. - */ - override def copyToArray[B >: A](xs: Array[B], start: Int): Array[B] = self.copyToArray(xs, start); - - /** Transform this sequence into a list of all elements. - * - * @return a list which enumerates all elements of this sequence. - */ - override def toList: List[A] = self.toList; + def self: Seq[A] + + /** Returns the length of the sequence. + * + * @return the sequence length. + */ + def length: Int = self.length + + /** Access element number <code>n</code>. + * + * @return the element at index <code>n</code>. + */ + def apply(n: Int): A = self.apply(n) + + /** Is this partial function defined for the index <code>x</code>? + * + * @return true, iff <code>x</code> is a legal sequence index. + */ + override def isDefinedAt(y: Int): Boolean = self.isDefinedAt(y) + + /** Returns the index of the first occurence of the specified + * object in this sequence. + * + * @param elem element to search for. + * @return the index in this sequence of the first occurence of the + * specified element, or -1 if the sequence does not contain + * this element. + */ + override def indexOf[B >: A](elem: B): Int = self.indexOf(elem) + + /** Returns the index of the last occurence of the specified + * element in this sequence, or -1 if the sequence does not + * contain this element. + * + * @param elem element to search for. + * @return the index in this sequence of the last occurence of the + * specified element, or -1 if the sequence does not contain + * this element. + */ + override def lastIndexOf[B >: A](elem: B): Int = self.lastIndexOf(elem) + + /** Returns the sub-sequence starting from index <code>n</code>. + * + * @param n ... + * @return ... + */ + override def take(n: Int): Seq[A] = self.take(n) + + /** Returns a new sub-sequence that drops the first <code>n</code> + * elements of this sequence. + * + * @param n ... + * @return ... + */ + override def drop(n: Int): Seq[A] = self.drop(n) + + /** Returns a subsequence starting from index <code>from</code> + * consisting of <code>len</code> elements. + * + * @param from ... + * @param len ... + */ + override def subseq(from: Int, len: Int): Seq[A] = self.subseq(from, len) + + /** Fills the given array <code>xs</code> with the elements of + * this sequence starting at position <code>start</code>. + * + * @param xs the array to fill. + * @param start starting index. + * @return the given array <code>xs</code> filled with the elements + * of this sequence. + */ + override def copyToArray[B >: A](xs: Array[B], start: Int): Array[B] = + self.copyToArray(xs, start) + + /** Transform this sequence into a list of all elements. + * + * @return a list which enumerates all elements of this sequence. + */ + override def toList: List[A] = self.toList } diff --git a/src/library/scala/Stream.scala b/src/library/scala/Stream.scala index 9b50a21010..0f2662cf5b 100644 --- a/src/library/scala/Stream.scala +++ b/src/library/scala/Stream.scala @@ -9,9 +9,9 @@ // $Id$ -package scala; +package scala -import scala.runtime.compat.StringBuilder; +import scala.runtime.compat.StringBuilder /** * The object <code>Stream</code> provides helper functions @@ -23,36 +23,35 @@ import scala.runtime.compat.StringBuilder; object Stream { val empty: Stream[Nothing] = new Stream[Nothing] { - def isEmpty = true; - def head: Nothing = error("head of empty stream"); - def tail: Stream[Nothing] = error("tail of empty stream"); - def printElems(buf: StringBuilder, prefix: String): StringBuilder = buf; + def isEmpty = true + def head: Nothing = error("head of empty stream") + def tail: Stream[Nothing] = error("tail of empty stream") + def printElems(buf: StringBuilder, prefix: String): StringBuilder = buf } def cons[a](hd: a, tl: => Stream[a]) = new Stream[a] { - def isEmpty = false; - def head = hd; - private var tlVal: Stream[a] = _; - private var tlDefined = false; + def isEmpty = false + def head = hd + private var tlVal: Stream[a] = _ + private var tlDefined = false def tail: Stream[a] = { - if (!tlDefined) { tlVal = tl; tlDefined = true; } + if (!tlDefined) { tlVal = tl; tlDefined = true } tlVal } def printElems(buf: StringBuilder, prefix: String): StringBuilder = { - val buf1 = buf.append(prefix).append(hd); - if (tlDefined) tlVal.printElems(buf1, ", ") else buf1 append ", ?"; + val buf1 = buf.append(prefix).append(hd) + if (tlDefined) tlVal.printElems(buf1, ", ") else buf1 append ", ?" } } def fromIterator[a](it: Iterator[a]): Stream[a] = - if (it.hasNext) cons(it.next, fromIterator(it)) else empty; + if (it.hasNext) cons(it.next, fromIterator(it)) else empty - def concat[a](xs: Seq[Stream[a]]): Stream[a] = concat(xs.elements); + def concat[a](xs: Seq[Stream[a]]): Stream[a] = concat(xs.elements) - def concat[a](xs: Iterator[Stream[a]]): Stream[a] = { + def concat[a](xs: Iterator[Stream[a]]): Stream[a] = if (xs.hasNext) xs.next append concat(xs) - else empty; - } + else empty /** * Create a stream with element values @@ -65,7 +64,7 @@ object Stream { * @return the stream starting at value <code>start</code>. */ def range(start: Int, end: Int): Stream[Int] = - range(start, end, 1); + range(start, end, 1) /** * Create a stream with element values @@ -112,7 +111,7 @@ object Stream { * @return the stream starting at value <code>start</code>. */ def from(start: Int, step: Int): Stream[Int] = - cons(start, from(start+step, step)) + cons(start, from(start+step, step)) /** * Create an infinite stream starting at <code>start</code> diff --git a/src/library/scala/collection/BitSet.scala b/src/library/scala/collection/BitSet.scala index c45c60a060..b4658049db 100644 --- a/src/library/scala/collection/BitSet.scala +++ b/src/library/scala/collection/BitSet.scala @@ -9,7 +9,7 @@ // $Id$ -package scala.collection; +package scala.collection /** @@ -23,29 +23,29 @@ package scala.collection; abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] { - import scala.runtime.compat.Platform.arraycopy; - import scala.runtime.compat.Math.min; + import scala.runtime.compat.Platform.arraycopy + import scala.runtime.compat.Math.min /** number of bits in this bitset */ - def size: Int; + def size: Int /** @return true if bit i is set */ def contains(i: Int): Boolean = - (i < capacity) && ((arr(offset(i)) & mask(i)) != 0); + (i < capacity) && ((arr(offset(i)) & mask(i)) != 0) - def capacity: Int; + def capacity: Int - protected def arr: Array[Int]; + protected def arr: Array[Int] /** returns an iterator over the truth values of all bits */ final def elements: Iterator[Int] = new Iterator[Int] { - var i = 0; + var i = 0 def findNext: Unit = { while (!BitSet.this.contains(i) && (i < capacity)) - i = i + 1; + i = i + 1 } - findNext; - def hasNext: Boolean = i < capacity; + findNext + def hasNext: Boolean = i < capacity def next: Int = { val j = i; i = i + 1; findNext; j } } @@ -54,9 +54,9 @@ abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] { * @return a copy of the array underlying this bitset */ def toArray: Array[Int] = { - val length = memsize(capacity); - val newarr = new Array[Int](length); - arraycopy(newarr, 0, this.arr, 0, length); + val length = memsize(capacity) + val newarr = new Array[Int](length) + arraycopy(newarr, 0, this.arr, 0, length) newarr } @@ -70,12 +70,12 @@ abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] { that.isInstanceOf[BitSet] && { val other = that.asInstanceOf[BitSet]; (size == other.size) && ( size == 0 || { - var len = memsize(min(this.capacity, other.capacity)); - var i = 0; - var res = true; + var len = memsize(min(this.capacity, other.capacity)) + var i = 0 + var res = true while((i < len) && res) { - res = arr(i) == other.arr(i); - i = i + 1; + res = arr(i) == other.arr(i) + i = i + 1 } res }) @@ -91,10 +91,10 @@ abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] { */ override def subsetOf(that: Set[Int]): Boolean = (that.isInstanceOf[BitSet] && { - val other = that.asInstanceOf[BitSet]; - val len = memsize(min(this.capacity, other.capacity)); - var i = 0; - var res = true; + val other = that.asInstanceOf[BitSet] + val len = memsize(min(this.capacity, other.capacity)) + var i = 0 + var res = true while((i < len) && res) { res = other.arr(i) == (other.arr(i) | arr(i)); i = i + 1; @@ -102,7 +102,7 @@ abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] { res && (this.capacity <= other.capacity || { // if this set is bigger check that the rest is empty while (i < memsize(this.capacity) && res) { - res == arr(i) == 0; + res == arr(i) == 0 i = i + 1 } res @@ -111,15 +111,15 @@ abstract class BitSet extends AnyRef with Function1[Int,Boolean] with Set[Int] { /** @return the number of Int cells needed to store <code>n</code> bits */ - protected final def memsize(n: Int): Int = offset(n + 31); + protected final def memsize(n: Int): Int = offset(n + 31) /** @return the number of bits represented by <code>n</code> words */ - protected final def nbits(n: Int): Int = n << 5; + protected final def nbits(n: Int): Int = n << 5 /** @return the position in the array where the bit resides */ - protected final def offset(n: Int): Int = n >>> 5; + protected final def offset(n: Int): Int = n >>> 5 /** @return a mask with 1 at the position of the bit */ - protected final def mask(n: Int): Int = 1 << (n & 0x1F); + protected final def mask(n: Int): Int = 1 << (n & 0x1F) } diff --git a/src/library/scala/collection/Map.scala b/src/library/scala/collection/Map.scala index 9f88c9dc71..3cc2fa8c0f 100644 --- a/src/library/scala/collection/Map.scala +++ b/src/library/scala/collection/Map.scala @@ -9,7 +9,7 @@ // $Id$ -package scala.collection; +package scala.collection /** This class defines the interface of collections that unambiguously map * keys to values (i.e. a key is mapped to at least one value). @@ -33,7 +33,7 @@ trait Map[A, +B] extends AnyRef * * @return the number of mappings */ - def size: Int; + def size: Int /** Check if this map maps <code>key</code> to a value and return the * value if it exists. @@ -41,13 +41,13 @@ trait Map[A, +B] extends AnyRef * @param key the key of the mapping of interest * @return the value of the mapping, if it exists */ - def get(key: A): Option[B]; + def get(key: A): Option[B] /** Is this an empty map? * * @return true, iff the map is empty. */ - def isEmpty: Boolean = (size == 0); + def isEmpty: Boolean = (size == 0) /** Retrieve the value which is associated with the given key. This * method throws an exception if there is no mapping from the given @@ -57,8 +57,8 @@ trait Map[A, +B] extends AnyRef * @return the value associated with the given key. */ def apply(key: A): B = get(key) match { - case None => default(key) - case Some(value) => value + case None => default(key) + case Some(value) => value } /** Is the given key mapped to a value by this map? @@ -67,8 +67,8 @@ trait Map[A, +B] extends AnyRef * @return true, iff there is a mapping for key in this map */ def contains(key: A): Boolean = get(key) match { - case None => false - case Some(_) => true + case None => false + case Some(_) => true } /** Does this map contain a mapping from the given key to a value? @@ -76,16 +76,16 @@ trait Map[A, +B] extends AnyRef * @param key the key * @return true, iff there is a mapping for key in this map */ - def isDefinedAt(key: A) = contains(key); + def isDefinedAt(key: A) = contains(key) /** Creates an iterator for all keys. * * @return an iterator over all keys. */ def keys: Iterator[A] = new Iterator[A] { - val iter = Map.this.elements; - def hasNext = iter.hasNext; - def next = iter.next._1; + val iter = Map.this.elements + def hasNext = iter.hasNext + def next = iter.next._1 } /** Creates an iterator for a contained values. @@ -93,9 +93,9 @@ trait Map[A, +B] extends AnyRef * @return an iterator over all values. */ def values: Iterator[B] = new Iterator[B] { - val iter = Map.this.elements; - def hasNext = iter.hasNext; - def next = iter.next._2; + val iter = Map.this.elements + def hasNext = iter.hasNext + def next = iter.next._2 } /** Executes the given function for all (key, value) pairs @@ -104,11 +104,11 @@ trait Map[A, +B] extends AnyRef * @param f the function to execute. */ def foreach(f: (A, B) => Unit) = { - val iter = elements; - while (iter.hasNext) { - val Pair(key, value) = iter.next; - f(key, value); - } + val iter = elements + while (iter.hasNext) { + val Pair(key, value) = iter.next + f(key, value) + } } /** Applies the given predicate to all (key, value) mappings @@ -119,7 +119,7 @@ trait Map[A, +B] extends AnyRef * @return true, iff p yields true for all mappings. */ def forall(p: (A, B) => Boolean): Boolean = elements.forall { - case Pair(key, value) => p(key, value) + case Pair(key, value) => p(key, value) } /** Applies the given predicate to all (key, value) mappings @@ -131,7 +131,7 @@ trait Map[A, +B] extends AnyRef * p yields true. */ def exists(p: (A, B) => Boolean): Boolean = elements.exists { - case Pair(key, value) => p(key, value) + case Pair(key, value) => p(key, value) } /** Compares two maps structurally; i.e. checks if all mappings @@ -144,8 +144,8 @@ trait Map[A, +B] extends AnyRef case other: Map[A, B] => this.size == other.size && this.elements.forall { case Pair(key, value) => other.get(key) match { - case None => false; - case Some(otherval) => value == otherval; + case None => false + case Some(otherval) => value == otherval } } case _ => false @@ -155,28 +155,30 @@ trait Map[A, +B] extends AnyRef * * @return a list containing all mappings */ - def toList: List[Pair[A, B]] = elements.toList; + def toList: List[Pair[A, B]] = elements.toList /** Creates a string representation for this map. * * @return a string showing all mappings */ override def toString() = - if (size == 0) - "{}" - else - "{" + { - val iter = elements; - var res = iter.next.toString(); - while (iter.hasNext) { - res = res + ", " + iter.next; - } - res; - } + "}"; + if (size == 0) + "{}" + else + "{" + { + val iter = elements + var res = iter.next.toString() + while (iter.hasNext) { + res = res + ", " + iter.next + } + res + } + "}" /** The default value for the map, returned when a key is not found * The method implemented here yields an error, * but it might be overridden in subclasses. + * + * @param key ... */ def default(key: A): B = error("key not found: " + key) diff --git a/src/library/scala/collection/MapProxy.scala b/src/library/scala/collection/MapProxy.scala index 819627546d..59c39991f5 100644 --- a/src/library/scala/collection/MapProxy.scala +++ b/src/library/scala/collection/MapProxy.scala @@ -9,7 +9,7 @@ // $Id$ -package scala.collection; +package scala.collection /** This is a simple wrapper class for <code>scala.collection.Map</code>. @@ -21,25 +21,25 @@ package scala.collection; */ trait MapProxy[A, +B] extends Map[A, B] with IterableProxy[Pair[A, B]] { - def self: Map[A, B]; + def self: Map[A, B] - def size: Int = self.size; + def size: Int = self.size - def get(key: A): Option[B] = self.get(key); + def get(key: A): Option[B] = self.get(key) - override def isEmpty: Boolean = self.isEmpty; + override def isEmpty: Boolean = self.isEmpty - override def apply(key: A): B = self.apply(key); + override def apply(key: A): B = self.apply(key) - override def contains(key: A): Boolean = self.contains(key); + override def contains(key: A): Boolean = self.contains(key) - override def isDefinedAt(key: A) = self.isDefinedAt(key); + override def isDefinedAt(key: A) = self.isDefinedAt(key) - override def keys: Iterator[A] = self.keys; + override def keys: Iterator[A] = self.keys - override def values: Iterator[B] = self.values; + override def values: Iterator[B] = self.values - override def foreach(f: (A, B) => Unit) = self.foreach(f); + override def foreach(f: (A, B) => Unit) = self.foreach(f) - override def toList: List[Pair[A, B]] = self.toList; + override def toList: List[Pair[A, B]] = self.toList } diff --git a/src/library/scala/collection/Set.scala b/src/library/scala/collection/Set.scala index 3d391f2c79..4f5b4f136e 100644 --- a/src/library/scala/collection/Set.scala +++ b/src/library/scala/collection/Set.scala @@ -9,7 +9,7 @@ // $Id$ -package scala.collection; +package scala.collection /** This class defines the interface of collections that do not contain @@ -31,14 +31,14 @@ trait Set[A] extends AnyRef with Function1[A, Boolean] with Iterable[A] { * * @return number of set elements. */ - def size: Int; + def size: Int /** Checks if this set contains element <code>elem</code>. * * @param elem the element to check for membership. * @return true, iff <code>elem</code> is contained in this set. */ - def contains(elem: A): Boolean; + def contains(elem: A): Boolean /** This method allows sets to be interpreted as predicates. * It returns true, iff this set contains element <code>elem</code>. @@ -46,20 +46,20 @@ trait Set[A] extends AnyRef with Function1[A, Boolean] with Iterable[A] { * @param elem the element to check for membership. * @return true, iff <code>elem</code> is contained in this set. */ - def apply(elem: A): Boolean = contains(elem); + def apply(elem: A): Boolean = contains(elem) /** Checks if this set is empty. * * @return true, iff there is no element in the set. */ - def isEmpty: Boolean = (size == 0); + def isEmpty: Boolean = (size == 0) /** Checks if this set is a subset of set <code>that</code>. * * @param that another set. * @return true, iff the other set is a superset of this set. */ - def subsetOf(that: Set[A]): Boolean = forall(that.contains); + def subsetOf(that: Set[A]): Boolean = forall(that.contains) /** Compares this set with another object and returns true, iff the * other object is also a set which contains the same elements as @@ -80,12 +80,12 @@ trait Set[A] extends AnyRef with Function1[A, Boolean] with Iterable[A] { * * @return a list containing all set elements. */ - def toList: List[A] = elements.toList; + def toList: List[A] = elements.toList /** Returns a string representation of this set. * * @return a string showing all elements of this set. */ override def toString(): String = - if (isEmpty) "{}" else toList.mkString("{", ", ", "}"); + if (isEmpty) "{}" else toList.mkString("{", ", ", "}") } diff --git a/src/library/scala/collection/SetProxy.scala b/src/library/scala/collection/SetProxy.scala index 5b0517551a..8988fc4795 100644 --- a/src/library/scala/collection/SetProxy.scala +++ b/src/library/scala/collection/SetProxy.scala @@ -9,7 +9,7 @@ // $Id$ -package scala.collection; +package scala.collection /** This is a simple wrapper class for <code>scala.collection.Set</code>. @@ -21,19 +21,19 @@ package scala.collection; */ trait SetProxy[A] extends Set[A] with IterableProxy[A] { - def self: Set[A]; + def self: Set[A] - def size: Int = self.size; + def size: Int = self.size - override def isEmpty: Boolean = self.isEmpty; + override def isEmpty: Boolean = self.isEmpty - def contains(elem: A): Boolean = self.contains(elem); + def contains(elem: A): Boolean = self.contains(elem) - override def subsetOf(that: Set[A]): Boolean = self.subsetOf(that); + override def subsetOf(that: Set[A]): Boolean = self.subsetOf(that) - override def foreach(f: A => Unit): Unit = self.foreach(f); + override def foreach(f: A => Unit): Unit = self.foreach(f) - override def exists(p: A => Boolean): Boolean = self.exists(p); + override def exists(p: A => Boolean): Boolean = self.exists(p) - override def toList: List[A] = self.toList; + override def toList: List[A] = self.toList } diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala index 8cae4007df..452d5664d3 100644 --- a/src/library/scala/collection/immutable/BitSet.scala +++ b/src/library/scala/collection/immutable/BitSet.scala @@ -9,7 +9,7 @@ // $Id$ -package scala.collection.immutable; +package scala.collection.immutable /** The class <code>BitSet</code>provides an immutable bitset view on an @@ -29,15 +29,15 @@ package scala.collection.immutable; class BitSet(val size: Int, val capacity: Int, ba: Array[Int], copy: Boolean) extends collection.BitSet { - import scala.runtime.compat.Platform.arraycopy; + import scala.runtime.compat.Platform.arraycopy protected val arr: Array[Int] = if (copy) { - val arr = new Array[Int](ba.length); - arraycopy(ba, 0, arr, 0, ba.length); + val arr = new Array[Int](ba.length) + arraycopy(ba, 0, arr, 0, ba.length) arr } else - ba; + ba } diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala index 6efe90b4b2..a8c765c3ed 100644 --- a/src/library/scala/collection/immutable/ListMap.scala +++ b/src/library/scala/collection/immutable/ListMap.scala @@ -9,11 +9,11 @@ // $Id$ -package scala.collection.immutable; +package scala.collection.immutable object ListMap { - def Empty[A, B] = new ListMap[A, B]; + def Empty[A, B] = new ListMap[A, B] } /** This class implements immutable maps using a list-based data @@ -27,16 +27,86 @@ object ListMap { [serializable] class ListMap[A, B] extends AnyRef with Map[A, B] { - /** This method returns a new ListMap instance mapping keys of the - * same type to values of type <code>C</code>. - */ - def empty[C] = ListMap.Empty[A, C]; - + /** This method returns a new ListMap instance mapping keys of the + * same type to values of type <code>C</code>. + */ + def empty[C] = ListMap.Empty[A, C] + + /** Returns the number of mappings in this map. + * + * @return number of mappings. + */ + def size: Int = 0 + + /** Check if this map maps <code>key</code> to a value and return the + * value if it exists. + * + * @param key the key of the mapping of interest + * @return the value of the mapping, if it exists + */ + def get(key: A): Option[B] = None + + /** This method allows one to create a new map with an + * additional mapping from <code>key</code> + * to <code>value</code>. If the map contains already a + * mapping for <code>key</code>, it will be overridden by this + * function. + */ + def update(key: A, value: B): ListMap[A, B] = new Node(key, value) + + /** This creates a new mapping without the given <code>key</code>. + * If the map does not contain a mapping for the given key, the + * method returns the same map. + */ + def -(key: A): ListMap[A, B] = this + + /** This returns an iterator over key-value pairs. + */ + def elements: Iterator[Pair[A, B]] = toList.elements + + /** This return a list of key-value pairs. + */ + override def toList: List[Pair[A, B]] = Nil + + /** Compares two maps for equality. + * Two maps are equal iff they contain exactly the + * same key-value pairs. + */ + override def equals(obj: Any): Boolean = + if (obj.isInstanceOf[scala.collection.Map[A, B]]) { + val that = obj.asInstanceOf[scala.collection.Map[A, B]] + if (size != that.size) false else toList.forall { + case Pair(key, value) => that.get(key) match { + case None => false + case Some(v) => v == value + } + } + } else + false + + override def hashCode(): Int = 0 + + protected class Node(key: A, value: B) extends ListMap[A, B] { /** Returns the number of mappings in this map. * * @return number of mappings. */ - def size: Int = 0; + override def size: Int = ListMap.this.size + 1 + + /** Is this an empty map? + * + * @return true, iff the map is empty. + */ + override def isEmpty: Boolean = false + + /** Retrieve the value which is associated with the given key. This + * method throws an exception if there is no mapping from the given + * key to a value. + * + * @param key the key + * @return the value associated with the given key. + */ + override def apply(k: A): B = if (k == key) value else ListMap.this(k) /** Check if this map maps <code>key</code> to a value and return the * value if it exists. @@ -44,109 +114,43 @@ class ListMap[A, B] extends AnyRef with Map[A, B] { * @param key the key of the mapping of interest * @return the value of the mapping, if it exists */ - def get(key: A): Option[B] = None; + override def get(k: A): Option[B] = + if (k == key) Some(value) else ListMap.this.get(k) /** This method allows one to create a new map with an * additional mapping from <code>key</code> * to <code>value</code>. If the map contains already a * mapping for <code>key</code>, it will be overridden by this * function. + * + * @param k ... + * @param v ... */ - def update(key: A, value: B): ListMap[A, B] = new Node(key, value); + override def update(k: A, v: B): ListMap[A, B] = + if (k == key) { + new ListMap.this.Node(k, v) + } else { + val tail = ListMap.this.update(k,v); new tail.Node(key, value) + } /** This creates a new mapping without the given <code>key</code>. * If the map does not contain a mapping for the given key, the * method returns the same map. */ - def -(key: A): ListMap[A, B] = this; - - /** This returns an iterator over key-value pairs. - */ - def elements: Iterator[Pair[A, B]] = toList.elements; + override def -(k: A): ListMap[A, B] = + if (k == key) + ListMap.this + else { + val tail = ListMap.this - k; new tail.Node(key, value) + } /** This return a list of key-value pairs. */ - override def toList: List[Pair[A, B]] = Nil; + override def toList: List[Pair[A, B]] = + Pair(key, value) :: ListMap.this.toList - /** Compares two maps for equality. - * Two maps are equal iff they contain exactly the - * same key-value pairs. - */ - override def equals(obj: Any): Boolean = - if (obj.isInstanceOf[scala.collection.Map[A, B]]) { - val that = obj.asInstanceOf[scala.collection.Map[A, B]]; - if (size != that.size) false else toList.forall { - case Pair(key, value) => that.get(key) match { - case None => false; - case Some(v) => v == value; - } - }; - } else - false; - - override def hashCode(): Int = 0; - - protected class Node(key: A, value: B) extends ListMap[A, B] { - /** Returns the number of mappings in this map. - * - * @return number of mappings. - */ - override def size: Int = ListMap.this.size + 1; - - /** Is this an empty map? - * - * @return true, iff the map is empty. - */ - override def isEmpty: Boolean = false; - - /** Retrieve the value which is associated with the given key. This - * method throws an exception if there is no mapping from the given - * key to a value. - * - * @param key the key - * @return the value associated with the given key. - */ - override def apply(k: A): B = if (k == key) value else ListMap.this(k); - - /** Check if this map maps <code>key</code> to a value and return the - * value if it exists. - * - * @param key the key of the mapping of interest - * @return the value of the mapping, if it exists - */ - override def get(k: A): Option[B] = - if (k == key) Some(value) else ListMap.this.get(k); - - /** This method allows one to create a new map with an - * additional mapping from <code>key</code> - * to <code>value</code>. If the map contains already a - * mapping for <code>key</code>, it will be overridden by this - * function. - */ - override def update(k: A, v: B): ListMap[A, B] = - if (k == key) { - new ListMap.this.Node(k, v); - } else { - val tail = ListMap.this.update(k,v); new tail.Node(key, value) - } - - /** This creates a new mapping without the given <code>key</code>. - * If the map does not contain a mapping for the given key, the - * method returns the same map. - */ - override def -(k: A): ListMap[A, B] = - if (k == key) - ListMap.this - else { - val tail = ListMap.this - k; new tail.Node(key, value) - } - - /** This return a list of key-value pairs. - */ - override def toList: List[Pair[A, B]] = Pair(key, value) :: ListMap.this.toList; - - override def hashCode(): Int = - (key.hashCode() ^ value.hashCode()) + ListMap.this.hashCode(); - } + override def hashCode(): Int = + (key.hashCode() ^ value.hashCode()) + ListMap.this.hashCode() + } } diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala index 2f63aa610e..a65babd3cf 100644 --- a/src/library/scala/collection/immutable/ListSet.scala +++ b/src/library/scala/collection/immutable/ListSet.scala @@ -9,13 +9,13 @@ // $Id$ -package scala.collection.immutable; +package scala.collection.immutable object ListSet { - /** constructs an empty ListSet - */ - def Empty[A] = new ListSet[A]; + /** constructs an empty ListSet + */ + def Empty[A] = new ListSet[A] } @@ -30,92 +30,92 @@ object ListSet { [serializable] class ListSet[A] extends AnyRef with Set[A] { + /** Returns the number of elements in this set. + * + * @return number of set elements. + */ + def size: Int = 0 + + def empty = new ListSet[A] + + /** Checks if this set contains element <code>elem</code>. + * + * @param elem the element to check for membership. + * @return true, iff <code>elem</code> is contained in this set. + */ + def contains(elem: A): Boolean = false + + /** This method creates a new set with an additional element. + */ + def +(elem: A): ListSet[A] = new Node(elem) + + /** <code>-</code> can be used to remove a single element from + * a set. + */ + def -(elem: A): ListSet[A] = this + + /** Creates a new iterator over all elements contained in this + * object. + * + * @return the new iterator + */ + def elements: Iterator[A] = toList.elements + + /** Transform this set into a list of all elements. + * + * @return a list which enumerates all elements of this set. + */ + override def toList: List[A] = Nil + + /** Compares two sets for equality. + * Two set are equal iff they contain the same elements. + */ + override def equals(obj: Any): Boolean = + if (obj.isInstanceOf[scala.collection.Set[A]]) { + val that = obj.asInstanceOf[scala.collection.Set[A]] + if (size != that.size) false else toList.forall(that.contains) + } else + false + + override def hashCode(): Int = 0 + + protected class Node(elem: A) extends ListSet[A] { /** Returns the number of elements in this set. * * @return number of set elements. */ - def size: Int = 0; + override def size = ListSet.this.size + 1 - def empty = new ListSet[A]; + /** Checks if this set is empty. + * + * @return true, iff there is no element in the set. + */ + override def isEmpty: Boolean = false /** Checks if this set contains element <code>elem</code>. * * @param elem the element to check for membership. * @return true, iff <code>elem</code> is contained in this set. */ - def contains(elem: A): Boolean = false; + override def contains(e: A) = (e == elem) || ListSet.this.contains(e) /** This method creates a new set with an additional element. */ - def +(elem: A): ListSet[A] = new Node(elem); + override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e) /** <code>-</code> can be used to remove a single element from * a set. */ - def -(elem: A): ListSet[A] = this; - - /** Creates a new iterator over all elements contained in this - * object. - * - * @return the new iterator - */ - def elements: Iterator[A] = toList.elements; + override def -(e: A): ListSet[A] = if (e == elem) ListSet.this else { + val tail = ListSet.this - e; new tail.Node(elem) + } /** Transform this set into a list of all elements. * * @return a list which enumerates all elements of this set. */ - override def toList: List[A] = Nil; + override def toList: List[A] = elem :: ListSet.this.toList - /** Compares two sets for equality. - * Two set are equal iff they contain the same elements. - */ - override def equals(obj: Any): Boolean = - if (obj.isInstanceOf[scala.collection.Set[A]]) { - val that = obj.asInstanceOf[scala.collection.Set[A]]; - if (size != that.size) false else toList.forall(that.contains); - } else - false; - - override def hashCode(): Int = 0; - - protected class Node(elem: A) extends ListSet[A] { - /** Returns the number of elements in this set. - * - * @return number of set elements. - */ - override def size = ListSet.this.size + 1; - - /** Checks if this set is empty. - * - * @return true, iff there is no element in the set. - */ - override def isEmpty: Boolean = false; - - /** Checks if this set contains element <code>elem</code>. - * - * @param elem the element to check for membership. - * @return true, iff <code>elem</code> is contained in this set. - */ - override def contains(e: A) = (e == elem) || ListSet.this.contains(e); - - /** This method creates a new set with an additional element. - */ - override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e); - - /** <code>-</code> can be used to remove a single element from - * a set. - */ - override def -(e: A): ListSet[A] = if (e == elem) ListSet.this else { - val tail = ListSet.this - e; new tail.Node(elem) - } - - /** Transform this set into a list of all elements. - * - * @return a list which enumerates all elements of this set. - */ - override def toList: List[A] = elem :: ListSet.this.toList; - - override def hashCode(): Int = elem.hashCode() + ListSet.this.hashCode(); - } + override def hashCode(): Int = elem.hashCode() + ListSet.this.hashCode() + } } diff --git a/src/library/scala/collection/immutable/Map.scala b/src/library/scala/collection/immutable/Map.scala index c6730c6fff..a98e859b36 100644 --- a/src/library/scala/collection/immutable/Map.scala +++ b/src/library/scala/collection/immutable/Map.scala @@ -9,7 +9,7 @@ // $Id$ -package scala.collection.immutable; +package scala.collection.immutable /** This class extends the Map interface of collections that unambiguously map @@ -26,121 +26,130 @@ package scala.collection.immutable; */ trait Map[A, B] extends AnyRef with collection.Map[A, B] { - /** This method returns a new map instance of the same class - * mapping keys of the same type to values of type <code>C</code>. - */ - def empty[C]: Map[A, C]; - - /** This method allows one to create a new map with an - * additional mapping from <code>key</code> - * to <code>value</code>. If the map contains already a - * mapping for <code>key</code>, it will be overridden by this - * function. - */ - def update(key: A, value: B): Map[A, B]; - - /** This creates a new mapping without the given <code>key</code>. - * If the map does not contain a mapping for the given key, the - * method returns the same map. - */ - def -(key: A): Map[A, B]; - - /** This method defines syntactic sugar for adding a - * mapping. It is typically used in the following way: - * <pre> - * map + key -> value; - * </pre> - */ - def +(key: A): MapTo = new MapTo(key); - - /** <code>incl</code> can be used to add many mappings at the same time - * to the map. The method assumes that a mapping is represented - * by a <code>Pair</code> object who's first component denotes the - * key, and who's second component refers to the value. - */ - def incl(mappings: Pair[A, B]*): Map[A, B] = incl(mappings); - - /** <code>incl</code> can be used to add many mappings at the same time - * to the map. The method assumes that each mapping is represented - * by an Iterator over <code>Pair</code> objects who's first component - * denotes the key, and who's second component refers to the value. - */ - def incl(map: Iterable[Pair[A, B]]): Map[A, B] = { - val iter = map.elements; - var res = this; - while (iter.hasNext) { - val Pair(key, value) = iter.next; - res = res.update(key, value); - } - res + /** This method returns a new map instance of the same class + * mapping keys of the same type to values of type <code>C</code>. + */ + def empty[C]: Map[A, C] + + /** This method allows one to create a new map with an + * additional mapping from <code>key</code> + * to <code>value</code>. If the map contains already a + * mapping for <code>key</code>, it will be overridden by this + * function. + */ + def update(key: A, value: B): Map[A, B] + + /** This creates a new mapping without the given <code>key</code>. + * If the map does not contain a mapping for the given key, the + * method returns the same map. + */ + def -(key: A): Map[A, B] + + /** This method defines syntactic sugar for adding a + * mapping. It is typically used in the following way: + * <pre> + * map + key -> value; + * </pre> + */ + def +(key: A): MapTo = new MapTo(key) + + /** <code>incl</code> can be used to add many mappings at the same time + * to the map. The method assumes that a mapping is represented + * by a <code>Pair</code> object who's first component denotes the + * key, and who's second component refers to the value. + */ + def incl(mappings: Pair[A, B]*): Map[A, B] = incl(mappings) + + /** <code>incl</code> can be used to add many mappings at the same time + * to the map. The method assumes that each mapping is represented + * by an Iterator over <code>Pair</code> objects who's first component + * denotes the key, and who's second component refers to the value. + * + * @param map ... + */ + def incl(map: Iterable[Pair[A, B]]): Map[A, B] = { + val iter = map.elements + var res = this + while (iter.hasNext) { + val Pair(key, value) = iter.next + res = res.update(key, value); } - - /** This method will return a map where all the mappings - * for the given sequence of keys are removed from the map. - */ - def excl(keys: A*): Map[A, B] = excl(keys); - - /** This method removes all the mappings for keys provided by an - * iterator over the elements of the <code>keys</code> object. - */ - def excl(keys: Iterable[A]): Map[A, B] = { - val iter = keys.elements; - var res = this; - while (iter.hasNext) { - res = res - iter.next; - } - res; + res + } + + /** This method will return a map where all the mappings + * for the given sequence of keys are removed from the map. + * + * @param keys ... + */ + def excl(keys: A*): Map[A, B] = excl(keys) + + /** This method removes all the mappings for keys provided by an + * iterator over the elements of the <code>keys</code> object. + * + * @param keys ... + */ + def excl(keys: Iterable[A]): Map[A, B] = { + val iter = keys.elements + var res = this + while (iter.hasNext) { + res = res - iter.next } - - /** This function transforms all the values of mappings contained - * in this map with function <code>f</code>. - */ - def map[C](f: (A, B) => C): Map[A, C] = { - var res = empty[C]; - elements foreach { - case Pair(key, value) => res = res.update(key, f(key, value)); - } - res; + res + } + + /** This function transforms all the values of mappings contained + * in this map with function <code>f</code>. + * + * @param f ... + */ + def map[C](f: (A, B) => C): Map[A, C] = { + var res = empty[C] + elements foreach { + case Pair(key, value) => res = res.update(key, f(key, value)) } - - /** This method removes all the mappings for which the predicate - * <code>p</code> returns <code>false</code>. - */ - def filter(p: (A, B) => Boolean): Map[A, B] = { - var res = this; - toList foreach { - case Pair(key, value) => if (!p(key, value)) { res = res.excl(key); } - } - res; + res + } + + /** This method removes all the mappings for which the predicate + * <code>p</code> returns <code>false</code>. + * + * @param p ... + */ + def filter(p: (A, B) => Boolean): Map[A, B] = { + var res = this + toList foreach { + case Pair(key, value) => if (!p(key, value)) { res = res.excl(key) } } + res + } + + /** Returns a string representation of this map which shows + * all the mappings. + */ + override def toString() = + if (size == 0) + "{}" + else + "{" + { + val iter = elements + var res = mappingToString(iter.next) + while (iter.hasNext) { + res = res + ", " + mappingToString(iter.next); + } + res + } + "}" - /** Returns a string representation of this map which shows - * all the mappings. - */ - override def toString() = - if (size == 0) - "{}" - else - "{" + { - val iter = elements; - var res = mappingToString(iter.next); - while (iter.hasNext) { - res = res + ", " + mappingToString(iter.next); - } - res; - } + "}"; - - override def hashCode() = { - elements.foldLeft(0)((hash:Int,pair:AnyRef) => hash + pair.hashCode()); - } + override def hashCode() = + elements.foldLeft(0)((hash: Int, pair: AnyRef) => hash + pair.hashCode()) - /** This method controls how a mapping is represented in the string - * representation provided by method <code>toString</code>. - */ - def mappingToString(p: Pair[A, B]) = p._1.toString() + " -> " + p._2; + /** This method controls how a mapping is represented in the string + * representation provided by method <code>toString</code>. + */ + def mappingToString(p: Pair[A, B]) = p._1.toString() + " -> " + p._2 - class MapTo(key: A) { - def ->(value: B) = update(key, value); - } + class MapTo(key: A) { + def ->(value: B) = update(key, value) + } } diff --git a/src/library/scala/collection/immutable/Queue.scala b/src/library/scala/collection/immutable/Queue.scala index 238a192c87..49b34634e9 100644 --- a/src/library/scala/collection/immutable/Queue.scala +++ b/src/library/scala/collection/immutable/Queue.scala @@ -9,11 +9,11 @@ // $Id$ -package scala.collection.immutable; +package scala.collection.immutable object Queue { - val Empty: Queue[All] = new Queue(); + val Empty: Queue[All] = new Queue() } /** <code>Queue</code> objects implement data structures that allow to @@ -24,14 +24,14 @@ object Queue { */ [serializable] class Queue[+A](elem: A*) extends Seq[A] { - protected val in: List[A] = Nil; - protected val out: List[A] = elem.elements.toList; + protected val in: List[A] = Nil + protected val out: List[A] = elem.elements.toList protected def mkQueue[A](i: List[A], o: List[A]): Queue[A] = new Queue[A]() { - override protected val in = i; + override protected val in = i override protected val out = o - }; + } /** Returns the <code>n</code>-th element of this queue. * The first element is at position 0. @@ -42,28 +42,28 @@ class Queue[+A](elem: A*) extends Seq[A] { */ def apply(n: Int): A = if (n < out.length) out.apply(n) - else in.reverse.apply(n - out.length); + else in.reverse.apply(n - out.length) /** Returns the elements in the list as an iterator */ - def elements: Iterator[A] = (out ::: in.reverse).elements; + def elements: Iterator[A] = (out ::: in.reverse).elements /** Checks if the queue is empty. * * @return true, iff there is no element in the queue. */ - def isEmpty: Boolean = in.isEmpty && out.isEmpty; + def isEmpty: Boolean = in.isEmpty && out.isEmpty /** Returns the length of the queue. */ - def length = in.length + out.length; + def length = in.length + out.length /** Creates a new queue with element added at the end * of the old queue. * * @param elem the element to insert */ - def +[B >: A](elem: B) = mkQueue(elem :: in, out); + def +[B >: A](elem: B) = mkQueue(elem :: in, out) /** Returns a new queue with all all elements provided by * an <code>Iterable</code> object added at the end of @@ -74,16 +74,16 @@ class Queue[+A](elem: A*) extends Seq[A] { * @param iter an iterable object */ def +[B >: A](iter: Iterable[B]) = { - var q: List[B] = in; - iter.elements.foreach(e => q = e :: q); - mkQueue(q, out); + var q: List[B] = in + iter.elements.foreach(e => q = e :: q) + mkQueue(q, out) } /** Returns a new queue with all elements added. * * @param elems the elements to add. */ - def enqueue [B >: A](elems: B*) = this + elems; + def enqueue [B >: A](elems: B*) = this + elems /** Returns a tuple with the first element in the queue, * and a new queue with this element removed. @@ -94,8 +94,8 @@ class Queue[+A](elem: A*) extends Seq[A] { val Pair(newOut, newIn) = if (out.isEmpty) Pair(in.reverse, Nil) else Pair(out, in); - if (newOut.isEmpty) error("queue empty"); - else Pair(newOut.head, mkQueue(newIn, newOut.tail)); + if (newOut.isEmpty) error("queue empty") + else Pair(newOut.head, mkQueue(newIn, newOut.tail)) } /** Returns the first element in the queue, or throws an error if there @@ -105,13 +105,13 @@ class Queue[+A](elem: A*) extends Seq[A] { */ def front: A = if (out.isEmpty) { - if (in.isEmpty) error("queue empty") else in.last; + if (in.isEmpty) error("queue empty") else in.last } else - out.head; + out.head /** Returns a string representation of this queue. */ - override def toString() = mkString("Queue(", ",", ")"); + override def toString() = mkString("Queue(", ",", ")") /** Compares two queues for equality by comparing * each element in the queues. @@ -138,13 +138,13 @@ class Queue[+A](elem: A*) extends Seq[A] { compare each element, starting at index 0. */ (q.length == this.length) && eqe(0); - case _ => false; /* o is not a queue: not equal to this. */ + case _ => false /* o is not a queue: not equal to this. */ } override def hashCode(): Int = if (isEmpty) 0 else { val q: Pair[A,Queue[A]] = dequeue; - q._1.hashCode() + q._2.hashCode(); + q._1.hashCode() + q._2.hashCode() } } diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala index a90c20fb69..1880636594 100644 --- a/src/library/scala/collection/immutable/Set.scala +++ b/src/library/scala/collection/immutable/Set.scala @@ -9,7 +9,7 @@ // $Id$ -package scala.collection.immutable; +package scala.collection.immutable /** This class represents immutable sets. Concrete set implementations @@ -26,66 +26,71 @@ package scala.collection.immutable; */ trait Set[A] extends AnyRef with collection.Set[A] { - /** This method creates a new set with an additional element. - */ - def +(elem: A): Set[A]; - - /** @return an empty set of the same type as this set - */ - def empty: Set[A]; - - /** <code>incl</code> can be used to add many elements to the set - * at the same time. - */ - def incl(elems: A*): Set[A] = incl(elems); - - /** This method will add all the elements provided by an iterator - * of the iterable object <code>that</code> to the set. - */ - def incl(that: Iterable[A]): Set[A] = { - var res = this; - that.elements.foreach(elem => res = res + elem); - res; - } + /** This method creates a new set with an additional element. + */ + def +(elem: A): Set[A] + + /** @return an empty set of the same type as this set + */ + def empty: Set[A] + + /** <code>incl</code> can be used to add many elements to the set + * at the same time. + */ + def incl(elems: A*): Set[A] = incl(elems) + + /** This method will add all the elements provided by an iterator + * of the iterable object <code>that</code> to the set. + * + * @param that ... + */ + def incl(that: Iterable[A]): Set[A] = { + var res = this + that.elements.foreach(elem => res = res + elem) + res + } - /** <code>-</code> can be used to remove a single element from - * a set. - */ - def -(elem: A): Set[A]; - - /** <code>excl</code> removes many elements from the set. - */ - def excl(elems: A*): Set[A] = excl(elems); - - /** This method removes all the elements provided by an iterator - * of the iterable object <code>that</code> from the set. - */ - def excl(that: Iterable[A]): Set[A] = { - var res = this; - that.elements.foreach(elem => res = res - elem); - res; - } + /** <code>-</code> can be used to remove a single element from + * a set. + */ + def -(elem: A): Set[A] + + /** <code>excl</code> removes many elements from the set. + */ + def excl(elems: A*): Set[A] = excl(elems) + + /** This method removes all the elements provided by an iterator + * of the iterable object <code>that</code> from the set. + */ + def excl(that: Iterable[A]): Set[A] = { + var res = this + that.elements.foreach(elem => res = res - elem) + res + } - /** This method computes an intersection with set <code>that</code>. - * It removes all the elements that are not present in <code>that</code>. - */ - def intersect(that: scala.collection.Set[A]): Set[A] = filter(that.contains); - - /** Method <code>filter</code> removes all elements from the set for - * which the predicate <code>p</code> yields the value <code>false</code>. - */ - def filter(p: A => Boolean): Set[A] = { - var res = this; - toList foreach { - elem => if (!p(elem)) { res = res - elem; } - } - res; + /** This method computes an intersection with set <code>that</code>. + * It removes all the elements that are not present in <code>that</code>. + * + * @param that ... + */ + def intersect(that: scala.collection.Set[A]): Set[A] = filter(that.contains) + + /** Method <code>filter</code> removes all elements from the set for + * which the predicate <code>p</code> yields the value <code>false</code>. + * + * @param p ... + */ + def filter(p: A => Boolean): Set[A] = { + var res = this + toList foreach { + elem => if (!p(elem)) res = res - elem } + res + } /** hashcode for this set */ - override def hashCode() = { - elements.foldLeft(0)((hash: Int, e: A) => hash + e.hashCode()); - } + override def hashCode() = + elements.foldLeft(0)((hash: Int, e: A) => hash + e.hashCode()) } diff --git a/src/library/scala/collection/immutable/Stack.scala b/src/library/scala/collection/immutable/Stack.scala index 2b40101949..c2305e156a 100644 --- a/src/library/scala/collection/immutable/Stack.scala +++ b/src/library/scala/collection/immutable/Stack.scala @@ -9,11 +9,11 @@ // $Id$ -package scala.collection.immutable; +package scala.collection.immutable object Stack { - def Empty[A] = new Stack[A]; + def Empty[A] = new Stack[A] } /** This class implements immutable stacks using a list-based data @@ -31,20 +31,20 @@ class Stack[+A] extends Seq[A] { * * @return true, iff there is no element on the stack. */ - def isEmpty: Boolean = true; + def isEmpty: Boolean = true /** Returns the size of this stack. * * @return the stack size. */ - def length: Int = 0; + def length: Int = 0 /** Push an element on the stack. * * @param elem the element to push on the stack. * @return the stack with the new element on top. */ - def +[B >: A](elem: B): Stack[B] = new Node(elem); + def +[B >: A](elem: B): Stack[B] = new Node(elem) /** Push all elements provided by the given iterable object onto * the stack. The last element returned by the iterable object @@ -54,8 +54,8 @@ class Stack[+A] extends Seq[A] { * @return the stack with the new elements on top. */ def +[B >: A](elems: Iterable[B]): Stack[B] = { - var res: Stack[B] = this; - elems.elements.foreach { elem => res = res + elem; } + var res: Stack[B] = this + elems.elements.foreach { elem => res = res + elem } res } @@ -65,20 +65,20 @@ class Stack[+A] extends Seq[A] { * @param elems the element sequence. * @return the stack with the new elements on top. */ - def push[B >: A](elems: B*): Stack[B] = this + elems; + def push[B >: A](elems: B*): Stack[B] = this + elems /** Returns the top element of the stack. An error is signaled if * there is no element on the stack. * * @return the top element. */ - def top: A = error("no element on stack"); + def top: A = error("no element on stack") /** Removes the top element from the stack. * * @return the new stack without the former top element. */ - def pop: Stack[A] = error("no element on stack"); + def pop: Stack[A] = error("no element on stack") /** Returns the n-th element of this stack. The top element has index * 0, elements below are indexed with increasing numbers. @@ -86,7 +86,7 @@ class Stack[+A] extends Seq[A] { * @param n the index number. * @return the n-th element on the stack. */ - def apply(n: Int): A = error("no element on stack"); + def apply(n: Int): A = error("no element on stack") /** Returns an iterator over all elements on the stack. The iterator * issues elements in the reversed order they were inserted into the @@ -94,13 +94,13 @@ class Stack[+A] extends Seq[A] { * * @return an iterator over all stack elements. */ - def elements: Iterator[A] = toList.elements; + def elements: Iterator[A] = toList.elements /** Creates a list of all stack elements in LIFO order. * * @return the created list. */ - override def toList: List[A] = Nil; + override def toList: List[A] = Nil /** Compares this stack with the given object. * @@ -109,33 +109,33 @@ class Stack[+A] extends Seq[A] { */ override def equals(obj: Any): Boolean = if (obj.isInstanceOf[Stack[A]]) - toList.equals((obj.asInstanceOf[Stack[A]]).toList); + toList.equals((obj.asInstanceOf[Stack[A]]).toList) else - false; + false /** Returns the hash code for this stack. * * @return the hash code of the stack. */ - override def hashCode(): Int = 0; + override def hashCode(): Int = 0 /** * Redefines the prefix of the string representation. */ - override def stringPrefix: String = "Stack"; + override def stringPrefix: String = "Stack" // Here comes true magic: covariant lists with implicit tail references [serializable] protected class Node[+B >: A](elem: B) extends Stack[B] { - override def isEmpty: Boolean = false; - override def length: Int = Stack.this.length + 1; - override def +[C >: B](elem: C): Stack[C] = new Node(elem); - override def +[C >: B](elems: Iterable[C]): Stack[C] = super.+(elems); - override def top: B = elem; - override def pop: Stack[B] = Stack.this; - override def apply(n: Int): B = if (n > 0) Stack.this(n - 1) else elem; - override def toList: List[B] = elem :: Stack.this.toList; - override def hashCode(): Int = elem.hashCode() + Stack.this.hashCode(); + override def isEmpty: Boolean = false + override def length: Int = Stack.this.length + 1 + override def +[C >: B](elem: C): Stack[C] = new Node(elem) + override def +[C >: B](elems: Iterable[C]): Stack[C] = super.+(elems) + override def top: B = elem + override def pop: Stack[B] = Stack.this + override def apply(n: Int): B = if (n > 0) Stack.this(n - 1) else elem + override def toList: List[B] = elem :: Stack.this.toList + override def hashCode(): Int = elem.hashCode() + Stack.this.hashCode() } } diff --git a/src/library/scala/collection/immutable/Tree.scala b/src/library/scala/collection/immutable/Tree.scala index fdeea70f1f..5fd419806e 100644 --- a/src/library/scala/collection/immutable/Tree.scala +++ b/src/library/scala/collection/immutable/Tree.scala @@ -37,7 +37,7 @@ ** --------------------------------------------------------------------- */ -package scala.collection.immutable; +package scala.collection.immutable /** General Balanced Trees - highly efficient functional dictionaries. * @@ -82,17 +82,17 @@ abstract class Tree[A <% Ordered[A], B]() extends AnyRef { * type This = C[T]; * </pre> */ - protected type This <: Tree[A,B]; - protected def getThis: This; + protected type This <: Tree[A,B] + protected def getThis: This /** * The type of nodes that the tree is build from. */ - protected type aNode = GBTree[A,B]; + protected type aNode = GBTree[A,B] /** The nodes in the tree. */ - protected def tree: aNode = GBLeaf[A,B](); + protected def tree: aNode = GBLeaf[A,B]() /** This abstract method should be defined by a concrete implementation ** C[T] as something like: @@ -107,20 +107,20 @@ abstract class Tree[A <% Ordered[A], B]() extends AnyRef { ** <code>override type This = C[T];</code> ** */ - protected def New(sz: Int, t: aNode): This; + protected def New(sz: Int, t: aNode): This /** The size of the tree, returns 0 (zero) if the tree is empty. ** @Returns The number of nodes in the tree as an integer. **/ - def size: Int = 0; + def size: Int = 0 /** * A new tree with the entry added is returned, * assuming that key is <em>not</em> in the tree. */ protected def add(key: A, entry: B): This = { - val newSize = size+1; - New(newSize, tree.insert(key, entry, newSize * newSize).node); + val newSize = size + 1 + New(newSize, tree.insert(key, entry, newSize * newSize).node) } /** @@ -128,12 +128,11 @@ abstract class Tree[A <% Ordered[A], B]() extends AnyRef { * if key is <em>not</em> in the tree, otherwise * the key is updated with the new entry. */ - protected def updateOrAdd(key: A, entry: B): This = { + protected def updateOrAdd(key: A, entry: B): This = if (tree.isDefinedAt(key)) New(size,tree.update(key,entry)) else - add(key,entry); - } + add(key,entry) /** Removes the key from the tree. */ protected def deleteAny(key: A): This = @@ -143,8 +142,8 @@ abstract class Tree[A <% Ordered[A], B]() extends AnyRef { getThis; /** Removes the key from the tree, assumimg that key is present. */ - private def delete(key:A): This = - New(size - 1, tree.delete(key)); + private def delete(key: A): This = + New(size - 1, tree.delete(key)) /** Check if this map maps <code>key</code> to a value and return the * value if it exists. @@ -152,8 +151,8 @@ abstract class Tree[A <% Ordered[A], B]() extends AnyRef { * @param key the key of the mapping of interest * @return the value of the mapping, if it exists */ - protected def findValue(key:A): Option[B] = - tree.get(key); + protected def findValue(key: A): Option[B] = + tree.get(key) /** * Gives you an iterator over all elements in the tree. @@ -164,17 +163,16 @@ abstract class Tree[A <% Ordered[A], B]() extends AnyRef { */ protected def entries: Iterator[B] = new Iterator[B] { - var iter = tree.mk_iter(scala.Nil); - def hasNext = !iter.isEmpty; - def next = - iter match { - case (GBNode(_,v,_,t)::iter_tail) => { - iter= t.mk_iter(iter_tail); - v; - } - case scala.Nil => - error("next on empty iterator"); + var iter = tree.mk_iter(scala.Nil) + def hasNext = !iter.isEmpty + def next = iter match { + case (GBNode(_,v,_,t)::iter_tail) => { + iter= t.mk_iter(iter_tail) + v } + case scala.Nil => + error("next on empty iterator") + } } /** @@ -182,22 +180,22 @@ abstract class Tree[A <% Ordered[A], B]() extends AnyRef { * after many deletions, since deletion does not rebalance the tree. */ def balance: This = - New(size, tree.balance(size)); + New(size, tree.balance(size)) } protected abstract class InsertTree[A <% Ordered[A],B]() extends AnyRef { - def insertLeft(k: A, v: B, t: GBTree[A,B]): InsertTree[A,B]; - def insertRight(k: A, v: B, t: GBTree[A,B]): InsertTree[A,B]; - def node: GBTree[A,B]; + def insertLeft(k: A, v: B, t: GBTree[A,B]): InsertTree[A,B] + def insertRight(k: A, v: B, t: GBTree[A,B]): InsertTree[A,B] + def node: GBTree[A,B] } private case class ITree[A <% Ordered[A],B](t: GBTree[A,B]) extends InsertTree[A,B] { def insertLeft(key: A, value: B, bigger: GBTree[A,B]) = - ITree(GBNode(key, value, t, bigger)); + ITree(GBNode(key, value, t, bigger)) def insertRight(key: A, value: B, smaller: GBTree[A,B]) = - ITree(GBNode(key, value, smaller, t)); - def node = t; + ITree(GBNode(key, value, smaller, t)) + def node = t } private case class INode[A <% Ordered[A],B](t1: GBTree[A,B], @@ -209,14 +207,14 @@ private case class INode[A <% Ordered[A],B](t1: GBTree[A,B], def insertRight(key: A, value: B, smaller: GBTree[A,B]) = balance_p(GBNode(key, value, smaller, t1),smaller); protected def balance_p(t:GBTree[A,B],subtree:GBTree[A,B]):InsertTree[A,B] = { - val Pair(subHeight, subSize) = subtree.count; - val totalHeight = 2 * scala.runtime.compat.Math.max(height, subHeight); - val totalSize = size + subSize + 1; - val BalanceHeight = totalSize * totalSize; - if(totalHeight > BalanceHeight) ITree(t.balance(totalSize)); - else INode(t, totalHeight, totalSize); + val Pair(subHeight, subSize) = subtree.count + val totalHeight = 2 * scala.runtime.compat.Math.max(height, subHeight) + val totalSize = size + subSize + 1 + val BalanceHeight = totalSize * totalSize + if (totalHeight > BalanceHeight) ITree(t.balance(totalSize)) + else INode(t, totalHeight, totalSize) } - def node = t1; + def node = t1 } /** @@ -224,46 +222,46 @@ private case class INode[A <% Ordered[A],B](t1: GBTree[A,B], */ [serializable] protected abstract class GBTree[A <% Ordered[A],B] extends AnyRef { - type aNode = GBTree[A,B]; - type anInsertTree = InsertTree[A,B]; + type aNode = GBTree[A,B] + type anInsertTree = InsertTree[A,B] /** Calculates 2^h, and size, where h is the height of the tree * and size is the number of nodes in the tree. */ - def count:Pair[Int,Int]; - def isDefinedAt(Key:A):Boolean; - def get(key:A):Option[B]; - def apply(key:A):B; - def update(key:A, value:B):aNode; - def insert(key:A, value:B, size:int):anInsertTree; - def toList(acc: List[Pair[A,B]]): List[Pair[A,B]]; - def mk_iter(iter_tail:List[aNode]): List[aNode]; - def delete(key:A):aNode; - def merge(t:aNode):aNode; - def takeSmallest:Triple[A,B,aNode]; - def balance(s:int):GBTree[A,B]; + def count: Pair[Int,Int] + def isDefinedAt(Key: A): Boolean + def get(key: A): Option[B] + def apply(key: A): B + def update(key: A, value: B): aNode + def insert(key: A, value: B, size: int): anInsertTree + def toList(acc: List[Pair[A,B]]): List[Pair[A,B]] + def mk_iter(iter_tail: List[aNode]): List[aNode] + def delete(key: A): aNode + def merge(t: aNode): aNode + def takeSmallest: Triple[A,B,aNode] + def balance(s: int): GBTree[A,B] } private case class GBLeaf[A <% Ordered[A],B]() extends GBTree[A,B] { - def count = Pair(1, 0); - def isDefinedAt(key:A) = false; - def get(_key:A) = None; - def apply(key:A) = error("key " + key + " not found"); - def update(key:A, value:B) = error("key " + key + " not found"); - def insert(key:A, value:B, s:int):anInsertTree = { + def count = Pair(1, 0) + def isDefinedAt(key:A) = false + def get(_key: A) = None + def apply(key: A) = error("key " + key + " not found") + def update(key: A, value: B) = error("key " + key + " not found") + def insert(key: A, value: B, s:int): anInsertTree = { if (s == 0) INode(GBNode(key, value, this, this), 1, 1) else ITree(GBNode(key, value, this, this)) } - def toList(acc: List[Pair[A,B]]): List[Pair[A,B]] = acc; - def mk_iter(iter_tail:List[GBTree[A,B]]) = iter_tail; - def merge(larger:GBTree[A,B]) = larger; - def takeSmallest:Triple[A,B,GBTree[A,B]] = - error("Take Smallest on empty tree"); - def delete(_key:A) = error("Delete on empty tree."); - def balance(s:int) = this; - override def hashCode() = 0; + def toList(acc: List[Pair[A,B]]): List[Pair[A,B]] = acc + def mk_iter(iter_tail: List[GBTree[A,B]]) = iter_tail + def merge(larger: GBTree[A,B]) = larger + def takeSmallest: Triple[A,B, GBTree[A,B]] = + error("Take Smallest on empty tree") + def delete(_key: A) = error("Delete on empty tree.") + def balance(s: int) = this + override def hashCode() = 0 } private case class GBNode[A <% Ordered[A],B](key: A, @@ -272,59 +270,58 @@ private case class GBNode[A <% Ordered[A],B](key: A, bigger: GBTree[A,B]) extends GBTree[A,B] { def count: Pair[Int,Int] = { - val Pair(sHeight, sSize) = smaller.count; - val Pair(bHeight, bSize) = bigger.count; - val mySize = sSize + bSize + 1; + val Pair(sHeight, sSize) = smaller.count + val Pair(bHeight, bSize) = bigger.count + val mySize = sSize + bSize + 1 if (mySize == 1) Pair(1, mySize) else - Pair(2 * scala.runtime.compat.Math.max(sHeight, bHeight), mySize); + Pair(2 * scala.runtime.compat.Math.max(sHeight, bHeight), mySize) } - def isDefinedAt(sKey:A):Boolean = { + def isDefinedAt(sKey: A): Boolean = if (sKey < key) smaller.isDefinedAt(sKey) else if (sKey > key) bigger.isDefinedAt(sKey) - else true; - } + else true - def get(sKey:A):Option[B] = - if (sKey < key) smaller.get(sKey); - else if (sKey > key) bigger.get(sKey); - else Some(value); + def get(sKey: A): Option[B] = + if (sKey < key) smaller.get(sKey) + else if (sKey > key) bigger.get(sKey) + else Some(value) - def apply(sKey:A):B = - if (sKey < key) smaller.apply(sKey); - else if (sKey > key) bigger.apply(sKey); - else value; + def apply(sKey: A): B = + if (sKey < key) smaller.apply(sKey) + else if (sKey > key) bigger.apply(sKey) + else value - def update(newKey:A, newValue:B):aNode = + def update(newKey: A, newValue: B): aNode = if (newKey < key) - GBNode(key, value, smaller.update(newKey,newValue), bigger); + GBNode(key, value, smaller.update(newKey,newValue), bigger) else if (newKey > key) - GBNode(key, value, smaller, bigger.update(newKey,newValue)); + GBNode(key, value, smaller, bigger.update(newKey,newValue)) else - GBNode(newKey, newValue, smaller, bigger); + GBNode(newKey, newValue, smaller, bigger) - def insert(newKey:A, newValue:B, s:int): anInsertTree = { + def insert(newKey: A, newValue: B, s: int): anInsertTree = { if (newKey < key) - smaller.insert(newKey, newValue, s / 2).insertLeft(key, value, bigger); + smaller.insert(newKey, newValue, s / 2).insertLeft(key, value, bigger) else if (newKey > key) - bigger.insert(newKey, newValue, s / 2).insertRight(key, value, smaller); + bigger.insert(newKey, newValue, s / 2).insertRight(key, value, smaller) else - error("Key exists: " + newKey); + error("Key exists: " + newKey) } def toList(acc: List[Pair[A,B]]): List[Pair[A,B]] = - smaller.toList(Pair(key, value) :: bigger.toList(acc)); + smaller.toList(Pair(key, value) :: bigger.toList(acc)) def mk_iter(iter_tail:List[aNode]):List[aNode] = - smaller.mk_iter(this :: iter_tail); + smaller.mk_iter(this :: iter_tail) def delete(sKey:A):aNode = { if (sKey < key) - GBNode(key, value, smaller.delete(sKey), bigger); + GBNode(key, value, smaller.delete(sKey), bigger) else if (sKey > key) - GBNode(key, value, smaller, bigger.delete(sKey)); + GBNode(key, value, smaller, bigger.delete(sKey)) else smaller.merge(bigger) } @@ -333,7 +330,7 @@ private case class GBNode[A <% Ordered[A],B](key: A, case GBLeaf() => this case _ => - val Triple(key1, value1, larger1) = larger.takeSmallest; + val Triple(key1, value1, larger1) = larger.takeSmallest GBNode(key1, value1, this, larger1) } @@ -341,27 +338,27 @@ private case class GBNode[A <% Ordered[A],B](key: A, case GBLeaf() => Triple(key, value, bigger) case _ => - val Triple(key1, value1, smaller1) = smaller.takeSmallest; + val Triple(key1, value1, smaller1) = smaller.takeSmallest Triple(key1, value1, GBNode(key, value, smaller1, bigger)) } def balance(s:int): GBTree[A,B] = - balance_list(toList(scala.Nil), s); + balance_list(toList(scala.Nil), s) protected def balance_list(list: List[Pair[A,B]], s:int): GBTree[A,B] = { val empty = GBLeaf[A,B](); def bal(list: List[Pair[A,B]], s:int): Pair[aNode,List[Pair[A,B]]] = { if (s > 1) { - val sm = s - 1; - val s2 = sm / 2; - val s1 = sm - s2; - val Pair(t1, Pair(k, v) :: l1) = bal(list, s1); - val Pair(t2, l2) = bal(l1, s2); - val t = GBNode(k, v, t1, t2); + val sm = s - 1 + val s2 = sm / 2 + val s1 = sm - s2 + val Pair(t1, Pair(k, v) :: l1) = bal(list, s1) + val Pair(t2, l2) = bal(l1, s2) + val t = GBNode(k, v, t1, t2) Pair(t, l2) } else if (s == 1) { - val Pair(k,v) :: rest = list; + val Pair(k,v) :: rest = list Pair(GBNode(k, v, empty, empty), rest) } else Pair(empty, list) @@ -370,5 +367,5 @@ private case class GBNode[A <% Ordered[A],B](key: A, } override def hashCode() = - value.hashCode() + smaller.hashCode() + bigger.hashCode(); + value.hashCode() + smaller.hashCode() + bigger.hashCode() } diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala index 54af053aa1..599453baf6 100644 --- a/src/library/scala/collection/immutable/TreeMap.scala +++ b/src/library/scala/collection/immutable/TreeMap.scala @@ -9,11 +9,11 @@ // $Id$ -package scala.collection.immutable; +package scala.collection.immutable object TreeMap { - def Empty[A <% Ordered[A], B] = new TreeMap[A, B]; + def Empty[A <% Ordered[A], B] = new TreeMap[A, B] } /** This class implements immutable maps using a tree. @@ -26,86 +26,94 @@ object TreeMap { [serializable] class TreeMap[A <% Ordered[A], B] extends Tree[A, Pair[A, B]] with Map[A, B] { - override protected type This = TreeMap[A, B]; - override protected def getThis: This = this; - - /** A factory to create empty maps of the same type of keys. - */ - def empty[C] = new TreeMap[A, C]; - - /** Creates a new TreeMap from a GBTree and its size. - */ - protected def New(sz:Int,t:aNode):This = new TreeMap[A,B] { - override def size=sz; - override protected def tree:aNode=t; + override protected type This = TreeMap[A, B] + override protected def getThis: This = this + + /** A factory to create empty maps of the same type of keys. + */ + def empty[C] = new TreeMap[A, C] + + /** Creates a new TreeMap from a GBTree and its size. + * + * @param sz ... + * @param t ... + * @return ... + */ + protected def New(sz: Int, t: aNode): This = new TreeMap[A, B] { + override def size = sz + override protected def tree: aNode = t + } + + /** A new TreeMap with the entry added is returned, + * if key is <em>not</em> in the TreeMap, otherwise + * the key is updated with the new entry. + * + * @param key ... + * @param value ... + * @return ... + */ + def update(key: A, value: B) = updateOrAdd(key, Pair(key, value)) + + /** A new TreeMap with the entry added is returned, + * assuming that key is <em>not</em> in the TreeMap. + */ + def insert(key:A,value:B) = add(key, Pair(key, value)) + + /** Removes the key from the TreeMap. + */ + def -(key:A) = deleteAny(key) + + /** Check if this map maps <code>key</code> to a value and return the + * value if it exists. + * + * @param key the key of the mapping of interest + * @return the value of the mapping, if it exists + */ + override def get(key: A): Option[B] = + findValue(key) match { + case Some(Pair(_, value: B)) => Some(value) + case _ => None } - /** A new TreeMap with the entry added is returned, - * if key is <em>not</em> in the TreeMap, otherwise - * the key is updated with the new entry. - */ - def update(key:A, value:B) = updateOrAdd(key, Pair(key, value)); - - /** A new TreeMap with the entry added is returned, - * assuming that key is <em>not</em> in the TreeMap. - */ - def insert(key:A,value:B) = add(key, Pair(key, value)); - - /** Removes the key from the TreeMap. - */ - def -(key:A) = deleteAny(key); - - /** Check if this map maps <code>key</code> to a value and return the - * value if it exists. - * - * @param key the key of the mapping of interest - * @return the value of the mapping, if it exists - */ - override def get(key: A): Option[B] = - findValue(key) match { - case Some(Pair(_, value: B)) => Some(value) - case _ => None - } - - /** Retrieve the value which is associated with the given key. This - * method throws an exception if there is no mapping from the given - * key to a value. - * - * @param key the key - * @return the value associated with the given key. - * @throws Error("key not found"). - */ - override def apply(key:A):B = tree.apply(key)._2; - - /** Creates a list of all (key, value) mappings. - * - * @return the list of all mappings - */ - override def toList: List[Pair[A,B]] = - tree.toList(scala.Nil) map (._2); - - /** Creates a new iterator over all elements contained in this - * object. - * - * @return the new iterator - */ - def elements: Iterator[Pair[A,B]] = entries; - - /** Compares two maps structurally; i.e. checks if all mappings - * contained in this map are also contained in the other map, - * and vice versa. - * - * @return true, iff both maps contain exactly the same mappings. - */ - override def equals(obj: Any): Boolean = - obj.isInstanceOf[scala.collection.Map[A, B]] && { - val that = obj.asInstanceOf[scala.collection.Map[A, B]]; - size == that.size && elements.forall { - case Pair(key, value) => that.get(key) match { - case None => false; - case Some(v) => v == value; - } + /** Retrieve the value which is associated with the given key. This + * method throws an exception if there is no mapping from the given + * key to a value. + * + * @param key the key + * @return the value associated with the given key. + * @throws Error("key not found"). + */ + override def apply(key: A): B = tree.apply(key)._2 + + /** Creates a list of all (key, value) mappings. + * + * @return the list of all mappings + */ + override def toList: List[Pair[A, B]] = + tree.toList(scala.Nil) map (._2) + + /** Creates a new iterator over all elements contained in this + * object. + * + * @return the new iterator + */ + def elements: Iterator[Pair[A, B]] = entries + + /** Compares two maps structurally; i.e. checks if all mappings + * contained in this map are also contained in the other map, + * and vice versa. + * + * @return true, iff both maps contain exactly the same mappings. + */ + override def equals(obj: Any): Boolean = + obj.isInstanceOf[scala.collection.Map[A, B]] && { + val that = obj.asInstanceOf[scala.collection.Map[A, B]] + size == that.size && elements.forall { + case Pair(key, value) => that.get(key) match { + case None => false + case Some(v) => v == value } - }; + } + } } diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala index 24a11c8b81..01258ee0f3 100644 --- a/src/library/scala/collection/immutable/TreeSet.scala +++ b/src/library/scala/collection/immutable/TreeSet.scala @@ -9,7 +9,7 @@ // $Id$ -package scala.collection.immutable; +package scala.collection.immutable /** This class implements immutable sets using a tree. @@ -22,52 +22,55 @@ package scala.collection.immutable; [serializable] class TreeSet[A <% Ordered[A]]() extends Tree[A, A] with Set[A] { - override protected type This = TreeSet[A]; - override protected def getThis: This = this; + override protected type This = TreeSet[A] + override protected def getThis: This = this - protected def New(sz: Int, t: aNode): This = new TreeSet[A] { - override def size = sz; - override protected def tree: aNode = t; - } + protected def New(sz: Int, t: aNode): This = new TreeSet[A] { + override def size = sz + override protected def tree: aNode = t + } - /** Checks if this set contains element <code>elem</code>. - * - * @param elem the element to check for membership. - * @return true, iff <code>elem</code> is contained in this set. - */ - def contains(elem: A): Boolean = !findValue(elem).isEmpty; + /** Checks if this set contains element <code>elem</code>. + * + * @param elem the element to check for membership. + * @return true, iff <code>elem</code> is contained in this set. + */ + def contains(elem: A): Boolean = !findValue(elem).isEmpty - /** This method creates a new set with an additional element. - */ - def +(elem: A): TreeSet[A] = updateOrAdd(elem, elem); + /** This method creates a new set with an additional element. + * + * @param elem ... + * @return ... + */ + def +(elem: A): TreeSet[A] = updateOrAdd(elem, elem) - override def empty: Set[A] = New(0, GBLeaf[A,A]()); + override def empty: Set[A] = New(0, GBLeaf[A,A]()) - /** <code>-</code> can be used to remove a single element from - * a set. - */ - def -(elem: A): TreeSet[A] = deleteAny(elem); + /** <code>-</code> can be used to remove a single element from + * a set. + */ + def -(elem: A): TreeSet[A] = deleteAny(elem) - /** Creates a new iterator over all elements contained in this - * object. - * - * @return the new iterator - */ - def elements: Iterator[A] = entries; + /** Creates a new iterator over all elements contained in this + * object. + * + * @return the new iterator + */ + def elements: Iterator[A] = entries - /** Transform this set into a list of all elements. - * - * @return a list which enumerates all elements of this set. - */ - override def toList: List[A] = - tree.toList(scala.Nil) map (._2); + /** Transform this set into a list of all elements. + * + * @return a list which enumerates all elements of this set. + */ + override def toList: List[A] = + tree.toList(scala.Nil) map (._2) - /** Compares two sets for equality. - * Two set are equal iff they contain the same elements. - */ - override def equals(obj: Any): Boolean = - obj.isInstanceOf[scala.collection.Set[A]] && { - val that = obj.asInstanceOf[scala.collection.Set[A]]; - (size == that.size) && toList.forall(that.contains); - } + /** Compares two sets for equality. + * Two set are equal iff they contain the same elements. + */ + override def equals(obj: Any): Boolean = + obj.isInstanceOf[scala.collection.Set[A]] && { + val that = obj.asInstanceOf[scala.collection.Set[A]] + (size == that.size) && toList.forall(that.contains) + } } diff --git a/src/library/scala/util/automata/BaseBerrySethi.scala b/src/library/scala/util/automata/BaseBerrySethi.scala index c7adf744c7..fddf31021d 100644 --- a/src/library/scala/util/automata/BaseBerrySethi.scala +++ b/src/library/scala/util/automata/BaseBerrySethi.scala @@ -9,14 +9,14 @@ // $Id$ -package scala.util.automata; +package scala.util.automata -import scala.util.regexp.Base; +import scala.util.regexp.Base -import scala.collection.mutable; -import scala.collection.immutable; -import scala.runtime.compat.Platform; +import scala.collection.mutable +import scala.collection.immutable +import scala.runtime.compat.Platform /** this turns a regexp over A into a NondetWorkAutom over A using the * celebrated position automata construction (also called Berry-Sethi or @@ -24,116 +24,125 @@ import scala.runtime.compat.Platform; */ abstract class BaseBerrySethi { - val lang: Base; - import lang.{Alt,Eps,Meta,RegExp,Sequ,Star} ; + val lang: Base + import lang.{Alt,Eps,Meta,RegExp,Sequ,Star} - protected var pos = 0;; + protected var pos = 0 - protected var globalFirst: immutable.Set[Int] = _; + protected var globalFirst: immutable.Set[Int] = _ // results which hold all info for the NondetWordAutomaton - protected var follow: mutable.HashMap[Int, immutable.Set[Int]] = _; + protected var follow: mutable.HashMap[Int, immutable.Set[Int]] = _ - protected var finalTag: Int = _; + protected var finalTag: Int = _ - protected var finals: immutable.TreeMap[int,int] = _; // final states + protected var finals: immutable.TreeMap[int,int] = _ // final states // constants -------------------------- - final val emptySet:immutable.Set[Int] = new immutable.TreeSet[Int](); + final val emptySet:immutable.Set[Int] = new immutable.TreeSet[Int]() /** computes first( r ) for the word regexp r */ protected def compFirst(r: RegExp): immutable.Set[Int] = r match { - case x:Alt => - var tmp = emptySet; - val it = x.rs.elements; // union - while( it.hasNext ) { tmp = tmp incl compFirst( it.next ); }; + case x:Alt => + var tmp = emptySet + val it = x.rs.elements // union + while (it.hasNext) { tmp = tmp incl compFirst(it.next) } tmp - case Eps => emptySet; + case Eps => emptySet //case x:Letter => emptySet + posMap(x); // singleton set - case x:Meta => compFirst( x.r ) + case x:Meta => compFirst(x.r) case x:Sequ => var tmp = emptySet; val it = x.rs.elements; // union - while( it.hasNext ) { + while (it.hasNext) { val z = it.next - tmp = tmp incl compFirst( z ) - if( !z.isNullable ) + tmp = tmp incl compFirst(z) + if (!z.isNullable) return tmp } tmp - case Star(t) => compFirst(t); - case _ => error("unexpected pattern " + Platform.getClass(r)); + case Star(t) => compFirst(t) + case _ => + error("unexpected pattern " + Platform.getClass(r)) } /** computes last( r ) for the regexp r */ protected def compLast(r: RegExp): immutable.Set[Int] = r match { - case x:Alt => - var tmp = emptySet; - val it = x.rs.elements; // union - while( it.hasNext ) { tmp = tmp incl compFirst( it.next ); }; + case x:Alt => + var tmp = emptySet + val it = x.rs.elements // union + while (it.hasNext) { tmp = tmp incl compFirst(it.next) } tmp - case Eps => emptySet; + case Eps => emptySet //case x:Letter => emptySet + posMap(x) // singleton set - case x:Meta => compLast( x.r ) - case x:Sequ => - var tmp = emptySet; - val it = x.rs.elements.toList.reverse.elements; // union - while( it.hasNext ) { - val z = it.next; - tmp = tmp incl compLast( z ); - if( !z.isNullable ) + case x:Meta => compLast(x.r) + case x:Sequ => + var tmp = emptySet + val it = x.rs.elements.toList.reverse.elements // union + while (it.hasNext) { + val z = it.next + tmp = tmp incl compLast(z) + if (!z.isNullable) return tmp - }; - tmp - case Star(t) => compLast(t); - case _ => error("unexpected pattern " + Platform.getClass(r)); + } + tmp + case Star(t) => compLast(t) + case _ => + error("unexpected pattern " + Platform.getClass(r)) } - // starts from the right-to-left - // precondition: pos is final - // pats are successor patterns of a Sequence node + /** Starts from the right-to-left + * precondition: pos is final + * pats are successor patterns of a Sequence node + * + * @param r ... + * @return ... + */ protected def compFollow(r: Seq[RegExp]): immutable.Set[Int] = { - //Console.println("compFollow( "+r.toList); - var first = emptySet; - var fol = emptySet; - if( r.length > 0 ) {//non-empty expr - - val it = r.elements.toList.reverse.elements; - - fol = fol + pos; // don't modify pos ! - while( it.hasNext ) { - val p = it.next; - //Console.println(" p now = "+p); - first = compFollow1( fol, p ); - //Console.println(" first = "+first); - //Console.println(" fol before = "+fol); - fol = if( p.isNullable ) - fol incl first - else - first; - //Console.println(" fol after = "+fol); + //Console.println("compFollow( "+r.toList) + var first = emptySet + var fol = emptySet + if (r.length > 0) {//non-empty expr + + val it = r.elements.toList.reverse.elements + + fol = fol + pos // don't modify pos ! + while (it.hasNext) { + val p = it.next + //Console.println(" p now = "+p) + first = compFollow1(fol, p) + //Console.println(" first = "+first) + //Console.println(" fol before = "+fol) + fol = + if (p.isNullable) fol incl first + else first + //Console.println(" fol after = "+fol) } } - this.follow.update( 0, fol /*first*/ ); - //Console.println("follow(0) = "+fol); - return fol; + this.follow.update(0, fol /*first*/) + //Console.println("follow(0) = "+fol) + fol } /** returns the first set of an expression, setting the follow set along - * the way + * the way. + * + * @param fol1 ... + * @param r ... + * @return ... */ - protected def compFollow1( fol1:immutable.Set[Int], r:RegExp): immutable.Set[Int] = { - var fol = fol1; - //System.out.println("compFollow1("+fol+","+r+")"); + protected def compFollow1(fol1: immutable.Set[Int], r: RegExp): immutable.Set[Int] = { + var fol = fol1 + //System.out.println("compFollow1("+fol+","+r+")") r match { case x:Alt => - var first = emptySet; - val it = x.rs.elements.toList.reverse.elements; - while( it.hasNext ) - first = first incl compFollow1( fol, it.next ); - first; + var first = emptySet + val it = x.rs.elements.toList.reverse.elements + while (it.hasNext) + first = first incl compFollow1(fol, it.next); + first /* case x:Letter => @@ -142,52 +151,49 @@ abstract class BaseBerrySethi { emptySet + i; */ case x:Meta => - compFollow1( fol1, x.r ); + compFollow1(fol1, x.r) case x:Star => - fol = fol incl compFirst( x.r ); - compFollow1( fol, x.r ); + fol = fol incl compFirst(x.r) + compFollow1(fol, x.r) case x:Sequ => - var first = emptySet; - val it = x.rs.elements.toList.reverse.elements; - while( it.hasNext ) { - val p = it.next; - first = compFollow1( fol, p ); - fol = if( p.isNullable ) - fol incl first ; - else - first; + var first = emptySet + val it = x.rs.elements.toList.reverse.elements + while (it.hasNext) { + val p = it.next + first = compFollow1(fol, p) + fol = + if (p.isNullable) fol incl first + else first } - first; + first - case _ => error("unexpected pattern: " + Platform.getClass(r)); + case _ => + error("unexpected pattern: " + Platform.getClass(r)) } } /** returns "Sethi-length" of a pattern, creating the set of position - * along the way + * along the way. + * + * @param r ... */ - // todo: replace global variable pos with acc - protected def traverse(r: RegExp): Unit = { - r match { // (is tree automaton stuff, more than Berry-Sethi) - - case x:Alt => - val it = x.rs.elements; - while( it.hasNext ) traverse( it.next ); - - case x:Sequ => - val it = x.rs.elements; - while( it.hasNext ) traverse( it.next ); - - case x:Meta => traverse( x.r ) - - case Star(t) => - traverse(t) - - case _ => error("unexp pattern " + Platform.getClass(r)); - } + protected def traverse(r: RegExp): Unit = r match { + // (is tree automaton stuff, more than Berry-Sethi) + case x:Alt => + val it = x.rs.elements + while (it.hasNext) traverse(it.next) + case x:Sequ => + val it = x.rs.elements + while (it.hasNext) traverse(it.next) + case x:Meta => + traverse(x.r) + case Star(t) => + traverse(t) + case _ => + error("unexp pattern " + Platform.getClass(r)) } } diff --git a/src/library/scala/util/automata/DetWordAutom.scala b/src/library/scala/util/automata/DetWordAutom.scala index 3b1cf13644..3eb148b134 100644 --- a/src/library/scala/util/automata/DetWordAutom.scala +++ b/src/library/scala/util/automata/DetWordAutom.scala @@ -9,10 +9,10 @@ // $Id$ -package scala.util.automata ; +package scala.util.automata -import scala.collection.{ Set, Map }; +import scala.collection.{Set, Map} /** A deterministic automaton. States are integers, where * 0 is always the only initial state. Transitions are represented @@ -20,18 +20,34 @@ import scala.collection.{ Set, Map }; * is taken when no other transition can be taken. * All states are reachable. Accepting states are those for which * the partial function 'finals' is defined. + * + * @author Burak Emir + * @version 1.0 */ abstract class DetWordAutom[T <: AnyRef] { - val nstates: Int; - val finals: Array[Int] ; - val delta: Array[Map[T,Int]]; - val default: Array[Int] ; + val nstates: Int + val finals: Array[Int] + val delta: Array[Map[T,Int]] + val default: Array[Int] - def isFinal(q: Int) = finals(q) != 0; + /** + * @param q ... + * @return ... + */ + def isFinal(q: Int) = finals(q) != 0 - def isSink(q: Int) = delta(q).isEmpty && default(q) == q; + /** + * @param q ... + * @return ... + */ + def isSink(q: Int) = delta(q).isEmpty && default(q) == q + /** + * @param q ... + * @param label ... + * @return ... + */ def next(q: Int, label: T) = { delta(q).get(label) match { case Some(p) => p @@ -40,29 +56,29 @@ abstract class DetWordAutom[T <: AnyRef] { } override def toString() = { - val sb = new scala.runtime.compat.StringBuilder(); - sb.append("[DetWordAutom nstates="); - sb.append(nstates); - sb.append(" finals="); - var map = new scala.collection.immutable.ListMap[Int,Int]; + val sb = new scala.runtime.compat.StringBuilder() + sb.append("[DetWordAutom nstates=") + sb.append(nstates) + sb.append(" finals=") + var map = new scala.collection.immutable.ListMap[Int,Int] var j = 0; while( j < nstates ) { - if(j < finals.length) - map = map.update(j,finals(j)); - j = j + 1; + if (j < finals.length) + map = map.update(j, finals(j)) + j = j + 1 } - sb.append(map.toString()); - sb.append(" delta=\n"); - for( val i <- Iterator.range(0,nstates)) { - sb.append( i ); - sb.append("->"); - sb.append(delta(i).toString()); - sb.append('\n'); - if(i < default.length) { - sb.append("_>"); - sb.append(default(i).toString()); - sb.append('\n'); + sb.append(map.toString()) + sb.append(" delta=\n") + for (val i <- 0 until nstates) { + sb.append( i ) + sb.append("->") + sb.append(delta(i).toString()) + sb.append('\n') + if (i < default.length) { + sb.append("_>") + sb.append(default(i).toString()) + sb.append('\n') } } - sb.toString(); + sb.toString() } } diff --git a/src/library/scala/util/automata/Inclusion.scala b/src/library/scala/util/automata/Inclusion.scala index 1e49617e21..eb8beb47b3 100644 --- a/src/library/scala/util/automata/Inclusion.scala +++ b/src/library/scala/util/automata/Inclusion.scala @@ -9,53 +9,59 @@ // $Id$ -package scala.util.automata ; +package scala.util.automata -/** a fast test of language inclusion between minimal automata. +/** A fast test of language inclusion between minimal automata. * inspired by the AMoRE automata library - * @author Burak + * + * @author Burak Emir + * @version 1.0 */ trait Inclusion[A <: AnyRef] { - val labels: Seq[A]; + val labels: Seq[A] - /** returns true if dfa1 is included in dfa2 */ + /** Returns true if dfa1 is included in dfa2. + * + * @param dfa1 ... + * @param dfa2 ... + */ def inclusion(dfa1: DetWordAutom[A], dfa2: DetWordAutom[A]) = { - def encode(q1:Int, q2:Int) = 1 + q1 + q2 * dfa1.nstates; - def decode2(c:Int) = (c-1) / (dfa1.nstates); //integer division - def decode1(c:Int) = (c-1) % (dfa1.nstates); + def encode(q1:Int, q2:Int) = 1 + q1 + q2 * dfa1.nstates + def decode2(c:Int) = (c-1) / (dfa1.nstates) //integer division + def decode1(c:Int) = (c-1) % (dfa1.nstates) - var q1 = 0; //dfa1.initstate; // == 0 - var q2 = 0; //dfa2.initstate; // == 0 + var q1 = 0 //dfa1.initstate; // == 0 + var q2 = 0 //dfa2.initstate; // == 0 - val max = 1 + dfa1.nstates * dfa2.nstates; - val mark = new Array[Int](max); + val max = 1 + dfa1.nstates * dfa2.nstates + val mark = new Array[Int](max) - var result = true; - var current = encode(q1,q2); - var last = current; - mark(last) = max; // mark (q1,q2) - while(current != 0 && result) { + var result = true + var current = encode(q1, q2) + var last = current + mark(last) = max // mark (q1,q2) + while (current != 0 && result) { //Console.println("current = [["+q1+" "+q2+"]] = "+current); - for(val letter <- labels) { - val r1 = dfa1.next(q1,letter); - val r2 = dfa2.next(q2,letter); - if(dfa1.isFinal(r1) && !dfa2.isFinal(r2)) - result = false; - val test = encode(r1,r2); + for (val letter <- labels) { + val r1 = dfa1.next(q1,letter) + val r2 = dfa2.next(q2,letter) + if (dfa1.isFinal(r1) && !dfa2.isFinal(r2)) + result = false + val test = encode(r1, r2) //Console.println("test = [["+r1+" "+r2+"]] = "+test); - if(mark(test) == 0) { - mark(last) = test; - mark(test) = max; - last = test; + if (mark(test) == 0) { + mark(last) = test + mark(test) = max + last = test } } - val ncurrent = mark(current); + val ncurrent = mark(current) if( ncurrent != max ) { - q1 = decode1(ncurrent); - q2 = decode2(ncurrent); + q1 = decode1(ncurrent) + q2 = decode2(ncurrent) current = ncurrent } else { current = 0 diff --git a/src/library/scala/util/automata/NondetWordAutom.scala b/src/library/scala/util/automata/NondetWordAutom.scala index 64f50df82a..ce4f3dd0b4 100644 --- a/src/library/scala/util/automata/NondetWordAutom.scala +++ b/src/library/scala/util/automata/NondetWordAutom.scala @@ -9,10 +9,10 @@ // $Id$ -package scala.util.automata ; +package scala.util.automata -import scala.collection.{ immutable, mutable, Set, Map }; +import scala.collection.{immutable, mutable, Set, Map} /** A nondeterministic automaton. States are integers, where * 0 is always the only initial state. Transitions are represented @@ -23,40 +23,40 @@ import scala.collection.{ immutable, mutable, Set, Map }; */ abstract class NondetWordAutom[T <: AnyRef] { - val nstates: Int; - val labels: Seq[T]; + val nstates: Int + val labels: Seq[T] - val finals: Array[Int] ; // 0 means not final - val delta: Array[Map[T, immutable.BitSet]]; - val default: Array[immutable.BitSet]; + val finals: Array[Int] // 0 means not final + val delta: Array[Map[T, immutable.BitSet]] + val default: Array[immutable.BitSet] /** returns true if the state is final */ - final def isFinal(state: Int) = finals( state ) > 0; + final def isFinal(state: Int) = finals(state) > 0 /** returns tag of final state */ - final def finalTag(state: Int) = finals( state ); + final def finalTag(state: Int) = finals(state) /** returns true if the set of states contains at least one final state */ final def containsFinal(Q: immutable.BitSet): Boolean = { - val it = Q.elements; - while( it.hasNext ) - if( isFinal( it.next )) - return true; - return false; + val it = Q.elements + while (it.hasNext) + if (isFinal(it.next)) + return true + return false } /** returns true if there are no accepting states */ final def isEmpty = { - var r = true; - var j = 0; while( r && ( j < nstates )) { - if(isFinal(j)) - r = false; + var r = true + var j = 0; while(r && (j < nstates)) { + if (isFinal(j)) + r = false } r } /** returns a bitset with the next states for given state and label */ - def next(q:Int, a: T): immutable.BitSet = { + def next(q: Int, a: T): immutable.BitSet = { delta(q).get(a) match { case Some(bs) => bs case _ => default(q) @@ -64,21 +64,21 @@ abstract class NondetWordAutom[T <: AnyRef] { } /** returns a bitset with the next states for given state and label */ - def next(Q:immutable.BitSet, a: T): immutable.BitSet = { - val x = new mutable.BitSet(nstates); - for(val q <- Q) { - for(val i <- next(q,a)) { - x += i; + def next(Q: immutable.BitSet, a: T): immutable.BitSet = { + val x = new mutable.BitSet(nstates) + for (val q <- Q) { + for (val i <- next(q,a)) { + x += i } } x.toImmutable } - def nextDefault(Q:immutable.BitSet): immutable.BitSet = { - val x = new mutable.BitSet(nstates); - for(val q <- Q) { - for(val i <- default(q)) { //@todo: OR + def nextDefault(Q: immutable.BitSet): immutable.BitSet = { + val x = new mutable.BitSet(nstates) + for (val q <- Q) { + for (val i <- default(q)) { //@todo: OR x += i } } @@ -86,28 +86,28 @@ abstract class NondetWordAutom[T <: AnyRef] { } override def toString() = { - val sb = new scala.runtime.compat.StringBuilder(); - sb.append("[NondetWordAutom nstates="); - sb.append(nstates); - sb.append(" finals="); - var map = new scala.collection.immutable.ListMap[Int,Int]; - var j = 0; while( j < nstates ) { - if(isFinal(j)) - map = map.update(j,finals(j)); - j = j + 1; + val sb = new scala.runtime.compat.StringBuilder() + sb.append("[NondetWordAutom nstates=") + sb.append(nstates) + sb.append(" finals=") + var map = new scala.collection.immutable.ListMap[Int,Int] + var j = 0; while (j < nstates) { + if (isFinal(j)) + map = map.update(j, finals(j)); + j = j + 1 } - sb.append(map.toString()); - sb.append(" delta=\n"); - for( val i <- Iterator.range(0,nstates)) { - sb.append(" "); - sb.append( i ); - sb.append("->"); - sb.append(delta(i).toString()); - sb.append("\n "); - sb.append(" _>"); - sb.append(default(i).toString()); - sb.append('\n'); + sb.append(map.toString()) + sb.append(" delta=\n") + for (val i <- 0 until nstates) { + sb.append(" ") + sb.append( i ) + sb.append("->") + sb.append(delta(i).toString()) + sb.append("\n ") + sb.append(" _>") + sb.append(default(i).toString()) + sb.append('\n') } - sb.toString(); + sb.toString() } } diff --git a/src/library/scala/util/automata/WordBerrySethi.scala b/src/library/scala/util/automata/WordBerrySethi.scala index 6a83e428b7..c1dae7566a 100644 --- a/src/library/scala/util/automata/WordBerrySethi.scala +++ b/src/library/scala/util/automata/WordBerrySethi.scala @@ -9,38 +9,38 @@ // $Id$ -package scala.util.automata ; +package scala.util.automata +import scala.collection.{immutable, mutable, Map} +import scala.util.regexp.WordExp -import scala.util.regexp.WordExp ; -import scala.collection.{immutable, - mutable, - Map } ; - -/** this turns a regexp into a NondetWordAutom using the +/** This class turns a regexp into a NondetWordAutom using the * celebrated position automata construction (also called Berry-Sethi or * Glushkov) + * + * @author Burak Emir + * @version 1.0 */ abstract class WordBerrySethi extends BaseBerrySethi { - override val lang: WordExp; + override val lang: WordExp - type _labelT = this.lang._labelT; + type _labelT = this.lang._labelT - import lang.{Alt, Eps, Letter, Meta, RegExp, Sequ, Star} ; + import lang.{Alt, Eps, Letter, Meta, RegExp, Sequ, Star} - protected var labels:mutable.HashSet[_labelT] = _ ; + protected var labels:mutable.HashSet[_labelT] = _ // don't let this fool you, only labelAt is a real, surjective mapping - protected var labelAt: immutable.TreeMap[Int, _labelT] = _; // new alphabet "gamma" + protected var labelAt: immutable.TreeMap[Int, _labelT] = _ // new alphabet "gamma" - protected var deltaq: Array[mutable.HashMap[_labelT,List[Int]]] = _; // delta + protected var deltaq: Array[mutable.HashMap[_labelT,List[Int]]] = _ // delta - protected var defaultq: Array[List[Int]] = _; // default transitions + protected var defaultq: Array[List[Int]] = _ // default transitions - protected var initials:immutable.Set[Int] = _ ; - //NondetWordAutom revNfa ; + protected var initials:immutable.Set[Int] = _ + //NondetWordAutom revNfa // maps a letter to an Integer ( the position ) // is not *really* needed (preorder determines position!) @@ -48,34 +48,36 @@ abstract class WordBerrySethi extends BaseBerrySethi { /** computes first( r ) where the word regexp r */ protected override def compFirst(r: RegExp): immutable.Set[Int] = r match { - case x:Letter => emptySet + x.pos ;//posMap(x); // singleton set + case x:Letter => emptySet + x.pos //posMap(x); // singleton set case Eps => emptySet /*ignore*/ - case _ => super.compFirst(r); + case _ => super.compFirst(r) } /** computes last( r ) where the word regexp r */ protected override def compLast(r: RegExp): immutable.Set[Int] = r match { - case x:Letter => emptySet + x.pos; //posMap(x) // singleton set + case x:Letter => emptySet + x.pos //posMap(x) // singleton set case Eps => emptySet /*ignore*/ case _ => super.compLast(r) } /** returns the first set of an expression, setting the follow set along - * the way + * the way. + * + * @param fol1 ... + * @param r ... + * @return ... */ - protected override def compFollow1( fol1:immutable.Set[Int], r:RegExp ): immutable.Set[Int] = + protected override def compFollow1(fol1: immutable.Set[Int], r: RegExp): immutable.Set[Int] = r match { - case x:Letter => //val i = posMap( x ); - val i = x.pos; - this.follow.update( i, fol1 ); - emptySet + i; - - case Eps => emptySet /*ignore*/ - - case _ => super.compFollow1(fol1, r) - + val i = x.pos + this.follow.update(i, fol1) + emptySet + i + case Eps => + emptySet /*ignore*/ + case _ => + super.compFollow1(fol1, r) } /** returns "Sethi-length" of a pattern, creating the set of position @@ -84,33 +86,33 @@ abstract class WordBerrySethi extends BaseBerrySethi { /** called at the leaves of the regexp */ - protected def seenLabel( r:RegExp, i:Int, label: _labelT ): Unit = { + protected def seenLabel(r: RegExp, i: Int, label: _labelT): Unit = { //Console.println("seenLabel (1)"); //this.posMap.update( r, i ); this.labelAt = this.labelAt.update( i, label ); //@ifdef if( label != Wildcard ) { - this.labels += label ; + this.labels += label //@ifdef } } // overriden in BindingBerrySethi - protected def seenLabel( r: RegExp, label: _labelT ): Int = { + protected def seenLabel(r: RegExp, label: _labelT): Int = { //Console.println("seenLabel (2)"); - pos = pos + 1; - seenLabel( r, pos, label ); + pos = pos + 1 + seenLabel(r, pos, label) pos } // todo: replace global variable pos with acc override def traverse(r: RegExp): Unit = r match { - case a @ Letter( label ) => a.pos = seenLabel( r, label ) ; - case Eps => /*ignore*/ - case _ => super.traverse(r) + case a @ Letter(label) => a.pos = seenLabel(r, label) + case Eps => /*ignore*/ + case _ => super.traverse(r) } - protected def makeTransition(src: Int, dest:Int, label: _labelT ):Unit = { + protected def makeTransition(src: Int, dest: Int, label: _labelT ): Unit = { //@ifdef compiler if( label == Wildcard ) //@ifdef compiler defaultq.update(src, dest::defaultq( src )) //@ifdef compiler else @@ -122,42 +124,41 @@ abstract class WordBerrySethi extends BaseBerrySethi { } protected def initialize(subexpr: Seq[RegExp]): Unit = { - //this.posMap = new mutable.HashMap[RegExp,Int](); - this.labelAt = new immutable.TreeMap[Int,_labelT](); - this.follow = new mutable.HashMap[Int,immutable.Set[Int]](); - this.labels = new mutable.HashSet[_labelT](); + //this.posMap = new mutable.HashMap[RegExp,Int]() + this.labelAt = new immutable.TreeMap[Int,_labelT]() + this.follow = new mutable.HashMap[Int,immutable.Set[Int]]() + this.labels = new mutable.HashSet[_labelT]() - this.pos = 0; + this.pos = 0 // determine "Sethi-length" of the regexp - //activeBinders = new Vector(); - var it = subexpr.elements; - while( it.hasNext ) - traverse( it.next ); + //activeBinders = new Vector() + var it = subexpr.elements + while (it.hasNext) + traverse(it.next) - //assert ( activeBinders.isEmpty() ); - this.initials = emptySet + 0; + //assert(activeBinders.isEmpty()) + this.initials = emptySet + 0 } protected def initializeAutom(): Unit = { - - finals = immutable.TreeMap.Empty[Int,Int]; // final states - deltaq = new Array[mutable.HashMap[_labelT,List[Int]]]( pos ); // delta - defaultq = new Array[List[Int]]( pos ); // default transitions - - var j = 0; - while( j < pos ) { - deltaq( j ) = new mutable.HashMap[_labelT,List[Int]](); - defaultq( j ) = Nil; + finals = immutable.TreeMap.Empty[Int, Int] // final states + deltaq = new Array[mutable.HashMap[_labelT, List[Int]]](pos) // delta + defaultq = new Array[List[Int]](pos) // default transitions + + var j = 0 + while (j < pos) { + deltaq(j) = new mutable.HashMap[_labelT,List[Int]]() + defaultq(j) = Nil j = j + 1 } } protected def collectTransitions(): Unit = { // make transitions - //Console.println("WBS.collectTrans, this.follow.keys = "+this.follow.keys); - //Console.println("WBS.collectTrans, pos = "+this.follow.keys); - var j = 0; while( j < pos ) { - //Console.println("WBS.collectTrans, j = "+j); + //Console.println("WBS.collectTrans, this.follow.keys = "+this.follow.keys) + //Console.println("WBS.collectTrans, pos = "+this.follow.keys) + var j = 0; while (j < pos) { + //Console.println("WBS.collectTrans, j = "+j) val fol = this.follow( j ); val it = fol.elements; while( it.hasNext ) { @@ -172,89 +173,90 @@ abstract class WordBerrySethi extends BaseBerrySethi { } def automatonFrom(pat: RegExp, finalTag: Int): NondetWordAutom[_labelT] = { - this.finalTag = finalTag; + this.finalTag = finalTag pat match { case x:Sequ => // (1,2) compute follow + first - initialize( x.rs ); - pos = pos + 1; - globalFirst = compFollow( x.rs ); + initialize(x.rs) + pos = pos + 1 + globalFirst = compFollow(x.rs) - //System.out.print("someFirst:");debugPrint(someFirst); - // (3) make automaton from follow sets - initializeAutom(); - collectTransitions(); + //System.out.print("someFirst:");debugPrint(someFirst); + // (3) make automaton from follow sets + initializeAutom() + collectTransitions() - if( x.isNullable ) // initial state is final - finals = finals.update( 0, finalTag ); + if (x.isNullable) // initial state is final + finals = finals.update(0, finalTag) - var delta1: immutable.TreeMap[Int,Map[_labelT,List[Int]]] = - new immutable.TreeMap[Int,Map[_labelT,List[Int]]]; + var delta1: immutable.TreeMap[Int, Map[_labelT, List[Int]]] = + new immutable.TreeMap[Int, Map[_labelT, List[Int]]] - var i = 0; - while( i < deltaq.length ) { - delta1 = delta1.update( i, deltaq( i )); - i = i + 1; - } - val finalsArr = new Array[Int](pos); - { - var k = 0; while(k < pos) { - finalsArr(k) = finals.get(k) match { - case Some(z) => z; - case None => 0; // 0 == not final - }; - k = k + 1; + var i = 0 + while (i < deltaq.length) { + delta1 = delta1.update(i, deltaq(i)) + i = i + 1 + } + val finalsArr = new Array[Int](pos) + { + var k = 0; while (k < pos) { + finalsArr(k) = finals.get(k) match { + case Some(z) => z + case None => 0 // 0 == not final + }; + k = k + 1 + } } - } - val initialsArr = new Array[Int](initials.size); - val it = initials.elements; - { - var k = 0; while(k < initials.size) { - initialsArr(k) = it.next; - k = k + 1; + val initialsArr = new Array[Int](initials.size) + val it = initials.elements + { + var k = 0; while (k < initials.size) { + initialsArr(k) = it.next + k = k + 1 + } } - } - val deltaArr = new Array[Map[_labelT,immutable.BitSet]](pos); - { - var k = 0; while(k < pos) { - val labels = delta1(k).keys; - val hmap = - new mutable.HashMap[_labelT,immutable.BitSet]; - for(val lab <- labels) { - val trans = delta1(k); - val x = new mutable.BitSet(pos); - for(val q <- trans(lab)) - x += q; - hmap.update(lab, x.toImmutable); + val deltaArr = new Array[Map[_labelT,immutable.BitSet]](pos) + { + var k = 0; while(k < pos) { + val labels = delta1(k).keys + val hmap = + new mutable.HashMap[_labelT,immutable.BitSet] + for (val lab <- labels) { + val trans = delta1(k) + val x = new mutable.BitSet(pos) + for (val q <- trans(lab)) + x += q + hmap.update(lab, x.toImmutable) + } + deltaArr(k) = hmap + k = k + 1 } - deltaArr(k) = hmap; - k = k + 1; } - } - val defaultArr = new Array[immutable.BitSet](pos); - { - var k = 0; while(k < pos) { - val x = new mutable.BitSet(pos); - for(val q <- defaultq(k)) - x += q; - defaultArr(k) = x.toImmutable; - k = k + 1; + val defaultArr = new Array[immutable.BitSet](pos) + { + var k = 0; while(k < pos) { + val x = new mutable.BitSet(pos) + for (val q <- defaultq(k)) + x += q + defaultArr(k) = x.toImmutable + k = k + 1 + } } - } - new NondetWordAutom[_labelT] { - type _labelT = WordBerrySethi.this._labelT; - val nstates = pos; - val labels = WordBerrySethi.this.labels.toList; - val initials = initialsArr; - val finals = finalsArr; - val delta = deltaArr; - val default = defaultArr; - } - case z:this.lang._regexpT => automatonFrom(Sequ(z), finalTag); + new NondetWordAutom[_labelT] { + type _labelT = WordBerrySethi.this._labelT + val nstates = pos + val labels = WordBerrySethi.this.labels.toList + val initials = initialsArr + val finals = finalsArr + val delta = deltaArr + val default = defaultArr + } + case z:this.lang._regexpT => + automatonFrom(Sequ(z), finalTag) } } |