Changeset 4318 for trunk/ProjectFortress/compiler_tests

Timestamp:

11/06/09 14:37:52 (3 weeks ago)

Author:

jmaessen

Message:

[compiler, tests] Some refactoring on TreapAndTest. Fixed #362 and
added a test for it. Some misc cleanups on AbstractMethodChecker
that didn't make it into the last commit [Still looking to fix this to
avoid O(n^{2) behavior].}

Location:

trunk/ProjectFortress/compiler_tests

Files:

• EmptyDoEnd.fss (added)
• EmptyDoEnd.test (added)
• TreapAndTest.fss (modified) (17 diffs)

trunk/ProjectFortress/compiler_tests/TreapAndTest.fss

@@ +1 @@
+(*******************************************************************************
+    Copyright 2009 Sun Microsystems, Inc.,
+    4150 Network Circle, Santa Clara, California 95054, U.S.A.
+    All rights reserved.
+
+    U.S. Government Rights - Commercial software.
+    Government users are subject to the Sun Microsystems, Inc. standard
+    license agreement and applicable provisions of the FAR and its supplements.
+
+    Use is subject to license terms.
+
+    This distribution may include materials developed by third parties.
+
+    Sun, Sun Microsystems, the Sun logo and Java are trademarks or registered
+    trademarks of Sun Microsystems, Inc. in the U.S. and other countries.
+ ******************************************************************************)
+
 export Executable
 
@@ -55 +72 @@
 
 
-
-
-Min_HK : ZZ32 = -1
+Min_W : ZZ32 = -1
 
 (* We organize the treap as a max-treap; a min-treap would work just as well. *)
@@ -67 +82 @@
     getter min(): Treap = Treap(root.min)
     getter max(): Treap = Treap(root.max)
+    (* Union and intersection are left-biased *)
     opr UNION(self, other: Treap): Treap = Treap(root.combine(UnionOp, other.root))
     opr INTERSECTION(self, other: Treap): Treap = Treap(root.combine(IntersectionOp, other.root))
@@ -73 +89 @@
     opr SYMDIFF(self, other: Treap): Treap =
         Treap(root.combine(SymdiffOp, other.root))
+    containsKey(key:ZZ32): Boolean = NOT root.nodeWithKey(key).isEmpty
     replace(key:ZZ32, val:String): Treap = singleton(key,val) UNION self
     add(key:ZZ32, val:String): Treap = self UNION singleton(key,val)
-    remove(key:ZZ32): Treap = self DIFFERENCE Treap(Leaf1(Min_HK,key,""))
+    remove(key:ZZ32): Treap = self DIFFERENCE Treap(Leaf1(Min_W,key,""))
     lookup(key:ZZ32, defaultValue:String): String =
         root.nodeWithKey(key).rootValue(defaultValue)
@@ -88 +105 @@
 trait TreapNode comprises { NonEmpty, Empty }
     getter isEmpty(): Boolean
-    getter hk(): ZZ32
+    getter w(): ZZ32
     getter min(): TreapNode
     getter max(): TreapNode
@@ -121 +138 @@
 object Empty extends TreapNode
     getter isEmpty(): Boolean = true
-    getter hk(): ZZ32 = Min_HK
+    getter w(): ZZ32 = Min_W
     getter min(): TreapNode = self
     getter max(): TreapNode = self
@@ -140 +157 @@
     joinNE(l: NonEmpty): NonEmpty = l
 
-    combine(c: CombiningOp, r: TreapNode): TreapNode = c.leftEmpty(r)
-    combineNE(l: NonEmpty, c: CombiningOp): TreapNode = c.rightEmpty(l)
-
-    combineRootL(lr: Leaf1, c: CombiningOp): TreapNode = c.rightEmpty(lr)
-    combineRootR(c: CombiningOp, rr: Leaf1): TreapNode = c.leftEmpty(rr)
+    combine(c: CombiningOp, r: TreapNode): TreapNode = c.rightAlone(r)
+    combineNE(l: NonEmpty, c: CombiningOp): TreapNode = c.leftAlone(l)
+
+    combineRootL(lr: Leaf1, c: CombiningOp): TreapNode = c.leftAlone(lr)
+    combineRootR(c: CombiningOp, rr: Leaf1): TreapNode = c.rightAlone(rr)
 
     rootKey(defaultKey: ZZ32): ZZ32 = defaultKey
@@ -151 +168 @@
 
 trait NonEmpty extends TreapNode comprises { Leaf1, Node }
+    getter isEmpty(): Boolean = false
     getter k(): ZZ32
     getter v(): String
     getter root(): Leaf1
