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

Stability | experimental |

Maintainer | Edward Kmett <ekmett@gmail.com> |

Safe Haskell | Safe-Inferred |

Provides online calculation of the the lowest common ancestor in *O(log h)*
by compressing the spine of a `Path`

using a skew-binary random access
list.

This library implements the technique described in my talk

http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search

to improve the known asymptotic bounds on both online lowest common ancestor search

http://en.wikipedia.org/wiki/Lowest_common_ancestor

and the online level ancestor problem:

http://en.wikipedia.org/wiki/Level_ancestor_problem

Algorithms used here assume that the key values chosen for `k`

are
globally unique.

- data Path a
- lca :: Path a -> Path b -> Path a
- empty :: Path a
- cons :: Int -> a -> Path a -> Path a
- uncons :: Path a -> Maybe (Int, a, Path a)
- view :: Path a -> View Path a
- null :: Path a -> Bool
- length :: Path a -> Int
- isAncestorOf :: Path a -> Path b -> Bool
- keep :: Int -> Path a -> Path a
- drop :: Int -> Path a -> Path a
- traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b)
- toList :: Path a -> [(Int, a)]
- fromList :: [(Int, a)] -> Path a
- (~=) :: Path a -> Path b -> Bool

# Documentation

Compressed paths using skew binary random access lists

cons :: Int -> a -> Path a -> Path aSource

*O(1)* Invariant: most operations assume that the keys `k`

are globally unique

Extend the `Path`

with a new node ID and value.

uncons :: Path a -> Maybe (Int, a, Path a)Source

*O(1)* Extract the node ID and value from the newest node on the `Path`

.

isAncestorOf :: Path a -> Path b -> BoolSource

*O(log h)* `xs `

holds when `isAncestorOf`

ys`xs`

is a prefix starting at the root of `Path`

`ys`

.

traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b)Source

Traverse a `Path`

with access to the node IDs.