Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] View of /archive/0.93/doc/examples/union-find.sml
ViewVC logotype

View of /archive/0.93/doc/examples/union-find.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4958 - (download) (annotate)
Wed Apr 10 01:33:29 2019 UTC (3 months, 1 week ago) by dbm
File size: 664 byte(s)
adding 0.93 src and doc to archive
(* Union-find algorithm *)

datatype 'a setelem 
  = NILSET
  | ELEM of 'a * 'a setelem ref * int ref

exception SETINFO

fun new_setelem x = ELEM(x, ref NILSET, ref 1)

fun set_union(NILSET, f) = f
  | set_union(e, NILSET) = e
  | set_union(e as ELEM(_,e_next,e_size), f as ELEM(_,f_next,f_size)) =
      if !e_size < !f_size
      then (f_size := !e_size + !f_size; e_next := f; f)
      else (e_size := !e_size + !f_size; f_next := e; e)

fun find NILSET = NILSET
  | find (e as ELEM(_,ref NILSET,_)) = e
  | find (ELEM(_,f,_)) = let val g = find (!f) in (f := g; g) end

fun setinfo NILSET = raise SETINFO
  | setinfo e = let val ELEM(x,_,_) = find e in x end

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