-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Balanced binary trees using the AVL algorithm. -- -- A comprehensive and efficient implementation of AVL trees. The raw AVL -- API has been designed with efficiency and generality in mind, not -- elagance or safety. It contains all the stuff you really don't want to -- write yourself if you can avoid it. This library may be useful for -- rolling your own Sets, Maps, Sequences, Queues (for example). This -- package is no longer actively maintained and will be tagged as such as -- soon as Hackage has this feature. @package AvlTree @version 3.1 -- | This module defines the XInt type which is a specialised -- instance of Ord which allows the number of comparisons -- performed to be counted. This may be used evaluate various algorithms. -- The functions defined here are not exported by the main -- Data.Tree.AVL module. You need to import this module explicitly -- if you want to use any of them. module Data.Tree.AVL.Test.Counter -- | Basic data type. newtype XInt XInt :: Int -> XInt -- | Read the current comparison counter. getCount :: IO Int -- | Reset the comparison counter to zero. resetCount :: IO () instance Eq XInt instance Show XInt instance Read XInt instance Ord XInt -- | Many of the functions defined by this package make use of generalised -- comparison functions which return a variant of the Prelude -- Ordering data type: Data.COrdering.COrdering. These -- are refered to as "combining comparisons". (This is because they -- combine "equal" values in some manner defined by the user.) -- -- The idea is that using this simple mechanism you can define many -- practical and useful variations of tree (or general set) operations -- from a few generic primitives, something that would not be so easy -- using plain Ordering comparisons (overloaded or otherwise). -- -- Functions which involve searching a tree really only require a single -- argument function which takes the current tree element value as -- argument and returns an Ordering or -- Data.COrdering.COrdering to direct the next stage of the -- search down the left or right sub-trees (or stop at the current -- element). For documentation purposes, these functions are called -- "selectors" throughout this library. Typically a selector will be -- obtained by partially applying the appropriate combining comparison -- with the value or key being searched for. For example.. -- -- 
--   mySelector :: Int -> Ordering               Tree elements are Ints
--   or..
--   mySelector :: (key,val) -> COrdering val    Tree elements are (key,val) pairs
--
module Data.Tree.AVL -- | 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). -- -- The Eq and Ord instances. -- -- Begining with version 3.0 these are now derived, and hence are defined -- in terms of strict structural equality, rather than observational -- equivalence. The reason for this change is that the observational -- equivalence abstraction was technically breakable with the exposed -- API. But since this change, some functions which were previously -- considered unsafe have become safe to expose (those that measure tree -- height). data AVL e -- | Empty Tree E :: AVL e -- | BF=-1 (right height > left height) N :: (AVL e) -> e -> (AVL e) -> AVL e -- | BF= 0 Z :: (AVL e) -> e -> (AVL e) -> AVL e -- | BF=+1 (left height > right height) P :: (AVL e) -> e -> (AVL e) -> AVL e -- | The empty AVL tree. empty :: AVL e -- | Returns True if an AVL tree is empty. -- -- Complexity: O(1) isEmpty :: AVL e -> Bool -- | Returns True if an AVL tree is non-empty. -- -- Complexity: O(1) isNonEmpty :: AVL e -> Bool -- | Creates an AVL tree with just one element. -- -- Complexity: O(1) singleton :: e -> AVL e -- | Create an AVL tree of two elements, occuring in same order as the -- arguments. pair :: e -> e -> AVL 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) tryGetSingleton :: AVL e -> Maybe e -- | Counts the total number of elements in an AVL tree. -- -- 
--   size = addSize 0
--
-- -- Complexity: O(n) size :: AVL e -> Int -- | Adds the size of a tree to the first argument. This is just a -- convenience wrapper for fastAddSize. -- -- Complexity: O(n) addSize :: Int -> AVL e -> Int -- | Fast algorithm to calculate size. This avoids visiting about 50% of -- tree nodes by using fact that trees with small heights can only have -- particular shapes. So it's still O(n), but with substantial saving in -- constant factors. -- -- Complexity: O(n) fastAddSize :: Int# -> AVL e -> Int# -- | Returns the exact tree size in the form (Just n) if -- this is less than or equal to the input clip value. Returns -- Nothing of the size is greater than the clip value. -- This function exploits the same optimisation as fastAddSize. -- -- Complexity: O(min n c) where n is tree size and c is clip value. clipSize :: Int -> AVL e -> Maybe Int -- | Determine the height of an AVL tree. -- -- Complexity: O(log n) height :: AVL e -> Int# -- | Adds the height of a tree to the first argument. -- -- Complexity: O(log n) addHeight :: Int# -> AVL e -> Int# -- | A fast algorithm for comparing the heights of two trees. This -- algorithm avoids the need to compute the heights of both trees and -- should offer better performance if the trees differ significantly in -- height. But if you need the heights anyway it will be quicker to just -- evaluate them both and compare the results. -- -- Complexity: O(log n), where n is the size of the smaller of the two -- trees. compareHeight :: AVL a -> AVL b -> Ordering -- | Read the leftmost element from a non-empty tree. Raises an -- error if the tree is empty. If the tree is sorted this will return the -- least element. -- -- Complexity: O(log n) assertReadL :: AVL e -> e -- | Similar to assertReadL but returns Nothing if the tree -- is empty. -- -- Complexity: O(log n) tryReadL :: AVL e -> Maybe e -- | Read the rightmost element from a non-empty tree. Raises an -- error if the tree is empty. If the tree is sorted this will return the -- greatest element. -- -- Complexity: O(log n) assertReadR :: AVL e -> e -- | Similar to assertReadR but returns Nothing if the tree -- is empty. -- -- Complexity: O(log n) tryReadR :: AVL e -> Maybe e -- | General purpose function to perform a search of a sorted tree, using -- the supplied selector. This function raises a error if the search -- fails. -- -- Complexity: O(log n) genAssertRead :: AVL e -> (e -> COrdering a) -> a -- | General purpose function to perform a search of a sorted tree, using -- the supplied selector. This function is similar to -- genAssertRead, but returns Nothing if the search failed. -- -- Complexity: O(log n) genTryRead :: AVL e -> (e -> COrdering a) -> Maybe a -- | This version returns the result of the selector (without adding a -- Just wrapper) if the search succeeds, or Nothing if it -- fails. -- -- Complexity: O(log n) genTryReadMaybe :: AVL e -> (e -> COrdering (Maybe a)) -> Maybe a -- | General purpose function to perform a search of a sorted tree, using -- the supplied selector. This function is similar to -- genAssertRead, but returns a the default value (first argument) -- if the search fails. -- -- Complexity: O(log n) genDefaultRead :: a -> AVL e -> (e -> COrdering a) -> a -- | General purpose function to perform a search of a sorted tree, using -- the supplied selector. Returns True if matching element is found. -- -- Complexity: O(log n) genContains :: AVL e -> (e -> Ordering) -> Bool -- | Replace the left most element of a tree with the supplied new element. -- This function raises an error if applied to an empty tree. -- -- Complexity: O(log n) writeL :: e -> AVL e -> AVL e -- | Similar to writeL, but returns Nothing if applied to an -- empty tree. -- -- Complexity: O(log n) tryWriteL :: e -> AVL e -> Maybe (AVL e) -- | Replace the right most element of a tree with the supplied new -- element. This function raises an error if applied to an empty tree. -- -- Complexity: O(log n) writeR :: AVL e -> e -> AVL e -- | Similar to writeR, but returns Nothing if applied to an -- empty tree. -- -- Complexity: O(log n) tryWriteR :: AVL e -> e -> Maybe (AVL e) -- | A general purpose function to perform a search of a tree, using the -- supplied selector. If the search succeeds the found element is -- replaced by the value (e) of the (Eq e) -- constructor returned by the selector. If the search fails this -- function returns the original tree. -- -- Complexity: O(log n) genWrite :: (e -> COrdering e) -> AVL e -> AVL e -- | Functionally identical to genWrite, but returns an identical -- tree (one with all the nodes on the path duplicated) if the search -- fails. This should probably only be used if you know the search will -- succeed and will return an element which is different from that -- already present. -- -- Complexity: O(log n) genWriteFast :: (e -> COrdering e) -> AVL e -> AVL e -- | A general purpose function to perform a search of a tree, using the -- supplied selector. The found element is replaced by the value -- (e) of the (Eq e) constructor returned by the -- selector. This function returns Nothing if the search failed. -- -- Complexity: O(log n) genTryWrite :: (e -> COrdering e) -> AVL e -> Maybe (AVL e) -- | Similar to genWrite, but also returns the original tree if the -- search succeeds but the selector returns (Eq -- Nothing). (This version is intended to help reduce heap -- burn rate if it's likely that no modification of the value is needed.) -- -- Complexity: O(log n) genWriteMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> AVL e -- | Similar to genTryWrite, but also returns the original tree if -- the search succeeds but the selector returns (Eq -- Nothing). (This version is intended to help reduce heap -- burn rate if it's likely that no modification of the value is needed.) -- -- Complexity: O(log n) genTryWriteMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> Maybe (AVL e) -- | Push a new element in the leftmost position of an AVL tree. No -- comparison or searching is involved. -- -- Complexity: O(log n) pushL :: e -> AVL e -> AVL e -- | Push a new element in the rightmost position of an AVL tree. No -- comparison or searching is involved. -- -- Complexity: O(log n) pushR :: AVL e -> e -> AVL e -- | General push. This function searches the AVL tree using the supplied -- selector. If a matching element is found it's replaced by the value -- (e) returned in the (Eq e) constructor -- returned by the selector. If no match is found then the default -- element value is added at in the appropriate position in the tree. -- -- Note that for this to work properly requires that the selector behave -- as if it were comparing the (potentially) new default element with -- existing tree elements, even if it isn't. -- -- Note also that this function is non-strict in it's second -- argument (the default value which is inserted if the search fails or -- is discarded if the search succeeds). If you want to force evaluation, -- but only if it's actually incorprated in the tree, then use -- genPush' -- -- Complexity: O(log n) genPush :: (e -> COrdering e) -> e -> AVL e -> AVL e -- | Almost identical to genPush, but this version forces evaluation -- of the default new element (second argument) if no matching element is -- found. Note that it does not do this if a matching element is -- found, because in this case the default new element is discarded -- anyway. Note also that it does not force evaluation of any replacement -- value provided by the selector (if it returns Eq). (You have to do -- that yourself if that's what you want.) -- -- Complexity: O(log n) genPush' :: (e -> COrdering e) -> e -> AVL e -> AVL e -- | Similar to genPush, but returns the original tree if the -- combining comparison returns (Eq Nothing). So -- this function can be used reduce heap burn rate by avoiding -- duplication of nodes on the insertion path. But it may also be -- marginally slower otherwise. -- -- Note that this function is non-strict in it's second argument -- (the default value which is inserted in the search fails or is -- discarded if the search succeeds). If you want to force evaluation, -- but only if it's actually incorprated in the tree, then use -- genPushMaybe' -- -- Complexity: O(log n) genPushMaybe :: (e -> COrdering (Maybe e)) -> e -> AVL e -> AVL e -- | Almost identical to genPushMaybe, but this version forces -- evaluation of the default new element (second argument) if no matching -- element is found. Note that it does not do this if a matching -- element is found, because in this case the default new element is -- discarded anyway. -- -- Complexity: O(log n) genPushMaybe' :: (e -> COrdering (Maybe e)) -> e -> AVL e -> AVL e -- | Delete the left-most element of an AVL tree. If the tree is sorted -- this will be the least element. This function returns an empty tree if -- it's argument is an empty tree. -- -- Complexity: O(log n) delL :: AVL e -> AVL e -- | Delete the right-most element of an AVL tree. If the tree is sorted -- this will be the greatest element. This function returns an empty tree -- if it's argument is an empty tree. -- -- Complexity: O(log n) delR :: AVL e -> AVL e -- | Delete the left-most element of a non-empty AVL tree. If the -- tree is sorted this will be the least element. This function raises an -- error if it's argument is an empty tree. -- -- Complexity: O(log n) assertDelL :: AVL e -> AVL e -- | Delete the right-most element of a non-empty AVL tree. If the -- tree is sorted this will be the greatest element. This function raises -- an error if it's argument is an empty tree. -- -- Complexity: O(log n) assertDelR :: AVL e -> AVL e -- | Try to delete the left-most element of a non-empty AVL tree. If -- the tree is sorted this will be the least element. This function -- returns Nothing if it's argument is an empty tree. -- -- Complexity: O(log n) tryDelL :: AVL e -> Maybe (AVL e) -- | Try to delete the right-most element of a non-empty AVL tree. -- If the tree is sorted this will be the greatest element. This function -- returns Nothing if it's argument is an empty tree. -- -- Complexity: O(log n) tryDelR :: AVL e -> Maybe (AVL e) -- | General purpose function for deletion of elements from a sorted AVL -- tree. If a matching element is not found then this function returns -- the original tree. -- -- Complexity: O(log n) genDel :: (e -> Ordering) -> AVL e -> AVL e -- | Functionally identical to genDel, but returns an identical tree -- (one with all the nodes on the path duplicated) if the search fails. -- This should probably only be used if you know the search will succeed. -- -- Complexity: O(log n) genDelFast :: (e -> Ordering) -> AVL e -> AVL e -- | This version only deletes the element if the supplied selector returns -- (Eq True). If it returns (Eq -- False) or if no matching element is found then this -- function returns the original tree. -- -- Complexity: O(log n) genDelIf :: (e -> COrdering Bool) -> AVL e -> AVL e -- | This version only deletes the element if the supplied selector returns -- (Eq Nothing). If it returns (Eq -- (Just e)) then the matching element is replaced by e. If -- no matching element is found then this function returns the original -- tree. -- -- Complexity: O(log n) genDelMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> AVL e -- | Pop the left-most element from a non-empty AVL tree, returning the -- popped element and the modified AVL tree. If the tree is sorted this -- will be the least element. This function raises an error if it's -- argument is an empty tree. -- -- Complexity: O(log n) assertPopL :: AVL e -> (e, AVL e) -- | Pop the right-most element from a non-empty AVL tree, returning the -- popped element and the modified AVL tree. If the tree is sorted this -- will be the greatest element. This function raises an error if it's -- argument is an empty tree. -- -- Complexity: O(log n) assertPopR :: AVL e -> (AVL e, e) -- | Same as assertPopL, except this version returns Nothing -- if it's argument is an empty tree. -- -- Complexity: O(log n) tryPopL :: AVL e -> Maybe (e, AVL e) -- | Same as assertPopR, except this version returns Nothing -- if it's argument is an empty tree. -- -- Complexity: O(log n) tryPopR :: AVL e -> Maybe (AVL e, e) -- | General purpose function for popping elements from a sorted AVL tree. -- An error is raised if a matching element is not found. The pair -- returned by this function consists of the popped value and the -- modified tree. -- -- Complexity: O(log n) genAssertPop :: (e -> COrdering a) -> AVL e -> (a, AVL e) -- | Similar to genPop, but this function returns Nothing -- if the search fails. -- -- Complexity: O(log n) genTryPop :: (e -> COrdering a) -> AVL e -> Maybe (a, AVL e) -- | In this case the selector returns two values if a search succeeds. If -- the second is (Just e) then the new value (e) -- is substituted in the same place in the tree. If the second is -- Nothing then the corresponding tree element is deleted. This -- function raises an error if the search fails. -- -- Complexity: O(log n) genAssertPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> (a, AVL e) -- | Similar to genAssertPopMaybe, but returns Nothing if the -- search fails. -- -- Complexity: O(log n) genTryPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> Maybe (a, AVL e) -- | A simpler version of genAssertPopMaybe. The corresponding -- element is deleted if the second value returned by the selector is -- True. If it's False, the original tree is returned. This -- function raises an error if the search fails. -- -- Complexity: O(log n) genAssertPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> (a, AVL e) -- | Similar to genPopIf, but returns Nothing if the search -- fails. -- -- Complexity: O(log n) genTryPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> Maybe (a, AVL e) -- | List AVL tree contents in left to right order. The resulting list in -- ascending order if the tree is sorted. -- -- Complexity: O(n) asListL :: AVL e -> [e] -- | Join the AVL tree contents to an existing list in left to right order. -- This is a ++ free function which behaves as if defined thusly.. -- -- 
--   avl `toListL` as = (asListL avl) ++ as
--
-- -- Complexity: O(n) toListL :: AVL e -> [e] -> [e] -- | List AVL tree contents in right to left order. The resulting list in -- descending order if the tree is sorted. -- -- Complexity: O(n) asListR :: AVL e -> [e] -- | Join the AVL tree contents to an existing list in right to left order. -- This is a ++ free function which behaves as if defined thusly.. -- -- 
--   avl `toListR` as = (asListR avl) ++ as
--
-- -- Complexity: O(n) toListR :: AVL e -> [e] -> [e] -- | Convert a list of known length into an AVL tree, such that the head of -- the list becomes the leftmost tree element. The resulting tree is flat -- (and also sorted if the supplied list is sorted in ascending order). -- -- If the actual length of the list is not the same as the supplied -- length then an error will be raised. -- -- Complexity: O(n) asTreeLenL :: Int -> [e] -> AVL e -- | As asTreeLenL, except the length of the list is calculated -- internally, not supplied as an argument. -- -- Complexity: O(n) asTreeL :: [e] -> AVL e -- | Convert a list of known length into an AVL tree, such that the head of -- the list becomes the rightmost tree element. The resulting tree is -- flat (and also sorted if the supplied list is sorted in descending -- order). -- -- If the actual length of the list is not the same as the supplied -- length then an error will be raised. -- -- Complexity: O(n) asTreeLenR :: Int -> [e] -> AVL e -- | As asTreeLenR, except the length of the list is calculated -- internally, not supplied as an argument. -- -- Complexity: O(n) asTreeR :: [e] -> AVL e -- | Invokes genPushList on the empty AVL tree. -- -- Complexity: O(n.(log n)) genAsTree :: (e -> e -> COrdering e) -> [e] -> AVL e -- | Push the elements of an unsorted List in a sorted AVL tree using the -- supplied combining comparison. -- -- Complexity: O(n.(log (m+n))) where n is the list length, m is the tree -- size. genPushList :: (e -> e -> COrdering e) -> AVL e -> [e] -> AVL e -- | Reverse an AVL tree (swaps and reverses left and right sub-trees). The -- resulting tree is the mirror image of the original. -- -- Complexity: O(n) reverseAVL :: AVL e -> AVL e -- | Apply a function to every element in an AVL tree. This function -- preserves the tree shape. There is also a strict version of this -- function (mapAVL'). -- -- N.B. If the tree is sorted the result of this operation will only be -- sorted if the applied function preserves ordering (for some suitable -- ordering definition). -- -- Complexity: O(n) mapAVL :: (a -> b) -> AVL a -> AVL b -- | Similar to mapAVL, but the supplied function is applied -- strictly. -- -- Complexity: O(n) mapAVL' :: (a -> b) -> AVL a -> AVL b -- | The AVL equivalent of Data.List.mapAccumL on lists. It -- behaves like a combination of mapAVL and foldlAVL. It -- applies a function to each element of a tree, passing an accumulating -- parameter from left to right, and returning a final value of this -- accumulator together with the new tree. -- -- Using this version with a function that is strict in it's first -- argument will result in O(n) stack use. See mapAccumLAVL' for a -- strict version. -- -- Complexity: O(n) mapAccumLAVL :: (z -> a -> (z, b)) -> z -> AVL a -> (z, AVL b) -- | The AVL equivalent of Data.List.mapAccumR on lists. It -- behaves like a combination of mapAVL and foldrAVL. It -- applies a function to each element of a tree, passing an accumulating -- parameter from right to left, and returning a final value of this -- accumulator together with the new tree. -- -- Using this version with a function that is strict in it's first -- argument will result in O(n) stack use. See mapAccumRAVL' for a -- strict version. -- -- Complexity: O(n) mapAccumRAVL :: (z -> a -> (z, b)) -> z -> AVL a -> (z, AVL b) -- | This is a strict version of mapAccumLAVL, which is useful for -- functions which are strict in their first argument. The advantage of -- this version is that it reduces the stack use from the O(n) that the -- lazy version gives (when used with strict functions) to O(log n). -- -- Complexity: O(n) mapAccumLAVL' :: (z -> a -> (z, b)) -> z -> AVL a -> (z, AVL b) -- | This is a strict version of mapAccumRAVL, which is useful for -- functions which are strict in their first argument. The advantage of -- this version is that it reduces the stack use from the O(n) that the -- lazy version gives (when used with strict functions) to O(log n). -- -- Complexity: O(n) mapAccumRAVL' :: (z -> a -> (z, b)) -> z -> AVL a -> (z, AVL b) -- | Glasgow Haskell only. Similar to mapAccumLAVL' but uses an -- unboxed pair in the accumulating function. -- -- Complexity: O(n) mapAccumLAVL'' :: (z -> a -> (# z, b #)) -> z -> AVL a -> (z, AVL b) -- | Glasgow Haskell only. Similar to mapAccumRAVL' but uses an -- unboxed pair in the accumulating function. -- -- Complexity: O(n) mapAccumRAVL'' :: (z -> a -> (# z, b #)) -> z -> AVL a -> (z, AVL b) traverseAVL :: (Applicative f) => (a -> f b) -> AVL a -> f (AVL b) -- | Construct a flat AVL tree of size n (n>=0), where all elements are -- identical. -- -- Complexity: O(log n) replicateAVL :: Int -> e -> AVL e -- | Remove all AVL tree elements which do not satisfy the supplied -- predicate. Element ordering is preserved. -- -- Complexity: O(n) filterAVL :: (e -> Bool) -> AVL e -> AVL e -- | Remove all AVL tree elements for which the supplied function returns -- Nothing. Element ordering is preserved. -- -- Complexity: O(n) mapMaybeAVL :: (a -> Maybe b) -> AVL a -> AVL b -- | Remove all AVL tree elements which do not satisfy the supplied -- predicate. Element ordering is preserved. The resulting tree is flat. -- See filterAVL for an alternative implementation which is -- probably more efficient. -- -- Complexity: O(n) filterViaList :: (e -> Bool) -> AVL e -> AVL e -- | Remove all AVL tree elements for which the supplied function returns -- Nothing. Element ordering is preserved. The resulting tree is -- flat. See mapMaybeAVL for an alternative implementation which -- is probably more efficient. -- -- Complexity: O(n) mapMaybeViaList :: (a -> Maybe b) -> AVL a -> AVL b -- | Partition an AVL tree using the supplied predicate. The first AVL tree -- in the resulting pair contains all elements for which the predicate is -- True, the second contains all those for which the predicate is False. -- Element ordering is preserved. Both of the resulting trees are flat. -- -- Complexity: O(n) partitionAVL :: (e -> Bool) -> AVL e -> (AVL e, AVL e) -- | The AVL equivalent of foldr on lists. This is a the lazy -- version (as lazy as the folding function anyway). Using this version -- with a function that is strict in it's second argument will result in -- O(n) stack use. See foldrAVL' for a strict version. -- -- It behaves as if defined.. -- -- 
--   foldrAVL f a avl = foldr f a (asListL avl)
--
-- -- For example, the asListL function could be defined.. -- -- 
--   asListL = foldrAVL (:) []
--
-- -- Complexity: O(n) foldrAVL :: (e -> a -> a) -> a -> AVL e -> a -- | The strict version of foldrAVL, which is useful for functions -- which are strict in their second argument. The advantage of this -- version is that it reduces the stack use from the O(n) that the lazy -- version gives (when used with strict functions) to O(log n). -- -- Complexity: O(n) foldrAVL' :: (e -> a -> a) -> a -> AVL e -> a -- | The AVL equivalent of foldr1 on lists. This is a the lazy -- version (as lazy as the folding function anyway). Using this version -- with a function that is strict in it's second argument will result in -- O(n) stack use. See foldr1AVL' for a strict version. -- -- 
--   foldr1AVL f avl = foldr1 f (asListL avl)
--
-- -- This function raises an error if the tree is empty. -- -- Complexity: O(n) foldr1AVL :: (e -> e -> e) -> AVL e -> e -- | The strict version of foldr1AVL, which is useful for functions -- which are strict in their second argument. The advantage of this -- version is that it reduces the stack use from the O(n) that the lazy -- version gives (when used with strict functions) to O(log n). -- -- Complexity: O(n) foldr1AVL' :: (e -> e -> e) -> AVL e -> e -- | This fold is a hybrid between foldrAVL and foldr1AVL. As -- with foldr1AVL, it requires a non-empty tree, but instead of -- treating the rightmost element as an initial value, it applies a -- function to it (second function argument) and uses the result instead. -- This allows a more flexible type for the main folding function (same -- type as that used by foldrAVL). As with foldrAVL and -- foldr1AVL, this function is lazy, so it's best not to use it -- with functions that are strict in their second argument. See -- foldr2AVL' for a strict version. -- -- Complexity: O(n) foldr2AVL :: (e -> a -> a) -> (e -> a) -> AVL e -> a -- | The strict version of foldr2AVL, which is useful for functions -- which are strict in their second argument. The advantage of this -- version is that it reduces the stack use from the O(n) that the lazy -- version gives (when used with strict functions) to O(log n). -- -- Complexity: O(n) foldr2AVL' :: (e -> a -> a) -> (e -> a) -> AVL e -> a -- | The AVL equivalent of foldl on lists. This is a the lazy -- version (as lazy as the folding function anyway). Using this version -- with a function that is strict in it's first argument will result in -- O(n) stack use. See foldlAVL' for a strict version. -- -- 
--   foldlAVL f a avl = foldl f a (asListL avl)
--
-- -- For example, the asListR function could be defined.. -- -- 
--   asListR = foldlAVL (flip (:)) []
--
-- -- Complexity: O(n) foldlAVL :: (a -> e -> a) -> a -> AVL e -> a -- | The strict version of foldlAVL, which is useful for functions -- which are strict in their first argument. The advantage of this -- version is that it reduces the stack use from the O(n) that the lazy -- version gives (when used with strict functions) to O(log n). -- -- Complexity: O(n) foldlAVL' :: (a -> e -> a) -> a -> AVL e -> a -- | The AVL equivalent of foldl1 on lists. This is a the lazy -- version (as lazy as the folding function anyway). Using this version -- with a function that is strict in it's first argument will result in -- O(n) stack use. See foldl1AVL' for a strict version. -- -- 
--   foldl1AVL f avl = foldl1 f (asListL avl)
--
-- -- This function raises an error if the tree is empty. -- -- Complexity: O(n) foldl1AVL :: (e -> e -> e) -> AVL e -> e -- | The strict version of foldl1AVL, which is useful for functions -- which are strict in their first argument. The advantage of this -- version is that it reduces the stack use from the O(n) that the lazy -- version gives (when used with strict functions) to O(log n). -- -- Complexity: O(n) foldl1AVL' :: (e -> e -> e) -> AVL e -> e -- | This fold is a hybrid between foldlAVL and foldl1AVL. As -- with foldl1AVL, it requires a non-empty tree, but instead of -- treating the leftmost element as an initial value, it applies a -- function to it (second function argument) and uses the result instead. -- This allows a more flexible type for the main folding function (same -- type as that used by foldlAVL). As with foldlAVL and -- foldl1AVL, this function is lazy, so it's best not to use it -- with functions that are strict in their first argument. See -- foldl2AVL' for a strict version. -- -- Complexity: O(n) foldl2AVL :: (a -> e -> a) -> (e -> a) -> AVL e -> a -- | The strict version of foldl2AVL, which is useful for functions -- which are strict in their first argument. The advantage of this -- version is that it reduces the stack use from the O(n) that the lazy -- version gives (when used with strict functions) to O(log n). -- -- Complexity: O(n) foldl2AVL' :: (a -> e -> a) -> (e -> a) -> AVL e -> a -- | This is a specialised version of foldrAVL' for use with an -- unboxed Int accumulator (with GHC). Defaults to boxed Int for -- other Haskells. -- -- Complexity: O(n) foldrAVL_UINT :: (e -> Int# -> Int#) -> Int# -> AVL e -> Int# -- | Flatten an AVL tree, preserving the ordering of the tree elements. -- -- Complexity: O(n) flatten :: AVL e -> AVL e -- | Similar to flatten, but the tree elements are reversed. This -- function has higher constant factor overhead than reverseAVL. -- -- Complexity: O(n) flatReverse :: AVL e -> AVL e -- | Similar to mapAVL, but the resulting tree is flat. This -- function has higher constant factor overhead than mapAVL. -- -- Complexity: O(n) flatMap :: (a -> b) -> AVL a -> AVL b -- | Same as flatMap, but the supplied function is applied strictly. -- -- Complexity: O(n) flatMap' :: (a -> b) -> AVL a -> AVL b -- | Join two AVL trees. This is the AVL equivalent of (++). -- -- 
--   asListL (l `join` r) = asListL l ++ asListL r
--
-- -- Complexity: O(log n), where n is the size of the larger of the two -- trees. join :: AVL e -> AVL e -> AVL e -- | Concatenate a finite list of AVL trees. During construction of -- the resulting tree the input list is consumed lazily, but it will be -- consumed entirely before the result is returned. -- -- 
--   asListL (concatAVL avls) = concatMap asListL avls
--
-- -- Complexity: Umm..Dunno. Uses a divide and conquer approach to splice -- adjacent pairs of trees in the list recursively, until only one tree -- remains. The complexity of each splice is proportional to the -- difference in tree heights. concatAVL :: [AVL e] -> AVL e -- | Similar to concatAVL, except the resulting tree is flat. This -- function evaluates the entire list of trees before constructing the -- result. -- -- Complexity: O(n), where n is the total number of elements in the -- resulting tree. flatConcat :: [AVL e] -> AVL e -- | Split an AVL tree from the Left. The Int argument n (n >= 0) -- specifies the split point. This function raises an error if n is -- negative. -- -- If the tree size is greater than n the result is (Right (l,r)) where l -- contains the leftmost n elements and r contains the remaining -- rightmost elements (r will be non-empty). -- -- If the tree size is less than or equal to n then the result is (Left -- s), where s is tree size. -- -- An empty tree will always yield a result of (Left 0). -- -- Complexity: O(n) splitAtL :: Int -> AVL e -> Either Int (AVL e, AVL e) -- | Split an AVL tree from the Right. The Int argument n (n >= -- 0) specifies the split point. This function raises an error if n is -- negative. -- -- If the tree size is greater than n the result is (Right (l,r)) where r -- contains the rightmost n elements and l contains the remaining -- leftmost elements (l will be non-empty). -- -- If the tree size is less than or equal to n then the result is (Left -- s), where s is tree size. -- -- An empty tree will always yield a result of (Left 0). -- -- Complexity: O(n) splitAtR :: Int -> AVL e -> Either Int (AVL e, AVL e) -- | This is a simplified version of splitAtL which does not return -- the remaining tree. The Int argument n (n >= 0) specifies -- the number of elements to take (from the left). This function raises -- an error if n is negative. -- -- If the tree size is greater than n the result is (Right l) where l -- contains the leftmost n elements. -- -- If the tree size is less than or equal to n then the result is (Left -- s), where s is tree size. -- -- An empty tree will always yield a result of (Left 0). -- -- Complexity: O(n) takeL :: Int -> AVL e -> Either Int (AVL e) -- | This is a simplified version of splitAtR which does not return -- the remaining tree. The Int argument n (n >= 0) specifies -- the number of elements to take (from the right). This function raises -- an error if n is negative. -- -- If the tree size is greater than n the result is (Right r) where r -- contains the rightmost n elements. -- -- If the tree size is less than or equal to n then the result is (Left -- s), where s is tree size. -- -- An empty tree will always yield a result of (Left 0). -- -- Complexity: O(n) takeR :: Int -> AVL e -> Either Int (AVL e) -- | This is a simplified version of splitAtL which returns the -- remaining tree only (rightmost elements). This function raises an -- error if n is negative. -- -- If the tree size is greater than n the result is (Right r) where r -- contains the remaining elements (r will be non-empty). -- -- If the tree size is less than or equal to n then the result is (Left -- s), where s is tree size. -- -- An empty tree will always yield a result of (Left 0). -- -- Complexity: O(n) dropL :: Int -> AVL e -> Either Int (AVL e) -- | This is a simplified version of splitAtR which returns the -- remaining tree only (leftmost elements). This function raises an error -- if n is negative. -- -- If the tree size is greater than n the result is (Right l) where l -- contains the remaining elements (l will be non-empty). -- -- If the tree size is less than or equal to n then the result is (Left -- s), where s is tree size. -- -- An empty tree will always yield a result of (Left 0). -- -- Complexity: O(n) dropR :: Int -> AVL e -> Either Int (AVL e) -- | Rotate an AVL tree one place left. This function pops the leftmost -- element and pushes into the rightmost position. An empty tree yields -- an empty tree. -- -- Complexity: O(log n) rotateL :: AVL e -> AVL e -- | Rotate an AVL tree one place right. This function pops the rightmost -- element and pushes into the leftmost position. An empty tree yields an -- empty tree. -- -- Complexity: O(log n) rotateR :: AVL e -> AVL e -- | Similar to rotateL, but returns the rotated element. This -- function raises an error if applied to an empty tree. -- -- Complexity: O(log n) popRotateL :: AVL e -> (e, AVL e) -- | Similar to rotateR, but returns the rotated element. This -- function raises an error if applied to an empty tree. -- -- Complexity: O(log n) popRotateR :: AVL e -> (AVL e, e) -- | Rotate an AVL tree left by n places. If s is the size of the tree then -- ordinarily n should be in the range [0..s-1]. However, this function -- will deliver a correct result for any n (n<0 or n>=s), the -- actual rotation being given by (n `mod` s) in such cases. The result -- of rotating an empty tree is an empty tree. -- -- Complexity: O(n) rotateByL :: AVL e -> Int -> AVL e -- | Rotate an AVL tree right by n places. If s is the size of the tree -- then ordinarily n should be in the range [0..s-1]. However, this -- function will deliver a correct result for any n (n<0 or n>=s), -- the actual rotation being given by (n `mod` s) in such cases. The -- result of rotating an empty tree is an empty tree. -- -- Complexity: O(n) rotateByR :: AVL e -> Int -> AVL e -- | Span an AVL tree from the left, using the supplied predicate. This -- function returns a pair of trees (l,r), where l contains the leftmost -- consecutive elements which satisfy the predicate. The leftmost element -- of r (if any) is the first to fail the predicate. Either of the -- resulting trees may be empty. Element ordering is preserved. -- -- Complexity: O(n), where n is the size of l. spanL :: (e -> Bool) -> AVL e -> (AVL e, AVL e) -- | Span an AVL tree from the right, using the supplied predicate. This -- function returns a pair of trees (l,r), where r contains the rightmost -- consecutive elements which satisfy the predicate. The rightmost -- element of l (if any) is the first to fail the predicate. Either of -- the resulting trees may be empty. Element ordering is preserved. -- -- Complexity: O(n), where n is the size of r. spanR :: (e -> Bool) -> AVL e -> (AVL e, AVL e) -- | This is a simplified version of spanL which does not return the -- remaining tree The result is the leftmost consecutive sequence of -- elements which satisfy the supplied predicate (which may be empty). -- -- Complexity: O(n), where n is the size of the result. takeWhileL :: (e -> Bool) -> AVL e -> AVL e -- | This is a simplified version of spanL which does not return the -- tree containing the elements which satisfy the supplied predicate. The -- result is a tree whose leftmost element is the first to fail the -- predicate, starting from the left (which may be empty). -- -- Complexity: O(n), where n is the number of elements dropped. dropWhileL :: (e -> Bool) -> AVL e -> AVL e -- | This is a simplified version of spanR which does not return the -- remaining tree The result is the rightmost consecutive sequence of -- elements which satisfy the supplied predicate (which may be empty). -- -- Complexity: O(n), where n is the size of the result. takeWhileR :: (e -> Bool) -> AVL e -> AVL e -- | This is a simplified version of spanR which does not return the -- tree containing the elements which satisfy the supplied predicate. The -- result is a tree whose rightmost element is the first to fail the -- predicate, starting from the right (which may be empty). -- -- Complexity: O(n), where n is the number of elements dropped. dropWhileR :: (e -> Bool) -> AVL e -> AVL e -- | Divide a sorted AVL tree into left and right sorted trees (l,r), such -- that l contains all the elements less than or equal to according to -- the supplied selector and r contains all the elements greater than -- according to the supplied selector. -- -- Complexity: O(log n) genForkL :: (e -> Ordering) -> AVL e -> (AVL e, AVL e) -- | Divide a sorted AVL tree into left and right sorted trees (l,r), such -- that l contains all the elements less than supplied selector and r -- contains all the elements greater than or equal to the supplied -- selector. -- -- Complexity: O(log n) genForkR :: (e -> Ordering) -> AVL e -> (AVL e, AVL e) -- | Similar to genForkL and genForkR, but returns any equal -- element found (instead of incorporating it into the left or right tree -- results respectively). -- -- Complexity: O(log n) genFork :: (e -> COrdering a) -> AVL e -> (AVL e, Maybe a, AVL e) -- | This is a simplified version of genForkL which returns a sorted -- tree containing only those elements which are less than or equal to -- according to the supplied selector. This function also has the synonym -- genDropGT. -- -- Complexity: O(log n) genTakeLE :: (e -> Ordering) -> AVL e -> AVL e -- | A synonym for genTakeLE. -- -- Complexity: O(log n) genDropGT :: (e -> Ordering) -> AVL e -> AVL e -- | This is a simplified version of genForkR which returns a sorted -- tree containing only those elements which are less than according to -- the supplied selector. This function also has the synonym -- genDropGE. -- -- Complexity: O(log n) genTakeLT :: (e -> Ordering) -> AVL e -> AVL e -- | A synonym for genTakeLT. -- -- Complexity: O(log n) genDropGE :: (e -> Ordering) -> AVL e -> AVL e -- | This is a simplified version of genForkL which returns a sorted -- tree containing only those elements which are greater according to the -- supplied selector. This function also has the synonym -- genDropLE. -- -- Complexity: O(log n) genTakeGT :: (e -> Ordering) -> AVL e -> AVL e -- | A synonym for genTakeGT. -- -- Complexity: O(log n) genDropLE :: (e -> Ordering) -> AVL e -> AVL e -- | This is a simplified version of genForkR which returns a sorted -- tree containing only those elements which are greater or equal to -- according to the supplied selector. This function also has the synonym -- genDropLT. -- -- Complexity: O(log n) genTakeGE :: (e -> Ordering) -> AVL e -> AVL e -- | A synonym for genTakeGE. -- -- Complexity: O(log n) genDropLT :: (e -> Ordering) -> AVL e -> AVL e -- | Uses the supplied combining comparison to evaluate the union of two -- sets represented as sorted AVL trees. Whenever the combining -- comparison is applied, the first comparison argument is an element of -- the first tree and the second comparison argument is an element of the -- second tree. -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. (Faster than Hedge union from Data.Set at any rate). genUnion :: (e -> e -> COrdering e) -> AVL e -> AVL e -> AVL e -- | Similar to genUnion, but the resulting tree does not include -- elements in cases where the supplied combining comparison returns -- (Eq Nothing). -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genUnionMaybe :: (e -> e -> COrdering (Maybe e)) -> AVL e -> AVL e -> AVL e -- | Uses the supplied combining comparison to evaluate the union of all -- sets in a list of sets represented as sorted AVL trees. Behaves as if -- defined.. -- -- 
--   genUnions ccmp avls = foldl' (genUnion ccmp) empty avls
--
genUnions :: (e -> e -> COrdering e) -> [AVL e] -> AVL e -- | Uses the supplied comparison to evaluate the difference between two -- sets represented as sorted AVL trees. The expression.. -- -- 
--   genDifference cmp setA setB
--
-- -- .. is a set containing all those elements of setA which do -- not appear in setB. -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genDifference :: (a -> b -> Ordering) -> AVL a -> AVL b -> AVL a -- | Similar to genDifference, but the resulting tree also includes -- those elements a' for which the combining comparison returns (Eq -- (Just a')). -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genDifferenceMaybe :: (a -> b -> COrdering (Maybe a)) -> AVL a -> AVL b -> AVL a -- | The symmetric difference is the set of elements which occur in one set -- or the other but not both. -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genSymDifference :: (e -> e -> Ordering) -> AVL e -> AVL e -> AVL e -- | Uses the supplied combining comparison to evaluate the intersection of -- two sets represented as sorted AVL trees. -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genIntersection :: (a -> b -> COrdering c) -> AVL a -> AVL b -> AVL c -- | Similar to genIntersection, but the resulting tree does not -- include elements in cases where the supplied combining comparison -- returns (Eq Nothing). -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genIntersectionMaybe :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> AVL c -- | Similar to genIntersection, but prepends the result to the -- supplied list in left to right order. This is a (++) free function -- which behaves as if defined: -- -- 
--   genIntersectionToListL c setA setB cs = asListL (genIntersection c setA setB) ++ cs
--
-- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genIntersectionToListL :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c] -> [c] -- | Applies genIntersectionToListL to the empty list. -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genIntersectionAsListL :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c] -- | Similar to genIntersectionToListL, but the result does not -- include elements in cases where the supplied combining comparison -- returns (Eq Nothing). -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genIntersectionMaybeToListL :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c] -> [c] -- | Applies genIntersectionMaybeToListL to the empty list. -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genIntersectionMaybeAsListL :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c] -- | Uses the supplied comparison to test whether the first set is a subset -- of the second, both sets being represented as sorted AVL trees. This -- function returns True if any of the following conditions hold.. -- -- -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genIsSubsetOf :: (a -> b -> Ordering) -> AVL a -> AVL b -> Bool -- | Similar to genIsSubsetOf, but also requires that the supplied -- combining comparison returns (Eq True) for matching -- elements. -- -- Complexity: Not sure, but I'd appreciate it if someone could figure it -- out. genIsSubsetOfBy :: (a -> b -> COrdering Bool) -> AVL a -> AVL b -> Bool -- | Abstract data type for a successfully opened AVL tree. All ZAVL's are -- non-empty! A ZAVL can be tought of as a functional pointer to an AVL -- tree element. data ZAVL e -- | Abstract data type for an unsuccessfully opened AVL tree. A PAVL can -- be thought of as a functional pointer to the gap where the expected -- element should be (but isn't). You can fill this gap using the -- fill function, or fill and close at the same time using the -- fillClose function. data PAVL e -- | Opens a non-empty AVL tree at the leftmost element. This function -- raises an error if the tree is empty. -- -- Complexity: O(log n) assertOpenL :: AVL e -> ZAVL e -- | Opens a non-empty AVL tree at the rightmost element. This function -- raises an error if the tree is empty. -- -- Complexity: O(log n) assertOpenR :: AVL e -> ZAVL e -- | Attempts to open a non-empty AVL tree at the leftmost element. This -- function returns Nothing if the tree is empty. -- -- Complexity: O(log n) tryOpenL :: AVL e -> Maybe (ZAVL e) -- | Attempts to open a non-empty AVL tree at the rightmost element. This -- function returns Nothing if the tree is empty. -- -- Complexity: O(log n) tryOpenR :: AVL e -> Maybe (ZAVL e) -- | Opens a sorted AVL tree at the element given by the supplied selector. -- This function raises an error if the tree does not contain such an -- element. -- -- Complexity: O(log n) genAssertOpen :: (e -> Ordering) -> AVL e -> ZAVL e -- | Attempts to open a sorted AVL tree at the element given by the -- supplied selector. This function returns Nothing if there is no -- such element. -- -- Note that this operation will still create a zipper path structure on -- the heap (which is promptly discarded) if the search fails, and so is -- potentially inefficient if failure is likely. In cases like this it -- may be better to use genOpenBAVL, test for "fullness" using -- fullBAVL and then convert to a ZAVL using -- fullBAVLtoZAVL. -- -- Complexity: O(log n) genTryOpen :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e) -- | Attempts to open a sorted AVL tree at the least element which is -- greater than or equal, according to the supplied selector. This -- function returns Nothing if the tree does not contain such an -- element. -- -- Complexity: O(log n) genTryOpenGE :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e) -- | Attempts to open a sorted AVL tree at the greatest element which is -- less than or equal, according to the supplied selector. This function -- returns _Nothing_ if the tree does not contain such an element. -- -- Complexity: O(log n) genTryOpenLE :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e) -- | Returns (Right zavl) if the expected element was -- found, (Left pavl) if the expected element was not -- found. It's OK to use this function on empty trees. -- -- Complexity: O(log n) genOpenEither :: (e -> Ordering) -> AVL e -> Either (PAVL e) (ZAVL e) -- | Closes a Zipper. -- -- Complexity: O(log n) close :: ZAVL e -> AVL e -- | Essentially the same operation as fill, but the resulting -- ZAVL is closed immediately. -- -- Complexity: O(log n) fillClose :: e -> PAVL e -> AVL e -- | Gets the current element of a Zipper. -- -- Complexity: O(1) getCurrent :: ZAVL e -> e -- | Overwrites the current element of a Zipper. -- -- Complexity: O(1) putCurrent :: e -> ZAVL e -> ZAVL e -- | Applies a function to the current element of a Zipper (lazily). See -- also applyCurrent' for a strict version of this function. -- -- Complexity: O(1) applyCurrent :: (e -> e) -> ZAVL e -> ZAVL e -- | Applies a function to the current element of a Zipper strictly. See -- also applyCurrent for a non-strict version of this function. -- -- Complexity: O(1) applyCurrent' :: (e -> e) -> ZAVL e -> ZAVL e -- | Moves one step left. This function raises an error if the current -- element is already the leftmost element. -- -- Complexity: O(1) average, O(log n) worst case. assertMoveL :: ZAVL e -> ZAVL e -- | Moves one step right. This function raises an error if the current -- element is already the rightmost element. -- -- Complexity: O(1) average, O(log n) worst case. assertMoveR :: ZAVL e -> ZAVL e -- | Attempts to move one step left. This function returns Nothing -- if the current element is already the leftmost element. -- -- Complexity: O(1) average, O(log n) worst case. tryMoveL :: ZAVL e -> Maybe (ZAVL e) -- | Attempts to move one step right. This function returns Nothing -- if the current element is already the rightmost element. -- -- Complexity: O(1) average, O(log n) worst case. tryMoveR :: ZAVL e -> Maybe (ZAVL e) -- | Inserts a new element to the immediate left of the current element. -- -- Complexity: O(1) average, O(log n) worst case. insertL :: e -> ZAVL e -> ZAVL e -- | Inserts a new element to the immediate right of the current element. -- -- Complexity: O(1) average, O(log n) worst case. insertR :: ZAVL e -> e -> ZAVL e -- | Inserts a new element to the immediate left of the current element and -- then moves one step left (so the newly inserted element becomes the -- current element). -- -- Complexity: O(1) average, O(log n) worst case. insertMoveL :: e -> ZAVL e -> ZAVL e -- | Inserts a new element to the immediate right of the current element -- and then moves one step right (so the newly inserted element becomes -- the current element). -- -- Complexity: O(1) average, O(log n) worst case. insertMoveR :: ZAVL e -> e -> ZAVL e -- | Fill the gap pointed to by a PAVL with the supplied element, -- which becomes the current element of the resulting ZAVL. The -- supplied filling element should be "equal" to the value used in the -- search which created the PAVL. -- -- Complexity: O(1) fill :: e -> PAVL e -> ZAVL e -- | Deletes the current element and then closes the Zipper. -- -- Complexity: O(log n) delClose :: ZAVL e -> AVL e -- | Deletes the current element and moves one step left. This function -- raises an error if the current element is already the leftmost -- element. -- -- Complexity: O(1) average, O(log n) worst case. assertDelMoveL :: ZAVL e -> ZAVL e -- | Deletes the current element and moves one step right. This function -- raises an error if the current element is already the rightmost -- element. -- -- Complexity: O(1) average, O(log n) worst case. assertDelMoveR :: ZAVL e -> ZAVL e -- | Attempts to delete the current element and move one step right. This -- function returns Nothing if the current element is already the -- rightmost element. -- -- Complexity: O(1) average, O(log n) worst case. tryDelMoveR :: ZAVL e -> Maybe (ZAVL e) -- | Attempts to delete the current element and move one step left. This -- function returns Nothing if the current element is already the -- leftmost element. -- -- Complexity: O(1) average, O(log n) worst case. tryDelMoveL :: ZAVL e -> Maybe (ZAVL e) -- | Delete all elements to the left of the current element. -- -- Complexity: O(log n) delAllL :: ZAVL e -> ZAVL e -- | Delete all elements to the right of the current element. -- -- Complexity: O(log n) delAllR :: ZAVL e -> ZAVL e -- | Similar to delAllL, in that all elements to the left of the -- current element are deleted, but this function also closes the tree in -- the process. -- -- Complexity: O(log n) delAllCloseL :: ZAVL e -> AVL e -- | Similar to delAllR, in that all elements to the right of the -- current element are deleted, but this function also closes the tree in -- the process. -- -- Complexity: O(log n) delAllCloseR :: ZAVL e -> AVL e -- | Similar to delAllCloseL, but in this case the current element -- and all those to the left of the current element are deleted. -- -- Complexity: O(log n) delAllIncCloseL :: ZAVL e -> AVL e -- | Similar to delAllCloseR, but in this case the current element -- and all those to the right of the current element are deleted. -- -- Complexity: O(log n) delAllIncCloseR :: ZAVL e -> AVL e -- | Inserts a new AVL tree to the immediate left of the current element. -- -- Complexity: O(log n), where n is the size of the inserted tree. insertTreeL :: AVL e -> ZAVL e -> ZAVL e -- | Inserts a new AVL tree to the immediate right of the current element. -- -- Complexity: O(log n), where n is the size of the inserted tree. insertTreeR :: ZAVL e -> AVL e -> ZAVL e -- | Returns True if the current element is the leftmost element. -- -- Complexity: O(1) average, O(log n) worst case. isLeftmost :: ZAVL e -> Bool -- | Returns True if the current element is the rightmost element. -- -- Complexity: O(1) average, O(log n) worst case. isRightmost :: ZAVL e -> Bool -- | Counts the number of elements to the left of the current element (this -- does not include the current element). -- -- Complexity: O(n), where n is the count result. sizeL :: ZAVL e -> Int -- | Counts the number of elements to the right of the current element -- (this does not include the current element). -- -- Complexity: O(n), where n is the count result. sizeR :: ZAVL e -> Int -- | Counts the total number of elements in a ZAVL. -- -- Complexity: O(n) sizeZAVL :: ZAVL e -> Int -- | A BAVL is like a pointer reference to somewhere inside an -- AVL tree. It may be either "full" (meaning it points to an -- actual tree node containing an element), or "empty" (meaning it points -- to the position in a tree where an element was expected but wasn't -- found). data BAVL e -- | Search for an element in a sorted AVL tree using the -- supplied selector. Returns a "full" BAVL if a matching element -- was found, otherwise returns an "empty" BAVL. -- -- Complexity: O(log n) genOpenBAVL :: (e -> Ordering) -> AVL e -> BAVL e -- | Returns the original tree, extracted from the BAVL. Typically -- you will not need this, as the original tree will still be in scope in -- most cases. -- -- Complexity: O(1) closeBAVL :: BAVL e -> AVL e -- | Returns True if the BAVL is "full" (a corresponding -- element was found). -- -- Complexity: O(1) fullBAVL :: BAVL e -> Bool -- | Returns True if the BAVL is "empty" (no corresponding -- element was found). -- -- Complexity: O(1) emptyBAVL :: BAVL e -> Bool -- | Read the element value from a "full" BAVL. This function -- returns Nothing if applied to an "empty" BAVL. -- -- Complexity: O(1) tryReadBAVL :: BAVL e -> Maybe e -- | Read the element value from a "full" BAVL. This function raises -- an error if applied to an "empty" BAVL. -- -- Complexity: O(1) readFullBAVL :: BAVL e -> e -- | If the BAVL is "full", this function returns the original tree -- with the corresponding element replaced by the new element (first -- argument). If it's "empty" the original tree is returned with the new -- element inserted. -- -- Complexity: O(log n) pushBAVL :: e -> BAVL e -> AVL e -- | If the BAVL is "full", this function returns the original tree -- with the corresponding element deleted. If it's "empty" the original -- tree is returned unmodified. -- -- Complexity: O(log n) (or O(1) for an empty BAVL) deleteBAVL :: BAVL e -> AVL e -- | Converts a "full" BAVL as a ZAVL. Raises an error if -- applied to an "empty" BAVL. -- -- Complexity: O(log n) fullBAVLtoZAVL :: BAVL e -> ZAVL e -- | Converts an "empty" BAVL as a PAVL. Raises an error if -- applied to a "full" BAVL. -- -- Complexity: O(log n) emptyBAVLtoPAVL :: BAVL e -> PAVL e -- | Converts a BAVL to either a PAVL or ZAVL -- (depending on whether it is "empty" or "full"). -- -- Complexity: O(log n) anyBAVLtoEither :: BAVL e -> Either (PAVL e) (ZAVL e) -- | Verify that a tree is height balanced and that the BF of each node is -- correct. -- -- Complexity: O(n) isBalanced :: AVL e -> Bool -- | Verify that a tree is sorted. -- -- Complexity: O(n) isSorted :: (e -> e -> Ordering) -> AVL e -> Bool -- | Verify that a tree is sorted, height balanced and the BF of each node -- is correct. -- -- Complexity: O(n) isSortedOK :: (e -> e -> Ordering) -> AVL e -> Bool -- | Detetermine the minimum number of elements in an AVL tree of given -- height. This function satisfies this recurrence relation.. -- -- 
--   minElements 0 = 0
--   minElements 1 = 1
--   minElements h = 1 + minElements (h-1) + minElements (h-2)
--              -- = Some weird expression involving the golden ratio
--
minElements :: Int -> Integer -- | Detetermine the maximum number of elements in an AVL tree of given -- height. This function satisfies this recurrence relation.. -- -- 
--   maxElements 0 = 0
--   maxElements h = 1 + 2 * maxElements (h-1) -- = 2^h-1
--
maxElements :: Int -> Integer -- | A BinPath is full if the search succeeded, empty otherwise. data BinPath a FullBP :: !!Int# -> a -> BinPath a EmptyBP :: !!Int# -> BinPath a -- | Find the path to a AVL tree element, returns -1 (invalid path) if -- element not found -- -- Complexity: O(log n) genFindPath :: (e -> Ordering) -> AVL e -> Int# -- | Get the BinPath of an element using the supplied selector. -- -- Complexity: O(log n) genOpenPath :: (e -> Ordering) -> AVL e -> BinPath e -- | Get the BinPath of an element using the supplied (combining) selector. -- -- Complexity: O(log n) genOpenPathWith :: (e -> COrdering a) -> AVL e -> BinPath a -- | Read a tree element. Assumes the path bits were extracted from -- FullBP constructor. Raises an error if the path leads to an -- empty tree. -- -- Complexity: O(log n) readPath :: Int# -> AVL e -> e -- | Overwrite a tree element. Assumes the path bits were extracted from -- FullBP constructor. Raises an error if the path leads to an -- empty tree. -- -- N.B This operation does not change tree shape (no insertion occurs). -- -- Complexity: O(log n) writePath :: Int# -> e -> AVL e -> AVL e -- | Inserts a new tree element. Assumes the path bits were extracted from -- a EmptyBP constructor. This function replaces the first Empty -- node it encounters with the supplied value, regardless of the current -- path bits (which are not checked). DO NOT USE THIS FOR REPLACING -- ELEMENTS ALREADY PRESENT IN THE TREE (use writePath for this). -- -- Complexity: O(log n) insertPath :: Int# -> e -> AVL e -> AVL e -- | Deletes a tree element. Assumes the path bits were extracted from a -- FullBP constructor. -- -- Complexity: O(log n) deletePath :: Int# -> AVL e -> AVL e instance Functor AVL instance (Read e) => Read (AVL e) instance (Show e) => Show (AVL e) instance Traversable AVL -- | This module contains a large set of fairly comprehensive but extremely -- time consuming tests of AVL tree functions (not based on QuickCheck). -- -- They can all be run using allTests, or they can be run -- individually. module Data.Tree.AVL.Test.AllTests -- | Run every test in this module (takes a very long time). allTests :: IO () -- | Test readPath testReadPath :: IO () -- | Test isBalanced is capable of failing for a few non-AVL trees. testIsBalanced :: IO () -- | Test isSorted is capable of failing for a few non-sorted trees. testIsSorted :: IO () -- | Test size function testSize :: IO () -- | Test clipSize function testClipSize :: IO () -- | Test genWrite function testGenWrite :: IO () -- | Test genPush function testGenPush :: IO () -- | Test pushL function Also exercises: asListL testPushL :: IO () -- | Test pushR function Also exercises: asListR testPushR :: IO () -- | Test genDel function testGenDel :: IO () -- | Test assertDelL function Also exercises: asListL testAssertDelL :: IO () -- | Test delR function Also exercises: asListR testAssertDelR :: IO () -- | Test assertPopL function Also exercises: asListL testAssertPopL :: IO () -- | Test popHL function This test can only be run if popHL and HAVL are -- not hidden. However, popHL is exercised by indirectly by testConcatAVL -- anyway testPopHL :: IO () -- | Test assertPopR function Also exercises: asListR testAssertPopR :: IO () -- | Test genAssertPop function testGenAssertPop :: IO () -- | Test flatten function Also exercises: asListL,replicateAVL testFlatten :: IO () -- | Test the join function testJoin :: IO () -- | Test the joinHAVL function testJoinHAVL :: IO () -- | Test the concatAVL function. testConcatAVL :: IO () -- | Test the flatConcat function. testFlatConcat :: IO () -- | Test foldrAVL testFoldrAVL :: IO () -- | Test foldrAVL' testFoldrAVL' :: IO () -- | Test foldlAVL testFoldlAVL :: IO () -- | Test foldlAVL' testFoldlAVL' :: IO () -- | Test foldr1AVL testFoldr1AVL :: IO () -- | Test foldr1AVL' testFoldr1AVL' :: IO () -- | Test foldl1AVL testFoldl1AVL :: IO () -- | Test foldl1AVL' testFoldl1AVL' :: IO () -- | Test mapAccumLAVL testMapAccumLAVL :: IO () -- | Test mapAccumRAVL testMapAccumRAVL :: IO () -- | Test mapAccumLAVL' testMapAccumLAVL' :: IO () -- | Test mapAccumRAVL' testMapAccumRAVL' :: IO () -- | Test mapAccumLAVL'' testMapAccumLAVL'' :: IO () -- | Test mapAccumRAVL'' testMapAccumRAVL'' :: IO () -- | Test splitAtL function testSplitAtL :: IO () -- | Test the filterViaList function testFilterViaList :: IO () -- | Test the filterAVL function testFilterAVL :: IO () -- | Test the mapMaybeViaList function testMapMaybeViaList :: IO () -- | Test the mapMaybeAVL function testMapMaybeAVL :: IO () -- | Test takeL function testTakeL :: IO () -- | Test dropL function testDropL :: IO () -- | Test splitAtR function testSplitAtR :: IO () -- | Test takeR function testTakeR :: IO () -- | Test dropR function testDropR :: IO () -- | Test spanL function testSpanL :: IO () -- | Test takeWhileL function testTakeWhileL :: IO () -- | Test dropWhileL function testDropWhileL :: IO () -- | Test spanR function testSpanR :: IO () -- | Test takeWhileR function testTakeWhileR :: IO () -- | Test dropWhileR function testDropWhileR :: IO () -- | Test rotateL function testRotateL :: IO () -- | Test rotateR function testRotateR :: IO () -- | Test rotateByL function testRotateByL :: IO () -- | Test rotateByR function testRotateByR :: IO () -- | Test genForkL function testGenForkL :: IO () -- | Test genForkR function testGenForkR :: IO () -- | Test genFork function testGenFork :: IO () -- | Test genTakeLE function testGenTakeLE :: IO () -- | Test genTakeGT function testGenTakeGT :: IO () -- | Test genTakeGE function testGenTakeGE :: IO () -- | Test genTakeLT function testGenTakeLT :: IO () -- | Test the genUnion function testGenUnion :: IO () -- | Test the genUnionMaybe function testGenUnionMaybe :: IO () -- | Test the genIntersection function testGenIntersection :: IO () -- | Test the genIntersectionMaybe function testGenIntersectionMaybe :: IO () -- | Test the genIntersectionAsListL function testGenIntersectionAsListL :: IO () -- | Test the genIntersectionMaybeAsListL function testGenIntersectionMaybeAsListL :: IO () -- | Test the genDifference function testGenDifference :: IO () -- | Test the genDifferenceMaybe function testGenDifferenceMaybe :: IO () -- | Test the genSymDifference function testGenSymDifference :: IO () -- | Test the genIsSubsetOf function testGenIsSubsetOf :: IO () -- | Test the genIsSubsetOfBy function testGenIsSubsetOfBy :: IO () -- | Test compareHeight function testCompareHeight :: IO () -- | Test Show,Read,Eq instances testShowReadEq :: IO () -- | Test Zipper open/close testGenOpenClose :: IO () -- | Test Zipper delClose testDelClose :: IO () -- | Test Zipper assertOpenL/close testOpenLClose :: IO () -- | Test Zipper assertOpenR/close testOpenRClose :: IO () -- | Test Zipper assertMoveL/isRightmost testMoveL :: IO () -- | Test Zipper assertMoveR/isLeftmost testMoveR :: IO () -- | Test Zipper insertL testInsertL :: IO () -- | Test Zipper insertMoveL testInsertMoveL :: IO () -- | Test Zipper insertR testInsertR :: IO () -- | Test Zipper insertMoveR testInsertMoveR :: IO () -- | Test Zipper insertTreeL testInsertTreeL :: IO () -- | Test Zipper insertTreeR testInsertTreeR :: IO () -- | Test Zipper assertDelMoveL testDelMoveL :: IO () -- | Test Zipper assertDelMoveR testDelMoveR :: IO () -- | Test Zipper delAllL testDelAllL :: IO () -- | Test Zipper delAllR testDelAllR :: IO () -- | Test Zipper delAllCloseL testDelAllCloseL :: IO () -- | Test Zipper delAllIncCloseL testDelAllIncCloseL :: IO () -- | Test Zipper delAllCloseR testDelAllCloseR :: IO () -- | Test Zipper delAllIncCloseR testDelAllIncCloseR :: IO () -- | Test Zipper sizeL/sizeR/sizeZAVL testZipSize :: IO () -- | Test Zipper genTryOpenLE testGenTryOpenLE :: IO () -- | Test Zipper genTryOpenGE testGenTryOpenGE :: IO () -- | Test Zipper genOpenEither (also tests fill and fillClose) testGenOpenEither :: IO () -- | Test anyBAVLtoEither testBAVLtoZipper :: IO ()