Data.Tree.AVL.Zipper

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.

Types.

data ZAVL e

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 PAVL e

Abstract data type for an unsuccessfully opened AVL tree. A PAVL can be tought 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.

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 Nothing if the tree is empty.

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 Nothing if the tree is empty.

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

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)

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

Closing.

close :: ZAVL e -> AVL e

Closes a Zipper.

Complexity: O(log n)

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

Essentially the same operation as fill, but the resulting ZAVL is closed immediately.

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

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

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

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

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

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

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

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 True if the current element is the leftmost element.

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

isRightmost :: ZAVL e -> Bool

Returns True if the current element is the rightmost element.

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

data BAVL e

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

Opening and closing.

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

closeBAVL :: BAVL e -> AVL 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)

Inspecting status.

fullBAVL :: BAVL e -> Bool

Returns True if the BAVL is "full" (a corresponding element was found).

Complexity: O(1)

emptyBAVL :: BAVL e -> Bool

Returns True if the BAVL is "empty" (no corresponding element was found).

Complexity: O(1)

tryReadBAVL :: BAVL e -> Maybe e

Read the element value from a "full" BAVL. This function returns Nothing if applied to an "empty" BAVL.

Complexity: O(1)

readFullBAVL :: BAVL e -> e

Read the element value from a "full" BAVL. This function raises an error if applied to an "empty" BAVL.

Complexity: O(1)

Modifying the tree.

pushBAVL :: e -> BAVL e -> AVL 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)

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

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" BAVL as a ZAVL. Raises an error if applied to an "empty" BAVL.

Complexity: O(log n)

emptyBAVLtoPAVL :: BAVL e -> PAVL e

Converts an "empty" BAVL as a PAVL. Raises an error if applied to a "full" BAVL.

Complexity: O(log n)

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

Converts a BAVL to either a PAVL or ZAVL (depending on whether it is "empty" or "full").

Complexity: O(log n)