Module Reins.SplaySet

module SplaySet: sig .. end

Sets with excellent non-uniform access performance

Splay trees are binary search trees that are balanced based on recently accessed elements. They provide amortized O(log n) performance for tree operations (mem, add, remove), 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., mem). 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.

module PolySet: Reins.Sets.PolySetSig 
  with type ('a,'b) result = 'a * 'b PolySet.t

This module provides an implementation of Splay trees with a polymorphic element type.

module MonoSet: functor (C : Reins.Types.Mono.Comparable) -> Reins.Sets.MonoSetSig  with type elt = C.t
		  and type 'a result = 'a * MonoSet(C).t

This functor provides an implementation of Splay trees that are parameterized by a specific monomorphic element type.

module GenSet: functor (C : Reins.Types.Mono.ArbitraryComparable) -> Reins.Sets.GenSetSig  with type elt = C.t
		 and type 'a result = 'a * GenSet(C).t

This functor is similar to the Reins.SplaySet.MonoSet functor except it is parameterized by a module that also supports the gen operation.