/usr/share/doc/racket/data/union-find.html is in racket-doc 6.7-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"/><title>10 Union-Find: Sets with only Canonical Elements</title><link rel="stylesheet" type="text/css" href="../scribble.css" title="default"/><link rel="stylesheet" type="text/css" href="../racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-style.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../doc-site.css" title="default"/><script type="text/javascript" src="../scribble-common.js"></script><script type="text/javascript" src="../manual-racket.js"></script><script type="text/javascript" src="../manual-racket.js"></script><script type="text/javascript" src="../doc-site.js"></script><script type="text/javascript" src="../local-redirect/local-redirect.js"></script><script type="text/javascript" src="../local-redirect/local-user-redirect.js"></script><!--[if IE 6]><style type="text/css">.SIEHidden { overflow: hidden; }</style><![endif]--></head><body id="doc-racket-lang-org"><div class="tocset"><div class="tocview"><div class="tocviewlist tocviewlisttopspace"><div class="tocviewtitle"><table cellspacing="0" cellpadding="0"><tr><td style="width: 1em;"><a href="javascript:void(0);" title="Expand/Collapse" class="tocviewtoggle" onclick="TocviewToggle(this,"tocview_0");">▼</a></td><td></td><td><a href="index.html" class="tocviewlink" data-pltdoc="x">Data:<span class="mywbr"> </span> Data Structures</a></td></tr></table></div><div class="tocviewsublistonly" style="display: block;" id="tocview_0"><table cellspacing="0" cellpadding="0"><tr><td align="right">1 </td><td><a href="Imperative_Queues.html" class="tocviewlink" data-pltdoc="x">Imperative Queues</a></td></tr><tr><td align="right">2 </td><td><a href="gvector.html" class="tocviewlink" data-pltdoc="x">Growable Vectors</a></td></tr><tr><td align="right">3 </td><td><a href="Orders_and_Ordered_Dictionaries.html" class="tocviewlink" data-pltdoc="x">Orders and Ordered Dictionaries</a></td></tr><tr><td align="right">4 </td><td><a href="Splay_Trees.html" class="tocviewlink" data-pltdoc="x">Splay Trees</a></td></tr><tr><td align="right">5 </td><td><a href="skip-list.html" class="tocviewlink" data-pltdoc="x">Skip Lists</a></td></tr><tr><td align="right">6 </td><td><a href="interval-map.html" class="tocviewlink" data-pltdoc="x">Interval Maps</a></td></tr><tr><td align="right">7 </td><td><a href="Binary_Heaps.html" class="tocviewlink" data-pltdoc="x">Binary Heaps</a></td></tr><tr><td align="right">8 </td><td><a href="integer-set.html" class="tocviewlink" data-pltdoc="x">Integer Sets</a></td></tr><tr><td align="right">9 </td><td><a href="bit-vector.html" class="tocviewlink" data-pltdoc="x">Bit Vectors</a></td></tr><tr><td align="right">10 </td><td><a href="" class="tocviewselflink" data-pltdoc="x">Union-<wbr></wbr>Find:<span class="mywbr"> </span> Sets with only Canonical Elements</a></td></tr><tr><td align="right">11 </td><td><a href="Enumerations.html" class="tocviewlink" data-pltdoc="x">Enumerations</a></td></tr></table></div></div></div><div class="tocsub"><div class="tocsubtitle">On this page:</div><table class="tocsublist" cellspacing="0"><tr><td><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="tocsublink" data-pltdoc="x"><span class="RktSym"><span class="RktValLink">uf-<wbr></wbr>new</span></span></a></td></tr><tr><td><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set~3f%29%29" class="tocsublink" data-pltdoc="x"><span class="RktSym"><span class="RktValLink">uf-<wbr></wbr>set?</span></span></a></td></tr><tr><td><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-find%29%29" class="tocsublink" data-pltdoc="x"><span class="RktSym"><span class="RktValLink">uf-<wbr></wbr>find</span></span></a></td></tr><tr><td><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-union%21%29%29" class="tocsublink" data-pltdoc="x"><span class="RktSym"><span class="RktValLink">uf-<wbr></wbr>union!</span></span></a></td></tr><tr><td><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-same-set~3f%29%29" class="tocsublink" data-pltdoc="x"><span class="RktSym"><span class="RktValLink">uf-<wbr></wbr>same-<wbr></wbr>set?</span></span></a></td></tr><tr><td><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set-canonical%21%29%29" class="tocsublink" data-pltdoc="x"><span class="RktSym"><span class="RktValLink">uf-<wbr></wbr>set-<wbr></wbr>canonical!</span></span></a></td></tr></table></div></div><div class="maincolumn"><div class="main"><div class="versionbox"><span class="version">6.7</span></div><div class="navsettop"><span class="navleft"><form class="searchform"><input class="searchbox" style="color: #888;" type="text" value="...search manuals..." title="Enter a search string to search the manuals" onkeypress="return DoSearchKey(event, this, "6.7", "../");" onfocus="this.style.color="black"; this.style.textAlign="left"; if (this.value == "...search manuals...") this.value="";" onblur="if (this.value.match(/^ *$/)) { this.style.color="#888"; this.style.textAlign="center"; this.value="...search manuals..."; }"/></form> <a href="../index.html" title="up to the documentation top" data-pltdoc="x" onclick="return GotoPLTRoot("6.7");">top</a></span><span class="navright"> <a href="bit-vector.html" title="backward to "9 Bit Vectors"" data-pltdoc="x">← prev</a> <a href="index.html" title="up to "Data: Data Structures"" data-pltdoc="x">up</a> <a href="Enumerations.html" title="forward to "11 Enumerations"" data-pltdoc="x">next →</a></span> </div><h3 x-source-module="(lib "data/scribblings/data.scrbl")" x-source-pkg="data-doc" x-part-tag=""union-find"">10<tt> </tt><a name="(part._union-find)"></a><a name="(mod-path._data/union-find)"></a>Union-Find: Sets with only Canonical Elements</h3><p><table cellspacing="0" cellpadding="0" class="defmodule"><tr><td align="left"><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=require.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._require%2529%2529&version=6.7" class="RktStxLink Sq" data-pltdoc="x">require</a></span><span class="stt"> </span><a href="" class="RktModLink" data-pltdoc="x"><span class="RktSym">data/union-find</span></a><span class="RktPn">)</span></td><td align="right"><span class="RpackageSpec"><span class="Smaller"> package:</span> <span class="stt">data-lib</span></span></td></tr></table></p><p>The union-find algorithm and data structure provides
an API for representing sets that contain a single,
canonical element. The sets support an (imperative) union
operation (the library picks one of the canonical elements
of the original sets to be the canonical element of the union),
as well as getting and setting the canonical element.</p><p>These operations are not thread-safe.</p><p><div class="SIntrapara"><blockquote class="SVInsetFlow"><table cellspacing="0" cellpadding="0" class="boxed RBoxed"><tr><td><blockquote class="SubFlow"><div class="RBackgroundLabel SIEHidden"><div class="RBackgroundLabelInner"><p>procedure</p></div></div><p class="RForeground"><span class="RktPn">(</span><a name="(def._((lib._data/union-find..rkt)._uf-new))"></a><span title="Provided from: data/union-find | Package: data-lib"><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValDef RktValLink" data-pltdoc="x">uf-new</a></span></span><span class="hspace"> </span><span class="RktVar">c</span><span class="RktPn">)</span><span class="hspace"> </span>→<span class="hspace"> </span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set~3f%29%29" class="RktValLink" data-pltdoc="x">uf-set?</a></span></p></blockquote></td></tr><tr><td><span class="hspace"> </span><span class="RktVar">c</span><span class="hspace"> </span>:<span class="hspace"> </span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528def._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fmisc..rkt%2529._any%252Fc%2529%2529&version=6.7" class="RktValLink Sq" data-pltdoc="x">any/c</a></span></td></tr></table></blockquote></div><div class="SIntrapara">Makes a new set with the canonical element <span class="RktVar">c</span>.</div></p><p>This is a constant time operation.</p><p><div class="SIntrapara">Examples:</div><div class="SIntrapara"><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValLink" data-pltdoc="x">uf-new</a></span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">whale</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">#<uf-set: 'whale></span></p></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValLink" data-pltdoc="x">uf-new</a></span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">dwarf-lantern</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">#<uf-set: 'dwarf-lantern></span></p></td></tr></table></blockquote></div></p><p><div class="SIntrapara"><blockquote class="SVInsetFlow"><table cellspacing="0" cellpadding="0" class="boxed RBoxed"><tr><td><blockquote class="SubFlow"><div class="RBackgroundLabel SIEHidden"><div class="RBackgroundLabelInner"><p>procedure</p></div></div><p class="RForeground"><span class="RktPn">(</span><a name="(def._((lib._data/union-find..rkt)._uf-set~3f))"></a><span title="Provided from: data/union-find | Package: data-lib"><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set~3f%29%29" class="RktValDef RktValLink" data-pltdoc="x">uf-set?</a></span></span><span class="hspace"> </span><span class="RktVar">x</span><span class="RktPn">)</span><span class="hspace"> </span>→<span class="hspace"> </span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=booleans.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._boolean%7E3f%2529%2529&version=6.7" class="RktValLink Sq" data-pltdoc="x">boolean?</a></span></p></blockquote></td></tr><tr><td><span class="hspace"> </span><span class="RktVar">x</span><span class="hspace"> </span>:<span class="hspace"> </span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528def._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fmisc..rkt%2529._any%252Fc%2529%2529&version=6.7" class="RktValLink Sq" data-pltdoc="x">any/c</a></span></td></tr></table></blockquote></div><div class="SIntrapara">Returns <span class="RktVal">#t</span> if <span class="RktVar">x</span> was created with <span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValLink" data-pltdoc="x">uf-new</a></span>,
and <span class="RktVal">#f</span> otherwise.</div></p><p>This is a constant time operation.</p><p><div class="SIntrapara">Examples:</div><div class="SIntrapara"><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set~3f%29%29" class="RktValLink" data-pltdoc="x">uf-set?</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValLink" data-pltdoc="x">uf-new</a></span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">spiny-dogfish</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">#t</span></p></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set~3f%29%29" class="RktValLink" data-pltdoc="x">uf-set?</a></span><span class="hspace"> </span><span class="RktVal">"I am not a uf-set"</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">#f</span></p></td></tr></table></blockquote></div></p><p><div class="SIntrapara"><blockquote class="SVInsetFlow"><table cellspacing="0" cellpadding="0" class="boxed RBoxed"><tr><td><blockquote class="SubFlow"><div class="RBackgroundLabel SIEHidden"><div class="RBackgroundLabelInner"><p>procedure</p></div></div><p class="RForeground"><span class="RktPn">(</span><a name="(def._((lib._data/union-find..rkt)._uf-find))"></a><span title="Provided from: data/union-find | Package: data-lib"><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-find%29%29" class="RktValDef RktValLink" data-pltdoc="x">uf-find</a></span></span><span class="hspace"> </span><span class="RktVar">a</span><span class="RktPn">)</span><span class="hspace"> </span>→<span class="hspace"> </span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528def._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fmisc..rkt%2529._any%252Fc%2529%2529&version=6.7" class="RktValLink Sq" data-pltdoc="x">any/c</a></span></p></blockquote></td></tr><tr><td><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span>:<span class="hspace"> </span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set~3f%29%29" class="RktValLink" data-pltdoc="x">uf-set?</a></span></td></tr></table></blockquote></div><div class="SIntrapara">Returns the canonical element of <span class="RktVar">a</span>.</div></p><p>This is an amortized (essentially) constant time operation.</p><p><div class="SIntrapara">Example:</div><div class="SIntrapara"><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-find%29%29" class="RktValLink" data-pltdoc="x">uf-find</a></span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValLink" data-pltdoc="x">uf-new</a></span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">tasselled-wobbegong</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">'tasselled-wobbegong</span></p></td></tr></table></blockquote></div></p><p><div class="SIntrapara"><blockquote class="SVInsetFlow"><table cellspacing="0" cellpadding="0" class="boxed RBoxed"><tr><td><blockquote class="SubFlow"><div class="RBackgroundLabel SIEHidden"><div class="RBackgroundLabelInner"><p>procedure</p></div></div><p class="RForeground"><span class="RktPn">(</span><a name="(def._((lib._data/union-find..rkt)._uf-union!))"></a><span title="Provided from: data/union-find | Package: data-lib"><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-union%21%29%29" class="RktValDef RktValLink" data-pltdoc="x">uf-union!</a></span></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktVar">b</span><span class="RktPn">)</span><span class="hspace"> </span>→<span class="hspace"> </span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=void.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._void%7E3f%2529%2529&version=6.7" class="RktValLink Sq" data-pltdoc="x">void?</a></span></p></blockquote></td></tr><tr><td><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span>:<span class="hspace"> </span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set~3f%29%29" class="RktValLink" data-pltdoc="x">uf-set?</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktVar">b</span><span class="hspace"> </span>:<span class="hspace"> </span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set~3f%29%29" class="RktValLink" data-pltdoc="x">uf-set?</a></span></td></tr></table></blockquote></div><div class="SIntrapara">Imperatively unifies <span class="RktVar">a</span> and <span class="RktVar">b</span>, making
them both have the same canonical element. Either
of <span class="RktVar">a</span> or <span class="RktVar">b</span>’s canonical elements may
become the canonical element for the union.</div></p><p>This is an amortized (essentially) constant time operation.</p><p><div class="SIntrapara">Examples:</div><div class="SIntrapara"><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.7" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValLink" data-pltdoc="x">uf-new</a></span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">sand-devil</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.7" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktVar">b</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValLink" data-pltdoc="x">uf-new</a></span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">pigeye</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-union%21%29%29" class="RktValLink" data-pltdoc="x">uf-union!</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktVar">b</span><span class="RktPn">)</span></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-find%29%29" class="RktValLink" data-pltdoc="x">uf-find</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">'sand-devil</span></p></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-find%29%29" class="RktValLink" data-pltdoc="x">uf-find</a></span><span class="hspace"> </span><span class="RktVar">b</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">'sand-devil</span></p></td></tr></table></blockquote></div></p><p><div class="SIntrapara"><blockquote class="SVInsetFlow"><table cellspacing="0" cellpadding="0" class="boxed RBoxed"><tr><td><blockquote class="SubFlow"><div class="RBackgroundLabel SIEHidden"><div class="RBackgroundLabelInner"><p>procedure</p></div></div><p class="RForeground"><span class="RktPn">(</span><a name="(def._((lib._data/union-find..rkt)._uf-same-set~3f))"></a><span title="Provided from: data/union-find | Package: data-lib"><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-same-set~3f%29%29" class="RktValDef RktValLink" data-pltdoc="x">uf-same-set?</a></span></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktVar">b</span><span class="RktPn">)</span><span class="hspace"> </span>→<span class="hspace"> </span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=booleans.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._boolean%7E3f%2529%2529&version=6.7" class="RktValLink Sq" data-pltdoc="x">boolean?</a></span></p></blockquote></td></tr><tr><td><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span>:<span class="hspace"> </span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set~3f%29%29" class="RktValLink" data-pltdoc="x">uf-set?</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktVar">b</span><span class="hspace"> </span>:<span class="hspace"> </span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set~3f%29%29" class="RktValLink" data-pltdoc="x">uf-set?</a></span></td></tr></table></blockquote></div><div class="SIntrapara">Returns <span class="RktVal">#t</span> if the sets <span class="RktVar">a</span> and <span class="RktVar">b</span>
have been unioned.</div></p><p>This is an amortized (essentially) constant time operation.</p><p><div class="SIntrapara">Examples:</div><div class="SIntrapara"><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.7" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValLink" data-pltdoc="x">uf-new</a></span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">finetooth</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.7" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktVar">b</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValLink" data-pltdoc="x">uf-new</a></span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">speartooth</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-same-set~3f%29%29" class="RktValLink" data-pltdoc="x">uf-same-set?</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktVar">b</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">#f</span></p></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-union%21%29%29" class="RktValLink" data-pltdoc="x">uf-union!</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktVar">b</span><span class="RktPn">)</span></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-same-set~3f%29%29" class="RktValLink" data-pltdoc="x">uf-same-set?</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktVar">b</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">#t</span></p></td></tr></table></blockquote></div></p><p><div class="SIntrapara"><blockquote class="SVInsetFlow"><table cellspacing="0" cellpadding="0" class="boxed RBoxed"><tr><td><blockquote class="SubFlow"><div class="RBackgroundLabel SIEHidden"><div class="RBackgroundLabelInner"><p>procedure</p></div></div><p class="RForeground"><span class="RktPn">(</span><a name="(def._((lib._data/union-find..rkt)._uf-set-canonical!))"></a><span title="Provided from: data/union-find | Package: data-lib"><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set-canonical%21%29%29" class="RktValDef RktValLink" data-pltdoc="x">uf-set-canonical!</a></span></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktVar">c</span><span class="RktPn">)</span><span class="hspace"> </span>→<span class="hspace"> </span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=void.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._void%7E3f%2529%2529&version=6.7" class="RktValLink Sq" data-pltdoc="x">void?</a></span></p></blockquote></td></tr><tr><td><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span>:<span class="hspace"> </span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set~3f%29%29" class="RktValLink" data-pltdoc="x">uf-set?</a></span></td></tr><tr><td><span class="hspace"> </span><span class="RktVar">c</span><span class="hspace"> </span>:<span class="hspace"> </span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=data-structure-contracts.html%23%2528def._%2528%2528lib._racket%252Fcontract%252Fprivate%252Fmisc..rkt%2529._any%252Fc%2529%2529&version=6.7" class="RktValLink Sq" data-pltdoc="x">any/c</a></span></td></tr></table></blockquote></div><div class="SIntrapara">Changes <span class="RktVar">a</span> to have a new canonical element.</div></p><p>This is an amortized (essentially) constant time operation.</p><p><div class="SIntrapara">Examples:</div><div class="SIntrapara"><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.7" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValLink" data-pltdoc="x">uf-new</a></span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">sand-devil</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set-canonical%21%29%29" class="RktValLink" data-pltdoc="x">uf-set-canonical!</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">lemon</span><span class="RktPn">)</span></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-find%29%29" class="RktValLink" data-pltdoc="x">uf-find</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">'lemon</span></p></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="https://download.racket-lang.org/docs/6.7/html/local-redirect/index.html?doc=reference&rel=define.html%23%2528form._%2528%2528lib._racket%252Fprivate%252Fbase..rkt%2529._define%2529%2529&version=6.7" class="RktStxLink Sq" data-pltdoc="x">define</a></span><span class="hspace"> </span><span class="RktSym">b</span><span class="hspace"> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-new%29%29" class="RktValLink" data-pltdoc="x">uf-new</a></span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">pigeye</span><span class="RktPn">)</span><span class="RktPn">)</span></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-union%21%29%29" class="RktValLink" data-pltdoc="x">uf-union!</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="hspace"> </span><span class="RktSym">b</span><span class="RktPn">)</span></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-set-canonical%21%29%29" class="RktValLink" data-pltdoc="x">uf-set-canonical!</a></span><span class="hspace"> </span><span class="RktSym">b</span><span class="hspace"> </span><span class="RktVal">'</span><span class="RktVal">sicklefin-lemon</span><span class="RktPn">)</span></td></tr><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="#%28def._%28%28lib._data%2Funion-find..rkt%29._uf-find%29%29" class="RktValLink" data-pltdoc="x">uf-find</a></span><span class="hspace"> </span><span class="RktVar">a</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">'sicklefin-lemon</span></p></td></tr></table></blockquote></div></p><div class="navsetbottom"><span class="navleft"><form class="searchform"><input class="searchbox" style="color: #888;" type="text" value="...search manuals..." title="Enter a search string to search the manuals" onkeypress="return DoSearchKey(event, this, "6.7", "../");" onfocus="this.style.color="black"; this.style.textAlign="left"; if (this.value == "...search manuals...") this.value="";" onblur="if (this.value.match(/^ *$/)) { this.style.color="#888"; this.style.textAlign="center"; this.value="...search manuals..."; }"/></form> <a href="../index.html" title="up to the documentation top" data-pltdoc="x" onclick="return GotoPLTRoot("6.7");">top</a></span><span class="navright"> <a href="bit-vector.html" title="backward to "9 Bit Vectors"" data-pltdoc="x">← prev</a> <a href="index.html" title="up to "Data: Data Structures"" data-pltdoc="x">up</a> <a href="Enumerations.html" title="forward to "11 Enumerations"" data-pltdoc="x">next →</a></span> </div></div></div><div id="contextindicator"> </div></body></html>
|