-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Euler tour trees
--   
--   Euler tour trees
@package euler-tour-tree
@version 0.1.0.1


-- | Implementation of Euler tour trees.
--   
--   <pre>
--   import qualified Data.EulerTourTree as ETTree
--   import Data.EulerTourTree(EulerTourTree)
--   </pre>
--   
--   When specified, time complexity refers to the number <i>n</i> of nodes
--   in the input tree.
module Data.EulerTourTree

-- | Euler-tour implementation of a tree structure. It is parameterized by
--   a node type <tt>node</tt>.
--   
--   Requirements:
--   
--   <ul>
--   <li><tt>node</tt> is ordered</li>
--   <li>node values are unique</li>
--   </ul>
data EulerTourTree node

-- | <i>O(1)</i> Construct an empty Euler tour tree.
empty :: Ord node => EulerTourTree node

-- | <i>O(1)</i> Construct an Euler tour tree with a single element.
singleton :: Ord node => node -> EulerTourTree node

-- | <i>O(n)</i> Construct an Euler tour tree from a <a>Tree</a>.
--   
--   Fail if, and only if, node values are not unique.
fromTree :: MonadPlus m => Ord node => Tree node -> m (EulerTourTree node)

-- | <i>O(n)</i> Deconstruct an Euler tour tree into a <a>Tree</a>.
toTree :: MonadPlus m => Ord node => EulerTourTree node -> m (Tree node)

-- | <i>O(1)</i> Return the root of the tree. Fail if it is empty.
root :: MonadPlus m => Ord node => EulerTourTree node -> m node

-- | <i>O(log n)</i> Return <a>True</a> if node is an element of the tree.
member :: Ord node => node -> EulerTourTree node -> Bool

-- | <i>O(1)</i> Return the number of elements in the tree.
size :: Ord node => EulerTourTree node -> Int

-- | <i>O(log n)</i> Return 2 subtrees of <tt>tree</tt> where <tt>a</tt> is
--   the subtree of nodes <b>a</b>bove <tt>edge</tt>, and <tt>b</tt> is the
--   subtree of nodes <b>b</b>elow <tt>edge</tt>.
--   
--   Fail if <tt>edge</tt> isn't found in <tt>tree</tt>
cutEdge :: MonadPlus m => Ord node => EulerTourTree node -> (node, node) -> m (EulerTourTree node, EulerTourTree node)

-- | <i>O(log n)</i> Attach <tt>tree1</tt> as a child of <tt>node</tt> in
--   <tt>tree2</tt>.
--   
--   Fail if <tt>node</tt> isn't found in <tt>tree2</tt>, or if
--   <tt>tree1</tt> and <tt>tree2</tt> have nodes in common.
splice :: MonadPlus m => Ord node => EulerTourTree node -> node -> EulerTourTree node -> m (EulerTourTree node)

-- | <i>O(log n)</i> Rotate <tt>tree</tt> such that <tt>node</tt> is the
--   new root.
--   
--   Fail if <tt>node</tt> isn't found in <tt>tree</tt>.
reroot :: MonadPlus m => Ord node => node -> EulerTourTree node -> m (EulerTourTree node)
instance GHC.Classes.Eq node => GHC.Classes.Eq (Data.EulerTourTree.EulerTourNode node)
instance GHC.Classes.Ord node => GHC.Classes.Ord (Data.EulerTourTree.EulerTourNode node)
instance GHC.Show.Show node => GHC.Show.Show (Data.EulerTourTree.EulerTourNode node)
instance GHC.Show.Show node => GHC.Show.Show (Data.EulerTourTree.EulerTourMonoid node)
instance GHC.Classes.Eq node => GHC.Classes.Eq (Data.EulerTourTree.EulerTourTree node)
instance GHC.Classes.Ord node => GHC.Classes.Ord (Data.EulerTourTree.EulerTourTree node)
instance GHC.Show.Show node => GHC.Show.Show (Data.EulerTourTree.EulerTourTree node)
instance GHC.Classes.Ord node => Data.FingerTree.Measured (Data.Set.Internal.Set (node, node), Data.Set.Internal.Set node, Data.Monoid.Sum GHC.Types.Int) (Data.EulerTourTree.EulerTourTree node)
instance Data.Foldable.Foldable Data.EulerTourTree.EulerTourTree
instance GHC.Classes.Ord node => GHC.Base.Monoid (Data.EulerTourTree.EulerTourMonoid node)
instance GHC.Classes.Ord node => Data.FingerTree.Measured (Data.EulerTourTree.EulerTourMonoid node) (Data.EulerTourTree.EulerTourNode node)
