{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-}
{-
This module is part of Chatty.
Copyleft (c) 2014 Marvin Cohrs
All wrongs reversed. Sharing is an act of love, not crime.
Please share Chatty with everyone you like.
Chatty is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
Chatty is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with Chatty. If not, see <http://www.gnu.org/licenses/>.
-}
-- | Provides a typeclass for all binary search trees and an unbalanced implementation
module Data.Chatty.BST where
import Data.Chatty.None
-- | Only instances of Indexable may be saved in a BST
class Ord o => Indexable i o v | i -> o, i -> v where
-- | Extract the index
indexOf :: i -> o
-- | Extract the value
valueOf :: i -> v
instance Indexable Int Int Int where
indexOf = id
valueOf = id
instance Ord o => Indexable (o,a) o a where
indexOf = fst
valueOf = snd
instance Ord o => Indexable (o,a,b) o (a,b) where
indexOf (o,_,_) = o
valueOf (_,a,b) = (a,b)
instance Ord o => Indexable (o,a,b,c) o (a,b,c) where
indexOf (o,_,_,_) = o
valueOf (_,a,b,c) = (a,b,c)
instance Ord o => Indexable (o,a,b,c,d) o (a,b,c,d) where
indexOf (o,_,_,_,_) = o
valueOf (_,a,b,c,d) = (a,b,c,d)
instance Ord o => Indexable (o,a,b,c,d,e) o (a,b,c,d,e) where
indexOf (o,a,b,c,d,e) = o
valueOf (o,a,b,c,d,e) = (a,b,c,d,e)
-- | Typeclass for all BSTs that store the given Indexable
class Indexable i o v => AnyBST t i o v where
-- | Insert into the tree
anyBstInsert :: i -> t i -> t i
-- | Remove from the tree
anyBstRemove :: o -> t i -> t i
-- | Get the greatest element
anyBstMax :: t i -> Maybe i
-- | Get the least element
anyBstMin :: t i -> Maybe i
-- | Lookup a given key
anyBstLookup :: o -> t i -> Maybe v
-- | An empty tree
anyBstEmpty :: t i
-- | The root of the tree
anyBstHead :: t i -> Maybe i
-- | Traverse the tree in order
anyBstInorder :: t i -> [i]
instance Indexable i o v => AnyBST BST i o v where
anyBstInsert = bstInsert
anyBstRemove = bstRemove
anyBstMax = bstMax
anyBstMin = bstMin
anyBstLookup = bstLookup
anyBstEmpty = EmptyBST
anyBstHead = bstHead
anyBstInorder = bstInorder
instance None (BST a) where
none = EmptyBST
-- | An unbalanced binary search tree
data BST a = EmptyBST | BST a !(BST a) !(BST a)
-- | Insert into the BST
bstInsert :: Indexable i o v => i -> BST i -> BST i
bstInsert i EmptyBST = BST i EmptyBST EmptyBST
bstInsert i (BST a l r)
| indexOf i < indexOf a = BST a (bstInsert i l) r
| indexOf i > indexOf a = BST a l (bstInsert i r)
| otherwise = BST i l r
-- | Remove from the BST
bstRemove :: Indexable i o v => o -> BST i -> BST i
bstRemove o EmptyBST = EmptyBST
bstRemove o (BST a EmptyBST r) | indexOf a == o = r
bstRemove o (BST a l EmptyBST) | indexOf a == o = l
bstRemove o (BST a l r)
| indexOf a < o = BST a (bstRemove o l) r
| indexOf a > o = BST a l (bstRemove o r)
| otherwise = let (Just m) = bstMax l in BST m (bstRemove (indexOf m) l) r
-- | Get the greatest element
bstMax :: BST i -> Maybe i
bstMax EmptyBST = Nothing
bstMax (BST a _ EmptyBST) = Just a
bstMax (BST _ _ r) = bstMax r
-- | Get the least element
bstMin :: BST i -> Maybe i
bstMin EmptyBST = Nothing
bstMin (BST a EmptyBST _) = Just a
bstMin (BST _ l _) = bstMin l
-- | Lookup a given key
bstLookup :: Indexable i o v => o -> BST i -> Maybe v
bstLookup _ EmptyBST = Nothing
bstLookup o (BST a l r)
| o == indexOf a = Just $ valueOf a
| o < indexOf a = bstLookup o l
| o > indexOf a = bstLookup o r
-- | Return the tree's root
bstHead :: Indexable i o v => BST i -> Maybe i
bstHead EmptyBST = Nothing
bstHead (BST a _ _) = Just a
-- | Traverse the tree in order
bstInorder :: Indexable i o v => BST i -> [i]
bstInorder EmptyBST = []
bstInorder (BST a l r) = bstInorder l ++ [a] ++ bstInorder r