SI-9347 Efficient head/tail, if possible, for immutable maps & sets

Most immutable collections, including sets and maps, have a better-than-O(n) method for removing an element.  In those cases, tail and possibly head were overridden so the head/tail pattern can be used with less of a performance penalty.

Speed improvements on head/tail pattern are
(for sets/maps of size 1024, unless otherwise specified):

```
BitSet    190x
HashSet   250x
Set       400x
Set2        9x
Set4       12x
HashMap   430x
ListMap  2500x   // size 128
Map       430x
```

Note: `ListMap` is actually `init`/`last` because it's maintained in reverse order.

Altered ListMap docs to explain that reverse traversal is the fast way to do it.

All tested sets/maps that were already fast are still fast.

Test code is reproduced below, except it does ListSet with head/tail which
doesn't show the improvement:

```scala
object BenchTailSetMap {
  val th = new ichi.bench.Thyme

  val standard = 1 to 1024

  val sets = Map[String, Set[Int]](
    "Set" -> (Set.empty[Int] ++ standard),
    "Set4"-> Set(4, 7, 2, 1),
    "Set2"-> Set(3, 4),
    "HashSet" -> (collection.immutable.HashSet.empty[Int] ++ standard),
    "BitSet" -> (collection.immutable.BitSet.empty ++ standard),
    "SortedSet" -> (collection.immutable.SortedSet.empty[Int] ++ standard),
    "ListSet" -> (collection.immutable.ListSet.empty[Int] ++ standard)
  )

  val pairs = standard.map(i => i -> i.toString)

  // ListMap implementation is HORRIBLE, O(n^3) tail!  Cut down size.
  val maps = Map[String, Map[Int, String]](
    "Map" -> (Map.empty[Int, String] ++ pairs),
    "HashMap" -> (collection.immutable.HashMap.empty[Int, String] ++ pairs),
    "SortedMap" -> (collection.immutable.SortedMap.empty[Int, String] ++ pairs),
    "ListMap" -> (collection.immutable.ListMap.empty[Int, String] ++ pairs.take(128))
  )

  def hts(s: Set[Int]) = {
    var si = s
    var x = 0
    while (si.nonEmpty) {
      x += si.head
      si = si.tail
    }
    x
  }

  def htm(m: Map[Int, String]) = {
    var mi = m
    var x = 0
    while (mi.nonEmpty) {
      x += mi.head._2.length
      mi = mi.tail
    }
    x
  }

  def run() {
    sets.toList.sortBy(_._1).foreach{ case (name, s) => th.pbench(hts(s), s.size, name) }
    maps.toList.sortBy(_._1).foreach{ case (name, m) => th.pbench(htm(m), m.size, name) }
  }
}
```

1 files changed, 6 insertions, 1 deletions

diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala
index 07758bf5a2..2d8cc0b386 100644
--- a/src/library/scala/collection/immutable/HashSet.scala
+++ b/src/library/scala/collection/immutable/HashSet.scala
@@ -162,6 +162,8 @@ class HashSet[A] extends AbstractSet[A]
   def - (e: A): HashSet[A] =
     nullToEmpty(removed0(e, computeHash(e), 0))
 
+  override def tail: HashSet[A] = this - head
+
   override def filter(p: A => Boolean) = {
     val buffer = new Array[HashSet[A]](bufferSize(size))
     nullToEmpty(filter0(p, false, 0, buffer, 0))
@@ -213,7 +215,10 @@ object HashSet extends ImmutableSetFactory[HashSet] {
   /** $setCanBuildFromInfo */
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, HashSet[A]] = setCanBuildFrom[A]
 
-  private object EmptyHashSet extends HashSet[Any] { }
+  private object EmptyHashSet extends HashSet[Any] {
+    override def head: Any = throw new NoSuchElementException("Empty Set")
+    override def tail: HashSet[Any] = throw new NoSuchElementException("Empty Set")
+  }
   private[collection] def emptyInstance: HashSet[Any] = EmptyHashSet
 
   // utility method to create a HashTrieSet from two leaf HashSets (HashSet1 or HashSetCollision1) with non-colliding hash code)