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