diff options
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/BitSet.scala | 2 | ||||
-rw-r--r-- | src/library/scala/collection/BitSetLike.scala | 53 | ||||
-rw-r--r-- | src/library/scala/collection/SortedSet.scala | 4 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/BitSet.scala | 49 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/SortedSet.scala | 4 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/BitSet.scala | 19 | ||||
-rw-r--r-- | src/library/scala/reflect/api/Trees.scala | 2 |
7 files changed, 113 insertions, 20 deletions
diff --git a/src/library/scala/collection/BitSet.scala b/src/library/scala/collection/BitSet.scala index 2f411f976f..59b53faf7e 100644 --- a/src/library/scala/collection/BitSet.scala +++ b/src/library/scala/collection/BitSet.scala @@ -15,7 +15,7 @@ import generic._ /** A common base class for mutable and immutable bitsets. * $bitsetinfo */ -trait BitSet extends Set[Int] +trait BitSet extends SortedSet[Int] with BitSetLike[BitSet] { override def empty: BitSet = BitSet.empty } diff --git a/src/library/scala/collection/BitSetLike.scala b/src/library/scala/collection/BitSetLike.scala index b96e8f6a91..7d9f48f299 100644 --- a/src/library/scala/collection/BitSetLike.scala +++ b/src/library/scala/collection/BitSetLike.scala @@ -32,7 +32,7 @@ import mutable.StringBuilder * @define coll bitset * @define Coll BitSet */ -trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, This] { self => +trait BitSetLike[+This <: BitSetLike[This] with SortedSet[Int]] extends SortedSetLike[Int, This] { self => def empty: This @@ -46,7 +46,19 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T /** Creates a new set of this kind from an array of longs */ - protected def fromArray(elems: Array[Long]): This + protected def fromBitMaskNoCopy(elems: Array[Long]): This + + /** Creates a bit mask for this set as a new array of longs + */ + def toBitMask: Array[Long] = { + val a = new Array[Long](nwords) + var i = a.length + while(i > 0) { + i -= 1 + a(i) = word(i) + } + a + } override def size: Int = { var s = 0 @@ -58,6 +70,35 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T s } + implicit def ordering: Ordering[Int] = Ordering.Int + + def rangeImpl(from: Option[Int], until: Option[Int]): This = { + val a = toBitMask + val len = a.length + if(from.isDefined) { + var f = from.get + var pos = 0 + while(f >= 64 && pos < len) { + f -= 64 + a(pos) = 0 + pos += 1 + } + if(f > 0 && pos < len) a(pos) &= ~((1L << f)-1) + } + if(until.isDefined) { + val u = until.get + val w = u / 64 + val b = u % 64 + var clearw = w+1 + while(clearw < len) { + a(clearw) = 0 + clearw += 1 + } + if(w < len) a(w) &= (1L << b)-1 + } + fromBitMaskNoCopy(a) + } + def iterator: Iterator[Int] = new AbstractIterator[Int] { private var current = 0 private val end = nwords * WordLength @@ -91,7 +132,7 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T val words = new Array[Long](len) for (idx <- 0 until len) words(idx) = this.word(idx) | other.word(idx) - fromArray(words) + fromBitMaskNoCopy(words) } /** Computes the intersection between this bitset and another bitset by performing @@ -105,7 +146,7 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T val words = new Array[Long](len) for (idx <- 0 until len) words(idx) = this.word(idx) & other.word(idx) - fromArray(words) + fromBitMaskNoCopy(words) } /** Computes the difference of this bitset and another bitset by performing @@ -120,7 +161,7 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T val words = new Array[Long](len) for (idx <- 0 until len) words(idx) = this.word(idx) & ~other.word(idx) - fromArray(words) + fromBitMaskNoCopy(words) } /** Computes the symmetric difference of this bitset and another bitset by performing @@ -135,7 +176,7 @@ trait BitSetLike[+This <: BitSetLike[This] with Set[Int]] extends SetLike[Int, T val words = new Array[Long](len) for (idx <- 0 until len) words(idx) = this.word(idx) ^ other.word(idx) - fromArray(words) + fromBitMaskNoCopy(words) } def contains(elem: Int): Boolean = diff --git a/src/library/scala/collection/SortedSet.scala b/src/library/scala/collection/SortedSet.scala index a1d1cd3fc3..f29b6d8aa3 100644 --- a/src/library/scala/collection/SortedSet.scala +++ b/src/library/scala/collection/SortedSet.scala @@ -27,5 +27,7 @@ trait SortedSet[A] extends Set[A] with SortedSetLike[A, SortedSet[A]] { */ object SortedSet extends SortedSetFactory[SortedSet] { def empty[A](implicit ord: Ordering[A]): immutable.SortedSet[A] = immutable.SortedSet.empty[A](ord) - implicit def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, SortedSet[A]] = new SortedSetCanBuildFrom[A] + def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, SortedSet[A]] = newCanBuildFrom[A] + // Force a declaration here so that BitSet's (which does not inherit from SortedSetFactory) can be more specific + override implicit def newCanBuildFrom[A](implicit ord : Ordering[A]) : CanBuildFrom[Coll, A, SortedSet[A]] = super.newCanBuildFrom } diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala index 36aa087dd0..ce4d688707 100644 --- a/src/library/scala/collection/immutable/BitSet.scala +++ b/src/library/scala/collection/immutable/BitSet.scala @@ -22,13 +22,16 @@ import mutable.{ Builder, SetBuilder } */ @SerialVersionUID(1611436763290191562L) abstract class BitSet extends scala.collection.AbstractSet[Int] - with Set[Int] + with SortedSet[Int] with scala.collection.BitSet with BitSetLike[BitSet] with Serializable { override def empty = BitSet.empty - def fromArray(elems: Array[Long]): BitSet = BitSet.fromArray(elems) + @deprecated("Use BitSet.fromBitMask[NoCopy] instead of fromArray", "2.10") + def fromArray(elems: Array[Long]): BitSet = fromBitMaskNoCopy(elems) + + protected def fromBitMaskNoCopy(elems: Array[Long]): BitSet = BitSet.fromBitMaskNoCopy(elems) /** Update word at index `idx`; enlarge set if `idx` outside range of set. */ @@ -64,14 +67,38 @@ object BitSet extends BitSetFactory[BitSet] { /** The empty bitset */ val empty: BitSet = new BitSet1(0L) - /** An adding builder for immutable Sets. */ - def newBuilder: Builder[Int, BitSet] = new SetBuilder[Int, BitSet](empty) + /** A builder that takes advantage of mutable BitSets. */ + def newBuilder: Builder[Int, BitSet] = new Builder[Int, BitSet] { + private[this] val b = new mutable.BitSet + def += (x: Int) = { b += x; this } + def clear() = b.clear + def result() = b.toImmutable + } /** $bitsetCanBuildFrom */ implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom /** A bitset containing all the bits in an array */ - def fromArray(elems: Array[Long]): BitSet = { + @deprecated("Use fromBitMask[NoCopy] instead of fromArray", "2.10") + def fromArray(elems: Array[Long]): BitSet = fromBitMaskNoCopy(elems) + + /** A bitset containing all the bits in an array */ + def fromBitMask(elems: Array[Long]): BitSet = { + val len = elems.length + if (len == 0) empty + else if (len == 1) new BitSet1(elems(0)) + else if (len == 2) new BitSet2(elems(0), elems(1)) + else { + val a = new Array[Long](len) + Array.copy(elems, 0, a, 0, len) + new BitSetN(a) + } + } + + /** A bitset containing all the bits in an array, wrapping the existing + * array without copying. + */ + def fromBitMaskNoCopy(elems: Array[Long]): BitSet = { val len = elems.length if (len == 0) empty else if (len == 1) new BitSet1(elems(0)) @@ -85,7 +112,7 @@ object BitSet extends BitSetFactory[BitSet] { protected def updateWord(idx: Int, w: Long): BitSet = if (idx == 0) new BitSet1(w) else if (idx == 1) new BitSet2(elems, w) - else fromArray(updateArray(Array(elems), idx, w)) + else fromBitMaskNoCopy(updateArray(Array(elems), idx, w)) } class BitSet2(val elems0: Long, elems1: Long) extends BitSet { @@ -94,12 +121,18 @@ object BitSet extends BitSetFactory[BitSet] { protected def updateWord(idx: Int, w: Long): BitSet = if (idx == 0) new BitSet2(w, elems1) else if (idx == 1) new BitSet2(elems0, w) - else fromArray(updateArray(Array(elems0, elems1), idx, w)) + else fromBitMaskNoCopy(updateArray(Array(elems0, elems1), idx, w)) } + /** The implementing class for bit sets with elements >= 128 (exceeding + * the capacity of two long values). The constructor wraps an existing + * bit mask without copying, thus exposing a mutable part of the internal + * implementation. Care needs to be taken not to modify the exposed + * array. + */ class BitSetN(val elems: Array[Long]) extends 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 = fromArray(updateArray(elems, idx, w)) + protected def updateWord(idx: Int, w: Long): BitSet = fromBitMaskNoCopy(updateArray(elems, idx, w)) } } diff --git a/src/library/scala/collection/immutable/SortedSet.scala b/src/library/scala/collection/immutable/SortedSet.scala index 50cd5445b9..e1637ce78b 100644 --- a/src/library/scala/collection/immutable/SortedSet.scala +++ b/src/library/scala/collection/immutable/SortedSet.scala @@ -35,6 +35,8 @@ trait SortedSet[A] extends Set[A] with scala.collection.SortedSet[A] with Sorted */ object SortedSet extends ImmutableSortedSetFactory[SortedSet] { /** $sortedSetCanBuildFromInfo */ - implicit def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, SortedSet[A]] = new SortedSetCanBuildFrom[A] + def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, SortedSet[A]] = newCanBuildFrom[A] def empty[A](implicit ord: Ordering[A]): SortedSet[A] = TreeSet.empty[A] + // Force a declaration here so that BitSet's (which does not inherit from SortedSetFactory) can be more specific + override implicit def newCanBuildFrom[A](implicit ord : Ordering[A]) : CanBuildFrom[Coll, A, SortedSet[A]] = super.newCanBuildFrom } diff --git a/src/library/scala/collection/mutable/BitSet.scala b/src/library/scala/collection/mutable/BitSet.scala index 0cff9f970f..9dce3ff9e2 100644 --- a/src/library/scala/collection/mutable/BitSet.scala +++ b/src/library/scala/collection/mutable/BitSet.scala @@ -34,7 +34,7 @@ import BitSetLike.{LogWL, updateArray} */ @SerialVersionUID(8483111450368547763L) class BitSet(protected var elems: Array[Long]) extends AbstractSet[Int] - with Set[Int] + with SortedSet[Int] with scala.collection.BitSet with BitSetLike[BitSet] with SetLike[Int, BitSet] @@ -65,7 +65,7 @@ class BitSet(protected var elems: Array[Long]) extends AbstractSet[Int] elems(idx) = w } - protected def fromArray(words: Array[Long]): BitSet = new BitSet(words) + protected def fromBitMaskNoCopy(words: Array[Long]): BitSet = new BitSet(words) override def add(elem: Int): Boolean = { require(elem >= 0) @@ -100,7 +100,7 @@ class BitSet(protected var elems: Array[Long]) extends AbstractSet[Int] * * @return an immutable set containing all the elements of this set. */ - def toImmutable = immutable.BitSet.fromArray(elems) + def toImmutable = immutable.BitSet.fromBitMaskNoCopy(elems) override def clone(): BitSet = { val elems1 = new Array[Long](elems.length) @@ -121,4 +121,17 @@ object BitSet extends BitSetFactory[BitSet] { /** $bitsetCanBuildFrom */ implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet] = bitsetCanBuildFrom + + /** A bitset containing all the bits in an array */ + def fromBitMask(elems: Array[Long]): BitSet = { + val len = elems.length + val a = new Array[Long](len) + Array.copy(elems, 0, a, 0, len) + new BitSet(a) + } + + /** A bitset containing all the bits in an array, wrapping the existing + * array without copying. + */ + def fromBitMaskNoCopy(elems: Array[Long]): BitSet = new BitSet(elems) } diff --git a/src/library/scala/reflect/api/Trees.scala b/src/library/scala/reflect/api/Trees.scala index 20f20890e8..752319d9a4 100644 --- a/src/library/scala/reflect/api/Trees.scala +++ b/src/library/scala/reflect/api/Trees.scala @@ -624,6 +624,8 @@ trait Trees /*extends reflect.generic.Trees*/ { self: Universe => } def TypeTree(tp: Type): TypeTree = TypeTree() setType tp + + def emptyValDef: ValDef // ------ traversers, copiers, and transformers --------------------------------------------- |