[commit: Cabal] master: Add new utils, duplicates, duplicatesBy and mergeBy (c36a533)

[Paolo Capriotti]

Repository : ssh://darcs.haskell.org//srv/darcs/packages/Cabal

On branch  : master

http://hackage.haskell.org/trac/ghc/changeset/c36a533498276c405625bfa540bdc70f9ac0646d

>---------------------------------------------------------------

commit c36a533498276c405625bfa540bdc70f9ac0646d
Author: Duncan Coutts <duncan at haskell.org>
Date:   Sun May 4 19:45:30 2008 +0000

    Add new utils, duplicates, duplicatesBy and mergeBy

>---------------------------------------------------------------

 cabal-install/Hackage/Utils.hs |   31 +++++++++++++++++++++++++++++++
 1 files changed, 31 insertions(+), 0 deletions(-)

diff --git a/cabal-install/Hackage/Utils.hs b/cabal-install/Hackage/Utils.hs
index 38dd73c..35a00e9 100644
--- a/cabal-install/Hackage/Utils.hs
+++ b/cabal-install/Hackage/Utils.hs
@@ -6,6 +6,8 @@ import Distribution.Text
          ( display )
 import Distribution.Simple.Utils (intercalate)
 
+import Data.List
+         ( sortBy, groupBy )
 import Control.Monad (guard)
 import Control.Exception (Exception, catchJust, ioErrors)
 import System.IO.Error (isDoesNotExistError)
@@ -22,3 +24,32 @@ fileNotFoundExceptions e =
 
 showDependencies :: [Dependency] -> String
 showDependencies = intercalate ", " . map display
+
+-- | Generic merging utility. For sorted input lists this is a full outer join.
+--
+-- * The result list never contains @(Nothing, Nothing)@.
+--
+mergeBy :: (a -> b -> Ordering) -> [a] -> [b] -> [MergeResult a b]
+mergeBy cmp = merge
+  where
+    merge []     ys     = [ OnlyInRight y | y <- ys]
+    merge xs     []     = [ OnlyInLeft  x | x <- xs]
+    merge (x:xs) (y:ys) =
+      case x `cmp` y of
+        GT -> OnlyInRight   y : merge (x:xs) ys
+        EQ -> InBoth      x y : merge xs     ys
+        LT -> OnlyInLeft  x   : merge xs  (y:ys)
+
+data MergeResult a b = OnlyInLeft a | InBoth a b | OnlyInRight b
+
+duplicates :: Ord a => [a] -> [[a]]
+duplicates = duplicatesBy compare
+
+duplicatesBy :: (a -> a -> Ordering) -> [a] -> [[a]]
+duplicatesBy cmp = filter moreThanOne . groupBy eq . sortBy cmp
+  where
+    eq a b = case cmp a b of
+               EQ -> True
+               _  -> False
+    moreThanOne (_:_:_) = True
+    moreThanOne _       = False