fixed headers/comments/svn props, made some pro...

fixed headers/comments/svn props, made some progress with serializable
classes

19 files changed, 208 insertions, 96 deletions

diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala
index 0849536755..730c8e1435 100644
--- a/src/library/scala/collection/immutable/HashMap.scala
+++ b/src/library/scala/collection/immutable/HashMap.scala
@@ -15,11 +15,16 @@ import scala.collection.generic._
 import scala.collection.mutable
 import annotation.unchecked.uncheckedVariance
 
-/** This class implements immutable maps using a hash table.
- * It is optimized for sequential accesses where the last updated table is accessed most often.
- * It supports with reasonable efficiency accesses to previous versions of the table by keeping
- * a change log that's regularly compacted.
- * It needs to synchronize most methods, so it is less suitable for highly concurrent accesses.
+/** <p>
+ *    This class implements immutable maps using a hash table.
+ *  </p>
+ *  <p>
+ *    It is optimized for sequential accesses where the last updated table is
+ *    accessed most often. It supports with reasonable efficiency accesses to
+ *    previous versions of the table by keeping a change log that's regularly
+ *    compacted. It needs to synchronize most methods, so it is less suitable
+ *    for highly concurrent accesses.
+ *  </p>
  *
  * @note the builder of a hash map returns specialized representations EmptyMap,Map1,..., Map4
  * for maps of size <= 4.
@@ -27,7 +32,7 @@ import annotation.unchecked.uncheckedVariance
  *  @author  Martin Odersky
  *  @version 2.0, 19/01/2007
  */
-@serializable
+@serializable @SerialVersionUID(8886909077084990906L)
 class HashMap[A, +B] extends Map[A,B] with ImmutableMapTemplate[A, B, HashMap[A, B]] with mutable.HashTable[A] {
 
   type Entry = collection.mutable.DefaultEntry[A, Any]
diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala
index 9300164438..6589e83e92 100644
--- a/src/library/scala/collection/immutable/HashSet.scala
+++ b/src/library/scala/collection/immutable/HashSet.scala
@@ -8,16 +8,22 @@
 
 // $Id$
 
+
 package scala.collection.immutable
 
 import scala.collection.generic._
 import scala.collection.mutable
 
-/** This class implements immutable sets using a hash table.
- * It is optimized for sequential accesses where the last updated table is accessed most often.
- * It supports with reasonable efficiency accesses to previous versions of the table by keeping
- * a change log that's regularly compacted.
- * It needs to synchronize most methods, so it is less suitable for highly concurrent accesses.
+/** <p>
+ *    This class implements immutable sets using a hash table.
+ *  </p>
+ *  <p>
+ *    It is optimized for sequential accesses where the last updated table is
+ *    accessed most often. It supports with reasonable efficiency accesses to
+ *    previous versions of the table by keeping a change log that's regularly
+ *    compacted. It needs to synchronize most methods, so it is less suitable
+ *    for highly concurrent accesses.
+ *  </p>
  *
  * @note the builder of a hash set returns specialized representations EmptySet,Set1,..., Set4
  * for sets of size <= 4.
@@ -25,7 +31,7 @@ import scala.collection.mutable
  *  @author  Martin Odersky
  *  @version 2.8
  */
-@serializable
+@serializable @SerialVersionUID(4020728942921483037L)
 class HashSet[A] extends Set[A]
                     with SetClass[A, HashSet]
                     with SetTemplate[A, HashSet[A]]
@@ -127,11 +133,11 @@ class HashSet[A] extends Set[A]
   }
 }
 
