<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> <link rel="stylesheet" href="style.css" type="text/css"> <meta content="text/html; charset=iso-8859-1" http-equiv="Content-Type"> <link rel="Start" href="index.html"> <link rel="previous" href="Reins.AVLSet.html"> <link rel="next" href="Reins.RBSet.html"> <link rel="Up" href="Reins.html"> <link title="Index of types" rel=Appendix href="index_types.html"> <link title="Index of exceptions" rel=Appendix href="index_exceptions.html"> <link title="Index of values" rel=Appendix href="index_values.html"> <link title="Index of modules" rel=Appendix href="index_modules.html"> <link title="Index of module types" rel=Appendix href="index_module_types.html"> <link title="Reins" rel="Chapter" href="Reins.html"><title>Reins.PatriciaSet</title> </head> <body> <div class="navbar"><a href="Reins.AVLSet.html">Previous</a> <a href="Reins.html">Up</a> <a href="Reins.RBSet.html">Next</a> </div> <center><h1>Module <a href="type_Reins.PatriciaSet.html">Reins.PatriciaSet</a></h1></center> <br> <pre><span class="keyword">module</span> PatriciaSet: <code class="code">sig</code> <a href="Reins.PatriciaSet.html">..</a> <code class="code">end</code></pre><hr width="100%"> <br> Efficient sets of integers <p> Patricia trees are balanced binary search trees whose elements are integers. These trees can be very efficient since navigating the each tree uses only specific bits of the elements value. They have O(w) worst case running time for the <code class="code">mem</code>, <code class="code">add</code>, <code class="code">remove</code> where w is the number of bits in an integer, but typically run in O(log n) time for most inputs. Because, Patricia trees never need to be re-balanced, <code class="code">union</code>, <code class="code">inter</code>, and <code class="code">diff</code> can be much faster than ordinary balanced trees, but still may take O(n+m) in the worst case.<br> <pre><span class="keyword">module</span> <a href="Reins.PatriciaSet.MonoSet.html">MonoSet</a>: <code class="type"><a href="Reins.Sets.MonoSetSig.html">Reins.Sets.MonoSetSig</a></code><code class="type"> with type elt = int and type 'a result = 'a</code></pre><div class="info"> This module implements sets with integer keys </div> <pre><span class="keyword">module</span> <a href="Reins.PatriciaSet.GenSet.html">GenSet</a>: <code class="type"><a href="Reins.Sets.GenSetSig.html">Reins.Sets.GenSetSig</a></code><code class="type"> with type elt = int and type 'a result = 'a</code></pre><div class="info"> Same as the <a href="Reins.PatriciaSet.MonoSet.html"><code class="code">Reins.PatriciaSet.MonoSet</code></a> module, except it also provides the <code class="code">gen</code> function. </div> </body></html>