<!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>
