splay
Splay trees

Next:

<splay> ( -- tree )

Vocabulary
trees.splay

Class description
This is the class for splay trees. Splay trees have amortized average-case logarithmic time storage and retrieval operations, and better complexity on more skewed lookup distributions, though in bad situations they can degrade to linear time, resembling a linked list. These conform to the assoc protocol.

Definition

USING: trees ;

IN: trees.splay

TUPLE: splay < tree ;

Methods

USING: assocs generic kernel sequences trees trees.private
trees.splay ;

M: splay assoc-clone-like
    [ dup tree? [ >bfs-alist reverse ] when ] dip
    M\ splay assoc-clone-like (call-next-method) ;


USING: assocs kernel trees.splay ;

M: splay assoc-like drop dup splay? [ >splay ] unless ;


USING: accessors assocs kernel trees.splay trees.splay.private ;

M: splay at*
    dup root>>
    [ get-splay [ dup [ value>> ] when ] dip ] [ 2drop f f ] if
    ;


USING: accessors assocs kernel trees.splay trees.splay.private ;

M: splay delete-at dup root>> [ remove-splay ] [ 2drop ] if ;


USING: assocs kernel trees.splay ;

M: splay new-assoc 2drop <splay> ;


USING: kernel prettyprint.custom trees.splay ;

M: splay pprint-delims drop \ SPLAY{ \ } ;


USING: accessors assocs kernel trees.splay trees.splay.private ;

M: splay set-at dup root>> [ set-splay ] [ new-root ] if ;