-- 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).
@package AvlTree
@version 4.2
-- | 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.
--
-- Controlling Strictness.
--
-- The AVL tree 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, for example).
--
-- The Read and Show instances.
--
-- Begining with version 4.0 these are now derived to ensure consistency
-- with Eq instance. (Show now reveals the exact tree structure).
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
-- | 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)
assertRead :: 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 assertRead,
-- but returns Nothing if the search failed.
--
-- Complexity: O(log n)
tryRead :: 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)
tryReadMaybe :: 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 assertRead,
-- but returns a the default value (first argument) if the search fails.
--
-- Complexity: O(log n)
defaultRead :: 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)
contains :: 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)
write :: (e -> COrdering e) -> AVL e -> AVL e
-- | Functionally identical to write, 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)
writeFast :: (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)
tryWrite :: (e -> COrdering e) -> AVL e -> Maybe (AVL e)
-- | Similar to write, 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)
writeMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> AVL e
-- | Similar to tryWrite, 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)
tryWriteMaybe :: (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
-- push'
--
-- Complexity: O(log n)
push :: (e -> COrdering e) -> e -> AVL e -> AVL e
-- | Almost identical to push, 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)
push' :: (e -> COrdering e) -> e -> AVL e -> AVL e
-- | Similar to push, 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
-- pushMaybe'
--
-- Complexity: O(log n)
pushMaybe :: (e -> COrdering (Maybe e)) -> e -> AVL e -> AVL e
-- | Almost identical to pushMaybe, 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)
pushMaybe' :: (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)
delete :: (e -> Ordering) -> AVL e -> AVL e
-- | Functionally identical to delete, 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)
deleteFast :: (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)
deleteIf :: (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)
deleteMaybe :: (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)
assertPop :: (e -> COrdering a) -> AVL e -> (a, AVL e)
-- | Similar to genPop, but this function returns Nothing
-- if the search fails.
--
-- Complexity: O(log n)
tryPop :: (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)
assertPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> (a, AVL e)
-- | Similar to assertPopMaybe, but returns Nothing if the
-- search fails.
--
-- Complexity: O(log n)
tryPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> Maybe (a, AVL e)
-- | A simpler version of assertPopMaybe. 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)
assertPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> (a, AVL e)
-- | Similar to genPopIf, but returns Nothing if the search
-- fails.
--
-- Complexity: O(log n)
tryPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> Maybe (a, 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.
union :: (e -> e -> COrdering e) -> AVL e -> AVL e -> AVL e
-- | Similar to union, 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.
unionMaybe :: (e -> e -> COrdering (Maybe e)) -> AVL e -> AVL e -> AVL e
-- | Uses the supplied comparison to evaluate the union of two
-- disjoint sets represented as sorted AVL trees. It will be
-- slightly faster than union but will raise an error if the two
-- sets intersect. Typically this would be used to re-combine the
-- "post-munge" results from one of the "venn" operations.
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out. (Faster than Hedge union from Data.Set at any rate).
disjointUnion :: (e -> e -> Ordering) -> 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..
--
--
-- unions ccmp avls = foldl' (union ccmp) empty avls
--
unions :: (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..
--
--
-- difference 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.
difference :: (a -> b -> Ordering) -> AVL a -> AVL b -> AVL a
-- | Similar to difference, 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.
differenceMaybe :: (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.
symDifference :: (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.
intersection :: (a -> b -> COrdering c) -> AVL a -> AVL b -> AVL c
-- | Similar to intersection, 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.
intersectionMaybe :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> AVL c
-- | Similar to intersection, but prepends the result to the
-- supplied list in ascending order. This is a (++) free function which
-- behaves as if defined:
--
--
-- intersectionToList c setA setB cs = asListL (intersection c setA setB) ++ cs
--
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
intersectionToList :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c] -> [c]
-- | Applies intersectionToList to the empty list.
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
intersectionAsList :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c]
-- | Similar to intersectionToList, 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.
intersectionMaybeToList :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c] -> [c]
-- | Applies intersectionMaybeToList to the empty list.
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
intersectionMaybeAsList :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c]
-- | Given two Sets A and B represented as sorted AVL
-- trees, this function extracts the 'Venn diagram' components
-- A-B, A.B and B-A. See also
-- vennMaybe.
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
venn :: (a -> b -> COrdering c) -> AVL a -> AVL b -> (AVL a, AVL c, AVL b)
-- | Similar to venn, but intersection elements for which the
-- combining comparison returns (Eq Nothing) are
-- deleted from the intersection result.
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
vennMaybe :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> (AVL a, AVL c, AVL b)
-- | Same as venn, but prepends the intersection component to the
-- supplied list in ascending order.
vennToList :: (a -> b -> COrdering c) -> [c] -> AVL a -> AVL b -> (AVL a, [c], AVL b)
-- | Same as venn, but returns the intersection component as a list
-- in ascending order. This is just vennToList applied to an empty
-- initial intersection list.
vennAsList :: (a -> b -> COrdering c) -> AVL a -> AVL b -> (AVL a, [c], AVL b)
-- | Same as vennMaybe, but prepends the intersection component to
-- the supplied list in ascending order.
vennMaybeToList :: (a -> b -> COrdering (Maybe c)) -> [c] -> AVL a -> AVL b -> (AVL a, [c], AVL b)
-- | Same as vennMaybe, but returns the intersection component as a
-- list in ascending order. This is just vennMaybeToList applied
-- to an empty initial intersection list.
vennMaybeAsList :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> (AVL a, [c], AVL b)
-- | 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..
--
--
-- - The first set is empty (the empty set is a subset of any
-- set).
-- - The two sets are equal.
-- - The first set is a proper subset of the second set.
--
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
isSubsetOf :: (a -> b -> Ordering) -> AVL a -> AVL b -> Bool
-- | Similar to isSubsetOf, 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.
isSubsetOfBy :: (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)
assertOpen :: (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 openBAVL, test for "fullness" using
-- fullBAVL and then convert to a ZAVL using
-- fullBAVLtoZAVL.
--
-- Complexity: O(log n)
tryOpen :: (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)
tryOpenGE :: (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)
tryOpenLE :: (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)
openEither :: (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)
openBAVL :: (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)
-- | 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
-- | 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 pushList on the empty AVL tree.
--
-- Complexity: O(n.(log n))
asTree :: (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.
pushList :: (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)
reverse :: 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 (map').
--
-- 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)
map :: (a -> b) -> AVL a -> AVL b
-- | Similar to map, but the supplied function is applied strictly.
--
-- Complexity: O(n)
map' :: (a -> b) -> AVL a -> AVL b
-- | The AVL equivalent of Data.List.mapAccumL on lists. It
-- behaves like a combination of map and foldl. 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 mapAccumL' for a
-- strict version.
--
-- Complexity: O(n)
mapAccumL :: (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 map and foldr. 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 mapAccumR' for a
-- strict version.
--
-- Complexity: O(n)
mapAccumR :: (z -> a -> (z, b)) -> z -> AVL a -> (z, AVL b)
-- | This is a strict version of mapAccumL, 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)
mapAccumL' :: (z -> a -> (z, b)) -> z -> AVL a -> (z, AVL b)
-- | This is a strict version of mapAccumR, 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)
mapAccumR' :: (z -> a -> (z, b)) -> z -> AVL a -> (z, AVL b)
-- | Construct a flat AVL tree of size n (n>=0), where all elements are
-- identical.
--
-- Complexity: O(log n)
replicate :: Int -> e -> AVL e
-- | Remove all AVL tree elements which do not satisfy the supplied
-- predicate. Element ordering is preserved.
--
-- Complexity: O(n)
filter :: (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)
mapMaybe :: (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 filter 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 mapMaybe 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)
partition :: (e -> Bool) -> AVL e -> (AVL e, AVL e)
-- | This is the non-overloaded version of the
-- Data.Traversable.traverse method for AVL trees.
traverseAVL :: Applicative f => (a -> f b) -> AVL a -> f (AVL b)
-- | 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 foldr' for a strict version.
--
-- It behaves as if defined..
--
--
-- foldr f a avl = foldr f a (asListL avl)
--
--
-- For example, the asListL function could be defined..
--
--
-- asListL = foldr (:) []
--
--
-- Complexity: O(n)
foldr :: (e -> a -> a) -> a -> AVL e -> a
-- | The strict version of foldr, 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)
foldr' :: (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 foldr1' for a strict version.
--
--
-- foldr1 f avl = foldr1 f (asListL avl)
--
--
-- This function raises an error if the tree is empty.
--
-- Complexity: O(n)
foldr1 :: (e -> e -> e) -> AVL e -> e
-- | The strict version of foldr1, 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)
foldr1' :: (e -> e -> e) -> AVL e -> e
-- | This fold is a hybrid between foldr and foldr1. As with
-- foldr1, 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 foldr). As with foldr and foldr1, this
-- function is lazy, so it's best not to use it with functions that are
-- strict in their second argument. See foldr2' for a strict
-- version.
--
-- Complexity: O(n)
foldr2 :: (e -> a -> a) -> (e -> a) -> AVL e -> a
-- | The strict version of foldr2, 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)
foldr2' :: (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 foldl' for a strict version.
--
--
-- foldl f a avl = foldl f a (asListL avl)
--
--
-- For example, the asListR function could be defined..
--
--
-- asListR = foldl (flip (:)) []
--
--
-- Complexity: O(n)
foldl :: (a -> e -> a) -> a -> AVL e -> a
-- | The strict version of foldl, 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)
foldl' :: (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 foldl1' for a strict version.
--
--
-- foldl1 f avl = foldl1 f (asListL avl)
--
--
-- This function raises an error if the tree is empty.
--
-- Complexity: O(n)
foldl1 :: (e -> e -> e) -> AVL e -> e
-- | The strict version of foldl1, 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)
foldl1' :: (e -> e -> e) -> AVL e -> e
-- | This fold is a hybrid between foldl and foldl1. As with
-- foldl1, 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 foldl). As with foldl and foldl1, this
-- function is lazy, so it's best not to use it with functions that are
-- strict in their first argument. See foldl2' for a strict
-- version.
--
-- Complexity: O(n)
foldl2 :: (a -> e -> a) -> (e -> a) -> AVL e -> a
-- | The strict version of foldl2, 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)
foldl2' :: (a -> e -> a) -> (e -> a) -> AVL e -> a
-- | Glasgow Haskell only. Similar to mapAccumL' but uses an unboxed
-- pair in the accumulating function.
--
-- Complexity: O(n)
mapAccumL'' :: (z -> a -> (# z, b #)) -> z -> AVL a -> (z, AVL b)
-- | Glasgow Haskell only. Similar to mapAccumR' but uses an unboxed
-- pair in the accumulating function.
--
-- Complexity: O(n)
mapAccumR'' :: (z -> a -> (# z, b #)) -> z -> AVL a -> (z, AVL b)
-- | This is a specialised version of foldr' for use with an
-- unboxed Int accumulator.
--
-- Complexity: O(n)
foldrInt# :: (e -> Int# -> Int#) -> Int# -> AVL e -> Int#
-- | A fast alternative implementation for Data.List.nub. Deletes
-- all but the first occurrence of an element from the input list.
--
-- Complexity: O(n.(log n))
nub :: Ord a => [a] -> [a]
-- | A fast alternative implementation for Data.List.nubBy.
-- Deletes all but the first occurrence of an element from the input
-- list.
--
-- Complexity: O(n.(log n))
nubBy :: (a -> a -> Ordering) -> [a] -> [a]
-- | 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 reverse.
--
-- Complexity: O(n)
flatReverse :: AVL e -> AVL e
-- | Similar to map, but the resulting tree is flat. This function
-- has higher constant factor overhead than map.
--
-- 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
-- | 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)
forkL :: (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)
forkR :: (e -> Ordering) -> AVL e -> (AVL e, AVL e)
-- | Similar to forkL and forkR, but returns any equal
-- element found (instead of incorporating it into the left or right tree
-- results respectively).
--
-- Complexity: O(log n)
fork :: (e -> COrdering a) -> AVL e -> (AVL e, Maybe a, AVL e)
-- | This is a simplified version of forkL 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
-- dropGT.
--
-- Complexity: O(log n)
takeLE :: (e -> Ordering) -> AVL e -> AVL e
-- | A synonym for takeLE.
--
-- Complexity: O(log n)
dropGT :: (e -> Ordering) -> AVL e -> AVL e
-- | This is a simplified version of forkR which returns a sorted
-- tree containing only those elements which are less than according to
-- the supplied selector. This function also has the synonym
-- dropGE.
--
-- Complexity: O(log n)
takeLT :: (e -> Ordering) -> AVL e -> AVL e
-- | A synonym for takeLT.
--
-- Complexity: O(log n)
dropGE :: (e -> Ordering) -> AVL e -> AVL e
-- | This is a simplified version of forkL which returns a sorted
-- tree containing only those elements which are greater according to the
-- supplied selector. This function also has the synonym dropLE.
--
-- Complexity: O(log n)
takeGT :: (e -> Ordering) -> AVL e -> AVL e
-- | A synonym for takeGT.
--
-- Complexity: O(log n)
dropLE :: (e -> Ordering) -> AVL e -> AVL e
-- | This is a simplified version of forkR 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
-- dropLT.
--
-- Complexity: O(log n)
takeGE :: (e -> Ordering) -> AVL e -> AVL e
-- | A synonym for takeGE.
--
-- Complexity: O(log n)
dropLT :: (e -> Ordering) -> AVL e -> AVL e
-- | A convenience wrapper for addSize#.
size :: AVL e -> Int
-- | See addSize#.
addSize :: 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 addSize.
--
-- Complexity: O(min n c) where n is tree size and c is clip value.
clipSize :: Int -> AVL e -> Maybe Int
-- | Fast algorithm to add the size of a tree to the first argument. 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)
addSize# :: Int# -> AVL e -> Int#
-- | A convenience wrapper for addSize#.
size# :: AVL e -> 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
-- | A BinPath is full if the search succeeded, empty otherwise.
data BinPath a
FullBP :: {-# UNPACK #-} !Int# -> a -> BinPath a
EmptyBP :: {-# UNPACK #-} !Int# -> BinPath a
-- | Find the path to a AVL tree element, returns -1 (invalid path) if
-- element not found
--
-- Complexity: O(log n)
findFullPath :: (e -> Ordering) -> AVL e -> Int#
-- | Find the path to a non-existant AVL tree element, returns -1 (invalid
-- path) if element is found
--
-- Complexity: O(log n)
findEmptyPath :: (e -> Ordering) -> AVL e -> Int#
-- | Get the BinPath of an element using the supplied selector.
--
-- Complexity: O(log n)
openPath :: (e -> Ordering) -> AVL e -> BinPath e
-- | Get the BinPath of an element using the supplied (combining) selector.
--
-- Complexity: O(log n)
openPathWith :: (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
-- | 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
-- | This name is deprecated. Instead use union.
genUnion :: (e -> e -> COrdering e) -> AVL e -> AVL e -> AVL e
-- | This name is deprecated. Instead use unionMaybe.
genUnionMaybe :: (e -> e -> COrdering (Maybe e)) -> AVL e -> AVL e -> AVL e
-- | This name is deprecated. Instead use disjointUnion.
genDisjointUnion :: (e -> e -> Ordering) -> AVL e -> AVL e -> AVL e
-- | This name is deprecated. Instead use unions.
genUnions :: (e -> e -> COrdering e) -> [AVL e] -> AVL e
-- | This name is deprecated. Instead use difference.
genDifference :: (a -> b -> Ordering) -> AVL a -> AVL b -> AVL a
-- | This name is deprecated. Instead use differenceMaybe.
genDifferenceMaybe :: (a -> b -> COrdering (Maybe a)) -> AVL a -> AVL b -> AVL a
-- | This name is deprecated. Instead use symDifference.
genSymDifference :: (e -> e -> Ordering) -> AVL e -> AVL e -> AVL e
-- | This name is deprecated. Instead use intersection.
genIntersection :: (a -> b -> COrdering c) -> AVL a -> AVL b -> AVL c
-- | This name is deprecated. Instead use intersectionMaybe.
genIntersectionMaybe :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> AVL c
-- | This name is deprecated. Instead use intersectionToList.
genIntersectionToListL :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c] -> [c]
-- | This name is deprecated. Instead use intersectionAsList.
genIntersectionAsListL :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c]
-- | This name is deprecated. Instead use
-- intersectionMaybeToList.
genIntersectionMaybeToListL :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c] -> [c]
-- | This name is deprecated. Instead use
-- intersectionMaybeAsList.
genIntersectionMaybeAsListL :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c]
-- | This name is deprecated. Instead use venn.
genVenn :: (a -> b -> COrdering c) -> AVL a -> AVL b -> (AVL a, AVL c, AVL b)
-- | This name is deprecated. Instead use vennMaybe.
genVennMaybe :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> (AVL a, AVL c, AVL b)
-- | This name is deprecated. Instead use vennToList.
genVennToList :: (a -> b -> COrdering c) -> [c] -> AVL a -> AVL b -> (AVL a, [c], AVL b)
-- | This name is deprecated. Instead use vennAsList.
genVennAsList :: (a -> b -> COrdering c) -> AVL a -> AVL b -> (AVL a, [c], AVL b)
-- | This name is deprecated. Instead use vennMaybeToList.
genVennMaybeToList :: (a -> b -> COrdering (Maybe c)) -> [c] -> AVL a -> AVL b -> (AVL a, [c], AVL b)
-- | This name is deprecated. Instead use vennMaybeAsList.
genVennMaybeAsList :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> (AVL a, [c], AVL b)
-- | This name is deprecated. Instead use isSubsetOf.
genIsSubsetOf :: (a -> b -> Ordering) -> AVL a -> AVL b -> Bool
-- | This name is deprecated. Instead use isSubsetOfBy.
genIsSubsetOfBy :: (a -> b -> COrdering Bool) -> AVL a -> AVL b -> Bool
-- | This name is deprecated. Instead use assertRead.
genAssertRead :: AVL e -> (e -> COrdering a) -> a
-- | This name is deprecated. Instead use tryRead.
genTryRead :: AVL e -> (e -> COrdering a) -> Maybe a
-- | This name is deprecated. Instead use tryReadMaybe.
genTryReadMaybe :: AVL e -> (e -> COrdering (Maybe a)) -> Maybe a
-- | This name is deprecated. Instead use defaultRead.
genDefaultRead :: a -> AVL e -> (e -> COrdering a) -> a
-- | This name is deprecated. Instead use contains.
genContains :: AVL e -> (e -> Ordering) -> Bool
-- | This name is deprecated. Instead use write.
genWrite :: (e -> COrdering e) -> AVL e -> AVL e
-- | This name is deprecated. Instead use writeFast.
genWriteFast :: (e -> COrdering e) -> AVL e -> AVL e
-- | This name is deprecated. Instead use tryWrite.
genTryWrite :: (e -> COrdering e) -> AVL e -> Maybe (AVL e)
-- | This name is deprecated. Instead use writeMaybe.
genWriteMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> AVL e
-- | This name is deprecated. Instead use tryWriteMaybe.
genTryWriteMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> Maybe (AVL e)
-- | This name is deprecated. Instead use delete.
genDel :: (e -> Ordering) -> AVL e -> AVL e
-- | This name is deprecated. Instead use deleteFast.
genDelFast :: (e -> Ordering) -> AVL e -> AVL e
-- | This name is deprecated. Instead use deleteIf.
genDelIf :: (e -> COrdering Bool) -> AVL e -> AVL e
-- | This name is deprecated. Instead use deleteMaybe.
genDelMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> AVL e
-- | This name is deprecated. Instead use assertPop.
genAssertPop :: (e -> COrdering a) -> AVL e -> (a, AVL e)
-- | This name is deprecated. Instead use tryPop.
genTryPop :: (e -> COrdering a) -> AVL e -> Maybe (a, AVL e)
-- | This name is deprecated. Instead use assertPopMaybe.
genAssertPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> (a, AVL e)
-- | This name is deprecated. Instead use tryPopMaybe.
genTryPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> Maybe (a, AVL e)
-- | This name is deprecated. Instead use assertPopIf.
genAssertPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> (a, AVL e)
-- | This name is deprecated. Instead use tryPopIf.
genTryPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> Maybe (a, AVL e)
-- | This name is deprecated. Instead use push.
genPush :: (e -> COrdering e) -> e -> AVL e -> AVL e
-- | This name is deprecated. Instead use ' push''.
genPush' :: (e -> COrdering e) -> e -> AVL e -> AVL e
-- | This name is deprecated. Instead use pushMaybe.
genPushMaybe :: (e -> COrdering (Maybe e)) -> e -> AVL e -> AVL e
-- | This name is deprecated. Instead use pushMaybe'.
genPushMaybe' :: (e -> COrdering (Maybe e)) -> e -> AVL e -> AVL e
-- | This name is deprecated. Instead use asTree.
genAsTree :: (e -> e -> COrdering e) -> [e] -> AVL e
-- | This name is deprecated. Instead use forkL.
genForkL :: (e -> Ordering) -> AVL e -> (AVL e, AVL e)
-- | This name is deprecated. Instead use forkR.
genForkR :: (e -> Ordering) -> AVL e -> (AVL e, AVL e)
-- | This name is deprecated. Instead use fork.
genFork :: (e -> COrdering a) -> AVL e -> (AVL e, Maybe a, AVL e)
-- | This name is deprecated. Instead use takeLE.
genTakeLE :: (e -> Ordering) -> AVL e -> AVL e
-- | This name is deprecated. Instead use dropGT.
genDropGT :: (e -> Ordering) -> AVL e -> AVL e
-- | This name is deprecated. Instead use takeLT.
genTakeLT :: (e -> Ordering) -> AVL e -> AVL e
-- | This name is deprecated. Instead use dropGE.
genDropGE :: (e -> Ordering) -> AVL e -> AVL e
-- | This name is deprecated. Instead use takeGT.
genTakeGT :: (e -> Ordering) -> AVL e -> AVL e
-- | This name is deprecated. Instead use dropLE.
genDropLE :: (e -> Ordering) -> AVL e -> AVL e
-- | This name is deprecated. Instead use takeGE.
genTakeGE :: (e -> Ordering) -> AVL e -> AVL e
-- | This name is deprecated. Instead use dropLT.
genDropLT :: (e -> Ordering) -> AVL e -> AVL e
-- | This name is deprecated. Instead use assertOpen.
genAssertOpen :: (e -> Ordering) -> AVL e -> ZAVL e
-- | This name is deprecated. Instead use tryOpen.
genTryOpen :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e)
-- | This name is deprecated. Instead use tryOpenGE.
genTryOpenGE :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e)
-- | This name is deprecated. Instead use tryOpenLE.
genTryOpenLE :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e)
-- | This name is deprecated. Instead use openEither.
genOpenEither :: (e -> Ordering) -> AVL e -> Either (PAVL e) (ZAVL e)
-- | This name is deprecated. Instead use openBAVL.
genOpenBAVL :: (e -> Ordering) -> AVL e -> BAVL e
-- | This name is deprecated. Instead use findPath.
genFindPath :: (e -> Ordering) -> AVL e -> Int#
-- | This name is deprecated. Instead use openPath.
genOpenPath :: (e -> Ordering) -> AVL e -> BinPath e
-- | This name is deprecated. Instead use openPathWith.
genOpenPathWith :: (e -> COrdering a) -> AVL e -> BinPath a
-- | This name is deprecated. Instead use addSize or
-- addSize#.
fastAddSize :: Int# -> AVL e -> Int#
-- | This name is deprecated. Instead use reverse.
reverseAVL :: AVL e -> AVL e
-- | This name is deprecated. Instead use map.
mapAVL :: (a -> b) -> AVL a -> AVL b
-- | This name is deprecated. Instead use map'.
mapAVL' :: (a -> b) -> AVL a -> AVL b
-- | This name is deprecated. Instead use mapAccumL.
mapAccumLAVL :: (z -> a -> (z, b)) -> z -> AVL a -> (z, AVL b)
-- | This name is deprecated. Instead use mapAccumR.
mapAccumRAVL :: (z -> a -> (z, b)) -> z -> AVL a -> (z, AVL b)
-- | This name is deprecated. Instead use mapAccumL'.
mapAccumLAVL' :: (z -> a -> (z, b)) -> z -> AVL a -> (z, AVL b)
-- | This name is deprecated. Instead use mapAccumR'.
mapAccumRAVL' :: (z -> a -> (z, b)) -> z -> AVL a -> (z, AVL b)
-- | This name is deprecated. Instead use mapAccumL''.
mapAccumLAVL'' :: (z -> a -> (# z, b #)) -> z -> AVL a -> (z, AVL b)
-- | This name is deprecated. Instead use mapAccumR''.
mapAccumRAVL'' :: (z -> a -> (# z, b #)) -> z -> AVL a -> (z, AVL b)
-- | This name is deprecated. Instead use replicate.
replicateAVL :: Int -> e -> AVL e
-- | This name is deprecated. Instead use filter.
filterAVL :: (e -> Bool) -> AVL e -> AVL e
-- | This name is deprecated. Instead use mapMaybe.
mapMaybeAVL :: (a -> Maybe b) -> AVL a -> AVL b
-- | This name is deprecated. Instead use partition.
partitionAVL :: (e -> Bool) -> AVL e -> (AVL e, AVL e)
-- | This name is deprecated. Instead use foldr.
foldrAVL :: (e -> a -> a) -> a -> AVL e -> a
-- | This name is deprecated. Instead use foldr'.
foldrAVL' :: (e -> a -> a) -> a -> AVL e -> a
-- | This name is deprecated. Instead use foldr1.
foldr1AVL :: (e -> e -> e) -> AVL e -> e
-- | This name is deprecated. Instead use foldr1'.
foldr1AVL' :: (e -> e -> e) -> AVL e -> e
-- | This name is deprecated. Instead use foldr2.
foldr2AVL :: (e -> a -> a) -> (e -> a) -> AVL e -> a
-- | This name is deprecated. Instead use foldr2'.
foldr2AVL' :: (e -> a -> a) -> (e -> a) -> AVL e -> a
-- | This name is deprecated. Instead use foldl.
foldlAVL :: (a -> e -> a) -> a -> AVL e -> a
-- | This name is deprecated. Instead use foldl'.
foldlAVL' :: (a -> e -> a) -> a -> AVL e -> a
-- | This name is deprecated. Instead use foldl1.
foldl1AVL :: (e -> e -> e) -> AVL e -> e
-- | This name is deprecated. Instead use foldl1'.
foldl1AVL' :: (e -> e -> e) -> AVL e -> e
-- | This name is deprecated. Instead use foldl2.
foldl2AVL :: (a -> e -> a) -> (e -> a) -> AVL e -> a
-- | This name is deprecated. Instead use foldl2'.
foldl2AVL' :: (a -> e -> a) -> (e -> a) -> AVL e -> a
-- | This name is deprecated. Instead use foldrInt#.
foldrAVL_UINT :: (e -> Int# -> Int#) -> Int# -> AVL e -> Int#
-- | This name is deprecated. Instead use findFullPath.
findPath :: (e -> Ordering) -> AVL e -> Int#
instance Traversable AVL
instance Functor 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 write function
testWrite :: IO ()
-- | Test push function
testPush :: IO ()
-- | Test pushL function Also exercises: asListL
testPushL :: IO ()
-- | Test pushR function Also exercises: asListR
testPushR :: IO ()
-- | Test delete function
testDelete :: 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 assertPop function
testAssertPop :: 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 foldr
testFoldr :: IO ()
-- | Test foldr'
testFoldr' :: IO ()
-- | Test foldl
testFoldl :: IO ()
-- | Test foldl'
testFoldl' :: IO ()
-- | Test foldr1
testFoldr1 :: IO ()
-- | Test foldr1'
testFoldr1' :: IO ()
-- | Test foldl1
testFoldl1 :: IO ()
-- | Test foldl1'
testFoldl1' :: IO ()
-- | Test mapAccumL
testMapAccumL :: IO ()
-- | Test mapAccumR
testMapAccumR :: IO ()
-- | Test mapAccumL'
testMapAccumL' :: IO ()
-- | Test mapAccumR'
testMapAccumR' :: IO ()
-- | Test mapAccumL''
testMapAccumL'' :: IO ()
-- | Test mapAccumR''
testMapAccumR'' :: IO ()
-- | Test splitAtL function
testSplitAtL :: IO ()
-- | Test the filterViaList function
testFilterViaList :: IO ()
-- | Test the filter function
testFilter :: IO ()
-- | Test the mapMaybeViaList function
testMapMaybeViaList :: IO ()
-- | Test the mapMaybe function
testMapMaybe :: 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 forkL function
testForkL :: IO ()
-- | Test forkR function
testForkR :: IO ()
-- | Test fork function
testFork :: IO ()
-- | Test takeLE function
testTakeLE :: IO ()
-- | Test takeGT function
testTakeGT :: IO ()
-- | Test takeGE function
testTakeGE :: IO ()
-- | Test takeLT function
testTakeLT :: IO ()
-- | Test the union function
testUnion :: IO ()
-- | Test the disjointUnion function
testDisjointUnion :: IO ()
-- | Test the unionMaybe function
testUnionMaybe :: IO ()
-- | Test the intersection function
testIntersection :: IO ()
-- | Test the intersectionMaybe function
testIntersectionMaybe :: IO ()
-- | Test the intersectionAsList function
testIntersectionAsList :: IO ()
-- | Test the intersectionMaybeAsList function
testIntersectionMaybeAsList :: IO ()
-- | Test the difference function
testDifference :: IO ()
-- | Test the differenceMaybe function
testDifferenceMaybe :: IO ()
-- | Test the symDifference function
testSymDifference :: IO ()
-- | Test the isSubsetOf function
testIsSubsetOf :: IO ()
-- | Test the isSubsetOfBy function
testIsSubsetOfBy :: IO ()
-- | Test the venn function. Also exercises disjointUnion
testVenn :: IO ()
-- | Test the vennMaybe function.
testVennMaybe :: IO ()
-- | Test compareHeight function
testCompareHeight :: IO ()
-- | Test Show,Read,Eq instances
testShowReadEq :: IO ()
-- | Test Zipper open/close
testOpenClose :: 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 tryOpenLE
testTryOpenLE :: IO ()
-- | Test Zipper tryOpenGE
testTryOpenGE :: IO ()
-- | Test Zipper openEither (also tests fill and fillClose)
testOpenEither :: IO ()
-- | Test anyBAVLtoEither
testBAVLtoZipper :: IO ()