+
+    join(r: TreapNode): TreapNode = r.joinNE(self)
     (* Join this treap (on left) to r (on right);
-       assumes hk > r.hk *)
+       assumes w > r.w *)
     joinNEH(r: NonEmpty): NonEmpty
 
+    combine(c: CombiningOp, r: TreapNode): TreapNode =
+        r.combineNE(self,c)
     combineNEH(c: CombiningOp, r: NonEmpty): TreapNode
-end
-
-object Leaf1(hk0: ZZ32, k0: ZZ32, v0: String) extends NonEmpty
-    getter isEmpty(): Boolean = false
+
+    combineRootL(lr: Leaf1, c: CombiningOp): TreapNode = c.combine(lr,self.root)
+    combineRootR(c: CombiningOp, rr: Leaf1): TreapNode = c.combine(self.root,rr)
+
+    rootKey(defaultKey: ZZ32): ZZ32 = self.k
+    rootValue(defaultValue: String): String = self.v
+end
+
+object Leaf1(w0: ZZ32, k0: ZZ32, v0: String) extends NonEmpty
     getter k(): ZZ32 = k0
     getter v(): String = v0
     getter root(): Leaf1 = self
-    getter hk(): ZZ32 = hk0
+    getter w(): ZZ32 = w0
     getter min(): TreapNode = self
     getter max(): TreapNode = self
@@ -172 +199 @@
     mkString(withParens: Boolean): String =
         if withParens then
-            "<" hk0.asString ">" self.asString
+            "<" w0.asString ">" self.asString
         else
             self.asString
@@ -197 +224 @@
         if key < k0 then self else Empty end
 
-    join(r: TreapNode): TreapNode = r.joinNE(self)
     joinNE(l: NonEmpty): NonEmpty =
-        if hk0 > l.hk then
-            Node(l, hk0, k0, v0, Empty)
+        if w0 > l.w then
+            Node(l, w0, k0, v0, Empty)
         else
             l.joinNEH(self)
         end
     joinNEH(r: NonEmpty): NonEmpty =
-        Node(Empty, hk0, k0, v0, r)
-
-    combine(c: CombiningOp, r: TreapNode): TreapNode =
-        r.combineNE(self,c)
+        Node(Empty, w0, k0, v0, r)
+
     combineNE(l: NonEmpty, c: CombiningOp): TreapNode =
-        if hk0 < l.hk then
+        if w0 > l.w then
+            (lt, m, rt) = (l.splitL(k0), l.nodeWithKey(k0), l.splitR(k0))
+            c.leftAlone(lt).join(m.combineRootR(c, self)).join(c.leftAlone(rt))
+        else
             l.combineNEH(c,self)
-        else
-            (lt, m, rt) = (l.splitL(k0), l.nodeWithKey(k0), l.splitR(k0))
-            c.rightEmpty(lt).join(m.combineRootR(c, self)).join(c.rightEmpty(rt))
         end
     combineNEH(c: CombiningOp, r: NonEmpty): TreapNode = do
             (lt, m, rt) = (r.splitL(k0), r.nodeWithKey(k0), r.splitR(k0))
-            c.leftEmpty(lt).join(m.combineRootL(self, c)).join(c.leftEmpty(rt))
-        end
-
-    combineRootL(lr: Leaf1, c: CombiningOp): TreapNode = c.combine(lr,self)
-    combineRootR(c: CombiningOp, rr: Leaf1): TreapNode = c.combine(self,rr)
-
-    rootKey(defaultKey: ZZ32): ZZ32 = k0
-    rootValue(defaultValue: String): String = v0
+            c.rightAlone(lt).join(m.combineRootL(self, c)).join(c.rightAlone(rt))
+        end
 end
 
@@ -231 +249 @@
     Leaf1(randomZZ32(2147483647), key, val)
 
-object Node(left: TreapNode, hk0: ZZ32, k0: ZZ32, v0: String, right: TreapNode)
+object Node(left: TreapNode, w0: ZZ32, k0: ZZ32, v0: String, right: TreapNode)
         extends NonEmpty
-    getter isEmpty(): Boolean = false
     getter k(): ZZ32 = k0
     getter v(): String = v0
-    getter root(): Leaf1 = Leaf1(hk0, k0, v0)
-    getter hk(): ZZ32 = hk0
+    getter root(): Leaf1 = Leaf1(w0, k0, v0)
+    getter w(): ZZ32 = w0
     getter min(): TreapNode =
         if left.isEmpty then self.root else left.min end
@@ -247 +264 @@
         (l,r) = (left.mkString(withParens), right.mkString(withParens))
         if withParens then
-            "(" l ") <" hk0.asString ">" mid " (" r ")"
+            "(" l ") <" w0.asString ">" mid " (" r ")"
         else
             lh = if l.isEmpty then mid else l " " mid end
