Return to union-find.sml CVS log

Up to [Research Unix] / researchv10no / cmd / sml / doc / examples

Annotation of researchv10no/cmd/sml/doc/examples/union-find.sml, revision 1.1.1.1

1.1       root        1: (* Union-find algorithm *)
                      2: 
                      3: datatype 'a setelem 
                      4:   = NILSET
                      5:   | ELEM of 'a * 'a setelem ref * int ref
                      6: 
                      7: exception SETINFO
                      8: 
                      9: fun new_setelem x = ELEM(x, ref nilset, ref 1)
                     10: 
                     11: fun set_union(NILSET, f) = f
                     12:   | set_union(e, NILSET) = e
                     13:   | set_union(e as ELEM(_,e_next,e_size), f as ELEM(_,f_next,f_size)) =
                     14:       if !e_size < !f_size
                     15:       then (f_size := !e_size + !f_size; e_next := f)
                     16:       else (e_size := !e_size + !f_size; f_next := e)
                     17: 
                     18: fun find NILSET = NILSET
                     19:   | find (e as ELEM(_,ref NILSET,_)) = e
                     20:   | find (ELEM(_,f,_)) = let g = find !f in (f := g; g) end
                     21: 
                     22: fun setinfo NILSET = raise SETINFO
                     23:   | setinfo e = let ELEM(x,_,_) = find e in x end

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.