Data.Struct.Internal.LinkCut

Documentation

>>> import Data.Struct.Internal.LinkCut

newtype LinkCut a s

Amortized Link-Cut trees via splay trees based on Tarjan's little book.

These support O(log n) operations for a lot of stuff.

The parameter a is an arbitrary user-supplied monoid that will be summarized along the path to the root of the tree.

In this example the choice of Monoid is String, so we can get a textual description of the path to the root.

>>> x <- new "x"
>>> y <- new "y"
>>> link x y -- now x is a child of y
>>> x == y
False
>>> connected x y
True
>>> z <- new "z"
>>> link z x -- now z is a child of y
>>> (y ==) <$> root z
True
>>> cost z
"yxz"
>>> w <- new "w"
>>> u <- new "u"
>>> v <- new "v"
>>> link u w
>>> link v z
>>> link w z
>>> cost u
"yxzwu"
>>> (y ==) <$> root v
True
>>> connected x v
True
>>> cut z

     y
    x          z    y
   z    ==>   w v  x
  w v        u
 u

>>> connected x v
False
>>> cost u
"zwu"
>>> (z ==) <$> root v
True

Constructors

LinkCut (Object s)

Instances

Struct (LinkCut a0)

Methods