{-# OPTIONS_GHC -fglasgow-exts #-} ----------------------------------------------------------------------------- -- | -- Module : Data.Tree.AVL.Types -- Copyright : (c) Adrian Hey 2004,2005 -- License : BSD3 -- -- Maintainer : http://homepages.nildram.co.uk/~ahey/em.png -- Stability : stable -- Portability : portable -- -- AVL Tree data type definition and a few simple utility functions. ----------------------------------------------------------------------------- module Data.Tree.AVL.Types ( -- * Types. AVL(..), -- * Simple AVL related utilities. empty,isEmpty,isNonEmpty,singleton,pair,tryGetSingleton, ) where import Prelude -- so haddock finds the symbols there import Data.Typeable #if __GLASGOW_HASKELL__ > 604 import Data.Foldable import Data.Monoid #endif -- | AVL tree data type. -- -- The balance factor (BF) of an 'AVL' tree node is defined as the difference between the height of -- the left and right sub-trees. An 'AVL' tree is ALWAYS height balanced, such that |BF| <= 1. -- The functions in this library ("Data.Tree.AVL") are designed so that they never construct -- an unbalanced tree (well that's assuming they're not broken). The 'AVL' tree type defined here -- has the BF encoded the constructors. -- -- Some functions in this library return 'AVL' trees that are also \"flat\", which (in the context -- of this library) means that the sizes of left and right sub-trees differ by at most one and -- are also flat. Flat sorted trees should give slightly shorter searches than sorted trees which -- are merely height balanced. Whether or not flattening is worth the effort depends on the number -- of times the tree will be searched and the cost of element comparison. -- -- In cases where the tree elements are sorted, all the relevant 'AVL' functions follow the -- convention that the leftmost tree element is least and the rightmost tree element is -- the greatest. Bear this in mind when defining general comparison functions. It should -- also be noted that all functions in this library for sorted trees require that the tree -- does not contain multiple elements which are \"equal\" (according to whatever criterion -- has been used to sort the elements). -- -- It is important to be consistent about argument ordering when defining general purpose -- comparison functions (or selectors) for searching a sorted tree, such as .. -- -- @ -- myComp :: (k -> e -> Ordering) -- -- or.. -- myCComp :: (k -> e -> COrdering a) -- @ -- -- In these cases the first argument is the search key and the second argument is an element of -- the 'AVL' tree. For example.. -- -- @ -- key \`myCComp\` element -> Lt implies key < element, proceed down the left sub-tree -- key \`myCComp\` element -> Gt implies key > element, proceed down the right sub-tree -- @ -- -- This convention is same as that used by the overloaded 'compare' method from 'Ord' class. -- -- WARNING: The constructors of this data type are exported from this module but not from -- the top level 'AVL' wrapper ("Data.Tree.AVL"). Don't try to construct your own 'AVL' -- trees unless you're sure you know what your doing. If you end up creating and using -- 'AVL' trees that aren't you'll break most of the functions in this library. -- -- Controlling Strictness. -- -- The 'AVL' data type is declared as non-strict in all it's fields, -- but all the functions in this library behave as though it is strict in its -- recursive fields (left and right sub-trees). Strictness in the element field is -- controlled either by using the strict variants of functions (defined in this library -- where appropriate), or using strict variants of the combinators defined in "Data.COrdering", -- or using 'seq' etc. in your own code (in any combining comparisons you define, for example). -- -- A note about 'Eq' and 'Ord' class instances. -- -- For 'AVL' trees the defined instances of 'Ord' and 'Eq' are based on the lists that are produced using -- the 'Data.Tree.AVL.List.asListL' function (it could just as well have been 'Data.Tree.AVL.List.asListR', -- the choice is arbitrary but I can only chose one). This means that two trees which contain the same elements -- in the same order are equal regardless of detailed tree structure. The same principle has been applied to -- the instances of 'Read' and 'Show'. Unfortunately, this has the undesirable and non-intuitive effect -- of making \"equal\" trees potentially distinguishable using some functions (such as height). -- All such functions have been placed in the Data.Tree.AVL.Internals modules, which are not -- included in the main "Data.Tree.AVL" wrapper. For all \"normal\" functions (f) exported by "Data.Tree.AVL" -- it is safe to assume that if a and b are 'AVL' trees then (a == b) implies (f a == f b), provided the same -- is true for the tree elements. -- data AVL e = E -- ^ Empty Tree | N (AVL e) e (AVL e) -- ^ BF=-1 (right height > left height) | Z (AVL e) e (AVL e) -- ^ BF= 0 | P (AVL e) e (AVL e) -- ^ BF=+1 (left height > right height) -- A name for the AVL type constructor, fully qualified avlTyConName :: String avlTyConName = "Data.Tree.AVL.AVL" -- A Typeable1 instance instance Typeable1 AVL where typeOf1 _ = mkTyConApp (mkTyCon avlTyConName) [] #ifndef _GLASGOW_HASKELL_ -- A Typeable instance (not needed by ghc, but Haddock fails to document this instance) instance Typeable e => Typeable (AVL e) where typeOf = typeOfDefault #endif #if __GLASGOW_HASKELL__ > 604 instance Foldable AVL where foldMap _f E = mempty foldMap f (N l v r) = foldMap f l `mappend` f v `mappend` foldMap f r foldMap f (Z l v r) = foldMap f l `mappend` f v `mappend` foldMap f r foldMap f (P l v r) = foldMap f l `mappend` f v `mappend` foldMap f r #endif -- | The empty AVL tree. {-# INLINE empty #-} empty :: AVL e empty = E -- | Returns 'True' if an AVL tree is empty. -- -- Complexity: O(1) {-# INLINE isEmpty #-} isEmpty :: AVL e -> Bool isEmpty E = True isEmpty _ = False -- | Returns 'True' if an AVL tree is non-empty. -- -- Complexity: O(1) {-# INLINE isNonEmpty #-} isNonEmpty :: AVL e -> Bool isNonEmpty E = False isNonEmpty _ = True -- | Creates an AVL tree with just one element. -- -- Complexity: O(1) {-# INLINE singleton #-} singleton :: e -> AVL e singleton e = Z E e E -- | Create an AVL tree of two elements, occuring in same order as the arguments. {-# INLINE pair #-} pair :: e -> e -> AVL e pair e0 e1 = P (Z E e0 E) e1 E -- | If the AVL tree is a singleton (has only one element @e@) then this function returns @('Just' e)@. -- Otherwise it returns Nothing. -- -- Complexity: O(1) {-# INLINE tryGetSingleton #-} tryGetSingleton :: AVL e -> Maybe e tryGetSingleton (Z E e _) = Just e -- Right subtree must be E too, but no need to waste time checking tryGetSingleton _ = Nothing