<!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.RBSet.html"> <link rel="next" href="Reins.Version.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.SplaySet</title> </head> <body> <div class="navbar"><a href="Reins.RBSet.html">Previous</a> <a href="Reins.html">Up</a> <a href="Reins.Version.html">Next</a> </div> <center><h1>Module <a href="type_Reins.SplaySet.html">Reins.SplaySet</a></h1></center> <br> <pre><span class="keyword">module</span> SplaySet: <code class="code">sig</code> <a href="Reins.SplaySet.html">..</a> <code class="code">end</code></pre><hr width="100%"> <br> Sets with excellent non-uniform access performance <p> Splay trees are binary search trees that are balanced based on recently accessed elements. They provide amortized O(log n) performance for tree operations (<code class="code">mem</code>, <code class="code">add</code>, <code class="code">remove</code>), and O(n) amortized time for set operations. Splay trees do not maintain any invariant information and are therefore very memory efficient. To achieve their amortized bounds, splay trees re-balance themselves on every tree access (e.g., <code class="code">mem</code>). Re-balancing always leaves the most recently accessed element at the root of the tree. Therefore repeated access to recent elements can be very efficient. However, this also means that tree operations may take O(n) for degenerate cases.<br> <pre><span class="keyword">module</span> <a href="Reins.SplaySet.PolySet.html">PolySet</a>: <code class="type"><a href="Reins.Sets.PolySetSig.html">Reins.Sets.PolySetSig</a></code><code class="type"> with type ('a,'b) result = 'a * 'b PolySet.t</code></pre><div class="info"> This module provides an implementation of Splay trees with a polymorphic element type. </div> <pre><span class="keyword">module</span> <a href="Reins.SplaySet.MonoSet.html">MonoSet</a>: <div class="sig_block"><code class="code">functor (</code><code class="code">C</code><code class="code"> : </code><code class="type"><a href="Reins.Types.Mono.Comparable.html">Reins.Types.Mono.Comparable</a></code><code class="code">) -> </code><code class="type"><a href="Reins.Sets.MonoSetSig.html">Reins.Sets.MonoSetSig</a></code><code class="type"> with type elt = C.t and type 'a result = 'a * MonoSet(C).t</code></div></pre><div class="info"> This functor provides an implementation of Splay trees that are parameterized by a specific monomorphic element type. </div> <pre><span class="keyword">module</span> <a href="Reins.SplaySet.GenSet.html">GenSet</a>: <div class="sig_block"><code class="code">functor (</code><code class="code">C</code><code class="code"> : </code><code class="type"><a href="Reins.Types.Mono.ArbitraryComparable.html">Reins.Types.Mono.ArbitraryComparable</a></code><code class="code">) -> </code><code class="type"><a href="Reins.Sets.GenSetSig.html">Reins.Sets.GenSetSig</a></code><code class="type"> with type elt = C.t and type 'a result = 'a * GenSet(C).t</code></div></pre><div class="info"> This functor is similar to the <a href="Reins.SplaySet.MonoSet.html"><code class="code">Reins.SplaySet.MonoSet</code></a> functor except it is parameterized by a module that also supports the <code class="code">gen</code> operation. </div> </body></html>