0000: 27 5c 22 0a 27 5c 22 20 47 65 6e 65 72 61 74 65 '\".'\" Generate
0010: 64 20 66 72 6f 6d 20 66 69 6c 65 20 27 64 69 73 d from file 'dis
0020: 6a 6f 69 6e 74 73 65 74 5c 26 2e 6d 61 6e 27 20 jointset\&.man'
0030: 62 79 20 74 63 6c 6c 69 62 2f 64 6f 63 74 6f 6f by tcllib/doctoo
0040: 6c 73 20 77 69 74 68 20 66 6f 72 6d 61 74 20 27 ls with format '
0050: 6e 72 6f 66 66 27 0a 27 5c 22 0a 2e 54 48 20 22 nroff'.'\"..TH "
0060: 73 74 72 75 63 74 3a 3a 64 69 73 6a 6f 69 6e 74 struct::disjoint
0070: 73 65 74 22 20 6e 20 31 5c 26 2e 32 20 74 63 6c set" n 1\&.2 tcl
0080: 6c 69 62 20 22 54 63 6c 20 44 61 74 61 20 53 74 lib "Tcl Data St
0090: 72 75 63 74 75 72 65 73 22 0a 2e 5c 22 20 54 68 ructures"..\" Th
00a0: 65 20 2d 2a 2d 20 6e 72 6f 66 66 20 2d 2a 2d 20 e -*- nroff -*-
00b0: 64 65 66 69 6e 69 74 69 6f 6e 73 20 62 65 6c 6f definitions belo
00c0: 77 20 61 72 65 20 66 6f 72 20 73 75 70 70 6c 65 w are for supple
00d0: 6d 65 6e 74 61 6c 20 6d 61 63 72 6f 73 20 75 73 mental macros us
00e0: 65 64 0a 2e 5c 22 20 69 6e 20 54 63 6c 2f 54 6b ed..\" in Tcl/Tk
00f0: 20 6d 61 6e 75 61 6c 20 65 6e 74 72 69 65 73 2e manual entries.
0100: 0a 2e 5c 22 0a 2e 5c 22 20 2e 41 50 20 74 79 70 ..\"..\" .AP typ
0110: 65 20 6e 61 6d 65 20 69 6e 2f 6f 75 74 20 3f 69 e name in/out ?i
0120: 6e 64 65 6e 74 3f 0a 2e 5c 22 09 53 74 61 72 74 ndent?..\".Start
0130: 20 70 61 72 61 67 72 61 70 68 20 64 65 73 63 72 paragraph descr
0140: 69 62 69 6e 67 20 61 6e 20 61 72 67 75 6d 65 6e ibing an argumen
0150: 74 20 74 6f 20 61 20 6c 69 62 72 61 72 79 20 70 t to a library p
0160: 72 6f 63 65 64 75 72 65 2e 0a 2e 5c 22 09 74 79 rocedure...\".ty
0170: 70 65 20 69 73 20 74 79 70 65 20 6f 66 20 61 72 pe is type of ar
0180: 67 75 6d 65 6e 74 20 28 69 6e 74 2c 20 65 74 63 gument (int, etc
0190: 2e 29 2c 20 69 6e 2f 6f 75 74 20 69 73 20 65 69 .), in/out is ei
01a0: 74 68 65 72 20 22 69 6e 22 2c 20 22 6f 75 74 22 ther "in", "out"
01b0: 2c 0a 2e 5c 22 09 6f 72 20 22 69 6e 2f 6f 75 74 ,..\".or "in/out
01c0: 22 20 74 6f 20 64 65 73 63 72 69 62 65 20 77 68 " to describe wh
01d0: 65 74 68 65 72 20 70 72 6f 63 65 64 75 72 65 20 ether procedure
01e0: 72 65 61 64 73 20 6f 72 20 6d 6f 64 69 66 69 65 reads or modifie
01f0: 73 20 61 72 67 2c 0a 2e 5c 22 09 61 6e 64 20 69 s arg,..\".and i
0200: 6e 64 65 6e 74 20 69 73 20 65 71 75 69 76 61 6c ndent is equival
0210: 65 6e 74 20 74 6f 20 73 65 63 6f 6e 64 20 61 72 ent to second ar
0220: 67 20 6f 66 20 2e 49 50 20 28 73 68 6f 75 6c 64 g of .IP (should
0230: 6e 27 74 20 65 76 65 72 20 62 65 0a 2e 5c 22 09 n't ever be..\".
0240: 6e 65 65 64 65 64 3b 20 20 75 73 65 20 2e 41 53 needed; use .AS
0250: 20 62 65 6c 6f 77 20 69 6e 73 74 65 61 64 29 0a below instead).
0260: 2e 5c 22 0a 2e 5c 22 20 2e 41 53 20 3f 74 79 70 .\"..\" .AS ?typ
0270: 65 3f 20 3f 6e 61 6d 65 3f 0a 2e 5c 22 09 47 69 e? ?name?..\".Gi
0280: 76 65 20 6d 61 78 69 6d 75 6d 20 73 69 7a 65 73 ve maximum sizes
0290: 20 6f 66 20 61 72 67 75 6d 65 6e 74 73 20 66 6f of arguments fo
02a0: 72 20 73 65 74 74 69 6e 67 20 74 61 62 20 73 74 r setting tab st
02b0: 6f 70 73 2e 20 20 54 79 70 65 20 61 6e 64 0a 2e ops. Type and..
02c0: 5c 22 09 6e 61 6d 65 20 61 72 65 20 65 78 61 6d \".name are exam
02d0: 70 6c 65 73 20 6f 66 20 6c 61 72 67 65 73 74 20 ples of largest
02e0: 70 6f 73 73 69 62 6c 65 20 61 72 67 75 6d 65 6e possible argumen
02f0: 74 73 20 74 68 61 74 20 77 69 6c 6c 20 62 65 20 ts that will be
0300: 70 61 73 73 65 64 0a 2e 5c 22 09 74 6f 20 2e 41 passed..\".to .A
0310: 50 20 6c 61 74 65 72 2e 20 20 49 66 20 61 72 67 P later. If arg
0320: 73 20 61 72 65 20 6f 6d 69 74 74 65 64 2c 20 64 s are omitted, d
0330: 65 66 61 75 6c 74 20 74 61 62 20 73 74 6f 70 73 efault tab stops
0340: 20 61 72 65 20 75 73 65 64 2e 0a 2e 5c 22 0a 2e are used...\"..
0350: 5c 22 20 2e 42 53 0a 2e 5c 22 09 53 74 61 72 74 \" .BS..\".Start
0360: 20 62 6f 78 20 65 6e 63 6c 6f 73 75 72 65 2e 20 box enclosure.
0370: 20 46 72 6f 6d 20 68 65 72 65 20 75 6e 74 69 6c From here until
0380: 20 6e 65 78 74 20 2e 42 45 2c 20 65 76 65 72 79 next .BE, every
0390: 74 68 69 6e 67 20 77 69 6c 6c 20 62 65 0a 2e 5c thing will be..\
03a0: 22 09 65 6e 63 6c 6f 73 65 64 20 69 6e 20 6f 6e ".enclosed in on
03b0: 65 20 6c 61 72 67 65 20 62 6f 78 2e 0a 2e 5c 22 e large box...\"
03c0: 0a 2e 5c 22 20 2e 42 45 0a 2e 5c 22 09 45 6e 64 ..\" .BE..\".End
03d0: 20 6f 66 20 62 6f 78 20 65 6e 63 6c 6f 73 75 72 of box enclosur
03e0: 65 2e 0a 2e 5c 22 0a 2e 5c 22 20 2e 43 53 0a 2e e...\"..\" .CS..
03f0: 5c 22 09 42 65 67 69 6e 20 63 6f 64 65 20 65 78 \".Begin code ex
0400: 63 65 72 70 74 2e 0a 2e 5c 22 0a 2e 5c 22 20 2e cerpt...\"..\" .
0410: 43 45 0a 2e 5c 22 09 45 6e 64 20 63 6f 64 65 20 CE..\".End code
0420: 65 78 63 65 72 70 74 2e 0a 2e 5c 22 0a 2e 5c 22 excerpt...\"..\"
0430: 20 2e 56 53 20 3f 76 65 72 73 69 6f 6e 3f 20 3f .VS ?version? ?
0440: 62 72 3f 0a 2e 5c 22 09 42 65 67 69 6e 20 76 65 br?..\".Begin ve
0450: 72 74 69 63 61 6c 20 73 69 64 65 62 61 72 2c 20 rtical sidebar,
0460: 66 6f 72 20 75 73 65 20 69 6e 20 6d 61 72 6b 69 for use in marki
0470: 6e 67 20 6e 65 77 6c 79 2d 63 68 61 6e 67 65 64 ng newly-changed
0480: 20 70 61 72 74 73 0a 2e 5c 22 09 6f 66 20 6d 61 parts..\".of ma
0490: 6e 20 70 61 67 65 73 2e 20 20 54 68 65 20 66 69 n pages. The fi
04a0: 72 73 74 20 61 72 67 75 6d 65 6e 74 20 69 73 20 rst argument is
04b0: 69 67 6e 6f 72 65 64 20 61 6e 64 20 75 73 65 64 ignored and used
04c0: 20 66 6f 72 20 72 65 63 6f 72 64 69 6e 67 0a 2e for recording..
04d0: 5c 22 09 74 68 65 20 76 65 72 73 69 6f 6e 20 77 \".the version w
04e0: 68 65 6e 20 74 68 65 20 2e 56 53 20 77 61 73 20 hen the .VS was
04f0: 61 64 64 65 64 2c 20 73 6f 20 74 68 61 74 20 74 added, so that t
0500: 68 65 20 73 69 64 65 62 61 72 73 20 63 61 6e 20 he sidebars can
0510: 62 65 0a 2e 5c 22 09 66 6f 75 6e 64 20 61 6e 64 be..\".found and
0520: 20 72 65 6d 6f 76 65 64 20 77 68 65 6e 20 74 68 removed when th
0530: 65 79 20 72 65 61 63 68 20 61 20 63 65 72 74 61 ey reach a certa
0540: 69 6e 20 61 67 65 2e 20 20 49 66 20 61 6e 6f 74 in age. If anot
0550: 68 65 72 20 61 72 67 75 6d 65 6e 74 0a 2e 5c 22 her argument..\"
0560: 09 69 73 20 70 72 65 73 65 6e 74 2c 20 74 68 65 .is present, the
0570: 6e 20 61 20 6c 69 6e 65 20 62 72 65 61 6b 20 69 n a line break i
0580: 73 20 66 6f 72 63 65 64 20 62 65 66 6f 72 65 20 s forced before
0590: 73 74 61 72 74 69 6e 67 20 74 68 65 20 73 69 64 starting the sid
05a0: 65 62 61 72 2e 0a 2e 5c 22 0a 2e 5c 22 20 2e 56 ebar...\"..\" .V
05b0: 45 0a 2e 5c 22 09 45 6e 64 20 6f 66 20 76 65 72 E..\".End of ver
05c0: 74 69 63 61 6c 20 73 69 64 65 62 61 72 2e 0a 2e tical sidebar...
05d0: 5c 22 0a 2e 5c 22 20 2e 44 53 0a 2e 5c 22 09 42 \"..\" .DS..\".B
05e0: 65 67 69 6e 20 61 6e 20 69 6e 64 65 6e 74 65 64 egin an indented
05f0: 20 75 6e 66 69 6c 6c 65 64 20 64 69 73 70 6c 61 unfilled displa
0600: 79 2e 0a 2e 5c 22 0a 2e 5c 22 20 2e 44 45 0a 2e y...\"..\" .DE..
0610: 5c 22 09 45 6e 64 20 6f 66 20 69 6e 64 65 6e 74 \".End of indent
0620: 65 64 20 75 6e 66 69 6c 6c 65 64 20 64 69 73 70 ed unfilled disp
0630: 6c 61 79 2e 0a 2e 5c 22 0a 2e 5c 22 20 2e 53 4f lay...\"..\" .SO
0640: 20 3f 6d 61 6e 70 61 67 65 3f 0a 2e 5c 22 09 53 ?manpage?..\".S
0650: 74 61 72 74 20 6f 66 20 6c 69 73 74 20 6f 66 20 tart of list of
0660: 73 74 61 6e 64 61 72 64 20 6f 70 74 69 6f 6e 73 standard options
0670: 20 66 6f 72 20 61 20 54 6b 20 77 69 64 67 65 74 for a Tk widget
0680: 2e 20 54 68 65 20 6d 61 6e 70 61 67 65 0a 2e 5c . The manpage..\
0690: 22 09 61 72 67 75 6d 65 6e 74 20 64 65 66 69 6e ".argument defin
06a0: 65 73 20 77 68 65 72 65 20 74 6f 20 6c 6f 6f 6b es where to look
06b0: 20 75 70 20 74 68 65 20 73 74 61 6e 64 61 72 64 up the standard
06c0: 20 6f 70 74 69 6f 6e 73 3b 20 69 66 0a 2e 5c 22 options; if..\"
06d0: 09 6f 6d 69 74 74 65 64 2c 20 64 65 66 61 75 6c .omitted, defaul
06e0: 74 73 20 74 6f 20 22 6f 70 74 69 6f 6e 73 22 2e ts to "options".
06f0: 20 54 68 65 20 6f 70 74 69 6f 6e 73 20 66 6f 6c The options fol
0700: 6c 6f 77 20 6f 6e 20 73 75 63 63 65 73 73 69 76 low on successiv
0710: 65 0a 2e 5c 22 09 6c 69 6e 65 73 2c 20 69 6e 20 e..\".lines, in
0720: 74 68 72 65 65 20 63 6f 6c 75 6d 6e 73 20 73 65 three columns se
0730: 70 61 72 61 74 65 64 20 62 79 20 74 61 62 73 2e parated by tabs.
0740: 0a 2e 5c 22 0a 2e 5c 22 20 2e 53 45 0a 2e 5c 22 ..\"..\" .SE..\"
0750: 09 45 6e 64 20 6f 66 20 6c 69 73 74 20 6f 66 20 .End of list of
0760: 73 74 61 6e 64 61 72 64 20 6f 70 74 69 6f 6e 73 standard options
0770: 20 66 6f 72 20 61 20 54 6b 20 77 69 64 67 65 74 for a Tk widget
0780: 2e 0a 2e 5c 22 0a 2e 5c 22 20 2e 4f 50 20 63 6d ...\"..\" .OP cm
0790: 64 4e 61 6d 65 20 64 62 4e 61 6d 65 20 64 62 43 dName dbName dbC
07a0: 6c 61 73 73 0a 2e 5c 22 09 53 74 61 72 74 20 6f lass..\".Start o
07b0: 66 20 64 65 73 63 72 69 70 74 69 6f 6e 20 6f 66 f description of
07c0: 20 61 20 73 70 65 63 69 66 69 63 20 6f 70 74 69 a specific opti
07d0: 6f 6e 2e 20 20 63 6d 64 4e 61 6d 65 20 67 69 76 on. cmdName giv
07e0: 65 73 20 74 68 65 0a 2e 5c 22 09 6f 70 74 69 6f es the..\".optio
07f0: 6e 27 73 20 6e 61 6d 65 20 61 73 20 73 70 65 63 n's name as spec
0800: 69 66 69 65 64 20 69 6e 20 74 68 65 20 63 6c 61 ified in the cla
0810: 73 73 20 63 6f 6d 6d 61 6e 64 2c 20 64 62 4e 61 ss command, dbNa
0820: 6d 65 20 67 69 76 65 73 0a 2e 5c 22 09 74 68 65 me gives..\".the
0830: 20 6f 70 74 69 6f 6e 27 73 20 6e 61 6d 65 20 69 option's name i
0840: 6e 20 74 68 65 20 6f 70 74 69 6f 6e 20 64 61 74 n the option dat
0850: 61 62 61 73 65 2c 20 61 6e 64 20 64 62 43 6c 61 abase, and dbCla
0860: 73 73 20 67 69 76 65 73 0a 2e 5c 22 09 74 68 65 ss gives..\".the
0870: 20 6f 70 74 69 6f 6e 27 73 20 63 6c 61 73 73 20 option's class
0880: 69 6e 20 74 68 65 20 6f 70 74 69 6f 6e 20 64 61 in the option da
0890: 74 61 62 61 73 65 2e 0a 2e 5c 22 0a 2e 5c 22 20 tabase...\"..\"
08a0: 2e 55 4c 20 61 72 67 31 20 61 72 67 32 0a 2e 5c .UL arg1 arg2..\
08b0: 22 09 50 72 69 6e 74 20 61 72 67 31 20 75 6e 64 ".Print arg1 und
08c0: 65 72 6c 69 6e 65 64 2c 20 74 68 65 6e 20 70 72 erlined, then pr
08d0: 69 6e 74 20 61 72 67 32 20 6e 6f 72 6d 61 6c 6c int arg2 normall
08e0: 79 2e 0a 2e 5c 22 0a 2e 5c 22 20 2e 51 57 20 61 y...\"..\" .QW a
08f0: 72 67 31 20 3f 61 72 67 32 3f 0a 2e 5c 22 09 50 rg1 ?arg2?..\".P
0900: 72 69 6e 74 20 61 72 67 31 20 69 6e 20 71 75 6f rint arg1 in quo
0910: 74 65 73 2c 20 74 68 65 6e 20 61 72 67 32 20 6e tes, then arg2 n
0920: 6f 72 6d 61 6c 6c 79 20 28 66 6f 72 20 74 72 61 ormally (for tra
0930: 69 6c 69 6e 67 20 70 75 6e 63 74 75 61 74 69 6f iling punctuatio
0940: 6e 29 2e 0a 2e 5c 22 0a 2e 5c 22 20 2e 50 51 20 n)...\"..\" .PQ
0950: 61 72 67 31 20 3f 61 72 67 32 3f 0a 2e 5c 22 09 arg1 ?arg2?..\".
0960: 50 72 69 6e 74 20 61 6e 20 6f 70 65 6e 20 70 61 Print an open pa
0970: 72 65 6e 74 68 65 73 69 73 2c 20 61 72 67 31 20 renthesis, arg1
0980: 69 6e 20 71 75 6f 74 65 73 2c 20 74 68 65 6e 20 in quotes, then
0990: 61 72 67 32 20 6e 6f 72 6d 61 6c 6c 79 0a 2e 5c arg2 normally..\
09a0: 22 09 28 66 6f 72 20 74 72 61 69 6c 69 6e 67 20 ".(for trailing
09b0: 70 75 6e 63 74 75 61 74 69 6f 6e 29 20 61 6e 64 punctuation) and
09c0: 20 74 68 65 6e 20 61 20 63 6c 6f 73 69 6e 67 20 then a closing
09d0: 70 61 72 65 6e 74 68 65 73 69 73 2e 0a 2e 5c 22 parenthesis...\"
09e0: 0a 2e 5c 22 09 23 20 53 65 74 20 75 70 20 74 72 ..\".# Set up tr
09f0: 61 70 73 20 61 6e 64 20 6f 74 68 65 72 20 6d 69 aps and other mi
0a00: 73 63 65 6c 6c 61 6e 65 6f 75 73 20 73 74 75 66 scellaneous stuf
0a10: 66 20 66 6f 72 20 54 63 6c 2f 54 6b 20 6d 61 6e f for Tcl/Tk man
0a20: 20 70 61 67 65 73 2e 0a 2e 69 66 20 74 20 2e 77 pages...if t .w
0a30: 68 20 2d 31 2e 33 69 20 5e 42 0a 2e 6e 72 20 5e h -1.3i ^B..nr ^
0a40: 6c 20 5c 6e 28 2e 6c 0a 2e 61 64 20 62 0a 2e 5c l \n(.l..ad b..\
0a50: 22 09 23 20 53 74 61 72 74 20 61 6e 20 61 72 67 ".# Start an arg
0a60: 75 6d 65 6e 74 20 64 65 73 63 72 69 70 74 69 6f ument descriptio
0a70: 6e 0a 2e 64 65 20 41 50 0a 2e 69 65 20 21 22 5c n..de AP..ie !"\
0a80: 5c 24 34 22 22 20 2e 54 50 20 5c 5c 24 34 0a 2e \$4"" .TP \\$4..
0a90: 65 6c 20 5c 7b 5c 0a 2e 20 20 20 69 65 20 21 22 el \{\.. ie !"
0aa0: 5c 5c 24 32 22 22 20 2e 54 50 20 5c 5c 6e 28 29 \\$2"" .TP \\n()
0ab0: 43 75 0a 2e 20 20 20 65 6c 20 20 20 20 20 20 20 Cu.. el
0ac0: 20 20 20 2e 54 50 20 31 35 0a 2e 5c 7d 0a 2e 74 .TP 15..\}..t
0ad0: 61 20 5c 5c 6e 28 29 41 75 20 5c 5c 6e 28 29 42 a \\n()Au \\n()B
0ae0: 75 0a 2e 69 65 20 21 22 5c 5c 24 33 22 22 20 5c u..ie !"\\$3"" \
0af0: 7b 5c 0a 5c 26 5c 5c 24 31 20 5c 5c 66 49 5c 5c {\.\&\\$1 \\fI\\
0b00: 24 32 5c 5c 66 50 20 28 5c 5c 24 33 29 0a 2e 5c $2\\fP (\\$3)..\
0b10: 22 2e 62 0a 2e 5c 7d 0a 2e 65 6c 20 5c 7b 5c 0a ".b..\}..el \{\.
0b20: 2e 62 72 0a 2e 69 65 20 21 22 5c 5c 24 32 22 22 .br..ie !"\\$2""
0b30: 20 5c 7b 5c 0a 5c 26 5c 5c 24 31 09 5c 5c 66 49 \{\.\&\\$1.\\fI
0b40: 5c 5c 24 32 5c 5c 66 50 0a 2e 5c 7d 0a 2e 65 6c \\$2\\fP..\}..el
0b50: 20 5c 7b 5c 0a 5c 26 5c 5c 66 49 5c 5c 24 31 5c \{\.\&\\fI\\$1\
0b60: 5c 66 50 0a 2e 5c 7d 0a 2e 5c 7d 0a 2e 2e 0a 2e \fP..\}..\}.....
0b70: 5c 22 09 23 20 64 65 66 69 6e 65 20 74 61 62 62 \".# define tabb
0b80: 69 6e 67 20 76 61 6c 75 65 73 20 66 6f 72 20 2e ing values for .
0b90: 41 50 0a 2e 64 65 20 41 53 0a 2e 6e 72 20 29 41 AP..de AS..nr )A
0ba0: 20 31 30 6e 0a 2e 69 66 20 21 22 5c 5c 24 31 22 10n..if !"\\$1"
0bb0: 22 20 2e 6e 72 20 29 41 20 5c 5c 77 27 5c 5c 24 " .nr )A \\w'\\$
0bc0: 31 27 75 2b 33 6e 0a 2e 6e 72 20 29 42 20 5c 5c 1'u+3n..nr )B \\
0bd0: 6e 28 29 41 75 2b 31 35 6e 0a 2e 5c 22 0a 2e 69 n()Au+15n..\"..i
0be0: 66 20 21 22 5c 5c 24 32 22 22 20 2e 6e 72 20 29 f !"\\$2"" .nr )
0bf0: 42 20 5c 5c 77 27 5c 5c 24 32 27 75 2b 5c 5c 6e B \\w'\\$2'u+\\n
0c00: 28 29 41 75 2b 33 6e 0a 2e 6e 72 20 29 43 20 5c ()Au+3n..nr )C \
0c10: 5c 6e 28 29 42 75 2b 5c 5c 77 27 28 69 6e 2f 6f \n()Bu+\\w'(in/o
0c20: 75 74 29 27 75 2b 32 6e 0a 2e 2e 0a 2e 41 53 20 ut)'u+2n.....AS
0c30: 54 63 6c 5f 49 6e 74 65 72 70 20 54 63 6c 5f 43 Tcl_Interp Tcl_C
0c40: 72 65 61 74 65 49 6e 74 65 72 70 20 69 6e 2f 6f reateInterp in/o
0c50: 75 74 0a 2e 5c 22 09 23 20 42 53 20 2d 20 73 74 ut..\".# BS - st
0c60: 61 72 74 20 62 6f 78 65 64 20 74 65 78 74 0a 2e art boxed text..
0c70: 5c 22 09 23 20 5e 79 20 3d 20 73 74 61 72 74 69 \".# ^y = starti
0c80: 6e 67 20 79 20 6c 6f 63 61 74 69 6f 6e 0a 2e 5c ng y location..\
0c90: 22 09 23 20 5e 62 20 3d 20 31 0a 2e 64 65 20 42 ".# ^b = 1..de B
0ca0: 53 0a 2e 62 72 0a 2e 6d 6b 20 5e 79 0a 2e 6e 72 S..br..mk ^y..nr
0cb0: 20 5e 62 20 31 75 0a 2e 69 66 20 6e 20 2e 6e 66 ^b 1u..if n .nf
0cc0: 0a 2e 69 66 20 6e 20 2e 74 69 20 30 0a 2e 69 66 ..if n .ti 0..if
0cd0: 20 6e 20 5c 6c 27 5c 5c 6e 28 2e 6c 75 5c 28 75 n \l'\\n(.lu\(u
0ce0: 6c 27 0a 2e 69 66 20 6e 20 2e 66 69 0a 2e 2e 0a l'..if n .fi....
0cf0: 2e 5c 22 09 23 20 42 45 20 2d 20 65 6e 64 20 62 .\".# BE - end b
0d00: 6f 78 65 64 20 74 65 78 74 20 28 64 72 61 77 20 oxed text (draw
0d10: 62 6f 78 20 6e 6f 77 29 0a 2e 64 65 20 42 45 0a box now)..de BE.
0d20: 2e 6e 66 0a 2e 74 69 20 30 0a 2e 6d 6b 20 5e 74 .nf..ti 0..mk ^t
0d30: 0a 2e 69 65 20 6e 20 5c 6c 27 5c 5c 6e 28 5e 6c ..ie n \l'\\n(^l
0d40: 75 5c 28 75 6c 27 0a 2e 65 6c 20 5c 7b 5c 0a 2e u\(ul'..el \{\..
0d50: 5c 22 09 44 72 61 77 20 66 6f 75 72 2d 73 69 64 \".Draw four-sid
0d60: 65 64 20 62 6f 78 20 6e 6f 72 6d 61 6c 6c 79 2c ed box normally,
0d70: 20 62 75 74 20 64 6f 6e 27 74 20 64 72 61 77 20 but don't draw
0d80: 74 6f 70 20 6f 66 0a 2e 5c 22 09 62 6f 78 20 69 top of..\".box i
0d90: 66 20 74 68 65 20 62 6f 78 20 73 74 61 72 74 65 f the box starte
0da0: 64 20 6f 6e 20 61 6e 20 65 61 72 6c 69 65 72 20 d on an earlier
0db0: 70 61 67 65 2e 0a 2e 69 65 20 21 5c 5c 6e 28 5e page...ie !\\n(^
0dc0: 62 2d 31 20 5c 7b 5c 0a 5c 68 27 2d 31 2e 35 6e b-1 \{\.\h'-1.5n
0dd0: 27 5c 4c 27 7c 5c 5c 6e 28 5e 79 75 2d 31 76 27 '\L'|\\n(^yu-1v'
0de0: 5c 6c 27 5c 5c 6e 28 5e 6c 75 2b 33 6e 5c 28 75 \l'\\n(^lu+3n\(u
0df0: 6c 27 5c 4c 27 5c 5c 6e 28 5e 74 75 2b 31 76 2d l'\L'\\n(^tu+1v-
0e00: 5c 5c 6e 28 5e 79 75 27 5c 6c 27 7c 30 75 2d 31 \\n(^yu'\l'|0u-1
0e10: 2e 35 6e 5c 28 75 6c 27 0a 2e 5c 7d 0a 2e 65 6c .5n\(ul'..\}..el
0e20: 20 5c 7d 5c 0a 5c 68 27 2d 31 2e 35 6e 27 5c 4c \}\.\h'-1.5n'\L
0e30: 27 7c 5c 5c 6e 28 5e 79 75 2d 31 76 27 5c 68 27 '|\\n(^yu-1v'\h'
0e40: 5c 5c 6e 28 5e 6c 75 2b 33 6e 27 5c 4c 27 5c 5c \\n(^lu+3n'\L'\\
0e50: 6e 28 5e 74 75 2b 31 76 2d 5c 5c 6e 28 5e 79 75 n(^tu+1v-\\n(^yu
0e60: 27 5c 6c 27 7c 30 75 2d 31 2e 35 6e 5c 28 75 6c '\l'|0u-1.5n\(ul
0e70: 27 0a 2e 5c 7d 0a 2e 5c 7d 0a 2e 66 69 0a 2e 62 '..\}..\}..fi..b
0e80: 72 0a 2e 6e 72 20 5e 62 20 30 0a 2e 2e 0a 2e 5c r..nr ^b 0.....\
0e90: 22 09 23 20 56 53 20 2d 20 73 74 61 72 74 20 76 ".# VS - start v
0ea0: 65 72 74 69 63 61 6c 20 73 69 64 65 62 61 72 0a ertical sidebar.
0eb0: 2e 5c 22 09 23 20 5e 59 20 3d 20 73 74 61 72 74 .\".# ^Y = start
0ec0: 69 6e 67 20 79 20 6c 6f 63 61 74 69 6f 6e 0a 2e ing y location..
0ed0: 5c 22 09 23 20 5e 76 20 3d 20 31 20 28 66 6f 72 \".# ^v = 1 (for
0ee0: 20 74 72 6f 66 66 3b 20 20 66 6f 72 20 6e 72 6f troff; for nro
0ef0: 66 66 20 74 68 69 73 20 64 6f 65 73 6e 27 74 20 ff this doesn't
0f00: 6d 61 74 74 65 72 29 0a 2e 64 65 20 56 53 0a 2e matter)..de VS..
0f10: 69 66 20 21 22 5c 5c 24 32 22 22 20 2e 62 72 0a if !"\\$2"" .br.
0f20: 2e 6d 6b 20 5e 59 0a 2e 69 65 20 6e 20 27 6d 63 .mk ^Y..ie n 'mc
0f30: 20 5c 73 31 32 5c 28 62 72 5c 73 30 0a 2e 65 6c \s12\(br\s0..el
0f40: 20 2e 6e 72 20 5e 76 20 31 75 0a 2e 2e 0a 2e 5c .nr ^v 1u.....\
0f50: 22 09 23 20 56 45 20 2d 20 65 6e 64 20 6f 66 20 ".# VE - end of
0f60: 76 65 72 74 69 63 61 6c 20 73 69 64 65 62 61 72 vertical sidebar
0f70: 0a 2e 64 65 20 56 45 0a 2e 69 65 20 6e 20 27 6d ..de VE..ie n 'm
0f80: 63 0a 2e 65 6c 20 5c 7b 5c 0a 2e 65 76 20 32 0a c..el \{\..ev 2.
0f90: 2e 6e 66 0a 2e 74 69 20 30 0a 2e 6d 6b 20 5e 74 .nf..ti 0..mk ^t
0fa0: 0a 5c 68 27 7c 5c 5c 6e 28 5e 6c 75 2b 33 6e 27 .\h'|\\n(^lu+3n'
0fb0: 5c 4c 27 7c 5c 5c 6e 28 5e 59 75 2d 31 76 5c 28 \L'|\\n(^Yu-1v\(
0fc0: 62 76 27 5c 76 27 5c 5c 6e 28 5e 74 75 2b 31 76 bv'\v'\\n(^tu+1v
0fd0: 2d 5c 5c 6e 28 5e 59 75 27 5c 68 27 2d 7c 5c 5c -\\n(^Yu'\h'-|\\
0fe0: 6e 28 5e 6c 75 2b 33 6e 27 0a 2e 73 70 20 2d 31 n(^lu+3n'..sp -1
0ff0: 0a 2e 66 69 0a 2e 65 76 0a 2e 5c 7d 0a 2e 6e 72 ..fi..ev..\}..nr
1000: 20 5e 76 20 30 0a 2e 2e 0a 2e 5c 22 09 23 20 53 ^v 0.....\".# S
1010: 70 65 63 69 61 6c 20 6d 61 63 72 6f 20 74 6f 20 pecial macro to
1020: 68 61 6e 64 6c 65 20 70 61 67 65 20 62 6f 74 74 handle page bott
1030: 6f 6d 3a 20 20 66 69 6e 69 73 68 20 6f 66 66 20 om: finish off
1040: 63 75 72 72 65 6e 74 0a 2e 5c 22 09 23 20 62 6f current..\".# bo
1050: 78 2f 73 69 64 65 62 61 72 20 69 66 20 69 6e 20 x/sidebar if in
1060: 62 6f 78 2f 73 69 64 65 62 61 72 20 6d 6f 64 65 box/sidebar mode
1070: 2c 20 74 68 65 6e 20 69 6e 76 6f 6b 65 64 20 73 , then invoked s
1080: 74 61 6e 64 61 72 64 0a 2e 5c 22 09 23 20 70 61 tandard..\".# pa
1090: 67 65 20 62 6f 74 74 6f 6d 20 6d 61 63 72 6f 2e ge bottom macro.
10a0: 0a 2e 64 65 20 5e 42 0a 2e 65 76 20 32 0a 27 74 ..de ^B..ev 2.'t
10b0: 69 20 30 0a 27 6e 66 0a 2e 6d 6b 20 5e 74 0a 2e i 0.'nf..mk ^t..
10c0: 69 66 20 5c 5c 6e 28 5e 62 20 5c 7b 5c 0a 2e 5c if \\n(^b \{\..\
10d0: 22 09 44 72 61 77 20 74 68 72 65 65 2d 73 69 64 ".Draw three-sid
10e0: 65 64 20 62 6f 78 20 69 66 20 74 68 69 73 20 69 ed box if this i
10f0: 73 20 74 68 65 20 62 6f 78 27 73 20 66 69 72 73 s the box's firs
1100: 74 20 70 61 67 65 2c 0a 2e 5c 22 09 64 72 61 77 t page,..\".draw
1110: 20 74 77 6f 20 73 69 64 65 73 20 62 75 74 20 6e two sides but n
1120: 6f 20 74 6f 70 20 6f 74 68 65 72 77 69 73 65 2e o top otherwise.
1130: 0a 2e 69 65 20 21 5c 5c 6e 28 5e 62 2d 31 20 5c ..ie !\\n(^b-1 \
1140: 68 27 2d 31 2e 35 6e 27 5c 4c 27 7c 5c 5c 6e 28 h'-1.5n'\L'|\\n(
1150: 5e 79 75 2d 31 76 27 5c 6c 27 5c 5c 6e 28 5e 6c ^yu-1v'\l'\\n(^l
1160: 75 2b 33 6e 5c 28 75 6c 27 5c 4c 27 5c 5c 6e 28 u+3n\(ul'\L'\\n(
1170: 5e 74 75 2b 31 76 2d 5c 5c 6e 28 5e 79 75 27 5c ^tu+1v-\\n(^yu'\
1180: 68 27 7c 30 75 27 5c 63 0a 2e 65 6c 20 5c 68 27 h'|0u'\c..el \h'
1190: 2d 31 2e 35 6e 27 5c 4c 27 7c 5c 5c 6e 28 5e 79 -1.5n'\L'|\\n(^y
11a0: 75 2d 31 76 27 5c 68 27 5c 5c 6e 28 5e 6c 75 2b u-1v'\h'\\n(^lu+
11b0: 33 6e 27 5c 4c 27 5c 5c 6e 28 5e 74 75 2b 31 76 3n'\L'\\n(^tu+1v
11c0: 2d 5c 5c 6e 28 5e 79 75 27 5c 68 27 7c 30 75 27 -\\n(^yu'\h'|0u'
11d0: 5c 63 0a 2e 5c 7d 0a 2e 69 66 20 5c 5c 6e 28 5e \c..\}..if \\n(^
11e0: 76 20 5c 7b 5c 0a 2e 6e 72 20 5e 78 20 5c 5c 6e v \{\..nr ^x \\n
11f0: 28 5e 74 75 2b 31 76 2d 5c 5c 6e 28 5e 59 75 0a (^tu+1v-\\n(^Yu.
1200: 5c 6b 78 5c 68 27 2d 5c 5c 6e 78 75 27 5c 68 27 \kx\h'-\\nxu'\h'
1210: 7c 5c 5c 6e 28 5e 6c 75 2b 33 6e 27 5c 6b 79 5c |\\n(^lu+3n'\ky\
1220: 4c 27 2d 5c 5c 6e 28 5e 78 75 27 5c 76 27 5c 5c L'-\\n(^xu'\v'\\
1230: 6e 28 5e 78 75 27 5c 68 27 7c 30 75 27 5c 63 0a n(^xu'\h'|0u'\c.
1240: 2e 5c 7d 0a 2e 62 70 0a 27 66 69 0a 2e 65 76 0a .\}..bp.'fi..ev.
1250: 2e 69 66 20 5c 5c 6e 28 5e 62 20 5c 7b 5c 0a 2e .if \\n(^b \{\..
1260: 6d 6b 20 5e 79 0a 2e 6e 72 20 5e 62 20 32 0a 2e mk ^y..nr ^b 2..
1270: 5c 7d 0a 2e 69 66 20 5c 5c 6e 28 5e 76 20 5c 7b \}..if \\n(^v \{
1280: 5c 0a 2e 6d 6b 20 5e 59 0a 2e 5c 7d 0a 2e 2e 0a \..mk ^Y..\}....
1290: 2e 5c 22 09 23 20 44 53 20 2d 20 62 65 67 69 6e .\".# DS - begin
12a0: 20 64 69 73 70 6c 61 79 0a 2e 64 65 20 44 53 0a display..de DS.
12b0: 2e 52 53 0a 2e 6e 66 0a 2e 73 70 0a 2e 2e 0a 2e .RS..nf..sp.....
12c0: 5c 22 09 23 20 44 45 20 2d 20 65 6e 64 20 64 69 \".# DE - end di
12d0: 73 70 6c 61 79 0a 2e 64 65 20 44 45 0a 2e 66 69 splay..de DE..fi
12e0: 0a 2e 52 45 0a 2e 73 70 0a 2e 2e 0a 2e 5c 22 09 ..RE..sp.....\".
12f0: 23 20 53 4f 20 2d 20 73 74 61 72 74 20 6f 66 20 # SO - start of
1300: 6c 69 73 74 20 6f 66 20 73 74 61 6e 64 61 72 64 list of standard
1310: 20 6f 70 74 69 6f 6e 73 0a 2e 64 65 20 53 4f 0a options..de SO.
1320: 27 69 65 20 27 5c 5c 24 31 27 27 20 2e 64 73 20 'ie '\\$1'' .ds
1330: 53 6f 20 5c 5c 66 42 6f 70 74 69 6f 6e 73 5c 5c So \\fBoptions\\
1340: 66 52 0a 27 65 6c 20 2e 64 73 20 53 6f 20 5c 5c fR.'el .ds So \\
1350: 66 42 5c 5c 24 31 5c 5c 66 52 0a 2e 53 48 20 22 fB\\$1\\fR..SH "
1360: 53 54 41 4e 44 41 52 44 20 4f 50 54 49 4f 4e 53 STANDARD OPTIONS
1370: 22 0a 2e 4c 50 0a 2e 6e 66 0a 2e 74 61 20 35 2e "..LP..nf..ta 5.
1380: 35 63 20 31 31 63 0a 2e 66 74 20 42 0a 2e 2e 0a 5c 11c..ft B....
1390: 2e 5c 22 09 23 20 53 45 20 2d 20 65 6e 64 20 6f .\".# SE - end o
13a0: 66 20 6c 69 73 74 20 6f 66 20 73 74 61 6e 64 61 f list of standa
13b0: 72 64 20 6f 70 74 69 6f 6e 73 0a 2e 64 65 20 53 rd options..de S
13c0: 45 0a 2e 66 69 0a 2e 66 74 20 52 0a 2e 4c 50 0a E..fi..ft R..LP.
13d0: 53 65 65 20 74 68 65 20 5c 5c 2a 28 53 6f 20 6d See the \\*(So m
13e0: 61 6e 75 61 6c 20 65 6e 74 72 79 20 66 6f 72 20 anual entry for
13f0: 64 65 74 61 69 6c 73 20 6f 6e 20 74 68 65 20 73 details on the s
1400: 74 61 6e 64 61 72 64 20 6f 70 74 69 6f 6e 73 2e tandard options.
1410: 0a 2e 2e 0a 2e 5c 22 09 23 20 4f 50 20 2d 20 73 .....\".# OP - s
1420: 74 61 72 74 20 6f 66 20 66 75 6c 6c 20 64 65 73 tart of full des
1430: 63 72 69 70 74 69 6f 6e 20 66 6f 72 20 61 20 73 cription for a s
1440: 69 6e 67 6c 65 20 6f 70 74 69 6f 6e 0a 2e 64 65 ingle option..de
1450: 20 4f 50 0a 2e 4c 50 0a 2e 6e 66 0a 2e 74 61 20 OP..LP..nf..ta
1460: 34 63 0a 43 6f 6d 6d 61 6e 64 2d 4c 69 6e 65 20 4c.Command-Line
1470: 4e 61 6d 65 3a 09 5c 5c 66 42 5c 5c 24 31 5c 5c Name:.\\fB\\$1\\
1480: 66 52 0a 44 61 74 61 62 61 73 65 20 4e 61 6d 65 fR.Database Name
1490: 3a 09 5c 5c 66 42 5c 5c 24 32 5c 5c 66 52 0a 44 :.\\fB\\$2\\fR.D
14a0: 61 74 61 62 61 73 65 20 43 6c 61 73 73 3a 09 5c atabase Class:.\
14b0: 5c 66 42 5c 5c 24 33 5c 5c 66 52 0a 2e 66 69 0a \fB\\$3\\fR..fi.
14c0: 2e 49 50 0a 2e 2e 0a 2e 5c 22 09 23 20 43 53 20 .IP.....\".# CS
14d0: 2d 20 62 65 67 69 6e 20 63 6f 64 65 20 65 78 63 - begin code exc
14e0: 65 72 70 74 0a 2e 64 65 20 43 53 0a 2e 52 53 0a erpt..de CS..RS.
14f0: 2e 6e 66 0a 2e 74 61 20 2e 32 35 69 20 2e 35 69 .nf..ta .25i .5i
1500: 20 2e 37 35 69 20 31 69 0a 2e 2e 0a 2e 5c 22 09 .75i 1i.....\".
1510: 23 20 43 45 20 2d 20 65 6e 64 20 63 6f 64 65 20 # CE - end code
1520: 65 78 63 65 72 70 74 0a 2e 64 65 20 43 45 0a 2e excerpt..de CE..
1530: 66 69 0a 2e 52 45 0a 2e 2e 0a 2e 5c 22 09 23 20 fi..RE.....\".#
1540: 55 4c 20 2d 20 75 6e 64 65 72 6c 69 6e 65 20 77 UL - underline w
1550: 6f 72 64 0a 2e 64 65 20 55 4c 0a 5c 5c 24 31 5c ord..de UL.\\$1\
1560: 6c 27 7c 30 5c 28 75 6c 27 5c 5c 24 32 0a 2e 2e l'|0\(ul'\\$2...
1570: 0a 2e 5c 22 09 23 20 51 57 20 2d 20 61 70 70 6c ..\".# QW - appl
1580: 79 20 71 75 6f 74 61 74 69 6f 6e 20 6d 61 72 6b y quotation mark
1590: 73 20 74 6f 20 77 6f 72 64 0a 2e 64 65 20 51 57 s to word..de QW
15a0: 0a 2e 69 65 20 27 5c 5c 2a 28 6c 71 27 22 27 20 ..ie '\\*(lq'"'
15b0: 60 60 5c 5c 24 31 27 27 5c 5c 24 32 0a 2e 5c 22 ``\\$1''\\$2..\"
15c0: 22 20 66 69 78 20 65 6d 61 63 73 20 68 69 67 68 " fix emacs high
15d0: 6c 69 67 68 74 69 6e 67 0a 2e 65 6c 20 5c 5c 2a lighting..el \\*
15e0: 28 6c 71 5c 5c 24 31 5c 5c 2a 28 72 71 5c 5c 24 (lq\\$1\\*(rq\\$
15f0: 32 0a 2e 2e 0a 2e 5c 22 09 23 20 50 51 20 2d 20 2.....\".# PQ -
1600: 61 70 70 6c 79 20 70 61 72 65 6e 73 20 61 6e 64 apply parens and
1610: 20 71 75 6f 74 61 74 69 6f 6e 20 6d 61 72 6b 73 quotation marks
1620: 20 74 6f 20 77 6f 72 64 0a 2e 64 65 20 50 51 0a to word..de PQ.
1630: 2e 69 65 20 27 5c 5c 2a 28 6c 71 27 22 27 20 28 .ie '\\*(lq'"' (
1640: 60 60 5c 5c 24 31 27 27 5c 5c 24 32 29 5c 5c 24 ``\\$1''\\$2)\\$
1650: 33 0a 2e 5c 22 22 20 66 69 78 20 65 6d 61 63 73 3..\"" fix emacs
1660: 20 68 69 67 68 6c 69 67 68 74 69 6e 67 0a 2e 65 highlighting..e
1670: 6c 20 28 5c 5c 2a 28 6c 71 5c 5c 24 31 5c 5c 2a l (\\*(lq\\$1\\*
1680: 28 72 71 5c 5c 24 32 29 5c 5c 24 33 0a 2e 2e 0a (rq\\$2)\\$3....
1690: 2e 5c 22 09 23 20 51 52 20 2d 20 71 75 6f 74 65 .\".# QR - quote
16a0: 64 20 72 61 6e 67 65 0a 2e 64 65 20 51 52 0a 2e d range..de QR..
16b0: 69 65 20 27 5c 5c 2a 28 6c 71 27 22 27 20 60 60 ie '\\*(lq'"' ``
16c0: 5c 5c 24 31 27 27 5c 5c 2d 60 60 5c 5c 24 32 27 \\$1''\\-``\\$2'
16d0: 27 5c 5c 24 33 0a 2e 5c 22 22 20 66 69 78 20 65 '\\$3..\"" fix e
16e0: 6d 61 63 73 20 68 69 67 68 6c 69 67 68 74 69 6e macs highlightin
16f0: 67 0a 2e 65 6c 20 5c 5c 2a 28 6c 71 5c 5c 24 31 g..el \\*(lq\\$1
1700: 5c 5c 2a 28 72 71 5c 5c 2d 5c 5c 2a 28 6c 71 5c \\*(rq\\-\\*(lq\
1710: 5c 24 32 5c 5c 2a 28 72 71 5c 5c 24 33 0a 2e 2e \$2\\*(rq\\$3...
1720: 0a 2e 5c 22 09 23 20 4d 54 20 2d 20 22 65 6d 70 ..\".# MT - "emp
1730: 74 79 22 20 73 74 72 69 6e 67 0a 2e 64 65 20 4d ty" string..de M
1740: 54 0a 2e 51 57 20 22 22 0a 2e 2e 0a 2e 42 53 0a T..QW "".....BS.
1750: 2e 53 48 20 4e 41 4d 45 0a 73 74 72 75 63 74 3a .SH NAME.struct:
1760: 3a 64 69 73 6a 6f 69 6e 74 73 65 74 20 5c 2d 20 :disjointset \-
1770: 44 69 73 6a 6f 69 6e 74 20 73 65 74 20 64 61 74 Disjoint set dat
1780: 61 20 73 74 72 75 63 74 75 72 65 0a 2e 53 48 20 a structure..SH
1790: 53 59 4e 4f 50 53 49 53 0a 70 61 63 6b 61 67 65 SYNOPSIS.package
17a0: 20 72 65 71 75 69 72 65 20 5c 66 42 54 63 6c 20 require \fBTcl
17b0: 20 38 5c 26 2e 36 20 39 5c 66 52 0a 2e 73 70 0a 8\&.6 9\fR..sp.
17c0: 70 61 63 6b 61 67 65 20 72 65 71 75 69 72 65 20 package require
17d0: 5c 66 42 73 74 72 75 63 74 3a 3a 64 69 73 6a 6f \fBstruct::disjo
17e0: 69 6e 74 73 65 74 20 20 3f 31 5c 26 2e 32 3f 5c intset ?1\&.2?\
17f0: 66 52 0a 2e 73 70 0a 5c 66 42 3a 3a 73 74 72 75 fR..sp.\fB::stru
1800: 63 74 3a 3a 64 69 73 6a 6f 69 6e 74 73 65 74 5c ct::disjointset\
1810: 66 52 20 5c 66 49 64 69 73 6a 6f 69 6e 74 73 65 fR \fIdisjointse
1820: 74 4e 61 6d 65 5c 66 52 0a 2e 73 70 0a 5c 66 49 tName\fR..sp.\fI
1830: 64 69 73 6a 6f 69 6e 74 73 65 74 4e 61 6d 65 5c disjointsetName\
1840: 66 52 20 5c 66 49 6f 70 74 69 6f 6e 5c 66 52 20 fR \fIoption\fR
1850: 3f 5c 66 49 61 72 67 20 61 72 67 20 5c 26 2e 5c ?\fIarg arg \&.\
1860: 26 2e 5c 26 2e 5c 66 52 3f 0a 2e 73 70 0a 5c 66 &.\&.\fR?..sp.\f
1870: 49 64 69 73 6a 6f 69 6e 74 73 65 74 4e 61 6d 65 IdisjointsetName
1880: 5c 66 52 20 5c 66 42 61 64 64 2d 65 6c 65 6d 65 \fR \fBadd-eleme
1890: 6e 74 5c 66 52 20 5c 66 49 69 74 65 6d 5c 66 52 nt\fR \fIitem\fR
18a0: 0a 2e 73 70 0a 5c 66 49 64 69 73 6a 6f 69 6e 74 ..sp.\fIdisjoint
18b0: 73 65 74 4e 61 6d 65 5c 66 52 20 5c 66 42 61 64 setName\fR \fBad
18c0: 64 2d 70 61 72 74 69 74 69 6f 6e 5c 66 52 20 5c d-partition\fR \
18d0: 66 49 65 6c 65 6d 65 6e 74 73 5c 66 52 0a 2e 73 fIelements\fR..s
18e0: 70 0a 5c 66 49 64 69 73 6a 6f 69 6e 74 73 65 74 p.\fIdisjointset
18f0: 4e 61 6d 65 5c 66 52 20 5c 66 42 70 61 72 74 69 Name\fR \fBparti
1900: 74 69 6f 6e 73 5c 66 52 0a 2e 73 70 0a 5c 66 49 tions\fR..sp.\fI
1910: 64 69 73 6a 6f 69 6e 74 73 65 74 4e 61 6d 65 5c disjointsetName\
1920: 66 52 20 5c 66 42 6e 75 6d 2d 70 61 72 74 69 74 fR \fBnum-partit
1930: 69 6f 6e 73 5c 66 52 0a 2e 73 70 0a 5c 66 49 64 ions\fR..sp.\fId
1940: 69 73 6a 6f 69 6e 74 73 65 74 4e 61 6d 65 5c 66 isjointsetName\f
1950: 52 20 5c 66 42 65 71 75 61 6c 5c 66 52 20 5c 66 R \fBequal\fR \f
1960: 49 61 5c 66 52 20 5c 66 49 62 5c 66 52 0a 2e 73 Ia\fR \fIb\fR..s
1970: 70 0a 5c 66 49 64 69 73 6a 6f 69 6e 74 73 65 74 p.\fIdisjointset
1980: 4e 61 6d 65 5c 66 52 20 5c 66 42 6d 65 72 67 65 Name\fR \fBmerge
1990: 5c 66 52 20 5c 66 49 61 5c 66 52 20 5c 66 49 62 \fR \fIa\fR \fIb
19a0: 5c 66 52 0a 2e 73 70 0a 5c 66 49 64 69 73 6a 6f \fR..sp.\fIdisjo
19b0: 69 6e 74 73 65 74 4e 61 6d 65 5c 66 52 20 5c 66 intsetName\fR \f
19c0: 42 66 69 6e 64 5c 66 52 20 5c 66 49 65 5c 66 52 Bfind\fR \fIe\fR
19d0: 0a 2e 73 70 0a 5c 66 49 64 69 73 6a 6f 69 6e 74 ..sp.\fIdisjoint
19e0: 73 65 74 4e 61 6d 65 5c 66 52 20 5c 66 42 65 78 setName\fR \fBex
19f0: 65 6d 70 6c 61 72 73 5c 66 52 0a 2e 73 70 0a 5c emplars\fR..sp.\
1a00: 66 49 64 69 73 6a 6f 69 6e 74 73 65 74 4e 61 6d fIdisjointsetNam
1a10: 65 5c 66 52 20 5c 66 42 66 69 6e 64 2d 65 78 65 e\fR \fBfind-exe
1a20: 6d 70 6c 61 72 5c 66 52 20 5c 66 49 65 5c 66 52 mplar\fR \fIe\fR
1a30: 0a 2e 73 70 0a 5c 66 49 64 69 73 6a 6f 69 6e 74 ..sp.\fIdisjoint
1a40: 73 65 74 4e 61 6d 65 5c 66 52 20 5c 66 42 64 65 setName\fR \fBde
1a50: 73 74 72 6f 79 5c 66 52 0a 2e 73 70 0a 2e 42 45 stroy\fR..sp..BE
1a60: 0a 2e 53 48 20 44 45 53 43 52 49 50 54 49 4f 4e ..SH DESCRIPTION
1a70: 0a 2e 50 50 0a 54 68 69 73 20 70 61 63 6b 61 67 ..PP.This packag
1a80: 65 20 70 72 6f 76 69 64 65 73 20 5c 66 49 64 69 e provides \fIdi
1a90: 73 6a 6f 69 6e 74 20 73 65 74 73 5c 66 52 5c 26 sjoint sets\fR\&
1aa0: 2e 20 41 6e 20 61 6c 74 65 72 6e 61 74 69 76 65 . An alternative
1ab0: 20 6e 61 6d 65 20 66 6f 72 0a 74 68 69 73 20 6b name for.this k
1ac0: 69 6e 64 20 6f 66 20 73 74 72 75 63 74 75 72 65 ind of structure
1ad0: 20 69 73 20 5c 66 49 6d 65 72 67 65 2d 66 69 6e is \fImerge-fin
1ae0: 64 5c 66 52 5c 26 2e 0a 2e 50 50 0a 4e 6f 72 6d d\fR\&...PP.Norm
1af0: 61 6c 6c 79 20 77 68 65 6e 20 64 65 61 6c 69 6e ally when dealin
1b00: 67 20 77 69 74 68 20 73 65 74 73 20 61 6e 64 20 g with sets and
1b10: 74 68 65 69 72 20 65 6c 65 6d 65 6e 74 73 20 74 their elements t
1b20: 68 65 20 71 75 65 73 74 69 6f 6e 20 69 73 20 22 he question is "
1b30: 49 73 0a 74 68 69 73 20 65 6c 65 6d 65 6e 74 20 Is.this element
1b40: 45 20 63 6f 6e 74 61 69 6e 65 64 20 69 6e 20 74 E contained in t
1b50: 68 69 73 20 73 65 74 20 53 3f 22 2c 20 77 69 74 his set S?", wit
1b60: 68 20 62 6f 74 68 20 45 20 61 6e 64 20 53 20 6b h both E and S k
1b70: 6e 6f 77 6e 5c 26 2e 0a 2e 50 50 0a 48 65 72 65 nown\&...PP.Here
1b80: 20 74 68 65 20 71 75 65 73 74 69 6f 6e 20 69 73 the question is
1b90: 20 22 57 68 69 63 68 20 6f 66 20 73 65 76 65 72 "Which of sever
1ba0: 61 6c 20 73 65 74 73 20 63 6f 6e 74 61 69 6e 73 al sets contains
1bb0: 20 74 68 65 20 65 6c 65 6d 65 6e 74 0a 45 3f 22 the element.E?"
1bc0: 5c 26 2e 20 49 5c 26 2e 65 5c 26 2e 20 77 68 69 \&. I\&.e\&. whi
1bd0: 6c 65 20 74 68 65 20 65 6c 65 6d 65 6e 74 20 69 le the element i
1be0: 73 20 6b 6e 6f 77 6e 2c 20 74 68 65 20 73 65 74 s known, the set
1bf0: 20 69 73 20 6e 6f 74 2c 20 61 6e 64 20 77 65 20 is not, and we
1c00: 77 69 73 68 20 74 6f 0a 66 69 6e 64 20 69 74 20 wish to.find it
1c10: 71 75 69 63 6b 6c 79 5c 26 2e 20 49 74 20 69 73 quickly\&. It is
1c20: 20 6e 6f 74 20 71 75 69 74 65 20 74 68 65 20 69 not quite the i
1c30: 6e 76 65 72 73 65 20 6f 66 20 74 68 65 20 6f 72 nverse of the or
1c40: 69 67 69 6e 61 6c 20 71 75 65 73 74 69 6f 6e 2c iginal question,
1c50: 0a 62 75 74 20 63 6c 6f 73 65 5c 26 2e 0a 41 6e .but close\&..An
1c60: 6f 74 68 65 72 20 6f 70 65 72 61 74 69 6f 6e 20 other operation
1c70: 77 68 69 63 68 20 69 73 20 6f 66 74 65 6e 20 77 which is often w
1c80: 61 6e 74 65 64 20 69 73 20 74 68 61 74 20 6f 66 anted is that of
1c90: 20 71 75 69 63 6b 6c 79 20 6d 65 72 67 69 6e 67 quickly merging
1ca0: 20 74 77 6f 0a 73 65 74 73 20 69 6e 74 6f 20 6f two.sets into o
1cb0: 6e 65 2c 20 77 69 74 68 20 74 68 65 20 72 65 73 ne, with the res
1cc0: 75 6c 74 20 73 74 69 6c 6c 20 66 61 73 74 20 66 ult still fast f
1cd0: 6f 72 20 66 69 6e 64 69 6e 67 20 65 6c 65 6d 65 or finding eleme
1ce0: 6e 74 73 5c 26 2e 20 48 65 6e 63 65 0a 74 68 65 nts\&. Hence.the
1cf0: 20 61 6c 74 65 72 6e 61 74 69 76 65 20 74 65 72 alternative ter
1d00: 6d 20 5c 66 49 6d 65 72 67 65 2d 66 69 6e 64 5c m \fImerge-find\
1d10: 66 52 20 66 6f 72 20 74 68 69 73 5c 26 2e 0a 2e fR for this\&...
1d20: 50 50 0a 57 68 79 20 6e 6f 77 20 69 73 20 74 68 PP.Why now is th
1d30: 69 73 20 6e 61 6d 65 64 20 61 20 5c 66 49 64 69 is named a \fIdi
1d40: 73 6a 6f 69 6e 74 2d 73 65 74 5c 66 52 20 3f 0a sjoint-set\fR ?.
1d50: 42 65 63 61 75 73 65 20 61 6e 6f 74 68 65 72 20 Because another
1d60: 77 61 79 20 6f 66 20 64 65 73 63 72 69 62 69 6e way of describin
1d70: 67 20 74 68 65 20 77 68 6f 6c 65 20 73 69 74 75 g the whole situ
1d80: 61 74 69 6f 6e 20 69 73 20 74 68 61 74 20 77 65 ation is that we
1d90: 20 68 61 76 65 0a 2e 49 50 20 5c 28 62 75 0a 61 have..IP \(bu.a
1da0: 20 66 69 6e 69 74 65 20 5c 66 49 73 65 74 5c 66 finite \fIset\f
1db0: 52 20 53 2c 20 63 6f 6e 74 61 69 6e 69 6e 67 0a R S, containing.
1dc0: 2e 49 50 20 5c 28 62 75 0a 61 20 6e 75 6d 62 65 .IP \(bu.a numbe
1dd0: 72 20 6f 66 20 5c 66 49 65 6c 65 6d 65 6e 74 73 r of \fIelements
1de0: 5c 66 52 20 45 2c 20 73 70 6c 69 74 20 69 6e 74 \fR E, split int
1df0: 6f 0a 2e 49 50 20 5c 28 62 75 0a 61 20 73 65 74 o..IP \(bu.a set
1e00: 20 6f 66 20 5c 66 49 70 61 72 74 69 74 69 6f 6e of \fIpartition
1e10: 73 5c 66 52 20 50 5c 26 2e 20 54 68 65 20 6c 61 s\fR P\&. The la
1e20: 74 74 65 72 20 74 65 72 6d 0a 61 70 70 6c 69 65 tter term.applie
1e30: 73 2c 20 62 65 63 61 75 73 65 20 74 68 65 20 69 s, because the i
1e40: 6e 74 65 72 73 65 63 74 69 6f 6e 20 6f 66 20 65 ntersection of e
1e50: 61 63 68 20 70 61 69 72 20 50 2c 20 50 27 20 6f ach pair P, P' o
1e60: 66 0a 70 61 72 74 69 74 69 6f 6e 73 20 69 73 20 f.partitions is
1e70: 65 6d 70 74 79 2c 20 77 69 74 68 20 74 68 65 20 empty, with the
1e80: 75 6e 69 6f 6e 20 6f 66 20 61 6c 6c 20 70 61 72 union of all par
1e90: 74 69 74 69 6f 6e 73 0a 63 6f 76 65 72 69 6e 67 titions.covering
1ea0: 20 74 68 65 20 77 68 6f 6c 65 20 73 65 74 5c 26 the whole set\&
1eb0: 2e 0a 2e 49 50 20 5c 28 62 75 0a 41 6e 20 61 6c ...IP \(bu.An al
1ec0: 74 65 72 6e 61 74 69 76 65 20 6e 61 6d 65 20 66 ternative name f
1ed0: 6f 72 20 74 68 65 20 5c 66 49 70 61 72 74 69 74 or the \fIpartit
1ee0: 69 6f 6e 73 5c 66 52 20 77 6f 75 6c 64 20 62 65 ions\fR would be
1ef0: 0a 5c 66 49 65 71 75 76 61 6c 65 6e 63 65 20 63 .\fIequvalence c
1f00: 6c 61 73 73 65 73 5c 66 52 2c 20 61 6e 64 20 61 lasses\fR, and a
1f10: 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 74 ll elements in t
1f20: 68 65 20 73 61 6d 65 0a 63 6c 61 73 73 20 61 72 he same.class ar
1f30: 65 20 63 6f 6e 73 69 64 65 72 65 64 20 61 73 20 e considered as
1f40: 65 71 75 61 6c 5c 26 2e 0a 2e 50 50 0a 48 65 72 equal\&...PP.Her
1f50: 65 20 69 73 20 61 20 70 69 63 74 6f 72 69 61 6c e is a pictorial
1f60: 20 72 65 70 72 65 73 65 6e 74 61 74 69 6f 6e 20 representation
1f70: 6f 66 20 74 68 65 20 63 6f 6e 63 65 70 74 73 20 of the concepts
1f80: 6c 69 73 74 65 64 20 61 62 6f 76 65 3a 0a 2e 43 listed above:..C
1f90: 53 0a 0a 0a 09 2b 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d S....+----------
1fa0: 2d 2d 2d 2d 2d 2d 2d 2b 20 54 68 65 20 6f 75 74 -------+ The out
1fb0: 65 72 20 6c 69 6e 65 73 20 61 72 65 20 74 68 65 er lines are the
1fc0: 20 62 6f 75 6e 64 61 72 69 65 73 20 6f 66 20 74 boundaries of t
1fd0: 68 65 20 73 65 74 20 53 5c 26 2e 0a 09 7c 20 20 he set S\&...|
1fe0: 20 20 20 20 20 20 20 20 20 2f 20 20 20 20 20 7c / |
1ff0: 20 54 68 65 20 69 6e 6e 65 72 20 72 65 67 69 6f The inner regio
2000: 6e 73 20 64 65 6c 69 6e 65 61 74 65 64 20 62 79 ns delineated by
2010: 20 74 68 65 20 73 6b 65 77 65 64 20 6c 69 6e 65 the skewed line
2020: 73 0a 09 7c 20 20 2a 20 20 20 20 20 20 20 2f 20 s..| * /
2030: 20 20 2a 20 20 7c 20 61 72 65 20 74 68 65 20 70 * | are the p
2040: 61 72 74 69 74 69 6f 6e 73 20 50 5c 26 2e 20 54 artitions P\&. T
2050: 68 65 20 2a 27 73 20 64 65 6e 6f 74 65 20 74 68 he *'s denote th
2060: 65 20 65 6c 65 6d 65 6e 74 73 0a 09 7c 20 20 20 e elements..|
2070: 20 20 20 2a 20 20 2f 20 5c 5c 20 20 20 20 20 7c * / \\ |
2080: 20 45 20 69 6e 20 74 68 65 20 73 65 74 2c 20 65 E in the set, e
2090: 61 63 68 20 69 6e 20 61 20 73 69 6e 67 6c 65 20 ach in a single
20a0: 70 61 72 74 69 74 69 6f 6e 2c 20 74 68 65 69 72 partition, their
20b0: 0a 09 7c 2a 20 20 20 20 20 20 20 2f 20 20 20 5c ..|* / \
20c0: 5c 20 20 20 20 7c 20 65 71 75 69 76 61 6c 65 6e \ | equivalen
20d0: 63 65 20 63 6c 61 73 73 5c 26 2e 0a 09 7c 20 20 ce class\&...|
20e0: 20 20 20 20 20 2f 20 20 2a 20 20 5c 5c 20 20 20 / * \\
20f0: 7c 0a 09 7c 20 20 20 20 20 20 2f 20 2a 20 20 20 |..| / *
2100: 2f 20 20 20 20 7c 0a 09 7c 20 2a 20 20 20 2f 5c / |..| * /\
2110: 5c 20 20 2a 20 2f 20 20 20 20 20 7c 0a 09 7c 20 \ * / |..|
2120: 20 20 20 2f 20 20 5c 5c 20 20 2f 20 20 20 20 20 / \\ /
2130: 20 7c 0a 09 7c 20 20 20 2f 20 20 20 20 5c 5c 2f |..| / \\/
2140: 20 20 2a 20 20 20 20 7c 0a 09 7c 20 20 2f 20 2a * |..| / *
2150: 20 20 20 20 5c 5c 20 20 20 20 20 20 20 7c 0a 09 \\ |..
2160: 7c 20 2f 20 20 20 20 20 2a 20 20 5c 5c 20 20 20 | / * \\
2170: 20 20 20 7c 0a 09 2b 2d 2d 2d 2d 2d 2d 2d 2d 2d |..+---------
2180: 2d 2d 2d 2d 2d 2d 2d 2d 2b 0a 0a 2e 43 45 0a 2e --------+...CE..
2190: 50 50 0a 46 6f 72 20 6d 6f 72 65 20 69 6e 66 6f PP.For more info
21a0: 72 6d 61 74 69 6f 6e 20 73 65 65 20 5c 66 49 68 rmation see \fIh
21b0: 74 74 70 3a 2f 2f 65 6e 5c 26 2e 77 69 6b 69 70 ttp://en\&.wikip
21c0: 65 64 69 61 5c 26 2e 6f 72 67 2f 77 69 6b 69 2f edia\&.org/wiki/
21d0: 44 69 73 6a 6f 69 6e 74 5f 73 65 74 5f 64 61 74 Disjoint_set_dat
21e0: 61 5f 73 74 72 75 63 74 75 72 65 5c 66 52 5c 26 a_structure\fR\&
21f0: 2e 0a 2e 53 48 20 41 50 49 0a 54 68 65 20 70 61 ...SH API.The pa
2200: 63 6b 61 67 65 20 65 78 70 6f 72 74 73 20 61 20 ckage exports a
2210: 73 69 6e 67 6c 65 20 63 6f 6d 6d 61 6e 64 2c 20 single command,
2220: 5c 66 42 3a 3a 73 74 72 75 63 74 3a 3a 64 69 73 \fB::struct::dis
2230: 6a 6f 69 6e 74 73 65 74 5c 66 52 5c 26 2e 20 41 jointset\fR\&. A
2240: 6c 6c 0a 66 75 6e 63 74 69 6f 6e 61 6c 69 74 79 ll.functionality
2250: 20 70 72 6f 76 69 64 65 64 20 68 65 72 65 20 63 provided here c
2260: 61 6e 20 62 65 20 72 65 61 63 68 65 64 20 74 68 an be reached th
2270: 72 6f 75 67 68 20 61 20 73 75 62 63 6f 6d 6d 61 rough a subcomma
2280: 6e 64 20 6f 66 0a 74 68 69 73 20 63 6f 6d 6d 61 nd of.this comma
2290: 6e 64 5c 26 2e 0a 2e 50 50 0a 2e 54 50 0a 5c 66 nd\&...PP..TP.\f
22a0: 42 3a 3a 73 74 72 75 63 74 3a 3a 64 69 73 6a 6f B::struct::disjo
22b0: 69 6e 74 73 65 74 5c 66 52 20 5c 66 49 64 69 73 intset\fR \fIdis
22c0: 6a 6f 69 6e 74 73 65 74 4e 61 6d 65 5c 66 52 0a jointsetName\fR.
22d0: 43 72 65 61 74 65 73 20 61 20 6e 65 77 20 64 69 Creates a new di
22e0: 73 6a 6f 69 6e 74 20 73 65 74 20 6f 62 6a 65 63 sjoint set objec
22f0: 74 20 77 69 74 68 20 61 6e 20 61 73 73 6f 63 69 t with an associ
2300: 61 74 65 64 20 67 6c 6f 62 61 6c 20 54 63 6c 0a ated global Tcl.
2310: 63 6f 6d 6d 61 6e 64 20 77 68 6f 73 65 20 6e 61 command whose na
2320: 6d 65 20 69 73 20 5c 66 49 64 69 73 6a 6f 69 6e me is \fIdisjoin
2330: 74 73 65 74 4e 61 6d 65 5c 66 52 5c 26 2e 20 54 tsetName\fR\&. T
2340: 68 69 73 20 63 6f 6d 6d 61 6e 64 20 6d 61 79 20 his command may
2350: 62 65 20 75 73 65 64 0a 74 6f 20 69 6e 76 6f 6b be used.to invok
2360: 65 20 76 61 72 69 6f 75 73 20 6f 70 65 72 61 74 e various operat
2370: 69 6f 6e 73 20 6f 6e 20 74 68 65 20 64 69 73 6a ions on the disj
2380: 6f 69 6e 74 73 65 74 5c 26 2e 20 49 74 20 68 61 ointset\&. It ha
2390: 73 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 0a s the following.
23a0: 67 65 6e 65 72 61 6c 20 66 6f 72 6d 3a 0a 2e 52 general form:..R
23b0: 53 0a 2e 54 50 0a 5c 66 49 64 69 73 6a 6f 69 6e S..TP.\fIdisjoin
23c0: 74 73 65 74 4e 61 6d 65 5c 66 52 20 5c 66 49 6f tsetName\fR \fIo
23d0: 70 74 69 6f 6e 5c 66 52 20 3f 5c 66 49 61 72 67 ption\fR ?\fIarg
23e0: 20 61 72 67 20 5c 26 2e 5c 26 2e 5c 26 2e 5c 66 arg \&.\&.\&.\f
23f0: 52 3f 0a 54 68 65 20 5c 66 42 6f 70 74 69 6f 6e R?.The \fBoption
2400: 5c 66 52 20 61 6e 64 20 74 68 65 20 5c 66 49 61 \fR and the \fIa
2410: 72 67 5c 66 52 73 20 64 65 74 65 72 6d 69 6e 65 rg\fRs determine
2420: 20 74 68 65 20 65 78 61 63 74 20 62 65 68 61 76 the exact behav
2430: 69 6f 72 20 6f 66 0a 74 68 65 20 63 6f 6d 6d 61 ior of.the comma
2440: 6e 64 5c 26 2e 20 54 68 65 20 66 6f 6c 6c 6f 77 nd\&. The follow
2450: 69 6e 67 20 63 6f 6d 6d 61 6e 64 73 20 61 72 65 ing commands are
2460: 20 70 6f 73 73 69 62 6c 65 20 66 6f 72 20 64 69 possible for di
2470: 73 6a 6f 69 6e 74 73 65 74 0a 6f 62 6a 65 63 74 sjointset.object
2480: 73 3a 0a 2e 52 45 0a 2e 54 50 0a 5c 66 49 64 69 s:..RE..TP.\fIdi
2490: 73 6a 6f 69 6e 74 73 65 74 4e 61 6d 65 5c 66 52 sjointsetName\fR
24a0: 20 5c 66 42 61 64 64 2d 65 6c 65 6d 65 6e 74 5c \fBadd-element\
24b0: 66 52 20 5c 66 49 69 74 65 6d 5c 66 52 0a 43 72 fR \fIitem\fR.Cr
24c0: 65 61 74 65 73 20 61 20 6e 65 77 20 70 61 72 74 eates a new part
24d0: 69 74 69 6f 6e 20 69 6e 20 74 68 65 20 73 70 65 ition in the spe
24e0: 63 69 66 69 65 64 20 64 69 73 6a 6f 69 6e 74 20 cified disjoint
24f0: 73 65 74 2c 20 61 6e 64 20 66 69 6c 6c 73 20 69 set, and fills i
2500: 74 0a 77 69 74 68 20 74 68 65 20 73 69 6e 67 6c t.with the singl
2510: 65 20 69 74 65 6d 20 5c 66 49 69 74 65 6d 5c 66 e item \fIitem\f
2520: 52 5c 26 2e 20 20 54 68 65 20 63 6f 6d 6d 61 6e R\&. The comman
2530: 64 20 6d 61 69 6e 74 61 69 6e 73 0a 74 68 65 20 d maintains.the
2540: 69 6e 74 65 67 72 69 74 79 20 6f 66 20 74 68 65 integrity of the
2550: 20 64 69 73 6a 6f 69 6e 74 20 73 65 74 2c 20 69 disjoint set, i
2560: 5c 26 2e 65 5c 26 2e 20 69 74 20 76 65 72 69 66 \&.e\&. it verif
2570: 69 65 73 20 74 68 61 74 20 6e 6f 6e 65 20 6f 66 ies that none of
2580: 20 74 68 65 0a 5c 66 49 65 6c 65 6d 65 6e 74 73 the.\fIelements
2590: 5c 66 52 20 61 72 65 20 61 6c 72 65 61 64 79 20 \fR are already
25a0: 70 61 72 74 20 6f 66 20 74 68 65 20 64 69 73 6a part of the disj
25b0: 6f 69 6e 74 20 73 65 74 20 61 6e 64 20 74 68 72 oint set and thr
25c0: 6f 77 73 20 61 6e 0a 65 72 72 6f 72 20 6f 74 68 ows an.error oth
25d0: 65 72 77 69 73 65 5c 26 2e 0a 2e 73 70 0a 54 68 erwise\&...sp.Th
25e0: 65 20 72 65 73 75 6c 74 20 6f 66 20 74 68 69 73 e result of this
25f0: 20 6d 65 74 68 6f 64 20 69 73 20 74 68 65 20 65 method is the e
2600: 6d 70 74 79 20 73 74 72 69 6e 67 5c 26 2e 0a 2e mpty string\&...
2610: 73 70 0a 54 68 69 73 20 6d 65 74 68 6f 64 20 72 sp.This method r
2620: 75 6e 73 20 69 6e 20 63 6f 6e 73 74 61 6e 74 20 uns in constant
2630: 74 69 6d 65 5c 26 2e 0a 2e 54 50 0a 5c 66 49 64 time\&...TP.\fId
2640: 69 73 6a 6f 69 6e 74 73 65 74 4e 61 6d 65 5c 66 isjointsetName\f
2650: 52 20 5c 66 42 61 64 64 2d 70 61 72 74 69 74 69 R \fBadd-partiti
2660: 6f 6e 5c 66 52 20 5c 66 49 65 6c 65 6d 65 6e 74 on\fR \fIelement
2670: 73 5c 66 52 0a 43 72 65 61 74 65 73 20 61 20 6e s\fR.Creates a n
2680: 65 77 20 70 61 72 74 69 74 69 6f 6e 20 69 6e 20 ew partition in
2690: 73 70 65 63 69 66 69 65 64 20 64 69 73 6a 6f 69 specified disjoi
26a0: 6e 74 20 73 65 74 2c 20 61 6e 64 20 66 69 6c 6c nt set, and fill
26b0: 73 20 69 74 20 77 69 74 68 0a 74 68 65 20 76 61 s it with.the va
26c0: 6c 75 65 73 20 66 6f 75 6e 64 20 69 6e 20 74 68 lues found in th
26d0: 65 20 73 65 74 20 6f 66 20 5c 66 49 65 6c 65 6d e set of \fIelem
26e0: 65 6e 74 73 5c 66 52 5c 26 2e 20 54 68 65 20 63 ents\fR\&. The c
26f0: 6f 6d 6d 61 6e 64 20 6d 61 69 6e 74 61 69 6e 73 ommand maintains
2700: 0a 74 68 65 20 69 6e 74 65 67 72 69 74 79 20 6f .the integrity o
2710: 66 20 74 68 65 20 64 69 73 6a 6f 69 6e 74 20 73 f the disjoint s
2720: 65 74 2c 20 69 5c 26 2e 65 5c 26 2e 20 69 74 20 et, i\&.e\&. it
2730: 76 65 72 69 66 69 65 73 20 74 68 61 74 20 6e 6f verifies that no
2740: 6e 65 20 6f 66 20 74 68 65 0a 5c 66 49 65 6c 65 ne of the.\fIele
2750: 6d 65 6e 74 73 5c 66 52 20 61 72 65 20 61 6c 72 ments\fR are alr
2760: 65 61 64 79 20 70 61 72 74 20 6f 66 20 74 68 65 eady part of the
2770: 20 64 69 73 6a 6f 69 6e 74 20 73 65 74 20 61 6e disjoint set an
2780: 64 20 74 68 72 6f 77 73 20 61 6e 0a 65 72 72 6f d throws an.erro
2790: 72 20 6f 74 68 65 72 77 69 73 65 5c 26 2e 0a 2e r otherwise\&...
27a0: 73 70 0a 54 68 65 20 72 65 73 75 6c 74 20 6f 66 sp.The result of
27b0: 20 74 68 65 20 63 6f 6d 6d 61 6e 64 20 69 73 20 the command is
27c0: 74 68 65 20 65 6d 70 74 79 20 73 74 72 69 6e 67 the empty string
27d0: 5c 26 2e 0a 2e 73 70 0a 54 68 69 73 20 6d 65 74 \&...sp.This met
27e0: 68 6f 64 20 72 75 6e 73 20 69 6e 20 74 69 6d 65 hod runs in time
27f0: 20 70 72 6f 70 6f 72 74 69 6f 6e 61 6c 20 74 6f proportional to
2800: 20 74 68 65 20 73 69 7a 65 20 6f 66 20 5c 66 49 the size of \fI
2810: 65 6c 65 6d 65 6e 74 73 5c 66 52 5d 5c 26 2e 0a elements\fR]\&..
2820: 2e 54 50 0a 5c 66 49 64 69 73 6a 6f 69 6e 74 73 .TP.\fIdisjoints
2830: 65 74 4e 61 6d 65 5c 66 52 20 5c 66 42 70 61 72 etName\fR \fBpar
2840: 74 69 74 69 6f 6e 73 5c 66 52 0a 52 65 74 75 72 titions\fR.Retur
2850: 6e 73 20 74 68 65 20 73 65 74 20 6f 66 20 70 61 ns the set of pa
2860: 72 74 69 74 69 6f 6e 73 20 74 68 65 20 6e 61 6d rtitions the nam
2870: 65 64 20 64 69 73 6a 6f 69 6e 74 20 73 65 74 20 ed disjoint set
2880: 63 75 72 72 65 6e 74 6c 79 0a 63 6f 6e 73 69 73 currently.consis
2890: 74 73 20 6f 66 5c 26 2e 20 54 68 65 20 66 6f 72 ts of\&. The for
28a0: 6d 20 6f 66 20 74 68 65 20 72 65 73 75 6c 74 20 m of the result
28b0: 69 73 20 61 20 6c 69 73 74 20 6f 66 20 6c 69 73 is a list of lis
28c0: 74 73 3b 20 74 68 65 20 69 6e 6e 65 72 0a 6c 69 ts; the inner.li
28d0: 73 74 73 20 63 6f 6e 74 61 69 6e 20 74 68 65 20 sts contain the
28e0: 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 elements of the
28f0: 70 61 72 74 69 74 69 6f 6e 73 5c 26 2e 0a 2e 73 partitions\&...s
2900: 70 0a 54 68 69 73 20 6d 65 74 68 6f 64 20 72 75 p.This method ru
2910: 6e 73 20 69 6e 20 74 69 6d 65 20 4f 28 4e 2a 61 ns in time O(N*a
2920: 6c 70 68 61 28 4e 29 29 2c 0a 77 68 65 72 65 20 lpha(N)),.where
2930: 4e 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 N is the number
2940: 6f 66 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 74 of elements in t
2950: 68 65 20 64 69 73 6a 6f 69 6e 74 20 73 65 74 20 he disjoint set
2960: 61 6e 64 20 61 6c 70 68 61 0a 69 73 20 74 68 65 and alpha.is the
2970: 20 69 6e 76 65 72 73 65 20 41 63 6b 65 72 6d 61 inverse Ackerma
2980: 6e 6e 20 66 75 6e 63 74 69 6f 6e 5c 26 2e 0a 2e nn function\&...
2990: 54 50 0a 5c 66 49 64 69 73 6a 6f 69 6e 74 73 65 TP.\fIdisjointse
29a0: 74 4e 61 6d 65 5c 66 52 20 5c 66 42 6e 75 6d 2d tName\fR \fBnum-
29b0: 70 61 72 74 69 74 69 6f 6e 73 5c 66 52 0a 52 65 partitions\fR.Re
29c0: 74 75 72 6e 73 20 74 68 65 20 6e 75 6d 62 65 72 turns the number
29d0: 20 6f 66 20 70 61 72 74 69 74 69 6f 6e 73 20 74 of partitions t
29e0: 68 65 20 6e 61 6d 65 64 20 64 69 73 6a 6f 69 6e he named disjoin
29f0: 74 20 73 65 74 20 63 75 72 72 65 6e 74 6c 79 0a t set currently.
2a00: 63 6f 6e 73 69 73 74 73 20 6f 66 5c 26 2e 0a 2e consists of\&...
2a10: 73 70 0a 54 68 69 73 20 6d 65 74 68 6f 64 20 72 sp.This method r
2a20: 75 6e 73 20 69 6e 20 63 6f 6e 73 74 61 6e 74 20 uns in constant
2a30: 74 69 6d 65 5c 26 2e 0a 2e 54 50 0a 5c 66 49 64 time\&...TP.\fId
2a40: 69 73 6a 6f 69 6e 74 73 65 74 4e 61 6d 65 5c 66 isjointsetName\f
2a50: 52 20 5c 66 42 65 71 75 61 6c 5c 66 52 20 5c 66 R \fBequal\fR \f
2a60: 49 61 5c 66 52 20 5c 66 49 62 5c 66 52 0a 44 65 Ia\fR \fIb\fR.De
2a70: 74 65 72 6d 69 6e 65 73 20 69 66 20 74 68 65 20 termines if the
2a80: 74 77 6f 20 65 6c 65 6d 65 6e 74 73 20 5c 66 49 two elements \fI
2a90: 61 5c 66 52 20 61 6e 64 20 5c 66 49 62 5c 66 52 a\fR and \fIb\fR
2aa0: 20 6f 66 20 74 68 65 20 64 69 73 6a 6f 69 6e 74 of the disjoint
2ab0: 20 73 65 74 0a 62 65 6c 6f 6e 67 20 74 6f 20 74 set.belong to t
2ac0: 68 65 20 73 61 6d 65 20 70 61 72 74 69 74 69 6f he same partitio
2ad0: 6e 5c 26 2e 20 54 68 65 20 72 65 73 75 6c 74 20 n\&. The result
2ae0: 6f 66 20 74 68 65 20 6d 65 74 68 6f 64 20 69 73 of the method is
2af0: 20 61 20 62 6f 6f 6c 65 61 6e 0a 76 61 6c 75 65 a boolean.value
2b00: 2c 20 5c 66 42 54 72 75 65 5c 66 52 20 69 66 20 , \fBTrue\fR if
2b10: 74 68 65 20 74 77 6f 20 65 6c 65 6d 65 6e 74 73 the two elements
2b20: 20 61 72 65 20 63 6f 6e 74 61 69 6e 65 64 20 69 are contained i
2b30: 6e 20 74 68 65 20 73 61 6d 65 0a 70 61 72 74 69 n the same.parti
2b40: 74 69 6f 6e 2c 20 61 6e 64 20 5c 66 42 46 61 6c tion, and \fBFal
2b50: 73 65 5c 66 52 20 6f 74 68 65 72 77 69 73 65 5c se\fR otherwise\
2b60: 26 2e 0a 2e 73 70 0a 41 6e 20 65 72 72 6f 72 20 &...sp.An error
2b70: 77 69 6c 6c 20 62 65 20 74 68 72 6f 77 6e 20 69 will be thrown i
2b80: 66 20 65 69 74 68 65 72 20 5c 66 49 61 5c 66 52 f either \fIa\fR
2b90: 20 6f 72 20 5c 66 49 62 5c 66 52 20 61 72 65 20 or \fIb\fR are
2ba0: 6e 6f 74 20 65 6c 65 6d 65 6e 74 73 0a 6f 66 20 not elements.of
2bb0: 74 68 65 20 64 69 73 6a 6f 69 6e 74 20 73 65 74 the disjoint set
2bc0: 5c 26 2e 0a 2e 73 70 0a 54 68 69 73 20 6d 65 74 \&...sp.This met
2bd0: 68 6f 64 20 72 75 6e 73 20 69 6e 20 61 6d 6f 72 hod runs in amor
2be0: 74 69 7a 65 64 20 74 69 6d 65 20 4f 28 61 6c 70 tized time O(alp
2bf0: 68 61 28 4e 29 29 2c 20 77 68 65 72 65 20 4e 20 ha(N)), where N
2c00: 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 is the number of
2c10: 0a 65 6c 65 6d 65 6e 74 73 20 69 6e 20 74 68 65 .elements in the
2c20: 20 6c 61 72 67 65 72 20 70 61 72 74 69 74 69 6f larger partitio
2c30: 6e 20 61 6e 64 20 61 6c 70 68 61 20 69 73 20 74 n and alpha is t
2c40: 68 65 20 69 6e 76 65 72 73 65 20 41 63 6b 65 72 he inverse Acker
2c50: 6d 61 6e 6e 20 66 75 6e 63 74 69 6f 6e 5c 26 2e mann function\&.
2c60: 0a 2e 54 50 0a 5c 66 49 64 69 73 6a 6f 69 6e 74 ..TP.\fIdisjoint
2c70: 73 65 74 4e 61 6d 65 5c 66 52 20 5c 66 42 6d 65 setName\fR \fBme
2c80: 72 67 65 5c 66 52 20 5c 66 49 61 5c 66 52 20 5c rge\fR \fIa\fR \
2c90: 66 49 62 5c 66 52 0a 44 65 74 65 72 6d 69 6e 65 fIb\fR.Determine
2ca0: 73 20 74 68 65 20 70 61 72 74 69 74 69 6f 6e 73 s the partitions
2cb0: 20 74 68 65 20 65 6c 65 6d 65 6e 74 73 20 5c 66 the elements \f
2cc0: 49 61 5c 66 52 20 61 6e 64 20 5c 66 49 62 5c 66 Ia\fR and \fIb\f
2cd0: 52 20 61 72 65 0a 63 6f 6e 74 61 69 6e 65 64 20 R are.contained
2ce0: 69 6e 20 61 6e 64 20 6d 65 72 67 65 73 20 74 68 in and merges th
2cf0: 65 6d 20 69 6e 74 6f 20 61 20 73 69 6e 67 6c 65 em into a single
2d00: 20 70 61 72 74 69 74 69 6f 6e 5c 26 2e 20 20 49 partition\&. I
2d10: 66 20 74 68 65 20 74 77 6f 0a 65 6c 65 6d 65 6e f the two.elemen
2d20: 74 73 20 77 65 72 65 20 61 6c 72 65 61 64 79 20 ts were already
2d30: 63 6f 6e 74 61 69 6e 65 64 20 69 6e 20 74 68 65 contained in the
2d40: 20 73 61 6d 65 20 70 61 72 74 69 74 69 6f 6e 20 same partition
2d50: 6e 6f 74 68 69 6e 67 20 77 69 6c 6c 0a 63 68 61 nothing will.cha
2d60: 6e 67 65 5c 26 2e 0a 2e 73 70 0a 54 68 65 20 72 nge\&...sp.The r
2d70: 65 73 75 6c 74 20 6f 66 20 74 68 65 20 6d 65 74 esult of the met
2d80: 68 6f 64 20 69 73 20 74 68 65 20 65 6d 70 74 79 hod is the empty
2d90: 20 73 74 72 69 6e 67 5c 26 2e 0a 2e 73 70 0a 54 string\&...sp.T
2da0: 68 69 73 20 6d 65 74 68 6f 64 20 72 75 6e 73 20 his method runs
2db0: 69 6e 20 61 6d 6f 72 74 69 7a 65 64 20 74 69 6d in amortized tim
2dc0: 65 20 4f 28 61 6c 70 68 61 28 4e 29 29 2c 20 77 e O(alpha(N)), w
2dd0: 68 65 72 65 20 4e 20 69 73 20 74 68 65 20 6e 75 here N is the nu
2de0: 6d 62 65 72 20 6f 66 0a 69 74 65 6d 73 20 69 6e mber of.items in
2df0: 20 74 68 65 20 6c 61 72 67 65 72 20 6f 66 20 74 the larger of t
2e00: 68 65 20 70 61 72 74 69 74 69 6f 6e 73 20 62 65 he partitions be
2e10: 69 6e 67 20 6d 65 72 67 65 64 5c 26 2e 20 54 68 ing merged\&. Th
2e20: 65 20 77 6f 72 73 74 20 63 61 73 65 20 74 69 6d e worst case tim
2e30: 65 0a 69 73 20 4f 28 4e 29 5c 26 2e 0a 2e 54 50 e.is O(N)\&...TP
2e40: 0a 5c 66 49 64 69 73 6a 6f 69 6e 74 73 65 74 4e .\fIdisjointsetN
2e50: 61 6d 65 5c 66 52 20 5c 66 42 66 69 6e 64 5c 66 ame\fR \fBfind\f
2e60: 52 20 5c 66 49 65 5c 66 52 0a 52 65 74 75 72 6e R \fIe\fR.Return
2e70: 73 20 61 20 6c 69 73 74 20 6f 66 20 74 68 65 20 s a list of the
2e80: 6d 65 6d 62 65 72 73 20 6f 66 20 74 68 65 20 70 members of the p
2e90: 61 72 74 69 74 69 6f 6e 20 6f 66 20 74 68 65 20 artition of the
2ea0: 64 69 73 6a 6f 69 6e 74 20 73 65 74 0a 77 68 69 disjoint set.whi
2eb0: 63 68 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 ch contains the
2ec0: 65 6c 65 6d 65 6e 74 0a 5c 66 49 65 5c 66 52 5c element.\fIe\fR\
2ed0: 26 2e 0a 2e 73 70 0a 54 68 69 73 20 6d 65 74 68 &...sp.This meth
2ee0: 6f 64 20 72 75 6e 73 20 69 6e 20 4f 28 4e 2a 61 od runs in O(N*a
2ef0: 6c 70 68 61 28 4e 29 29 20 74 69 6d 65 2c 20 77 lpha(N)) time, w
2f00: 68 65 72 65 20 4e 20 69 73 20 74 68 65 20 74 6f here N is the to
2f10: 74 61 6c 20 6e 75 6d 62 65 72 20 6f 66 0a 69 74 tal number of.it
2f20: 65 6d 73 20 69 6e 20 74 68 65 20 64 69 73 6a 6f ems in the disjo
2f30: 69 6e 74 20 73 65 74 20 61 6e 64 20 61 6c 70 68 int set and alph
2f40: 61 20 69 73 20 74 68 65 20 69 6e 76 65 72 73 65 a is the inverse
2f50: 20 41 63 6b 65 72 6d 61 6e 6e 20 66 75 6e 63 74 Ackermann funct
2f60: 69 6f 6e 2c 0a 53 65 65 20 5c 66 42 66 69 6e 64 ion,.See \fBfind
2f70: 2d 65 78 65 6d 70 6c 61 72 5c 66 52 20 66 6f 72 -exemplar\fR for
2f80: 20 61 20 66 61 73 74 65 72 20 6d 65 74 68 6f 64 a faster method
2f90: 2c 20 69 66 20 61 6c 6c 20 74 68 61 74 20 69 73 , if all that is
2fa0: 20 6e 65 65 64 65 64 0a 69 73 20 61 20 75 6e 69 needed.is a uni
2fb0: 71 75 65 20 69 64 65 6e 74 69 66 69 65 72 20 66 que identifier f
2fc0: 6f 72 20 74 68 65 20 70 61 72 74 69 74 69 6f 6e or the partition
2fd0: 2c 20 72 61 74 68 65 72 20 74 68 61 6e 20 61 6e , rather than an
2fe0: 20 65 6e 75 6d 65 72 61 74 69 6f 6e 0a 6f 66 20 enumeration.of
2ff0: 61 6c 6c 20 69 74 73 20 65 6c 65 6d 65 6e 74 73 all its elements
3000: 5c 26 2e 0a 2e 54 50 0a 5c 66 49 64 69 73 6a 6f \&...TP.\fIdisjo
3010: 69 6e 74 73 65 74 4e 61 6d 65 5c 66 52 20 5c 66 intsetName\fR \f
3020: 42 65 78 65 6d 70 6c 61 72 73 5c 66 52 0a 52 65 Bexemplars\fR.Re
3030: 74 75 72 6e 73 20 61 20 6c 69 73 74 20 63 6f 6e turns a list con
3040: 74 61 69 6e 69 6e 67 20 61 6e 20 65 78 65 6d 70 taining an exemp
3050: 6c 61 72 20 6f 66 20 65 61 63 68 20 70 61 72 74 lar of each part
3060: 69 74 69 6f 6e 20 69 6e 20 74 68 65 20 64 69 73 ition in the dis
3070: 6a 6f 69 6e 74 0a 73 65 74 5c 26 2e 20 54 68 65 joint.set\&. The
3080: 20 65 78 65 6d 70 6c 61 72 20 69 73 20 61 20 6d exemplar is a m
3090: 65 6d 62 65 72 20 6f 66 20 74 68 65 20 70 61 72 ember of the par
30a0: 74 69 74 69 6f 6e 2c 20 63 68 6f 73 65 6e 20 61 tition, chosen a
30b0: 72 62 69 74 72 61 72 69 6c 79 5c 26 2e 0a 2e 73 rbitrarily\&...s
30c0: 70 0a 54 68 69 73 20 6d 65 74 68 6f 64 20 72 75 p.This method ru
30d0: 6e 73 20 69 6e 20 4f 28 4e 2a 61 6c 70 68 61 28 ns in O(N*alpha(
30e0: 4e 29 29 20 74 69 6d 65 2c 20 77 68 65 72 65 20 N)) time, where
30f0: 4e 20 69 73 20 74 68 65 20 74 6f 74 61 6c 20 6e N is the total n
3100: 75 6d 62 65 72 20 6f 66 20 69 74 65 6d 73 0a 69 umber of items.i
3110: 6e 20 74 68 65 20 64 69 73 6a 6f 69 6e 74 20 73 n the disjoint s
3120: 65 74 20 61 6e 64 20 61 6c 70 68 61 20 69 73 20 et and alpha is
3130: 74 68 65 20 69 6e 76 65 72 73 65 20 41 63 6b 65 the inverse Acke
3140: 72 6d 61 6e 6e 20 66 75 6e 63 74 69 6f 6e 5c 26 rmann function\&
3150: 2e 0a 2e 54 50 0a 5c 66 49 64 69 73 6a 6f 69 6e ...TP.\fIdisjoin
3160: 74 73 65 74 4e 61 6d 65 5c 66 52 20 5c 66 42 66 tsetName\fR \fBf
3170: 69 6e 64 2d 65 78 65 6d 70 6c 61 72 5c 66 52 20 ind-exemplar\fR
3180: 5c 66 49 65 5c 66 52 0a 52 65 74 75 72 6e 73 20 \fIe\fR.Returns
3190: 74 68 65 20 65 78 65 6d 70 6c 61 72 20 6f 66 20 the exemplar of
31a0: 74 68 65 20 70 61 72 74 69 74 69 6f 6e 20 6f 66 the partition of
31b0: 20 74 68 65 20 64 69 73 6a 6f 69 6e 74 20 73 65 the disjoint se
31c0: 74 20 63 6f 6e 74 61 69 6e 69 6e 67 0a 74 68 65 t containing.the
31d0: 20 65 6c 65 6d 65 6e 74 20 5c 66 49 65 5c 66 52 element \fIe\fR
31e0: 5c 26 2e 20 20 54 68 72 6f 77 73 20 61 6e 20 65 \&. Throws an e
31f0: 72 72 6f 72 20 69 66 20 5c 66 49 65 5c 66 52 20 rror if \fIe\fR
3200: 69 73 20 6e 6f 74 20 66 6f 75 6e 64 20 69 6e 20 is not found in
3210: 74 68 65 0a 64 69 73 6a 6f 69 6e 74 20 73 65 74 the.disjoint set
3220: 5c 26 2e 20 20 54 68 65 20 65 78 65 6d 70 6c 61 \&. The exempla
3230: 72 20 69 73 20 61 6e 20 61 72 62 69 74 72 61 72 r is an arbitrar
3240: 69 6c 79 20 63 68 6f 73 65 6e 20 6d 65 6d 62 65 ily chosen membe
3250: 72 20 6f 66 20 74 68 65 20 70 61 72 74 69 74 69 r of the partiti
3260: 6f 6e 5c 26 2e 0a 54 68 65 20 6f 6e 6c 79 20 6f on\&..The only o
3270: 70 65 72 61 74 69 6f 6e 20 74 68 61 74 20 77 69 peration that wi
3280: 6c 6c 20 63 68 61 6e 67 65 20 74 68 65 20 65 78 ll change the ex
3290: 65 6d 70 6c 61 72 20 6f 66 20 61 6e 79 20 70 61 emplar of any pa
32a0: 72 74 69 74 69 6f 6e 20 69 73 0a 5c 66 42 6d 65 rtition is.\fBme
32b0: 72 67 65 5c 66 52 5c 26 2e 0a 2e 73 70 0a 54 68 rge\fR\&...sp.Th
32c0: 69 73 20 6d 65 74 68 6f 64 20 72 75 6e 73 20 69 is method runs i
32d0: 6e 20 4f 28 61 6c 70 68 61 28 4e 29 29 20 74 69 n O(alpha(N)) ti
32e0: 6d 65 2c 20 77 68 65 72 65 20 4e 20 69 73 20 74 me, where N is t
32f0: 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 69 74 65 he number of ite
3300: 6d 73 20 69 6e 0a 74 68 65 20 70 61 72 74 69 74 ms in.the partit
3310: 69 6f 6e 20 63 6f 6e 74 61 69 6e 69 6e 67 20 45 ion containing E
3320: 2c 20 61 6e 64 20 61 6c 70 68 61 20 69 73 20 74 , and alpha is t
3330: 68 65 20 69 6e 76 65 72 73 65 20 41 63 6b 65 72 he inverse Acker
3340: 6d 61 6e 6e 20 66 75 6e 63 74 69 6f 6e 5c 26 2e mann function\&.
3350: 0a 2e 54 50 0a 5c 66 49 64 69 73 6a 6f 69 6e 74 ..TP.\fIdisjoint
3360: 73 65 74 4e 61 6d 65 5c 66 52 20 5c 66 42 64 65 setName\fR \fBde
3370: 73 74 72 6f 79 5c 66 52 0a 44 65 73 74 72 6f 79 stroy\fR.Destroy
3380: 73 20 74 68 65 20 64 69 73 6a 6f 69 6e 74 20 73 s the disjoint s
3390: 65 74 20 6f 62 6a 65 63 74 20 61 6e 64 20 61 6c et object and al
33a0: 6c 20 61 73 73 6f 63 69 61 74 65 64 20 6d 65 6d l associated mem
33b0: 6f 72 79 5c 26 2e 0a 2e 50 50 0a 2e 53 48 20 22 ory\&...PP..SH "
33c0: 42 55 47 53 2c 20 49 44 45 41 53 2c 20 46 45 45 BUGS, IDEAS, FEE
33d0: 44 42 41 43 4b 22 0a 54 68 69 73 20 64 6f 63 75 DBACK".This docu
33e0: 6d 65 6e 74 2c 20 61 6e 64 20 74 68 65 20 70 61 ment, and the pa
33f0: 63 6b 61 67 65 20 69 74 20 64 65 73 63 72 69 62 ckage it describ
3400: 65 73 2c 20 77 69 6c 6c 20 75 6e 64 6f 75 62 74 es, will undoubt
3410: 65 64 6c 79 20 63 6f 6e 74 61 69 6e 0a 62 75 67 edly contain.bug
3420: 73 20 61 6e 64 20 6f 74 68 65 72 20 70 72 6f 62 s and other prob
3430: 6c 65 6d 73 5c 26 2e 0a 50 6c 65 61 73 65 20 72 lems\&..Please r
3440: 65 70 6f 72 74 20 73 75 63 68 20 69 6e 20 74 68 eport such in th
3450: 65 20 63 61 74 65 67 6f 72 79 20 5c 66 49 73 74 e category \fIst
3460: 72 75 63 74 20 3a 3a 20 64 69 73 6a 6f 69 6e 74 ruct :: disjoint
3470: 73 65 74 5c 66 52 20 6f 66 20 74 68 65 0a 5c 66 set\fR of the.\f
3480: 49 54 63 6c 6c 69 62 20 54 72 61 63 6b 65 72 73 ITcllib Trackers
3490: 5c 66 52 20 5b 68 74 74 70 3a 2f 2f 63 6f 72 65 \fR [http://core
34a0: 5c 26 2e 74 63 6c 5c 26 2e 74 6b 2f 74 63 6c 6c \&.tcl\&.tk/tcll
34b0: 69 62 2f 72 65 70 6f 72 74 6c 69 73 74 5d 5c 26 ib/reportlist]\&
34c0: 2e 0a 50 6c 65 61 73 65 20 61 6c 73 6f 20 72 65 ..Please also re
34d0: 70 6f 72 74 20 61 6e 79 20 69 64 65 61 73 20 66 port any ideas f
34e0: 6f 72 20 65 6e 68 61 6e 63 65 6d 65 6e 74 73 20 or enhancements
34f0: 79 6f 75 20 6d 61 79 20 68 61 76 65 20 66 6f 72 you may have for
3500: 20 65 69 74 68 65 72 0a 70 61 63 6b 61 67 65 20 either.package
3510: 61 6e 64 2f 6f 72 20 64 6f 63 75 6d 65 6e 74 61 and/or documenta
3520: 74 69 6f 6e 5c 26 2e 0a 2e 50 50 0a 57 68 65 6e tion\&...PP.When
3530: 20 70 72 6f 70 6f 73 69 6e 67 20 63 6f 64 65 20 proposing code
3540: 63 68 61 6e 67 65 73 2c 20 70 6c 65 61 73 65 20 changes, please
3550: 70 72 6f 76 69 64 65 20 5c 66 49 75 6e 69 66 69 provide \fIunifi
3560: 65 64 20 64 69 66 66 73 5c 66 52 2c 0a 69 5c 26 ed diffs\fR,.i\&
3570: 2e 65 20 74 68 65 20 6f 75 74 70 75 74 20 6f 66 .e the output of
3580: 20 5c 66 42 64 69 66 66 20 2d 75 5c 66 52 5c 26 \fBdiff -u\fR\&
3590: 2e 0a 2e 50 50 0a 4e 6f 74 65 20 66 75 72 74 68 ...PP.Note furth
35a0: 65 72 20 74 68 61 74 20 5c 66 49 61 74 74 61 63 er that \fIattac
35b0: 68 6d 65 6e 74 73 5c 66 52 20 61 72 65 20 73 74 hments\fR are st
35c0: 72 6f 6e 67 6c 79 20 70 72 65 66 65 72 72 65 64 rongly preferred
35d0: 20 6f 76 65 72 0a 69 6e 6c 69 6e 65 64 20 70 61 over.inlined pa
35e0: 74 63 68 65 73 5c 26 2e 20 41 74 74 61 63 68 6d tches\&. Attachm
35f0: 65 6e 74 73 20 63 61 6e 20 62 65 20 6d 61 64 65 ents can be made
3600: 20 62 79 20 67 6f 69 6e 67 20 74 6f 20 74 68 65 by going to the
3610: 20 5c 66 42 45 64 69 74 5c 66 52 0a 66 6f 72 6d \fBEdit\fR.form
3620: 20 6f 66 20 74 68 65 20 74 69 63 6b 65 74 20 69 of the ticket i
3630: 6d 6d 65 64 69 61 74 65 6c 79 20 61 66 74 65 72 mmediately after
3640: 20 69 74 73 20 63 72 65 61 74 69 6f 6e 2c 20 61 its creation, a
3650: 6e 64 20 74 68 65 6e 20 75 73 69 6e 67 20 74 68 nd then using th
3660: 65 0a 6c 65 66 74 2d 6d 6f 73 74 20 62 75 74 74 e.left-most butt
3670: 6f 6e 20 69 6e 20 74 68 65 20 73 65 63 6f 6e 64 on in the second
3680: 61 72 79 20 6e 61 76 69 67 61 74 69 6f 6e 20 62 ary navigation b
3690: 61 72 5c 26 2e 0a 2e 53 48 20 4b 45 59 57 4f 52 ar\&...SH KEYWOR
36a0: 44 53 0a 64 69 73 6a 6f 69 6e 74 20 73 65 74 2c DS.disjoint set,
36b0: 20 65 71 75 69 76 61 6c 65 6e 63 65 20 63 6c 61 equivalence cla
36c0: 73 73 2c 20 66 69 6e 64 2c 20 6d 65 72 67 65 20 ss, find, merge
36d0: 66 69 6e 64 2c 20 70 61 72 74 69 74 69 6f 6e 2c find, partition,
36e0: 20 70 61 72 74 69 74 69 6f 6e 65 64 20 73 65 74 partitioned set
36f0: 2c 20 75 6e 69 6f 6e 0a 2e 53 48 20 43 41 54 45 , union..SH CATE
3700: 47 4f 52 59 0a 44 61 74 61 20 73 74 72 75 63 74 GORY.Data struct
3710: 75 72 65 73 0a ures.
