Haskell Hierarchical Libraries (collections package)ContentsIndex
Data.Tree.AVL.Internals.HSet
Portabilityportable
Stabilitystable
Maintainerhttp://homepages.nildram.co.uk/~ahey/em.png
Contents
Union primitives.
Intersection primitives.
Difference primitives.
Description
Set primitives on AVL trees with (height information supplied where needed). All the functions in this module use essentially the same symetric "Divide and Conquer" algorithm.
Synopsis
unionH :: (e -> e -> COrdering e) -> AVL e -> Int# -> AVL e -> Int# -> (#AVL e, Int##)
unionMaybeH :: (e -> e -> COrdering (Maybe e)) -> AVL e -> Int# -> AVL e -> Int# -> (#AVL e, Int##)
intersectionH :: (a -> b -> COrdering c) -> AVL a -> AVL b -> (#AVL c, Int##)
intersectionMaybeH :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> (#AVL c, Int##)
differenceH :: (a -> b -> Ordering) -> AVL a -> Int# -> AVL b -> (#AVL a, Int##)
differenceMaybeH :: (a -> b -> COrdering (Maybe a)) -> AVL a -> Int# -> AVL b -> (#AVL a, Int##)
symDifferenceH :: (e -> e -> Ordering) -> AVL e -> Int# -> AVL e -> Int# -> (#AVL e, Int##)
Union primitives.
unionH :: (e -> e -> COrdering e) -> AVL e -> Int# -> AVL e -> Int# -> (#AVL e, Int##)

Uses the supplied combining comparison to evaluate the union of two sets represented as sorted AVL trees of known height. Whenever the combining comparison is applied, the first comparison argument is an element of the first tree and the second comparison argument is an element of the second tree.

Complexity: Not sure, but I'd appreciate it if someone could figure it out. (Faster than Hedge union from Data.Set at any rate).

unionMaybeH :: (e -> e -> COrdering (Maybe e)) -> AVL e -> Int# -> AVL e -> Int# -> (#AVL e, Int##)

Similar to _unionH_, but the resulting tree does not include elements in cases where the supplied combining comparison returns (Eq Nothing).

Complexity: Not sure, but I_d appreciate it if someone could figure it out.

Intersection primitives.
intersectionH :: (a -> b -> COrdering c) -> AVL a -> AVL b -> (#AVL c, Int##)

Uses the supplied combining comparison to evaluate the intersection of two sets represented as sorted AVL trees. This function requires no height information at all for the two tree inputs. The absolute height of the resulting tree is returned also.

Complexity: Not sure, but I_d appreciate it if someone could figure it out.

intersectionMaybeH :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> (#AVL c, Int##)

Similar to _intersectionH_, but the resulting tree does not include elements in cases where the supplied combining comparison returns (Eq Nothing).

Complexity: Not sure, but I_d appreciate it if someone could figure it out.

Difference primitives.
differenceH :: (a -> b -> Ordering) -> AVL a -> Int# -> AVL b -> (#AVL a, Int##)

Uses the supplied comparison to evaluate the difference between two sets represented as sorted AVL trees.

N.B. This function works with relative heights for the first tree and needs no height information for the second tree, so it_s OK to initialise the height of the first to zero, rather than calculating the absolute height. However, if you do this the height of the resulting tree will be incorrect also (it will have the same fixed offset as the first tree).

Complexity: Not sure, but I_d appreciate it if someone could figure it out.

differenceMaybeH :: (a -> b -> COrdering (Maybe a)) -> AVL a -> Int# -> AVL b -> (#AVL a, Int##)

Similar to _differenceH_, but the resulting tree also includes those elements a_ for which the combining comparison returns Eq (Just a_).

N.B. This function works with relative heights for the first tree and needs no height information for the second tree, so it_s OK to initialise the height of the first to zero, rather than calculating the absolute height. However, if you do this the height of the resulting tree will be incorrect also (it will have the same fixed offset as the first tree).

Complexity: Not sure, but I_d appreciate it if someone could figure it out.

symDifferenceH :: (e -> e -> Ordering) -> AVL e -> Int# -> AVL e -> Int# -> (#AVL e, Int##)

The symmetric difference is the set of elements which occur in one set or the other but not both.

Complexity: Not sure, but I_d appreciate it if someone could figure it out.

Produced by Haddock version 0.7