Optimized implementation of init/tail for TreeSet/TreeMap.

2 files changed, 6 insertions, 0 deletions

diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index be67a45b1e..0e160ca50e 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -82,6 +82,9 @@ class TreeMap[A, +B](override val size: Int, t: RedBlack[A]#Tree[B])(implicit va
   }
   override def lastOption = if (t.isEmpty) None else Some(last)
 
+  override def tail = new TreeMap(size - 1, tree.delete(firstKey))
+  override def init = new TreeMap(size - 1, tree.delete(lastKey))
+
   /** A factory to create empty maps of the same type of keys.
    */
   override def empty: TreeMap[A, B] = TreeMap.empty[A, B](ordering)
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index 85f4ae4b0e..b969ecc0e8 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -58,6 +58,9 @@ class TreeSet[A](override val size: Int, t: RedBlack[A]#Tree[Unit])
   override def last = t.greatest.key
   override def lastOption = if (t.isEmpty) None else Some(last)
 
+  override def tail = new TreeSet(size - 1, tree.delete(firstKey))
+  override def init = new TreeSet(size - 1, tree.delete(lastKey))
+
   def isSmaller(x: A, y: A) = compare(x,y) < 0
 
   def this()(implicit ordering: Ordering[A]) = this(0, null)(ordering)