Copyright	(C) 2011-2015 Edward Kmett
License	BSD-style (see the file LICENSE)
Maintainer	Edward Kmett <ekmett@gmail.com>
Stability	experimental
Portability	portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.LCA.Online.Naive

Description

Naive online calculation of the the lowest common ancestor in O(h)

Synopsis

data 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
lca :: Path a -> Path b -> Path a
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

data Path a Source #

An uncompressed Path with memoized length.

Instances

Instances details

Functor Path Source #
Instance details Defined in Data.LCA.Online.Naive Methods fmap :: (a -> b) -> Path a -> Path b # (<$) :: a -> Path b -> Path a #
Foldable Path Source #
Instance details Defined in Data.LCA.Online.Naive Methods fold :: Monoid m => Path m -> m # foldMap :: Monoid m => (a -> m) -> Path a -> m # foldMap' :: Monoid m => (a -> m) -> Path a -> m # foldr :: (a -> b -> b) -> b -> Path a -> b # foldr' :: (a -> b -> b) -> b -> Path a -> b # foldl :: (b -> a -> b) -> b -> Path a -> b # foldl' :: (b -> a -> b) -> b -> Path a -> b # foldr1 :: (a -> a -> a) -> Path a -> a # foldl1 :: (a -> a -> a) -> Path a -> a # toList :: Path a -> [a] # null :: Path a -> Bool # length :: Path a -> Int # elem :: Eq a => a -> Path a -> Bool # maximum :: Ord a => Path a -> a # minimum :: Ord a => Path a -> a # sum :: Num a => Path a -> a # product :: Num a => Path a -> a #
Traversable Path Source #
Instance details Defined in Data.LCA.Online.Naive Methods traverse :: Applicative f => (a -> f b) -> Path a -> f (Path b) # sequenceA :: Applicative f => Path (f a) -> f (Path a) # mapM :: Monad m => (a -> m b) -> Path a -> m (Path b) # sequence :: Monad m => Path (m a) -> m (Path a) #
Read a => Read (Path a) Source #
Instance details Defined in Data.LCA.Online.Naive Methods readsPrec :: Int -> ReadS (Path a) # readList :: ReadS [Path a] # readPrec :: ReadPrec (Path a) # readListPrec :: ReadPrec [Path a] #
Show a => Show (Path a) Source #
Instance details Defined in Data.LCA.Online.Naive Methods showsPrec :: Int -> Path a -> ShowS # show :: Path a -> String # showList :: [Path a] -> ShowS #

empty :: Path a Source #

The empty Path

cons :: Int -> a -> Path a -> Path a Source #

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.

view :: Path a -> View Path a Source #

O(1) Extract the node ID and value from the newest node on the Path, slightly faster than uncons.

null :: Path a -> Bool Source #

O(1) Returns True iff the Path is empty.

length :: Path a -> Int Source #

O(1) Determine the length of a Path.

isAncestorOf :: Path a -> Path b -> Bool Source #

O(h) xs isAncestorOf ys holds when xs is a prefix starting at the root of Path ys.

lca :: Path a -> Path b -> Path a Source #

O(h) Compute the lowest common ancestor of two paths

>>> let fromList' = fromList . map (flip (,) ())
>>> length (lca (fromList' [1, 2, 3, 4, 5, 6]) (fromList' [7, 8, 3, 4, 5, 6]))
4

keep :: Int -> Path a -> Path a Source #

O(h - k) to keep k elements of Path of length h

drop :: Int -> Path a -> Path a Source #

O(k) to drop k elements from a Path

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

Traverse a Path with access to the node IDs.

toList :: Path a -> [(Int, a)] Source #

Convert a Path to a list of (ID, value) pairs.

fromList :: [(Int, a)] -> Path a Source #

Build a Path from a list of (ID, value) pairs.

(~=) :: Path a -> Path b -> Bool infix 4 Source #

O(1) Compare to see if two trees have the same root key