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

sml/branches/SMLNJ/src/smlnj-lib/Util/splay-map-fn.sml revision 289, Sat May 22 21:01:25 1999 UTC sml/trunk/src/smlnj-lib/Util/splay-map-fn.sml revision 499, Tue Dec 7 15:44:50 1999 UTC
# Line 30  Line 30 
30        | first (MAP{root, ...}) = let        | first (MAP{root, ...}) = let
31            fun f (SplayObj{value=(_, value), left=SplayNil, ...}) = SOME value            fun f (SplayObj{value=(_, value), left=SplayNil, ...}) = SOME value
32              | f (SplayObj{left, ...}) = f left              | f (SplayObj{left, ...}) = f left
33                | f SplayNil = raise Fail "SplayMapFn.first"
34            in            in
35              f (!root)              f (!root)
36            end            end
# Line 39  Line 40 
40        | firsti (MAP{root, ...}) = let        | firsti (MAP{root, ...}) = let
41            fun f (SplayObj{value=(key, value), left=SplayNil, ...}) = SOME(key, value)            fun f (SplayObj{value=(key, value), left=SplayNil, ...}) = SOME(key, value)
42              | f (SplayObj{left, ...}) = f left              | f (SplayObj{left, ...}) = f left
43                | f SplayNil = raise Fail "SplayMapFn.firsti"
44            in            in
45              f (!root)              f (!root)
46            end            end
47    
48          (* Insert an item.      fun singleton (key, v) =
49           *)            MAP{nobj=1,root=ref(SplayObj{value=(key,v),left=SplayNil,right=SplayNil})}
50    
51      (* Insert an item.  *)
52      fun insert (EMPTY,key,v) =      fun insert (EMPTY,key,v) =
53            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})}
54        | insert (MAP{root,nobj},key,v) =        | insert (MAP{root,nobj},key,v) =
# Line 68  Line 72 
72            | (_,SplayNil) => raise LibBase.Impossible "SplayMapFn.insert SplayNil"            | (_,SplayNil) => raise LibBase.Impossible "SplayMapFn.insert SplayNil"
73      fun insert' ((k, x), m) = insert(m, k, x)      fun insert' ((k, x), m) = insert(m, k, x)
74    
75        fun inDomain (EMPTY, _) = false
76          | inDomain (MAP{root,nobj}, key) = (case splay (cmpf key, !root)
77               of (EQUAL, r as SplayObj{value,...}) => (root := r; true)
78                | (_, r) => (root := r; false)
79              (* end case *))
80    
81    (* Look for an item, return NONE if the item doesn't exist *)    (* Look for an item, return NONE if the item doesn't exist *)
82      fun find (EMPTY,_) = NONE      fun find (EMPTY,_) = NONE
83        | find (MAP{root,nobj},key) = (case splay (cmpf key, !root)        | find (MAP{root,nobj},key) = (case splay (cmpf key, !root)
# Line 108  Line 118 
118            apply (!root,[])            apply (!root,[])
119          end          end
120    
121        fun listKeys EMPTY = []
122          | listKeys (MAP{root,...}) = let
123              fun apply (SplayNil, l) = l
124                | apply (SplayObj{value=(key, _),left,right},l) =
125                    apply(left, key::(apply (right,l)))
126            in
127              apply (!root, [])
128            end
129    
130      local      local
131        fun next ((t as SplayObj{right, ...})::rest) = (t, left(right, rest))        fun next ((t as SplayObj{right, ...})::rest) = (t, left(right, rest))
132          | next _ = (SplayNil, [])          | next _ = (SplayNil, [])

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

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