-/** A factory object for immutable HashSets
-  *
-  *  @author  Martin Odersky
-  *  @version 2.8
-  */
+/** A factory object for immutable HashSets.
+ *
+ *  @author  Martin Odersky
+ *  @version 2.8
+ */
 object HashSet extends SetFactory[HashSet] {
   implicit def builderFactory[A]: BuilderFactory[A, HashSet[A], Coll] = setBuilderFactory[A]
   override def empty[A]: HashSet[A] = new HashSet
diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala
index 19ebbdfac4..8c22089f21 100644
--- a/src/library/scala/collection/immutable/IntMap.scala
+++ b/src/library/scala/collection/immutable/IntMap.scala
@@ -1,9 +1,20 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: $
+
+
 package scala.collection.immutable;
 
 /**
  * @author David MacIver
  */
-private[immutable] object IntMapUtils{
+private[immutable] object IntMapUtils {
   def zero(i : Int, mask : Int) = (i & mask) == 0;
   def mask(i : Int, mask : Int) = i & (complement(mask - 1) ^ mask)
   def hasMatch(key : Int, prefix : Int, m : Int) = mask(key, m) == prefix;
@@ -38,7 +49,7 @@ private[immutable] object IntMapUtils{
 
 import IntMapUtils._
 
-object IntMap{
+object IntMap {
   def empty[T] : IntMap[T]  = IntMap.Nil;
   def singleton[T](key : Int, value : T) : IntMap[T] = IntMap.Tip(key, value);
   def apply[T](elems : (Int, T)*) : IntMap[T] =
@@ -122,14 +133,14 @@ private[immutable] class IntMapEntryIterator[V](it : IntMap[V]) extends IntMapIt
 }
 
 private[immutable] class IntMapValueIterator[V](it : IntMap[V]) extends IntMapIterator[V, V](it){
-  def valueOf(tip : IntMap.Tip[V]) = tip.value;
+  def valueOf(tip : IntMap.Tip[V]) = tip.value
 }
 
 private[immutable] class IntMapKeyIterator[V](it : IntMap[V]) extends IntMapIterator[V, Int](it){
-  def valueOf(tip : IntMap.Tip[V]) = tip.key;
+  def valueOf(tip : IntMap.Tip[V]) = tip.key
 }
 
-import IntMap._;
+import IntMap._
 
 /**
  * Specialised immutable map structure for integer keys, based on
diff --git a/src/library/scala/collection/immutable/Iterable.scala b/src/library/scala/collection/immutable/Iterable.scala
index 649d2eafc5..4a85779443 100644
--- a/src/library/scala/collection/immutable/Iterable.scala
+++ b/src/library/scala/collection/immutable/Iterable.scala
@@ -1,3 +1,14 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+
 package scala.collection.immutable
 
 import scala.collection.generic._
@@ -17,7 +28,11 @@ trait Iterable[+A] extends Traversable[A]
   override def companion: Companion[Iterable] = Iterable
 }
 
-/* A factory object for the trait `Iterable` */
+/** A factory object for the trait <code>Iterable</code>.
+ *
+ *  @author   Martin Odersky
+ *  @version 2.8
+ */
 object Iterable extends TraversableFactory[Iterable] {
   implicit def builderFactory[A]: BuilderFactory[A, Iterable[A], Coll] = new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Iterable[A]] = new mutable.ListBuffer
diff --git a/src/library/scala/collection/immutable/LinearSequence.scala b/src/library/scala/collection/immutable/LinearSequence.scala
index da4b364b74..073a3691ca 100644
--- a/src/library/scala/collection/immutable/LinearSequence.scala
+++ b/src/library/scala/collection/immutable/LinearSequence.scala
@@ -1,9 +1,20 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id$
+
+
 package scala.collection.immutable
 
 import scala.collection.generic._
 import scala.collection.mutable
 
-/** A subtrait of collection.Sequence which represents sequences
+/** A subtrait of <code>collection.Sequence</code> which represents sequences
  *  that cannot be mutated.
  */
 trait LinearSequence[+A] extends Sequence[A]
diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index 26c8a309a5..2642337540 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -743,6 +743,7 @@ object List extends SequenceFactory[List] {
 
   /** Returns the list resulting from applying the given function <code>f</code>
    *  to corresponding elements of the argument lists.
+   *
    *  @param f function to apply to each pair of elements.
    *  @return <code>[f(a0,b0), ..., f(an,bn)]</code> if the lists are
    *          <code>[a0, ..., ak]</code>, <code>[b0, ..., bl]</code> and
@@ -837,7 +838,7 @@ object List extends SequenceFactory[List] {
    *  @param xss the list of lists
    *  @return    the transposed list of lists
    */
-  @deprecated("use p`xss.transpose' instead")
+  @deprecated("use `xss.transpose' instead")
   def transpose[A](xss: List[List[A]]): List[List[A]] = {
     val buf = new ListBuffer[List[A]]
     var yss = xss
diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala
index 40ecc67381..c991318872 100644
--- a/src/library/scala/collection/immutable/ListMap.scala
+++ b/src/library/scala/collection/immutable/ListMap.scala
@@ -9,14 +9,15 @@
 // $Id$
 
 
-
 package scala.collection.immutable
 
 import scala.collection.generic._
 
-/** The canonical factory of <a href="ListMap.html">ListMap</a>'s */
+/** The canonical factory of <a href="ListMap.html">ListMap</a>'s.
+ */
 object ListMap extends ImmutableMapFactory[ListMap] {
-  implicit def builderFactory[A, B]: BuilderFactory[(A, B), ListMap[A, B], Coll] = new MapBuilderFactory[A, B]
+  implicit def builderFactory[A, B]: BuilderFactory[(A, B), ListMap[A, B], Coll] =
+    new MapBuilderFactory[A, B]
   def empty[A, B]: ListMap[A, B] = new ListMap
 }
 
@@ -29,7 +30,7 @@ object ListMap extends ImmutableMapFactory[ListMap] {
  *  @author  Martin Oderskty
  *  @version 2.0, 01/01/2007
  */
-@serializable
+@serializable @SerialVersionUID(301002838095710379L)
 class ListMap[A, +B] extends Map[A, B] with ImmutableMapTemplate[A, B, ListMap[A, B]] {
 
   override def empty = ListMap.empty
@@ -99,7 +100,7 @@ class ListMap[A, +B] extends Map[A, B] with ImmutableMapTemplate[A, B, ListMap[A
   protected def value: B = throw new NoSuchElementException("empty map")
   protected def next: ListMap[A, B] = throw new NoSuchElementException("empty map")
 
-  @serializable
+  @serializable @SerialVersionUID(-6453056603889598734L)
   protected class Node[B1 >: B](override protected val key: A,
                                 override protected val value: B1) extends ListMap[A, B1] {
     /** Returns the number of mappings in this map.
diff --git a/src/library/scala/collection/immutable/MapProxy.scala b/src/library/scala/collection/immutable/MapProxy.scala
index 933ba3acfc..de3474a2d0 100644
--- a/src/library/scala/collection/immutable/MapProxy.scala
+++ b/src/library/scala/collection/immutable/MapProxy.scala
@@ -25,7 +25,6 @@ import scala.collection.generic.MapProxyTemplate
  *  @author  Matthias Zenger, Martin Odersky
  *  @version 2.0, 31/12/2006
  */
-
 trait MapProxy[A, +B] extends Map[A, B] with MapProxyTemplate[A, B, Map[A, B]]
 {
   override def repr = this
diff --git a/src/library/scala/collection/immutable/Queue.scala b/src/library/scala/collection/immutable/Queue.scala
index 0daa31af77..343c4d2779 100644
--- a/src/library/scala/collection/immutable/Queue.scala
+++ b/src/library/scala/collection/immutable/Queue.scala
@@ -25,6 +25,7 @@ object Queue {
  *  @version 1.0, 08/07/2003
  */
 @serializable
+@SerialVersionUID(-7622936493364270175L)
 class Queue[+A] protected(
   protected val  in: List[A],
   protected val out: List[A]) extends Sequence[A]
@@ -110,7 +111,7 @@ class Queue[+A] protected(
   def dequeue: (A, Queue[A]) = out match {
     case Nil if !in.isEmpty => val rev = in.reverse ; (rev.head, new Queue(Nil, rev.tail))
     case x :: xs            => (x, new Queue(in, xs))
-    case _                  => throw new NoSuchElementException("queue empty")
+    case _                  => throw new NoSuchElementException("dequeue on empty queue")
   }
 
   /** Returns the first element in the queue, or throws an error if there
@@ -122,7 +123,7 @@ class Queue[+A] protected(
   def front: A =
     if (!out.isEmpty) out.head
     else if (!in.isEmpty) in.last
-    else throw new NoSuchElementException("queue empty")
+    else throw new NoSuchElementException("front on empty queue")
 
   /** Returns a string representation of this queue.
    */
diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala
index ee00d36ad2..0ff253045e 100644
--- a/src/library/scala/collection/immutable/RedBlack.scala
+++ b/src/library/scala/collection/immutable/RedBlack.scala
@@ -7,9 +7,11 @@
 \*                                                                      */
 
 // $Id$
+
+
 package scala.collection.immutable
 
-@serializable
+@serializable @SerialVersionUID(8691885935445612921L)
 abstract class RedBlack[A] {
 
   def isSmaller(x: A, y: A): Boolean
@@ -30,14 +32,14 @@ abstract class RedBlack[A] {
     def delete(k: A): Tree[B] = del(k)
     def foreach[U](f: (A, B) =>  U)
     @deprecated("use `foreach' instead")
-    def visit[T](input : T)(f : (T,A,B) => Tuple2[Boolean,T]) : Tuple2[Boolean,T];
+    def visit[T](input: T)(f: (T, A, B) => (Boolean, T)): (Boolean, T)
     def toStream: Stream[(A,B)]
     def iterator: Iterator[(A, B)]
     @deprecated("use `iterator' instead") def elements = iterator
     def upd[B1 >: B](k: A, v: B1): Tree[B1]
     def del(k: A): Tree[B]
     def smallest: NonEmpty[B]
-    def range(from : Option[A], until : Option[A]) : Tree[B]
+    def range(from: Option[A], until: Option[A]): Tree[B]
     def first : A
     def last : A
     def count : Int
@@ -85,27 +87,28 @@ abstract class RedBlack[A] {
       }
     }
     def smallest: NonEmpty[B] = if (left.isEmpty) this else left.smallest
+
     def toStream: Stream[(A,B)] =
       left.toStream ++ Stream((key,value)) ++ right.toStream
 
     def iterator: Iterator[(A, B)] =
       left.iterator ++ Iterator.single(Pair(key, value)) ++ right.iterator
 
-    def foreach[U](f: (A, B) =>  U) {
+    def foreach[U](f: (A, B) => U) {
       left foreach f
       f(key, value)
       right foreach f
     }
 
     @deprecated("use `foreach' instead")
-    def visit[T](input : T)(f : (T,A,B) => Tuple2[Boolean,T]) : Tuple2[Boolean,T] = {
+    def visit[T](input: T)(f: (T,A,B) => (Boolean, T)): (Boolean, T) = {
       val left = this.left.visit(input)(f)
       if (!left._1) return left
       val middle = f(left._2, key, value)
       if (!middle._1) return middle
       return this.right.visit(middle._2)(f)
     }
-   override def range(from : Option[A], until : Option[A]) : Tree[B] = {
+   override def range(from: Option[A], until: Option[A]): Tree[B] = {
       if (from == None && until == None) return this
       if (from != None && isSmaller(key, from.get)) return right.range(from, until);
       if (until != None && (isSmaller(until.get,key) || !isSmaller(key,until.get)))
@@ -132,12 +135,12 @@ abstract class RedBlack[A] {
     def iterator: Iterator[(A, Nothing)] = Iterator.empty
     def toStream: Stream[(A,Nothing)] = Stream.empty
 
-    def foreach[U](f: (A, Nothing) =>  U) {}
+    def foreach[U](f: (A, Nothing) => U) {}
 
     @deprecated("use `foreach' instead")
-    def visit[T](input : T)(f : (T,A,Nothing) => Tuple2[Boolean,T]) = Tuple2(true,input)
+    def visit[T](input: T)(f: (T, A, Nothing) => (Boolean, T)) = (true, input)
 
-    def range(from : Option[A], until : Option[A]) = this
+    def range(from: Option[A], until: Option[A]) = this
     def first = throw new NoSuchElementException("empty map")
     def last = throw new NoSuchElementException("empty map")
     def count = 0
diff --git a/src/library/scala/collection/immutable/Sequence.scala b/src/library/scala/collection/immutable/Sequence.scala
index 7663b9c3ce..3ce7cd3b00 100644
--- a/src/library/scala/collection/immutable/Sequence.scala
+++ b/src/library/scala/collection/immutable/Sequence.scala
@@ -5,6 +5,10 @@
 ** /____/\___/_/ |_/____/_/ | |                                         **
 **                          |/                                          **
 \*                                                                      */
+
+// $Id$
+
+
 package scala.collection.immutable
 
 import scala.collection.generic._
diff --git a/src/library/scala/collection/immutable/SetProxy.scala b/src/library/scala/collection/immutable/SetProxy.scala
index 30b11f62b4..55acfe0236 100644
--- a/src/library/scala/collection/immutable/SetProxy.scala
+++ b/src/library/scala/collection/immutable/SetProxy.scala
@@ -6,6 +6,9 @@
 **                          |/                                          **
 \*                                                                      */
 
+// $Id$
+
+
 package scala.collection.immutable
 
 import scala.collection.generic.SetProxyTemplate
@@ -19,7 +22,6 @@ import scala.collection.generic.SetProxyTemplate
  *    dynamically using object composition and forwarding.
  *  </p>
  */
-
 trait SetProxy[A] extends Set[A] with SetProxyTemplate[A, Set[A]]
 {
   override def repr = this
diff --git a/src/library/scala/collection/immutable/SortedMap.scala b/src/library/scala/collection/immutable/SortedMap.scala
index b363c54a29..4f3bbf6c0d 100644
--- a/src/library/scala/collection/immutable/SortedMap.scala
+++ b/src/library/scala/collection/immutable/SortedMap.scala
@@ -9,17 +9,17 @@
 // $Id$
 
 
+package scala.collection.immutable
+
+import scala.collection.generic._
+import annotation.unchecked.uncheckedVariance
+
 /** A map whose keys are sorted.
  *
  *  @author Sean McDirmid
  *  @author Martin Odersky
  *  @version 2.8
  */
-package scala.collection.immutable
-
-import scala.collection.generic._
-import annotation.unchecked.uncheckedVariance
-
 trait SortedMap[A, +B] extends Map[A, B]
                          with collection.SortedMap[A, B]
                          with ImmutableMapTemplate[A, B, SortedMap[A, B]]
diff --git a/src/library/scala/collection/immutable/SortedSet.scala b/src/library/scala/collection/immutable/SortedSet.scala
index 80fd411acd..d2afc58cf2 100644
--- a/src/library/scala/collection/immutable/SortedSet.scala
+++ b/src/library/scala/collection/immutable/SortedSet.scala
@@ -8,16 +8,17 @@
 
 // $Id$
 
+
+package scala.collection.immutable
+
+import scala.collection.generic._
+
 /** A sorted set.
  *
  *  @author Sean McDirmid
  *  @author Martin Odersky
  *  @version 2.8
  */
-package scala.collection.immutable
-
-import scala.collection.generic._
-
 trait SortedSet[A] extends Set[A] with collection.SortedSet[A] with SortedSetTemplate[A, SortedSet[A]] {
   /** Needs to be overridden in subclasses. */
   override def empty: SortedSet[A] = throw new UnsupportedOperationException("SortedMap.empty")
diff --git a/src/library/scala/collection/immutable/Stack.scala b/src/library/scala/collection/immutable/Stack.scala
index 4684a22162..779e727623 100644
--- a/src/library/scala/collection/immutable/Stack.scala
+++ b/src/library/scala/collection/immutable/Stack.scala
@@ -11,42 +11,46 @@
 
 package scala.collection.immutable
 
-
-//import Predef.NoSuchElementException
+import scala.annotation.tailrec
 
 object Stack {
-  val Empty = new Stack[Nothing]
+  val Empty: Stack[Nothing] = new Stack(Nil)
+  def apply[A](elems: A*) = new Stack(elems.toList)
 }
 
 /** This class implements immutable stacks using a list-based data
  *  structure. Instances of <code>Stack</code> represent
  *  empty stacks; they can be either created by calling the constructor
  *  directly, or by applying the function <code>Stack.Empty</code>.
- *  @note    This class exists only for historical reason and as an analogue of mutable stacks
+ *
+ *  @note    This class exists only for historical reason and as an
+ *           analogue of mutable stacks
  *           Instead of an immutable stack you can just use a list.
  *
  *  @author  Matthias Zenger
  *  @version 1.0, 10/07/2003
  */
-@serializable
-class Stack[+A] extends Sequence[A] {
+@serializable @SerialVersionUID(1976480595012942526L)
+class Stack[+A] protected (protected val elems: List[A]) extends Sequence[A] {
+
+  def this() = this(Nil)
 
   /** Checks if this stack is empty.
    *
    *  @return true, iff there is no element on the stack.
    */
-  override def isEmpty: Boolean = true
+  override def isEmpty: Boolean = elems.isEmpty
 
   /** The number of elements in the stack
    */
-  def length: Int = 0
+  def length: Int = elems.length
 
   /** 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 push[B >: A](elem: B): Stack[B] = new Node(elem)
+  def push[B >: A](elem: B): Stack[B] = new Stack(elem :: elems)
 
   /** Push a sequence of elements onto the stack. The last element
    *  of the sequence will be on top of the new stack.
@@ -81,23 +85,45 @@ class Stack[+A] extends Sequence[A] {
   /** Returns the top element of the stack. An error is signaled if
    *  there is no element on the stack.
    *
+   *  @throws Predef.NoSuchElementException
    *  @return the top element.
    */
-  def top: A = throw new NoSuchElementException("top of empty stack")
+  def top: A =
+    if (!elems.isEmpty) elems.head
+    else throw new NoSuchElementException("top of empty stack")
 
   /** Removes the top element from the stack.
+   *  Note: should return <code>(A, Stack[A])</code> as for queues (mics)
    *
+   *  @throws Predef.NoSuchElementException
    *  @return the new stack without the former top element.
    */
-  def pop: Stack[A] = throw new NoSuchElementException("pop of empty stack")
+  def pop: Stack[A] =
+    if (!elems.isEmpty) new Stack(elems.tail)
+    else throw new NoSuchElementException("pop of empty stack")
+
+  def pop2: (A, Stack[A]) =
+    if (!elems.isEmpty) (elems.head, new Stack(elems.tail))
+    else throw new NoSuchElementException("pop of empty stack")
 
   /** Returns the n-th element of this stack. The bottom element has index
    *  0, elements above are indexed with increasing numbers.
    *
+   *  @throws Predef.NoSuchElementException
    *  @param   n      the index number.
    *  @return the n-th element on the stack.
    */
-  def apply(n: Int): A = if (n <= 0) top else pop.apply(n - 1)
+  def apply(n: Int): A = {
+    @tailrec
+    def walk(i: Int, xs: List[A]): A =
+      (i == 0, xs.isEmpty) match {
+        case (_, true)  => throw new NoSuchElementException("index out of range")
+        case (true, _)  => xs.head
+        case (false, _) => walk(i - 1, xs.tail)
+      }
+
+    walk(n, elems)
+  }
 
   /** Returns an iterator over all elements on the stack. The iterator
    *  issues elements in the reversed order they were inserted into the
@@ -111,17 +137,17 @@ class Stack[+A] extends Sequence[A] {
     def next: A = { val r = top; cur = cur.pop; r }
   }
 
-  /**
-   * Redefines the prefix of the string representation.
+  /** Returns the hash code for this stack.
+   *
+   *  @return the hash code of the stack.
    */
-  override def stringPrefix: String = "Stack"
-
-  @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 top: B = elem
-    override def pop: Stack[B] = Stack.this
-  }
+  override def hashCode(): Int = //"Stack".hashCode
+    if (isEmpty) 0
+    else pop2 match { case (x,y) => x.hashCode + y.hashCode }
+
+  /** Returns a string representation of this stack.
+   */
+  override def toString() = elems.mkString("Stack(", ", ", ")")
+
 }
 
diff --git a/src/library/scala/collection/immutable/Traversable.scala b/src/library/scala/collection/immutable/Traversable.scala
index 53fc96aae0..ed79a87b7a 100644
--- a/src/library/scala/collection/immutable/Traversable.scala
+++ b/src/library/scala/collection/immutable/Traversable.scala
@@ -1,13 +1,25 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: $
+
+
 package scala.collection.immutable
 
 import scala.collection.generic._
 import scala.collection.mutable
 
-/** A subtrait of Traversable in package collection which represents traversables
- *  that cannot be mutated.
+/** A subtrait of <code>collection.Traversable</code> which represents
+ *  traversables that cannot be mutated.
  *  !!! todo: revise equality
+ *
  *  @author  Matthias Zenger
- *  @author   Martin Odersky
+ *  @author  Martin Odersky
  *  @version 2.8
  */
 trait Traversable[+A] extends collection.Traversable[A]
@@ -17,10 +29,13 @@ trait Traversable[+A] extends collection.Traversable[A]
   override def companion: Companion[Traversable] = Traversable
 }
 
-/* A factory object for the trait `Traversable` */
+/** A factory object for the trait <code>Traversable</code>.
+ *
+ *  @author  Martin Odersky
+ *  @version 2.8
+ */
 object Traversable extends TraversableFactory[Traversable] {
-  implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] = new VirtualBuilderFactory[A]
+  implicit def builderFactory[A]: BuilderFactory[A, Traversable[A], Coll] =
+    new VirtualBuilderFactory[A]
   def newBuilder[A]: Builder[A, Traversable[A]] = new mutable.ListBuffer
 }
-
-
diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index c146064296..90f8fe9827 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -8,6 +8,7 @@
 
 // $Id$
 
+
 package scala.collection.immutable
 
 import scala.collection.generic._
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index 0e5496828a..58d1bddba5 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -13,15 +13,17 @@ package scala.collection.immutable
 
 import scala.collection.generic._
 
-/** The canonical factory of <a href="TreeSet.html">TreeSet</a>'s. */
+/** The canonical factory of <a href="TreeSet.html">TreeSet</a>'s.
+ */
 object TreeSet extends SortedSetFactory[TreeSet]{
 
-  implicit def implicitBuilder[A](implicit ordering : Ordering[A]) : Builder[A, TreeSet[A]] = newBuilder[A](ordering)
-  def newBuilder[A](implicit ordering : Ordering[A]) : Builder[A, TreeSet[A]] = new AddingBuilder(empty[A](ordering))
+  implicit def implicitBuilder[A](implicit ordering: Ordering[A]): Builder[A, TreeSet[A]] = newBuilder[A](ordering)
+  def newBuilder[A](implicit ordering: Ordering[A]): Builder[A, TreeSet[A]] =
+    new AddingBuilder(empty[A](ordering))
 
   /** The empty set of this type
    */
-  def empty[A](implicit ordering : Ordering[A]) = new TreeSet[A]
+  def empty[A](implicit ordering: Ordering[A]) = new TreeSet[A]
 
 }
 
@@ -30,16 +32,16 @@ object TreeSet extends SortedSetFactory[TreeSet]{
  *  @author  Martin Odersky
  *  @version 2.0, 02/01/2007
  */
-
-@serializable
-class TreeSet[A](override val size: Int, t: RedBlack[A]#Tree[Unit])(implicit val ordering : Ordering[A])
+@serializable @SerialVersionUID(-234066569443569402L)
+class TreeSet[A](override val size: Int, t: RedBlack[A]#Tree[Unit])
+                (implicit val ordering: Ordering[A])
   extends RedBlack[A] with SortedSet[A] with SortedSetTemplate[A, TreeSet[A]] {
 
   override def stringPrefix = "TreeSet"
 
   def isSmaller(x: A, y: A) = compare(x,y) < 0
 
-  def this()(implicit ordering : Ordering[A]) = this(0, null)(ordering)
+  def this()(implicit ordering: Ordering[A]) = this(0, null)(ordering)
 
   protected val tree: RedBlack[A]#Tree[Unit] = if (size == 0) Empty else t
 
@@ -59,14 +61,14 @@ class TreeSet[A](override val size: Int, t: RedBlack[A]#Tree[Unit])(implicit val
   /** A new TreeSet with the entry added is returned,
    *  assuming that elem is <em>not</em> in the TreeSet.
    */
-  def insert (elem: A): TreeSet[A] = {
+  def insert(elem: A): TreeSet[A] = {
     assert(tree.lookup(elem).isEmpty)
     newSet(size + 1, tree.update(elem, ()))
   }
 
   def - (elem:A): TreeSet[A] =
     if (tree.lookup(elem).isEmpty) this
-    else newSet(size - 1, tree.delete(elem))
+    else newSet(size - 1, tree delete elem)
 
   /** Checks if this set contains element <code>elem</code>.
    *
diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala
index 41b4be580a..ff224507ee 100644
--- a/src/library/scala/collection/immutable/Vector.scala
+++ b/src/library/scala/collection/immutable/Vector.scala
@@ -5,12 +5,16 @@
 ** /____/\___/_/ |_/____/_/ | |                                         **
 **                          |/                                          **
 \*                                                                      */
+
+// $Id$
+
+
 package scala.collection.immutable
 
 import scala.collection.generic._
 import scala.collection.mutable.ArrayBuffer
 
-/** A subtrait of collection.Vector which represents sequences
+/** A subtrait of <code>collection.Vector</code> which represents sequences
  *  that cannot be mutated.
  */
 trait Vector[+A] extends Sequence[A]
@@ -21,10 +25,14 @@ trait Vector[+A] extends Sequence[A]
 }
 
 object Vector extends SequenceFactory[Vector] {
-  class Impl[A](buf: ArrayBuffer[A]) extends Vector[A] { // todo: insert better vector implementation here
+  // todo: insert better vector implementation here
+  @serializable @SerialVersionUID(7129304555082767876L)
+  class Impl[A](buf: ArrayBuffer[A]) extends Vector[A] {
     def length = buf.length
     def apply(idx: Int) = buf.apply(idx)
   }
-  implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new VirtualBuilderFactory[A]
-  def newBuilder[A]: Builder[A, Vector[A]] = new ArrayBuffer[A] mapResult (buf => new Impl(buf))
+  implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] =
+    new VirtualBuilderFactory[A]
+  def newBuilder[A]: Builder[A, Vector[A]] =
+    new ArrayBuffer[A] mapResult (buf => new Impl(buf))
 }