Utils: Add ordNub
authorNiklas Hambuechen <niklash@google.com>
Fri, 1 Aug 2014 15:27:11 +0000 (17:27 +0200)
committerKlaus Aehlig <aehlig@google.com>
Tue, 4 Aug 2015 14:56:01 +0000 (16:56 +0200)
For n*log(n) duplicate removal (as opposed to nub's n^2).

Signed-off-by: Niklas Hambuechen <niklash@google.com>
Signed-off-by: Petr Pudlak <pudlak@google.com>
Reviewed-by: Klaus Aehlig <aehlig@google.com>

Cherry-picked-from: 5dd8067d
Signed-off-by: Klaus Aehlig <aehlig@google.com>
Reviewed-by: Petr Pudlak <pudlak@google.com>

src/Ganeti/Utils.hs

index e3d865f..6e342d1 100644 (file)
@@ -90,6 +90,7 @@ module Ganeti.Utils
   , safeRenameFile
   , FilePermissions(..)
   , ensurePermissions
+  , ordNub
   ) where
 
 import Control.Concurrent
@@ -751,3 +752,12 @@ safeRenameFile perms from to = do
         _ <- ensurePermissions dir perms
         renameFile from to
       return $ either (Bad . show) Ok (result :: Either IOError ())
+
+-- | Removes duplicates, preserving order.
+ordNub :: (Ord a) => [a] -> [a]
+ordNub =
+  let go _ [] = []
+      go s (x:xs) = if x `S.member` s
+        then go s xs
+        else x : go (S.insert x s) xs
+  in go S.empty