1247975Scognet(* ========================================================================= *) 2247975Scognet(* FINITE MAPS IMPLEMENTED WITH RANDOMLY BALANCED TREES *) 3247975Scognet(* Copyright (c) 2004-2006 Joe Hurd, distributed under the GNU GPL version 2 *) 4247975Scognet(* ========================================================================= *) 5247975Scognet 6247975Scognetstructure Map :> Map = 7247975Scognetstruct 8247975Scognet 9247975Scognet(* ------------------------------------------------------------------------- *) 10247975Scognet(* Helper functions. *) 11247975Scognet(* ------------------------------------------------------------------------- *) 12247975Scognet 13247975Scognetexception Bug = mlibUseful.Bug; 14247975Scognet 15247975Scognetexception Error = mlibUseful.Error; 16247975Scognet 17247975Scognetval pointerEqual = Portable.pointer_eq; 18247975Scognet 19247975Scognetval K = mlibUseful.K; 20247975Scognet 21247975Scognetval snd = mlibUseful.snd; 22247975Scognet 23247975Scognet(* ------------------------------------------------------------------------- *) 24247975Scognet(* Random search trees. *) 25247975Scognet(* ------------------------------------------------------------------------- *) 26247975Scognet 27247975Scognettype ('a,'b,'c) binaryNode = 28247975Scognet {size : int, 29247975Scognet priority : real, 30247975Scognet left : 'c, 31247975Scognet key : 'a, 32247975Scognet value : 'b, 33247975Scognet right : 'c}; 34247975Scognet 35247975Scognetdatatype ('a,'b) tree = E | T of ('a, 'b, ('a,'b) tree) binaryNode; 36247975Scognet 37247975Scognettype ('a,'b) node = ('a, 'b, ('a,'b) tree) binaryNode; 38247975Scognet 39247975Scognetdatatype ('a,'b) map = Map of ('a * 'a -> order) * ('a,'b) tree; 40247975Scognet 41247975Scognet(* ------------------------------------------------------------------------- *) 42247975Scognet(* Random priorities. *) 43247975Scognet(* ------------------------------------------------------------------------- *) 44247975Scognet 45247975Scognetlocal 46247975Scognet val randomPriority = 47247975Scognet let 48247975Scognet val gen = Random.newgenseed 2.0 49247975Scognet in 50247975Scognet fn () => Random.random gen 51247975Scognet end; 52247975Scognet 53247975Scognet val priorityOrder = Real.compare; 54247975Scognetin 55247975Scognet fun treeSingleton (key,value) = 56247975Scognet T {size = 1, priority = randomPriority (), 57247975Scognet left = E, key = key, value = value, right = E}; 58247975Scognet 59247975Scognet fun nodePriorityOrder cmp (x1 : ('a,'b) node, x2 : ('a,'b) node) = 60247975Scognet let 61247975Scognet val {priority = p1, key = k1, ...} = x1 62247975Scognet and {priority = p2, key = k2, ...} = x2 63247975Scognet in 64247975Scognet case priorityOrder (p1,p2) of 65247975Scognet LESS => LESS 66247975Scognet | EQUAL => cmp (k1,k2) 67247975Scognet | GREATER => GREATER 68247975Scognet end; 69247975Scognetend; 70247975Scognet 71247975Scognet(* ------------------------------------------------------------------------- *) 72247975Scognet(* Basic operations. *) 73247975Scognet(* ------------------------------------------------------------------------- *) 74247975Scognet 75247975Scognetlocal 76247975Scognet fun checkSizes E = 0 77247975Scognet | checkSizes (T {size,left,right,...}) = 78247975Scognet let 79247975Scognet val l = checkSizes left 80247975Scognet and r = checkSizes right 81247975Scognet val () = if l + 1 + r = size then () else raise Error "wrong size" 82247975Scognet in 83247975Scognet size 84247975Scognet end 85247975Scognet 86247975Scognet fun checkSorted _ x E = x 87247975Scognet | checkSorted cmp x (T {left,key,right,...}) = 88247975Scognet let 89247975Scognet val x = checkSorted cmp x left 90247975Scognet val () = 91247975Scognet case x of 92247975Scognet NONE => () 93247975Scognet | SOME k => 94247975Scognet case cmp (k,key) of 95247975Scognet LESS => () 96247975Scognet | EQUAL => raise Error "duplicate keys" 97247975Scognet | GREATER => raise Error "unsorted" 98247975Scognet in 99247975Scognet checkSorted cmp (SOME key) right 100247975Scognet end; 101247975Scognet 102247975Scognet fun checkPriorities _ E = NONE 103247975Scognet | checkPriorities cmp (T (x as {left,right,...})) = 104247975Scognet let 105247975Scognet val () = 106247975Scognet case checkPriorities cmp left of 107247975Scognet NONE => () 108247975Scognet | SOME l => 109247975Scognet case nodePriorityOrder cmp (l,x) of 110247975Scognet LESS => () 111247975Scognet | EQUAL => raise Error "left child has equal key" 112247975Scognet | GREATER => raise Error "left child has greater priority" 113247975Scognet val () = 114247975Scognet case checkPriorities cmp right of 115247975Scognet NONE => () 116247975Scognet | SOME r => 117247975Scognet case nodePriorityOrder cmp (r,x) of 118247975Scognet LESS => () 119247975Scognet | EQUAL => raise Error "right child has equal key" 120247975Scognet | GREATER => raise Error "right child has greater priority" 121247975Scognet in 122247975Scognet SOME x 123247975Scognet end; 124247975Scognetin 125247975Scognet fun checkWellformed s (m as Map (cmp,tree)) = 126247975Scognet (let 127247975Scognet val _ = checkSizes tree 128247975Scognet val _ = checkSorted cmp NONE tree 129247975Scognet val _ = checkPriorities cmp tree 130247975Scognet val () = print "." 131247975Scognet in 132247975Scognet m 133247975Scognet end 134247975Scognet handle Error err => raise Bug err) 135247975Scognet handle Bug bug => 136247975Scognet raise Bug ("RandomMap.checkWellformed: " ^ bug ^ " (" ^ s ^ ")"); 137247975Scognetend; 138247975Scognet 139247975Scognetfun comparison (Map (cmp,_)) = cmp; 140247975Scognet 141247975Scognetfun new cmp = Map (cmp,E); 142247975Scognet 143247975Scognetfun treeSize E = 0 144247975Scognet | treeSize (T {size = s, ...}) = s; 145247975Scognet 146247975Scognetfun size (Map (_,tree)) = treeSize tree; 147247975Scognet 148247975Scognetfun mkT p l k v r = 149247975Scognet T {size = treeSize l + 1 + treeSize r, priority = p, 150247975Scognet left = l, key = k, value = v, right = r}; 151247975Scognet 152247975Scognetfun singleton cmp key_value = Map (cmp, treeSingleton key_value); 153247975Scognet 154247975Scognetlocal 155247975Scognet fun treePeek cmp E pkey = NONE 156247975Scognet | treePeek cmp (T {left,key,value,right,...}) pkey = 157247975Scognet case cmp (pkey,key) of 158247975Scognet LESS => treePeek cmp left pkey 159247975Scognet | EQUAL => SOME value 160247975Scognet | GREATER => treePeek cmp right pkey 161247975Scognetin 162247975Scognet fun peek (Map (cmp,tree)) key = treePeek cmp tree key; 163247975Scognetend; 164247975Scognet 165247975Scognet(* treeAppend assumes that every element of the first tree is less than *) 166247975Scognet(* every element of the second tree. *) 167247975Scognet 168247975Scognetfun treeAppend _ t1 E = t1 169247975Scognet | treeAppend _ E t2 = t2 170247975Scognet | treeAppend cmp (t1 as T x1) (t2 as T x2) = 171247975Scognet case nodePriorityOrder cmp (x1,x2) of 172247975Scognet LESS => 173247975Scognet let 174247975Scognet val {priority = p2, 175247975Scognet left = l2, key = k2, value = v2, right = r2, ...} = x2 176247975Scognet in 177247975Scognet mkT p2 (treeAppend cmp t1 l2) k2 v2 r2 178247975Scognet end 179247975Scognet | EQUAL => raise Bug "RandomSet.treeAppend: equal keys" 180247975Scognet | GREATER => 181247975Scognet let 182247975Scognet val {priority = p1, 183247975Scognet left = l1, key = k1, value = v1, right = r1, ...} = x1 184247975Scognet in 185247975Scognet mkT p1 l1 k1 v1 (treeAppend cmp r1 t2) 186247975Scognet end; 187247975Scognet 188247975Scognet(* nodePartition splits the node into three parts: the keys comparing less *) 189247975Scognet(* than the supplied key, an optional equal key, and the keys comparing *) 190247975Scognet(* greater. *) 191247975Scognet 192247975Scognetlocal 193247975Scognet fun mkLeft [] t = t 194247975Scognet | mkLeft (({priority,left,key,value,...} : ('a,'b) node) :: xs) t = 195247975Scognet mkLeft xs (mkT priority left key value t); 196247975Scognet 197247975Scognet fun mkRight [] t = t 198247975Scognet | mkRight (({priority,key,value,right,...} : ('a,'b) node) :: xs) t = 199247975Scognet mkRight xs (mkT priority t key value right); 200247975Scognet 201247975Scognet fun treePart _ _ lefts rights E = (mkLeft lefts E, NONE, mkRight rights E) 202247975Scognet | treePart cmp pkey lefts rights (T x) = nodePart cmp pkey lefts rights x 203247975Scognet and nodePart cmp pkey lefts rights (x as {left,key,value,right,...}) = 204247975Scognet case cmp (pkey,key) of 205247975Scognet LESS => treePart cmp pkey lefts (x :: rights) left 206247975Scognet | EQUAL => (mkLeft lefts left, SOME (key,value), mkRight rights right) 207247975Scognet | GREATER => treePart cmp pkey (x :: lefts) rights right; 208247975Scognetin 209247975Scognet fun nodePartition cmp x pkey = nodePart cmp pkey [] [] x; 210247975Scognetend; 211247975Scognet 212247975Scognet(* union first calls treeCombineRemove, to combine the values *) 213247975Scognet(* for equal keys into the first map and remove them from the second map. *) 214247975Scognet(* Note that the combined key is always the one from the second map. *) 215247975Scognet 216247975Scognetlocal 217247975Scognet fun treeCombineRemove _ _ t1 E = (t1,E) 218247975Scognet | treeCombineRemove _ _ E t2 = (E,t2) 219247975Scognet | treeCombineRemove cmp f (t1 as T x1) (t2 as T x2) = 220247975Scognet let 221247975Scognet val {priority = p1, 222247975Scognet left = l1, key = k1, value = v1, right = r1, ...} = x1 223247975Scognet val (l2,k2_v2,r2) = nodePartition cmp x2 k1 224247975Scognet val (l1,l2) = treeCombineRemove cmp f l1 l2 225247975Scognet and (r1,r2) = treeCombineRemove cmp f r1 r2 226247975Scognet in 227247975Scognet case k2_v2 of 228247975Scognet NONE => 229247975Scognet if treeSize l2 + treeSize r2 = #size x2 then (t1,t2) 230247975Scognet else (mkT p1 l1 k1 v1 r1, treeAppend cmp l2 r2) 231247975Scognet | SOME (k2,v2) => 232247975Scognet case f (v1,v2) of 233247975Scognet NONE => (treeAppend cmp l1 r1, treeAppend cmp l2 r2) 234247975Scognet | SOME v => (mkT p1 l1 k2 v r1, treeAppend cmp l2 r2) 235247975Scognet end; 236247975Scognet 237247975Scognet fun treeUnionDisjoint _ t1 E = t1 238247975Scognet | treeUnionDisjoint _ E t2 = t2 239247975Scognet | treeUnionDisjoint cmp (T x1) (T x2) = 240247975Scognet case nodePriorityOrder cmp (x1,x2) of 241247975Scognet LESS => nodeUnionDisjoint cmp x2 x1 242247975Scognet | EQUAL => raise Bug "RandomSet.unionDisjoint: equal keys" 243247975Scognet | GREATER => nodeUnionDisjoint cmp x1 x2 244247975Scognet and nodeUnionDisjoint cmp x1 x2 = 245247975Scognet let 246247975Scognet val {priority = p1, 247247975Scognet left = l1, key = k1, value = v1, right = r1, ...} = x1 248247975Scognet val (l2,_,r2) = nodePartition cmp x2 k1 249247975Scognet val l = treeUnionDisjoint cmp l1 l2 250247975Scognet and r = treeUnionDisjoint cmp r1 r2 251247975Scognet in 252247975Scognet mkT p1 l k1 v1 r 253247975Scognet end; 254247975Scognetin 255247975Scognet fun union f (m1 as Map (cmp,t1)) (Map (_,t2)) = 256247975Scognet if pointerEqual (t1,t2) then m1 257247975Scognet else 258247975Scognet let 259247975Scognet val (t1,t2) = treeCombineRemove cmp f t1 t2 260247975Scognet in 261247975Scognet Map (cmp, treeUnionDisjoint cmp t1 t2) 262247975Scognet end; 263247975Scognetend; 264247975Scognet 265247975Scognet(* 266247975Scognetval union = 267247975Scognet fn f => fn t1 => fn t2 => 268247975Scognet checkWellformed 269247975Scognet "after union" 270247975Scognet (union f (checkWellformed "before union 1" t1) 271247975Scognet (checkWellformed "before union 2" t2)); 272247975Scognet*) 273247975Scognet 274247975Scognet(* intersect is a simple case of the union algorithm. *) 275247975Scognet 276247975Scognetlocal 277247975Scognet fun treeIntersect _ _ _ E = E 278247975Scognet | treeIntersect _ _ E _ = E 279247975Scognet | treeIntersect cmp f (t1 as T x1) (t2 as T x2) = 280247975Scognet let 281247975Scognet val {priority = p1, 282247975Scognet left = l1, key = k1, value = v1, right = r1, ...} = x1 283247975Scognet val (l2,k2_v2,r2) = nodePartition cmp x2 k1 284247975Scognet val l = treeIntersect cmp f l1 l2 285247975Scognet and r = treeIntersect cmp f r1 r2 286247975Scognet in 287247975Scognet case k2_v2 of 288247975Scognet NONE => treeAppend cmp l r 289247975Scognet | SOME (k2,v2) => 290247975Scognet case f (v1,v2) of 291247975Scognet NONE => treeAppend cmp l r 292247975Scognet | SOME v => mkT p1 l k2 v r 293247975Scognet end; 294247975Scognetin 295247975Scognet fun intersect f (m1 as Map (cmp,t1)) (Map (_,t2)) = 296247975Scognet if pointerEqual (t1,t2) then m1 297247975Scognet else Map (cmp, treeIntersect cmp f t1 t2); 298247975Scognetend; 299247975Scognet 300247975Scognet(* 301247975Scognetval intersect = 302247975Scognet fn f => fn t1 => fn t2 => 303247975Scognet checkWellformed 304247975Scognet "after intersect" 305247975Scognet (intersect f (checkWellformed "before intersect 1" t1) 306247975Scognet (checkWellformed "before intersect 2" t2)); 307247975Scognet*) 308247975Scognet 309247975Scognet(* delete raises an exception if the supplied key is not found, which *) 310247975Scognet(* makes it simpler to maximize sharing. *) 311247975Scognet 312247975Scognetlocal 313247975Scognet fun treeDelete _ E _ = raise Error "RandomMap.delete: element not found" 314247975Scognet | treeDelete cmp (T {priority,left,key,value,right,...}) dkey = 315247975Scognet case cmp (dkey,key) of 316247975Scognet LESS => mkT priority (treeDelete cmp left dkey) key value right 317247975Scognet | EQUAL => treeAppend cmp left right 318247975Scognet | GREATER => mkT priority left key value (treeDelete cmp right dkey); 319247975Scognetin 320247975Scognet fun delete (Map (cmp,tree)) key = Map (cmp, treeDelete cmp tree key); 321247975Scognetend; 322247975Scognet 323247975Scognet(* 324247975Scognetval delete = 325247975Scognet fn t => fn x => 326247975Scognet checkWellformed 327247975Scognet "after delete" (delete (checkWellformed "before delete" t) x); 328247975Scognet*) 329247975Scognet 330247975Scognet(* Set difference is mainly used when using maps as sets *) 331247975Scognet 332247975Scognetlocal 333247975Scognet fun treeDifference _ t1 E = t1 334247975Scognet | treeDifference _ E _ = E 335247975Scognet | treeDifference cmp (t1 as T x1) (T x2) = 336247975Scognet let 337247975Scognet val {size = s1, priority = p1, 338247975Scognet left = l1, key = k1, value = v1, right = r1} = x1 339247975Scognet val (l2,k2_v2,r2) = nodePartition cmp x2 k1 340247975Scognet val l = treeDifference cmp l1 l2 341247975Scognet and r = treeDifference cmp r1 r2 342247975Scognet in 343247975Scognet if Option.isSome k2_v2 then treeAppend cmp l r 344247975Scognet else if treeSize l + treeSize r + 1 = s1 then t1 345247975Scognet else mkT p1 l k1 v1 r 346247975Scognet end; 347247975Scognetin 348247975Scognet fun difference (Map (cmp,tree1)) (Map (_,tree2)) = 349247975Scognet if pointerEqual (tree1,tree2) then Map (cmp,E) 350247975Scognet else Map (cmp, treeDifference cmp tree1 tree2); 351247975Scognetend; 352247975Scognet 353247975Scognet(* 354247975Scognetval difference = 355247975Scognet fn t1 => fn t2 => 356247975Scognet checkWellformed 357247975Scognet "after difference" 358247975Scognet (difference (checkWellformed "before difference 1" t1) 359247975Scognet (checkWellformed "before difference 2" t2)); 360247975Scognet*) 361247975Scognet 362247975Scognet(* subsetDomain is mainly used when using maps as sets. *) 363247975Scognet 364247975Scognetlocal 365247975Scognet fun treeSubsetDomain _ E _ = true 366247975Scognet | treeSubsetDomain _ _ E = false 367247975Scognet | treeSubsetDomain cmp (t1 as T x1) (T x2) = 368247975Scognet let 369247975Scognet val {size = s1, left = l1, key = k1, right = r1, ...} = x1 370 and {size = s2, ...} = x2 371 in 372 s1 <= s2 andalso 373 let 374 val (l2,k2_v2,r2) = nodePartition cmp x2 k1 375 in 376 Option.isSome k2_v2 andalso 377 treeSubsetDomain cmp l1 l2 andalso 378 treeSubsetDomain cmp r1 r2 379 end 380 end; 381in 382 fun subsetDomain (Map (cmp,tree1)) (Map (_,tree2)) = 383 pointerEqual (tree1,tree2) orelse 384 treeSubsetDomain cmp tree1 tree2 385end; 386 387(* equalDomain is mainly used when using maps as sets. *) 388 389local 390 fun treeEqualDomain _ E _ = true 391 | treeEqualDomain _ _ E = false 392 | treeEqualDomain cmp (t1 as T x1) (T x2) = 393 let 394 val {size = s1, left = l1, key = k1, right = r1, ...} = x1 395 and {size = s2, ...} = x2 396 in 397 s1 = s2 andalso 398 let 399 val (l2,k2_v2,r2) = nodePartition cmp x2 k1 400 in 401 Option.isSome k2_v2 andalso 402 treeEqualDomain cmp l1 l2 andalso 403 treeEqualDomain cmp r1 r2 404 end 405 end; 406in 407 fun equalDomain (Map (cmp,tree1)) (Map (_,tree2)) = 408 pointerEqual (tree1,tree2) orelse 409 treeEqualDomain cmp tree1 tree2 410end; 411 412(* mapPartial is the basic function for preserving the tree structure. *) 413(* It applies the argument function to the elements *in order*. *) 414 415local 416 fun treeMapPartial cmp _ E = E 417 | treeMapPartial cmp f (T {priority,left,key,value,right,...}) = 418 let 419 val left = treeMapPartial cmp f left 420 and value' = f (key,value) 421 and right = treeMapPartial cmp f right 422 in 423 case value' of 424 NONE => treeAppend cmp left right 425 | SOME value => mkT priority left key value right 426 end; 427in 428 fun mapPartial f (Map (cmp,tree)) = Map (cmp, treeMapPartial cmp f tree); 429end; 430 431(* map is a primitive function for efficiency reasons. *) 432(* It also applies the argument function to the elements *in order*. *) 433 434local 435 fun treeMap _ E = E 436 | treeMap f (T {size,priority,left,key,value,right}) = 437 let 438 val left = treeMap f left 439 and value = f (key,value) 440 and right = treeMap f right 441 in 442 T {size = size, priority = priority, left = left, 443 key = key, value = value, right = right} 444 end; 445in 446 fun map f (Map (cmp,tree)) = Map (cmp, treeMap f tree); 447end; 448 449(* nth picks the nth smallest key/value (counting from 0). *) 450 451 452local 453 fun treeNth E _ = raise Error "RandomMap.nth" 454 | treeNth (T {left,key,value,right,...}) n = 455 let 456 val k = treeSize left 457 in 458 if n = k then (key,value) 459 else if n < k then treeNth left n 460 else treeNth right (n - (k + 1)) 461 end; 462in 463 fun nth (Map (_,tree)) n = treeNth tree n; 464end; 465 466(* ------------------------------------------------------------------------- *) 467(* Iterators. *) 468(* ------------------------------------------------------------------------- *) 469 470fun leftSpine E acc = acc 471 | leftSpine (t as T {left,...}) acc = leftSpine left (t :: acc); 472 473fun rightSpine E acc = acc 474 | rightSpine (t as T {right,...}) acc = rightSpine right (t :: acc); 475 476datatype ('key,'a) iterator = 477 LR of ('key * 'a) * ('key,'a) tree * ('key,'a) tree list 478 | RL of ('key * 'a) * ('key,'a) tree * ('key,'a) tree list; 479 480fun mkLR [] = NONE 481 | mkLR (T {key,value,right,...} :: l) = SOME (LR ((key,value),right,l)) 482 | mkLR (E :: _) = raise Bug "RandomMap.mkLR"; 483 484fun mkRL [] = NONE 485 | mkRL (T {key,value,left,...} :: l) = SOME (RL ((key,value),left,l)) 486 | mkRL (E :: _) = raise Bug "RandomMap.mkRL"; 487 488fun mkIterator (Map (_,tree)) = mkLR (leftSpine tree []); 489 490fun mkRevIterator (Map (_,tree)) = mkRL (rightSpine tree []); 491 492fun readIterator (LR (key_value,_,_)) = key_value 493 | readIterator (RL (key_value,_,_)) = key_value; 494 495fun advanceIterator (LR (_,next,l)) = mkLR (leftSpine next l) 496 | advanceIterator (RL (_,next,l)) = mkRL (rightSpine next l); 497 498(* ------------------------------------------------------------------------- *) 499(* Derived operations. *) 500(* ------------------------------------------------------------------------- *) 501 502fun null m = size m = 0; 503 504fun get m key = 505 case peek m key of 506 NONE => raise Error "RandomMap.get: element not found" 507 | SOME value => value; 508 509fun inDomain key m = Option.isSome (peek m key); 510 511fun insert m key_value = 512 union (SOME o snd) m (singleton (comparison m) key_value); 513 514(* 515val insert = 516 fn m => fn x => 517 checkWellformed 518 "after insert" (insert (checkWellformed "before insert" m) x); 519*) 520 521local 522 fun fold _ NONE acc = acc 523 | fold f (SOME iter) acc = 524 let 525 val (key,value) = readIterator iter 526 in 527 fold f (advanceIterator iter) (f (key,value,acc)) 528 end; 529in 530 fun foldl f b m = fold f (mkIterator m) b; 531 532 fun foldr f b m = fold f (mkRevIterator m) b; 533end; 534 535local 536 fun find _ NONE = NONE 537 | find pred (SOME iter) = 538 let 539 val key_value = readIterator iter 540 in 541 if pred key_value then SOME key_value 542 else find pred (advanceIterator iter) 543 end; 544in 545 fun findl p m = find p (mkIterator m); 546 547 fun findr p m = find p (mkRevIterator m); 548end; 549 550fun fromList cmp l = List.foldl (fn (k_v,m) => insert m k_v) (new cmp) l; 551 552fun insertList m l = union (SOME o snd) m (fromList (comparison m) l); 553 554fun filter p = 555 let 556 fun f (key_value as (_,value)) = 557 if p key_value then SOME value else NONE 558 in 559 mapPartial f 560 end; 561 562fun app f m = foldl (fn (key,value,()) => f (key,value)) () m; 563 564fun transform f = map (fn (_,value) => f value); 565 566fun toList m = foldr (fn (key,value,l) => (key,value) :: l) [] m; 567 568fun domain m = foldr (fn (key,_,l) => key :: l) [] m; 569 570fun exists p m = Option.isSome (findl p m); 571 572fun all p m = not (exists (not o p) m); 573 574local 575 fun iterCompare _ _ NONE NONE = EQUAL 576 | iterCompare _ _ NONE (SOME _) = LESS 577 | iterCompare _ _ (SOME _) NONE = GREATER 578 | iterCompare kcmp vcmp (SOME i1) (SOME i2) = 579 keyIterCompare kcmp vcmp (readIterator i1) (readIterator i2) i1 i2 580 and keyIterCompare kcmp vcmp (k1,v1) (k2,v2) i1 i2 = 581 case kcmp (k1,k2) of 582 LESS => LESS 583 | EQUAL => 584 (case vcmp (v1,v2) of 585 LESS => LESS 586 | EQUAL => 587 iterCompare kcmp vcmp (advanceIterator i1) (advanceIterator i2) 588 | GREATER => GREATER) 589 | GREATER => GREATER; 590in 591 fun compare cmp (m1,m2) = 592 iterCompare (comparison m1) cmp (mkIterator m1) (mkIterator m2); 593end; 594 595end 596