Changeset 2139

Show
Ignore:
Timestamp:
06/30/08 10:43:04 (3 months ago)
Author:
mspiegel
Message:

[library] some style cleanup of SkipTree?.fss based on experiments with fortex.

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • trunk/Library/incomplete/SkipTree.fss

    r2138 r2139  
    2424trait SkipTree[\Key,Value\] 
    2525 
    26     (** Takes a querykey as input and returns either a Just[\Value\] 
    27       * object if the (key,value) pair lives in this map, or 
    28       * returns Nothing[\Value\] otherwise. 
     26    (** Takes a querykey as input and returns either a %Just[\Value\]% 
     27      * object if the %(key, val)% pair lives in this map, or 
     28      * returns %Nothing[\Value\]% otherwise. 
    2929      *) 
    3030    find(querykey : Key) : Maybe[\Value\] 
    3131 
    3232    (** Takes a newkey and newvalue as input and returns a  
    33       * new skip tree with the (key, value) pair inserted. 
     33      * new skip tree with the %(key, val)% pair inserted. 
    3434      * Currently, if newkey already exists in the tree, 
    35       * then this operation does not insert (key, newvalue) 
     35      * then this operation does not insert %(key, val)% 
    3636      * into the tree. 
    3737      *) 
    …… 
    3939 
    4040    (** 
    41      *  Return a random level >= 1 with a negative binomial distribution. 
     41     *  Return a random level %>=% 1 with a negative binomial distribution. 
    4242     *) 
    4343    randomLevel():ZZ32 = do 
    …… 
    5656    verify():()     
    5757 
    58 end (* trait SkipTree[\Key,Value\] *) 
     58end 
     59 
     60 
     61 
     62object EmptySkipTree[\Key,Value\] extends { SkipTree[\Key,Value\] } 
     63 
     64    find(querykey : Key) : Maybe[\Value\] = Nothing[\Value\] 
     65     
     66    insert(newkey : Key, newvalue : Value) : SkipTree[\Key,Value\] = do 
     67        newheight = randomLevel() 
     68        root = LeafNode[\Key,Value\](newkey, newvalue, newheight)      
     69        NonEmptySkipTree[\Key,Value\](root')         
     70    end 
     71     
     72    verify():() = () 
     73 
     74end 
     75 
    5976 
    6077 
    …… 
    7794end 
    7895 
    79 object EmptySkipTree[\Key,Value\] extends { SkipTree[\Key,Value\] } 
    80  
    81     find(querykey : Key) : Maybe[\Value\] = Nothing[\Value\] 
    82      
    83     insert(newkey : Key, newvalue : Value) : SkipTree[\Key,Value\] = do 
    84         newheight = randomLevel() 
    85         root = LeafNode[\Key,Value\](newkey, newvalue, newheight)      
    86         NonEmptySkipTree[\Key,Value\](root')         
    87     end 
    88      
    89     verify():() = () 
    90  
    91 end 
    92  
    93  
    94 object Filter[\Key\](pivot : Key, lessThanOrEquals : Boolean) 
    95  
    96     filter(query : Key) : Boolean = do 
    97         if lessThanOrEquals then 
    98             query <= pivot 
    99         else 
    100             query > pivot 
    101         end 
    102     end 
    103      
    104 end 
     96 
     97 
    10598 
    10699object Node[\Key,Value\](keys     : List[\Key\], 
    …… 
    109102                         height   : ZZ32) 
    110103 
     104 
    111105    getter toString() : String = keys "" values "" children " h" height 
    112106 
    113     (** Takes a querykey as input and returns either a Just[\Value\] 
    114       * object if the (key,value) pair lives in this map, or 
    115       * returns Nothing[\Value\] otherwise. 
     107 
     108    (** Takes a querykey as input and returns either a %Just[\Value\]% 
     109      * object if the %(key,val)% pair lives in this map, or 
     110      * returns %Nothing[\Value\]% otherwise. 
    116111      *)     
    117112    find(querykey : Key) : Maybe[\Value\] = do 
    …… 
    130125 
    131126    (** Takes a newkey and newvalue as input and returns a  
    132       * new node with the (key, value) pair inserted. 
     127      * new node with the %(key, val)% pair inserted. 
    133128      * Currently, if newkey already exists in the tree, 
    134       * then this operation does not insert (key, newvalue) 
     129      * then this operation does not insert %(key, val)% 
    135130      * into the tree.       
    136131      *) 
    …… 
    145140    end 
    146141 
    147     (* perform the insert operation when self.height > newheight *) 
     142 
     143    (** perform the insert operation when %self.height > newheight% *) 
    148144    private insertBelowHeight(newkey:Key, newvalue:Value, newheight:ZZ32) : Node[\Key,Value\] = do 
    149145        i = insertionPoint(binarySearch[\Key\](keys,newkey)) 
    150         newchild = typecase child = children[i] of 
    151             Just[\Node[\Key,Value\]\] => child.get().insert(newkey,newvalue,newheight) 
    152             else => LeafNode[\Key,Value\](newkey,newvalue,newheight) 
     146        newchild:Maybe[\Node[\Key,Value\]\] 
     147        typecase child = children[i] of 
     148            Just[\Node[\Key,Value\]\] =>  
     149                newchild = child.get().insert(newkey,newvalue,newheight) 
     150            else =>  
     151                newchild = LeafNode[\Key,Value\](newkey,newvalue,newheight) 
    153152        end 
    154153        newchildren = children[0 # i] || <| newchild |> || children[(i + 1):] 
    …… 
    156155    end 
    157156 
    158     (* perform the insert operation when self.height = newheight *) 
     157 
     158    (** perform the insert operation when %self.height = newheight% *) 
    159159    private insertEqualHeight(newkey:Key, newvalue:Value) : Node[\Key,Value\] = do 
    160160        i = insertionPoint(binarySearch[\Key\](keys,newkey)) 
    …… 
    162162        newvalues = values[0#i] || <| newvalue |> || values[i:] 
    163163        (newleft, newright) =  
    164                 (filterChild(newkey, children[i], true), 
    165                  filterChild(newkey, children[i], false)) 
     164                (filter(newkey, children[i], true), 
     165                 filter(newkey, children[i], false)) 
    166166        leftchildren = children[0#i] || <|[\Maybe[\Node[\Key,Value\]\]\] newleft |> 
    167167        rightchildren = <|[\Maybe[\Node[\Key,Value\]\]\] newright |> || children[(i + 1):] 
    …… 
    170170    end 
    171171 
    172     (* perform the insert operation when self.height < newheight *) 
     172 
     173    (** perform the insert operation when %self.height < newheight% *) 
    173174    private insertAboveHeight(newkey:Key,newvalue:Value,newheight:ZZ32) : Node[\Key,Value\] = do 
    174175        newkeys     = singleton[\Key\](newkey) 
    175176        newvalues   = singleton[\Value\](newvalue) 
    176         (newleft,newright) = (filterChild(newkey, Just[\Node[\Key,Value\]\](self), true), 
    177                          filterChild(newkey, Just[\Node[\Key,Value\]\](self), false)) 
     177        (newleft,newright) = (filter(newkey, Just[\Node[\Key,Value\]\](self), true), 
     178                         filter(newkey, Just[\Node[\Key,Value\]\](self), false)) 
    178179        newchildren = <| newleft, newright |> 
    179180        Node[\Key,Value\](newkeys,newvalues,newchildren,newheight) 
    180181    end 
    181182 
    182     private filterChild(newkey : Key,  
    183                         target : Maybe[\Node[\Key,Value\]\], 
    184                         lessThanOrEquals : Boolean) 
    185                        : Maybe[\Node[\Key,Value\]\] = do 
     183 
     184    private filter(newkey : Key,  
     185                   target : Maybe[\Node[\Key,Value\]\], 
     186                   lessThanOrEquals : Boolean) 
     187                  : Maybe[\Node[\Key,Value\]\] = do 
     188        filter = Filter[\Key\](newkey, lessThanOrEquals)                    
    186189        typecase target of 
    187190            Just[\Node[\Key,Value\]\] => 
    188                 filter = Filter[\Key\](newkey, lessThanOrEquals)  
    189191                target.get().applyFilter(filter) 
    190192            else => 
    …… 
    193195    end 
    194196 
     197 
    195198    private applyFilter(filter : Filter[\Key\]) : Maybe[\Node[\Key,Value\]\] = do 
    196199        parentIndex = binarySearch[\Key\](keys, filter.pivot) 
    …… 
    200203            insertionPoint(parentIndex) 
    201204        end 
    202         filteredChild = typecase child = children[childIndex] of     
    203             Just[\Node[\Key,Value\]\] => child.get().applyFilter(filter) 
    204             else => child 
     205        filteredChild : Maybe[\Node[\Key,Value\]\] 
     206        typecase child = children[childIndex] of     
     207            Just[\Node[\Key,Value\]\] =>  
     208                filteredChild = child.get().applyFilter(filter) 
     209            else =>  
     210                filteredChild = child 
    205211        end 
    206212        if filter.lessThanOrEquals then 
    …… 
    211217    end 
    212218 
     219 
    213220    private filterLessThanOrEquals(insertIndex   : ZZ32,  
    214                            filteredChild : Maybe[\Node[\Key,Value\]\])  
    215                           : Maybe[\Node[\Key,Value\]\] = do 
     221                                   filteredChild : Maybe[\Node[\Key,Value\]\])  
     222                                  : Maybe[\Node[\Key,Value\]\] = do 
    216223        if insertIndex = 0 then 
    217224            filteredChild 
    …… 
    223230        end 
    224231    end 
     232 
    225233     
    226234    private filterGreaterThan(insertIndex   : ZZ32,  
    227                       filteredChild : Maybe[\Node[\Key,Value\]\])  
    228                      : Maybe[\Node[\Key,Value\]\] = do 
     235                              filteredChild : Maybe[\Node[\Key,Value\]\])  
     236                             : Maybe[\Node[\Key,Value\]\] = do 
    229237        if insertIndex = keys.size() then 
    230238            filteredChild 
    …… 
    236244        end 
    237245    end     
    238      
    239     (* transform the index from binarySearch(list, key) 
     246 
     247     
     248    (** transform the index from %binarySearch[\T\](list, key)% 
    240249     * into an insertion point. 
    241      *) 
     250     **) 
    242251    private insertionPoint(index : ZZ32) : ZZ32 = do 
    243252        if index >= 0 then index 
    244253        else |index| - 1 end 
    245254    end 
     255 
    246256 
    247257    smallestKey():Key = do 
    …… 
    251261        end 
    252262    end 
     263 
    253264     
    254265    largestKey():Key = do 
    …… 
    306317    end 
    307318     
    308 end (** object Node[\Key,Value\] **) 
     319end 
    309320 
    310321LeafNode[\Key,Value\](key : Key, val : Value, height : ZZ32) = do 
    …… 
    314325    children = child || child 
    315326    Node[\Key,Value\](keys,values,children,height)  
    316 end (** LeafNode[\Key,Value\](key : Key, val : Value, height : ZZ32) **) 
     327end 
    317328 
    318329 
    …… 
    337348  *      the index of the first element greater than the key, or list.size() 
    338349  *      if all elements in the list are less than the specified key.  
    339   *      Note that this guarantees that the return value will be >= 0 
     350  *      Note that this guarantees that the return value will be %>=% 0 
    340351  *      if and only if the key is found.  
    341352  **) 
    …… 
    368379 
    369380 
    370 end (* component SkipTree *) 
     381object Filter[\Key\](pivot : Key, lessThanOrEquals : Boolean) 
     382 
     383    filter(query : Key) : Boolean = do 
     384        if lessThanOrEquals then 
     385            query <= pivot 
     386        else 
     387            query > pivot 
     388        end 
     389    end 
     390         
     391end 
     392 
     393 
     394end