O(n) fromAscList IntSet / IntMap
authorsedillard@gmail.com <unknown>
Wed, 21 May 2008 19:59:41 +0000 (19:59 +0000)
committersedillard@gmail.com <unknown>
Wed, 21 May 2008 19:59:41 +0000 (19:59 +0000)
Added algorithm by Scott Dillard and Bertram Felgenhauer to build IntSets and
IntMaps from sorted input in linear time. Also changed quickcheck prop_Ordered
(no longer a tautology!) to include negative and duplicate keys.

Data/IntMap.hs
Data/IntSet.hs
Data/Set.hs

index 1e21574..6ad151d 100644 (file)
@@ -173,7 +173,7 @@ import Control.Monad ( liftM )
 {-
 -- just for testing
 import qualified Prelude
-import Debug.QuickCheck 
+import Test.QuickCheck 
 import List (nub,sort)
 import qualified List
 -}  
@@ -1452,7 +1452,7 @@ fromListWithKey f xs
   where
     ins t (k,x) = insertWithKey f k x t
 
--- | /O(n*min(n,W))/. Build a map from a list of key\/value pairs where
+-- | /O(n)/. Build a map from a list of key\/value pairs where
 -- the keys are in ascending order.
 --
 -- > fromAscList [(3,"b"), (5,"a")]          == fromList [(3, "b"), (5, "a")]
@@ -1460,34 +1460,62 @@ fromListWithKey f xs
 
 fromAscList :: [(Key,a)] -> IntMap a
 fromAscList xs
-  = fromList xs
+  = fromAscListWithKey (\k x y -> x) xs
 
--- | /O(n*min(n,W))/. Build a map from a list of key\/value pairs where
+-- | /O(n)/. Build a map from a list of key\/value pairs where
 -- the keys are in ascending order, with a combining function on equal keys.
+-- /The precondition (input list is ascending) is not checked./
 --
 -- > fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
 
 fromAscListWith :: (a -> a -> a) -> [(Key,a)] -> IntMap a
 fromAscListWith f xs
-  = fromListWith f xs
+  = fromAscListWithKey (\k x y -> f x y) xs
 
--- | /O(n*min(n,W))/. Build a map from a list of key\/value pairs where
+-- | /O(n)/. Build a map from a list of key\/value pairs where
 -- the keys are in ascending order, with a combining function on equal keys.
+-- /The precondition (input list is ascending) is not checked./
 --
 -- > fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
 
 fromAscListWithKey :: (Key -> a -> a -> a) -> [(Key,a)] -> IntMap a
-fromAscListWithKey f xs
-  = fromListWithKey f xs
+fromAscListWithKey _ []     = Nil
+fromAscListWithKey f (x:xs) = fromDistinctAscList (combineEq x xs)
+  where
+    -- [combineEq f xs] combines equal elements with function [f] in an ordered list [xs]
+    combineEq z [] = [z]
+    combineEq z@(kz,zz) (x@(kx,xx):xs)
+      | kx==kz    = let yy = f kx xx zz in combineEq (kx,yy) xs
+      | otherwise = z:combineEq x xs
 
--- | /O(n*min(n,W))/. Build a map from a list of key\/value pairs where
+-- | /O(n)/. Build a map from a list of key\/value pairs where
 -- the keys are in ascending order and all distinct.
+-- /The precondition (input list is strictly ascending) is not checked./
 --
 -- > fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
 
 fromDistinctAscList :: [(Key,a)] -> IntMap a
