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     ! 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.