Safe Haskell	None
Language	Haskell2010

Data.Graph.Dynamic.Internal.Tree

Synopsis

class Tree (t :: * -> * -> * -> *) where
- type TreeGen t :: * -> *
- newTreeGen :: PrimMonad m => Proxy t -> m (TreeGen t (PrimState m))
- singleton :: (PrimMonad m, Monoid v) => TreeGen t (PrimState m) -> a -> v -> m (t (PrimState m) a v)
- append :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v)
- cons :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v)
- snoc :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v)
- split :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (Maybe (t (PrimState m) a v), Maybe (t (PrimState m) a v))
- connected :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m Bool
- root :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (t (PrimState m) a v)
- readRoot :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (t (PrimState m) a v)
- label :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m a
- aggregate :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m v
- toList :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m [a]
concat :: forall t m a v. (Tree t, PrimMonad m, Monoid v) => NonEmpty (t (PrimState m) a v) -> m (t (PrimState m) a v)
class Tree t => TestTree t where
- print :: Show a => t (PrimState IO) a v -> IO ()
- assertInvariants :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m ()
- assertSingleton :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m ()
- assertRoot :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m ()

Documentation

class Tree (t :: * -> * -> * -> *) where Source #

The chosen represenation of the tree has a big impact on the performance of the algorithms. This typeclass allows us to swap them out more easily.

Minimal complete definition

newTreeGen, singleton, append, split, connected, root, label, aggregate, toList

Associated Types

type TreeGen t :: * -> * Source #

A management structure used to create new trees

Methods

newTreeGen :: PrimMonad m => Proxy t -> m (TreeGen t (PrimState m)) Source #

Create a tree gen itself

singleton :: (PrimMonad m, Monoid v) => TreeGen t (PrimState m) -> a -> v -> m (t (PrimState m) a v) Source #

Create a tree with a single element.

append :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v) Source #

Join two trees together.

cons :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v) Source #

Prepend a singleton tree

snoc :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v) Source #

Append a singleton tree

split :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (Maybe (t (PrimState m) a v), Maybe (t (PrimState m) a v)) Source #

Split a tree, turning the argument into a singleton and returning the left and right halves of the tree.

connected :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m Bool Source #

Check if two nodes belong to the same tree

root :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (t (PrimState m) a v) Source #

Find the root of a tree

readRoot :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (t (PrimState m) a v) Source #

Read the root of a tree. This is not allowed to modify the tree (e.g., no splaying allowed).

label :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m a Source #

Read the label from a tree

aggregate :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m v Source #

Read the aggregate of a tree

toList :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m [a] Source #

Convert a tree to a list

Instances

Tree Tree Source #
Instance details Defined in Data.Graph.Dynamic.Internal.Splay Associated Types type TreeGen Tree :: Type -> Type Source # Methods newTreeGen :: PrimMonad m => Proxy Tree -> m (TreeGen Tree (PrimState m)) Source # singleton :: (PrimMonad m, Monoid v) => TreeGen Tree (PrimState m) -> a -> v -> m (Tree (PrimState m) a v) Source # append :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # cons :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # snoc :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # split :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Maybe (Tree (PrimState m) a v), Maybe (Tree (PrimState m) a v)) Source # connected :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m Bool Source # root :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # readRoot :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # label :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m a Source # aggregate :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m v Source # toList :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m [a] Source #
Tree Tree Source #
Instance details Defined in Data.Graph.Dynamic.Internal.Random Associated Types type TreeGen Tree :: Type -> Type Source # Methods newTreeGen :: PrimMonad m => Proxy Tree -> m (TreeGen Tree (PrimState m)) Source # singleton :: (PrimMonad m, Monoid v) => TreeGen Tree (PrimState m) -> a -> v -> m (Tree (PrimState m) a v) Source # append :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # cons :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # snoc :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # split :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Maybe (Tree (PrimState m) a v), Maybe (Tree (PrimState m) a v)) Source # connected :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m Bool Source # root :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # readRoot :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # label :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m a Source # aggregate :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m v Source # toList :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m [a] Source #
Tree Tree Source #
Instance details Defined in Data.Graph.Dynamic.Internal.Avl Associated Types type TreeGen Tree :: Type -> Type Source # Methods newTreeGen :: PrimMonad m => Proxy Tree -> m (TreeGen Tree (PrimState m)) Source # singleton :: (PrimMonad m, Monoid v) => TreeGen Tree (PrimState m) -> a -> v -> m (Tree (PrimState m) a v) Source # append :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # cons :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # snoc :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # split :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Maybe (Tree (PrimState m) a v), Maybe (Tree (PrimState m) a v)) Source # connected :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> Tree (PrimState m) a v -> m Bool Source # root :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # readRoot :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m (Tree (PrimState m) a v) Source # label :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m a Source # aggregate :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m v Source # toList :: (PrimMonad m, Monoid v) => Tree (PrimState m) a v -> m [a] Source #

concat :: forall t m a v. (Tree t, PrimMonad m, Monoid v) => NonEmpty (t (PrimState m) a v) -> m (t (PrimState m) a v) Source #

class Tree t => TestTree t where Source #

These methods can be used for testing and debugging.

Methods

print :: Show a => t (PrimState IO) a v -> IO () Source #

assertInvariants :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m () Source #

assertSingleton :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m () Source #

assertRoot :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m () Source #

Instances

TestTree Tree Source #
Instance details Defined in Data.Graph.Dynamic.Internal.Splay Methods print :: Show a => Tree (PrimState IO) a v -> IO () Source # assertInvariants :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m () Source # assertSingleton :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m () Source # assertRoot :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m () Source #
TestTree Tree Source #
Instance details Defined in Data.Graph.Dynamic.Internal.Random Methods print :: Show a => Tree (PrimState IO) a v -> IO () Source # assertInvariants :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m () Source # assertSingleton :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m () Source # assertRoot :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m () Source #
TestTree Tree Source #
Instance details Defined in Data.Graph.Dynamic.Internal.Avl Methods print :: Show a => Tree (PrimState IO) a v -> IO () Source # assertInvariants :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m () Source # assertSingleton :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m () Source # assertRoot :: (PrimMonad m, Monoid v, Eq v, Show v) => Tree (PrimState m) a v -> m () Source #