| ||||||||

| ||||||||

| ||||||||

Description | ||||||||

An implementation of "The Zipper" for AVL trees. This can be used like a functional pointer to a serial data structure which can be navigated and modified, without having to worry about all those tricky tree balancing issues. See JFP Vol.7 part 5 or .. http://haskell.org/hawiki/TheZipper Notes about efficiency: The functions defined here provide a useful way to achieve those awkward operations which may not be covered by the rest of this package. They're reasonably efficient (mostly O(log n) or better), but zipper flexibility is bought at the expense of keeping path information explicitly as a heap data structure rather than implicitly on the stack. Since heap storage probably costs more, zipper operations will are likely to incur higher constant factors than equivalent non-zipper operations (if available). Some of the functions provided here may appear to be weird combinations of functions from a more logical set of primitives. They are provided because they are not really simple combinations of the corresponding primitives. They are more efficient, so you should use them if possible (e.g combining deleting with Zipper closing). Also, consider using the | ||||||||

Synopsis | ||||||||

Types. | ||||||||

data ZAVL e | ||||||||

| ||||||||

data PAVL e | ||||||||

| ||||||||

Opening. | ||||||||

assertOpenL :: AVL e -> ZAVL 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) | ||||||||

assertOpenR :: 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) | ||||||||

tryOpenL :: AVL e -> Maybe (ZAVL e) | ||||||||

Attempts to open a non-empty AVL tree at the leftmost element.
This function returns Complexity: O(log n) | ||||||||

tryOpenR :: AVL e -> Maybe (ZAVL e) | ||||||||

Attempts to open a non-empty AVL tree at the rightmost element.
This function returns Complexity: O(log n) | ||||||||

genAssertOpen :: (e -> Ordering) -> AVL e -> 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) | ||||||||

genTryOpen :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e) | ||||||||

Attempts to open a sorted AVL tree at the element given by the supplied selector.
This function returns 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 Complexity: O(log n) | ||||||||

