diff options
author | stenman <stenman@epfl.ch> | 2003-11-26 14:23:16 +0000 |
---|---|---|
committer | stenman <stenman@epfl.ch> | 2003-11-26 14:23:16 +0000 |
commit | 24349248b132f9de8715de87adf7521cf3efb40f (patch) | |
tree | 1673bfef08ec0bb898d8ec327ddc0e57dad614e8 /sources | |
parent | bfe5383a1e3f0ff9850a3ec05d30ab28222b4719 (diff) | |
download | scala-24349248b132f9de8715de87adf7521cf3efb40f.tar.gz scala-24349248b132f9de8715de87adf7521cf3efb40f.tar.bz2 scala-24349248b132f9de8715de87adf7521cf3efb40f.zip |
Bugfixes to Tree and TreeMap
Diffstat (limited to 'sources')
-rw-r--r-- | sources/scala/collection/immutable/Order.scala | 4 | ||||
-rw-r--r-- | sources/scala/collection/immutable/Tree.scala | 255 | ||||
-rw-r--r-- | sources/scala/collection/immutable/TreeMap.scala | 7 |
3 files changed, 130 insertions, 136 deletions
diff --git a/sources/scala/collection/immutable/Order.scala b/sources/scala/collection/immutable/Order.scala index eae120b76d..ee733e98f4 100644 --- a/sources/scala/collection/immutable/Order.scala +++ b/sources/scala/collection/immutable/Order.scala @@ -10,8 +10,8 @@ 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 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 gt (e1:t, e2:t) = less(e2,e1); def geq (e1:t, e2:t) = leq(e2,e1); } diff --git a/sources/scala/collection/immutable/Tree.scala b/sources/scala/collection/immutable/Tree.scala index 0f1b715512..4a3d8cc3d9 100644 --- a/sources/scala/collection/immutable/Tree.scala +++ b/sources/scala/collection/immutable/Tree.scala @@ -32,13 +32,11 @@ ** USA ** ** Author contact: erik.stenman@epfl.ch -** (svenolof@csd.uu.se, richardc@csd.uu.se) ** --------------------------------------------------------------------- */ package scala.collection.immutable; - /** General Balanced Trees - highly efficient functional dictionaries. ** ** An efficient implementation of Prof. Arne Andersson's General @@ -56,64 +54,67 @@ package scala.collection.immutable; ** @version 1.0, 10/07/2003 */ -class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) { - /* Data structure: - ** - Size:int - the number of elements in the tree. - ** - Tree:T, which is composed of nodes of the form: - ** - Node(Key, Value, Smaller, Bigger), and the "empty tree" node: - ** - Nil(). - ** - ** Original balance condition h(T) <= ceil(c * log(|T|)) has been - ** changed to the similar (but not quite equivalent) condition 2 ^ h(T) - ** <= |T| ^ c. I figure this should also be OK. - ** - */ - protected type aNode = Tree[KEY,Entry]#T; - protected type anInsertTree = Tree[KEY,Entry]#InsertTree; - protected val tree:aNode = Nil(); - - /** 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; - - /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - * Factory method to create new trees. - */ - private def mkTree(sz:int,t:aNode):Tree[KEY,Entry] = - new Tree[KEY,Entry](order,entryKey){ - override def size=sz; - override protected val tree:aNode=t; - }; - /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% */ - - - /** 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 = mkTree(size,tree.balance(size)); - - - - // The iterator structure is really just a list corresponding to - // the call stack of an in-order traversal. - // - // Note: The iterator has a state, i.e., it is not functional. - def entries:Iterator[Entry] = - new Iterator[Entry] { - var iter = tree.mk_iter(scala.Nil); - def hasNext = !iter.isEmpty; - def next = - iter.match { - case (Node(v,_,t)::iter_tail) => - iter= iter_tail; - v; - case scala.Nil => - error("next on empty iterator"); - } + +class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) { + /* Data structure: + ** - Size:int - the number of elements in the tree. + ** - Tree:T, which is composed of nodes of the form: + ** - Node(Key, Value, Smaller, Bigger), and the "empty tree" node: + ** - Nil(). + ** + ** Original balance condition h(T) <= ceil(c * log(|T|)) has been + ** changed to the similar (but not quite equivalent) condition 2 ^ h(T) + ** <= |T| ^ c. I figure this should also be OK. + ** + */ + + protected type aNode = Tree[KEY,Entry]#T; + protected type anInsertTree = Tree[KEY,Entry]#InsertTree; + protected val tree:aNode = Nil(); + + /** 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; + + /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + * Factory method to create new trees. + */ + private def mkTree(sz:int,t:aNode):Tree[KEY,Entry] = + new Tree[KEY,Entry](order,entryKey){ + override def size=sz; + override protected val tree:aNode=t; + }; + /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% */ + + + /** 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 = mkTree(size,tree.balance(size)); + + + + // The iterator structure is really just a list corresponding to + // the call stack of an in-order traversal. + // + // Note: The iterator has a state, i.e., it is not functional. + def entries:Iterator[Entry] = + new Iterator[Entry] { + var iter = tree.mk_iter(scala.Nil); + def hasNext = !iter.isEmpty; + def next = + iter.match { + case (Node(v,_,t)::iter_tail) => { + iter= t.mk_iter(iter_tail); + v; + } + case scala.Nil => + error("next on empty iterator"); } + } private abstract class T() { @@ -132,79 +133,75 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) { def balance(s:int) = balance_list(toList(scala.Nil), s); private def balance_list(list:List[Entry], s:int) = { - val Pair(t, _) = balance_list_1(list, s); - t; + val Pair(t, _) = balance_list_1(list, s); + t; } private def balance_list_1(list:List[Entry], s:int): - Pair[aNode,List[Entry]] = { - 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 = Node(v, t1, t2); - Pair(t, l2); - } else - if(s == 1) { - val v = list.head; - Pair(Node(v,Nil(),Nil()), list.tail); - } else - Pair(Nil(),list); - } - - - + Pair[aNode,List[Entry]] = { + 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 = Node(v, t1, t2); + Pair(t, l2); + } else + if(s == 1) { + val v = list.head; + Pair(Node(v,Nil(),Nil()), list.tail); + } else + Pair(Nil(),list); + } } - private case class Node(value:Entry,smaller:aNode,bigger:aNode) - extends T { - def count:Info = { - if (smaller == Nil() && bigger == Nil()) - Info(1,1); - else { - val sInfo = smaller.count; - val bInfo = bigger.count; - Info(mul2(max(sInfo.height,bInfo.height)), - sInfo.size + bInfo.size +1); - } + private case class Node(value:Entry,smaller:aNode,bigger:aNode) extends T { + def count:Info = { + if (smaller == Nil() && bigger == Nil()) 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:KEY):Boolean = - if(order.lt(key,entryKey(value))) smaller.is_defined(key); - else if (order.gt(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); - 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); - else value; - - def update(key:KEY, newValue:Entry):aNode = - if (order.lt(key,entryKey(value))) - Node(value, smaller.update(key,newValue), bigger); - else if (order.gt(key,entryKey(value))) - Node(value, smaller, bigger.update(key,newValue)); - else - this; - - def insert(key:KEY, newValue:Entry, s:int):anInsertTree = - if(order.lt(key,entryKey(value))) - smaller.insert(key, newValue, div2(s)).insert_left(value,bigger); - else if(order.gt(key,entryKey(value))) - bigger.insert(key, value, div2(s)).insert_right(value,smaller); - else error("Key exists" + 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) + 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); + 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); + else value; + + def update(key:KEY, newValue:Entry):aNode = + if (order.lt(key,entryKey(value))) + Node(value, smaller.update(key,newValue), bigger); + else if (order.gt(key,entryKey(value))) + Node(value, smaller, bigger.update(key,newValue)); + else + Node(newValue, smaller, bigger); + + def insert(key:KEY, newValue:Entry, s:int):anInsertTree = { + if(order.lt(key,entryKey(value))) + smaller.insert(key, newValue, div2(s)).insert_left(value,bigger); + else if(order.gt(key,entryKey(value))) + bigger.insert(key, newValue, div2(s)).insert_right(value,smaller); + else error("Key exists" + key); + } - def toList(acc:List[Entry]):List[Entry] = - smaller.toList(value::bigger.toList(acc)); + def toList(acc:List[Entry]):List[Entry] = + smaller.toList(value::bigger.toList(acc)); def mk_iter(iter_tail:List[aNode]):List[aNode] = if (smaller == Nil()) this::iter_tail; @@ -241,7 +238,7 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) { private case class Nil() extends T { def count = Info(1,0); - def is_defined(_key:KEY) = false; + def is_defined(key:KEY) = false; def get(_key:KEY) = None; def apply(key:KEY) = error("key " + key + "not found"); def update(key:KEY, value:Entry) = error("key " + key + "not found"); @@ -264,10 +261,9 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) { */ protected val p = 2; // It seems that p = 2 is optimal for sorted keys */ protected def pow(a:int, b:int):int = - b.match { + b.match { case 2 => a * a; case 1 => a; - case 0 => 1; case x if x > 0 => a * pow(a, b-1); }; private def div2(x:int) = x >> 1; @@ -289,17 +285,17 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) { ITree(Node(value,smaller,t)); def node = t; } - private case class INode(t1:aNode,height:int,size:int) extends InsertTree{ + private case class INode(t1:aNode,height:int,siz:int) extends InsertTree{ def insert_left(value:Entry,bigger:aNode) = { - insert(Node(value, t1, bigger), bigger); + balance_p(Node(value, t1, bigger), bigger); } def insert_right(value:Entry,smaller:aNode) = { - insert(Node(value, smaller, t1),smaller); + balance_p(Node(value, smaller, t1),smaller); } - private def insert(t:aNode,subtree:aNode):anInsertTree = { + private def balance_p(t:aNode,subtree:aNode):anInsertTree = { val info = subtree.count; val totalHeight = mul2(max(height, info.height)); - val totalSize = size + info.size + 1; + val totalSize = siz + info.size + 1; val BalanceHeight = pow(totalSize, p); if(totalHeight > BalanceHeight) ITree(t.balance(totalSize)); else INode(t, totalHeight, totalSize); @@ -308,4 +304,3 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) { } } - diff --git a/sources/scala/collection/immutable/TreeMap.scala b/sources/scala/collection/immutable/TreeMap.scala index 35437e80cc..d25657df92 100644 --- a/sources/scala/collection/immutable/TreeMap.scala +++ b/sources/scala/collection/immutable/TreeMap.scala @@ -25,13 +25,12 @@ class TreeMap[KEY,VALUE](order:Order[KEY]) extends new TreeMap[KEY,VALUE](order){ override def size=sz; override protected val tree:aNode=t; - }; - + } def update(key:KEY, value:VALUE):TreeMap[KEY,VALUE] = { - if(contains(key)) mkTreeMap(size,tree.update(key,Pair(key,value))) + if(contains(key)) mkTreeMap(size,tree.update(key,Pair(key,value))) else insert(key,value); - } + } def insert(key:KEY,value:VALUE) = { val newSize = size+1; |