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/int-redblack-map.sml
ViewVC logotype

Diff of /smlnj-lib/branches/rt-transition/Util/int-redblack-map.sml

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

revision 468, Wed Nov 10 22:42:52 1999 UTC revision 475, Wed Nov 10 22:59:58 1999 UTC
# Line 267  Line 267 
267              fn (MAP(_, m1), MAP(_, m2)) => cmp (start m1, start m2)              fn (MAP(_, m1), MAP(_, m2)) => cmp (start m1, start m2)
268            end            end
269    
270    (* support for constructing red-black trees in linear time from ordered    (* support for constructing red-black trees in linear time from increasing
271     * sequences (based on a description by R. Hinze).     * ordered sequences (based on a description by R. Hinze).  Note that the
272       * elements in the digits are ordered with the largest on the left, whereas
273       * the elements of the trees are ordered with the largest on the right.
274     *)     *)
275      datatype 'a digit      datatype 'a digit
276        = ZERO        = ZERO
277        | ONE of (int * 'a * 'a tree * 'a digit)        | ONE of (int * 'a * 'a tree * 'a digit)
278        | TWO of (int * 'a * 'a tree * int * 'a * 'a tree * 'a digit)        | TWO of (int * 'a * 'a tree * int * 'a * 'a tree * 'a digit)
279      (* add an item that is guaranteed to be larger than any in l *)
280      fun addItem (ak, a, l) = let      fun addItem (ak, a, l) = let
281            fun incr (ak, a, t, ZERO) = ONE(ak, a, t, ZERO)            fun incr (ak, a, t, ZERO) = ONE(ak, a, t, ZERO)
282              | incr (ak1, a1, t1, ONE(ak2, a2, t2, r)) =              | incr (ak1, a1, t1, ONE(ak2, a2, t2, r)) =
283                  TWO(ak1, a1, t1, ak2, a2, t2, r)                  TWO(ak1, a1, t1, ak2, a2, t2, r)
284              | incr (ak1, a1, t1, TWO(ak2, a2, t2, ak3, a3, t3, r)) =              | incr (ak1, a1, t1, TWO(ak2, a2, t2, ak3, a3, t3, r)) =
285                  ONE(ak1, a1, t1, incr(ak2, a2, T(B, t2, ak3, a3, t3), r))                  ONE(ak1, a1, t1, incr(ak2, a2, T(B, t3, ak3, a3, t2), r))
286            in            in
287              incr(ak, a, E, l)              incr(ak, a, E, l)
288            end            end
289      (* link the digits into a tree *)
290      fun linkAll t = let      fun linkAll t = let
291            fun link (t, ZERO) = t            fun link (t, ZERO) = t
292              | link (t1, ONE(ak, a, t2, r)) = link(T(B, t1, ak, a, t2), r)              | link (t1, ONE(ak, a, t2, r)) = link(T(B, t2, ak, a, t1), r)
293              | link (t, TWO(ak1, a1, t1, ak2, a2, t2, r)) =              | link (t, TWO(ak1, a1, t1, ak2, a2, t2, r)) =
294                  link(T(B, T(R, t, ak1, a1, t1), ak2, a2, t2), r)                  link(T(B, T(R, t2, ak2, a2, t1), ak1, a1, t), r)
295            in            in
296              link (E, t)              link (E, t)
297            end            end

Legend:
Removed from v.468  
changed lines
  Added in v.475

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