genTryOpenGE :: (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 Complexity: O(log n) | ||||||||

genTryOpenLE :: (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) | ||||||||

genOpenEither :: (e -> Ordering) -> AVL e -> Either (PAVL e) (ZAVL e) | ||||||||

Returns ( if the
expected element was not found. It's OK to use this function on empty trees.
Left pavl)Complexity: O(log n) | ||||||||

Closing. | ||||||||

close :: ZAVL e -> AVL e | ||||||||

Closes a Zipper. Complexity: O(log n) | ||||||||

fillClose :: e -> PAVL e -> AVL e | ||||||||

Essentially the same operation as Complexity: O(log n) | ||||||||

Manipulating the current element. | ||||||||

getCurrent :: ZAVL e -> e | ||||||||

Gets the current element of a Zipper. Complexity: O(1) | ||||||||

putCurrent :: e -> ZAVL e -> ZAVL e | ||||||||

Overwrites the current element of a Zipper. Complexity: O(1) | ||||||||

applyCurrent :: (e -> e) -> ZAVL e -> ZAVL e | ||||||||

Applies a function to the current element of a Zipper (lazily).
See also Complexity: O(1) | ||||||||

applyCurrent' :: (e -> e) -> ZAVL e -> ZAVL e | ||||||||

Applies a function to the current element of a Zipper strictly.
See also Complexity: O(1) | ||||||||

Moving. | ||||||||

assertMoveL :: 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. | ||||||||

assertMoveR :: 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. | ||||||||

tryMoveL :: ZAVL e -> Maybe (ZAVL e) | ||||||||

Attempts to move one step left.
This function returns Complexity: O(1) average, O(log n) worst case. | ||||||||

tryMoveR :: ZAVL e -> Maybe (ZAVL e) | ||||||||

Attempts to move one step right.
This function returns Complexity: O(1) average, O(log n) worst case. | ||||||||

Inserting elements. | ||||||||

insertL :: e -> ZAVL e -> ZAVL e | ||||||||

Inserts a new element to the immediate left 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 right of 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 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. | ||||||||

insertMoveR :: ZAVL e -> 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. | ||||||||

fill :: e -> PAVL e -> ZAVL e | ||||||||

Fill the gap pointed to by a Complexity: O(1) | ||||||||

Deleting elements. | ||||||||

delClose :: ZAVL e -> AVL e | ||||||||

Deletes the current element and then closes the Zipper. Complexity: O(log n) | ||||||||

assertDelMoveL :: ZAVL e -> ZAVL 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. | ||||||||

assertDelMoveR :: 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. | ||||||||

tryDelMoveR :: ZAVL e -> Maybe (ZAVL e) | ||||||||

Attempts to delete the current element and move one step right.
This function returns Complexity: O(1) average, O(log n) worst case. | ||||||||

tryDelMoveL :: ZAVL e -> Maybe (ZAVL e) | ||||||||

Attempts to delete the current element and move one step left.
This function returns Complexity: O(1) average, O(log n) worst case. | ||||||||

delAllL :: ZAVL e -> ZAVL e | ||||||||

Delete all elements to the left of the current element. Complexity: O(log n) | ||||||||

delAllR :: ZAVL e -> ZAVL e | ||||||||

Delete all elements to the right of the current element. Complexity: O(log n) | ||||||||

delAllCloseL :: ZAVL e -> AVL e | ||||||||

Similar to Complexity: O(log n) | ||||||||

delAllCloseR :: ZAVL e -> AVL e | ||||||||

Similar to Complexity: O(log n) | ||||||||

delAllIncCloseL :: ZAVL e -> AVL e | ||||||||

Similar to Complexity: O(log n) | ||||||||

delAllIncCloseR :: ZAVL e -> AVL e | ||||||||

Similar to Complexity: O(log n) | ||||||||

Inserting AVL trees. | ||||||||

insertTreeL :: AVL e -> ZAVL e -> ZAVL 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. | ||||||||

insertTreeR :: ZAVL e -> AVL 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. | ||||||||

Current element status. | ||||||||

isLeftmost :: ZAVL e -> Bool | ||||||||

Returns Complexity: O(1) average, O(log n) worst case. | ||||||||

isRightmost :: ZAVL e -> Bool | ||||||||

Returns Complexity: O(1) average, O(log n) worst case. | ||||||||

sizeL :: ZAVL e -> Int | ||||||||

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. | ||||||||

sizeR :: 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. | ||||||||

Operations on whole zippers. | ||||||||

sizeZAVL :: ZAVL e -> Int | ||||||||

Counts the total number of elements in a ZAVL. Complexity: O(n) | ||||||||

A cheaper option is to use BAVL | ||||||||

These are a cheaper but more restrictive alternative to using the full Zipper.
They use "Binary Paths" (Ints) to point to a particular element of an If you subsequently decide you need a Zipper rather than a BAVL then some conversion utilities are provided. | ||||||||

Types. | ||||||||

data BAVL e | ||||||||

| ||||||||

Opening and closing. | ||||||||

genOpenBAVL :: (e -> Ordering) -> AVL e -> BAVL e | ||||||||

Search for an element in a Complexity: O(log n) | ||||||||

closeBAVL :: BAVL e -> AVL e | ||||||||

Returns the original tree, extracted from the Complexity: O(1) | ||||||||

Inspecting status. | ||||||||

fullBAVL :: BAVL e -> Bool | ||||||||

Returns Complexity: O(1) | ||||||||

emptyBAVL :: BAVL e -> Bool | ||||||||

Returns Complexity: O(1) | ||||||||

tryReadBAVL :: BAVL e -> Maybe e | ||||||||

Read the element value from a "full" Complexity: O(1) | ||||||||

readFullBAVL :: BAVL e -> e | ||||||||

Read the element value from a "full" Complexity: O(1) | ||||||||

Modifying the tree. | ||||||||

pushBAVL :: e -> BAVL e -> AVL e | ||||||||

If the Complexity: O(log n) | ||||||||

deleteBAVL :: BAVL e -> AVL e | ||||||||

If the Complexity: O(log n) (or O(1) for an empty | ||||||||

Converting to BAVL to Zipper. | ||||||||

These are O(log n) operations but with low constant factors because no comparisons are required (and the tree nodes on the path will most likely still be in cache as a result of opening the BAVL in the first place). | ||||||||

fullBAVLtoZAVL :: BAVL e -> ZAVL e | ||||||||

Converts a "full" Complexity: O(log n) | ||||||||

emptyBAVLtoPAVL :: BAVL e -> PAVL e | ||||||||

Converts an "empty" Complexity: O(log n) | ||||||||

anyBAVLtoEither :: BAVL e -> Either (PAVL e) (ZAVL e) | ||||||||

Converts a Complexity: O(log n) | ||||||||

Produced by Haddock version 0.7 |