@@ -258 +275 @@
         if key < k0 then
             (l, match, r) = left.split(key)
-            (l, match, node(r, hk0, k0, v0, right))
+            (l, match, node(r, w0, k0, v0, right))
         elif key > k0 then
             (l, match, r) = right.split(key)
-            (node(left, hk0, k0, v0, l), match, r)
+            (node(left, w0, k0, v0, l), match, r)
         else
             (left, self, right)
@@ -271 +288 @@
             left.splitL(key)
         elif key > k0 then
-            Node(left, hk0, k0, v0, right.splitL(key))
+            Node(left, w0, k0, v0, right.splitL(key))
         else
             left
@@ -287 +304 @@
     splitR(key:ZZ32): TreapNode =
         if key < k0 then
-            Node(left.splitR(key), hk0, k0, v0, right)
+            Node(left.splitR(key), w0, k0, v0, right)
         elif key > k0 then
             right.splitR(key)
@@ -294 +311 @@
         end
 
-    join(r: TreapNode): TreapNode = r.joinNE(self)
     joinNE(l: NonEmpty): NonEmpty =
-        if hk0 > l.hk then
-            Node(l.join(left), hk0, k0, v0, right)
+        if w0 > l.w then
+            Node(l.join(left), w0, k0, v0, right)
         else
             l.joinNEH(self)
         end
     joinNEH(r: NonEmpty): NonEmpty =
-        Node(left, hk0, k0, v0, right.join(r))
-
-    combine(c: CombiningOp, r: TreapNode): TreapNode =
-        r.combineNE(self,c)
+        Node(left, w0, k0, v0, right.join(r))
+
     combineNE(l: NonEmpty, c: CombiningOp): TreapNode =
-        if hk0 < l.hk then
-            l.combineNEH(c,self)
-        else
+        if w0 > l.w then
             (lt, m, rt) = (l.splitL(k0), l.nodeWithKey(k0), l.splitR(k0))
             lt.combine(c,left).join(m.combineRootR(c, self.root)).join(rt.combine(c,right))
+        else
+            l.combineNEH(c,self)
         end
     combineNEH(c: CombiningOp, r: NonEmpty): TreapNode = do
@@ -317 +331 @@
             left.combine(c,lt).join(m.combineRootL(self.root, c)).join(right.combine(c,rt))
         end
-
-    combineRootL(lr: Leaf1, c: CombiningOp): TreapNode = c.combine(lr,self.root)
-    combineRootR(c: CombiningOp, rr: Leaf1): TreapNode = c.combine(self.root,rr)
-
-    rootKey(defaultKey: ZZ32): ZZ32 = k0
-    rootValue(defaultValue: String): String = v0
 end
 
 trait CombiningOp
-    leftEmpty(right: TreapNode): TreapNode
-    rightEmpty(left: TreapNode): TreapNode
+    rightAlone(right: TreapNode): TreapNode
+    leftAlone(left: TreapNode): TreapNode
     combine(leftArg: Leaf1, rightArg: Leaf1): TreapNode
 end
 
 object UnionOp extends CombiningOp
-    leftEmpty(right: TreapNode): TreapNode = right
-    rightEmpty(left: TreapNode): TreapNode = left
+    rightAlone(right: TreapNode): TreapNode = right
+    leftAlone(left: TreapNode): TreapNode = left
     combine(leftArg: Leaf1, rightArg: Leaf1): TreapNode = leftArg
 end
 
 object IntersectionOp extends CombiningOp
-    leftEmpty(right: TreapNode): TreapNode = Empty
-    rightEmpty(left: TreapNode): TreapNode = Empty
+    rightAlone(right: TreapNode): TreapNode = Empty
+    leftAlone(left: TreapNode): TreapNode = Empty
     combine(leftArg: Leaf1, rightArg: Leaf1): TreapNode = leftArg
 end
 
 object DifferenceOp extends CombiningOp
-    leftEmpty(right: TreapNode): TreapNode = Empty
-    rightEmpty(left: TreapNode): TreapNode = left
+    rightAlone(right: TreapNode): TreapNode = Empty
+    leftAlone(left: TreapNode): TreapNode = left
     combine(leftArg: Leaf1, rightArg: Leaf1): TreapNode = Empty
 end
 
 object SymdiffOp extends CombiningOp
-    leftEmpty(right: TreapNode): TreapNode = right
-    rightEmpty(left: TreapNode): TreapNode = left
+    rightAlone(right: TreapNode): TreapNode = right
+    leftAlone(left: TreapNode): TreapNode = left
     combine(leftArg: Leaf1, rightArg: Leaf1): TreapNode = Empty
 end