lib

Splay tree

Based on Sam Westrick's SML implementation: https://github.com/shwestrick/pure-splay/blob/master/BottomUpSplay.sml Note for using this library in IC: Since lookup changes the shape of the splay tree, we cannot use query calls for anything that touches the splay tree.

import Splay "mo:splay";

let t = Splay.Splay<Int>(Int.compare);
t.fromArray([3,5,4,2,6,4,1,9,7,8]);
for (x in arr.vals()) {
   assert(t.find(x) == true);
   t.remove(x);
   assert(t.find(x) == false);
   t.insert(x);
   assert(t.find(x) == true);
   assert(t.min() == ?1);
};

type Tree<X> = {#node : (Tree<X>, X, Tree<X>); #empty}

class Splay<X>(compareTo : (X, X) -> O.Order)

lib

type Tree<X> = {#node : (Tree<X>, X, Tree<X>); #empty}

class Splay<X>(compareTo : (X, X) -> O.Order)

`public func insert(k : X)`

`public func find(k : X) : Bool`

`public func remove(k : X)`

`public func min() : ?X`

`public func fromArray(arr : [X])`

`public func entries() : I.Iter<X>`