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 PlayerState PlayerId PlayerState

Indexable Currency CurrencyId Currency

Indexable CooldownId CooldownId CooldownId

Indexable ObjectState ObjectId ObjectState

Indexable Feature Feature Feature

Indexable EquipKey EquipKey EquipKey

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

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