uLUt documentation converted to XML DocBook variant.

[ulut.git] / doc / srcdoc / gavl.tmpl

diff --git a/doc/srcdoc/gavl.tmpl b/doc/srcdoc/gavl.tmpl
index 17eceb886d9fc022cccad771e23c594da6934c08..8774fff84d8094558fcdb4d308ca211057d7a8e9 100644 (file)
--- a/doc/srcdoc/gavl.tmpl
+++ b/doc/srcdoc/gavl.tmpl
@@ -1,4 +1,16 @@
-<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook V4.1//EN"[]>
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.5//EN"
+                    "http://www.oasis-open.org/docbook/xml/4.5/docbookx.dtd"
+[
+<!ENTITY % MATHML.prefixed "INCLUDE">
+<!ENTITY % MATHML.prefix "mml">
+<!ENTITY % equation.content "(alt?, (graphic+|mediaobject+|mml:math))">
+<!ENTITY % inlineequation.content 
+                "(alt?, (inlinegraphic+|inlinemediaobject+|mml:math))">
+<!ENTITY % mathml PUBLIC "-//W3C//DTD MathML 2.0//EN"
+        "http://www.w3.org/Math/DTD/mathml2/mathml2.dtd">
+%mathml;
+]>
 
 <book id="GAVLdoc">
  <bookinfo>
@@ -644,7 +656,7 @@ typedef struct cust2_item {
 } cust2_item_t;
 
 typedef struct cust2_root {
-  gavl_node_t *my_root;
+  gavl_cust_root_field_t my_root;
   /* more user root/tree data ... */
 } cust2_root_t;
 
@@ -653,7 +665,7 @@ int cust_cmp_fnc(cust_key_t *a, cust_key_t *b);</programlisting>
    <para>
     As can be seen from above code fragment, the key field with user declared
     type (<type>cust_key_t</type>) and internal node structure are required
-    for items. The only one field with type <type>gavl_node_t</type>* is required
+    for items. The only one field with type <type>gavl_cust_root_field_t</type> is required
     for the custom tree root  structure.
    </para>
    <para>
@@ -757,7 +769,7 @@ cust2_root_t cust2_tree;</programlisting>
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation>. The height of subtree starting at 
@@ -766,7 +778,7 @@ cust2_root_t cust2_tree;</programlisting>
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> is labeled as 
@@ -775,7 +787,7 @@ cust2_root_t cust2_tree;</programlisting>
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation>. Height difference (balance factor) for node 
@@ -784,7 +796,7 @@ cust2_root_t cust2_tree;</programlisting>
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> is labeled as 
@@ -793,7 +805,7 @@ cust2_root_t cust2_tree;</programlisting>
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation>.
@@ -805,19 +817,19 @@ cust2_root_t cust2_tree;</programlisting>
     <title>Tree balancing case 1</title>
     <mediaobject>
       <imageobject>
-        <imagedata align="center" fileref="fig/gavl_t11.pdf" format="EPS" scale="75" >
+        <imagedata align="center" fileref="fig/gavl_t11.pdf" format="EPS" scale="75" />
       </imageobject>
       <imageobject>
-        <imagedata align="center" fileref="fig/gavl_t11.gif" format="GIF" scale="75" >
+        <imagedata align="center" fileref="fig/gavl_t11.gif" format="GIF" scale="75" />
       </imageobject>
       <caption><para>Before operation</para></caption>
     </mediaobject>
     <mediaobject>
       <imageobject>
-        <imagedata align="center" fileref="fig/gavl_t12.pdf" format="EPS" scale="75" >
+        <imagedata align="center" fileref="fig/gavl_t12.pdf" format="EPS" scale="75" />
       </imageobject>
       <imageobject>
-        <imagedata align="center" fileref="fig/gavl_t12.gif" format="GIF" scale="75" >
+        <imagedata align="center" fileref="fig/gavl_t12.gif" format="GIF" scale="75" />
       </imageobject>
       <caption><para>After operation</para></caption>
     </mediaobject>
