On Tue, Aug 04, 2015 at 03:39:25PM +0200, Klaus Aehlig wrote:
From: Niklas Hambuechen <[email protected]>
For n*log(n) duplicate removal (as opposed to nub's n^2).
Signed-off-by: Niklas Hambuechen <[email protected]>
Signed-off-by: Petr Pudlak <[email protected]>
Reviewed-by: Klaus Aehlig <[email protected]>
Cherry-picked-from: 5dd8067d
Signed-off-by: Klaus Aehlig <[email protected]>
---
src/Ganeti/Utils.hs | 10 ++++++++++
1 file changed, 10 insertions(+)
diff --git a/src/Ganeti/Utils.hs b/src/Ganeti/Utils.hs
index e3d865f..6e342d1 100644
--- a/src/Ganeti/Utils.hs
+++ b/src/Ganeti/Utils.hs
@@ -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
--
2.5.0.rc2.392.g76e840b
LGTM
