diff options
author | Iulian Dragos <jaguarul@gmail.com> | 2008-03-13 11:39:05 +0000 |
---|---|---|
committer | Iulian Dragos <jaguarul@gmail.com> | 2008-03-13 11:39:05 +0000 |
commit | d0a90c7c4a11fac5beb186567a09c85aef1485bd (patch) | |
tree | 51bd514dd3c94d685653cbc0d05cfc3182638a24 | |
parent | 10b30e9d2246dd9e2c3664c72438f234443bf8a4 (diff) | |
download | scala-d0a90c7c4a11fac5beb186567a09c85aef1485bd.tar.gz scala-d0a90c7c4a11fac5beb186567a09c85aef1485bd.tar.bz2 scala-d0a90c7c4a11fac5beb186567a09c85aef1485bd.zip |
Updated documentation with complexity informati...
Updated documentation with complexity information on buffer
implementations.
-rw-r--r-- | src/library/scala/collection/mutable/ArrayBuffer.scala | 16 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/ListBuffer.scala | 31 |
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>. |