Data.Chatty.BST

Provides a typeclass for all binary search trees and an unbalanced implementation

Documentation

class Ord o => Indexable i o v | i -> o, i -> v where

Only instances of Indexable may be saved in a BST

Methods

indexOf :: i -> o

Extract the index

valueOf :: i -> v

Extract the value

Instances

Indexable Int Int Int

Defined in Data.Chatty.BST

Methods

indexOf :: Int -> Int

valueOf :: Int -> Int

Indexable (Node a) NodeId (Node a)

Defined in Data.Chatty.Graph

Methods

indexOf :: Node a -> NodeId

valueOf :: Node a -> Node a

Ord o => Indexable (o, a) o a

Defined in Data.Chatty.BST

Methods

indexOf :: (o, a) -> o

valueOf :: (o, a) -> a

Ord o => Indexable (o, a, b) o (a, b)

Defined in Data.Chatty.BST

Methods

indexOf :: (o, a, b) -> o

valueOf :: (o, a, b) -> (a, b)

Ord o => Indexable (o, a, b, c) o (a, b, c)

Defined in Data.Chatty.BST

Methods

indexOf :: (o, a, b, c) -> o

valueOf :: (o, a, b, c) -> (a, b, c)

Ord o => Indexable (o, a, b, c, d) o (a, b, c, d)

Defined in Data.Chatty.BST

Methods

indexOf :: (o, a, b, c, d) -> o

valueOf :: (o, a, b, c, d) -> (a, b, c, d)

Ord o => Indexable (o, a, b, c, d, e) o (a, b, c, d, e)

Defined in Data.Chatty.BST

Methods

indexOf :: (o, a, b, c, d, e) -> o

valueOf :: (o, a, b, c, d, e) -> (a, b, c, d, e)

class Indexable i o v => AnyBST t i o v where

Typeclass for all BSTs that store the given Indexable

Methods

anyBstInsert :: i -> t i -> t i

Insert into the tree

anyBstRemove :: o -> t i -> t i

Remove from the tree

anyBstMax :: t i -> Maybe i

Get the greatest element

anyBstMin :: t i -> Maybe i

Get the least element

anyBstLookup :: o -> t i -> Maybe v

Lookup a given key

anyBstEmpty :: t i

An empty tree

anyBstHead :: t i -> Maybe i

The root of the tree

anyBstInorder :: t i -> [i]

Traverse the tree in order

Instances

Indexable i o v => AnyBST BST i o v

Defined in Data.Chatty.BST

Methods

anyBstInsert :: i -> BST i -> BST i

anyBstRemove :: o -> BST i -> BST i

anyBstMax :: BST i -> Maybe i

anyBstMin :: BST i -> Maybe i

anyBstLookup :: o -> BST i -> Maybe v

anyBstEmpty :: BST i

anyBstHead :: BST i -> Maybe i

anyBstInorder :: BST i -> [i]

Indexable i o v => AnyBST Focus i o v

Defined in Data.Chatty.Focus

Methods

anyBstInsert :: i -> Focus i -> Focus i

anyBstRemove :: o -> Focus i -> Focus i

anyBstMax :: Focus i -> Maybe i

anyBstMin :: Focus i -> Maybe i

anyBstLookup :: o -> Focus i -> Maybe v

anyBstEmpty :: Focus i

anyBstHead :: Focus i -> Maybe i

anyBstInorder :: Focus i -> [i]

Indexable i o v => AnyBST AVL i o v

Defined in Data.Chatty.AVL

Methods

anyBstInsert :: i -> AVL i -> AVL i

anyBstRemove :: o -> AVL i -> AVL i

anyBstMax :: AVL i -> Maybe i

anyBstMin :: AVL i -> Maybe i

anyBstLookup :: o -> AVL i -> Maybe v

anyBstEmpty :: AVL i

anyBstHead :: AVL i -> Maybe i

anyBstInorder :: AVL i -> [i]

data BST a

An unbalanced binary search tree

Constructors

EmptyBST

BST a !(BST a) !(BST a)

Instances

Indexable i o v => AnyBST BST i o v

Defined in Data.Chatty.BST

Methods

anyBstInsert :: i -> BST i -> BST i

anyBstRemove :: o -> BST i -> BST i

anyBstMax :: BST i -> Maybe i

anyBstMin :: BST i -> Maybe i

anyBstLookup :: o -> BST i -> Maybe v

anyBstEmpty :: BST i

anyBstHead :: BST i -> Maybe i

anyBstInorder :: BST i -> [i]

None (BST a)

Defined in Data.Chatty.BST

Methods

none :: BST a

bstInsert :: Indexable i o v => i -> BST i -> BST i

Insert into the BST

bstRemove :: Indexable i o v => o -> BST i -> BST i

Remove from the BST

bstMax :: BST i -> Maybe i

Get the greatest element

bstMin :: BST i -> Maybe i

Get the least element

bstLookup :: Indexable i o v => o -> BST i -> Maybe v

Lookup a given key

bstContains :: Indexable i o v => o -> BST i -> Bool

Lookup if a given key is contained

bstHead :: Indexable i o v => BST i -> Maybe i

Return the tree's root

bstInorder :: Indexable i o v => BST i -> [i]

Traverse the tree in order