| |||||||||||||

| |||||||||||||

| |||||||||||||

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

| |||||||||||||

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 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 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 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 Complexity: Not sure, but I_d appreciate it if someone could figure it out. | |||||||||||||

Produced by Haddock version 0.7 |