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/trunk/src/smlnj-lib/Util/splay-map-fn.sml revision 499, Tue Dec 7 15:44:50 1999 UTC smlnj-lib/trunk/Util/splay-map-fn.sml revision 2274, Tue Jan 30 15:00:09 2007 UTC
# Line 82  Line 82 
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)
84             of (EQUAL, r as SplayObj{value,...}) => (root := r; SOME(#2 value))             of (EQUAL, r as SplayObj{value,...}) => (root := r; SOME(#2 value))
85              | (_, r) => (root := r; NONE))              | (_, r) => (root := r; NONE)
86              (* end case *))
87    
88      (* Look for an item, raise NotFound if the item doesn't exist *)
89        fun lookup (EMPTY,_) = raise LibBase.NotFound
90          | lookup (MAP{root,nobj},key) = (case splay (cmpf key, !root)
91               of (EQUAL, r as SplayObj{value,...}) => (root := r; #2 value)
92                | (_, r) => (root := r; raise LibBase.NotFound)
93              (* end case *))
94    
95          (* Remove an item.          (* Remove an item.
96           * Raise LibBase.NotFound if not found           * Raise LibBase.NotFound if not found
# Line 249  Line 257 
257            MAP{root = ref(ap (!root)), nobj = nobj}            MAP{root = ref(ap (!root)), nobj = nobj}
258          end          end
259    
260  (* the following are generic implementations of the unionWith and intersectWith  (* the following are generic implementations of the unionWith, intersectWith,
261   * operetions.  These should be specialized for the internal representations   * and mergeWith operetions.  These should be specialized for the internal
262   * at some point.   * representations at some point.
263   *)   *)
264      fun unionWith f (m1, m2) = let      fun unionWith f (m1, m2) = let
265            fun ins f (key, x, m) = (case find(m, key)            fun ins f (key, x, m) = (case find(m, key)
# Line 306  Line 314 
314                else intersect (fn (k, a, b) => f(k, b, a)) (m2, m1)                else intersect (fn (k, a, b) => f(k, b, a)) (m2, m1)
315            end            end
316    
317        fun mergeWith f (m1, m2) = let
318              fun merge ([], [], m) = m
319                | merge ((k1, x1)::r1, [], m) = mergef (k1, SOME x1, NONE, r1, [], m)
320                | merge ([], (k2, x2)::r2, m) = mergef (k2, NONE, SOME x2, [], r2, m)
321                | merge (m1 as ((k1, x1)::r1), m2 as ((k2, x2)::r2), m) = (
322                    case Key.compare (k1, k2)
323                     of LESS => mergef (k1, SOME x1, NONE, r1, m2, m)
324                      | EQUAL => mergef (k1, SOME x1, SOME x2, r1, r2, m)
325                      | GREATER => mergef (k2, NONE, SOME x2, m1, r2, m)
326                    (* end case *))
327              and mergef (k, x1, x2, r1, r2, m) = (case f (x1, x2)
328                     of NONE => merge (r1, r2, m)
329                      | SOME y => merge (r1, r2, insert(m, k, y))
330                    (* end case *))
331              in
332                merge (listItemsi m1, listItemsi m2, empty)
333              end
334    
335        fun mergeWithi f (m1, m2) = let
336              fun merge ([], [], m) = m
337                | merge ((k1, x1)::r1, [], m) = mergef (k1, SOME x1, NONE, r1, [], m)
338                | merge ([], (k2, x2)::r2, m) = mergef (k2, NONE, SOME x2, [], r2, m)
339                | merge (m1 as ((k1, x1)::r1), m2 as ((k2, x2)::r2), m) = (
340                    case Key.compare (k1, k2)
341                     of LESS => mergef (k1, SOME x1, NONE, r1, m2, m)
342                      | EQUAL => mergef (k1, SOME x1, SOME x2, r1, r2, m)
343                      | GREATER => mergef (k2, NONE, SOME x2, m1, r2, m)
344                    (* end case *))
345              and mergef (k, x1, x2, r1, r2, m) = (case f (k, x1, x2)
346                     of NONE => merge (r1, r2, m)
347                      | SOME y => merge (r1, r2, insert(m, k, y))
348                    (* end case *))
349              in
350                merge (listItemsi m1, listItemsi m2, empty)
351              end
352    
353    (* this is a generic implementation of mapPartial.  It should    (* this is a generic implementation of mapPartial.  It should
354     * be specialized to the data-structure at some point.     * be specialized to the data-structure at some point.
355     *)     *)

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

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