root/trunk/Library/Map.fss

Revision 4130, 20.9 KB (checked in by sukyoungryu, 3 months ago)

[disambiguator] Fixed handling getters and setters in ExprDisambiguator?. Fixed libraries and tests using getters.
Line 
1(*******************************************************************************
2    Copyright 2009 Sun Microsystems, Inc.,
3    4150 Network Circle, Santa Clara, California 95054, U.S.A.
4    All rights reserved.
5
6    U.S. Government Rights - Commercial software.
7    Government users are subject to the Sun Microsystems, Inc. standard
8    license agreement and applicable provisions of the FAR and its supplements.
9
10    Use is subject to license terms.
11
12    This distribution may include materials developed by third parties.
13
14    Sun, Sun Microsystems, the Sun logo and Java are trademarks or registered
15    trademarks of Sun Microsystems, Inc. in the U.S. and other countries.
16 ******************************************************************************)
17
18component Map
19import List.{...}
20import Set.{Set, set}
21import CovariantCollection.{...}
22import QuickSort.{quicksort}
23export Map
24
25weight:ZZ32 = 4
26
27object KeyOverlap[\Key,Val\](key:Key, val1:Val, val2:Val)
28        extends UncheckedException
29    getter asString(): String =
30        "Map.KeyOverlap: " key " |-> " val1 " and |-> " val2
31end
32
33(** Note that the map interface is purely functional; methods return a
34    fresh map rather than updating the receiving map in place.
35    Methods that operate on a particular key leave the rest of the map
36    untouched unless otherwise specified. **)
37trait Map[\Key,Val\]
38      extends { Generator[\(Key,Val)\], Equality[\Map[\Key,Val\]\] }
39      comprises {NodeMap[\Key,Val\], EmptyMap[\Key,Val\]}
40    getter isEmpty():Boolean
41    getter asDebugString():String
42    seqgen[\R\](r: Reduction[\R\], body: (Key,Val)->R): R
43    seq(self): SequentialGenerator[\(Key,Val)\] =
44        SeqMapGenerator[\Key,Val\](self)
45    dom(self):Set[\Key\]
46    opr |self| : ZZ32
47    getPair():(Key, Val) throws NotFound
48    getKey():Key throws NotFound
49    getVal():Val throws NotFound
50    getLeftChild():Map[\Key,Val\]
51    getRightChild():Map[\Key,Val\]
52    opr[k:Key]: Val throws NotFound = mem(k).getVal()
53    mem(k:Key): Map[\Key,Val\] = do
54        n : Map[\Key,Val\] := self
55        notDone : Boolean := true
56        while notDone do
57            typecase ni = n of
58                NodeMap[\Key,Val\] =>
59                    typecase _ = k CMP ni.getKey() of
60                        LessThan => n := ni.getLeftChild()
61                        EqualTo  => notDone := false
62                        else     => n := ni.getRightChild()
63                    end
64                else => notDone := false
65            end
66        end
67        n
68      end
69    member(x:Key): Maybe[\Val\] =
70        typecase t = mem(x) of
71            NodeMap[\Key,Val\] => Just[\Val\](t.getVal())
72            else => Nothing[\Val\]
73        end
74    (** The two-argument version of member returns the default value v
75        if the key is absent from the map. **)
76    member(x:Key, v:Val): Val =
77        typecase t = mem(x) of
78            NodeMap[\Key,Val\] => t.getVal()
79            else => v
80        end
81    (** minimum and maximum refer to the key **)
82    minimum():Maybe[\(Key,Val)\]
83    deleteMinimum():Map[\Key,Val\] =
84        if (_,_,r) <- extractMinimum() then r else self end
85    extractMinimum():Maybe[\(Key,Val, Map[\Key,Val\])\]
86    maximum(): Maybe[\(Key,Val)\]
87    deleteMaximum():Map[\Key,Val\] =
88        if (_,_,r) <- extractMaximum() then r else self end
89    extractMaximum():Maybe[\(Key,Val, Map[\Key,Val\])\]
90
91    (** If no mapping presently exists, maps k to v. **)
92    add(k:Key, v:Val):Map[\Key,Val\]
93    (** Maps k to v. **)
94    update(k:Key, v:Val):Map[\Key,Val\]
95    (** Eliminate any mapping for key k. **)
96    delete(k:Key):Map[\Key,Val\]
97    (** Process mapping for key k with function f:
98        * If no mapping exists, f is passed Nothing[\Val\]
99        * If k maps to value v, f is passed Just[\Val\](v)
100        If f returns nothing, the mapping for k is deleted; otherwise
101        it is updated with the value contained in the result.
102     **)
103    updateWith(f:Maybe[\Val\]->Maybe[\Val\], k:Key): Map[\Key,Val\]
104    (** UNION favors the leftmost value when a key occurs in both maps. **)
105    opr UNION(self, other: Map[\Key,Val\]): Map[\Key,Val\]
106    (** UPLUS (disjoint union) throws the KeyOverlap exception when a key
107        occurs in both maps. **)
108    opr UPLUS(self, other: Map[\Key,Val\]): Map[\Key,Val\]
109    (** the union method takes a function f used to combine the values
110        of keys that overlap.  **)
111    union(f:(Key,Val,Val)->Val, other: Map[\Key,Val\]): Map[\Key,Val\]
112    splitAt(k:Key):(Map[\Key,Val\],Maybe[\Val\],Map[\Key,Val\])
113
114    balancedDelete(r:Map[\Key,Val\]):Map[\Key,Val\]
115    balancedAdd(k:Key,v:Val, left:Map[\Key,Val\], right:Map[\Key,Val\]):
116        NodeMap[\Key,Val\]
117    concat(t2:Map[\Key,Val\]): Map[\Key,Val\]
118    concat3(k:Key, v:Val, t2:Map[\Key,Val\]): Map[\Key,Val\]
119    (** combine is the "swiss army knife" combinator on pairs of maps.
120        We call f() on keys present in both input maps;
121        We call doThis on keys present in self but not in that;
122        We call doThat on keys present in that but not in self.
123        When any of these functions returns r=Just[\Result\], the key is mapped
124            to r.get in the result.
125        When any of these functions returns Nothing[\Result\] there is no
126            mapping for the key in the result.
127
128        mapThis must be equivalent to mapFilter(doThis) and mapThat must
129            be equivalent to mapFilter(doThat); they are included
130            because often they can do their jobs without traversing
131            their argument (eg for union and interesection operations we
132            can pass through or discard whole submaps without traversing
133            them).
134     **)
135    combine[\That,Result\](f:(Key,Val,That)->Maybe[\Result\],
136                           doThis:(Key,Val)->Maybe[\Result\],
137                           doThat:(Key,That)->Maybe[\Result\],
138                           mapThis:Map[\Key,Val\]->Map[\Key,Result\],
139                           mapThat:Map[\Key,That\]->Map[\Key,Result\],
140                           that: Map[\Key,That\]): Map[\Key,Result\]
141    (** self.mapFilter(f) is equivalent to:
142          { k |-> v'  |  (k,v) <- self, v' <- f(k,v) }
143        It fuses generation, mapping, and filtering.
144     **)
145    mapFilter[\Result\](f:(Key,Val)->Maybe[\Result\]): Map[\Key,Result\]
146end
147
148singleton[\Key,Val\](k:Key,v:Val): Map[\Key,Val\] = do
149    e = EmptyMap[\Key,Val\]
150    NodeMap[\Key,Val\](k,v,e,e)
151  end
152
153mapping[\Key,Val\](): Map[\Key,Val\] = EmptyMap[\Key,Val\]
154mapping[\Key,Val\](g: Generator[\(Key,Val)\]): Map[\Key,Val\] =
155    g.generate[\Map[\Key,Val\]\](DisjointMapUnion[\Key,Val\],
156                                 singleton[\Key,Val\])
157mapping[\Key,Val\](g: ReadableArray[\(Key,Val),ZZ32\]): Map[\Key,Val\] = do
158    a = array[\(Key,Val)\](|g|)
159    a.init0(i,g.get(i)), i <- a.indices
160    fromCopiedArray(a)
161  end
162
163fromCopiedArray[\Key,Val\](a: Array[\(Key,Val),ZZ32\]): Map[\Key,Val\] = do
164    lt(kv1, kv2): Boolean =
165        do (k1,_) = kv1; (k2,_) = kv2; k1 < k2 end
166    quicksort[\(Key,Val)\](lt,a)
167    (* Complain about duplicates. *)
168    for i <- a.indices, i > 0 do
169        (pk,pv) = a[i-1]
170        (ck,cv) = a[i]
171        if pk = ck then
172            throw KeyOverlap[\Key,Val\](pk,pv,cv)
173        end
174    end
175    fromSortedArrayFragment[\Key,Val\](a, 0, |a| - 1)
176  end
177
178fromCovariantCollection[\Key,Val\](cc: CovariantCollection[\(Key,Val)\]): Map[\Key,Val\] =
179    fromCopiedArray[\Key,Val\](cc.toArray())
180
181fromSortedArrayFragment[\Key,Val\](a: Array[\(Key,Val),ZZ32\], lo:ZZ32, hi:ZZ32): Map[\Key,Val\] =
182    if hi < lo then
183        EmptyMap[\Key,Val\]
184    else
185        mid = (hi+lo) DIV 2
186        (l,r) = (fromSortedArrayFragment[\Key,Val\](a,lo,mid-1),
187                 fromSortedArrayFragment[\Key,Val\](a,mid+1,hi))
188        (k,v) = a[mid]
189        NodeMap[\Key,Val\](k,v,l,r)
190    end
191
192opr {|->[\Key,Val\] xs:(Key,Val)... }:Map[\Key,Val\] =
193    mapping[\Key,Val\](xs)
194
195opr {[\Key,Val\] }:Map[\Key,Val\] = mapping[\Key,Val\]()
196
197opr BIG {|->[\Key,Val\] } : Comprehension[\(Key,Val),Map[\Key,Val\],AnyCovColl,AnyCovColl\] =
198    covariantCompr[\(Key,Val),Map[\Key,Val\]\](fn cc => fromCovariantCollection(cc))
199
200opr BIG {|->[\Key,Val\] g: Generator[\(Key,Val)\] }:Map[\Key,Val\] =
201    __bigOperatorSugar[\(Key,Val),Map[\Key,Val\],AnyCovColl,AnyCovColl\](BIG {|->[\Key,Val\]}(), g)
202
203opr BIG UNION[\Key,Val\]() : Comprehension[\Map[\Key,Val\],Map[\Key,Val\],Any,Any\] =
204    embiggen[\ Map[\Key,Val\] \](fn (a,b) => a UNION b, EmptyMap[\Key,Val\])
205
206opr BIG UNION[\Key,Val\](g: Generator[\Map[\Key,Val\]\]):Map[\Key,Val\] =
207    __bigOperatorSugar[\Map[\Key,Val\],Map[\Key,Val\],Any,Any\](BIG UNION[\Key,Val\](), g)
208
209opr BIG UPLUS[\Key,Val\]() : Comprehension[\Map[\Key,Val\],Map[\Key,Val\],Any,Any\] =
210    embiggen[\ Map[\Key,Val\] \](fn (a,b) => a UPLUS b, EmptyMap[\Key,Val\])
211
212opr BIG UPLUS[\Key,Val\](g: Generator[\Map[\Key,Val\]\]):Map[\Key,Val\] =
213    __bigOperatorSugar[\Map[\Key,Val\],Map[\Key,Val\],Any,Any\](BIG UPLUS[\Key,Val\](), g)
214
215object SeqMapGenerator[\Key,Val\](o:Map[\Key,Val\])
216    extends SequentialGenerator[\(Key,Val)\]
217  generate[\R\](r: Reduction[\R\], body: (Key,Val)->R): R = o.seqgen[\R\](r,body)
218end
219
220object DisjointMapUnion[\Key,Val\] extends MonoidReduction[\Map[\Key,Val\]\]
221    getter asString(): String = "Disjoint map union reduction"
222    empty():Map[\Key,Val\] = EmptyMap[\Key,Val\]
223    join(a:Map[\Key,Val\], b:Map[\Key,Val\]): Map[\Key,Val\] =
224        a UPLUS b
225end
226
227object EmptyMap[\Key,Val\] extends Map[\Key,Val\]
228    getter size():ZZ32 = 0
229    getter isEmpty():Boolean = true
230    getter asDebugString():String = "[]"
231    getter asString():String = "{}"
232    opr |self| : ZZ32 = 0
233    generate[\R\](r: Reduction[\R\], body: (Key,Val)->R): R = r.empty()
234    seqgen[\R\](r: Reduction[\R\], body: (Key,Val)->R): R = r.empty()
235    dom(self):Set[\Key\] = set[\Key\]()
236    getPair():(Key, Val) = throw NotFound
237    getKey():Key = throw NotFound
238    getVal():Val = throw NotFound
239    getLeftChild():Map[\Key,Val\] = self
240    getRightChild():Map[\Key,Val\] = self
241    minimum(): Nothing[\(Key,Val)\] = Nothing[\(Key,Val)\]
242    extractMinimum():Nothing[\(Key,Val, Map[\Key,Val\])\] =
243        Nothing[\(Key,Val, Map[\Key,Val\])\]
244    maximum(): Nothing[\(Key,Val)\] = Nothing[\(Key,Val)\]
245    extractMaximum():Nothing[\(Key,Val, Map[\Key,Val\])\] =
246        Nothing[\(Key,Val, Map[\Key,Val\])\]
247    add(k:Key, v:Val):Map[\Key,Val\] = NodeMap[\Key,Val\](k,v, self, self)
248    update(k:Key, v:Val):Map[\Key,Val\] = add(k, v)
249    delete(k:Key):Map[\Key,Val\] = self
250    updateWith(f:Maybe[\Val\]->Maybe[\Val\], k:Key): Map[\Key,Val\] =
251        if r <- f(Nothing[\Val\])
252        then add(k,r)
253        else self end
254    opr UNION(self, other: Map[\Key,Val\]): Map[\Key,Val\] = other
255    opr UPLUS(self, other: Map[\Key,Val\]): Map[\Key,Val\] = other
256    union(f:(Key,Val,Val)->Val, other: Map[\Key,Val\]): Map[\Key,Val\] =
257        other
258    splitAt(k:Key):(Map[\Key,Val\],Maybe[\Val\],Map[\Key,Val\]) =
259        (self,Nothing[\Val\],self)
260
261    balancedDelete(r:Map[\Key,Val\]):Map[\Key,Val\] = r
262    balancedAdd(k:Key,v:Val, left:Map[\Key,Val\], right:Map[\Key,Val\]):
263        NodeMap[\Key,Val\] = NodeMap[\Key,Val\](k,v,self,self)
264    concat(t2:Map[\Key,Val\]): Map[\Key,Val\] = t2
265    concat3(k:Key, v:Val, t2:Map[\Key,Val\]): Map[\Key,Val\] = t2.add(k,v)
266    combine[\That,Result\](f:(Key,Val,That)->Maybe[\Result\],
267                           doThis:(Key,Val)->Maybe[\Result\],
268                           doThat:(Key,That)->Maybe[\Result\],
269                           mapThis:Map[\Key,Val\]->Map[\Key,Result\],
270                           mapThat:Map[\Key,That\]->Map[\Key,Result\],
271                           that: Map[\Key,That\]): Map[\Key,Result\] =
272      mapThat(that)
273    mapFilter[\Result\](f:(Key,Val)->Maybe[\Result\]): Map[\Key,Result\] =
274      EmptyMap[\Key,Result\]
275    opr =(self,other:Map[\Key,Val\]):Boolean = other.isEmpty
276end
277
278object NodeMap[\Key,Val\](key:Key, val:Val, left:Map[\Key,Val\], right:Map[\Key,Val\])
279        extends Map[\Key,Val\]
280    sz:ZZ32 = 1 + |left| + |right|
281    getter isEmpty():Boolean = false
282    getter size():ZZ32 = sz
283    getter asDebugString():String =
284      "[" left.asDebugString " (" key "," val ") " right.asDebugString "]"
285    getter asString():String = "{" || ", ".join[\String\](self.map[\String\](fn(k:Key,v:Val):String => k "|->" v)) || "}"
286
287    opr |self| : ZZ32 = sz
288
289    generate[\R\](r: Reduction[\R\], body: (Key,Val)->R): R =
290      r.join(r.join(left.generate[\R\](r,body),body(key,val)),
291             right.generate[\R\](r,body))
292    ivgen[\R\](i0: ZZ32, r: Reduction[\R\], body: (ZZ32,(Key,Val))->R): R = do
293        mi = i0 + |left|
294        r.join(r.join(left.ivgen[\R\](i0,r,body),body(mi,(key,val))),
295               right.ivgen[\R\](mi+1,r,body))
296      end
297    seqgen[\R\](r: Reduction[\R\], body: (Key,Val)->R): R = do
298        ll = left.seqgen[\R\](r,body)
299        mm = body(key,val)
300        lm = r.join(ll,mm)
301        rr = right.seqgen[\R\](r,body)
302        r.join(lm,rr)
303      end
304
305    dom(self): Set[\Key\] = dom(left).concat3(key,dom(right))
306
307    getPair():(Key, Val) = (key,val)
308    getKey():Key = key
309    getVal():Val = val
310    getLeftChild():Map[\Key,Val\] = left
311    getRightChild():Map[\Key,Val\] = right
312
313    minimum():Just[\(Key,Val)\] = do
314        t : NodeMap[\Key,Val\] := self
315        notDone : Boolean := true
316        while notDone do
317            typecase l = t.getLeftChild() of
318                NodeMap[\Key,Val\] => t := l
319                else => notDone := false
320            end
321        end
322        Just[\(Key,Val)\](t.getPair())
323      end
324    extractMinimum():Just[\(Key,Val,Map[\Key,Val\])\] =
325        if (k,v,delmin) <- left.extractMinimum() then
326            Just[\(Key,Val,Map[\Key,Val\])\](k,v, balancedAdd(key,val,delmin,right))
327        else
328            Just[\(Key,Val,Map[\Key,Val\])\](key,val,right)
329        end
330    maximum():Just[\(Key,Val)\] = do
331        t : NodeMap[\Key,Val\] := self
332        notDone : Boolean := true
333        while notDone do
334            typecase r = t.getRightChild() of
335                NodeMap[\Key,Val\] => t := r
336                else => notDone := false
337            end
338        end
339        Just[\(Key,Val)\](t.getPair())
340      end
341    extractMaximum():Just[\(Key,Val,Map[\Key,Val\])\] =
342        if (k,v,delmax) <- right.extractMaximum() then
343            Just[\(Key,Val,Map[\Key,Val\])\](k,v, balancedAdd(key,val,left,delmax))
344        else
345            Just[\(Key,Val,Map[\Key,Val\])\](key,val,left)
346        end
347
348    add(k:Key, v:Val):Map[\Key,Val\] =
349      typecase _ = k CMP key of
350          EqualTo  => self
351          LessThan => balancedAdd(key,val,left.add(k,v),right)
352          else     => balancedAdd(key,val,left,right.add(k,v))
353      end
354
355    update(k:Key, v:Val):Map[\Key,Val\] =
356      typecase _ = k CMP key of
357          EqualTo  => NodeMap[\Key,Val\](k,v, left, right)
358          LessThan => NodeMap[\Key,Val\](key, val, left.update(k,v), right)
359          else     => NodeMap[\Key,Val\](key, val, left, right.update(k,v))
360      end
361
362    delete(k:Key):Map[\Key,Val\] =
363      typecase _ = k CMP key of
364          LessThan    => balancedAdd(key,val,left.delete(k),right)
365          GreaterThan => balancedAdd(key,val,left,right.delete(k))
366          else        => left.balancedDelete(right)
367      end
368
369    updateWith(f:Maybe[\Val\]->Maybe[\Val\], k:Key): Map[\Key,Val\] =
370      typecase _ = k CMP key of
371          LessThan    => balancedAdd(key,val, left.updateWith(f,k), right)
372          GreaterThan => balancedAdd(key,val, left, right.updateWith(f,k))
373          else =>
374              if r <- f(Just[\Val\](val))
375              then NodeMap[\Key,Val\](k,r, left, right)
376              else left.balancedDelete(right) end
377      end
378
379    opr UNION(self, other: Map[\Key,Val\]): Map[\Key,Val\] = do
380        (newl, _, newr) = other.splitAt(key)
381        (left UNION newl).concat3(key,val,right UNION newr)
382      end
383    opr UPLUS(self, other: Map[\Key,Val\]): Map[\Key,Val\] = do
384        (newl, mv, newr) = other.splitAt(key)
385        if m <- mv then
386            throw KeyOverlap[\Key,Val\](key,val,m)
387        else
388            (left UPLUS newl).concat3(key,val,right UPLUS newr)
389        end
390      end
391    union(f:(Key,Val,Val)->Val, other: Map[\Key,Val\]): Map[\Key,Val\] = do
392        (newl, mv, newr) = other.splitAt(key)
393        val' = if v <- mv
394               then f(key,val,mv.get)
395               else val end
396        left.union(f,newl).concat3(key,val',right.union(f,newr))
397      end
398    splitAt(k:Key):(Map[\Key,Val\],Maybe[\Val\],Map[\Key,Val\]) =
399        typecase _ = k CMP key of
400            LessThan =>
401                (ll, v, rl) = left.splitAt(k)
402                (ll, v, rl.concat3(key,val,right))
403            GreaterThan =>
404                (lr, v, rr) = right.splitAt(k)
405                (left.concat3(key,val,lr), v, rr)
406            else =>
407                (left, Just[\Val\](val), right)
408        end
409
410    concat(t2:Map[\Key,Val\]): Map[\Key,Val\] =
411        if (k,v,butMin) <- t2.extractMinimum() then
412            self.concat3(k,v,butMin)
413        else
414            self
415        end
416    concat3(k:Key, v:Val, t2:Map[\Key,Val\]): Map[\Key,Val\] = add(k,v)
417    concat3(k:Key, v:Val, t2:NodeMap[\Key,Val\]): Map[\Key,Val\] =
418        typecase _ = sz CMP |t2| of
419            LessThan =>
420                balancedAdd(t2.key,t2.val,concat3(k,v,t2.left),t2.right)
421            GreaterThan =>
422                balancedAdd(key,val,left,right.concat3(k,v,t2))
423            else =>
424                NodeMap[\Key,Val\](k,v,self,t2)
425        end
426
427    combine[\That,Result\](f:(Key,Val,That)->Maybe[\Result\],
428                           doThis:(Key,Val)->Maybe[\Result\],
429                           doThat:(Key,That)->Maybe[\Result\],
430                           mapThis:Map[\Key,Val\]->Map[\Key,Result\],
431                           mapThat:Map[\Key,That\]->Map[\Key,Result\],
432                           that: Map[\Key,That\]): Map[\Key,Result\] =
433        if that.isEmpty then mapThis(self)
434        else
435            (l,mv,r) = that.splitAt(key)
436            (lc,mc,rc) = (left.combine[\That,Result\](f,doThis,doThat,mapThis,mapThat,l),
437                          if v <- mv
438                          then f(key,val,v)
439                          else doThis(key,val) end,
440                          right.combine[\That,Result\](f,doThis,doThat,mapThis,mapThat,r))
441            if c <- mc
442            then lc.concat3(key,c,rc)
443            else lc.concat(rc) end
444        end
445    mapFilter[\Result\](f:(Key,Val)->Maybe[\Result\]): Map[\Key,Result\] = do
446        (lf,nv,rf) = (left.mapFilter[\Result\](f), f(key,val),
447                      right.mapFilter[\Result\](f))
448        if v <- nv
449        then lf.concat3(key,v,rf)
450        else lf.concat(rf) end
451      end
452
453    opr =(self,other:Map[\Key,Val\]): Boolean =
454        if self SEQV other then true
455        elif other.isEmpty then false
456        else
457            (l,m,r) = other.splitAt(key)
458            if v <- m
459            then (val=v) AND: (left=l AND right=r)
460            else false end
461        end
462
463    balancedDelete(r:Map[\Key,Val\]):Map[\Key,Val\] =
464        if (min_k, min_v, del_min) <- r.extractMinimum() then
465            balancedAdd(min_k, min_v, self, del_min)
466        else
467            self
468        end
469
470    balancedAdd(k:Key, v:Val, l:Map[\Key,Val\], r:Map[\Key,Val\]):NodeMap[\Key,Val\] = do
471      ln = |l|
472      rn = |r|
473      if ln + rn < weight then NodeMap[\Key,Val\](k,v, l, r)
474      elif rn > weight ln then
475        rl = r.getLeftChild()
476        rr = r.getRightChild()
477        rln = |rl|
478        rrn = |rr|
479        if rln < rrn
480        then single_L(k,v, l, r)
481        else double_L(k,v, l, r)
482        end
483      elif ln > weight rn then
484        ll = l.getLeftChild()
485        lr = l.getRightChild()
486        lln = |ll|
487        lrn = |lr|
488        if lrn < lln
489        then single_R(k,v, l, r)
490        else double_R(k,v, l, r)
491        end
492      else NodeMap[\Key,Val\](k,v, l, r) end
493    end
494
495    single_L(k:Key,v:Val, l:Map[\Key,Val\], r:NodeMap[\Key,Val\]):NodeMap[\Key,Val\] =
496      NodeMap[\Key,Val\](r.getKey(), r.getVal(),
497                         NodeMap[\Key,Val\](k,v, l, r.getLeftChild()),
498                         r.getRightChild())
499
500    single_R(k:Key,v:Val, l:NodeMap[\Key,Val\], r:Map[\Key,Val\]):NodeMap[\Key,Val\] =
501      NodeMap[\Key,Val\](l.getKey(), l.getVal(),
502                         l.getLeftChild(),
503                         NodeMap[\Key,Val\](k,v,l.getRightChild(),r))
504
505    double_L(k:Key,v:Val, l:Map[\Key,Val\], r:NodeMap[\Key,Val\]):NodeMap[\Key,Val\] = do
506        x = l
507        (ck,cv) = r.getPair()
508        (bk,bv) = r.getLeftChild().getPair()
509        (* println("double_L " a ">" b "\\" c) *)
510        y1 = r.getLeftChild().getLeftChild()
511        y2 = r.getLeftChild().getRightChild()
512        z = r.getRightChild()
513        NodeMap[\Key,Val\](bk,bv, NodeMap[\Key,Val\](k,v,x,y1),NodeMap[\Key,Val\](ck,cv,y2,z))
514     end
515
516    double_R(k:Key,v:Val, l:NodeMap[\Key,Val\], r:Map[\Key,Val\]):NodeMap[\Key,Val\] = do
517        (* println("double_R " NodeMap[\Key,Val\](c,l,r).asDebugString) *)
518        (ak,av) = l.getPair()
519        x = l.getLeftChild()
520        (bk,bv) = l.getRightChild().getPair()
521        (* println("double_R " a "/" b "<" c) *)
522        y1 = l.getRightChild().getLeftChild()
523        y2 = l.getRightChild().getRightChild()
524        z = r
525        NodeMap[\Key,Val\](bk,bv, NodeMap[\Key,Val\](ak,av,x,y1), NodeMap[\Key,Val\](k,v,y2,z))
526      end
527end
528
529end
Note: See TracBrowser for help on using the browser.