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.

2 files changed, 41 insertions, 0 deletions

diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index 5791e9788d..fb7808bc41 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -22,6 +22,38 @@ import annotation.tailrec
  *  and `scala.::` that implement the abstract members `isEmpty`,
  *  `head` and `tail`.
  *
+ *  This class is optimal for last-in-first-out (LIFO), stack-like access patterns. If you need another access
+ *  pattern, for example, random access or FIFO, consider using a collection more suited to this than `List`.
+ *
+ *  @example {{{
+ *  // Make a list via the companion object factory
+ *  val days = List("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday")
+ *
+ *  // Make a list element-by-element
+ *  val when = "AM" :: "PM" :: List()
+ *
+ *  // Pattern match
+ *  days match {
+ *    case firstDay :: otherDays =>
+ *      println("The first day of the week is: " + firstDay)
+ *    case List() =>
+ *      println("There don't seem to be any week days.")
+ *  }
+ *  }}}
+ *
+ *  ==Performance==
+ *  '''Time:''' `List` has `O(1)` prepend and head/tail access. Most other operations are `O(n)` on the number of elements in the list.
+ *  This includes the index-based lookup of elements, `length`, `append` and `reverse`.
+ *
+ *  '''Space:''' `List` implements '''structural sharing''' of the tail list. This means that many operations are either
+ *  zero- or constant-memory cost.
+ *  {{{
+ *  val mainList = List(3, 2, 1)
+ *  val with4 =    4 :: mainList  // re-uses mainList, costs one :: instance
+ *  val with42 =   42 :: mainList // also re-uses mainList, cost one :: instance
+ *  val shorter =  mainList.tail  // costs nothing as it uses the same 2::1::Nil instances as mainList
+ *  }}}
+ *
  *  @author  Martin Odersky and others
  *  @version 2.8
  *  @since   1.0
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]