Data.EulerTourTree

Implementation of Euler tour trees.

import qualified Data.EulerTourTree as ETTree
import Data.EulerTourTree(EulerTourTree)

When specified, time complexity refers to the number n of nodes in the input tree.

Documentation

data EulerTourTree node

 Euler-tour implementation of a tree structure. It is parameterized by a node type node.

Requirements:

• node is ordered
• node values are unique

Instances

Foldable EulerTourTree

member and size are respectively faster than elem and length (which run in O(n)).

Methods

fold :: Monoid m => EulerTourTree m -> m

foldMap :: Monoid m => (a -> m) -> EulerTourTree a -> m

foldr :: (a -> b -> b) -> b -> EulerTourTree a -> b

foldr' :: (a -> b -> b) -> b -> EulerTourTree a -> b

foldl :: (b -> a -> b) -> b -> EulerTourTree a -> b

foldl' :: (b -> a -> b) -> b -> EulerTourTree a -> b

foldr1 :: (a -> a -> a) -> EulerTourTree a -> a

foldl1 :: (a -> a -> a) -> EulerTourTree a -> a

toList :: EulerTourTree a -> [a]

null :: EulerTourTree a -> Bool

length :: EulerTourTree a -> Int

elem :: Eq a => a -> EulerTourTree a -> Bool

maximum :: Ord a => EulerTourTree a -> a

minimum :: Ord a => EulerTourTree a -> a

sum :: Num a => EulerTourTree a -> a

product :: Num a => EulerTourTree a -> a

Eq node => Eq (EulerTourTree node)

Methods

(==) :: EulerTourTree node -> EulerTourTree node -> Bool

(/=) :: EulerTourTree node -> EulerTourTree node -> Bool

Ord node => Ord (EulerTourTree node)

Methods

compare :: EulerTourTree node -> EulerTourTree node -> Ordering

(<) :: EulerTourTree node -> EulerTourTree node -> Bool

(<=) :: EulerTourTree node -> EulerTourTree node -> Bool

(>) :: EulerTourTree node -> EulerTourTree node -> Bool

(>=) :: EulerTourTree node -> EulerTourTree node -> Bool

max :: EulerTourTree node -> EulerTourTree node -> EulerTourTree node

min :: EulerTourTree node -> EulerTourTree node -> EulerTourTree node

Show node => Show (EulerTourTree node)

Methods

showsPrec :: Int -> EulerTourTree node -> ShowS

show :: EulerTourTree node -> String

showList :: [EulerTourTree node] -> ShowS

Ord node => Measured (Set (node, node), Set node, Sum Int) (EulerTourTree node)

Methods

measure :: EulerTourTree node -> (Set (node, node), Set node, Sum Int)

Construction

empty :: Ord node => EulerTourTree node

O(1) Construct an empty Euler tour tree.

singleton :: Ord node => node -> EulerTourTree node

O(1) Construct an Euler tour tree with a single element.

fromTree :: MonadPlus m => Ord node => Tree node -> m (EulerTourTree node)

O(n) Construct an Euler tour tree from a Tree.

Fail if, and only if, node values are not unique.

Deconstruction

toTree :: MonadPlus m => Ord node => EulerTourTree node -> m (Tree node)

O(n) Deconstruct an Euler tour tree into a Tree.

Query

root :: MonadPlus m => Ord node => EulerTourTree node -> m node

O(1) Return the root of the tree. Fail if it is empty.

member :: Ord node => node -> EulerTourTree node -> Bool

O(log n) Return True if node is an element of the tree.

size :: Ord node => EulerTourTree node -> Int

O(1) Return the number of elements in the tree.

Transformation

cutEdge

Arguments

:: MonadPlus m

=> Ord node

=> EulerTourTree node

Denoted by tree

-> (node, node)

Denoted by edge

-> m (EulerTourTree node, EulerTourTree node)

Denoted by (a, b)

O(log n) Return 2 subtrees of tree where a is the subtree of nodes above edge, and b is the subtree of nodes below edge.

Fail if edge isn't found in tree

splice

Arguments

:: MonadPlus m

=> Ord node

=> EulerTourTree node

Denoted by tree1

-> node

Denoted by node

-> EulerTourTree node

Denoted by tree2

-> m (EulerTourTree node)

O(log n) Attach tree1 as a child of node in tree2.

Fail if node isn't found in tree2, or if tree1 and tree2 have nodes in common.

reroot

Arguments

:: MonadPlus m

=> Ord node

=> node

Denoted by node

-> EulerTourTree node

Denoted by tree

-> m (EulerTourTree node)

O(log n) Rotate tree such that node is the new root.

Return Nothing if node isn't found in tree.