diff options
author | Heather Miller <heather.miller@epfl.ch> | 2011-08-21 00:29:10 +0000 |
---|---|---|
committer | Heather Miller <heather.miller@epfl.ch> | 2011-08-21 00:29:10 +0000 |
commit | cecee085f345097055737f318e0ef30a02b7ac96 (patch) | |
tree | 39982ef201b646dee617a5b254f73aaf9d5d0c6d /src/library/scala/collection/immutable/Queue.scala | |
parent | 7e99a7d380d7a6331e456ab032a5994d268d37fc (diff) | |
download | scala-cecee085f345097055737f318e0ef30a02b7ac96.tar.gz scala-cecee085f345097055737f318e0ef30a02b7ac96.tar.bz2 scala-cecee085f345097055737f318e0ef30a02b7ac96.zip |
Improved documentation for scala.collection.imm...
Improved documentation for scala.collection.immutable.List and
scala.collection.immutable.Queue. Contributed by Matthew Pocock during
the Monthly Docspree. Review by phaller.
Diffstat (limited to 'src/library/scala/collection/immutable/Queue.scala')
-rw-r--r-- | src/library/scala/collection/immutable/Queue.scala | 9 |
1 files changed, 9 insertions, 0 deletions
diff --git a/src/library/scala/collection/immutable/Queue.scala b/src/library/scala/collection/immutable/Queue.scala index 892f75ae91..813497f994 100644 --- a/src/library/scala/collection/immutable/Queue.scala +++ b/src/library/scala/collection/immutable/Queue.scala @@ -16,6 +16,14 @@ import annotation.tailrec /** `Queue` objects implement data structures that allow to * insert and retrieve elements in a first-in-first-out (FIFO) manner. * + * `Queue` is implemented as a pair of `List`s, one containing the ''in'' elements and the other the ''out'' elements. + * Elements are added to the ''in'' list and removed from the ''out'' list. When the ''out'' list runs dry, the + * queue is pivoted by replacing the ''out'' list by ''in.reverse'', and ''in'' by ''Nil''. + * + * Adding items to the queue always has cost `O(1)`. Removing items has cost `O(1)`, except in the case + * where a pivot is required, in which case, a cost of `O(n)` is incurred, where `n` is the number of elements in the queue. When this happens, + * `n` remove operations with `O(1)` cost are guaranteed. Removing an item is on average `O(1)`. + * * @author Erik Stenman * @version 1.0, 08/07/2003 * @since 1 @@ -24,6 +32,7 @@ import annotation.tailrec * @define mayNotTerminateInf * @define willNotTerminateInf */ + @SerialVersionUID(-7622936493364270175L) class Queue[+A] protected(protected val in: List[A], protected val out: List[A]) extends LinearSeq[A] |