Data.Struct.Internal.LinkCut

Documentation

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 a)

Eq (LinkCut a s)

path :: Slot (LinkCut a) (LinkCut a)

parent :: Slot (LinkCut a) (LinkCut a)

left :: Slot (LinkCut a) (LinkCut a)

right :: Slot (LinkCut a) (LinkCut a)

value :: Field (LinkCut a) a

summary :: Field (LinkCut a) a

new :: (PrimMonad m, Monoid a) => a -> m (LinkCut a (PrimState m))

O(1). Allocate a new link-cut tree with a given monoidal summary.

cut :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m ()

O(log n). cut v removes the linkage between v upwards to whatever tree it was in, making v a root node.

Repeated calls on the same value without intermediate accesses are O(1).

link :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m ()

O(log n). link v w inserts v which must be the root of a tree in as a child of w. v and w must not be connected.

connected :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m Bool

O(log n). connected v w determines if v and w inhabit the same tree.

cost :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m a

O(log n). cost v computes the root-to-leaf path cost of v under whatever Monoid was built into the tree.

Repeated calls on the same value without intermediate accesses are O(1).

root :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m (LinkCut a (PrimState m))

O(log n). Find the root of a tree.

Repeated calls on the same value without intermediate accesses are O(1).

up :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m (LinkCut a (PrimState m))

O(log n). Move upward one level.

This will return Nil if the parent is not available.

Note: Repeated calls on the same value without intermediate accesses are O(1).

summarize :: Monoid a => LinkCut a s -> ST s a

O(1)

access :: Monoid a => LinkCut a s -> ST s ()

O(log n)

splay :: Monoid a => LinkCut a s -> ST s ()

O(log n). Splay within an auxiliary tree