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