summaryrefslogtreecommitdiff
path: root/sources
diff options
context:
space:
mode:
Diffstat (limited to 'sources')
-rw-r--r--sources/scala/collection/immutable/Tree.scala433
-rw-r--r--sources/scala/collection/immutable/TreeMap.scala49
-rw-r--r--sources/scala/collection/immutable/TreeSet.scala21
3 files changed, 234 insertions, 269 deletions
diff --git a/sources/scala/collection/immutable/Tree.scala b/sources/scala/collection/immutable/Tree.scala
index a6bd8920db..ecc4e0311f 100644
--- a/sources/scala/collection/immutable/Tree.scala
+++ b/sources/scala/collection/immutable/Tree.scala
@@ -38,6 +38,7 @@
package scala.collection.immutable;
+import java.lang.Math;
/** General Balanced Trees - highly efficient functional dictionaries.
*
@@ -47,28 +48,25 @@ package scala.collection.immutable;
* than AVL trees.
* <p/>
* This implementation does not balance the trees after deletions.
- * Since deletions
- * don't increase the height of a tree, this should be OK in most
- * applications. A balance method is provided for those cases
- * where rebalancing is needed.
+ * Since deletions don't increase the height of a tree, this should
+ * be OK in most applications. A balance method is provided for those
+ * cases where rebalancing is needed.
* <p/>
* The tree consists of entries conatining a key with an order.
- * Concrete implementations of the tree class has to suply the
- * function entryKey that given an entry in the tree return
- * its key.
* <p/>
* When instanciating the tree an order for the keys has to be
* supplied.
*
* @author Erik Stenman
- * @version 1.0, 10/07/2003
+ * @author Michel Schinz
+ * @version 1.1, 2005-01-20
*/
abstract class Tree[A <% Ordered[A], B] with java.io.Serializable {
/* Data structure:
** - size:Int - the number of elements in the tree.
** - tree:T, which is composed of nodes of the form:
- ** - GBNode(entry:B, smaller:T, bigger:T), and the "empty tree" node:
- ** - GBNil.
+ ** - GBNode(key: A, entry:B, smaller:T, bigger:T),
+ ** - and the "empty tree" node GBLeaf.
**
** Original balance condition h(T) <= ceil(c * log(|T|)) has been
** changed to the similar (but not quite equivalent) condition
@@ -83,16 +81,19 @@ abstract class Tree[A <% Ordered[A], B] with java.io.Serializable {
* type This = C[T];
* </pre>
*/
- type This <: Tree[A,B];
+ protected type This <: Tree[A,B];
+ protected def getThis: This;
/**
* The type of nodes that the tree is build from.
*/
protected type aNode = GBTree[A,B];
+ private val empty: aNode = GBLeaf[A,B]();
+
/** The nodes in the tree.
*/
- protected val tree:aNode = GBNil;
+ protected def tree: aNode = empty;
/** This abstract method should be defined by a concrete implementation
** C[T] as something like:
@@ -100,45 +101,27 @@ abstract class Tree[A <% Ordered[A], B] with java.io.Serializable {
** override def New(sz:Int,t:aNode):This {
** new C[T](order) {
** override def size=sz;
- ** override protected val tree:aNode=t;
+ ** override protected def tree:aNode=t;
** }
** </pre>
** The concrete implementation should also override the def of This
** <code>override type This = C[T];</code>
**
*/
- protected def New(sz:Int,t:aNode):This;
+ protected def New(sz: Int, t: aNode): This;
/** The size of the tree, returns 0 (zero) if the tree is empty.
** @Returns The number of nodes in the tree as an integer.
**/
- def size = 0;
-
- /** Returns the key of an entry.
- * This method has to be defined by concrete implementations
- * of the class.
- */
- def entryKey(entry:B):A;
-
-
- /** Is the given key mapped to a value by this map?
- *
- * @param key the key
- * @return true, iff there is a mapping for key in this map
- */
- def is_defined(key:A) = tree.is_defined(key);
-
+ def size: Int = 0;
/**
* A new tree with the entry added is returned,
* assuming that key is <em>not</em> in the tree.
*/
- def add(key:A,entry:B):This = {
+ protected def add(key: A, entry: B): This = {
val newSize = size+1;
- New(newSize,
- tree.insert(key,
- entry,
- pow(newSize, p)).node);
+ New(newSize, tree.insert(key, entry, newSize * newSize).node);
}
/**
@@ -146,22 +129,23 @@ abstract class Tree[A <% Ordered[A], B] with java.io.Serializable {
* if key is <em>not</em> in the tree, otherwise
* the key is updated with the new entry.
*/
- def update_or_add(key:A, entry:B):This = {
- if(is_defined(key)) New(size,tree.update(key,entry))
- else add(key,entry);
+ protected def updateOrAdd(key: A, entry: B): This = {
+ if (tree.isDefinedAt(key))
+ New(size,tree.update(key,entry))
+ else
+ add(key,entry);
}
+ /** Removes the key from the tree. */
+ protected def deleteAny(key: A): This =
+ if (tree.isDefinedAt(key))
+ delete(key)
+ else
+ getThis;
- /** Removes the key from the tree.
- */
- def delete_any(key:A) =
- if(is_defined(key)) delete(key) else
- // TODO: Avoid this creation by convincing the type system that this has type This.
- New(size,tree);
-
- /** Removes the key from the tree, assumimg that key is present.
- */
- private def delete(key:A) = New(size - 1, tree.delete(key));
+ /** Removes the key from the tree, assumimg that key is present. */
+ private def delete(key:A): This =
+ New(size - 1, tree.delete(key));
/** Check if this map maps <code>key</code> to a value and return the
* value if it exists.
@@ -169,7 +153,8 @@ abstract class Tree[A <% Ordered[A], B] with java.io.Serializable {
* @param key the key of the mapping of interest
* @return the value of the mapping, if it exists
*/
- def findValue(key:A) = tree.get(key);
+ protected def findValue(key:A): Option[B] =
+ tree.get(key);
/**
* Gives you an iterator over all elements in the tree.
@@ -178,13 +163,13 @@ abstract class Tree[A <% Ordered[A], B] with java.io.Serializable {
*
* Note: The iterator itself has a state, i.e., it is not functional.
*/
- def entries:Iterator[B] =
+ protected def entries: Iterator[B] =
new Iterator[B] {
var iter = tree.mk_iter(scala.Nil);
def hasNext = !iter.isEmpty;
def next =
iter.match {
- case (GBNode(v,_,t)::iter_tail) => {
+ case (GBNode(_,v,_,t)::iter_tail) => {
iter= t.mk_iter(iter_tail);
v;
}
@@ -193,213 +178,199 @@ abstract class Tree[A <% Ordered[A], B] with java.io.Serializable {
}
}
- /** Create a new balanced tree from the tree.
- * Might be useful to call after many deletions,
- * since deletion does not rebalance the tree.
- **/
- def balance = New(size,tree.balance(size));
-
-
- case object GBNil extends GBTree[A,B] {
- def count = Info(1,0);
- def is_defined(key:A) = false;
- def get(_key:A) = None;
- def apply(key:A) = error("key " + key + " not found");
- def update(key:A, value:B) = error("key " + key + " not found");
- def insert(key:A, value:B, s:int):anInsertTree =
- if (s == 0) INode(GBNode(value, GBNil, GBNil), 1, 1);
- else ITree(GBNode(value, GBNil, GBNil));
- def toList(acc:List[B]) = acc;
- def mk_iter(iter_tail:List[GBTree[A,B]]) = iter_tail;
- def merge(larger:GBTree[A,B]) = larger;
- def take_smallest:Pair[B,GBTree[A,B]] = error("Take Smallest on empty tree");
- def delete(_key:A) = error("Delete on empty tree.");
- def balance(s:int) = this;
- override def hashCode() = 0;
- }
-
- private case class GBNode(value:B,smaller:GBTree[A,B],bigger:GBTree[A,B]) extends GBTree[A,B] {
- def count:Info = {
- if (smaller == GBNil && bigger == GBNil) Info(1,1);
- else {
- val sInfo = smaller.count;
- val bInfo = bigger.count;
- Info(mul2(max(sInfo.height,bInfo.height)),
- sInfo.size + bInfo.size +1);
- }
- }
-
- def is_defined(key:A):Boolean = {
- if(key < entryKey(value)) smaller.is_defined(key)
- else if(key > entryKey(value)) bigger.is_defined(key)
- else true;
- }
-
- def get(key:A):Option[B] =
- if (key < entryKey(value)) smaller.get(key);
- else if (key > entryKey(value)) bigger.get(key);
- else Some(value);
-
- def apply(key:A):B =
- if (key < entryKey(value)) smaller.apply(key);
- else if (key > entryKey(value)) bigger.apply(key);
- else value;
-
- def update(key:A, newValue:B):aNode =
- if (key < entryKey(value))
- GBNode(value, smaller.update(key,newValue), bigger);
- else if (key > entryKey(value))
- GBNode(value, smaller, bigger.update(key,newValue));
- else
- GBNode(newValue, smaller, bigger);
-
- def insert(key:A, newValue:B, s:int):anInsertTree = {
- if(key < entryKey(value))
- smaller.insert(key, newValue, div2(s)).insert_left(value,bigger);
- else if(key > entryKey(value))
- bigger.insert(key, newValue, div2(s)).insert_right(value,smaller);
- else error("Key exists" + key);
- }
-
- def toList(acc:List[B]):List[B] =
- smaller.toList(value::bigger.toList(acc));
-
- def mk_iter(iter_tail:List[aNode]):List[aNode] =
- if (smaller == GBNil) this::iter_tail;
- else smaller.mk_iter(this::iter_tail);
-
-
- def delete(key:A):aNode = {
- if (key < entryKey(value))
- GBNode(value, smaller.delete(key), bigger);
- else
- if (key > entryKey(value))
- GBNode(value, smaller, bigger.delete(key));
- else
- smaller.merge(bigger)
- }
-
- def merge(larger:aNode) = {
- if(larger==GBNil) this;
- else {
- val Pair(value1,larger1) = larger.take_smallest;
- GBNode(value1,this,larger1);
- }
- }
-
- def take_smallest:Pair[B,aNode] = {
- if (smaller == GBNil) Pair(value,bigger);
- else {
- val Pair(value1, smaller1) = smaller.take_smallest;
- Pair(value1, GBNode(value, smaller1, bigger));
- }
- }
-
- def balance(s:int):GBTree[A,B] = balance_list(toList(scala.Nil), s);
-
- override def hashCode() =
- value.hashCode() + smaller.hashCode() + bigger.hashCode();
-
- }
-
-
- protected def balance_list(list:List[B], s:int) = balance_list_1(list, s)._1;
-
- protected def balance_list_1(list:List[B], s:int):Pair[aNode,List[B]] = {
- if(s > 1) {
- val sm = s - 1;
- val s2 = div2(sm);
- val s1 = sm - s2;
- val Pair(t1,v::l1) = balance_list_1(list, s1);
- val Pair(t2, l2) = balance_list_1(l1, s2);
- val t = GBNode(v, t1, t2);
- Pair(t, l2);
- } else
- if(s == 1) {
- val v = list.head;
- Pair(GBNode(v,GBNil,GBNil), list.tail);
- } else
- Pair(GBNil,list);
- }
-
+ /**
+ * Create a new balanced tree from the tree. Might be useful to call
+ * after many deletions, since deletion does not rebalance the tree.
+ */
+ def balance: This =
+ New(size, tree.balance(size));
+}
+private abstract class InsertTree[A <% Ordered[A],B]()
+ with java.io.Serializable {
+ def insertLeft(k: A, v: B, t: GBTree[A,B]): InsertTree[A,B];
+ def insertRight(k: A, v: B, t: GBTree[A,B]): InsertTree[A,B];
+ def node: GBTree[A,B];
+}
- // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% */
+private case class ITree[A <% Ordered[A],B](t: GBTree[A,B])
+ extends InsertTree[A,B] {
+ def insertLeft(key: A, value: B, bigger: GBTree[A,B]) =
+ ITree(GBNode(key, value, t, bigger));
+ def insertRight(key: A, value: B, smaller: GBTree[A,B]) =
+ ITree(GBNode(key, value, smaller, t));
+ def node = t;
+}
- protected case class ITree(t:aNode) extends InsertTree[A,B] {
- def insert_left(value:B,bigger:aNode) = ITree(GBNode(value,t,bigger));
- def insert_right(value:B,smaller:aNode) = ITree(GBNode(value,smaller,t));
- def node = t;
- }
- protected case class INode(t1:aNode,height:int,siz:int) extends InsertTree[A,B]{
- def insert_left(value:B,bigger:aNode) = balance_p(GBNode(value, t1, bigger), bigger);
- def insert_right(value:B,smaller:aNode) = balance_p(GBNode(value, smaller, t1),smaller);
- protected def balance_p(t:aNode,subtree:aNode):anInsertTree = {
- val info = subtree.count;
- val totalHeight = mul2(max(height, info.height));
- val totalSize = siz + info.size + 1;
- val BalanceHeight = pow(totalSize, p);
- if(totalHeight > BalanceHeight) ITree(t.balance(totalSize));
- else INode(t, totalHeight, totalSize);
- }
- def node = t1;
+private case class INode[A <% Ordered[A],B](t1: GBTree[A,B],
+ height: int,
+ size: int)
+ extends InsertTree[A,B] {
+ def insertLeft(key: A, value: B, bigger: GBTree[A,B]) =
+ balance_p(GBNode(key, value, t1, bigger), bigger);
+ def insertRight(key: A, value: B, smaller: GBTree[A,B]) =
+ balance_p(GBNode(key, value, smaller, t1),smaller);
+ protected def balance_p(t:GBTree[A,B],subtree:GBTree[A,B]):InsertTree[A,B] = {
+ val Pair(subHeight, subSize) = subtree.count;
+ val totalHeight = 2 * Math.max(height, subHeight);
+ val totalSize = size + subSize + 1;
+ val BalanceHeight = totalSize * totalSize;
+ if(totalHeight > BalanceHeight) ITree(t.balance(totalSize));
+ else INode(t, totalHeight, totalSize);
}
-
- /* -----------------------------------------------------------
- // Some helpful definitions.
- */
- private val p = 2; // It seems that p = 2 is optimal for sorted keys */
- private def pow(a:int, b:int):int =
- b.match {
- case 2 => a * a;
- case 1 => a;
- case x if x > 0 => a * pow(a, b-1);
- };
- private def div2(x:int) = x >> 1;
- private def mul2(x:int) = x << 1;
- private def max(x:int, y:int):int = if(x>y) x else y;
-
-
-} // End of class Tree...
-
-private abstract class InsertTree[A,B]() {
- type aNode = GBTree[A,B];
- type anInsertTree = InsertTree[A,B];
-
- def insert_left(v:B,t:aNode):anInsertTree;
- def insert_right(v:B,t:aNode):anInsertTree;
- def node:aNode;
+ def node = t1;
}
/**
* GBTree is an internal class used by Tree.
*/
-private abstract class GBTree[A,B] {
+private abstract class GBTree[A <% Ordered[A],B] with java.io.Serializable {
type aNode = GBTree[A,B];
type anInsertTree = InsertTree[A,B];
/** Calculates 2^h, and size, where h is the height of the tree
* and size is the number of nodes in the tree.
*/
- def count:Info;
- def is_defined(Key:A):Boolean;
+ def count:Pair[Int,Int];
+ def isDefinedAt(Key:A):Boolean;
def get(key:A):Option[B];
def apply(key:A):B;
def update(key:A, value:B):aNode;
def insert(key:A, value:B, size:int):anInsertTree;
- def toList(acc:List[B]):List[B];
- def mk_iter(iter_tail:List[aNode]):List[aNode];
+ def toList(acc: List[Pair[A,B]]): List[Pair[A,B]];
+ def mk_iter(iter_tail:List[aNode]): List[aNode];
def delete(key:A):aNode;
def merge(t:aNode):aNode;
- def take_smallest:Pair[B,aNode];
+ def takeSmallest:Triple[A,B,aNode];
def balance(s:int):GBTree[A,B];
+}
- case class Info(height:int, size:int);
+private case class GBLeaf[A <% Ordered[A],B] extends GBTree[A,B] {
+ def count = Pair(1, 0);
+ def isDefinedAt(key:A) = false;
+ def get(_key:A) = None;
+ def apply(key:A) = error("key " + key + " not found");
+ def update(key:A, value:B) = error("key " + key + " not found");
+ def insert(key:A, value:B, s:int):anInsertTree = {
+ if (s == 0)
+ INode(GBNode(key, value, this, this), 1, 1)
+ else
+ ITree(GBNode(key, value, this, this))
+ }
+ def toList(acc: List[Pair[A,B]]): List[Pair[A,B]] = acc;
+ def mk_iter(iter_tail:List[GBTree[A,B]]) = iter_tail;
+ def merge(larger:GBTree[A,B]) = larger;
+ def takeSmallest:Triple[A,B,GBTree[A,B]] =
+ error("Take Smallest on empty tree");
+ def delete(_key:A) = error("Delete on empty tree.");
+ def balance(s:int) = this;
+ override def hashCode() = 0;
+}
+private case class GBNode[A <% Ordered[A],B](key: A,
+ value: B,
+ smaller: GBTree[A,B],
+ bigger: GBTree[A,B])
+ extends GBTree[A,B] {
+ def count: Pair[Int,Int] = {
+ val Pair(sHeight, sSize) = smaller.count;
+ val Pair(bHeight, bSize) = bigger.count;
+ val mySize = sSize + bSize + 1;
+ if (mySize == 1)
+ Pair(1, mySize)
+ else
+ Pair(2 * Math.max(sHeight, bHeight), mySize);
+ }
-}
+ def isDefinedAt(sKey:A):Boolean = {
+ if (sKey < key) smaller.isDefinedAt(sKey)
+ else if (sKey > key) bigger.isDefinedAt(sKey)
+ else true;
+ }
+ def get(sKey:A):Option[B] =
+ if (sKey < key) smaller.get(sKey);
+ else if (sKey > key) bigger.get(sKey);
+ else Some(value);
+
+ def apply(sKey:A):B =
+ if (sKey < key) smaller.apply(sKey);
+ else if (sKey > key) bigger.apply(sKey);
+ else value;
+
+ def update(newKey:A, newValue:B):aNode =
+ if (newKey < key)
+ GBNode(key, value, smaller.update(newKey,newValue), bigger);
+ else if (newKey > key)
+ GBNode(key, value, smaller, bigger.update(newKey,newValue));
+ else
+ GBNode(newKey, newValue, smaller, bigger);
+
+ def insert(newKey:A, newValue:B, s:int): anInsertTree = {
+ if (newKey < key)
+ smaller.insert(newKey, newValue, s / 2).insertLeft(key, value, bigger);
+ else if (newKey > key)
+ bigger.insert(newKey, newValue, s / 2).insertRight(key, value, smaller);
+ else
+ error("Key exists: " + newKey);
+ }
+
+ def toList(acc: List[Pair[A,B]]): List[Pair[A,B]] =
+ smaller.toList(Pair(key, value) :: bigger.toList(acc));
+ def mk_iter(iter_tail:List[aNode]):List[aNode] =
+ smaller.mk_iter(this :: iter_tail);
+ def delete(sKey:A):aNode = {
+ if (sKey < key)
+ GBNode(key, value, smaller.delete(sKey), bigger);
+ else if (sKey > key)
+ GBNode(key, value, smaller, bigger.delete(sKey));
+ else
+ smaller.merge(bigger)
+ }
+ def merge(larger: aNode): GBTree[A,B] = larger match {
+ case GBLeaf() =>
+ this
+ case _ =>
+ val Triple(key1, value1, larger1) = larger.takeSmallest;
+ GBNode(key1, value1, this, larger1)
+ }
+
+ def takeSmallest: Triple[A, B, aNode] = smaller match {
+ case GBLeaf() =>
+ Triple(key, value, bigger)
+ case _ =>
+ val Triple(key1, value1, smaller1) = smaller.takeSmallest;
+ Triple(key1, value1, GBNode(key, value, smaller1, bigger))
+ }
+
+ def balance(s:int): GBTree[A,B] =
+ balance_list(toList(scala.Nil), s);
+
+ protected def balance_list(list: List[Pair[A,B]], s:int): GBTree[A,B] = {
+ val empty = GBLeaf[A,B]();
+ def bal(list: List[Pair[A,B]], s:int): Pair[aNode,List[Pair[A,B]]] = {
+ if (s > 1) {
+ val sm = s - 1;
+ val s2 = sm / 2;
+ val s1 = sm - s2;
+ val Pair(t1, Pair(k, v) :: l1) = bal(list, s1);
+ val Pair(t2, l2) = bal(l1, s2);
+ val t = GBNode(k, v, t1, t2);
+ Pair(t, l2)
+ } else
+ if (s == 1) {
+ val Pair(k,v) :: rest = list;
+ Pair(GBNode(k, v, empty, empty), rest)
+ } else
+ Pair(empty, list)
+ }
+ bal(list, s)._1
+ }
+
+ override def hashCode() =
+ value.hashCode() + smaller.hashCode() + bigger.hashCode();
+}
diff --git a/sources/scala/collection/immutable/TreeMap.scala b/sources/scala/collection/immutable/TreeMap.scala
index 1520fd1222..a2d4893564 100644
--- a/sources/scala/collection/immutable/TreeMap.scala
+++ b/sources/scala/collection/immutable/TreeMap.scala
@@ -21,39 +21,34 @@ object TreeMap {
*/
class TreeMap[A <% Ordered[A], B] extends Tree[A, Pair[A, B]] with Map[A, B] {
- override type This = TreeMap[A, B];
+ override protected type This = TreeMap[A, B];
+ override protected def getThis: This = this;
/** A factory to create empty maps of the same type of keys.
*/
def empty[C] = new TreeMap[A, C];
- /** Returns the key of an entry.
- * This method has to be defined by concrete implementations
- * of the class.
- */
- override def entryKey(entry:Pair[A,B]) = entry._1;
-
/** Creates a new TreeMap from a GBTree and its size.
*/
protected def New(sz:Int,t:aNode):This = new TreeMap[A,B] {
override def size=sz;
- override protected val tree:aNode=t;
+ override protected def tree:aNode=t;
}
/** A new TreeMap with the entry added is returned,
* if key is <em>not</em> in the TreeMap, otherwise
* the key is updated with the new entry.
*/
- def update(key:A, value:B) = update_or_add(key,Pair(key,value));
+ def update(key:A, value:B) = updateOrAdd(key, Pair(key, value));
/** A new TreeMap with the entry added is returned,
* assuming that key is <em>not</em> in the TreeMap.
*/
- def insert(key:A,value:B) = add(key,Pair(key,value));
+ def insert(key:A,value:B) = add(key, Pair(key, value));
/** Removes the key from the TreeMap.
*/
- def -(key:A) = delete_any(key);
+ def -(key:A) = deleteAny(key);
/** Check if this map maps <code>key</code> to a value and return the
* value if it exists.
@@ -61,10 +56,10 @@ class TreeMap[A <% Ordered[A], B] extends Tree[A, Pair[A, B]] with Map[A, B] {
* @param key the key of the mapping of interest
* @return the value of the mapping, if it exists
*/
- override def get(key:A) =
- findValue(key).match {
- case Some(Pair(_,value:B)) => Some(value);
- case _ => None;
+ override def get(key: A): Option[B] =
+ findValue(key) match {
+ case Some(Pair(_, value: B)) => Some(value)
+ case _ => None
}
/** Retrieve the value which is associated with the given key. This
@@ -81,14 +76,15 @@ class TreeMap[A <% Ordered[A], B] extends Tree[A, Pair[A, B]] with Map[A, B] {
*
* @return the list of all mappings
*/
- override def toList:List[Pair[A,B]] = tree.toList(scala.Nil);
+ override def toList: List[Pair[A,B]] =
+ tree.toList(scala.Nil) map (._2);
/** Creates a new iterator over all elements contained in this
* object.
*
* @return the new iterator
*/
- def elements:Iterator[Pair[A,B]] = entries;
+ def elements: Iterator[Pair[A,B]] = entries;
/** Compares two maps structurally; i.e. checks if all mappings
* contained in this map are also contained in the other map,
@@ -97,14 +93,13 @@ class TreeMap[A <% Ordered[A], B] extends Tree[A, Pair[A, B]] with Map[A, B] {
* @return true, iff both maps contain exactly the same mappings.
*/
override def equals(obj: Any): Boolean =
- if (obj.isInstanceOf[scala.collection.Map[A, B]]) {
- val that = obj.asInstanceOf[scala.collection.Map[A, B]];
- if (size != that.size) false else elements.forall {
- case Pair(key, value) => that.get(key) match {
- case None => false;
- case Some(v) => v == value;
- }
- }
- } else
- false;
+ obj.isInstanceOf[scala.collection.Map[A, B]] && {
+ val that = obj.asInstanceOf[scala.collection.Map[A, B]];
+ size == that.size && elements.forall {
+ case Pair(key, value) => that.get(key) match {
+ case None => false;
+ case Some(v) => v == value;
+ }
+ }
+ };
}
diff --git a/sources/scala/collection/immutable/TreeSet.scala b/sources/scala/collection/immutable/TreeSet.scala
index cde2ae86a3..e8e9cf3b99 100644
--- a/sources/scala/collection/immutable/TreeSet.scala
+++ b/sources/scala/collection/immutable/TreeSet.scala
@@ -18,13 +18,12 @@ package scala.collection.immutable;
*/
class TreeSet[A <% Ordered[A]] extends Tree[A, A] with Set[A] {
- type This = TreeSet[A];
-
- def entryKey(entry: A) = entry;
+ override protected type This = TreeSet[A];
+ override protected def getThis: This = this;
protected def New(sz: Int, t: aNode): This = new TreeSet[A] {
override def size = sz;
- override protected val tree: aNode = t;
+ override protected def tree: aNode = t;
}
/** Checks if this set contains element <code>elem</code>.
@@ -36,12 +35,12 @@ class TreeSet[A <% Ordered[A]] extends Tree[A, A] with Set[A] {
/** This method creates a new set with an additional element.
*/
- def +(elem: A): TreeSet[A] = update_or_add(elem, elem);
+ def +(elem: A): TreeSet[A] = updateOrAdd(elem, elem);
/** <code>-</code> can be used to remove a single element from
* a set.
*/
- def -(elem: A): TreeSet[A] = delete_any(elem);
+ def -(elem: A): TreeSet[A] = deleteAny(elem);
/** Creates a new iterator over all elements contained in this
* object.
@@ -54,15 +53,15 @@ class TreeSet[A <% Ordered[A]] extends Tree[A, A] with Set[A] {
*
* @return a list which enumerates all elements of this set.
*/
- override def toList: List[A] = tree.toList(scala.Nil);
+ override def toList: List[A] =
+ tree.toList(scala.Nil) map (._2);
/** Compares two sets for equality.
* Two set are equal iff they contain the same elements.
*/
override def equals(obj: Any): Boolean =
- if (obj.isInstanceOf[scala.collection.Set[A]]) {
+ obj.isInstanceOf[scala.collection.Set[A]] && {
val that = obj.asInstanceOf[scala.collection.Set[A]];
- if (size != that.size) false else toList.forall(that.contains);
- } else
- false;
+ (size == that.size) && toList.forall(that.contains);
+ }
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-19 20:03:59 +0000