1 files changed, 30 insertions, 1 deletions
diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala
index 70543aa3a6..6bb1f116fe 100644
--- a/src/library/scala/collection/immutable/BitSet.scala
+++ b/src/library/scala/collection/immutable/BitSet.scala
@@ -14,7 +14,7 @@ package immutable
 
 import generic._
 import BitSetLike.{LogWL, updateArray}
-import mutable.{ Builder, SetBuilder }
+import mutable.Builder
 
 /** A class for immutable bitsets.
  *  $bitsetinfo
@@ -103,6 +103,7 @@ object BitSet extends BitSetFactory[BitSet] {
     else new BitSetN(elems)
   }
 
+  @SerialVersionUID(2260107458435649300L)
   class BitSet1(val elems: Long) extends BitSet {
     protected def nwords = 1
     protected def word(idx: Int) = if (idx == 0) elems else 0L
@@ -110,6 +111,12 @@ object BitSet extends BitSetFactory[BitSet] {
       if (idx == 0) new BitSet1(w)
       else if (idx == 1) new BitSet2(elems, w)
       else fromBitMaskNoCopy(updateArray(Array(elems), idx, w))
+    override def head: Int =
+      if (elems == 0L) throw new NoSuchElementException("Empty BitSet")
+      else java.lang.Long.numberOfTrailingZeros(elems)
+    override def tail: BitSet =
+      if (elems == 0L) throw new NoSuchElementException("Empty BitSet")
+      else new BitSet1(elems - java.lang.Long.lowestOneBit(elems))
   }
 
   class BitSet2(val elems0: Long, elems1: Long) extends BitSet {
@@ -119,6 +126,18 @@ object BitSet extends BitSetFactory[BitSet] {
       if (idx == 0) new BitSet2(w, elems1)
       else if (idx == 1) new BitSet2(elems0, w)
       else fromBitMaskNoCopy(updateArray(Array(elems0, elems1), idx, w))
+    override def head: Int =
+      if (elems0 == 0L) {
+        if (elems1 == 0) throw new NoSuchElementException("Empty BitSet")
+        64 + java.lang.Long.numberOfTrailingZeros(elems1)
+      }
+      else java.lang.Long.numberOfTrailingZeros(elems0)
+    override def tail: BitSet =
+      if (elems0 == 0L) {
+        if (elems1 == 0L) throw new NoSuchElementException("Empty BitSet")
+        new BitSet2(elems0, elems1 - java.lang.Long.lowestOneBit(elems1))
+      }
+      else new BitSet2(elems0 - java.lang.Long.lowestOneBit(elems0), elems1)
   }
 
   /** The implementing class for bit sets with elements >= 128 (exceeding
@@ -131,5 +150,15 @@ object BitSet extends BitSetFactory[BitSet] {
     protected def nwords = elems.length
     protected def word(idx: Int) = if (idx < nwords) elems(idx) else 0L
     protected def updateWord(idx: Int, w: Long): BitSet = fromBitMaskNoCopy(updateArray(elems, idx, w))
+    override def tail: BitSet = {
+      val n = nwords
+      var i = 0
+      while (i < n) {
+        val wi = word(i)
+        if (wi != 0L) return fromBitMaskNoCopy(updateArray(elems, i, wi - java.lang.Long.lowestOneBit(wi)))
+        i += 1
+      }
+      throw new NoSuchElementException("Empty BitSet")
+    }
   }
 }