Changeset 9030 in project


Ignore:
Timestamp:
02/26/08 15:54:26 (12 years ago)
Author:
Kon Lovett
Message:

Canon dir struct

Location:
release/3/binary-tree
Files:
2 added
2 copied
6 moved

Legend:

Unmodified
Added
Removed
  • release/3/binary-tree/trunk/binary-tree.html

    r9024 r9030  
    156156<h3>Author</h3><a href="mailto:klovett@pacbell.net">Kon Lovett</a></div>
    157157<div class="section">
     158<h3>Requires</h3>
     159<ul>
     160<li><a href="misc-extn.html">misc-extn</a></li></ul></div>
     161<div class="section">
     162<h3>Download</h3><a href="binary-tree.egg">binary-tree.egg</a></div>
     163<div class="section">
     164<h3>Documentation</h3>
     165<div class="subsection">
     166<h4>AVL Tree</h4>
     167<div class="section">
     168<h3>Usage</h3>(require-extension avltree)</div>
     169<p>The procedures without a trailing '!' are pure. Those with a '!' are impure.</p>
     170<dt class="definition"><strong>procedure:</strong> (make-avltree LESS-THAN)</dt>
     171<dd>
     172<p>Returns a new avltree object.</p></dd>
     173<dt class="definition"><strong>procedure:</strong> (alist-&gt;avltree ALIST LESS-THAN [DUPLICATE (ORIGINAL NEW -&gt; OBJECT)])</dt>
     174<dd>
     175<p>Returns a new avltree object built from the assocication list <tt>ALIST</tt>. The <tt>DUPLICATE</tt> procedure is invoked to determine the value for a duplicate item.</p></dd>
     176<dt class="definition"><strong>procedure:</strong> (avltree? OBJECT)</dt>
     177<dd>
     178<p>Is the <tt>OBJECT</tt> an avltree?</p></dd>
     179<dt class="definition"><strong>procedure:</strong> (avltree-empty? AVL-TREE)</dt>
     180<dd>
     181<p>Is the <tt>AVL-TREE</tt> empty?</p></dd>
     182<dt class="definition"><strong>procedure:</strong> (avltree-less-than-function AVL-TREE)</dt>
     183<dd>
     184<p>Returns the less-than procedure for <tt>AVL-TREE</tt>.</p></dd>
     185<dt class="definition"><strong>procedure:</strong> (avltree-size AVL-TREE)</dt>
     186<dd>
     187<p>Returns the number of elements for <tt>AVL-TREE</tt>.</p></dd>
     188<dt class="definition"><strong>procedure:</strong> (avltree-keys AVL-TREE)</dt>
     189<dd>
     190<p>Returns the keys for <tt>AVL-TREE</tt> as a list.</p></dd>
     191<dt class="definition"><strong>procedure:</strong> (avltree-values AVL-TREE)</dt>
     192<dd>
     193<p>Returns the values for <tt>AVL-TREE</tt> as a list.</p></dd>
     194<dt class="definition"><strong>procedure:</strong> (avltree-&gt;alist AVL-TREE)</dt>
     195<dd>
     196<p>Returns the keys &amp; values for <tt>AVL-TREE</tt> as an association list.</p></dd>
     197<dt class="definition"><strong>procedure:</strong> (avltree-ref AVL-TREE KEY [NOT-FOUND (-&gt; OBJECT)])</dt>
     198<dd>
     199<p>Returns the value for <tt>KEY</tt> in <tt>AVL-TREE</tt>. When the key is not found the <tt>NOT-FOUND</tt> procedure is invoked. The default will signal an error.</p></dd>
     200<dt class="definition"><strong>procedure:</strong> (avltree-ref/default AVL-TREE KEY DEFAULT)</dt>
     201<dd>
     202<p>Returns the value for <tt>KEY</tt> in <tt>AVL-TREE</tt>. When the key is not found the <tt>DEFAULT</tt> is returned.</p></dd>
     203<dt class="definition"><strong>procedure:</strong> (avltree-exists? AVL-TREE KEY)</dt>
     204<dd>
     205<p>Does the <tt>KEY</tt> exist in <tt>AVL-TREE</tt>?</p></dd>
     206<dt class="definition"><strong>procedure:</strong> (avltree-update! AVL-TREE KEY FOUND [NOT-FOUND (-&gt; OBJECT)])</dt>
     207<dd>
     208<p>Updates the entry for <tt>KEY</tt> in <tt>AVL-TREE</tt>. Invokes the <tt>FOUND</tt> procedure to determine the value to use for an existing entry, and the <tt>NOT-FOUND</tt> procedure for a new entry. The default will signal an error.</p></dd>
     209<dt class="definition"><strong>procedure:</strong> (avltree-update!/default AVL-TREE KEY FOUND DEFAULT)</dt>
     210<dd>
     211<p>Updates the entry for <tt>KEY</tt> in <tt>AVL-TREE</tt>. Invokes the <tt>FOUND</tt> procedure to determine the value to use for an existing entry, and uses the <tt>DEFAULT</tt> value for a new entry.</p></dd>
     212<dt class="definition"><strong>procedure:</strong> (avltree-set! AVL-TREE KEY VALUE [FOUND (ORIGINAL -&gt; OBJECT)])</dt>
     213<dd>
     214<p>Adds the entry for <tt>KEY VALUE</tt> to <tt>AVL-TREE</tt>. Invokes the <tt>FOUND</tt> procedure to determine the value to use for an existing entry. The default uses the new value.</p></dd>
     215<dt class="definition"><strong>procedure:</strong> (avltree-delete! AVL-TREE KEY [FOUND (ORIGINAL -&gt; OBJECT)] [NOT-FOUND (-&gt; OBJECT)])</dt>
     216<dd>
     217<p>Deletes the entry for <tt>KEY</tt> from <tt>AVL-TREE</tt>.</p>
     218<p>Entries are flagged as deleted, not actually removed.</p></dd>
     219<dt class="definition"><strong>procedure:</strong> (avltree-vacuum! AVL-TREE)</dt>
     220<dd>
     221<p>Removes deleted entries from <tt>AVL-TREE</tt>.</p></dd>
     222<dt class="definition"><strong>procedure:</strong> (avltree-merge! AVL-TREE-1 AVL-TREE-2)</dt>
     223<dd>
     224<p>Merges the entries from <tt>AVL-TREE-2</tt> into <tt>AVL-TREE-1</tt>, using overwrite semantics.</p></dd>
     225<dt class="definition"><strong>procedure:</strong> (avltree-update AVL-TREE KEY FOUND [NOT-FOUND (-&gt; OBJECT)])</dt>
     226<dd>
     227<p>Returns a new avltree object with the entry for <tt>KEY</tt> updated  in a copy of <tt>AVL-TREE</tt>. Invokes the <tt>FOUND</tt> procedure to determine the value to use for an existing entry, and the <tt>NOT-FOUND</tt> procedure for a new entry. The default will signal an error.</p></dd>
     228<dt class="definition"><strong>procedure:</strong> (avltree-update/default AVL-TREE KEY FOUND DEFAULT)</dt>
     229<dd>
     230<p>Returns a new avltree object with the entry for <tt>KEY</tt> updated  in a copy of <tt>AVL-TREE</tt>. Invokes the <tt>FOUND</tt> procedure to determine the value to use for an existing entry, and uses the <tt>DEFAULT</tt> value for a new entry.</p></dd>
     231<dt class="definition"><strong>procedure:</strong> (avltree-set AVL-TREE KEY VALUE [FOUND (ORIGINAL -&gt; OBJECT)])</dt>
     232<dd>
     233<p>Returns a new avltree object with the entry for <tt>KEY VALUE</tt> added to  a copy of <tt>AVL-TREE</tt>. Invokes the <tt>FOUND</tt> procedure to determine the value to use for an existing entry. The default uses the new value.</p></dd>
     234<dt class="definition"><strong>procedure:</strong> (avltree-delete AVL-TREE KEY [FOUND (ORIGINAL -&gt; OBJECT)] [NOT-FOUND (-&gt; OBJECT)])</dt>
     235<dd>
     236<p>Returns a new avltree object with the entry for <tt>KEY</tt> deleted from  a copy of <tt>AVL-TREE</tt>.</p>
     237<p>Entries are flagged as deleted, not actually removed.</p></dd>
     238<dt class="definition"><strong>procedure:</strong> (avltree-copy AVL-TREE)</dt>
     239<dd>
     240<p>Returns a new avltree object from <tt>AVL-TREE</tt>, without deleted entries.</p></dd>
     241<dt class="definition"><strong>procedure:</strong> (avltree-merge AVL-TREE-1 AVL-TREE-2)</dt>
     242<dd>
     243<p>Returns a new avltree object from a copy of <tt>AVL-TREE-1</tt>, merged with the entries from <tt>AVL-TREE-2</tt>, using overwrite semantics.</p></dd>
     244<dt class="definition"><strong>procedure:</strong> (avltree-walk AVL-TREE PROC)</dt>
     245<dd>
     246<p>Invoke the procedure <tt>PROC</tt>, '(KEY VALUE -&gt; UNDEFINED)', for every key &amp; value in <tt>AVL-TREE</tt>. Return value is undefined.</p></dd>
     247<dt class="definition"><strong>procedure:</strong> (avltree-fold AVL-TREE FUNC INITIAL-VALUE)</dt>
     248<dd>
     249<p>Invoke the procedure <tt>FUNC</tt>, '(KEY VALUE ACCUM -&gt; OBJECT)', for every key &amp; value in <tt>AVL-TREE</tt>. Returns the last result of the procedure.</p></dd>
     250<dt class="definition"><strong>procedure:</strong> (avltree-enfold AVL-TREE FUNC INITIAL-VALUE)</dt>
     251<dd>
     252<p>Invokes the procedure <tt>FUNC</tt>, '(KEY VALUE ACCUM (OBJECT -&gt; OBJECT) -&gt; OBJECT)', for every key &amp; value in <tt>AVL-TREE</tt>. The fourth argument to <tt>FUNC</tt>, termed <tt>NEXT</tt>, must be called to continue the fold operation. Usually the function will return with <code>(NEXT NEW-ACCUM)</code>.</p></dd>
     253<dt class="definition"><strong>procedure:</strong> (avltree-bifold AVL-TREE BEFORE AFTER INITIAL-VALUE)</dt>
     254<dd>
     255<p>Invoke the procedure <tt>BEFORE</tt>, '(KEY VALUE ACCUM -&gt; OBJECT)', for every key &amp; value in <tt>AVL-TREE</tt> on the way &quot;down&quot;, and the procedure <tt>AFTER</tt>, '(KEY VALUE ACCUM -&gt; OBJECT)', on the way &quot;up&quot;. Returns the last result of the after procedure.</p></dd></div></div>
     256<div class="section">
    158257<h3>Version</h3>
    159258<ul>
    160259<li>1.0 Initial release</li></ul></div>
    161 <div class="section">
    162 <h3>Requires</h3>
    163 <ul>
    164 <li><a href="misc-extn.html">misc-extn</a></li></ul></div>
    165 <div class="section">
    166 <h3>Download</h3><a href="binary-tree.egg">binary-tree.egg</a></div>
    167 <div class="section">
    168 <h3>Documentation</h3>
    169 <div class="subsection">
    170 <h4>AVL Tree</h4>
    171 <div class="section">
    172 <h3>Usage</h3>(require-extension avltree)</div>
    173 <p>The procedures without a trailing '!' are pure. Those with a '!' are impure.</p>
    174 <dt class="definition"><strong>procedure:</strong> (make-avltree LESS-THAN-PROCEDURE)</dt>
    175 <dd>
    176 <p>Returns a new avltree object.</p></dd>
    177 <dt class="definition"><strong>procedure:</strong> (alist-&gt;avltree ALIST LESS-THAN-PROCEDURE [IF-DUPLICATE (-&gt; ORIGINAL NEW OBJECT)])</dt>
    178 <dd>
    179 <p>Returns a new avltree object built from the assocication list <tt>ALIST</tt>. The <tt>IF-DUPLICATE</tt> procedure is invoked to determine the value for a duplicate item.</p></dd>
    180 <dt class="definition"><strong>procedure:</strong> (avltree? OBJECT)</dt>
    181 <dd>
    182 <p>Is the <tt>OBJECT</tt> an avltree?</p></dd>
    183 <dt class="definition"><strong>procedure:</strong> (avltree-empty? AVL-TREE)</dt>
    184 <dd>
    185 <p>Is the <tt>AVL-TREE</tt> empty?</p></dd>
    186 <dt class="definition"><strong>procedure:</strong> (avltree-less-than-function AVL-TREE)</dt>
    187 <dd>
    188 <p>Returns the less-than procedure for <tt>AVL-TREE</tt>.</p></dd>
    189 <dt class="definition"><strong>procedure:</strong> (avltree-size AVL-TREE)</dt>
    190 <dd>
    191 <p>Returns the number of elements for <tt>AVL-TREE</tt>.</p></dd>
    192 <dt class="definition"><strong>procedure:</strong> (avltree-keys AVL-TREE)</dt>
    193 <dd>
    194 <p>Returns the keys for <tt>AVL-TREE</tt> as a list.</p></dd>
    195 <dt class="definition"><strong>procedure:</strong> (avltree-values AVL-TREE)</dt>
    196 <dd>
    197 <p>Returns the values for <tt>AVL-TREE</tt> as a list.</p></dd>
    198 <dt class="definition"><strong>procedure:</strong> (avltree-&gt;alist AVL-TREE)</dt>
    199 <dd>
    200 <p>Returns the keys &amp; values for <tt>AVL-TREE</tt> as an association list.</p></dd>
    201 <dt class="definition"><strong>procedure:</strong> (avltree-ref AVL-TREE KEY [IF-NOT-FOUND (-&gt; OBJECT)])</dt>
    202 <dd>
    203 <p>Returns the value for <tt>KEY</tt> in <tt>AVL-TREE</tt>. When the key is not found the <tt>IF-NOT-FOUND</tt> procedure is invoked. The default will signal an error.</p></dd>
    204 <dt class="definition"><strong>procedure:</strong> (avltree-ref/default AVL-TREE KEY DEFAULT)</dt>
    205 <dd>
    206 <p>Returns the value for <tt>KEY</tt> in <tt>AVL-TREE</tt>. When the key is not found the <tt>DEFAULT</tt> is returned.</p></dd>
    207 <dt class="definition"><strong>procedure:</strong> (avltree-exists? AVL-TREE KEY)</dt>
    208 <dd>
    209 <p>Does the <tt>KEY</tt> exist in <tt>AVL-TREE</tt>?</p></dd>
    210 <dt class="definition"><strong>procedure:</strong> (avltree-update! AVL-TREE KEY IF-FOUND [IF-NOT-FOUND (-&gt; OBJECT)])</dt>
    211 <dd>
    212 <p>Updates the entry for <tt>KEY</tt> in <tt>AVL-TREE</tt>. Invokes the <tt>IF-FOUND</tt> procedure to determine the value to use for an existing entry, and the <tt>IF-NOT-FOUND</tt> procedure for a new entry. The default will signal an error.</p></dd>
    213 <dt class="definition"><strong>procedure:</strong> (avltree-update!/default AVL-TREE KEY IF-FOUND DEFAULT)</dt>
    214 <dd>
    215 <p>Updates the entry for <tt>KEY</tt> in <tt>AVL-TREE</tt>. Invokes the <tt>IF-FOUND</tt> procedure to determine the value to use for an existing entry, and uses the <tt>DEFAULT</tt> value for a new entry.</p></dd>
    216 <dt class="definition"><strong>procedure:</strong> (avltree-set! AVL-TREE KEY VALUE [IF-FOUND (-&gt; ORIGINAL OBJECT)])</dt>
    217 <dd>
    218 <p>Adds the entry for <tt>KEY VALUE</tt> to <tt>AVL-TREE</tt>. Invokes the <tt>IF-FOUND</tt> procedure to determine the value to use for an existing entry. The default uses the new value.</p></dd>
    219 <dt class="definition"><strong>procedure:</strong> (avltree-delete! AVL-TREE KEY [IF-FOUND (-&gt; ORIGINAL OBJECT)] [IF-NOT-FOUND (-&gt; OBJECT)])</dt>
    220 <dd>
    221 <p>Deletes the entry for <tt>KEY</tt> from <tt>AVL-TREE</tt>.</p>
    222 <p>Entries are flagged as deleted, not actually removed.</p></dd>
    223 <dt class="definition"><strong>procedure:</strong> (avltree-vacuum! AVL-TREE)</dt>
    224 <dd>
    225 <p>Removes deleted entries from <tt>AVL-TREE</tt>.</p></dd>
    226 <dt class="definition"><strong>procedure:</strong> (avltree-merge! AVL-TREE-1 AVL-TREE-2)</dt>
    227 <dd>
    228 <p>Merges the entries from <tt>AVL-TREE-2</tt> into <tt>AVL-TREE-1</tt>, using overwrite semantics.</p></dd>
    229 <dt class="definition"><strong>procedure:</strong> (avltree-update AVL-TREE KEY IF-FOUND [IF-NOT-FOUND (-&gt; OBJECT)])</dt>
    230 <dd>
    231 <p>Returns a new avltree object with the entry for <tt>KEY</tt> updated  in a copy of <tt>AVL-TREE</tt>. Invokes the <tt>IF-FOUND</tt> procedure to determine the value to use for an existing entry, and the <tt>IF-NOT-FOUND</tt> procedure for a new entry. The default will signal an error.</p></dd>
    232 <dt class="definition"><strong>procedure:</strong> (avltree-update/default AVL-TREE KEY IF-FOUND DEFAULT)</dt>
    233 <dd>
    234 <p>Returns a new avltree object with the entry for <tt>KEY</tt> updated  in a copy of <tt>AVL-TREE</tt>. Invokes the <tt>IF-FOUND</tt> procedure to determine the value to use for an existing entry, and uses the <tt>DEFAULT</tt> value for a new entry.</p></dd>
    235 <dt class="definition"><strong>procedure:</strong> (avltree-set AVL-TREE KEY VALUE [IF-FOUND (-&gt; ORIGINAL OBJECT)])</dt>
    236 <dd>
    237 <p>Returns a new avltree object with the entry for <tt>KEY VALUE</tt> added to  a copy of <tt>AVL-TREE</tt>. Invokes the <tt>IF-FOUND</tt> procedure to determine the value to use for an existing entry. The default uses the new value.</p></dd>
    238 <dt class="definition"><strong>procedure:</strong> (avltree-delete AVL-TREE KEY [IF-FOUND (-&gt; ORIGINAL OBJECT)] [IF-NOT-FOUND (-&gt; OBJECT)])</dt>
    239 <dd>
    240 <p>Returns a new avltree object with the entry for <tt>KEY</tt> deleted from  a copy of <tt>AVL-TREE</tt>.</p>
    241 <p>Entries are flagged as deleted, not actually removed.</p></dd>
    242 <dt class="definition"><strong>procedure:</strong> (avltree-copy AVL-TREE)</dt>
    243 <dd>
    244 <p>Returns a new avltree object from <tt>AVL-TREE</tt>, without deleted entries.</p></dd>
    245 <dt class="definition"><strong>procedure:</strong> (avltree-merge AVL-TREE-1 AVL-TREE-2)</dt>
    246 <dd>
    247 <p>Returns a new avltree object from a copy of <tt>AVL-TREE-1</tt>, merged with the entries from <tt>AVL-TREE-2</tt>, using overwrite semantics.</p></dd>
    248 <dt class="definition"><strong>procedure:</strong> (avltree-walk AVL-TREE PROC)</dt>
    249 <dd>
    250 <p>Invoke the procedure <tt>PROC</tt>, '(-&gt; KEY VALUE UNDEFINED)', for every key &amp; value in <tt>AVL-TREE</tt>. Return value is undefined.</p></dd>
    251 <dt class="definition"><strong>procedure:</strong> (avltree-fold AVL-TREE FUNC INITIAL-VALUE)</dt>
    252 <dd>
    253 <p>Invoke the procedure <tt>FUNC</tt>, '(-&gt; KEY VALUE ACCUM OBJECT)', for every key &amp; value in <tt>AVL-TREE</tt>. Returns the last result of the procedure.</p></dd>
    254 <dt class="definition"><strong>procedure:</strong> (avltree-enfold AVL-TREE FUNC INITIAL-VALUE)</dt>
    255 <dd>
    256 <p>Invokes the procedure <tt>FUNC</tt>, '(-&gt; KEY VALUE ACCUM (-&gt; OBJECT OBJECT) OBJECT)', for every key &amp; value in <tt>AVL-TREE</tt>. The fourth argument to <tt>FUNC</tt>, termed <tt>NEXT</tt>, must be called to continue the fold operation. Usually the function will return with <code>(NEXT NEW-ACCUM)</code>.</p></dd>
    257 <dt class="definition"><strong>procedure:</strong> (avltree-bifold AVL-TREE BEFORE AFTER INITIAL-VALUE)</dt>
    258 <dd>
    259 <p>Invoke the procedure <tt>BEFORE</tt>, '(-&gt; KEY VALUE ACCUM OBJECT)', for every key &amp; value in <tt>AVL-TREE</tt> on the way &quot;down&quot;, and the procedure <tt>AFTER</tt>, '(-&gt; KEY VALUE ACCUM OBJECT)', on the way &quot;up&quot;. Returns the last result of the after procedure.</p></dd></div></div>
    260260<div class="section">
    261261<h3>License</h3>
Note: See TracChangeset for help on using the changeset viewer.