Updated documentation with complexity informati...

Updated documentation with complexity information on buffer
implementations.

2 files changed, 31 insertions, 16 deletions

diff --git a/src/library/scala/collection/mutable/ArrayBuffer.scala b/src/library/scala/collection/mutable/ArrayBuffer.scala
index 0a4856fcd2..6ec54577c3 100644
--- a/src/library/scala/collection/mutable/ArrayBuffer.scala
+++ b/src/library/scala/collection/mutable/ArrayBuffer.scala
@@ -15,7 +15,9 @@ package scala.collection.mutable
 import Predef._
 
 /** An implementation of the <code>Buffer</code> class using an array to
- *  represent the assembled sequence internally.
+ *  represent the assembled sequence internally. Append, update and random
+ *  access take constant time (amortized time). Prepends and removes are
+ *  linear in the buffer size.
  *
  *  @author  Matthias Zenger
  *  @version 1.0, 15/03/2004
@@ -23,7 +25,7 @@ import Predef._
 @serializable
 class ArrayBuffer[A] extends RandomAccessSeq.Mutable[A] with Buffer[A] with ResizableArray[A] {
   /** Appends a single element to this buffer and returns
-   *  the identity of the buffer.
+   *  the identity of the buffer. It takes constant time.
    *
    *  @param elem  the element to append.
    */
@@ -62,7 +64,8 @@ class ArrayBuffer[A] extends RandomAccessSeq.Mutable[A] with Buffer[A] with Resi
   }
 
   /** Prepends a single element to this buffer and return
-   *  the identity of the buffer.
+   *  the identity of the buffer. It takes time linear in
+   *  the buffer size.
    *
    *  @param elem  the element to append.
    *  @return      the updated buffer.
@@ -75,7 +78,7 @@ class ArrayBuffer[A] extends RandomAccessSeq.Mutable[A] with Buffer[A] with Resi
     this
   }
 
-  /** Returns the i-th element of this ArrayBuffer.
+  /** Returns the i-th element of this ArrayBuffer. It takes constant time.
    *
    *  @param i  the specified index.
    *  @return   the i-th element.
@@ -117,7 +120,7 @@ class ArrayBuffer[A] extends RandomAccessSeq.Mutable[A] with Buffer[A] with Resi
   }
 
   /** Replace element at index <code>n</code> with the new element
-   *  <code>newelem</code>.
+   *  <code>newelem</code>. It takes constant time.
    *
    *  @param n       the index of the element to replace.
    *  @param newelem the new element.
@@ -133,7 +136,8 @@ class ArrayBuffer[A] extends RandomAccessSeq.Mutable[A] with Buffer[A] with Resi
     }
   }
 
-  /** Removes the element on a given index position.
+  /** Removes the element on a given index position. It takes time linear in
+   *  the buffer size.
    *
    *  @param n  the index which refers to the element to delete.
    *  @return   the updated array buffer.
diff --git a/src/library/scala/collection/mutable/ListBuffer.scala b/src/library/scala/collection/mutable/ListBuffer.scala
index fb230966e0..13a3ca65f2 100644
--- a/src/library/scala/collection/mutable/ListBuffer.scala
+++ b/src/library/scala/collection/mutable/ListBuffer.scala
@@ -14,7 +14,8 @@ package scala.collection.mutable
 
 import Predef._
 
-/** The class <code>ListBuffer</code> ..
+/** 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
@@ -25,7 +26,8 @@ final class ListBuffer[A] extends Buffer[A] {
   private var last0: ::[A] = _
   private var exported: Boolean = false
 
-  /** Prepends a single element to this buffer.
+  /** Prepends a single element to this buffer. It takes constant
+   *  time.
    *
    *  @param x  the element to prepend.
    *  @return   this buffer.
@@ -40,7 +42,8 @@ final class ListBuffer[A] extends Buffer[A] {
 
 
 
-  /** Appends a single element to this buffer.
+  /** Appends a single element to this buffer. It takes constant
+   *  time.
    *
    *  @param x  the element to append.
    */
@@ -57,14 +60,17 @@ final class ListBuffer[A] extends Buffer[A] {
   }
 
   /** Removes a single element from the buffer and return
-   *  the identity of the buffer. Same as <code>this -= x; this</code>
+   *  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.
+  /** 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.
    */
@@ -84,7 +90,8 @@ final class ListBuffer[A] extends Buffer[A] {
     }
   }
 
-  /** Converts this buffer to a list
+  /** 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
@@ -119,7 +126,7 @@ final class ListBuffer[A] extends Buffer[A] {
     }
   }
 
-  /** Returns the length of this buffer.
+  /** Returns the length of this buffer. It takes linear time.
    *
    *  @return the length of this buffer.
    */
@@ -129,7 +136,8 @@ final class ListBuffer[A] extends Buffer[A] {
   override def isEmpty = start.isEmpty
 
   /** Returns the n-th element of this list. This method
-   *  yields an error if the element does not exist.
+   *  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.
@@ -143,7 +151,8 @@ final class ListBuffer[A] extends Buffer[A] {
   }
 
   /** Replaces element at index <code>n</code> with the new element
-   *  <code>newelem</code>.
+   *  <code>newelem</code>. Takes time linear in the buffer size. (except the first
+   *  element, which is updated in constant time).
    *
    *  @param n  the index of the element to replace.
    *  @param x  the new element.
@@ -211,7 +220,9 @@ final class ListBuffer[A] extends Buffer[A] {
     }
   }
 
-  /** Removes the element on a given index position.
+  /** 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).
    *
    *  @param  n  the index which refers to the element to delete.
    *  @return n  the element that was formerly at position <code>n</code>.