anchor.diff:  -export([new/0, find/2, insert/3, insert/4, remove/2, expire/2]).
   
   -opaque treap() :: undefined | {Left :: treap(), Key :: term(),
  -		Time :: erlang:system_time(), Item :: term(), Right :: treap()}.
  +		Time :: pos_integer(), Item :: term(), Right :: treap()}.
   -export_type([treap/0]).
  +%% @type treap(). The treap data structure is a combination of a tree
  +%% 	and a heap. This `treap()' is a binary search tree with respect
  +%% 	to a `Key' and a heap with respect to an integer `Time'. The
  +%% 	tree is rebalanced when an `Item' is inserted or removed so that
  +%%		the oldest entries are leef nodes and the newest are clustered
  +%% 	around the root of the tree. The main benefit is that expiring
  +%% 	all entries older than a selected `Time' may be done very
  +%% 	efficiently by pruning branches.
   
  --spec new() -> treap().
  +-spec new() -> Tree
  +	when
  +		Tree :: treap().
   %% @doc Returns a new empty `Tree'.
   new() ->
   	undefined.
   
  --spec find(Tree :: treap(), Key :: term()) -> Item :: term().
  -%% @doc Find value `Item' with key `Key' in `Tree'.
  +-spec find(Tree, Key) -> Item
  +	when
  +		Tree :: treap(),
  +		Key :: term(),
  +		Item :: term().
  +%% @doc Retrieves the value stored with `Key' in `Tree'.
  +%% 	Assumes the key exists, crashes otherwise.
   find({_, Key, _, Item, _} = _Tree, Key) ->
   	Item;
   find({Left, K, _, _, _}, Key) when Key < K ->
  
positive.code: %%% @reference <a href="http://arxiv.org/pdf/cs/0505038v1.pdf">
  %%% 	Efficient Management of Short-Lived Data</a>
  %%% @todo Expire during operations?
  %%%---------------------------------------------------------------------
  %%%
  -module(ephemeral_trees).
  
negative.code: insert(undefined, Key, Time, Item) ->
  	{undefined, Key, Time, Item, undefined}.
  
  -spec remove(Tree1, Key) -> Tree2
  	when
  		Tree1 :: treap(),
  		Key :: term(),
  		Tree2 :: treap().
  %% @doc Remove `Key' from `Tree1'.
  %% 	Returns a new `treap()' in `Tree2'.
  remove({_, Key, _, _, _} = Tree1, Key) ->
  	percolate(Tree1);
  remove({Left, K, T, I, Right}, Key) when Key < K ->
  	{remove(Left, Key), K, T, I, Right};
  remove({Left, K, T, I, Right}, Key) ->
  	{Left, K, T, I, remove(Right, Key)}.
  	
  -spec expire(Tree1, Time) -> Tree2
  	when
  		Tree1 :: treap(),
  		Time :: pos_integer(),
  		Tree2 :: treap().
  %% @doc Efficiently emove every item older than `Time'.
  %% 	Returns a new `treap()' in `Tree2'.
  expire({_, K, T, _, _} = Tree1, Time) when T < Time ->
  	expire(remove(Tree1, K), Time);
  expire(Tree, _Time) ->
  	Tree.
  
  %%%
  %%% internal functions
  %%% 
  
  -spec rebalance(Tree1) -> Tree2
  	when
  		Tree1 :: treap(),
  		Tree2 :: treap().
  %% @doc Rebalance through order-preserving node rotations.
  %% @private
  rebalance({{S1, K, T, I, S2}, Key, Time, Item, S3} = _Tree1) when Time > T ->
  	{S1, K, T, I, {S2, Key, Time, Item, S3}};
  rebalance({S1, Key, Time, Item, {S2, K, T, I, S3}}) when Time > T ->
  	{{S1, Key, Time, Item, S2}, K, T, I, S3};
  rebalance(Tree) ->
  	Tree.
  
  -spec percolate(Tree1) -> Tree2
  	when
  		Tree1 :: treap(),
  		Tree2 :: treap().
  %% @doc Rebalancing node rotations during removal.
  %% @private
  percolate({undefined, _, _, _, undefined} = _Tree1) ->
  	undefined;
  percolate({undefined, K, T, I, {Lr, Kr, Tr, Ir, Rr}}) ->
  	{Lr, Kr, Tr, Ir, percolate({undefined, K, T, I, Rr})};
  