Changeset 2137

Timestamp:

06/30/08 07:23:42 (3 months ago)

Author:

mspiegel

Message:

Implemented verify() method of skip tree data structures. test suite for skip trees is almost complete.

Files:

• trunk/Library/incomplete/SkipTree.fsi (modified) (1 diff)
• trunk/Library/incomplete/SkipTree.fss (modified) (5 diffs)
• trunk/Library/incomplete/SkipTreeTest.fss (modified) (2 diffs)

trunk/Library/incomplete/SkipTree.fsi

@@ -40 +40 @@
-    randomLevel():ZZ32
-
+    (**
+     * The verify method will throw an error
+     * if this structure does not satisfy the properties
+     * of a Skip Tree.
+     **)    
+    verify():()
+
-end (* trait SkipTree[\Key,Value\] *)
-

trunk/Library/incomplete/SkipTree.fss

@@ -48 +48 @@
-        level
-    end
+    
+    (**
+     * The verify method will throw an error
+     * if this structure does not satisfy the properties
+     * of a Skip Tree.
+     **)    
+    verify():()    
-
-end (* trait SkipTree[\Key,Value\] *)
@@ -66 +73 @@
-    end
-    
+    verify():() = root.verify()
+   
-end
-
@@ -77 +86 @@
-        NonEmptySkipTree[\Key,Value\](root')        
-    end
+    
+    verify():() = ()
-
-end
@@ -232 +243 @@
-        if index >= 0 then index
-        else |index| - 1 end
+    end
+
+    smallestKey():Key = do
+        typecase child = children[0] of    
+            Just[\Node[\Key,Value\]\] => child.get().smallestKey()
+            else => keys[0]
+        end
+    end
+    
+    largestKey():Key = do
+        typecase child = children[children.size() - 1] of    
+            Just[\Node[\Key,Value\]\] => child.get().largestKey()
+            else => keys[keys.size() - 1]
+        end
+    end
+
+    (**
+     * The verify method will throw an error
+     * if this structure does not satisfy the properties
+     * of a Skip Tree.
+     **)        
+    verify():() = do
+        if height <= 0 then
+            fail(toString() " : All nodes must have a height that is a positive integer")
+        end
+        if |keys| =/= |values| then
+            fail(toString() " : Size of keys is not equal to size of values")
+        end
+        if |keys| + 1 =/= |children| then
+            fail(toString() " : Size of children is not equal to size of keys plus one")
+        end
+        for i <- 0 # (keys.size() - 1) do
+            if keys[i] >= keys[i + 1] then
+                fail(toString() " : Keys " keys[i] " and " keys[i + 1] " are not in sorted order")
+            end
+        end
+        for i <- 0 # keys.size() do        
+            typecase child = children[i] of    
+                Just[\Node[\Key,Value\]\] => do
+                    if child.get().largestKey() > keys[i] then
+                        fail(toString() " : " child.get().largestKey() " > " keys[i])
+                    end
+                end
+                else => ()
+            end
+            typecase child = children[i + 1] of    
+                Just[\Node[\Key,Value\]\] => do
+                    if child.get().smallestKey() < keys[i] then
+                        fail(toString() " : " child.get().smallestKey() " < " keys[i])
+                    end
+                end
+                else => ()
+            end            
+        end
+        (* recusively check non-empty children *)
+        for i <- 0 # children.size() do
+            typecase child = children[i] of    
+                Just[\Node[\Key,Value\]\] => child.get().verify()
+                else => ()
+            end        
+        end
-    end
-    
@@ -269 +341 @@
-  **)
-binarySearch[\T\](list : List[\T\], key : T) : ZZ32 = do
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    else (* recursive step *)
-        split = list.size() DIV 2

trunk/Library/incomplete/SkipTreeTest.fss

@@ -15 +15 @@
-    trademarks of Sun Microsystems, Inc. in the U.S. and other countries.
- ******************************************************************************)
+
-
-component SkipTreeTest
@@ -38 +39 @@
-
-    println leaf.insert(5,2,4).toString()
+    foo = leaf.insert(5,2,3)
+    println foo.toString()
+    foo.verify();
+    
-    (** tree = SkipTree[\ZZ32,ZZ32\](Just[\Node[\ZZ32,ZZ32\]\](leaf)) *)
-