massive new collections checkin.

1 files changed, 188 insertions, 168 deletions

diff --git a/src/library/scala/collection/mutable/ListBuffer.scala b/src/library/scala/collection/mutable/ListBuffer.scala
index 2fb8e39bdf..9374afc3db 100644
--- a/src/library/scala/collection/mutable/ListBuffer.scala
+++ b/src/library/scala/collection/mutable/ListBuffer.scala
@@ -11,144 +11,40 @@
 
 package scala.collection.mutable
 
-
-import Predef._
+import generic._
+// import immutable.{List, Nil, ::}
 
 /** A Buffer implementation back up by a list. It provides constant time
  *  prepend and append. Most other operations are linear.
  *
  *  @author  Matthias Zenger
- *  @version 1.0, 15/03/2004
+ *  @author  Martin Odersky
+ *  @version 2.8
  */
 @serializable
-final class ListBuffer[A] extends Buffer[A] {
+final class ListBuffer[A]
+      extends Buffer[A]
+         with BufferTemplate[A, ListBuffer[A]]
+         with Builder[A, List[A], Any]
+         with SequenceForwarder[A]
+{
+  import collection.Traversible
+
   private var start: List[A] = Nil
   private var last0: ::[A] = _
   private var exported: Boolean = false
+  private var len = 0
 
-  /** Prepends a single element to this buffer. It takes constant
-   *  time.
-   *
-   *  @param x  the element to prepend.
-   *  @return   this buffer.
-   */
-  def +: (x: A): Buffer[A] = {
-    if (exported) copy()
-    val newElem = new scala.:: (x, start)
-    if (start.isEmpty) last0 = newElem
-    start = newElem
-    this
-  }
-
-
-
-  /** Appends a single element to this buffer. It takes constant
-   *  time.
-   *
-   *  @param x  the element to append.
-   */
-  override def += (x: A) {
-    if (exported) copy()
-    if (start.isEmpty) {
-      last0 = new scala.:: (x, Nil)
-      start = last0
-    } else {
-      val last1 = last0
-      last0 = new scala.:: (x, Nil)
-      last1.tl = last0
-    }
-  }
-
-  /** Removes a single element from the buffer and return
-   *  the identity of the buffer. Same as <code>this -= x; this</code>. It
-   *  takes linear time (except removing the first element, which is done
-   *  in constant time).
-   *
-   *  @param x  the element to remove.
-   *  @return   this buffer.
-   */
-  def - (x: A): Buffer[A] = { this -= x; this }
-
-  /** Remove a single element from this buffer. It takes linear time
-   *  (except removing the first element, which is done  in constant time).
-   *
-   *  @param x  the element to remove.
-   */
-  override def -= (x: A) {
-    if (exported) copy()
-    if (start.isEmpty) {}
-    else if (start.head == x) start = start.tail
-    else {
-      var cursor = start
-      while (!cursor.tail.isEmpty && cursor.tail.head != x) { cursor = cursor.tail }
-      if (!cursor.tail.isEmpty) {
-        val z = cursor.asInstanceOf[scala.::[A]]
-        if (z.tl == last0)
-          last0 = z
-        z.tl = cursor.tail.tail
-      }
-    }
-  }
-
-  /** Converts this buffer to a list. Takes constant time. The buffer is
-   *  copied lazily, the first time it is mutated.
-   */
-  override def toList: List[A] = {
-    exported = !start.isEmpty
-    start
-  }
-  /** expose the underlying list but do not mark it as exported */
-  override def readOnly : List[A] = start
+  protected def underlying: immutable.Sequence[A] = start
 
-  /** Prepends the elements of this buffer to a given list
-   *
-   *  @param xs   the list to which elements are prepended
-   */
-  def prependToList(xs: List[A]): List[A] =
-    if (start.isEmpty) xs
-    else { last0.tl = xs; toList }
+  override protected[this] def newBuilder = ListBuffer.newBuilder[A]
+  override def traversibleBuilder[B]: Builder[B, ListBuffer[B], Any] = ListBuffer.newBuilder[B]
 
-  /** Clears the buffer contents.
+  /** The current length of the buffer
    */
-  def clear() {
-    start = Nil
-    exported = false
-  }
+  override def length = len
 
-  /** Copy contents of this buffer */
-  private def copy() {
-    var cursor = start
-    val limit = last0.tail
-    clear
-    while (cursor ne limit) {
-      this += cursor.head
-      cursor = cursor.tail
-    }
-  }
-
-  /** Returns the length of this buffer. It takes linear time.
-   *
-   *  @return the length of this buffer.
-   */
-  def length: Int = start.length
-
-  // will be faster since this is a list
-  override def isEmpty = start.isEmpty
-
-  /** Returns the n-th element of this list. This method
-   *  yields an error if the element does not exist. Takes time
-   *  linear in the buffer size.
-   *
-   *  @param n  the position of the element to be returned.
-   *  @return   the n-th element of this buffer.
-   *  @throws Predef.IndexOutOfBoundsException
-   */
-  def apply(n: Int): A = try {
-    start(n)
-  } catch {
-    case ex: Exception =>
-      throw new IndexOutOfBoundsException(n.toString())
-  }
+  // Implementations of abstract methods in Buffer
 
   /** Replaces element at index <code>n</code> with the new element
    *  <code>newelem</code>. Takes time linear in the buffer size. (except the first
@@ -162,8 +58,11 @@ final class ListBuffer[A] extends Buffer[A] {
     try {
       if (exported) copy()
       if (n == 0) {
-        val newElem = new scala.:: (x, start.tail);
-        if (last0 eq start) last0 = newElem
+        val newElem = new :: (x, start.tail);
+        if (last0 eq start) {
+          last0 = newElem
+          len += 1
+        }
         start = newElem
       } else {
         var cursor = start
@@ -172,15 +71,58 @@ final class ListBuffer[A] extends Buffer[A] {
           cursor = cursor.tail
           i += 1
         }
-        val newElem = new scala.:: (x, cursor.tail.tail)
-        if (last0 eq cursor.tail) last0 = newElem
-        cursor.asInstanceOf[scala.::[A]].tl = newElem
+        val newElem = new :: (x, cursor.tail.tail)
+        if (last0 eq cursor.tail) {
+          last0 = newElem
+          len += 1
+        }
+        cursor.asInstanceOf[::[A]].tl = newElem
       }
     } catch {
       case ex: Exception => throw new IndexOutOfBoundsException(n.toString())
     }
   }
 
+  /** Appends a single element to this buffer. This operation takes constant time.
+   *
+   *  @param x  the element to append.
+   */
+  def += (x: A) {
+    if (exported) copy()
+    if (start.isEmpty) {
+      last0 = new :: (x, Nil)
+      start = last0
+    } else {
+      val last1 = last0
+      last0 = new :: (x, Nil)
+      last1.tl = last0
+    }
+    len += 1
+  }
+
+  /** Clears the buffer contents.
+   */
+  def clear() {
+    start = Nil
+    exported = false
+    len = 0
+  }
+
+  /** Prepends a single element to this buffer. This operation takes constant
+   *  time.
+   *
+   *  @param x  the element to prepend.
+   *  @return   this buffer.
+   */
+  def +: (x: A): this.type = {
+    if (exported) copy()
+    val newElem = new :: (x, start)
+    if (start.isEmpty) last0 = newElem
+    start = newElem
+    len += 1
+    this
+  }
+
   /** Inserts new elements at the index <code>n</code>. Opposed to method
    *  <code>update</code>, this method will not replace an element with a new
    *  one. Instead, it will insert a new element at index <code>n</code>.
@@ -189,13 +131,14 @@ final class ListBuffer[A] extends Buffer[A] {
    *  @param  iter  the iterable object providing all elements to insert.
    *  @throws Predef.IndexOutOfBoundsException if <code>n</code> is out of bounds.
    */
-  def insertAll(n: Int, iter: Iterable[A]) {
+  def insertAll(n: Int, seq: Traversible[A]) {
     try {
       if (exported) copy()
-      var elems = iter.elements.toList.reverse
+      var elems = seq.toList.reverse
+      len += elems.length
       if (n == 0) {
         while (!elems.isEmpty) {
-          val newElem = new scala.:: (elems.head, start)
+          val newElem = new :: (elems.head, start)
           if (start.isEmpty) last0 = newElem
           start = newElem
           elems = elems.tail
@@ -208,9 +151,9 @@ final class ListBuffer[A] extends Buffer[A] {
           i += 1
         }
         while (!elems.isEmpty) {
-          val newElem = new scala.:: (elems.head, cursor.tail)
+          val newElem = new :: (elems.head, cursor.tail)
           if (cursor.tail.isEmpty) last0 = newElem
-          cursor.asInstanceOf[scala.::[A]].tl = newElem
+          cursor.asInstanceOf[::[A]].tl = newElem
           elems = elems.tail
         }
       }
@@ -220,9 +163,66 @@ final class ListBuffer[A] extends Buffer[A] {
     }
   }
 
-  /** Removes the element on a given index position. Takes time linear in
-   *  the buffer size (except for the first element, which is removed in constant
-   *  time).
+  /** Removes a given number of elements on a given index position. May take time linear in
+   *  the buffer size.
+   *
+   *  @param n         the index which refers to the first element to remove.
+   *  @param count     the number of elements to remove.
+   */
+  override def remove(n: Int, count: Int) {
+    if (exported) copy()
+    val n1 = n max 0
+    val count1 = count min (len - n1)
+    var old = start.head;
+    if (n1 == 0) {
+      var c = count1
+      while (c > 0) {
+        start = start.tail
+        c -= 1
+      }
+    } else {
+      var cursor = start
+      var i = 1
+      while (i < n1) {
+        cursor = cursor.tail
+        i += 1
+      }
+      var c = count1
+      while (c > 0) {
+        if (last0 eq cursor.tail) last0 = cursor.asInstanceOf[::[A]]
+        cursor.asInstanceOf[::[A]].tl = cursor.tail.tail
+        c -= 1
+      }
+    }
+    len -= count1
+  }
+
+// Implementation of abstract method in Builder
+
+  def result: List[A] = toList
+
+  /** Converts this buffer to a list. Takes constant time. The buffer is
+   *  copied lazily, the first time it is mutated.
+   */
+  override def toList: List[A] = {
+    exported = !start.isEmpty
+    start
+  }
+
+// New methods in ListBuffer
+
+  /** Prepends the elements of this buffer to a given list
+   *
+   *  @param xs   the list to which elements are prepended
+   */
+  def prependToList(xs: List[A]): List[A] =
+    if (start.isEmpty) xs
+    else { last0.tl = xs; toList }
+
+// Overrides of methods in Buffer
+
+  /** Removes the element on a given index position. May take time linear in
+   *  the buffer size
    *
    *  @param  n  the index which refers to the element to delete.
    *  @return n  the element that was formerly at position <code>n</code>.
@@ -230,6 +230,7 @@ final class ListBuffer[A] extends Buffer[A] {
    *  @throws Predef.IndexOutOfBoundsException if <code>n</code> is out of bounds.
    */
   def remove(n: Int): A = try {
+    if (n < 0 || n >= len) throw new IndexOutOfBoundsException(n.toString())
     if (exported) copy()
     var old = start.head;
     if (n == 0) {
@@ -242,27 +243,38 @@ final class ListBuffer[A] extends Buffer[A] {
         i += 1
       }
       old = cursor.tail.head
-      if (last0 eq cursor.tail) last0 = cursor.asInstanceOf[scala.::[A]]
-      cursor.asInstanceOf[scala.::[A]].tl = cursor.tail.tail
+      if (last0 eq cursor.tail) last0 = cursor.asInstanceOf[::[A]]
+      cursor.asInstanceOf[::[A]].tl = cursor.tail.tail
     }
+    len -= 1
     old
-  } catch {
-    case ex: Exception =>
-      throw new IndexOutOfBoundsException(n.toString())
   }
 
-  /** <p>
-   *    Returns an iterator over all elements of this list.
-   *  </p>
-   *  <blockquote>
-   *    Note: the iterator can be affected by insertions, updates and
-   *    deletions that are performed afterwards on the buffer. To get
-   *    iterator an over the current buffer snapshot, use
-   *    <code>toList.elements</code>.
-   *  </blockquote>
+  /** Remove a single element from this buffer. May take time linear in the buffer size.
    *
-   *  @throws Predef.NoSuchElementException if buffer is empty
+   *  @param x  the element to remove.
    */
+  override def -= (elem: A) {
+    if (exported) copy()
+    if (start.isEmpty) {}
+    else if (start.head == elem) {
+      start = start.tail
+      len -= 1
+    } else {
+      var cursor = start
+      while (!cursor.tail.isEmpty && cursor.tail.head != elem) {
+        cursor = cursor.tail
+      }
+      if (!cursor.tail.isEmpty) {
+        val z = cursor.asInstanceOf[::[A]]
+        if (z.tl == last0)
+          last0 = z
+        z.tl = cursor.tail.tail
+        len -= 1
+      }
+    }
+  }
+
   override def elements = new Iterator[A] {
     var cursor: List[A] = null
     def hasNext: Boolean = !start.isEmpty && cursor != last0
@@ -275,31 +287,39 @@ final class ListBuffer[A] extends Buffer[A] {
       }
   }
 
+  /** expose the underlying list but do not mark it as exported */
+  def readOnly: List[A] = start
+
+  // Private methods
+
+  /** Copy contents of this buffer */
+  private def copy() {
+    var cursor = start
+    val limit = last0.tail
+    clear
+    while (cursor ne limit) {
+      this += cursor.head
+      cursor = cursor.tail
+    }
+  }
+
   /** Returns a clone of this buffer.
    *
    *  @return a <code>ListBuffer</code> with the same elements.
    */
-  override def clone(): Buffer[A] = (new ListBuffer[A]) ++ this
-
-  /** Checks if two buffers are structurally identical.
-   *
-   *  @return <code>true</code>, iff both buffers contain the same sequence
-   *          of elements.
-   */
-  override def equals(obj: Any): Boolean = obj match {
-    case that: ListBuffer[_] =>
-      (this.length == that.length &&
-       elements.zip(that.elements).forall {
-         case (thiselem, thatelem) => thiselem == thatelem
-       })
-    case _ =>
-      false
-  }
+  override def clone(): ListBuffer[A] = (new ListBuffer[A]) ++ this
 
   /** Defines the prefix of the string representation.
    *
    *  @return the string representation of this buffer.
    */
-  override protected def stringPrefix: String = "ListBuffer"
+  override def stringPrefix: String = "ListBuffer"
+}
+
+/* Factory object for `ListBuffer` class */
+object ListBuffer extends SequenceFactory[ListBuffer] {
+  type Coll = ListBuffer[_]
+  implicit def builderFactory[A]: BuilderFactory[A, ListBuffer[A], Coll] = new BuilderFactory[A, ListBuffer[A], Coll] { def apply(from: Coll) = from.traversibleBuilder[A] }
+  def newBuilder[A]: Builder[A, ListBuffer[A], Any] = new AddingBuilder(new ListBuffer[A])
 }