-fromDistinctAscList xs
-  = fromList xs
+fromDistinctAscList []     = Nil
+fromDistinctAscList (z:zs) = work z zs Nada
+  where
+    work x@(kx,vx) []            stk = finish kx (Tip kx vx) stk
+    work x@(kx,vx) (z@(kz,_):zs) stk = reduce z zs (branchMask kx kz) kx (Tip kx vx) stk
+
+    reduce :: (Key,a) -> [(Key,a)] -> Mask -> Prefix -> IntMap a -> Stack a -> IntMap a
+    reduce z zs _ px tx Nada = work z zs (Push px tx Nada)
+    reduce z zs m px tx stk@(Push py ty stk') =
+        let mxy = branchMask px py
+            pxy = mask px mxy
+        in  if shorter m mxy
+                 then reduce z zs m pxy (Bin pxy mxy ty tx) stk'
+                 else work z zs (Push px tx stk)
+
+    finish _  t  Nada = t
+    finish px tx (Push py ty stk) = finish p (join py ty px tx) stk
+        where m = branchMask px py
+              p = mask px m
+
+data Stack a = Push {-# UNPACK #-} !Prefix !(IntMap a) !(Stack a) | Nada
 
 
 {--------------------------------------------------------------------
@@ -1847,7 +1875,7 @@ prop_Int xs ys
 --------------------------------------------------------------------}
 prop_Ordered
   = forAll (choose (5,100)) $ \n ->
-    let xs = [(x,()) | x <- [0..n::Int]] 
+    let xs = concat [[(x-n,()),(x-n,())] | x <- [0..2*n::Int]] 
     in fromAscList xs == fromList xs
 
 prop_List :: [Key] -> Bool
index c563d1c..551067b 100644 (file)
@@ -670,15 +670,40 @@ fromList xs
   where
     ins t x  = insert x t
 
--- | /O(n*min(n,W))/. Build a set from an ascending list of elements.
+-- | /O(n)/. Build a set from an ascending list of elements.
+-- /The precondition (input list is ascending) is not checked./
 fromAscList :: [Int] -> IntSet 
-fromAscList xs
-  = fromList xs
-
--- | /O(n*min(n,W))/. Build a set from an ascending list of distinct elements.
+fromAscList [] = Nil
+fromAscList (x:xs) = fromDistinctAscList (combineEq x xs)
+  where 
+    combineEq x' [] = [x']
+    combineEq x' (x:xs) 
+      | x==x'     = combineEq x' xs
+      | otherwise = x' : combineEq x xs
+
+-- | /O(n)/. Build a set from an ascending list of distinct elements.
+-- /The precondition (input list is strictly ascending) is not checked./
 fromDistinctAscList :: [Int] -> IntSet
-fromDistinctAscList xs
-  = fromList xs
+fromDistinctAscList []     = Nil
+fromDistinctAscList (z:zs) = work z zs Nada
+  where
+    work x []     stk = finish x (Tip x) stk
+    work x (z:zs) stk = reduce z zs (branchMask z x) x (Tip x) stk
+
+    reduce z zs _ px tx Nada = work z zs (Push px tx Nada)
+    reduce z zs m px tx stk@(Push py ty stk') =
+        let mxy = branchMask px py
+            pxy = mask px mxy
+        in  if shorter m mxy
+                 then reduce z zs m pxy (Bin pxy mxy ty tx) stk'
+                 else work z zs (Push px tx stk)
+
+    finish _  t  Nada = t
+    finish px tx (Push py ty stk) = finish p (join py ty px tx) stk
+        where m = branchMask px py
+              p = mask px m
+
+data Stack = Push {-# UNPACK #-} !Prefix !IntSet !Stack | Nada
 
 
 {--------------------------------------------------------------------
@@ -1024,7 +1049,7 @@ prop_Int xs ys
 --------------------------------------------------------------------}
 prop_Ordered
   = forAll (choose (5,100)) $ \n ->
-    let xs = [0..n::Int]
+    let xs = concat [[i-n,i-n]|i<-[0..2*n :: Int]]
     in fromAscList xs == fromList xs
 
 prop_List :: [Int] -> Bool
index b326605..c19ca27 100644 (file)
@@ -1,3 +1,4 @@
+{-# OPTIONS -cpp #-}
 -----------------------------------------------------------------------------
 -- |
 -- Module      :  Data.Set