antisplice-0.14.0.0: An engine for text-based dungeons.

Safe HaskellNone

Game.Antisplice.Utils.BST

Description

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

Synopsis

Documentation

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

Only instances of Indexable may be saved in a BST

Associated Types

type IndexOf i Source

type ValueOf i Source

Methods

indexOf :: i -> oSource

Extract the index

valueOf :: i -> vSource

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 whereSource

Typeclass for all BSTs that store the given Indexable

Methods

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

Insert into the tree

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

Remove from the tree

anyBstMax :: t i -> Maybe iSource

Get the greatest element

anyBstMin :: t i -> Maybe iSource

Get the least element

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

Lookup a given key

anyBstEmpty :: t iSource

An empty tree

anyBstHead :: t i -> Maybe iSource

The root of the tree

anyBstInorder :: t i -> [i]Source

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 Source

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 iSource

Insert into the BST

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

Remove from the BST

bstMax :: BST i -> Maybe iSource

Get the greatest element

bstMin :: BST i -> Maybe iSource

Get the least element

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

Lookup a given key

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

Return the tree's root

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

Traverse the tree in order