diff options
author | stenman <stenman@epfl.ch> | 2003-12-09 14:25:53 +0000 |
---|---|---|
committer | stenman <stenman@epfl.ch> | 2003-12-09 14:25:53 +0000 |
commit | fa15a3d86678031567fd8d1cce2e73628f4d24ac (patch) | |
tree | 37924f95a9c6f5068e342c8e6488a1b06555f748 | |
parent | e6ed073577c6c03cb91eff97e684d9057bf5e169 (diff) | |
download | scala-fa15a3d86678031567fd8d1cce2e73628f4d24ac.tar.gz scala-fa15a3d86678031567fd8d1cce2e73628f4d24ac.tar.bz2 scala-fa15a3d86678031567fd8d1cce2e73628f4d24ac.zip |
More comments and cleanups.
-rw-r--r-- | sources/scala/collection/Set.scala | 8 | ||||
-rw-r--r-- | sources/scala/collection/immutable/ListMap.scala | 2 | ||||
-rw-r--r-- | sources/scala/collection/immutable/ListSet.scala | 69 | ||||
-rw-r--r-- | sources/scala/collection/immutable/Order.scala | 105 | ||||
-rw-r--r-- | sources/scala/collection/immutable/Set.scala | 2 | ||||
-rw-r--r-- | sources/scala/collection/immutable/Tree.scala | 43 | ||||
-rw-r--r-- | sources/scala/collection/immutable/TreeMap.scala | 35 | ||||
-rw-r--r-- | test/files/run/map_test.scala | 2 |
8 files changed, 227 insertions, 39 deletions
diff --git a/sources/scala/collection/Set.scala b/sources/scala/collection/Set.scala index 705a3d24ad..8cec4c200c 100644 --- a/sources/scala/collection/Set.scala +++ b/sources/scala/collection/Set.scala @@ -25,10 +25,10 @@ package scala.collection; */ trait Set[A] with Function1[A, Boolean] with Iterable[A] { - /** Returns the number of elements in this set. - * - * @return number of set elements. - */ + /** Returns the number of elements in this set. + * + * @return number of set elements. + */ def size: Int; /** Checks if this set contains element <code>elem</code>. diff --git a/sources/scala/collection/immutable/ListMap.scala b/sources/scala/collection/immutable/ListMap.scala index 5e80447a3d..8089f6681e 100644 --- a/sources/scala/collection/immutable/ListMap.scala +++ b/sources/scala/collection/immutable/ListMap.scala @@ -33,6 +33,8 @@ object ListMap { * @version 1.0, 09/07/2003 */ class ListMap[A, B] with Map[A, B] { + /** A factory to create empty maps of the same type of keys. + */ val factory = new ListMapFactory[A]; /** Returns the number of mappings in this map. diff --git a/sources/scala/collection/immutable/ListSet.scala b/sources/scala/collection/immutable/ListSet.scala index fa3582e31f..dd89906cec 100644 --- a/sources/scala/collection/immutable/ListSet.scala +++ b/sources/scala/collection/immutable/ListSet.scala @@ -24,18 +24,44 @@ object ListSet { */ class ListSet[A] with Set[A] { + /** Returns the number of elements in this set. + * + * @return number of set elements. + */ def size: Int = 0; + /** Checks if this set contains element <code>elem</code>. + * + * @param elem the element to check for membership. + * @return true, iff <code>elem</code> is contained in this set. + */ def contains(elem: A): Boolean = false; + /** This method creates a new set with an additional element. + */ def +(elem: A): ListSet[A] = new Node(elem); + /** <code>-</code> can be used to remove a single element from + * a set. + */ def -(elem: A): ListSet[A] = this; + /** Creates a new iterator over all elements contained in this + * object. + * + * @return the new iterator + */ def elements: Iterator[A] = toList.elements; + /** Transform this set into a list of all elements. + * + * @return a list which enumerates all elements of this set. + */ override def toList: List[A] = Nil; + /** 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]]) { val that = obj.asInstanceOf[scala.collection.Set[A]]; @@ -46,14 +72,39 @@ class ListSet[A] with Set[A] { override def hashCode(): Int = 0; protected class Node(elem: A) extends ListSet[A] { - override def size = ListSet.this.size + 1; - override def isEmpty: Boolean = false; - override def contains(e: A) = (e == elem) || ListSet.this.contains(e); - override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e); - override def -(e: A): ListSet[A] = if (e == elem) ListSet.this else { - val tail = ListSet.this - e; new tail.Node(elem) - } - override def toList: List[A] = elem :: ListSet.this.toList; - override def hashCode(): Int = elem.hashCode() + ListSet.this.hashCode(); + /** Returns the number of elements in this set. + * + * @return number of set elements. + */ + override def size = ListSet.this.size + 1; + /** Checks if this set is empty. + * + * @return true, iff there is no element in the set. + */ + override def isEmpty: Boolean = false; + + /** Checks if this set contains element <code>elem</code>. + * + * @param elem the element to check for membership. + * @return true, iff <code>elem</code> is contained in this set. + */ + override def contains(e: A) = (e == elem) || ListSet.this.contains(e); + + /** This method creates a new set with an additional element. + */ + override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e); + /** <code>-</code> can be used to remove a single element from + * a set. + */ + override def -(e: A): ListSet[A] = if (e == elem) ListSet.this else { + val tail = ListSet.this - e; new tail.Node(elem) + } + + /** Transform this set into a list of all elements. + * + * @return a list which enumerates all elements of this set. + */ + override def toList: List[A] = elem :: ListSet.this.toList; + override def hashCode(): Int = elem.hashCode() + ListSet.this.hashCode(); } } diff --git a/sources/scala/collection/immutable/Order.scala b/sources/scala/collection/immutable/Order.scala index ee733e98f4..44ad1f2482 100644 --- a/sources/scala/collection/immutable/Order.scala +++ b/sources/scala/collection/immutable/Order.scala @@ -9,9 +9,104 @@ package scala.collection.immutable; -class Order[t](less:(t,t) => Boolean,equal:(t,t) => Boolean) { - def lt (e1:t, e2:t) = less(e1,e2); - def leq (e1:t, e2:t) = less(e1,e2) || equal(e1,e2); - def gt (e1:t, e2:t) = less(e2,e1); - def geq (e1:t, e2:t) = leq(e2,e1); +/** The object Order provides constructors for orderings between +* objects. +*/ +object Order { + /** + * Creates an Order given a predicate + * (<code>inferiority(e1,e2)</code>). + * The predicate is true iff e1 is less than + * e2. The ordinary equality operator == will be used for + * equality by the order. + */ + def make[A](inferiority:(A,A) => Boolean) = + new Order[A](inferiority,(e1:A,e2:A) => e1 == e2); + /** + * Creates an Order given two predicates + * (<code>inferiority(e1,e2)</code> and + * <code>equality(e1,e2)</code>). The first is true iff e1 is less than + * e2 and the second predicate is true when e1 is equal to e2. + */ + def make[A](inferiority:(A,A) => Boolean, equality:(A,A) => Boolean) = + new Order[A](inferiority,equality); + /** + * Creates a 'standard' order between objects. <strong>NOTE:</strong> + * The order is arbitrary and uses the <code>hashCode()</code> of + * objects which might mean that the order is not really total + * for some objects <code>(!(e1 < e2) && !(e2 < e1) && !(e1==e2))</code> + * is true. This function should only be used when no other + * comparision predicates can be defined. + */ + def make = + new Order[Any]( + (e1:Any,e2:Any) => + e1.match { + case x:Int => { + e2.match { + case y:Int => x < y; + case y:Double => x < y; + case y:Float => x < y; + case y:Long => x < y; + case _ => true; + } + } + case x:Double => { + e2.match { + case y:Int => x < y; + case y:Double => x < y; + case y:Float => x < y; + case y:Long => x < y; + case _ => true; + } + } + case x:Float => { + e2.match { + case y:Int => x < y; + case y:Double => x < y + case y:Float => x < y;; + case y:Long => x < y; + case _ => true; + } + } + case x:Long => { + e2.match { + case y:Int => x < y; + case y:Double => x < y + case y:Float => x < y;; + case y:Long => x < y; + case _ => true; + } + } + case x:AnyRef => { + e2.match { + case y:AnyVal => false; + case y:AnyRef => x.hashCode() < y.hashCode(); + } + } + }, + (e1:Any,e2:Any) => e1 == e2); +} + + +/** The class Order[A] defines an order between objects of + * type A, given two predicates (<code>inferiority(e1,e2)</code> and + * <code>equality(e1,e2)</code>). The first is true iff e1 is less than + * e2 and the second predicate is true when e1 is equal to e2. + * An Order object can be used for ordered trees, maps, and sets. + * In order to use the order with the given + * TreeMap and TreeSet implementations the definition of the + * predicates <code>inferiority</code> and <code>equality</code> + * should be total. They predicate should + * also define a true total ordering (i.e., inferiority should be + * transitive, non-reflexive and asymmetric, and equality should be + * transitive, reflexive and symetric.) + */ +class Order[A](inferiority:(A,A) => Boolean, equality:(A,A) => Boolean) { + def < (e1:A, e2:A) = inferiority(e1,e2); + def <= (e1:A, e2:A) = inferiority(e1,e2) || equality(e1,e2); + def > (e1:A, e2:A) = inferiority(e2,e1); + def >= (e1:A, e2:A) = ! inferiority(e1,e2); + def == (e1:A, e2:A) = equality(e1,e2); + def != (e1:A, e2:A) = ! equality(e1,e2); } diff --git a/sources/scala/collection/immutable/Set.scala b/sources/scala/collection/immutable/Set.scala index 2ed79d9e24..b613c7d86f 100644 --- a/sources/scala/collection/immutable/Set.scala +++ b/sources/scala/collection/immutable/Set.scala @@ -38,7 +38,7 @@ trait Set[A] with scala.collection.Set[A] { res; } - /** <code>-=</code> can be used to remove a single element from + /** <code>-</code> can be used to remove a single element from * a set. */ def -(elem: A): Set[A]; diff --git a/sources/scala/collection/immutable/Tree.scala b/sources/scala/collection/immutable/Tree.scala index cdc2b2b669..a478e9a93b 100644 --- a/sources/scala/collection/immutable/Tree.scala +++ b/sources/scala/collection/immutable/Tree.scala @@ -124,13 +124,14 @@ abstract class Tree[KEY,Entry](order:Order[KEY]) { * @param key the key * @return true, iff there is a mapping for key in this map */ - def is_defined(key:KEY) = tree.is_defined(key); + def is_defined(key:KEY) = tree.is_defined(key); /** * A new tree with the entry added is returned, * assuming that key is <emph>not</emph> in the tree. - */ def add(key:KEY,entry:Entry):This = { + */ + def add(key:KEY,entry:Entry):This = { val newSize = size+1; New(newSize, tree.insert(key, @@ -149,6 +150,8 @@ abstract class Tree[KEY,Entry](order:Order[KEY]) { } + /** Removes the key from the tree. + */ def delete_any(key:KEY) = if(is_defined(key)) delete(key) else // TODO: Avoid this creation by convincing the type system that this has type This. @@ -225,33 +228,33 @@ abstract class Tree[KEY,Entry](order:Order[KEY]) { } def is_defined(key:KEY):Boolean = { - if(order.lt(key,entryKey(value))) smaller.is_defined(key) - else if(order.gt(key,entryKey(value))) bigger.is_defined(key) + if(order.<(key,entryKey(value))) smaller.is_defined(key) + else if(order.>(key,entryKey(value))) bigger.is_defined(key) else true; } def get(key:KEY):Option[Entry] = - if (order.lt(key,entryKey(value))) smaller.get(key); - else if (order.gt(key,entryKey(value))) bigger.get(key); + if (order.<(key,entryKey(value))) smaller.get(key); + else if (order.>(key,entryKey(value))) bigger.get(key); else Some(value); def apply(key:KEY):Entry = - if (order.lt(key,entryKey(value))) smaller.apply(key); - else if (order.gt(key,entryKey(value))) bigger.apply(key); + if (order.<(key,entryKey(value))) smaller.apply(key); + else if (order.>(key,entryKey(value))) bigger.apply(key); else value; def update(key:KEY, newValue:Entry):aNode = - if (order.lt(key,entryKey(value))) + if (order.<(key,entryKey(value))) GBNode(value, smaller.update(key,newValue), bigger); - else if (order.gt(key,entryKey(value))) + else if (order.>(key,entryKey(value))) GBNode(value, smaller, bigger.update(key,newValue)); else GBNode(newValue, smaller, bigger); def insert(key:KEY, newValue:Entry, s:int):anInsertTree = { - if(order.lt(key,entryKey(value))) + if(order.<(key,entryKey(value))) smaller.insert(key, newValue, div2(s)).insert_left(value,bigger); - else if(order.gt(key,entryKey(value))) + else if(order.>(key,entryKey(value))) bigger.insert(key, newValue, div2(s)).insert_right(value,smaller); else error("Key exists" + key); } @@ -265,10 +268,10 @@ abstract class Tree[KEY,Entry](order:Order[KEY]) { def delete(key:KEY):aNode = { - if (order.lt(key,entryKey(value))) + if (order.<(key,entryKey(value))) GBNode(value, smaller.delete(key), bigger); else - if (order.gt(key,entryKey(value))) + if (order.>(key,entryKey(value))) GBNode(value, smaller, bigger.delete(key)); else smaller.merge(bigger) @@ -357,8 +360,6 @@ abstract class Tree[KEY,Entry](order:Order[KEY]) { } // End of class Tree... -case class Info(height:int, size:int); - abstract class InsertTree[KEY,Entry]() { type aNode = GBTree[KEY,Entry]; type anInsertTree = InsertTree[KEY,Entry]; @@ -368,10 +369,17 @@ abstract class InsertTree[KEY,Entry]() { def node:aNode; } +/** +* GBTree is an internal class used by Tree. +*/ + abstract class GBTree[KEY,Entry] { type aNode = GBTree[KEY,Entry]; type anInsertTree = InsertTree[KEY,Entry]; + /** 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:KEY):Boolean; def get(key:KEY):Option[Entry]; @@ -385,6 +393,9 @@ abstract class GBTree[KEY,Entry] { def take_smallest:Pair[Entry,aNode]; def balance(s:int):GBTree[KEY,Entry]; + case class Info(height:int, size:int); + + } diff --git a/sources/scala/collection/immutable/TreeMap.scala b/sources/scala/collection/immutable/TreeMap.scala index 878a4bdb24..c903721b6b 100644 --- a/sources/scala/collection/immutable/TreeMap.scala +++ b/sources/scala/collection/immutable/TreeMap.scala @@ -20,21 +20,39 @@ class TreeMapFactory[KEY](order:Order[KEY]) extends MapFactory[KEY] { */ class TreeMap[KEY,VALUE](order:Order[KEY]) extends Tree[KEY,Pair[KEY,VALUE]](order) with Map[KEY, VALUE] { override type This = TreeMap[KEY,VALUE]; + /** A factory to create empty maps of the same type of keys. + */ val factory = new TreeMapFactory[KEY](order); + + /** Returns the key of an entry. + * This method has to be defined by concrete implementations + * of the class. + */ override def entryKey(entry:Pair[KEY,VALUE]) = entry._1; + /** Creates a new TreeMap from a GBTree and its size. */ protected def New(sz:Int,t:aNode):This = new TreeMap[KEY,VALUE](order) { override def size=sz; override protected val tree:aNode=t; } + /** + * A new TreeMap with the entry added is returned, + * if key is <emph>not</emph> in the TreeMap, otherwise + * the key is updated with the new entry. + */ def update(key:KEY, value:VALUE) = update_or_add(key,Pair(key,value)); + /** + * A new TreeMap with the entry added is returned, + * assuming that key is <emph>not</emph> in the TreeMap. + */ def insert(key:KEY,value:VALUE) = add(key,Pair(key,value)); - def -(key:KEY) = delete_any(key); - + /** Removes the key from the TreeMap. + */ + def -(key:KEY) = delete_any(key); /** Check if this map maps <code>key</code> to a value and return the * value if it exists. @@ -68,9 +86,20 @@ class TreeMapFactory[KEY](order:Order[KEY]) extends MapFactory[KEY] { */ override def toList:List[Pair[KEY,VALUE]] = tree.toList(scala.Nil); - def elements:Iterator[Pair[KEY,VALUE]] = entries; + /** Creates a new iterator over all elements contained in this + * object. + * + * @return the new iterator + */ + def elements:Iterator[Pair[KEY,VALUE]] = entries; + /** Compares two maps structurally; i.e. checks if all mappings + * contained in this map are also contained in the other map, + * and vice versa. + * + * @return true, iff both maps contain exactly the same mappings. + */ override def equals(obj: Any): Boolean = if (obj.isInstanceOf[scala.collection.Map[KEY, VALUE]]) { val that = obj.asInstanceOf[scala.collection.Map[KEY, VALUE]]; diff --git a/test/files/run/map_test.scala b/test/files/run/map_test.scala index 82a2c12e5a..709a7e0233 100644 --- a/test/files/run/map_test.scala +++ b/test/files/run/map_test.scala @@ -5,7 +5,7 @@ import scala.collection.immutable.Order; object Test with Executable { val intOrder = - new Order((x:int,y:int) => x < y, (x:int,y:int) => x == y); + Order.make((x:int,y:int) => x < y); test1(); test2(); |