Changeset 2140

Show
Ignore:
Timestamp:
06/30/08 15:15:47 (4 months ago)
Author:
mspiegel
Message:

[Library] a working basic implementation of skip tree data structure, with test cases to probabilistically prove correctness. Also added list append to PureList?.fsi and PureList?.fss.

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • trunk/Library/PureList.fsi

    r1832 r2140  
    5959      by the elements of %f% *) 
    6060  append(f:List[\E\]): List[\E\] 
     61  (** the operator %||% performs the %append% operation *) 
     62  opr ||(self, other:List[\E\]): List[\E\]      
    6163  (** %addLeft% and %addRight% add an element to the left or right of 
    62       the list, respectively *) 
     64      the list, respectively *)       
    6365  addLeft(e:E):List[\E\] 
    6466  addRight(e:E):List[\E\] 

  • trunk/Library/PureList.fss

    r1825 r2140  
    5252  getter extractRight(): Maybe[\(List[\E\],E)\] 
    5353  append(f:List[\E\]): List[\E\] 
     54  opr ||(self, other:List[\E\]): List[\E\]      
    5455  addLeft(e:E):List[\E\] 
    5556  addRight(e:E):List[\E\] 
    …… 
    129130      it.generate[\R\](r,body) 
    130131  seq(self): SequentialGenerator[\E\] = SeqListGenerator[\E\](it) 
     132  opr ||(self, other:List[\E\]): List[\E\] = append(other)      
    131133  append(f:List[\E\]): PureList[\E\] = 
    132134      append(f.generate[\PureList[\E\]\](PLConcat[\E\],singleton[\E\])) 

  • trunk/Library/incomplete/SkipTree.fsi

    r2137 r2140  
    2020 
    2121trait SkipTree[\Key,Value\] 
     22 
     23    getter toString():String 
     24 
     25    opr |self| : ZZ32 
    2226 
    2327    (** Takes a querykey as input and returns either a Just[\Value\] 

  • trunk/Library/incomplete/SkipTree.fss

    r2139 r2140  
    1717 
    1818component SkipTree 
    19 import List.{...} 
     19import PureList.{...} 
    2020 
    2121 
    …… 
    2323 
    2424trait SkipTree[\Key,Value\] 
     25 
     26    getter toString():String 
     27 
     28    opr |self| : ZZ32 
    2529 
    2630    (** Takes a querykey as input and returns either a %Just[\Value\]% 
    …… 
    5559     **)     
    5660    verify():()     
     61     
     62 
    5763 
    5864end 
    …… 
    6167 
    6268object EmptySkipTree[\Key,Value\] extends { SkipTree[\Key,Value\] } 
     69 
     70    getter toString():String = "(EMPTY)" 
     71 
     72    opr |self| : ZZ32 = 0 
    6373 
    6474    find(querykey : Key) : Maybe[\Value\] = Nothing[\Value\] 
    …… 
    6777        newheight = randomLevel() 
    6878        root = LeafNode[\Key,Value\](newkey, newvalue, newheight)      
    69         NonEmptySkipTree[\Key,Value\](root')         
     79        NonEmptySkipTree[\Key,Value\](root)         
    7080    end 
    7181     
    7282    verify():() = () 
     83     
    7384 
    7485end 
    …… 
    7788 
    7889object NonEmptySkipTree[\Key,Value\](root : Node[\Key,Value\]) extends { SkipTree[\Key,Value\] } 
     90 
     91    getter toString():String = root.toString() 
     92 
     93    opr |self| : ZZ32 = |root| 
    7994 
    8095    find(querykey : Key) : Maybe[\Value\] = root.find(querykey) 
    …… 
    90105    end 
    91106     
    92     verify():() = root.verify() 
     107    verify():() = root.verify()    
    93108    
    94109end 
    …… 
    104119 
    105120    getter toString() : String = keys "" values "" children " h" height 
     121 
     122    opr |self| : ZZ32 = |keys| + children.generate[\Number\](SumReduction,  
     123        fn (child) => typecase child of 
     124                Just[\Node[\Key,Value\]\] => |child.get()| 
     125                else => 0 end) 
     126     
     127 
     128    opr =(self, other:Node[\Key,Value\]): Boolean = 
     129        if self SEQV other then true 
     130        else 
     131            (keys = other.keys AND values = other.values  
     132            AND children = other.children AND height = other.height) 
     133        end 
    106134 
    107135 
    …… 
    117145            childIndex = insertionPoint(parentIndex) 
    118146            typecase child = children[childIndex] of 
    119                 Just[\Value\] => child.get().find(querykey) 
     147                Just[\Node[\Key,Value\]\] => child.get().find(querykey) 
    120148                else => Nothing[\Value\] 
    121149            end 
    …… 
    147175        typecase child = children[i] of 
    148176            Just[\Node[\Key,Value\]\] =>  
    149                 newchild = child.get().insert(newkey,newvalue,newheight) 
     177                newchild = Just[\Node[\Key,Value\]\](child.get().insert(newkey,newvalue,newheight)) 
    150178            else =>  
    151                 newchild = LeafNode[\Key,Value\](newkey,newvalue,newheight) 
    152         end 
    153         newchildren = children[0 # i] || <| newchild |> || children[(i + 1):] 
     179                newchild = Just[\Node[\Key,Value\]\](LeafNode[\Key,Value\](newkey,newvalue,newheight)) 
     180        end 
     181        newchildren = children[0 # i].addRight(newchild) || children[(i + 1) : (|children| - 1)] 
    154182        Node[\Key,Value\](keys,values,newchildren,height) 
    155183    end 
    …… 
    159187    private insertEqualHeight(newkey:Key, newvalue:Value) : Node[\Key,Value\] = do 
    160188        i = insertionPoint(binarySearch[\Key\](keys,newkey)) 
    161         newkeys = keys[0#i] || <| newkey |> || keys[i:] 
    162         newvalues = values[0#i] || <| newvalue |> || values[i:] 
     189        newkeys = keys[0#i].addRight(newkey) || keys[i:(|keys| - 1)] 
     190        newvalues = values[0#i].addRight(newvalue) || values[i : (|values| - 1)] 
    163191        (newleft, newright) =  
    164                 (filter(newkey, children[i], true), 
    165                  filter(newkey, children[i], false)) 
    166         leftchildren = children[0#i] || <|[\Maybe[\Node[\Key,Value\]\]\] newleft |> 
    167         rightchildren = <|[\Maybe[\Node[\Key,Value\]\]\] newright |> || children[(i + 1):] 
     192                (filterTarget(newkey, children[i], true), 
     193                 filterTarget(newkey, children[i], false)) 
     194        leftchildren = children[0#i].addRight(newleft) 
     195        rightchildren = children[(i + 1):(|children| - 1)].addLeft(newright) 
    168196        newchildren =  leftchildren || rightchildren 
    169197        Node[\Key,Value\](newkeys,newvalues,newchildren,height) 
    …… 
    175203        newkeys     = singleton[\Key\](newkey) 
    176204        newvalues   = singleton[\Value\](newvalue) 
    177         (newleft,newright) = (filter(newkey, Just[\Node[\Key,Value\]\](self), true), 
    178                          filter(newkey, Just[\Node[\Key,Value\]\](self), false)) 
    179         newchildren = <| newleft, newright |> 
     205        (newleft,newright) = (filterTarget(newkey, Just[\Node[\Key,Value\]\](self), true), 
     206                         filterTarget(newkey, Just[\Node[\Key,Value\]\](self), false)) 
     207        newchildren = <|[\Maybe[\Node[\Key,Value\]\]\] newleft, newright |> 
    180208        Node[\Key,Value\](newkeys,newvalues,newchildren,newheight) 
    181209    end 
    182210 
    183211 
    184     private filter(newkey : Key,  
     212    private filterTarget(newkey : Key,  
    185213                   target : Maybe[\Node[\Key,Value\]\], 
    186214                   lessThanOrEquals : Boolean) 
    …… 
    226254            newkeys = keys[0 # insertIndex] 
    227255            newvalues = values[0 # insertIndex] 
    228             newchildren = children[0 # insertIndex] || <| filteredChild |> 
     256            newchildren = children[0 # insertIndex].addRight(filteredChild) 
    229257            Just[\Node[\Key,Value\]\](Node[\Key,Value\](newkeys,newvalues,newchildren,height)) 
    230258        end 
    …… 
    235263                              filteredChild : Maybe[\Node[\Key,Value\]\])  
    236264                             : Maybe[\Node[\Key,Value\]\] = do 
    237         if insertIndex = keys.size() then 
     265        if insertIndex = |keys| then 
    238266            filteredChild 
    239267        else 
    240             newkeys = keys[insertIndex:] 
    241             newvalues = values[insertIndex:] 
    242             newchildren = <|[\Maybe[\Node[\Key,Value\]\]\] filteredChild |> || children[(insertIndex + 1):]  
     268            newkeys = keys[insertIndex : (|keys| - 1)] 
     269            newvalues = values[insertIndex : (|values| - 1)] 
     270            newchildren = children[(insertIndex + 1) : |children| - 1].addLeft(filteredChild)  
    243271            Just[\Node[\Key,Value\]\](Node[\Key,Value\](newkeys,newvalues,newchildren,height)) 
    244272        end 
    …… 
    264292     
    265293    largestKey():Key = do 
    266         typecase child = children[children.size() - 1] of     
     294        typecase child = children[|children| - 1] of     
    267295            Just[\Node[\Key,Value\]\] => child.get().largestKey() 
    268             else => keys[keys.size() - 1] 
     296            else => keys[|keys| - 1] 
    269297        end 
    270298    end 
    …… 
    285313            fail(toString() " : Size of children is not equal to size of keys plus one") 
    286314        end 
    287         for i <- 0 # (keys.size() - 1) do 
     315        for i <- 0 # (|keys| - 1) do 
    288316            if keys[i] >= keys[i + 1] then 
    289317                fail(toString() " : Keys " keys[i] " and " keys[i + 1] " are not in sorted order") 
    290318            end 
    291319        end 
    292         for i <- 0 # keys.size() do         
     320        for i <- 0 # |keys| do         
    293321            typecase child = children[i] of     
    294322                Just[\Node[\Key,Value\]\] => do 
    …… 
    309337        end 
    310338        (* recusively check non-empty children *) 
    311         for i <- 0 # children.size() do 
     339        for i <- 0 # |children| do 
    312340            typecase child = children[i] of     
    313341                Just[\Node[\Key,Value\]\] => child.get().verify() 
    …… 
    346374  *      otherwise, (-(insertion point) - 1). The insertion point is defined 
    347375  *      as the point at which the key would be inserted into the list:  
    348   *      the index of the first element greater than the key, or list.size() 
     376  *      the index of the first element greater than the key, or |list| 
    349377  *      if all elements in the list are less than the specified key.  
    350378  *      Note that this guarantees that the return value will be %>=% 0 
    …… 
    352380  **) 
    353381binarySearch[\T\](list : List[\T\], key : T) : ZZ32 = do 
    354     if list.size() <= 8 then (* base case *) 
    355         index:ZZ32 := - list.size() - 1 
     382    if |list| <= 8 then (* base case *) 
     383        index:ZZ32 := - |list| - 1 
    356384        label loop 
    357             for i <- seq(0 # list.size()) do 
     385            for i <- seq(0 # |list|) do 
    358386                if list[i] = key then 
    359387                    index := i 
    …… 
    367395        index 
    368396    else (* recursive step *) 
    369         split = list.size() DIV 2 
     397        split = |list| DIV 2 
    370398        if (key < list[split]) then 
    371399            binarySearch[\T\](list[0 # split], key) 
    372400        else 
    373             right = binarySearch[\T\](list[split:], key) 
     401            right = binarySearch[\T\](list[split:(|list| - 1)], key) 
    374402            if right >= 0 then right + split 
    375403            else right - split end 

  • trunk/Library/incomplete/SkipTreeTest.fss

    r2138 r2140  
    1919component SkipTreeTest 
    2020import SkipTree.{...} 
    21 import List.{...} 
     21import PureList.{...} 
    2222export Executable 
    2323 
    24 run(args:String...):() = do 
    25     leaf = LeafNode[\ZZ32,ZZ32\](7,1,3) 
    26     println leaf.toString() 
    27     println leaf.find(3) 
    28     println leaf.find(7) 
    29     testList = <| 5, 10, 15, 20 |> 
    30     assert(binarySearch[\ZZ32\](testList, 2), -1) 
    31     assert(binarySearch[\ZZ32\](testList, 5), 0) 
    32     assert(binarySearch[\ZZ32\](testList, 7), -2) 
    33     assert(binarySearch[\ZZ32\](testList, 10), 1) 
    34     assert(binarySearch[\ZZ32\](testList, 13), -3) 
    35     assert(binarySearch[\ZZ32\](testList, 15), 2) 
    36     assert(binarySearch[\ZZ32\](testList, 17), -4) 
    37     assert(binarySearch[\ZZ32\](testList, 20), 3) 
    38     assert(binarySearch[\ZZ32\](testList, 23), -5) 
     24    testBinarySearch():() = do 
     25        testList = <| 5, 10, 15, 20 |> 
     26        assert(binarySearch[\ZZ32\](testList, 2), -1) 
     27        assert(binarySearch[\ZZ32\](testList, 5), 0) 
     28        assert(binarySearch[\ZZ32\](testList, 7), -2) 
     29        assert(binarySearch[\ZZ32\](testList, 10), 1) 
     30        assert(binarySearch[\ZZ32\](testList, 13), -3) 
     31        assert(binarySearch[\ZZ32\](testList, 15), 2) 
     32        assert(binarySearch[\ZZ32\](testList, 17), -4) 
     33        assert(binarySearch[\ZZ32\](testList, 20), 3) 
     34        assert(binarySearch[\ZZ32\](testList, 23), -5)     
     35    end 
    3936 
    40     println leaf.insert(5,2,4).toString() 
    41     foo = leaf.insert(5,2,3) 
    42     println foo.toString() 
    43     foo.verify(); 
    44      
    45     (** tree = SkipTree[\ZZ32,ZZ32\](Just[\Node[\ZZ32,ZZ32\]\](leaf)) *) 
     37    testLeafInsert1():() = do 
     38        a = LeafNode[\ZZ32,String\](7,"foo",3) 
     39        observed = a.insert(5, "bar", 2) 
     40 
     41        keys = <| 7 |> 
     42        values = <| "foo" |> 
     43        children = <|[\Maybe[\Node[\ZZ32,String\]\]\]  
     44            Just[\Node[\ZZ32,String\]\](LeafNode[\ZZ32,String\](5,"bar",2)),  
     45            Nothing[\Node[\ZZ32,String\]\] |> 
     46         
     47        expected = Node[\ZZ32,String\](keys,values,children,3) 
     48         
     49        assert(observed,expected) 
     50             
     51    end 
     52 
     53    testLeafInsert2():() = do 
     54        a = LeafNode[\ZZ32,String\](7,"foo",3) 
     55        observed = a.insert(5, "bar", 3) 
     56 
     57        keys = <| 5,7 |> 
     58        values = <| "bar","foo" |> 
     59        children = <|[\Maybe[\Node[\ZZ32,String\]\]\]  
     60            Nothing[\Node[\ZZ32,String\]\],  
     61            Nothing[\Node[\ZZ32,String\]\], 
     62            Nothing[\Node[\ZZ32,String\]\] |> 
     63         
     64        expected = Node[\ZZ32,String\](keys,values,children,3) 
     65         
     66        assert(observed,expected) 
     67             
     68    end 
     69 
     70    testLeafInsert3():() = do 
     71        a = LeafNode[\ZZ32,String\](7,"foo",3) 
     72        observed = a.insert(5, "bar", 4) 
     73 
     74        keys = <| 5 |> 
     75        values = <| "bar" |> 
     76        children = <|[\Maybe[\Node[\ZZ32,String\]\]\]  
     77             Nothing[\Node[\ZZ32,String\]\], 
     78             Just[\Node[\ZZ32,String\]\](LeafNode[\ZZ32,String\](7,"foo",3)) |> 
     79 
     80         
     81        expected = Node[\ZZ32,String\](keys,values,children,4) 
     82         
     83        assert(observed,expected) 
     84             
     85    end 
    4686 
    4787 
    4888 
     89    testProbabilisticSkipTreeInsert():() = do 
     90        for i <- 1 # 4 do 
     91            tree:SkipTree[\ZZ32,ZZ32\] := EmptySkipTree[\ZZ32,ZZ32\] 
     92            for j <- seq(1 # narrow(|\ random(64) /|)) do 
     93                newkey = narrow(|\ random(1024) /|) 
     94                newvalue = newkey 
     95                oldvalue = tree.find(newkey) 
     96                newTree = tree.insert(newkey, newvalue) 
     97                newTree.verify() 
     98                if oldvalue.isEmpty() AND (|tree| + 1 =/= |newTree|) then 
     99                    fail("Skip Tree has not grown on attempt to insert a new key!") 
     100                elif NOT oldvalue.isEmpty() AND (|tree| =/= |newTree|) then 
     101                    fail("Skip Tree has grown on attempt to insert an existing key!") 
     102                end  
     103                tree := newTree 
     104            end 
     105        end 
     106    end 
    49107 
    50 end (* run(args:String...):() *) 
     108 
     109    run(args:String...):() = do 
     110        testBinarySearch() 
     111        testLeafInsert1() 
     112        testLeafInsert2() 
     113        testLeafInsert3() 
     114        testProbabilisticSkipTreeInsert() 
     115 
     116 
     117    end 
    51118 
    52119end (* component SkipTreeTest *)