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`