diff options
author | Geoffrey Washburn <geoffrey.washburn@epfl.ch> | 2008-08-05 09:44:36 +0000 |
---|---|---|
committer | Geoffrey Washburn <geoffrey.washburn@epfl.ch> | 2008-08-05 09:44:36 +0000 |
commit | 6e159702e1e2b12e30ca014441591b7be03e8f19 (patch) | |
tree | 0dde01fbec52c8d3b7334b34b66dae8ce6f17574 | |
parent | 2e5ad2767011cb24e4145a940842cd04eeb38e4e (diff) | |
download | scala-6e159702e1e2b12e30ca014441591b7be03e8f19.tar.gz scala-6e159702e1e2b12e30ca014441591b7be03e8f19.tar.bz2 scala-6e159702e1e2b12e30ca014441591b7be03e8f19.zip |
Added David's additional collections.
-rw-r--r-- | src/library/scala/collection/immutable/IntMap.scala | 360 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/LongMap.scala | 360 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/TreeHashMap.scala | 270 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/ArrayStack.scala | 155 |
4 files changed, 1145 insertions, 0 deletions
diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala new file mode 100644 index 0000000000..71b10610a3 --- /dev/null +++ b/src/library/scala/collection/immutable/IntMap.scala @@ -0,0 +1,360 @@ +package scala.collection.immutable; + +private[immutable] object IntMapUtils{ + def zero(i : Int, mask : Int) = (i & mask) == 0; + def mask(i : Int, mask : Int) = i & (complement(mask - 1) ^ mask) + def hasMatch(key : Int, prefix : Int, m : Int) = mask(key, m) == prefix; + def unsignedCompare(i : Int, j : Int) = (i < j) ^ (i < 0) ^ (j < 0) + def shorter(m1 : Int, m2 : Int) = unsignedCompare(m2, m1) + def complement(i : Int) = (-1) ^ i; + def branchMask(i : Int, j : Int) = java.lang.Integer.highestOneBit(i ^ j); + + def join[T](p1 : Int, t1 : IntMap[T], p2 : Int, t2 : IntMap[T]) : IntMap[T] = { + val m = branchMask(p1, p2); + val p = mask(p1, m); + if (zero(p1, m)) IntMap.Bin(p, m, t1, t2) + else IntMap.Bin(p, m, t2, t1); + } + + def bin[T](prefix : Int, mask : Int, left : IntMap[T], right : IntMap[T]) : IntMap[T] = (left, right) match { + case (left, IntMap.Nil) => left; + case (IntMap.Nil, right) => right; + case (left, right) => IntMap.Bin(prefix, mask, left, right); + } +} + +import IntMapUtils._ + +object IntMap{ + def empty[T] : IntMap[T] = IntMap.Nil; + def singleton[T](key : Int, value : T) : IntMap[T] = IntMap.Tip(key, value); + def apply[T](elems : (Int, T)*) : IntMap[T] = + elems.foldLeft(empty[T])((x, y) => x.update(y._1, y._2)); + + + private[immutable] case object Nil extends IntMap[Nothing]{ + override def equals(that : Any) = this eq that.asInstanceOf[AnyRef] + }; + private[immutable] case class Tip[+T](key : Int, value : T) extends IntMap[T]{ + def withValue[S](s : S) = + if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[IntMap.Tip[S]]; + else IntMap.Tip(key, s); + } + private[immutable] case class Bin[+T](prefix : Int, mask : Int, left : IntMap[T], right : IntMap[T]) extends IntMap[T]{ + def bin[S](left : IntMap[S], right : IntMap[S]) : IntMap[S] = { + if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[IntMap.Bin[S]]; + else IntMap.Bin[S](prefix, mask, left, right); + } + } + +} + +import IntMap._ + +// Iterator over a non-empty IntMap. +private[immutable] abstract class IntMapIterator[V, T](it : IntMap[V]) extends Iterator[T]{ + + // Basically this uses a simple stack to emulate conversion over the tree. However + // because we know that Ints are at least 32 bits we can have at most 32 IntMap.Bins and + // one IntMap.Tip sitting on the tree at any point. Therefore we know the maximum stack + // depth is 33 and + var index = 0; + var buffer = new Array[AnyRef](33); + + def pop = { + index -= 1; + buffer(index).asInstanceOf[IntMap[V]]; + } + + def push(x : IntMap[V]) { + buffer(index) = x.asInstanceOf[AnyRef]; + index += 1; + } + push(it); + + /** + * What value do we assign to a tip? + */ + def valueOf(tip : IntMap.Tip[V]) : T; + + def hasNext = index != 0; + final def next : T = + pop match { + case IntMap.Bin(_,_, t@IntMap.Tip(_, _), right) => { + push(right); + valueOf(t); + } + case IntMap.Bin(_, _, left, right) => { + push(right); + push(left); + next; + } + case t@IntMap.Tip(_, _) => valueOf(t); + // This should never happen. We don't allow IntMap.Nil in subtrees of the IntMap + // and don't return an IntMapIterator for IntMap.Nil. + case IntMap.Nil => error("Empty maps not allowed as subtrees"); + } +} + +private[immutable] class IntMapEntryIterator[V](it : IntMap[V]) extends IntMapIterator[V, (Int, V)](it){ + def valueOf(tip : IntMap.Tip[V]) = (tip.key, tip.value); +} + +private[immutable] class IntMapValueIterator[V](it : IntMap[V]) extends IntMapIterator[V, V](it){ + def valueOf(tip : IntMap.Tip[V]) = tip.value; +} + +private[immutable] class IntMapKeyIterator[V](it : IntMap[V]) extends IntMapIterator[V, Int](it){ + def valueOf(tip : IntMap.Tip[V]) = tip.key; +} + +import IntMap._; + +/** + * Specialised immutable map structure for integer keys, based on + * <a href="http://citeseer.ist.psu.edu/okasaki98fast.html">Fast Mergeable Integer Maps</a> + * by Okasaki and Gill. Essentially a trie based on binary digits of the the integers. + */ +sealed abstract class IntMap[+T] extends scala.collection.immutable.Map[Int, T]{ + def empty[S] : IntMap[S] = IntMap.Nil; + + override def toList = { + val buffer = new scala.collection.mutable.ListBuffer[(Int, T)]; + foreach(buffer += _); + buffer.toList; + } + + /** + * Iterator over key, value pairs of the map in unsigned order of the keys. + */ + def elements : Iterator[(Int, T)] = this match { + case IntMap.Nil => Iterator.empty; + case _ => new IntMapEntryIterator(this); + } + + /** + * Loops over the key, value pairs of the map in unsigned order of the keys. + */ + override final def foreach(f : ((Int, T)) => Unit) : Unit = this match { + case IntMap.Bin(_, _, left, right) => {left.foreach(f); right.foreach(f); } + case IntMap.Tip(key, value) => f((key, value)); + case IntMap.Nil => {}; + } + + override def keys : Iterator[Int] = this match { + case IntMap.Nil => Iterator.empty; + case _ => new IntMapKeyIterator(this); + } + + /** + * Loop over the keys of the map. The same as keys.foreach(f), but may + * be more efficient. + * + * @param f The loop body + */ + final def foreachKey(f : Int => Unit) : Unit = this match { + case IntMap.Bin(_, _, left, right) => {left.foreachKey(f); right.foreachKey(f); } + case IntMap.Tip(key, _) => f(key); + case IntMap.Nil => {} + } + + override def values : Iterator[T] = this match { + case IntMap.Nil => Iterator.empty; + case _ => new IntMapValueIterator(this); + } + + /** + * Loop over the keys of the map. The same as keys.foreach(f), but may + * be more efficient. + * + * @param f The loop body + */ + final def foreachValue(f : T => Unit) : Unit = this match { + case IntMap.Bin(_, _, left, right) => {left.foreachValue(f); right.foreachValue(f); } + case IntMap.Tip(_, value) => f(value); + case IntMap.Nil => {}; + } + + override def stringPrefix = "IntMap" + + override def isEmpty = this == IntMap.Nil; + + override def filter(f : ((Int, T)) => Boolean) : IntMap[T] = this match { + case IntMap.Bin(prefix, mask, left, right) => { + val (newleft, newright) = (left.filter(f), right.filter(f)); + if ((left eq newleft) && (right eq newright)) this; + else bin(prefix, mask, newleft, newright); + } + case IntMap.Tip(key, value) => + if (f((key, value))) this + else IntMap.Nil; + case IntMap.Nil => IntMap.Nil; + } + + override def transform[S](f : (Int, T) => S) : IntMap[S] = this match { + case b@IntMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f)); + case t@IntMap.Tip(key, value) => t.withValue(f(key, value)); + case IntMap.Nil => IntMap.Nil; + } + + final def size : Int = this match { + case IntMap.Nil => 0; + case IntMap.Tip(_, _) => 1; + case IntMap.Bin(_, _, left, right) => left.size + right.size; + } + + final def get(key : Int) : Option[T] = this match { + case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key); + case IntMap.Tip(key2, value) => if (key == key2) Some(value) else None; + case IntMap.Nil => None; + } + + final override def getOrElse[S >: T](key : Int, default : =>S) : S = this match { + case IntMap.Nil => default; + case IntMap.Tip(key2, value) => if (key == key2) value else default; + case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key); + } + + final override def apply(key : Int) : T = this match { + case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key); + case IntMap.Tip(key2, value) => if (key == key2) value else error("Key not found"); + case IntMap.Nil => error("key not found"); + } + + def update[S >: T](key : Int, value : S) : IntMap[S] = this match { + case IntMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this); + else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.update(key, value), right) + else IntMap.Bin(prefix, mask, left, right.update(key, value)); + case IntMap.Tip(key2, value2) => if (key == key2) IntMap.Tip(key, value); + else join(key, IntMap.Tip(key, value), key2, this); + case IntMap.Nil => IntMap.Tip(key, value); + } + + /** + * Updates the map, using the provided function to resolve conflicts if the key is already present. + * Equivalent to + * <pre>this.get(key) match { + * case None => this.update(key, value); + * case Some(oldvalue) => this.update(key, f(oldvalue, value) } + * </pre> + * + * @param key The key to update + * @param value The value to use if there is no conflict + * @param f The function used to resolve conflicts. + */ + def updateWith[S >: T](key : Int, value : S, f : (T, S) => S) : IntMap[S] = this match { + case IntMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this); + else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.updateWith(key, value, f), right) + else IntMap.Bin(prefix, mask, left, right.updateWith(key, value, f)); + case IntMap.Tip(key2, value2) => if (key == key2) IntMap.Tip(key, f(value2, value)); + else join(key, IntMap.Tip(key, value), key2, this); + case IntMap.Nil => IntMap.Tip(key, value); + } + + def -(key : Int) : IntMap[T] = this match { + case IntMap.Bin(prefix, mask, left, right) => + if (!hasMatch(key, prefix, mask)) this; + else if (zero(key, mask)) bin(prefix, mask, left - key, right); + else bin(prefix, mask, left, right - key); + case IntMap.Tip(key2, _) => + if (key == key2) IntMap.Nil; + else this; + case IntMap.Nil => IntMap.Nil; + } + + /** + * A combined transform and filter function. Returns an IntMap such that for each (key, value) mapping + * in this map, if f(key, value) == None the map contains no mapping for key, and if <code>f(key, value) + * + * @param f The transforming function. + */ + def modifyOrRemove[S](f : (Int, T) => Option[S]) : IntMap[S] = this match { + case IntMap.Bin(prefix, mask, left, right) => { + val newleft = left.modifyOrRemove(f); + val newright = right.modifyOrRemove(f); + if ((left eq newleft) && (right eq newright)) this.asInstanceOf[IntMap[S]]; + else bin(prefix, mask, newleft, newright) + } + case IntMap.Tip(key, value) => f(key, value) match { + case None => IntMap.Nil; + case Some(value2) => + //hack to preserve sharing + if (value.asInstanceOf[AnyRef] eq value2.asInstanceOf[AnyRef]) this.asInstanceOf[IntMap[S]] + else IntMap.Tip(key, value2); + } + case IntMap.Nil => IntMap.Nil; + } + + + /** + * Forms a union map with that map, using the combining function to resolve conflicts. + * + * @param that the map to form a union with. + * @param f the function used to resolve conflicts between two mappings. + */ + def unionWith[S >: T](that : IntMap[S], f : (Int, S, S) => S) : IntMap[S] = (this, that) match{ + case (IntMap.Bin(p1, m1, l1, r1), that@(IntMap.Bin(p2, m2, l2, r2))) => + if (shorter(m1, m2)) { + if (!hasMatch(p2, p1, m1)) join(p1, this, p2, that); + else if (zero(p2, m1)) IntMap.Bin(p1, m1, l1.unionWith(that, f), r1); + else IntMap.Bin(p1, m1, l1, r1.unionWith(that, f)); + } else if (shorter(m2, m1)){ + if (!hasMatch(p1, p2, m2)) join(p1, this, p2, that); + else if (zero(p1, m2)) IntMap.Bin(p2, m2, this.unionWith(l2, f), r2); + else IntMap.Bin(p2, m2, l2, this.unionWith(r2, f)); + } + else { + if (p1 == p2) IntMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f)); + else join(p1, this, p2, that); + } + case (IntMap.Tip(key, value), x) => x.updateWith(key, value, (x, y) => f(key, y, x)); + case (x, IntMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y)); + case (IntMap.Nil, x) => x; + case (x, IntMap.Nil) => x; + } + + /** + * Forms the intersection of these two maps with a combinining function. The resulting map is + * a map that has only keys present in both maps and has values produced from the original mappings + * by combining them with f. + * + * @param that The map to intersect with. + * @param f The combining function. + */ + def intersectionWith[S, R](that : IntMap[S], f : (Int, T, S) => R) : IntMap[R] = (this, that) match { + case (IntMap.Bin(p1, m1, l1, r1), that@IntMap.Bin(p2, m2, l2, r2)) => + if (shorter(m1, m2)) { + if (!hasMatch(p2, p1, m1)) IntMap.Nil; + else if (zero(p2, m1)) l1.intersectionWith(that, f); + else r1.intersectionWith(that, f); + } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f)); + else { + if (!hasMatch(p1, p2, m2)) IntMap.Nil; + else if (zero(p1, m2)) this.intersectionWith(l2, f); + else this.intersectionWith(r2, f); + } + case (IntMap.Tip(key, value), that) => that.get(key) match { + case None => IntMap.Nil; + case Some(value2) => IntMap.Tip(key, f(key, value, value2)); + } + case (_, IntMap.Tip(key, value)) => this.get(key) match { + case None => IntMap.Nil; + case Some(value2) => IntMap.Tip(key, f(key, value2, value)); + } + case (_, _) => IntMap.Nil; + } + + /** + * Left biased intersection. Returns the map that has all the same mappings as this but only for keys + * which are present in the other map. + * + * @param that The map to intersect with. + */ + def intersection[R](that : IntMap[R]) : IntMap[T] = this.intersectionWith(that, (key : Int, value : T, value2 : R) => value); + + override def ++[S >: T](that : Iterable[(Int, S)]) = that match { + case (that : IntMap[_]) => this.unionWith[S](that.asInstanceOf[IntMap[S]], (key, x, y) => y); + case that => that.foldLeft(this : IntMap[S])({case (m, (x, y)) => m.update(x, y)}); + } +} + diff --git a/src/library/scala/collection/immutable/LongMap.scala b/src/library/scala/collection/immutable/LongMap.scala new file mode 100644 index 0000000000..b23537aca6 --- /dev/null +++ b/src/library/scala/collection/immutable/LongMap.scala @@ -0,0 +1,360 @@ +package scala.collection.immutable; + +private[immutable] object LongMapUtils{ + def zero(i : Long, mask : Long) = (i & mask) == 0; + def mask(i : Long, mask : Long) = i & (complement(mask - 1) ^ mask) + def hasMatch(key : Long, prefix : Long, m : Long) = mask(key, m) == prefix; + def unsignedCompare(i : Long, j : Long) = (i < j) ^ (i < 0) ^ (j < 0) + def shorter(m1 : Long, m2 : Long) = unsignedCompare(m2, m1) + def complement(i : Long) = (-1) ^ i; + def branchMask(i : Long, j : Long) = java.lang.Long.highestOneBit(i ^ j); + + def join[T](p1 : Long, t1 : LongMap[T], p2 : Long, t2 : LongMap[T]) : LongMap[T] = { + val m = branchMask(p1, p2); + val p = mask(p1, m); + if (zero(p1, m)) LongMap.Bin(p, m, t1, t2) + else LongMap.Bin(p, m, t2, t1); + } + + def bin[T](prefix : Long, mask : Long, left : LongMap[T], right : LongMap[T]) : LongMap[T] = (left, right) match { + case (left, LongMap.Nil) => left; + case (LongMap.Nil, right) => right; + case (left, right) => LongMap.Bin(prefix, mask, left, right); + } +} + +import LongMapUtils._ + +object LongMap{ + def empty[T] : LongMap[T] = LongMap.Nil; + def singleton[T](key : Long, value : T) : LongMap[T] = LongMap.Tip(key, value); + def apply[T](elems : (Long, T)*) : LongMap[T] = + elems.foldLeft(empty[T])((x, y) => x.update(y._1, y._2)); + + + private[immutable] case object Nil extends LongMap[Nothing]{ + override def equals(that : Any) = this eq that.asInstanceOf[AnyRef] + }; + private[immutable] case class Tip[+T](key : Long, value : T) extends LongMap[T]{ + def withValue[S](s : S) = + if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[LongMap.Tip[S]]; + else LongMap.Tip(key, s); + } + private[immutable] case class Bin[+T](prefix : Long, mask : Long, left : LongMap[T], right : LongMap[T]) extends LongMap[T]{ + def bin[S](left : LongMap[S], right : LongMap[S]) : LongMap[S] = { + if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[LongMap.Bin[S]]; + else LongMap.Bin[S](prefix, mask, left, right); + } + } + +} + +import LongMap._ + +// Iterator over a non-empty LongMap. +private[immutable] abstract class LongMapIterator[V, T](it : LongMap[V]) extends Iterator[T]{ + + // Basically this uses a simple stack to emulate conversion over the tree. However + // because we know that Longs are only 64 bits we can have at most 64 LongMap.Bins and + // one LongMap.Tip sitting on the tree at any point. Therefore we know the maximum stack + // depth is 65 + var index = 0; + var buffer = new Array[AnyRef](65); + + def pop = { + index -= 1; + buffer(index).asInstanceOf[LongMap[V]]; + } + + def push(x : LongMap[V]) { + buffer(index) = x.asInstanceOf[AnyRef]; + index += 1; + } + push(it); + + /** + * What value do we assign to a tip? + */ + def valueOf(tip : LongMap.Tip[V]) : T; + + def hasNext = index != 0; + final def next : T = + pop match { + case LongMap.Bin(_,_, t@LongMap.Tip(_, _), right) => { + push(right); + valueOf(t); + } + case LongMap.Bin(_, _, left, right) => { + push(right); + push(left); + next; + } + case t@LongMap.Tip(_, _) => valueOf(t); + // This should never happen. We don't allow LongMap.Nil in subtrees of the LongMap + // and don't return an LongMapIterator for LongMap.Nil. + case LongMap.Nil => error("Empty maps not allowed as subtrees"); + } +} + +private[immutable] class LongMapEntryIterator[V](it : LongMap[V]) extends LongMapIterator[V, (Long, V)](it){ + def valueOf(tip : LongMap.Tip[V]) = (tip.key, tip.value); +} + +private[immutable] class LongMapValueIterator[V](it : LongMap[V]) extends LongMapIterator[V, V](it){ + def valueOf(tip : LongMap.Tip[V]) = tip.value; +} + +private[immutable] class LongMapKeyIterator[V](it : LongMap[V]) extends LongMapIterator[V, Long](it){ + def valueOf(tip : LongMap.Tip[V]) = tip.key; +} + +import LongMap._; + +/** + * Specialised immutable map structure for long keys, based on + * <a href="http://citeseer.ist.psu.edu/okasaki98fast.html">Fast Mergeable Long Maps</a> + * by Okasaki and Gill. Essentially a trie based on binary digits of the the integers. + */ +sealed abstract class LongMap[+T] extends scala.collection.immutable.Map[Long, T]{ + def empty[S] : LongMap[S] = LongMap.Nil; + + override def toList = { + val buffer = new scala.collection.mutable.ListBuffer[(Long, T)]; + foreach(buffer += _); + buffer.toList; + } + + /** + * Iterator over key, value pairs of the map in unsigned order of the keys. + */ + def elements : Iterator[(Long, T)] = this match { + case LongMap.Nil => Iterator.empty; + case _ => new LongMapEntryIterator(this); + } + + /** + * Loops over the key, value pairs of the map in unsigned order of the keys. + */ + override final def foreach(f : ((Long, T)) => Unit) : Unit = this match { + case LongMap.Bin(_, _, left, right) => {left.foreach(f); right.foreach(f); } + case LongMap.Tip(key, value) => f((key, value)); + case LongMap.Nil => {}; + } + + override def keys : Iterator[Long] = this match { + case LongMap.Nil => Iterator.empty; + case _ => new LongMapKeyIterator(this); + } + + /** + * Loop over the keys of the map. The same as keys.foreach(f), but may + * be more efficient. + * + * @param f The loop body + */ + final def foreachKey(f : Long => Unit) : Unit = this match { + case LongMap.Bin(_, _, left, right) => {left.foreachKey(f); right.foreachKey(f); } + case LongMap.Tip(key, _) => f(key); + case LongMap.Nil => {} + } + + override def values : Iterator[T] = this match { + case LongMap.Nil => Iterator.empty; + case _ => new LongMapValueIterator(this); + } + + /** + * Loop over the keys of the map. The same as keys.foreach(f), but may + * be more efficient. + * + * @param f The loop body + */ + final def foreachValue(f : T => Unit) : Unit = this match { + case LongMap.Bin(_, _, left, right) => {left.foreachValue(f); right.foreachValue(f); } + case LongMap.Tip(_, value) => f(value); + case LongMap.Nil => {}; + } + + override def stringPrefix = "LongMap" + + override def isEmpty = this == LongMap.Nil; + + override def filter(f : ((Long, T)) => Boolean) : LongMap[T] = this match { + case LongMap.Bin(prefix, mask, left, right) => { + val (newleft, newright) = (left.filter(f), right.filter(f)); + if ((left eq newleft) && (right eq newright)) this; + else bin(prefix, mask, newleft, newright); + } + case LongMap.Tip(key, value) => + if (f((key, value))) this + else LongMap.Nil; + case LongMap.Nil => LongMap.Nil; + } + + override def transform[S](f : (Long, T) => S) : LongMap[S] = this match { + case b@LongMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f)); + case t@LongMap.Tip(key, value) => t.withValue(f(key, value)); + case LongMap.Nil => LongMap.Nil; + } + + final def size : Int = this match { + case LongMap.Nil => 0; + case LongMap.Tip(_, _) => 1; + case LongMap.Bin(_, _, left, right) => left.size + right.size; + } + + final def get(key : Long) : Option[T] = this match { + case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key); + case LongMap.Tip(key2, value) => if (key == key2) Some(value) else None; + case LongMap.Nil => None; + } + + final override def getOrElse[S >: T](key : Long, default : =>S) : S = this match { + case LongMap.Nil => default; + case LongMap.Tip(key2, value) => if (key == key2) value else default; + case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key); + } + + final override def apply(key : Long) : T = this match { + case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key); + case LongMap.Tip(key2, value) => if (key == key2) value else error("Key not found"); + case LongMap.Nil => error("key not found"); + } + + def update[S >: T](key : Long, value : S) : LongMap[S] = this match { + case LongMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this); + else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.update(key, value), right) + else LongMap.Bin(prefix, mask, left, right.update(key, value)); + case LongMap.Tip(key2, value2) => if (key == key2) LongMap.Tip(key, value); + else join(key, LongMap.Tip(key, value), key2, this); + case LongMap.Nil => LongMap.Tip(key, value); + } + + /** + * Updates the map, using the provided function to resolve conflicts if the key is already present. + * Equivalent to + * <pre>this.get(key) match { + * case None => this.update(key, value); + * case Some(oldvalue) => this.update(key, f(oldvalue, value) } + * </pre> + * + * @param key The key to update + * @param value The value to use if there is no conflict + * @param f The function used to resolve conflicts. + */ + def updateWith[S >: T](key : Long, value : S, f : (T, S) => S) : LongMap[S] = this match { + case LongMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this); + else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.updateWith(key, value, f), right) + else LongMap.Bin(prefix, mask, left, right.updateWith(key, value, f)); + case LongMap.Tip(key2, value2) => if (key == key2) LongMap.Tip(key, f(value2, value)); + else join(key, LongMap.Tip(key, value), key2, this); + case LongMap.Nil => LongMap.Tip(key, value); + } + + def -(key : Long) : LongMap[T] = this match { + case LongMap.Bin(prefix, mask, left, right) => + if (!hasMatch(key, prefix, mask)) this; + else if (zero(key, mask)) bin(prefix, mask, left - key, right); + else bin(prefix, mask, left, right - key); + case LongMap.Tip(key2, _) => + if (key == key2) LongMap.Nil; + else this; + case LongMap.Nil => LongMap.Nil; + } + + /** + * A combined transform and filter function. Returns an LongMap such that for each (key, value) mapping + * in this map, if f(key, value) == None the map contains no mapping for key, and if <code>f(key, value) + * + * @param f The transforming function. + */ + def modifyOrRemove[S](f : (Long, T) => Option[S]) : LongMap[S] = this match { + case LongMap.Bin(prefix, mask, left, right) => { + val newleft = left.modifyOrRemove(f); + val newright = right.modifyOrRemove(f); + if ((left eq newleft) && (right eq newright)) this.asInstanceOf[LongMap[S]]; + else bin(prefix, mask, newleft, newright) + } + case LongMap.Tip(key, value) => f(key, value) match { + case None => LongMap.Nil; + case Some(value2) => + //hack to preserve sharing + if (value.asInstanceOf[AnyRef] eq value2.asInstanceOf[AnyRef]) this.asInstanceOf[LongMap[S]] + else LongMap.Tip(key, value2); + } + case LongMap.Nil => LongMap.Nil; + } + + + /** + * Forms a union map with that map, using the combining function to resolve conflicts. + * + * @param that the map to form a union with. + * @param f the function used to resolve conflicts between two mappings. + */ + def unionWith[S >: T](that : LongMap[S], f : (Long, S, S) => S) : LongMap[S] = (this, that) match{ + case (LongMap.Bin(p1, m1, l1, r1), that@(LongMap.Bin(p2, m2, l2, r2))) => + if (shorter(m1, m2)) { + if (!hasMatch(p2, p1, m1)) join(p1, this, p2, that); + else if (zero(p2, m1)) LongMap.Bin(p1, m1, l1.unionWith(that, f), r1); + else LongMap.Bin(p1, m1, l1, r1.unionWith(that, f)); + } else if (shorter(m2, m1)){ + if (!hasMatch(p1, p2, m2)) join(p1, this, p2, that); + else if (zero(p1, m2)) LongMap.Bin(p2, m2, this.unionWith(l2, f), r2); + else LongMap.Bin(p2, m2, l2, this.unionWith(r2, f)); + } + else { + if (p1 == p2) LongMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f)); + else join(p1, this, p2, that); + } + case (LongMap.Tip(key, value), x) => x.updateWith(key, value, (x, y) => f(key, y, x)); + case (x, LongMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y)); + case (LongMap.Nil, x) => x; + case (x, LongMap.Nil) => x; + } + + /** + * Forms the intersection of these two maps with a combinining function. The resulting map is + * a map that has only keys present in both maps and has values produced from the original mappings + * by combining them with f. + * + * @param that The map to intersect with. + * @param f The combining function. + */ + def intersectionWith[S, R](that : LongMap[S], f : (Long, T, S) => R) : LongMap[R] = (this, that) match { + case (LongMap.Bin(p1, m1, l1, r1), that@LongMap.Bin(p2, m2, l2, r2)) => + if (shorter(m1, m2)) { + if (!hasMatch(p2, p1, m1)) LongMap.Nil; + else if (zero(p2, m1)) l1.intersectionWith(that, f); + else r1.intersectionWith(that, f); + } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f)); + else { + if (!hasMatch(p1, p2, m2)) LongMap.Nil; + else if (zero(p1, m2)) this.intersectionWith(l2, f); + else this.intersectionWith(r2, f); + } + case (LongMap.Tip(key, value), that) => that.get(key) match { + case None => LongMap.Nil; + case Some(value2) => LongMap.Tip(key, f(key, value, value2)); + } + case (_, LongMap.Tip(key, value)) => this.get(key) match { + case None => LongMap.Nil; + case Some(value2) => LongMap.Tip(key, f(key, value2, value)); + } + case (_, _) => LongMap.Nil; + } + + /** + * Left biased intersection. Returns the map that has all the same mappings as this but only for keys + * which are present in the other map. + * + * @param that The map to intersect with. + */ + def intersection[R](that : LongMap[R]) : LongMap[T] = this.intersectionWith(that, (key : Long, value : T, value2 : R) => value); + + override def ++[S >: T](that : Iterable[(Long, S)]) = that match { + case (that : LongMap[_]) => this.unionWith[S](that.asInstanceOf[LongMap[S]], (key, x, y) => y); + case that => that.foldLeft(this : LongMap[S])({case (m, (x, y)) => m.update(x, y)}); + } +} + diff --git a/src/library/scala/collection/immutable/TreeHashMap.scala b/src/library/scala/collection/immutable/TreeHashMap.scala new file mode 100644 index 0000000000..1e0dd490fa --- /dev/null +++ b/src/library/scala/collection/immutable/TreeHashMap.scala @@ -0,0 +1,270 @@ +package scala.collection.immutable; + +object TreeHashMap{ + private[TreeHashMap] val _empty = new TreeHashMap[Any, Nothing](IntMap.empty[Nothing]); + def empty[Key, Value] : TreeHashMap[Key, Value] = _empty.asInstanceOf[TreeHashMap[Key, Value]]; + + def apply[Key, Value](elems : (Key, Value)*) : TreeHashMap[Key, Value] = fromIterable(elems) + + def fromIterable[Key, Value](elems : Iterable[(Key, Value)]) : TreeHashMap[Key, Value] = + elems.foldLeft(TreeHashMap.empty[Key, Value])((m, entry) => m.update(entry._1, entry._2)) + + private def apply[Key, Value](underlying : IntMap[AssocMap[Key, Value]]) = new TreeHashMap(underlying); +} + +/** + * An immutable Map which is based on an IntMap mapping hash codes to lists of (Key, Value) pairs with the + * same hashCode. + * + * Unlike the usual immutable.HashMap it is truly immutable behind the scenes. Consequently it is entirely + * safe to share between multiple threads and should achieve a much greater degree of sharing between instances. + * + * Performancewise, get and update seem to be somewhat slower than with a traditional hash map, but bulk operations + * such as filter, foreach and transform appear to get something of a speedup. + */ +class TreeHashMap[Key, +Value] private (private val underlying : IntMap[AssocMap[Key, Value]]) extends scala.collection.immutable.Map[Key, Value]{ + def elements : Iterator[(Key, Value)] = new Iterator[(Key, Value)]{ + val assocIt = new AssocMapIterator(AssocMap.empty[Key, Value]); + val intIterator = underlying.values; + + def hasNext = assocIt.hasNext || intIterator.hasNext; + def next = { + if (!assocIt.hasNext) assocIt.it = intIterator.next; + assocIt.next + } + } + + def empty[V] = TreeHashMap.empty[Key, V]; + + private def hash(key : Key) = { + var h = key.hashCode; + h ^= ((h >>> 20) ^ (h >>> 12)); + h ^ (h >>> 7) ^ (h >>> 4); + } + + override def stringPrefix="TreeHashMap" + + override lazy val size = underlying.values.foldLeft(0)((x, y) => x + y.size); + + override def equals(that : Any) = that match { + case (that : TreeHashMap[_, _]) => + if (this eq that) true + else if (this.size != that.size) false; + else this.underlying == that.underlying; + case _ => false; + } + + override def hashCode = underlying.hashCode; + + override def foreach(f : ((Key, Value)) => Unit) = underlying.foreachValue(_.foreach(f)); + + override def toList : List[(Key, Value)] = { + val buffer = new scala.collection.mutable.ListBuffer[(Key, Value)]; + foreach(buffer += _); + buffer.toList; + } + + override def apply(key : Key) = + underlying.get(hash(key)) match { + case None => default(key); + case Some(table) => table.getOrElse(key, default(key)); + } + + override def isEmpty = underlying.isEmpty; + + override def filter(f : ((Key, Value)) => Boolean) : TreeHashMap[Key, Value]= { + val newunderlying = underlying.modifyOrRemove( + (key, x) => { + val newtable = x.filter(f); + if (newtable.isEmpty) None; + else Some(newtable); + } + ) + if (newunderlying eq underlying) this; + else TreeHashMap(newunderlying); + } + + override def transform[C](f : (Key, Value) => C) = { + val newunderlying = underlying.transform( + (key, value) => value.transform(f) + ) + if (underlying eq newunderlying) this.asInstanceOf[TreeHashMap[Key, C]]; + else TreeHashMap(newunderlying); + } + + def get(key : Key) = underlying.get(hash(key)).flatMap(_.get(key)); + def update[S >: Value](key : Key, value : S) : TreeHashMap[Key, S] = TreeHashMap( + underlying.updateWith[AssocMap[Key, S]](hash(key), AssocMap.singleton[Key, S](key, value), (x, y) => y.merge(x)) + ) + + def -(key : Key) : TreeHashMap[Key, Value] = { + val h = hash(key); + underlying.get(h) match { + case None => this; + case Some(table) => { + val newtable = table - key; + if (table eq newtable) this; + else TreeHashMap(underlying.update(h, newtable)); + } + } + } + + override def ++[V >: Value](that : Iterable[(Key, V)]) : TreeHashMap[Key, V] = that match { + case (that : TreeHashMap[_, _]) => this ++ TreeHashMap.fromIterable(that.asInstanceOf[TreeHashMap[Key, V]]) + case that => that.foldLeft(this : TreeHashMap[Key, V])((m, e) => m.update(e._1, e._2)); + } + + def ++[V >: Value](that : TreeHashMap[Key, V]) : TreeHashMap[Key, V] = + TreeHashMap(this.underlying.unionWith[AssocMap[Key, V]](that.underlying, (key, x, y) => x ++ y)); +} + + +private [collection] object AssocMap{ + val _empty = Nil[Any]; + def empty[Key, Value] : AssocMap[Key, Value] = _empty.asInstanceOf[AssocMap[Key, Value]] + def singleton[Key, Value](key : Key, value : Value) = Cons(key, value, empty); + def apply[Key, Value](maps : (Key, Value)*) = + maps.foldLeft(empty[Key, Value])((x, y) => x.update(y._1, y._2)); + + private[collection] case class Nil[Key] extends AssocMap[Key, Nothing]; + private[collection] case class Cons[S, +T](key : S, value : T, tail : AssocMap[S, T]) extends AssocMap[S, T] +} + +import AssocMap._; + +// AssocMap is very similar to ListMap. I don't want to patch ListMap right now, so I've got a separate +// implementation here to make tweaks to. Long term any of these changes should be merged into ListMap +// Short term it doesn't really matter because there are almost no viable use cases for ListMap compared +// to one of the alternatives. +private[collection] sealed abstract class AssocMap[Key, +Value] extends immutable.Map[Key, Value]{ + def empty[V] = AssocMap.empty[Key, V] + + final def get(key : Key) : Option[Value] = this match { + case Nil() => None; + case Cons(key2, value, tail) => if (key == key2) Some(value) + else tail.get(key); + } + + override final def getOrElse[V >: Value](key : Key, default : =>V) : V = this match { + case Nil() => default; + case Cons(key2, value, tail) => if (key == key2) value + else tail.getOrElse(key, default); + } + + override final def apply(key : Key) : Value = getOrElse(key, default(key)); + + override def filter(f : ((Key, Value)) => Boolean) : AssocMap[Key, Value] = this match { + case Cons(key, value, tail) => { + val filteredtail = tail.filter(f); + + if (f((key, value))) { + if (tail eq filteredtail) this; + else Cons(key, value, filteredtail); + } else filteredtail; + } + case Nil() => AssocMap.empty; + } + + def elements : Iterator[(Key, Value)] = new AssocMapIterator(this); + + override final def foreach(f : ((Key, Value)) => Unit) = this match { + case Cons(key, value, tail) => { f((key, value)); tail.foreach(f); } + case Nil() => {} + } + + def size = this match { + case Nil() => 0; + case Cons(_, _, tail) => 1 + tail.size; + } + + override def isEmpty = this match { + case Nil() => true; + case _ => false; + } + + private def removeKeyValue(key : Any, value : Any) : Option[AssocMap[Key, Value]] = this match { + case Nil() => None; + case Cons(key2, value2, tail) => + if (key == key2){ + if (value == value2) Some(tail); + else None; + } else tail.removeKeyValue(key, value) match { + case None => None; + case Some(x) => Some(Cons(key2, value2, x)); + } + } + + private def sameMappings(that : AssocMap[_, _]) : Boolean = (this, that) match { + case (Nil(), Nil()) => true; + case (Nil(), _) => false; + case (_, Nil()) => false; + case (Cons(key, value, tail), that) => that.removeKeyValue(key, value) match { + case None => false; + case Some(x) => tail.sameMappings(x); + } + } + + override def equals(that : Any) = + if (this eq that.asInstanceOf[AnyRef]) true; + else that match { + case (that : AssocMap[_, _]) => + if (this.size != that.size) false; + else this.sameMappings(that); + case _ => false; + } + + final def merge[S >: Value](that : AssocMap[Key, S]) : AssocMap[Key, S] = (this, that) match { + case (Nil(), that) => that; + case (_, Nil()) => this; + case (Cons(key, value, tail), that) => + tail.merge[S](that).update(key, value); + } + + def update[S >: Value](key : Key, value : S) : AssocMap[Key, S] = this match { + case Nil() => Cons(key, value, empty); + case Cons(key2, value2, tail) => + if (key2 == key) Cons(key, value, tail) + else Cons(key2, value2, tail.update(key, value)); + } + + override def transform[C](f : (Key, Value) => C) : AssocMap[Key, C] = this match { + case Nil() => AssocMap.empty[Key, C]; + case Cons(key, value, tail) => { + val newtail = tail.transform(f); + val newval = f(key, value); + if ((tail eq newtail) && (value.asInstanceOf[AnyRef] eq newval.asInstanceOf[AnyRef])) this.asInstanceOf[AssocMap[Key, C]]; + else Cons(key, newval, newtail); + } + } + + def -(key : Key) : AssocMap[Key, Value]= this match { + case Nil() => this; + case Cons(key2, value, tail) => + if (key == key2) tail; + else { + val newtail = tail - key; + if (tail eq newtail) this; + else Cons(key2, value, newtail); + } + } + + final def ++[V >: Value](that : AssocMap[Key, V]) : AssocMap[Key, V] = (this, that) match { + case (Nil(), that) => that; + case (_, Nil()) => this; + case (t1, Cons(key, value, tail)) => t1.update(key, value.asInstanceOf[Value] /* evil hack to work around bug 1140 */) ++ tail; + } +} + +private[collection] class AssocMapIterator[Key, Value](var it : AssocMap[Key, Value]) extends Iterator[(Key, Value)]{ + def hasNext = it match { + case Nil() => false; + case _ => true; + } + + def next = { + val Cons(key, value, next) = it; + it = next; + (key, value); + } +} + diff --git a/src/library/scala/collection/mutable/ArrayStack.scala b/src/library/scala/collection/mutable/ArrayStack.scala new file mode 100644 index 0000000000..27e73f364e --- /dev/null +++ b/src/library/scala/collection/mutable/ArrayStack.scala @@ -0,0 +1,155 @@ +package scala.collection.mutable; + +private object Utils{ + def growArray(x : Array[AnyRef]) = { + val y = new Array[AnyRef](x.length * 2); + Array.copy(x, 0, y, 0, x.length); + y; + } + + def clone(x : Array[AnyRef]) = { + val y = new Array[AnyRef](x.length); + Array.copy(x, 0, y, 0, x.length); + y; + } +} + +/** + * Simple stack class backed by an array. Should be significantly faster + * than the standard mutable stack. + */ +class ArrayStack[T] private(private var table : Array[AnyRef], + private var index : Int) extends Collection[T]{ + def this() = this(new Array[AnyRef](1), 0); + + /** + * Push an element onto the stack. + * + * @param x The element to push + */ + def push(x : T) = { + if (index == table.length) table = Utils.growArray(table); + table(index) = x.asInstanceOf[AnyRef]; + index += 1; + } + + /** + * Pop the top element off the stack. + */ + def pop = { + if (index == 0) error("Stack empty"); + index -= 1; + val x = table(index).asInstanceOf[T]; + table(index) = null; + x; + } + + /** + * View the top element of the stack. + */ + def peek = table(index - 1).asInstanceOf[T] + + /** + * Duplicate the top element of the stack. + */ + def dup = push(peek); + + /** + * Empties the stack. + */ + def clear = { + index = 0; + table = new Array(1); + } + + /** + * Empties the stack, passing all elements on it in FIFO order to the + * provided function. + * + * @param f The function to drain to. + */ + def drain(f : T => Unit) = while(!isEmpty) f(pop); + + /** + * Pushes all the provided elements onto the stack. + * + * @param x The source of elements to push + */ + def ++=(x : Iterable[T]) = x.foreach(this +=(_)) + + + /** + * Pushes all the provided elements onto the stack. + * + * @param x The source of elements to push + */ + def ++=(x : Iterator[T]) = x.foreach(this +=(_)) + + /** + * Alias for push. + * + * @param x The element to push + */ + def +=(x : T) = push(x); + + + + /** + * Pop the top two elements off the stack, apply f to them and push the result + * back on to the stack. + * + * @param f The combining function + */ + def combine(f : (T, T) => T) = push(f(pop, pop)); + + /** + * Repeatedly combine the top elements of the stack until the stack contains only + * one element. + */ + def reduceWith(f : (T, T) => T) = while(size > 1) combine(f) + + def size = index; + + /** + * Evaluates the expression, preserving the contents of the stack so that + * any changes the evaluation makes to the stack contents will be undone after + * it completes. + * + * @param action The action to run. + */ + def preserving[T](action : => T) = { + val oldIndex = index; + val oldTable = Utils.clone(table); + + try{ + action; + } finally { + index = oldIndex; + table = oldTable; + } + } + + override def isEmpty = index == 0; + + /** + * Iterates over the stack in fifo order. + */ + def elements = new Iterator[T]{ + var currentIndex = index; + def hasNext = currentIndex > 0; + def next = { + currentIndex -= 1; + table(currentIndex).asInstanceOf[T]; + } + } + + override def foreach(f : T => Unit){ + var currentIndex = index; + while(currentIndex > 0){ + currentIndex -= 1; + f(table(currentIndex).asInstanceOf[T]); + } + } + + override def clone = new ArrayStack[T](Utils.clone(table), index); +} |