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

Indexable (Node a) NodeId (Node a)

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

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

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

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

Ord o => Indexable (o, a, b, c, d, e) o (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

Indexable i o v => AnyBST Focus i o v

Indexable i o v => AnyBST AVL i o v

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

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