Safe Haskell	Safe
Language	Haskell2010

Data.Chatty.BST

Description

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

Synopsis

class Ord o => Indexable i o v | i -> o, i -> v where
- indexOf :: i -> o
- valueOf :: i -> v
class Indexable i o v => AnyBST t i o v where
- anyBstInsert :: i -> t i -> t i
- anyBstRemove :: o -> t i -> t i
- anyBstMax :: t i -> Maybe i
- anyBstMin :: t i -> Maybe i
- anyBstLookup :: o -> t i -> Maybe v
- anyBstEmpty :: t i
- anyBstHead :: t i -> Maybe i
- anyBstInorder :: t i -> [i]
data BST a
- = EmptyBST
- | BST a !(BST a) !(BST a)
bstInsert :: Indexable i o v => i -> BST i -> BST i
bstRemove :: Indexable i o v => o -> BST i -> BST i
bstMax :: BST i -> Maybe i
bstMin :: BST i -> Maybe i
bstLookup :: Indexable i o v => o -> BST i -> Maybe v
bstContains :: Indexable i o v => o -> BST i -> Bool
bstHead :: Indexable i o v => BST i -> Maybe i
bstInorder :: Indexable i o v => BST i -> [i]

Documentation

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

Only instances of Indexable may be saved in a BST

Methods

indexOf :: i -> o Source #

Extract the index

valueOf :: i -> v Source #

Extract the value

Instances

Instances details

Indexable Int Int Int Source #
Instance details Defined in Data.Chatty.BST Methods indexOf :: Int -> Int Source # valueOf :: Int -> Int Source #
Indexable (Node a) NodeId (Node a) Source #
Instance details Defined in Data.Chatty.Graph Methods indexOf :: Node a -> NodeId Source # valueOf :: Node a -> Node a Source #
Ord o => Indexable (o, a) o a Source #
Instance details Defined in Data.Chatty.BST Methods indexOf :: (o, a) -> o Source # valueOf :: (o, a) -> a Source #
Ord o => Indexable (o, a, b) o (a, b) Source #
Instance details Defined in Data.Chatty.BST Methods indexOf :: (o, a, b) -> o Source # valueOf :: (o, a, b) -> (a, b) Source #
Ord o => Indexable (o, a, b, c) o (a, b, c) Source #
Instance details Defined in Data.Chatty.BST Methods indexOf :: (o, a, b, c) -> o Source # valueOf :: (o, a, b, c) -> (a, b, c) Source #
Ord o => Indexable (o, a, b, c, d) o (a, b, c, d) Source #
Instance details Defined in Data.Chatty.BST Methods indexOf :: (o, a, b, c, d) -> o Source # valueOf :: (o, a, b, c, d) -> (a, b, c, d) Source #
Ord o => Indexable (o, a, b, c, d, e) o (a, b, c, d, e) Source #
Instance details Defined in Data.Chatty.BST Methods indexOf :: (o, a, b, c, d, e) -> o Source # valueOf :: (o, a, b, c, d, e) -> (a, b, c, d, e) Source #

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

Typeclass for all BSTs that store the given Indexable

Methods

anyBstInsert :: i -> t i -> t i Source #

Insert into the tree

anyBstRemove :: o -> t i -> t i Source #

Remove from the tree

anyBstMax :: t i -> Maybe i Source #

Get the greatest element

anyBstMin :: t i -> Maybe i Source #

Get the least element

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

Lookup a given key

anyBstEmpty :: t i Source #

An empty tree

anyBstHead :: t i -> Maybe i Source #

The root of the tree

anyBstInorder :: t i -> [i] Source #

Traverse the tree in order

Instances

Instances details

Indexable i o v => AnyBST BST i o v Source #
Instance details Defined in Data.Chatty.BST Methods anyBstInsert :: i -> BST i -> BST i Source # anyBstRemove :: o -> BST i -> BST i Source # anyBstMax :: BST i -> Maybe i Source # anyBstMin :: BST i -> Maybe i Source # anyBstLookup :: o -> BST i -> Maybe v Source # anyBstEmpty :: BST i Source # anyBstHead :: BST i -> Maybe i Source # anyBstInorder :: BST i -> [i] Source #
Indexable i o v => AnyBST Focus i o v Source #
Instance details Defined in Data.Chatty.Focus Methods anyBstInsert :: i -> Focus i -> Focus i Source # anyBstRemove :: o -> Focus i -> Focus i Source # anyBstMax :: Focus i -> Maybe i Source # anyBstMin :: Focus i -> Maybe i Source # anyBstLookup :: o -> Focus i -> Maybe v Source # anyBstEmpty :: Focus i Source # anyBstHead :: Focus i -> Maybe i Source # anyBstInorder :: Focus i -> [i] Source #
Indexable i o v => AnyBST AVL i o v Source #
Instance details Defined in Data.Chatty.AVL Methods anyBstInsert :: i -> AVL i -> AVL i Source # anyBstRemove :: o -> AVL i -> AVL i Source # anyBstMax :: AVL i -> Maybe i Source # anyBstMin :: AVL i -> Maybe i Source # anyBstLookup :: o -> AVL i -> Maybe v Source # anyBstEmpty :: AVL i Source # anyBstHead :: AVL i -> Maybe i Source # anyBstInorder :: AVL i -> [i] Source #

data BST a Source #

An unbalanced binary search tree

Constructors

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

Instances

Instances details

Indexable i o v => AnyBST BST i o v Source #
Instance details Defined in Data.Chatty.BST Methods anyBstInsert :: i -> BST i -> BST i Source # anyBstRemove :: o -> BST i -> BST i Source # anyBstMax :: BST i -> Maybe i Source # anyBstMin :: BST i -> Maybe i Source # anyBstLookup :: o -> BST i -> Maybe v Source # anyBstEmpty :: BST i Source # anyBstHead :: BST i -> Maybe i Source # anyBstInorder :: BST i -> [i] Source #
None (BST a) Source #
Instance details Defined in Data.Chatty.BST Methods none :: BST a Source #

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

Insert into the BST

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

Remove from the BST

bstMax :: BST i -> Maybe i Source #

Get the greatest element

bstMin :: BST i -> Maybe i Source #

Get the least element

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

Lookup a given key

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

Lookup if a given key is contained

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

Return the tree's root

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

Traverse the tree in order