Documentation

for commutative monoids

make v root

>>> lct <- newLCT @() 3
>>> linkLCT lct 1 0 >> linkLCT lct 2 1
>>> findRootLCT lct 2
0
>>> evertLCT lct 1
>>> findRootLCT lct 2
1

require: the edge (u, v) exists

link u to v

require: u and v are *not connected*

require: l and r connected

>>> import Data.Monoid
>>> lct <- buildLCT @(Sum Int) $ U.fromList $ map Sum [0..3]
>>> linkLCT lct 1 0 >> linkLCT lct 2 1 >> linkLCT lct 3 1
>>> mconcatPathLCT lct 0 1
Sum {getSum = 1}
>>> mconcatPathLCT lct 2 3  -- 2 - 1 - 3
Sum {getSum = 6}
>>> mconcatPathLCT lct 0 3  -- 0 - 1 - 3
Sum {getSum = 4}

root is the left most node of the root path

commutative monoids

>>> import Data.Monoid
>>> lct <- buildLCT @(Sum Int) $ U.fromList $ map Sum [0..2]
>>> linkLCT lct 1 0 >> linkLCT lct 2 1
>>> mconcatPathLCT lct 0 2
Sum {getSum = 3}
>>> setCMonLCT lct 1 (Sum 100)
>>> mconcatPathLCT lct 0 2
Sum {getSum = 102}

require: u and v are connected

>>> lct <- newLCT @() 4
>>> linkLCT lct 1 0 >> linkLCT lct 2 1 >> linkLCT lct 3 2
>>> evertLCT lct 0
>>> lcaLCT lct 0 3
0
>>> evertLCT lct 2
>>> lcaLCT lct 0 3
2

from the splay tree root to v

make v on the root path

properties * v is the root of the splay tree. * v is the right most node of the root path. * expose u >> expose v == lca u v.

>>> lct <- newLCT @() 2
>>> linkLCT lct 0 1
>>> evertLCT lct 0
>>> exposeLCT lct 1
1
>>> isSplayTreeRootLCT lct 1
True
>>> findRootLCT lct 1
0