@@ -833,7 +845,7 @@ cust2_root_t cust2_tree;</programlisting>
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation> The height of subtree 
@@ -842,7 +854,7 @@ cust2_root_t cust2_tree;</programlisting>
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> is defined by highest branch, which is branch grovinggrowing from node 
@@ -851,7 +863,7 @@ cust2_root_t cust2_tree;</programlisting>
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation>. This leads to next equations.
@@ -866,7 +878,7 @@ b &#38; = &#38; a+1-\Delta s
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>The height of branches 
@@ -875,7 +887,7 @@ b &#38; = &#38; a+1-\Delta s
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> and 
@@ -884,7 +896,7 @@ b &#38; = &#38; a+1-\Delta s
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> is marked as 
@@ -893,7 +905,7 @@ b &#38; = &#38; a+1-\Delta s
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> and 
@@ -902,7 +914,7 @@ b &#38; = &#38; a+1-\Delta s
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> after balancing.
@@ -915,7 +927,7 @@ b &#38; = &#38; a+1-\Delta s
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>
@@ -930,7 +942,7 @@ s1 &#38; = &#38; a+1-\min (\Delta n,\Delta s-1)
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>
@@ -949,7 +961,7 @@ s1 &#38; = &#38; a+1-\min (\Delta n,\Delta s-1)
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>Because balancing in case 1 does not guarantee that new tree has lower height than original tree, it is necessary to compute tree height change (tree height lowering).
@@ -969,7 +981,7 @@ s-n1 &#38; = &#38; \left\langle \begin{array}{cc}
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation></para></sect2>
@@ -979,19 +991,19 @@ s-n1 &#38; = &#38; \left\langle \begin{array}{cc}
     <title>Tree balancing case 2</title>
     <mediaobject>
       <imageobject>
-        <imagedata align="center" fileref="fig/gavl_t21.pdf" format="EPS" scale="75" >
+        <imagedata align="center" fileref="fig/gavl_t21.pdf" format="EPS" scale="75" />
       </imageobject>
       <imageobject>
-        <imagedata align="center" fileref="fig/gavl_t21.gif" format="GIF" scale="75" >
+        <imagedata align="center" fileref="fig/gavl_t21.gif" format="GIF" scale="75" />
       </imageobject>
       <caption><para>Before operation</para></caption>
     </mediaobject>
     <mediaobject>
       <imageobject>
-        <imagedata align="center" fileref="fig/gavl_t22.pdf" format="EPS" scale="75" >
+        <imagedata align="center" fileref="fig/gavl_t22.pdf" format="EPS" scale="75" />
       </imageobject>
       <imageobject>
-        <imagedata align="center" fileref="fig/gavl_t22.gif" format="GIF" scale="75" >
+        <imagedata align="center" fileref="fig/gavl_t22.gif" format="GIF" scale="75" />
       </imageobject>
       <caption><para>After operation</para></caption>
     </mediaobject>
