Game.Antisplice.Utils.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

Associated Types

type IndexOf i

type ValueOf i

Methods

indexOf :: i -> o

Extract the index

valueOf :: i -> v

Extract the value

Instances

Indexable Int Int Int

Indexable ObjectState ObjectId ObjectState

Indexable (Node a) NodeId (Node a)

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

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

Instances

Indexable i o v => AnyBST BST 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

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