Data.BinaryTree

Several types of Binary trees.

Documentation

data BinLeafTree v a

Binary tree that stores its values (of type a) in the leaves. Internal nodes store something of type v.

Constructors

Leaf !a

Node (BinLeafTree v a) !v (BinLeafTree v a)

Instances

Measured v a => Measured v (BinLeafTree v a)

Defined in Data.BinaryTree

Methods

measure :: BinLeafTree v a -> v

Functor (BinLeafTree v)

Defined in Data.BinaryTree

Methods

fmap :: (a -> b) -> BinLeafTree v a -> BinLeafTree v b

(<$) :: a -> BinLeafTree v b -> BinLeafTree v a

Foldable (BinLeafTree v)

Defined in Data.BinaryTree

Methods

fold :: Monoid m => BinLeafTree v m -> m

foldMap :: Monoid m => (a -> m) -> BinLeafTree v a -> m

foldr :: (a -> b -> b) -> b -> BinLeafTree v a -> b

foldr' :: (a -> b -> b) -> b -> BinLeafTree v a -> b

foldl :: (b -> a -> b) -> b -> BinLeafTree v a -> b

foldl' :: (b -> a -> b) -> b -> BinLeafTree v a -> b

foldr1 :: (a -> a -> a) -> BinLeafTree v a -> a

foldl1 :: (a -> a -> a) -> BinLeafTree v a -> a

toList :: BinLeafTree v a -> [a]

null :: BinLeafTree v a -> Bool

length :: BinLeafTree v a -> Int

elem :: Eq a => a -> BinLeafTree v a -> Bool

maximum :: Ord a => BinLeafTree v a -> a

minimum :: Ord a => BinLeafTree v a -> a

sum :: Num a => BinLeafTree v a -> a

product :: Num a => BinLeafTree v a -> a

Traversable (BinLeafTree v)

Defined in Data.BinaryTree

Methods

traverse :: Applicative f => (a -> f b) -> BinLeafTree v a -> f (BinLeafTree v b)

sequenceA :: Applicative f => BinLeafTree v (f a) -> f (BinLeafTree v a)

mapM :: Monad m => (a -> m b) -> BinLeafTree v a -> m (BinLeafTree v b)

sequence :: Monad m => BinLeafTree v (m a) -> m (BinLeafTree v a)

Foldable1 (BinLeafTree v)

Defined in Data.BinaryTree

Methods

fold1 :: Semigroup m => BinLeafTree v m -> m

foldMap1 :: Semigroup m => (a -> m) -> BinLeafTree v a -> m

toNonEmpty :: BinLeafTree v a -> NonEmpty a

(Eq a, Eq v) => Eq (BinLeafTree v a)

Defined in Data.BinaryTree

Methods

(==) :: BinLeafTree v a -> BinLeafTree v a -> Bool

(/=) :: BinLeafTree v a -> BinLeafTree v a -> Bool

(Ord a, Ord v) => Ord (BinLeafTree v a)

Defined in Data.BinaryTree

Methods

compare :: BinLeafTree v a -> BinLeafTree v a -> Ordering

(<) :: BinLeafTree v a -> BinLeafTree v a -> Bool

(<=) :: BinLeafTree v a -> BinLeafTree v a -> Bool

(>) :: BinLeafTree v a -> BinLeafTree v a -> Bool

(>=) :: BinLeafTree v a -> BinLeafTree v a -> Bool

max :: BinLeafTree v a -> BinLeafTree v a -> BinLeafTree v a

min :: BinLeafTree v a -> BinLeafTree v a -> BinLeafTree v a

(Read a, Read v) => Read (BinLeafTree v a)

Defined in Data.BinaryTree

Methods

readsPrec :: Int -> ReadS (BinLeafTree v a)

readList :: ReadS [BinLeafTree v a]

readPrec :: ReadPrec (BinLeafTree v a)

readListPrec :: ReadPrec [BinLeafTree v a]

(Show a, Show v) => Show (BinLeafTree v a)

Defined in Data.BinaryTree

Methods

showsPrec :: Int -> BinLeafTree v a -> ShowS

show :: BinLeafTree v a -> String

showList :: [BinLeafTree v a] -> ShowS

Generic (BinLeafTree v a)

Defined in Data.BinaryTree

