Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell98 |
Pure Haskell Red-Black tree implementation
Synopsis
- data Color
- data RBTree a
- emptyRB :: RBTree a
- data Interval a = Interval (RealOrd a, RealOrd a)
- data RealOrd a
- (<</) :: Ord a => RBTree a -> a -> RBTree a
- insert :: (a -> a -> Ordering) -> RBTree a -> a -> RBTree a
- insertOrd :: Ord a => RBTree a -> a -> RBTree a
- insertOrdList :: Ord a => RBTree a -> [a] -> RBTree a
- (<<\) :: Ord a => RBTree a -> a -> RBTree a
- delete :: (a -> a -> Ordering) -> RBTree a -> a -> RBTree a
- deleteOrd :: Ord a => RBTree a -> a -> RBTree a
- deleteOrdList :: Ord a => RBTree a -> [a] -> RBTree a
- (<<?) :: Ord a => RBTree a -> a -> Maybe a
- search :: (b -> a -> Ordering) -> RBTree a -> b -> Maybe a
- searchOrd :: Ord a => RBTree a -> a -> Maybe a
- searchFast :: (b -> a -> Ordering) -> RBTree a -> b -> Maybe a
- searchMax :: Ord a => RBTree a -> Maybe a
- searchMin :: Ord a => RBTree a -> Maybe a
- searchInterval :: (b -> a -> Ordering) -> RBTree a -> b -> Interval a
- searchIntervalOrd :: Ord a => RBTree a -> a -> Interval a
- vD :: RBTree a -> Maybe Int
- vR :: RBTree a -> Bool
Tree Types
Color of a Node
.
Leaf is assumed to be Black.
Basic RBTree Structure.
Interval Types
used for range query.
Interval value from -INF to +INF.
Insertion
insert :: (a -> a -> Ordering) -> RBTree a -> a -> RBTree a Source #
Insert anything. |you have to provide a compare function.
Delete
delete :: (a -> a -> Ordering) -> RBTree a -> a -> RBTree a Source #
If there is no relevant element in tree, tree will be returned unmodified.
Search
search :: (b -> a -> Ordering) -> RBTree a -> b -> Maybe a Source #
search for any thing, you should provide proper compare function.
searchFast :: (b -> a -> Ordering) -> RBTree a -> b -> Maybe a Source #
a faster search
function implemetation. strongly recommanded.
searchMax :: Ord a => RBTree a -> Maybe a Source #
Search the Maximum value in the tree, equals to get the right-most element.
searchMin :: Ord a => RBTree a -> Maybe a Source #
Search the Minimum value in the tree, equals to get the left-most element.
searchInterval :: (b -> a -> Ordering) -> RBTree a -> b -> Interval a Source #
Search for a Interval.
For example: tree has 1,3,5,7. search for 3 returns [3,3] that indicates itself search for 4 returns [3,5] indicates that 4 is between the element 3 and 5
The given value be or not be an element of the tree.
searchIntervalOrd :: Ord a => RBTree a -> a -> Interval a Source #
Search 'Ord' things, see searchInterval