@@ -1003,7 +1015,7 @@ s-n1 &#38; = &#38; \left\langle \begin{array}{cc}
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation>
@@ -1012,7 +1024,7 @@ s-n1 &#38; = &#38; \left\langle \begin{array}{cc}
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> or 
@@ -1021,7 +1033,7 @@ s-n1 &#38; = &#38; \left\langle \begin{array}{cc}
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation>
@@ -1030,7 +1042,7 @@ s-n1 &#38; = &#38; \left\langle \begin{array}{cc}
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation>.
@@ -1043,7 +1055,7 @@ s-n1 &#38; = &#38; \left\langle \begin{array}{cc}
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>
@@ -1058,7 +1070,7 @@ a &#38; = &#38; p+\Delta n
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>
@@ -1071,7 +1083,7 @@ a &#38; = &#38; p+\Delta n
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>When 
@@ -1080,7 +1092,7 @@ a &#38; = &#38; p+\Delta n
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> then the height differences 
@@ -1089,7 +1101,7 @@ a &#38; = &#38; p+\Delta n
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation>, 
@@ -1098,7 +1110,7 @@ a &#38; = &#38; p+\Delta n
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> and 
@@ -1107,7 +1119,7 @@ a &#38; = &#38; p+\Delta n
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> for nodes 
@@ -1116,7 +1128,7 @@ a &#38; = &#38; p+\Delta n
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation>, 
@@ -1125,7 +1137,7 @@ a &#38; = &#38; p+\Delta n
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> and 
@@ -1134,7 +1146,7 @@ a &#38; = &#38; p+\Delta n
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> of the balanced tree can be computed from next equations.
@@ -1155,7 +1167,7 @@ s1 &#38; = &#38; \max (c,d)+1=\max (b-\Delta p,b+2-\Delta s)+1\\
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>When 
@@ -1164,7 +1176,7 @@ s1 &#38; = &#38; \max (c,d)+1=\max (b-\Delta p,b+2-\Delta s)+1\\
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> then the height differences 
@@ -1173,7 +1185,7 @@ s1 &#38; = &#38; \max (c,d)+1=\max (b-\Delta p,b+2-\Delta s)+1\\
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation>, 
@@ -1182,7 +1194,7 @@ s1 &#38; = &#38; \max (c,d)+1=\max (b-\Delta p,b+2-\Delta s)+1\\
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> and 
@@ -1191,7 +1203,7 @@ s1 &#38; = &#38; \max (c,d)+1=\max (b-\Delta p,b+2-\Delta s)+1\\
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> for nodes 
@@ -1200,7 +1212,7 @@ s1 &#38; = &#38; \max (c,d)+1=\max (b-\Delta p,b+2-\Delta s)+1\\
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation>, 
@@ -1209,7 +1221,7 @@ s1 &#38; = &#38; \max (c,d)+1=\max (b-\Delta p,b+2-\Delta s)+1\\
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> and 
@@ -1218,7 +1230,7 @@ s1 &#38; = &#38; \max (c,d)+1=\max (b-\Delta p,b+2-\Delta s)+1\\
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> of the balanced tree can be computed from next equations.
@@ -1239,7 +1251,7 @@ n1 &#38; = &#38; \max (a,b)+1=\max (c+1+\Delta n,c+\Delta p)+1\\
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation></para></sect2>
@@ -1250,7 +1262,7 @@ n1 &#38; = &#38; \max (a,b)+1=\max (c+1+\Delta n,c+\Delta p)+1\\
     </alt>
     <inlinemediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </inlinemediaobject>
    </inlineequation> can be computed recursively.
@@ -1261,7 +1273,7 @@ T(h)=T(h-1)+T(h-2)+1,\, T(0)=0,\, T(1)=1\]
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986</para><para>
@@ -1272,7 +1284,7 @@ T(h)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{(h+2)}-1\]
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>
@@ -1283,7 +1295,7 @@ T(h)=\frac{1}{\sqrt{5}}\, 2^{(h+2)\, log_{2}\left(\frac{1+\sqrt{5}}{2}\right)}-1
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>
@@ -1294,7 +1306,7 @@ h=\left(log_{2}(T+1)-log_{2}\left(\frac{1}{\sqrt{5}}\right)\right)log_{2}^{-1}\l
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation>
@@ -1305,7 +1317,7 @@ log_{2}^{-1}\left(\frac{1+\sqrt{5}}{2}\right)=1.44042\]
     </alt>
     <mediaobject>
      <imageobject>
-      <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+      <imagedata fileref="img/gavl_eq1.gif" format="GIF"/>
      </imageobject>
     </mediaobject>
    </equation></para><para>An AVL tree with n nodes has height between log2 (n + 1) and 1.44 * log2 (n + 2) - 0.328. An AVL tree with height h has between pow (2, (h + .328) / 1.44) - 1 and pow (2, h) - 1 nodes.</para><para>A red-black tree with n nodes has height at least log2 (n + 1) but no more than 2 * log2 (n + 1). A red-black tree with height h has at least pow (2, h / 2) - 1 nodes but no more than pow (2, h) - 1. </para>