Associated Types

type Rep (BinLeafTree v a) :: Type -> Type

Methods

from :: BinLeafTree v a -> Rep (BinLeafTree v a) x

to :: Rep (BinLeafTree v a) x -> BinLeafTree v a

Measured v a => Semigroup (BinLeafTree v a)

Defined in Data.BinaryTree

Methods

(<>) :: BinLeafTree v a -> BinLeafTree v a -> BinLeafTree v a

sconcat :: NonEmpty (BinLeafTree v a) -> BinLeafTree v a

stimes :: Integral b => b -> BinLeafTree v a -> BinLeafTree v a

(Arbitrary a, Arbitrary v) => Arbitrary (BinLeafTree v a)

Defined in Test.QuickCheck.HGeometryInstances

Methods

arbitrary :: Gen (BinLeafTree v a)

shrink :: BinLeafTree v a -> [BinLeafTree v a]

(NFData v, NFData a) => NFData (BinLeafTree v a)

Defined in Data.BinaryTree

Methods

rnf :: BinLeafTree v a -> ()

type Rep (BinLeafTree v a)

Defined in Data.BinaryTree

type Rep (BinLeafTree v a) = D1 (MetaData "BinLeafTree" "Data.BinaryTree" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" False) (C1 (MetaCons "Leaf" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 a)) :+: C1 (MetaCons "Node" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (BinLeafTree v a)) :*: (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 v) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (BinLeafTree v a)))))

class Semigroup v => Measured v a | a -> v where

Methods

measure :: a -> v

Instances

Measured Size (Elem a)

Defined in Data.BinaryTree

Methods

measure :: Elem a -> Size

Measured v a => Measured v (BinLeafTree v a)

Defined in Data.BinaryTree

Methods

measure :: BinLeafTree v a -> v

Semigroup v => Measured v (NodeData d r v)

Defined in Algorithms.Geometry.WellSeparatedPairDecomposition.Types

Methods

measure :: NodeData d r v -> v

Measured [I a] (I a)

Defined in Data.Geometry.SegmentTree.Generic

Methods

measure :: I a -> [I a]

node :: Measured v a => BinLeafTree v a -> BinLeafTree v a -> BinLeafTree v a

smart constructor

asBalancedBinLeafTree :: NonEmpty a -> BinLeafTree Size (Elem a)

Create a balanced tree, i.e. a tree of height \(O(\log n)\) with the elements in the leaves.

\(O(n)\) time.

foldUp :: (b -> v -> b -> b) -> (a -> b) -> BinLeafTree v a -> b

Given a function to combine internal nodes into b's and leafs into b's, traverse the tree bottom up, and combine everything into one b.

foldUpData :: (w -> v -> w -> w) -> (a -> w) -> BinLeafTree v a -> BinLeafTree w a

Traverses the tree bottom up, recomputing the assocated values.

zipExactWith :: (u -> v -> w) -> (a -> b -> c) -> BinLeafTree u a -> BinLeafTree v b -> BinLeafTree w c

Takes two trees, that have the same structure, and uses the provided functions to "zip" them together

newtype Size

Constructors

Size Int

Instances

Enum Size

Defined in Data.BinaryTree

Methods

succ :: Size -> Size

pred :: Size -> Size

toEnum :: Int -> Size

fromEnum :: Size -> Int

enumFrom :: Size -> [Size]

enumFromThen :: Size -> Size -> [Size]

enumFromTo :: Size -> Size -> [Size]

enumFromThenTo :: Size -> Size -> Size -> [Size]

Eq Size

Defined in Data.BinaryTree

Methods

(==) :: Size -> Size -> Bool

(/=) :: Size -> Size -> Bool

Integral Size

Defined in Data.BinaryTree

Methods

quot :: Size -> Size -> Size

rem :: Size -> Size -> Size

div :: Size -> Size -> Size

mod :: Size -> Size -> Size

quotRem :: Size -> Size -> (Size, Size)

divMod :: Size -> Size -> (Size, Size)

toInteger :: Size -> Integer

Num Size

Defined in Data.BinaryTree

Methods

(+) :: Size -> Size -> Size

(-) :: Size -> Size -> Size

(*) :: Size -> Size -> Size

negate :: Size -> Size

abs :: Size -> Size

signum :: Size -> Size

fromInteger :: Integer -> Size

Ord Size

Defined in Data.BinaryTree

Methods

compare :: Size -> Size -> Ordering

(<) :: Size -> Size -> Bool

(<=) :: Size -> Size -> Bool

(>) :: Size -> Size -> Bool

(>=) :: Size -> Size -> Bool

max :: Size -> Size -> Size

min :: Size -> Size -> Size

Read Size

Defined in Data.BinaryTree

Methods

readsPrec :: Int -> ReadS Size

readList :: ReadS [Size]

readPrec :: ReadPrec Size

readListPrec :: ReadPrec [Size]

Real Size

Defined in Data.BinaryTree

Methods

toRational :: Size -> Rational

Show Size

Defined in Data.BinaryTree

Methods

showsPrec :: Int -> Size -> ShowS

show :: Size -> String

showList :: [Size] -> ShowS

Generic Size

Defined in Data.BinaryTree

Associated Types

type Rep Size :: Type -> Type

Methods

from :: Size -> Rep Size x

to :: Rep Size x -> Size

Semigroup Size

Defined in Data.BinaryTree

Methods

(<>) :: Size -> Size -> Size

sconcat :: NonEmpty Size -> Size

stimes :: Integral b => b -> Size -> Size

Monoid Size

Defined in Data.BinaryTree

Methods

mempty :: Size

mappend :: Size -> Size -> Size

mconcat :: [Size] -> Size

NFData Size

Defined in Data.BinaryTree

Methods

rnf :: Size -> ()

Measured Size (Elem a)

Defined in Data.BinaryTree

Methods

measure :: Elem a -> Size

type Rep Size

Defined in Data.BinaryTree

type Rep Size = D1 (MetaData "Size" "Data.BinaryTree" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" True) (C1 (MetaCons "Size" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Int)))

newtype Elem a

Constructors

Elem

Fields

• _unElem :: a

Instances

Functor Elem

Defined in Data.BinaryTree

Methods

fmap :: (a -> b) -> Elem a -> Elem b

(<$) :: a -> Elem b -> Elem a

Foldable Elem

Defined in Data.BinaryTree

Methods

fold :: Monoid m => Elem m -> m

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

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

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

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

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

foldr1 :: (a -> a -> a) -> Elem a -> a

foldl1 :: (a -> a -> a) -> Elem a -> a

toList :: Elem a -> [a]

null :: Elem a -> Bool

length :: Elem a -> Int

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

maximum :: Ord a => Elem a -> a

minimum :: Ord a => Elem a -> a

sum :: Num a => Elem a -> a

product :: Num a => Elem a -> a

Traversable Elem

Defined in Data.BinaryTree

Methods

traverse :: Applicative f => (a -> f b) -> Elem a -> f (Elem b)

sequenceA :: Applicative f => Elem (f a) -> f (Elem a)

mapM :: Monad m => (a -> m b) -> Elem a -> m (Elem b)

sequence :: Monad m => Elem (m a) -> m (Elem a)

Measured Size (Elem a)

Defined in Data.BinaryTree

Methods

measure :: Elem a -> Size

Eq a => Eq (Elem a)

Defined in Data.BinaryTree

Methods

(==) :: Elem a -> Elem a -> Bool

(/=) :: Elem a -> Elem a -> Bool

Ord a => Ord (Elem a)

Defined in Data.BinaryTree

Methods

compare :: Elem a -> Elem a -> Ordering

(<) :: Elem a -> Elem a -> Bool

(<=) :: Elem a -> Elem a -> Bool

(>) :: Elem a -> Elem a -> Bool

(>=) :: Elem a -> Elem a -> Bool

max :: Elem a -> Elem a -> Elem a

min :: Elem a -> Elem a -> Elem a

Read a => Read (Elem a)

Defined in Data.BinaryTree

Methods

readsPrec :: Int -> ReadS (Elem a)

readList :: ReadS [Elem a]

readPrec :: ReadPrec (Elem a)

readListPrec :: ReadPrec [Elem a]

Show a => Show (Elem a)

Defined in Data.BinaryTree

Methods

showsPrec :: Int -> Elem a -> ShowS

show :: Elem a -> String

showList :: [Elem a] -> ShowS

data Sized a

Constructors

Sized !Size a

Instances

Functor Sized

Defined in Data.BinaryTree

Methods

fmap :: (a -> b) -> Sized a -> Sized b

(<$) :: a -> Sized b -> Sized a

Foldable Sized

Defined in Data.BinaryTree

Methods

fold :: Monoid m => Sized m -> m

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

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

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

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

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

foldr1 :: (a -> a -> a) -> Sized a -> a

foldl1 :: (a -> a -> a) -> Sized a -> a

toList :: Sized a -> [a]

null :: Sized a -> Bool

length :: Sized a -> Int

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

maximum :: Ord a => Sized a -> a

minimum :: Ord a => Sized a -> a

sum :: Num a => Sized a -> a

product :: Num a => Sized a -> a

Traversable Sized

Defined in Data.BinaryTree

Methods

traverse :: Applicative f => (a -> f b) -> Sized a -> f (Sized b)

sequenceA :: Applicative f => Sized (f a) -> f (Sized a)

mapM :: Monad m => (a -> m b) -> Sized a -> m (Sized b)

sequence :: Monad m => Sized (m a) -> m (Sized a)

Eq a => Eq (Sized a)

Defined in Data.BinaryTree

Methods

(==) :: Sized a -> Sized a -> Bool

(/=) :: Sized a -> Sized a -> Bool

Ord a => Ord (Sized a)

Defined in Data.BinaryTree

Methods

compare :: Sized a -> Sized a -> Ordering

(<) :: Sized a -> Sized a -> Bool

(<=) :: Sized a -> Sized a -> Bool

(>) :: Sized a -> Sized a -> Bool

(>=) :: Sized a -> Sized a -> Bool

max :: Sized a -> Sized a -> Sized a

min :: Sized a -> Sized a -> Sized a

Show a => Show (Sized a)

Defined in Data.BinaryTree

Methods

showsPrec :: Int -> Sized a -> ShowS

show :: Sized a -> String

showList :: [Sized a] -> ShowS

Generic (Sized a)

Defined in Data.BinaryTree

Associated Types

type Rep (Sized a) :: Type -> Type

Methods

from :: Sized a -> Rep (Sized a) x

to :: Rep (Sized a) x -> Sized a

Semigroup a => Semigroup (Sized a)

Defined in Data.BinaryTree

Methods

(<>) :: Sized a -> Sized a -> Sized a

sconcat :: NonEmpty (Sized a) -> Sized a

stimes :: Integral b => b -> Sized a -> Sized a

Monoid a => Monoid (Sized a)

Defined in Data.BinaryTree

Methods

mempty :: Sized a

mappend :: Sized a -> Sized a -> Sized a

mconcat :: [Sized a] -> Sized a

NFData a => NFData (Sized a)

Defined in Data.BinaryTree

Methods

rnf :: Sized a -> ()

type Rep (Sized a)

Defined in Data.BinaryTree

type Rep (Sized a) = D1 (MetaData "Sized" "Data.BinaryTree" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" False) (C1 (MetaCons "Sized" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Size) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)))

Converting into a Data.Tree

data RoseElem v a

Constructors

InternalNode v

LeafNode a

Instances

Functor (RoseElem v)

Defined in Data.BinaryTree

Methods

fmap :: (a -> b) -> RoseElem v a -> RoseElem v b

(<$) :: a -> RoseElem v b -> RoseElem v a

(Eq v, Eq a) => Eq (RoseElem v a)

Defined in Data.BinaryTree

Methods

(==) :: RoseElem v a -> RoseElem v a -> Bool

(/=) :: RoseElem v a -> RoseElem v a -> Bool

(Show v, Show a) => Show (RoseElem v a)

Defined in Data.BinaryTree

Methods

showsPrec :: Int -> RoseElem v a -> ShowS

show :: RoseElem v a -> String

showList :: [RoseElem v a] -> ShowS

toRoseTree :: BinLeafTree v a -> Tree (RoseElem v a)

drawTree :: (Show v, Show a) => BinLeafTree v a -> String

Internal Node Tree

data BinaryTree a

Binary tree in which we store the values of type a in internal nodes.

Constructors

Nil

Internal (BinaryTree a) !a (BinaryTree a)

Instances

Functor BinaryTree

Defined in Data.BinaryTree

Methods

fmap :: (a -> b) -> BinaryTree a -> BinaryTree b

(<$) :: a -> BinaryTree b -> BinaryTree a

Foldable BinaryTree

Defined in Data.BinaryTree

Methods

fold :: Monoid m => BinaryTree m -> m

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

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

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

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

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

foldr1 :: (a -> a -> a) -> BinaryTree a -> a

foldl1 :: (a -> a -> a) -> BinaryTree a -> a

toList :: BinaryTree a -> [a]

null :: BinaryTree a -> Bool

length :: BinaryTree a -> Int

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

maximum :: Ord a => BinaryTree a -> a

minimum :: Ord a => BinaryTree a -> a

sum :: Num a => BinaryTree a -> a

product :: Num a => BinaryTree a -> a

Traversable BinaryTree

Defined in Data.BinaryTree

Methods

traverse :: Applicative f => (a -> f b) -> BinaryTree a -> f (BinaryTree b)

sequenceA :: Applicative f => BinaryTree (f a) -> f (BinaryTree a)

mapM :: Monad m => (a -> m b) -> BinaryTree a -> m (BinaryTree b)

sequence :: Monad m => BinaryTree (m a) -> m (BinaryTree a)

Eq a => Eq (BinaryTree a)

Defined in Data.BinaryTree

Methods

(==) :: BinaryTree a -> BinaryTree a -> Bool

(/=) :: BinaryTree a -> BinaryTree a -> Bool

Ord a => Ord (BinaryTree a)

Defined in Data.BinaryTree

Methods

compare :: BinaryTree a -> BinaryTree a -> Ordering

(<) :: BinaryTree a -> BinaryTree a -> Bool

(<=) :: BinaryTree a -> BinaryTree a -> Bool

(>) :: BinaryTree a -> BinaryTree a -> Bool

(>=) :: BinaryTree a -> BinaryTree a -> Bool

max :: BinaryTree a -> BinaryTree a -> BinaryTree a

min :: BinaryTree a -> BinaryTree a -> BinaryTree a

Read a => Read (BinaryTree a)

Defined in Data.BinaryTree

Methods

readsPrec :: Int -> ReadS (BinaryTree a)

readList :: ReadS [BinaryTree a]

readPrec :: ReadPrec (BinaryTree a)

readListPrec :: ReadPrec [BinaryTree a]

Show a => Show (BinaryTree a)

Defined in Data.BinaryTree

Methods

showsPrec :: Int -> BinaryTree a -> ShowS

show :: BinaryTree a -> String

showList :: [BinaryTree a] -> ShowS

Generic (BinaryTree a)

Defined in Data.BinaryTree

Associated Types

type Rep (BinaryTree a) :: Type -> Type

Methods

from :: BinaryTree a -> Rep (BinaryTree a) x

to :: Rep (BinaryTree a) x -> BinaryTree a

Arbitrary a => Arbitrary (BinaryTree a)

Defined in Test.QuickCheck.HGeometryInstances

Methods

arbitrary :: Gen (BinaryTree a)

shrink :: BinaryTree a -> [BinaryTree a]

NFData a => NFData (BinaryTree a)

Defined in Data.BinaryTree

Methods

rnf :: BinaryTree a -> ()

type Rep (BinaryTree a)

Defined in Data.BinaryTree

type Rep (BinaryTree a) = D1 (MetaData "BinaryTree" "Data.BinaryTree" "hgeometry-0.8.0.0-2B18HmKepFxHOPvqiUEkND" False) (C1 (MetaCons "Nil" PrefixI False) (U1 :: Type -> Type) :+: C1 (MetaCons "Internal" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (BinaryTree a)) :*: (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 a) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (BinaryTree a)))))

access :: BinaryTree a -> Maybe a

Get the element stored at the root, if it exists

asBalancedBinTree :: [a] -> BinaryTree a

Create a balanced binary tree.

running time: \(O(n)\)

foldBinaryUp :: b -> (a -> b -> b -> b) -> BinaryTree a -> BinaryTree (a, b)

Fold function for folding over a binary tree.

toRoseTree' :: BinaryTree a -> Maybe (Tree a)

Convert a BinaryTree into a RoseTree

drawTree' :: Show a => BinaryTree a -> String

Draw a binary tree.