Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /smlnj-lib/branches/rt-transition/Util/splay-map-fn.sml
ViewVC logotype

Diff of /smlnj-lib/branches/rt-transition/Util/splay-map-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 289, Sat May 22 21:01:25 1999 UTC revision 411, Fri Sep 3 00:25:03 1999 UTC
# Line 43  Line 43 
43              f (!root)              f (!root)
44            end            end
45    
46          (* Insert an item.      fun singleton (key, v) =
47           *)            MAP{nobj=1,root=ref(SplayObj{value=(key,v),left=SplayNil,right=SplayNil})}
48    
49      (* Insert an item.  *)
50      fun insert (EMPTY,key,v) =      fun insert (EMPTY,key,v) =
51            MAP{nobj=1,root=ref(SplayObj{value=(key,v),left=SplayNil,right=SplayNil})}            MAP{nobj=1,root=ref(SplayObj{value=(key,v),left=SplayNil,right=SplayNil})}
52        | insert (MAP{root,nobj},key,v) =        | insert (MAP{root,nobj},key,v) =
# Line 68  Line 70 
70            | (_,SplayNil) => raise LibBase.Impossible "SplayMapFn.insert SplayNil"            | (_,SplayNil) => raise LibBase.Impossible "SplayMapFn.insert SplayNil"
71      fun insert' ((k, x), m) = insert(m, k, x)      fun insert' ((k, x), m) = insert(m, k, x)
72    
73        fun inDomain (EMPTY, _) = false
74          | inDomain (MAP{root,nobj}, key) = (case splay (cmpf key, !root)
75               of (EQUAL, r as SplayObj{value,...}) => (root := r; true)
76                | (_, r) => (root := r; false)
77              (* end case *))
78    
79    (* Look for an item, return NONE if the item doesn't exist *)    (* Look for an item, return NONE if the item doesn't exist *)
80      fun find (EMPTY,_) = NONE      fun find (EMPTY,_) = NONE
81        | find (MAP{root,nobj},key) = (case splay (cmpf key, !root)        | find (MAP{root,nobj},key) = (case splay (cmpf key, !root)
# Line 108  Line 116 
116            apply (!root,[])            apply (!root,[])
117          end          end
118    
119        fun listKeys EMPTY = []
120          | listKeys (MAP{root,...}) = let
121              fun apply (SplayNil, l) = l
122                | apply (SplayObj{value=(key, _),left,right},l) =
123                    apply(left, key::(apply (right,l)))
124            in
125              apply (!root, [])
126            end
127    
128      local      local
129        fun next ((t as SplayObj{right, ...})::rest) = (t, left(right, rest))        fun next ((t as SplayObj{right, ...})::rest) = (t, left(right, rest))
130          | next _ = (SplayNil, [])          | next _ = (SplayNil, [])

Legend:
Removed from v.289  
changed lines
  Added in v.411

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0