Changeset 2138

Show
Ignore:
Timestamp:
06/30/08 07:23:48 (4 months ago)
Author:
mspiegel
Message:

[Library] replaced calls to singleton() List constructors with List generator notation <| |> in SkipTree?.fss and SkipTreeTest?.fss.

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • trunk/Library/incomplete/SkipTree.fss

    r2137 r2138  
    6565    insert(newkey : Key, newvalue : Value) : SkipTree[\Key,Value\] = do 
    6666        newheight = randomLevel() 
    67         typecase exists = root.find(newkey) of 
    68             Just[\Value\] => self 
    69             else => 
    70                 root' = root.insert(newkey,newvalue,newheight) 
    71                 NonEmptySkipTree[\Key,Value\](root') 
     67        if root.find(newkey).isEmpty() then 
     68            root' = root.insert(newkey,newvalue,newheight) 
     69            NonEmptySkipTree[\Key,Value\](root') 
     70        else 
     71            self 
    7272        end 
    7373    end 
    …… 
    148148    private insertBelowHeight(newkey:Key, newvalue:Value, newheight:ZZ32) : Node[\Key,Value\] = do 
    149149        i = insertionPoint(binarySearch[\Key\](keys,newkey)) 
    150         newchild = typecase child = children[i] of     
     150        newchild = typecase child = children[i] of 
    151151            Just[\Node[\Key,Value\]\] => child.get().insert(newkey,newvalue,newheight) 
    152152            else => LeafNode[\Key,Value\](newkey,newvalue,newheight) 
    153153        end 
    154         newchildren = children[0 # i].addRight(Just[\Node[\Key,Value\]\](newchild)) || children[(i + 1):] 
     154        newchildren = children[0 # i] || <| newchild |> || children[(i + 1):] 
    155155        Node[\Key,Value\](keys,values,newchildren,height) 
    156156    end 
    …… 
    159159    private insertEqualHeight(newkey:Key, newvalue:Value) : Node[\Key,Value\] = do 
    160160        i = insertionPoint(binarySearch[\Key\](keys,newkey)) 
    161         newkeys = keys[0#i] || singleton[\Key\](newkey) || keys[i:] 
    162         newvalues = values[0#i] || singleton[\Value\](newvalue) || values[i:] 
     161        newkeys = keys[0#i] || <| newkey |> || keys[i:] 
     162        newvalues = values[0#i] || <| newvalue |> || values[i:] 
    163163        (newleft, newright) =  
    164164                (filterChild(newkey, children[i], true), 
    165165                 filterChild(newkey, children[i], false)) 
    166         leftchildren = children[0#i].addRight(newleft) 
    167         rightchildren = children[(i + 1):].addLeft(newright) 
     166        leftchildren = children[0#i] || <|[\Maybe[\Node[\Key,Value\]\]\] newleft |> 
     167        rightchildren = <|[\Maybe[\Node[\Key,Value\]\]\] newright |> || children[(i + 1):] 
    168168        newchildren =  leftchildren || rightchildren 
    169169        Node[\Key,Value\](newkeys,newvalues,newchildren,height) 
    …… 
    176176        (newleft,newright) = (filterChild(newkey, Just[\Node[\Key,Value\]\](self), true), 
    177177                         filterChild(newkey, Just[\Node[\Key,Value\]\](self), false)) 
    178         newchildren = emptyList[\Maybe[\Node[\Key,Value\]\]\]().addRight(newleft).addRight(newright) 
     178        newchildren = <| newleft, newright |> 
    179179        Node[\Key,Value\](newkeys,newvalues,newchildren,newheight) 
    180180    end 
    …… 
    219219            newkeys = keys[0 # insertIndex] 
    220220            newvalues = values[0 # insertIndex] 
    221             newchildren = children[0 # insertIndex].addRight(filteredChild)  
     221            newchildren = children[0 # insertIndex] || <| filteredChild |> 
    222222            Just[\Node[\Key,Value\]\](Node[\Key,Value\](newkeys,newvalues,newchildren,height)) 
    223223        end 
    …… 
    232232            newkeys = keys[insertIndex:] 
    233233            newvalues = values[insertIndex:] 
    234             newchildren = children[(insertIndex + 1):].addLeft(filteredChild)  
     234            newchildren = <|[\Maybe[\Node[\Key,Value\]\]\] filteredChild |> || children[(insertIndex + 1):]  
    235235            Just[\Node[\Key,Value\]\](Node[\Key,Value\](newkeys,newvalues,newchildren,height)) 
    236236        end 
    …… 
    309309 
    310310LeafNode[\Key,Value\](key : Key, val : Value, height : ZZ32) = do 
    311     keys = singleton[\Key\](key) 
    312     values = singleton[\Value\](val) 
    313     child = singleton[\Maybe[\Node[\Key,Value\]\]\](Nothing[\Node[\Key,Value\]\]) 
    314     children = child.append(child) 
     311    keys = <| key |> 
     312    values = <| val |> 
     313    child = <|[\Maybe[\Node[\Key,Value\]\]\] Nothing[\Node[\Key,Value\]\] |> 
     314    children = child || child 
    315315    Node[\Key,Value\](keys,values,children,height)  
    316316end (** LeafNode[\Key,Value\](key : Key, val : Value, height : ZZ32) **) 
    …… 
    347347                if list[i] = key then 
    348348                    index := i 
    349                     exit loop 
     349                    exit 
    350350                elif list[i] > key then 
    351351                    index := -i - 1 
    352                     exit loop                     
     352                    exit 
    353353                end 
    354354           end 

  • trunk/Library/incomplete/SkipTreeTest.fss

    r2137 r2138  
    2727    println leaf.find(3) 
    2828    println leaf.find(7) 
    29     testList = emptyList[\ZZ32\]().addRight(5).addRight(10).addRight(15).addRight(20) 
     29    testList = <| 5, 10, 15, 20 |> 
    3030    assert(binarySearch[\ZZ32\](testList, 2), -1) 
    3131    assert(binarySearch[\ZZ32\](testList, 5), 0)