RBTree 0.0.3 → 0.0.4

raw patch · 3 files changed

+138/−17 lines, 3 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Data/Tree/RBTree.lhs +116/−12
• RBTree.cabal +4/−4
• README +18/−1

@@ -7,10 +7,12 @@ > {-# LANGUAGE BangPatterns #-}  > module Data.Tree.RBTree-> (Color, RBTree, emptyRB,+> (Color (Red, Black), RBTree (Node, Leaf), emptyRB,+>  Interval (Interval), RealOrd (PInfinity, NInfinity, RealValue), >  insert, insertOrd, insertOrdList, >  delete, deleteOrd, deleteOrdList,->  search, searchOrd, searchFast,+>  search, searchOrd, searchFast, searchMax, searchMin,+>  searchInterval, searchIntervalOrd, >  vD, vR > ) > where@@ -29,7 +31,7 @@   RBZip is equivalent to RBTree in Logic.   All RBZip can be convert to a RBTree by Trace back to Root point. -> data Direction = ToLeft | ToRight deriving (Show,Eq)+> data Direction = ToLeft | ToRight deriving (Eq)  > data Path a = Path Color a Direction !(RBTree a) >               deriving (Show)@@ -37,11 +39,15 @@ > data RBZip a = RBZip !(RBTree a) ![Path a] >                deriving (Show) +> data Interval a = Interval (RealOrd a, RealOrd a)++> data RealOrd a = PInfinity | NInfinity | RealValue a+   Simply show tree in (), hard to read but easy to parse  > instance Show a => Show (RBTree a) where >     show (Node c v l r) = "(" ++ show l ++ show v ++ show c ++ show r ++ ")"->     show Leaf = []+>     show Leaf = "."    Red node shows '*' @@ -49,6 +55,18 @@ >     show Red = "*" >     show Black = "" +> instance Show Direction where+>     show ToLeft = "L"+>     show ToRight = "R"++> instance Show a => Show (RealOrd a) where+>     show PInfinity = "+INF"+>     show NInfinity = "-INF"+>     show (RealValue a) = show a++> instance Show a => Show (Interval a) where+>     show (Interval (l, r)) = "[" ++ show l ++ ", " ++ show r ++ "]"+ > emptyRB :: RBTree a  > emptyRB = Leaf@@ -83,6 +101,10 @@ > toTree z = tree >     where (RBZip tree _) = topMostZip z +> --getValueZip :: RBZip a -> Maybe a+> --getValueZip (RBZip Leaf _) = Nothing+> --getValueZip (RBZip (Node _ v _ _) _) = Just v+   Zip up.  > topMostZip :: RBZip a -> RBZip a@@ -94,12 +116,54 @@    Get the Leftmost non-leaf node from a Zip. -> leftmostZip :: RBZip a -> RBZip a+> leftMostZip :: RBZip a -> RBZip a -> leftmostZip this@(RBZip (Node _ _ Leaf _) _) = this-> leftmostZip (RBZip (Node c v l r) path) = leftmostZip (RBZip l ((Path c v ToLeft r):path))-> leftmostZip z = z+> leftMostZip this@(RBZip (Node _ _ Leaf _) _) = this+> leftMostZip (RBZip (Node c v l r) path) = leftMostZip (RBZip l ((Path c v ToLeft r):path))+> leftMostZip z = z --only when leaf itself from start over +> rightMostZip :: RBZip a -> RBZip a++> rightMostZip this@(RBZip (Node _ _ _ Leaf) _) = this+> rightMostZip (RBZip (Node c v l r) path) = rightMostZip (RBZip r ((Path c v ToRight l):path))+> rightMostZip z = z --leaf itself++> leftParentZip :: RBZip a -> RBZip a+> leftParentZip (RBZip l ((Path c v ToLeft r):path)) = leftParentZip (RBZip (Node c v l r) path)+> leftParentZip (RBZip r ((Path c v ToRight l):path)) = RBZip (Node c v l r) path+> leftParentZip (RBZip _ []) = RBZip Leaf [] -- no such parent, return a empty zip++> rightParentZip :: RBZip a -> RBZip a+> rightParentZip (RBZip r ((Path c v ToRight l):path)) = rightParentZip (RBZip (Node c v l r) path)+> rightParentZip (RBZip l ((Path c v ToLeft r):path)) = RBZip (Node c v l r) path+> rightParentZip (RBZip _ []) = RBZip Leaf [] -- no such parent, return a empty zip++  find predecessor/successor of a node/leaf++> predZip :: RBZip a -> RBZip a++> predZip (RBZip (Node c v l@(Node _ _ _ _) r) path) = rightMostZip (RBZip l ((Path c v ToLeft r):path))+> predZip z@(RBZip Leaf _) = case lp of+>   RBZip Leaf [] -> z -- itself+>   _ -> lp+>   where lp = leftParentZip z+> predZip z@(RBZip (Node c v l r) path) = case lp of+>   RBZip Leaf [] -> RBZip l ((Path c v ToLeft r):path)+>   _ -> lp+>   where lp = leftParentZip z++> succZip :: RBZip a -> RBZip a++> succZip (RBZip (Node c v l r@(Node _ _ _ _)) path) = leftMostZip (RBZip r ((Path c v ToRight l):path))+> succZip z@(RBZip Leaf _) = case lp of+>   RBZip Leaf [] -> z -- itself+>   _ -> lp+>   where lp = rightParentZip z+> succZip z@(RBZip (Node c v l r) path) = case lp of+>   RBZip Leaf [] -> RBZip r ((Path c v ToRight l):path)+>   _ -> lp+>   where lp = rightParentZip z+   Get the Leftmost non-leaf node's value from a Zip.   param 1 : current node's value.   param 2 : current node's left child.@@ -177,14 +241,14 @@  > searchOrd = search compare -> search :: (a -> a -> Ordering) -> RBTree a -> a -> Maybe a+> search :: (b -> a -> Ordering) -> RBTree a -> b -> Maybe a  > search f t v = case rZip of >     Just (RBZip (Node _ v' _ _) _) -> Just v' >     _ -> Nothing >     where rZip = searchZip f (toZip t) v -> searchFast :: (a -> a -> Ordering) -> RBTree a -> a -> Maybe a+> searchFast :: (b -> a -> Ordering) -> RBTree a -> b -> Maybe a  > searchFast f (Node _ v l r) vs = case f vs v of >     LT -> searchFast f l vs@@ -192,14 +256,54 @@ >     EQ -> Just v > searchFast _ Leaf _ = Nothing -> searchZip :: (a -> a -> Ordering) -> RBZip a -> a -> Maybe (RBZip a)+> searchMax :: (Ord a) => RBTree a -> Maybe a+> searchMax t = case r of+>     RBZip (Node _ v _ _) _ -> Just v+>     _ -> Nothing+>     where r = rightMostZip . toZip $ t +> searchMin :: (Ord a) => RBTree a -> Maybe a+> searchMin t = case r of+>     RBZip (Node _ v _ _) _ -> Just v+>     _ -> Nothing+>     where r = leftMostZip . toZip $ t+++> searchZip :: (b -> a -> Ordering) -> RBZip a -> b -> Maybe (RBZip a)+ > searchZip _ (RBZip Leaf _) _ = Nothing > searchZip f this@(RBZip (Node c v l r) path) vs = case f vs v of >     LT -> searchZip f (RBZip l ((Path c v ToLeft r):path)) vs >     GT -> searchZip f (RBZip r ((Path c v ToRight l):path)) vs >     EQ -> Just this +  searchZipTrace : always returns the current point that the search stops.+  returns a Zip-Node on equal, otherwise a Zip-Leaf++> searchZipTrace :: (b -> a -> Ordering) -> RBZip a -> b -> RBZip a+> searchZipTrace _ z@(RBZip Leaf _) _ = z+> searchZipTrace f this@(RBZip (Node c v l r) path) vs = case f vs v of+>     LT -> searchZipTrace f (RBZip l ((Path c v ToLeft r):path)) vs+>     GT -> searchZipTrace f (RBZip r ((Path c v ToRight l):path)) vs+>     EQ -> this++> searchIntervalOrd :: (Ord a) => RBTree a -> a -> Interval a+> searchIntervalOrd t a = searchInterval compare t a++  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++> searchInterval :: (b -> a -> Ordering) -> RBTree a -> b -> Interval a+> searchInterval f t a = case r of+>     RBZip Leaf _ -> Interval (toNRealOrd (predZip r), toPRealOrd (succZip r))+>     _ -> Interval (toNRealOrd r, toPRealOrd r)+>     where r = searchZipTrace f (toZip t) a+>           toNRealOrd (RBZip Leaf _) = NInfinity+>           toNRealOrd (RBZip (Node _ v _ _) _) = RealValue v+>           toPRealOrd (RBZip Leaf _) = PInfinity+>           toPRealOrd (RBZip (Node _ v _ _) _) = RealValue v+   delete functions.   If there is no 'a' in tree, tree will be returned unmodified. @@ -237,7 +341,7 @@   case 3: both not null  > deleteZip (RBZip (Node c _ l r@(Node _ vr srl _)) path) = deleteZip newX->     where !newX = leftmostZip (RBZip r ((Path c newV ToRight l):path))+>     where !newX = leftMostZip (RBZip r ((Path c newV ToRight l):path)) >           !newV = leftmostV vr srl    fixup : 

@@ -1,12 +1,12 @@ Name:              RBTree-Version:           0.0.3+Version:           0.0.4 Synopsis:          Pure haskell Red-Black-Tree implemetation Description:       This package implemets Red-Black tree data-structure. homepage:          git://github.com/wuxb45/Haskell-RBTree.git License:           BSD3 License-file:      LICENSE Author:            Wu Xingbo-Copyright:         2011 Wu Xingbo (wuxb45@gmail.com)+Copyright:         2010-2011 Wu Xingbo (wuxb45@gmail.com) Maintainer:        Wu Xingbo Bug-reports:       mailto:wuxb45@gmail.com Category:          Data Structures@@ -17,7 +17,7 @@  Library   Build-Depends:   base > 3 && < 5-  Exposed-modules:  -    Data.Tree.RBTree, +  Exposed-modules:+    Data.Tree.RBTree,     Data.Tree.RBTreeTest   ghc-options:     -Wall -funbox-strict-fields -optc-O2

@@ -1,6 +1,9 @@ Pure haskell implementation from Wu Xingbo (wuxb45@gmail.com) 2011 -to build & install for yourself:+WARNING:This Implementation mainly concerns about functionality. +  After that I will improve the performence and efficiency.++to Build & Install for yourself: shell> runhaskell Setup.lhs configure --user shell> runhaskell Setup.lhs build shell> runhaskell Setup.lhs install@@ -26,4 +29,18 @@ change log (0.0.3): add function "searchFast". rename 'remove*' functions to 'delete*'s.++change log (0.0.4):+add functions for search min/max value.+add functions for search for a interval that the two values in the tree holds the given value+modified search functions can accept a 'compare' function like:+    (b -> a -> Ordering)+  search for an 'a' by first key of a (RBTree (a,b)) canbe done in such way:+> b :: Int+> b = 10+> t :: RBTree (Int,String)+> t = insertOrdList emptyRB [(1,"hello"), (2,"world")]+> result :: (Int,String)+> result = search (\k (k',_) -> k `compare` k') t 2+it returns "Just (2,"world")"