Portability | portable |
---|---|

Stability | stable |

Maintainer | http://homepages.nildram.co.uk/~ahey/em.png |

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 `BAVL`

as a cheaper alternative if you don't actually
need to navigate the tree.

- data ZAVL e
- data PAVL e
- assertOpenL :: AVL e -> ZAVL e
- assertOpenR :: AVL e -> ZAVL e
- tryOpenL :: AVL e -> Maybe (ZAVL e)
- tryOpenR :: AVL e -> Maybe (ZAVL e)
- genAssertOpen :: (e -> Ordering) -> AVL e -> ZAVL e
- genTryOpen :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e)
- genTryOpenGE :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e)
- genTryOpenLE :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e)
- genOpenEither :: (e -> Ordering) -> AVL e -> Either (PAVL e) (ZAVL e)
- close :: ZAVL e -> AVL e
- fillClose :: e -> PAVL e -> AVL e
- getCurrent :: ZAVL e -> e
- putCurrent :: e -> ZAVL e -> ZAVL e
- applyCurrent :: (e -> e) -> ZAVL e -> ZAVL e
- applyCurrent' :: (e -> e) -> ZAVL e -> ZAVL e
- assertMoveL :: ZAVL e -> ZAVL e
- assertMoveR :: ZAVL e -> ZAVL e
- tryMoveL :: ZAVL e -> Maybe (ZAVL e)
- tryMoveR :: ZAVL e -> Maybe (ZAVL e)
- insertL :: e -> ZAVL e -> ZAVL e
- insertR :: ZAVL e -> e -> ZAVL e
- insertMoveL :: e -> ZAVL e -> ZAVL e
- insertMoveR :: ZAVL e -> e -> ZAVL e
- fill :: e -> PAVL e -> ZAVL e
- delClose :: ZAVL e -> AVL e
- assertDelMoveL :: ZAVL e -> ZAVL e
- assertDelMoveR :: ZAVL e -> ZAVL e
- tryDelMoveR :: ZAVL e -> Maybe (ZAVL e)
- tryDelMoveL :: ZAVL e -> Maybe (ZAVL e)
- delAllL :: ZAVL e -> ZAVL e
- delAllR :: ZAVL e -> ZAVL e
- delAllCloseL :: ZAVL e -> AVL e
- delAllCloseR :: ZAVL e -> AVL e
- delAllIncCloseL :: ZAVL e -> AVL e
- delAllIncCloseR :: ZAVL e -> AVL e
- insertTreeL :: AVL e -> ZAVL e -> ZAVL e
- insertTreeR :: ZAVL e -> AVL e -> ZAVL e
- isLeftmost :: ZAVL e -> Bool
- isRightmost :: ZAVL e -> Bool
- sizeL :: ZAVL e -> Int
- sizeR :: ZAVL e -> Int
- sizeZAVL :: ZAVL e -> Int
- data BAVL e
- genOpenBAVL :: (e -> Ordering) -> AVL e -> BAVL e
- closeBAVL :: BAVL e -> AVL e
- fullBAVL :: BAVL e -> Bool
- emptyBAVL :: BAVL e -> Bool
- tryReadBAVL :: BAVL e -> Maybe e
- readFullBAVL :: BAVL e -> e
- pushBAVL :: e -> BAVL e -> AVL e
- deleteBAVL :: BAVL e -> AVL e
- fullBAVLtoZAVL :: BAVL e -> ZAVL e
- emptyBAVLtoPAVL :: BAVL e -> PAVL e
- anyBAVLtoEither :: BAVL e -> Either (PAVL e) (ZAVL e)

# Types.

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.

# Opening.

assertOpenL :: AVL e -> ZAVL eSource

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 eSource

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)Source

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)

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

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)

genAssertOpen :: (e -> Ordering) -> AVL e -> ZAVL eSource

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)Source

Attempts to open a sorted AVL tree at the element given by the supplied selector.
This function returns `Nothing`

if there is no such element.

Note that this operation will still create a zipper path structure on the heap (which
is promptly discarded) if the search fails, and so is potentially inefficient if failure
is likely. In cases like this it may be better to use `genOpenBAVL`

, test for "fullness"
using `fullBAVL`

and then convert to a `ZAVL`

using `fullBAVLtoZAVL`

.

Complexity: O(log n)

genTryOpenGE :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e)Source

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)

genTryOpenLE :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e)Source

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)

# Closing.

# Manipulating the current element.

getCurrent :: ZAVL e -> eSource

Gets the current element of a Zipper.

Complexity: O(1)

putCurrent :: e -> ZAVL e -> ZAVL eSource

Overwrites the current element of a Zipper.

Complexity: O(1)

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

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 eSource

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)

# Moving.

assertMoveL :: ZAVL e -> ZAVL eSource

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 eSource

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)Source

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.

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

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.

# Inserting elements.

insertL :: e -> ZAVL e -> ZAVL eSource

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 eSource

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 eSource

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 eSource

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.

# Deleting elements.

delClose :: ZAVL e -> AVL eSource

Deletes the current element and then closes the Zipper.

Complexity: O(log n)

assertDelMoveL :: ZAVL e -> ZAVL eSource

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 eSource

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)Source

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.

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

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.

delAllL :: ZAVL e -> ZAVL eSource

Delete all elements to the left of the current element.

Complexity: O(log n)

delAllR :: ZAVL e -> ZAVL eSource

Delete all elements to the right of the current element.

Complexity: O(log n)

delAllCloseL :: ZAVL e -> AVL eSource

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)

delAllCloseR :: ZAVL e -> AVL eSource

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)

delAllIncCloseL :: ZAVL e -> AVL eSource

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)

delAllIncCloseR :: ZAVL e -> AVL eSource

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)

# Inserting AVL trees.

insertTreeL :: AVL e -> ZAVL e -> ZAVL eSource

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 eSource

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

Returns `True`

if the current element is the leftmost element.

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

isRightmost :: ZAVL e -> BoolSource

Returns `True`

if the current element is the rightmost element.

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

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.

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.

# 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 `AVL`

tree.
Use these when you don't need to navigate the tree, you just want to look at a
particular element (and perhaps modify or delete it). The advantage of these is
that they don't create the usual Zipper heap structure, so they will be faster
(and reduce heap burn rate too).

If you subsequently decide you need a Zipper rather than a BAVL then some conversion utilities are provided.

## Types.

## Opening and closing.

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

closeBAVL :: BAVL e -> AVL eSource

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)

## Inspecting status.

tryReadBAVL :: BAVL e -> Maybe eSource

readFullBAVL :: BAVL e -> eSource

## Modifying the tree.

pushBAVL :: e -> BAVL e -> AVL eSource

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)

deleteBAVL :: BAVL e -> AVL eSource

## 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 eSource

emptyBAVLtoPAVL :: BAVL e -> PAVL eSource