Spaces at end of lines removed.
authorMilan Straka <fox@ucw.cz>
Thu, 24 Nov 2011 13:49:12 +0000 (14:49 +0100)
committerMilan Straka <fox@ucw.cz>
Thu, 24 Nov 2011 13:49:12 +0000 (14:49 +0100)
Since my Google internship I am annoyed by spaced before end of lines
as vim shows them in red color.

Data/Graph.hs
Data/IntSet.hs
Data/Map/Base.hs
Data/Set.hs
Data/Tree.hs
LICENSE
benchmarks/IntMap.hs
include/Typeable.h
tests/intmap-properties.hs
tests/map-properties.hs

index c8a5d04..a2029ff 100644 (file)
@@ -6,7 +6,7 @@
 -- Module      :  Data.Graph
 -- Copyright   :  (c) The University of Glasgow 2002
 -- License     :  BSD-style (see the file libraries/base/LICENSE)
--- 
+--
 -- Maintainer  :  libraries@haskell.org
 -- Stability   :  experimental
 -- Portability :  portable
 
 module Data.Graph(
 
-       -- * External interface
+        -- * External interface
 
-       -- At present the only one with a "nice" external interface
-       stronglyConnComp, stronglyConnCompR, SCC(..), flattenSCC, flattenSCCs,
+        -- At present the only one with a "nice" external interface
+        stronglyConnComp, stronglyConnCompR, SCC(..), flattenSCC, flattenSCCs,
 
-       -- * Graphs
+        -- * Graphs
 
-       Graph, Table, Bounds, Edge, Vertex,
+        Graph, Table, Bounds, Edge, Vertex,
 
-       -- ** Building graphs
+        -- ** Building graphs
 
-       graphFromEdges, graphFromEdges', buildG, transposeG,
-       -- reverseE,
+        graphFromEdges, graphFromEdges', buildG, transposeG,
+        -- reverseE,
 
-       -- ** Graph properties
+        -- ** Graph properties
 
-       vertices, edges,
-       outdegree, indegree,
+        vertices, edges,
+        outdegree, indegree,
 
-       -- * Algorithms
+        -- * Algorithms
 
-       dfs, dff,
-       topSort,
-       components,
-       scc,
-       bcc,
-       -- tree, back, cross, forward,
-       reachable, path,
+        dfs, dff,
+        topSort,
+        components,
+        scc,
+        bcc,
+        -- tree, back, cross, forward,
+        reachable, path,
 
-       module Data.Tree
+        module Data.Tree
 
     ) where
 
@@ -73,16 +73,16 @@ import Data.Array
 import Data.List
 
 -------------------------------------------------------------------------
---                                                                     -
---     External interface
---                                                                     -
+--                                                                      -
+--      External interface
+--                                                                      -
 -------------------------------------------------------------------------
 
 -- | Strongly connected component.
-data SCC vertex = AcyclicSCC vertex    -- ^ A single vertex that is not
-                                       -- in any cycle.
-               | CyclicSCC  [vertex]   -- ^ A maximal set of mutually
-                                       -- reachable vertices.
+data SCC vertex = AcyclicSCC vertex     -- ^ A single vertex that is not
+                                        -- in any cycle.
+                | CyclicSCC  [vertex]   -- ^ A maximal set of mutually
+                                        -- reachable vertices.
 
 -- | The vertices of a list of strongly connected components.
 flattenSCCs :: [SCC a] -> [a]
@@ -96,13 +96,13 @@ flattenSCC (CyclicSCC vs) = vs
 -- | The strongly connected components of a directed graph, topologically
 -- sorted.
 stronglyConnComp
-       :: Ord key
-       => [(node, key, [key])]
-               -- ^ The graph: a list of nodes uniquely identified by keys,
-               -- with a list of keys of nodes this node has edges to.
-               -- The out-list may contain keys that don't correspond to
-               -- nodes of the graph; such edges are ignored.
-       -> [SCC node]
+        :: Ord key
+        => [(node, key, [key])]
+                -- ^ The graph: a list of nodes uniquely identified by keys,
+                -- with a list of keys of nodes this node has edges to.
+                -- The out-list may contain keys that don't correspond to
+                -- nodes of the graph; such edges are ignored.
+        -> [SCC node]
 
 stronglyConnComp edges0
   = map get_node (stronglyConnCompR edges0)
@@ -117,31 +117,31 @@ stronglyConnComp edges0
 -- (some of) the result of 'SCC', so you don't want to lose the
 -- dependency information.
 stronglyConnCompR
-       :: Ord key
-       => [(node, key, [key])]
-               -- ^ The graph: a list of nodes uniquely identified by keys,
-               -- with a list of keys of nodes this node has edges to.
-               -- The out-list may contain keys that don't correspond to
-               -- nodes of the graph; such edges are ignored.
-       -> [SCC (node, key, [key])]     -- ^ Topologically sorted
+        :: Ord key
+        => [(node, key, [key])]
+                -- ^ The graph: a list of nodes uniquely identified by keys,
+                -- with a list of keys of nodes this node has edges to.
+                -- The out-list may contain keys that don't correspond to
+                -- nodes of the graph; such edges are ignored.
+        -> [SCC (node, key, [key])]     -- ^ Topologically sorted
 
 stronglyConnCompR [] = []  -- added to avoid creating empty array in graphFromEdges -- SOF
 stronglyConnCompR edges0
   = map decode forest
   where
     (graph, vertex_fn,_) = graphFromEdges edges0
-    forest            = scc graph
+    forest             = scc graph
     decode (Node v []) | mentions_itself v = CyclicSCC [vertex_fn v]
-                      | otherwise         = AcyclicSCC (vertex_fn v)
+                       | otherwise         = AcyclicSCC (vertex_fn v)
     decode other = CyclicSCC (dec other [])
-                where
-                  dec (Node v ts) vs = vertex_fn v : foldr dec vs ts
+                 where
+                   dec (Node v ts) vs = vertex_fn v : foldr dec vs ts
     mentions_itself v = v `elem` (graph ! v)
 
 -------------------------------------------------------------------------
---                                                                     -
---     Graphs
---                                                                     -
+--                                                                      -
+--      Graphs
+--                                                                      -
 -------------------------------------------------------------------------
 
 -- | Abstract representation of vertices.
@@ -191,9 +191,9 @@ indegree  = outdegree . transposeG
 -- does not include the function which maps keys to vertices.  This
 -- version of 'graphFromEdges' is for backwards compatibility.
 graphFromEdges'
-       :: Ord key
-       => [(node, key, [key])]
-       -> (Graph, Vertex -> (node, key, [key]))
+        :: Ord key
+        => [(node, key, [key])]
+        -> (Graph, Vertex -> (node, key, [key]))
 graphFromEdges' x = (a,b) where
     (a,b,_) = graphFromEdges x
 
@@ -202,40 +202,40 @@ graphFromEdges' x = (a,b) where
 -- The out-list may contain keys that don't correspond to
 -- nodes of the graph; they are ignored.
 graphFromEdges
-       :: Ord key
-       => [(node, key, [key])]
-       -> (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex)
+        :: Ord key
+        => [(node, key, [key])]
+        -> (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex)
 graphFromEdges edges0
   = (graph, \v -> vertex_map ! v, key_vertex)
   where
-    max_v                  = length edges0 - 1
+    max_v           = length edges0 - 1
     bounds0         = (0,max_v) :: (Vertex, Vertex)
     sorted_edges    = sortBy lt edges0
-    edges1         = zipWith (,) [0..] sorted_edges
+    edges1          = zipWith (,) [0..] sorted_edges
 
-    graph          = array bounds0 [(,) v (mapMaybe key_vertex ks) | (,) v (_,    _, ks) <- edges1]
-    key_map        = array bounds0 [(,) v k                       | (,) v (_,    k, _ ) <- edges1]
-    vertex_map     = array bounds0 edges1
+    graph           = array bounds0 [(,) v (mapMaybe key_vertex ks) | (,) v (_,    _, ks) <- edges1]
+    key_map         = array bounds0 [(,) v k                       | (,) v (_,    k, _ ) <- edges1]
+    vertex_map      = array bounds0 edges1
 
     (_,k1,_) `lt` (_,k2,_) = k1 `compare` k2
 
     -- key_vertex :: key -> Maybe Vertex
-    --         returns Nothing for non-interesting vertices
+    --  returns Nothing for non-interesting vertices
     key_vertex k   = findVertex 0 max_v
-                  where
-                    findVertex a b | a > b
-                             = Nothing
-                    findVertex a b = case compare k (key_map ! mid) of
-                                  LT -> findVertex a (mid-1)
-                                  EQ -> Just mid
-                                  GT -> findVertex (mid+1) b
-                             where
-                               mid = (a + b) `div` 2
+                   where
+                     findVertex a b | a > b
+                              = Nothing
+                     findVertex a b = case compare k (key_map ! mid) of
+                                   LT -> findVertex a (mid-1)
+                                   EQ -> Just mid
+                                   GT -> findVertex (mid+1) b
+                              where
+                                mid = (a + b) `div` 2
 
 -------------------------------------------------------------------------
---                                                                     -
---     Depth first search
---                                                                     -
+--                                                                      -
+--      Depth first search
+--                                                                      -
 -------------------------------------------------------------------------
 
 -- | A spanning forest of the graph, obtained from a depth-first search of
@@ -310,9 +310,9 @@ include v     = SetM $ \ m -> ((), Set.insert v m)
 #endif /* !USE_ST_MONAD */
 
 -------------------------------------------------------------------------
---                                                                     -
---     Algorithms
---                                                                     -
+--                                                                      -
+--      Algorithms
+--                                                                      -
 -------------------------------------------------------------------------
 
 ------------------------------------------------------------
index e3dfa98..390c335 100644 (file)
@@ -133,7 +133,7 @@ module Data.IntSet (
 
 
 import Prelude hiding (filter,foldr,foldl,null,map)
-import Data.Bits 
+import Data.Bits
 
 import qualified Data.List as List
 import Data.Monoid (Monoid(..))
@@ -198,7 +198,7 @@ shiftLL x i   = shiftL x i
 m1 \\ m2 = difference m1 m2
 
 {--------------------------------------------------------------------
-  Types  
+  Types
 --------------------------------------------------------------------}
 
 -- The order of constructors of IntSet matters when considering performance.
@@ -240,7 +240,7 @@ instance Monoid IntSet where
 #if __GLASGOW_HASKELL__
 
 {--------------------------------------------------------------------
-  A Data instance  
+  A Data instance
 --------------------------------------------------------------------}
 
 -- This instance preserves data abstraction at the cost of inefficiency.
@@ -361,7 +361,7 @@ unions xs
   = foldlStrict union empty xs
 
 
--- | /O(n+m)/. The union of two sets. 
+-- | /O(n+m)/. The union of two sets.
 union :: IntSet -> IntSet -> IntSet
 union t1@(Bin p1 m1 l1 r1) t2@(Bin p2 m2 l2 r2)
   | shorter m1 m2  = union1
@@ -386,7 +386,7 @@ union t Nil     = t
 {--------------------------------------------------------------------
   Difference
 --------------------------------------------------------------------}
--- | /O(n+m)/. Difference between two sets. 
+-- | /O(n+m)/. Difference between two sets.
 difference :: IntSet -> IntSet -> IntSet
 difference t1@(Bin p1 m1 l1 r1) t2@(Bin p2 m2 l2 r2)
   | shorter m1 m2  = difference1
@@ -417,7 +417,7 @@ difference t Nil     = t
 {--------------------------------------------------------------------
   Intersection
 --------------------------------------------------------------------}
--- | /O(n+m)/. The intersection of two sets. 
+-- | /O(n+m)/. The intersection of two sets.
 intersection :: IntSet -> IntSet -> IntSet
 intersection t1@(Bin p1 m1 l1 r1) t2@(Bin p2 m2 l2 r2)
   | shorter m1 m2  = intersection1
@@ -443,11 +443,11 @@ intersection _ Nil = Nil
 intersectBM :: Prefix -> BitMap -> IntSet -> IntSet
 STRICT_1_OF_3(intersectBM)
 STRICT_2_OF_3(intersectBM)
-intersectBM kx bm (Bin p2 m2 l2 r2) 
+intersectBM kx bm (Bin p2 m2 l2 r2)
   | nomatch kx p2 m2 = Nil
   | zero kx m2       = intersectBM kx bm l2
   | otherwise        = intersectBM kx bm r2
-intersectBM kx bm (Tip kx' bm') 
+intersectBM kx bm (Tip kx' bm')
   | kx == kx' = tip kx (bm .&. bm')
   | otherwise = Nil
 intersectBM _ _ Nil = Nil
@@ -459,7 +459,7 @@ intersectBM _ _ Nil = Nil
 -- | /O(n+m)/. Is this a proper subset? (ie. a subset but not equal).
 isProperSubsetOf :: IntSet -> IntSet -> Bool
 isProperSubsetOf t1 t2
-  = case subsetCmp t1 t2 of 
+  = case subsetCmp t1 t2 of
       LT -> True
       _  -> False
 
@@ -482,7 +482,7 @@ subsetCmp t1@(Bin p1 m1 l1 r1) (Bin p2 m2 l2 r2)
                     _       -> LT
 
 subsetCmp (Bin _ _ _ _) _  = GT
-subsetCmp (Tip kx1 bm1) (Tip kx2 bm2)  
+subsetCmp (Tip kx1 bm1) (Tip kx2 bm2)
   | kx1 /= kx2                  = GT -- disjoint
   | bm1 == bm2                  = EQ
   | bm1 .&. complement bm2 == 0 = LT
@@ -502,7 +502,7 @@ isSubsetOf :: IntSet -> IntSet -> Bool
 isSubsetOf t1@(Bin p1 m1 l1 r1) (Bin p2 m2 l2 r2)
   | shorter m1 m2  = False
   | shorter m2 m1  = match p1 p2 m2 && (if zero p1 m2 then isSubsetOf t1 l2
-                                                      else isSubsetOf t1 r2)                     
+                                                      else isSubsetOf t1 r2)
   | otherwise      = (p1==p2) && isSubsetOf l1 l2 && isSubsetOf r1 r2
 isSubsetOf (Bin _ _ _ _) _  = False
 isSubsetOf (Tip kx1 bm1) (Tip kx2 bm2) = kx1 == kx2 && bm1 .&. complement bm2 == 0
@@ -521,9 +521,9 @@ isSubsetOf Nil _         = True
 filter :: (Int -> Bool) -> IntSet -> IntSet
 filter predicate t
   = case t of
-      Bin p m l r 
+      Bin p m l r
         -> bin p m (filter predicate l) (filter predicate r)
-      Tip kx bm 
+      Tip kx bm
         -> tip kx (foldl'Bits 0 (bitPred kx) 0 bm)
       Nil -> Nil
   where bitPred kx bm bi | predicate (kx + bi) = bm .|. bitmapOfSuffix bi
@@ -534,11 +534,11 @@ filter predicate t
 partition :: (Int -> Bool) -> IntSet -> (IntSet,IntSet)
 partition predicate t
   = case t of
-      Bin p m l r 
+      Bin p m l r
         -> let (l1,l2) = partition predicate l
                (r1,r2) = partition predicate r
            in (bin p m l1 r1, bin p m l2 r2)
-      Tip kx bm 
+      Tip kx bm
         -> let bm1 = foldl'Bits 0 (bitPred kx) 0 bm
            in  (tip kx bm1, tip kx (bm `xor` bm1))
       Nil -> (Nil,Nil)
@@ -621,13 +621,13 @@ minView t =
     go Nil = error "minView Nil"
 
 -- | /O(min(n,W))/. Delete and find the minimal element.
--- 
+--
 -- > deleteFindMin set = (findMin set, deleteMin set)
 deleteFindMin :: IntSet -> (Int, IntSet)
 deleteFindMin = fromMaybe (error "deleteFindMin: empty set has no minimal element") . minView
 
 -- | /O(min(n,W))/. Delete and find the maximal element.
--- 
+--
 -- > deleteFindMax set = (findMax set, deleteMax set)
 deleteFindMax :: IntSet -> (Int, IntSet)
 deleteFindMax = fromMaybe (error "deleteFindMax: empty set has no maximal element") . maxView
@@ -668,9 +668,9 @@ deleteMax = maybe (error "deleteMax: empty set has no maximal element") snd . ma
   Map
 ----------------------------------------------------------------------}
 
--- | /O(n*min(n,W))/. 
+-- | /O(n*min(n,W))/.
 -- @'map' f s@ is the set obtained by applying @f@ to each element of @s@.
--- 
+--
 -- It's worth noting that the size of the result may be smaller if,
 -- for some @(x,y)@, @x \/= y && f x == f y@
 
@@ -751,7 +751,7 @@ foldl' f z t =
 {-# INLINE foldl' #-}
 
 {--------------------------------------------------------------------
-  List variations 
+  List variations
 --------------------------------------------------------------------}
 -- | /O(n)/. The elements of a set. (For sets, this is equivalent to toList.)
 elems :: IntSet -> [Int]
@@ -759,7 +759,7 @@ elems t
   = toAscList t
 
 {--------------------------------------------------------------------
-  Lists 
+  Lists
 --------------------------------------------------------------------}
 -- | /O(n)/. Convert the set to a list of elements.
 toList :: IntSet -> [Int]
@@ -779,12 +779,12 @@ fromList xs
 
 -- | /O(n)/. Build a set from an ascending list of elements.
 -- /The precondition (input list is ascending) is not checked./
-fromAscList :: [Int] -> IntSet 
+fromAscList :: [Int] -> IntSet
 fromAscList [] = Nil
 fromAscList (x0 : xs0) = fromDistinctAscList (combineEq x0 xs0)
-  where 
+  where
     combineEq x' [] = [x']
-    combineEq x' (x:xs) 
+    combineEq x' (x:xs)
       | x==x'     = combineEq x' xs
       | otherwise = x' : combineEq x xs
 
@@ -817,7 +817,7 @@ data Stack = Push {-# UNPACK #-} !Prefix !IntSet !Stack | Nada
 
 
 {--------------------------------------------------------------------
-  Eq 
+  Eq
 --------------------------------------------------------------------}
 instance Eq IntSet where
   t1 == t2  = equal t1 t2
@@ -825,7 +825,7 @@ instance Eq IntSet where
 
 equal :: IntSet -> IntSet -> Bool
 equal (Bin p1 m1 l1 r1) (Bin p2 m2 l2 r2)
-  = (m1 == m2) && (p1 == p2) && (equal l1 l2) && (equal r1 r2) 
+  = (m1 == m2) && (p1 == p2) && (equal l1 l2) && (equal r1 r2)
 equal (Tip kx1 bm1) (Tip kx2 bm2)
   = kx1 == kx2 && bm1 == bm2
 equal Nil Nil = True
@@ -833,18 +833,18 @@ equal _   _   = False
 
 nequal :: IntSet -> IntSet -> Bool
 nequal (Bin p1 m1 l1 r1) (Bin p2 m2 l2 r2)
-  = (m1 /= m2) || (p1 /= p2) || (nequal l1 l2) || (nequal r1 r2) 
+  = (m1 /= m2) || (p1 /= p2) || (nequal l1 l2) || (nequal r1 r2)
 nequal (Tip kx1 bm1) (Tip kx2 bm2)
   = kx1 /= kx2 || bm1 /= bm2
 nequal Nil Nil = False
 nequal _   _   = True
 
 {--------------------------------------------------------------------
-  Ord 
+  Ord
 --------------------------------------------------------------------}
 
 instance Ord IntSet where
-    compare s1 s2 = compare (toAscList s1) (toAscList s2) 
+    compare s1 s2 = compare (toAscList s1) (toAscList s2)
     -- tentative implementation. See if more efficient exists.
 
 {--------------------------------------------------------------------
@@ -857,9 +857,9 @@ instance Show IntSet where
 {-
 XXX unused code
 showSet :: [Int] -> ShowS
-showSet []     
-  = showString "{}" 
-showSet (x:xs) 
+showSet []
+  = showString "{}"
+showSet (x:xs)
   = showChar '{' . shows x . showTail xs
   where
     showTail []     = showChar '}'
@@ -931,30 +931,30 @@ showsTree wide lbars rbars t
              showsTree wide (withEmpty lbars) (withBar lbars) l
       Tip kx bm
           -> showsBars lbars . showString " " . shows kx . showString " + " .
-                                                showsBitMap bm . showString "\n" 
+                                                showsBitMap bm . showString "\n"
       Nil -> showsBars lbars . showString "|\n"
 
 showsTreeHang :: Bool -> [String] -> IntSet -> ShowS
 showsTreeHang wide bars t
   = case t of
       Bin p m l r
-          -> showsBars bars . showString (showBin p m) . showString "\n" . 
+          -> showsBars bars . showString (showBin p m) . showString "\n" .
              showWide wide bars .
              showsTreeHang wide (withBar bars) l .
              showWide wide bars .
              showsTreeHang wide (withEmpty bars) r
       Tip kx bm
           -> showsBars bars . showString " " . shows kx . showString " + " .
-                                               showsBitMap bm . showString "\n" 
-      Nil -> showsBars bars . showString "|\n" 
+                                               showsBitMap bm . showString "\n"
+      Nil -> showsBars bars . showString "|\n"
 
 showBin :: Prefix -> Mask -> String
 showBin _ _
   = "*" -- ++ show (p,m)
 
 showWide :: Bool -> [String] -> String -> String
-showWide wide bars 
-  | wide      = showString (concat (reverse bars)) . showString "|\n" 
+showWide wide bars
+  | wide      = showString (concat (reverse bars)) . showString "|\n"
   | otherwise = id
 
 showsBars :: [String] -> ShowS
@@ -1064,7 +1064,7 @@ mask i m
 {-# INLINE mask #-}
 
 {--------------------------------------------------------------------
-  Big endian operations  
+  Big endian operations
 --------------------------------------------------------------------}
 maskW :: Nat -> Nat -> Prefix
 maskW i m
@@ -1084,17 +1084,17 @@ branchMask p1 p2
 {----------------------------------------------------------------------
   Finding the highest bit (mask) in a word [x] can be done efficiently in
   three ways:
-  * convert to a floating point value and the mantissa tells us the 
-    [log2(x)] that corresponds with the highest bit position. The mantissa 
-    is retrieved either via the standard C function [frexp] or by some bit 
-    twiddling on IEEE compatible numbers (float). Note that one needs to 
-    use at least [double] precision for an accurate mantissa of 32 bit 
+  * convert to a floating point value and the mantissa tells us the
+    [log2(x)] that corresponds with the highest bit position. The mantissa
+    is retrieved either via the standard C function [frexp] or by some bit
+    twiddling on IEEE compatible numbers (float). Note that one needs to
+    use at least [double] precision for an accurate mantissa of 32 bit
     numbers.
   * use bit twiddling, a logarithmic sequence of bitwise or's and shifts (bit).
   * use processor specific assembler instruction (asm).
 
   The most portable way would be [bit], but is it efficient enough?
-  I have measured the cycle counts of the different methods on an AMD 
+  I have measured the cycle counts of the different methods on an AMD
   Athlon-XP 1800 (~ Pentium III 1.8Ghz) using the RDTSC instruction:
 
   highestBitMask: method  cycles
@@ -1117,7 +1117,7 @@ branchMask p1 p2
 
 {----------------------------------------------------------------------
   [highestBitMask] returns a word where only the highest bit is set.
-  It is found by first setting all bits in lower positions than the 
+  It is found by first setting all bits in lower positions than the
   highest bit and than taking an exclusive or with the original value.
   Allthough the function may look expensive, GHC compiles this into
   excellent C code that subsequently compiled into highly efficient
@@ -1272,7 +1272,7 @@ highestBitSet n0 =
         (n3,b3) = if n2 .&. 0xFF00 /= 0             then (n2 `shiftRL` 8,  8+b2)  else (n2,b2)
         (n4,b4) = if n3 .&. 0xF0 /= 0               then (n3 `shiftRL` 4,  4+b3)  else (n3,b3)
         (n5,b5) = if n4 .&. 0xC /= 0                then (n4 `shiftRL` 2,  2+b4)  else (n4,b4)
-        b6      = if n5 .&. 0x2 /= 0                then                   1+b5   else     b5 
+        b6      = if n5 .&. 0x2 /= 0                then                   1+b5   else     b5
     in b6
 
 foldlBits prefix f z bm = let lb = lowestBitSet bm
@@ -1325,7 +1325,7 @@ bitcount a0 x0 = go a0 x0
 
 
 {--------------------------------------------------------------------
-  Utilities 
+  Utilities
 --------------------------------------------------------------------}
 foldlStrict :: (a -> b -> a) -> a -> [b] -> a
 foldlStrict f = go
index a6ad669..377ec15 100644 (file)
@@ -269,9 +269,9 @@ m1 \\ m2 = difference m1 m2
 {--------------------------------------------------------------------
   Size balanced trees.
 --------------------------------------------------------------------}
--- | A Map from keys @k@ to values @a@. 
-data Map k a  = Tip 
-              | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) 
+-- | A Map from keys @k@ to values @a@.
+data Map k a  = Tip
+              | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
 
 type Size     = Int
 
@@ -283,7 +283,7 @@ instance (Ord k) => Monoid (Map k v) where
 #if __GLASGOW_HASKELL__
 
 {--------------------------------------------------------------------
-  A Data instance  
+  A Data instance
 --------------------------------------------------------------------}
 
 -- This instance preserves data abstraction at the cost of inefficiency.
@@ -490,7 +490,7 @@ insert = go
 #endif
 
 -- | /O(log n)/. Insert with a function, combining new value and old value.
--- @'insertWith' f key value mp@ 
+-- @'insertWith' f key value mp@
 -- will insert the pair (key, value) into @mp@ if key does
 -- not exist in the map. If the key does exist, the function will
 -- insert the pair @(key, f new_value old_value)@.
@@ -515,7 +515,7 @@ insertWith' f = insertWithKey' (\_ x' y' -> f x' y')
 {-# INLINE insertWith' #-}
 
 -- | /O(log n)/. Insert with a function, combining key, new value and old value.
--- @'insertWithKey' f key value mp@ 
+-- @'insertWithKey' f key value mp@
 -- will insert the pair (key, value) into @mp@ if key does
 -- not exist in the map. If the key does exist, the function will
 -- insert the pair @(key,f key new_value old_value)@.
@@ -708,7 +708,7 @@ updateWithKey = go
 
 -- | /O(log n)/. Lookup and update. See also 'updateWithKey'.
 -- The function returns changed value, if it is updated.
--- Returns the original key value if the map entry is deleted. 
+-- Returns the original key value if the map entry is deleted.
 --
 -- > let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
 -- > updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "5:new a", fromList [(3, "b"), (5, "5:new a")])
@@ -723,7 +723,7 @@ updateLookupWithKey = go
    go f k (Bin sx kx x l r) =
           case compare k kx of
                LT -> let (found,l') = go f k l in (found,balanceR kx x l' r)
-               GT -> let (found,r') = go f k r in (found,balanceL kx x l r') 
+               GT -> let (found,r') = go f k r in (found,balanceL kx x l r')
                EQ -> case f kx x of
                        Just x' -> (Just x',Bin sx kx x' l r)
                        Nothing -> (Just x,glue l r)
@@ -1042,7 +1042,7 @@ first :: (a -> b) -> (a,c) -> (b,c)
 first f (x,y) = (f x, y)
 
 {--------------------------------------------------------------------
-  Union. 
+  Union.
 --------------------------------------------------------------------}
 -- | The union of a list of maps:
 --   (@'unions' == 'Prelude.foldl' 'union' 'empty'@).
@@ -1073,7 +1073,7 @@ unionsWith f ts
 #endif
 
 -- | /O(n+m)/.
--- The expression (@'union' t1 t2@) takes the left-biased union of @t1@ and @t2@. 
+-- The expression (@'union' t1 t2@) takes the left-biased union of @t1@ and @t2@.
 -- It prefers @t1@ when duplicate keys are encountered,
 -- i.e. (@'union' == 'unionWith' 'const'@).
 -- The implementation uses the efficient /hedge-union/ algorithm.
@@ -1161,7 +1161,7 @@ hedgeUnionWithKey f blo bhi (Bin _ kx x l r) t2
 {--------------------------------------------------------------------
   Difference
 --------------------------------------------------------------------}
--- | /O(n+m)/. Difference of two maps. 
+-- | /O(n+m)/. Difference of two maps.
 -- Return elements of the first map not existing in the second map.
 -- The implementation uses an efficient /hedge/ algorithm comparable with /hedge-union/.
 --
@@ -1191,11 +1191,11 @@ hedgeDiff blo bhi t (Bin _ kx _ l r)
 {-# INLINABLE hedgeDiff #-}
 #endif
 
--- | /O(n+m)/. Difference with a combining function. 
+-- | /O(n+m)/. Difference with a combining function.
 -- When two equal keys are
 -- encountered, the combining function is applied to the values of these keys.
 -- If it returns 'Nothing', the element is discarded (proper set difference). If
--- it returns (@'Just' y@), the element is updated with a new value @y@. 
+-- it returns (@'Just' y@), the element is updated with a new value @y@.
 -- The implementation uses an efficient /hedge/ algorithm comparable with /hedge-union/.
 --
 -- > let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
@@ -1210,7 +1210,7 @@ differenceWith f m1 m2
 -- | /O(n+m)/. Difference with a combining function. When two equal keys are
 -- encountered, the combining function is applied to the key and both values.
 -- If it returns 'Nothing', the element is discarded (proper set difference). If
--- it returns (@'Just' y@), the element is updated with a new value @y@. 
+-- it returns (@'Just' y@), the element is updated with a new value @y@.
 -- The implementation uses an efficient /hedge/ algorithm comparable with /hedge-union/.
 --
 -- > let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
@@ -1234,10 +1234,10 @@ hedgeDiffWithKey _ _     _     Tip _
   = Tip
 hedgeDiffWithKey _ blo bhi (Bin _ kx x l r) Tip
   = join kx x (filterGt blo l) (filterLt bhi r)
-hedgeDiffWithKey f blo bhi t (Bin _ kx x l r) 
+hedgeDiffWithKey f blo bhi t (Bin _ kx x l r)
   = case found of
       Nothing -> merge tl tr
-      Just (ky,y) -> 
+      Just (ky,y) ->
           case f ky y x of
             Nothing -> merge tl tr
             Just z  -> join ky z tl tr
@@ -1321,19 +1321,19 @@ isSubmapOf m1 m2 = isSubmapOfBy (==) m1 m2
 {- | /O(n+m)/.
  The expression (@'isSubmapOfBy' f t1 t2@) returns 'True' if
  all keys in @t1@ are in tree @t2@, and when @f@ returns 'True' when
- applied to their respective values. For example, the following 
+ applied to their respective values. For example, the following
  expressions are all 'True':
+
  > isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
  > isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
  > isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])
 
  But the following are all 'False':
+
  > isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)])
  > isSubmapOfBy (<)  (fromList [('a',1)]) (fromList [('a',1),('b',2)])
  > isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])
+
 
 -}
 isSubmapOfBy :: Ord k => (a->b->Bool) -> Map k a -> Map k b -> Bool
@@ -1356,7 +1356,7 @@ submap' f (Bin _ kx x l r) t
 {-# INLINABLE submap' #-}
 #endif
 
--- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal). 
+-- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal).
 -- Defined as (@'isProperSubmapOf' = 'isProperSubmapOfBy' (==)@).
 isProperSubmapOf :: (Ord k,Eq a) => Map k a -> Map k a -> Bool
 isProperSubmapOf m1 m2
@@ -1369,19 +1369,19 @@ isProperSubmapOf m1 m2
  The expression (@'isProperSubmapOfBy' f m1 m2@) returns 'True' when
  @m1@ and @m2@ are not equal,
  all keys in @m1@ are in @m2@, and when @f@ returns 'True' when
- applied to their respective values. For example, the following 
+ applied to their respective values. For example, the following
  expressions are all 'True':
+
   > isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
   > isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
 
  But the following are all 'False':
+
   > isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
   > isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
   > isProperSubmapOfBy (<)  (fromList [(1,1)])       (fromList [(1,1),(2,2)])
-  
+
+
 -}
 isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
 isProperSubmapOfBy f t1 t2
@@ -1596,7 +1596,7 @@ mapAccumRWithKey f a (Bin sx kx x l r) =
 
 -- | /O(n*log n)/.
 -- @'mapKeys' f s@ is the map obtained by applying @f@ to each key of @s@.
--- 
+--
 -- The size of the result may be smaller if @f@ maps two or more distinct
 -- keys to the same new key.  In this case the value at the greatest of the
 -- original keys is retained.
@@ -1613,7 +1613,7 @@ mapKeys = mapKeysWith (\x _ -> x)
 
 -- | /O(n*log n)/.
 -- @'mapKeysWith' c f s@ is the map obtained by applying @f@ to each key of @s@.
--- 
+--
 -- The size of the result may be smaller if @f@ maps two or more distinct
 -- keys to the same new key.  In this case the associated values will be
 -- combined using @c@.
@@ -1635,8 +1635,8 @@ mapKeysWith c f = fromListWith c . List.map fFirst . toList
 -- That is, for any values @x@ and @y@, if @x@ < @y@ then @f x@ < @f y@.
 -- /The precondition is not checked./
 -- Semi-formally, we have:
--- 
--- > and [x < y ==> f x < f y | x <- ls, y <- ls] 
+--
+-- > and [x < y ==> f x < f y | x <- ls, y <- ls]
 -- >                     ==> mapKeysMonotonic f s == mapKeys f s
 -- >     where ls = keys s
 --
@@ -1656,7 +1656,7 @@ mapKeysMonotonic f (Bin sz k x l r) =
 #endif
 
 {--------------------------------------------------------------------
-  Folds  
+  Folds
 --------------------------------------------------------------------}
 
 -- | /O(n)/. Fold the values in the map using the given right-associative
@@ -1788,7 +1788,7 @@ foldlWithKey' f = go
 {-# INLINE foldlWithKey' #-}
 
 {--------------------------------------------------------------------
-  List variations 
+  List variations
 --------------------------------------------------------------------}
 -- | /O(n)/.
 -- Return all elements of the map in the ascending order of their keys.
@@ -1839,7 +1839,7 @@ assocs m
 #endif
 
 {--------------------------------------------------------------------
-  Lists 
+  Lists
   use [foldlStrict] to reduce demand on the control-stack
 --------------------------------------------------------------------}
 -- | /O(n*log n)/. Build a map from a list of key\/value pairs. See also 'fromAscList'.
@@ -1850,8 +1850,8 @@ assocs m
 -- > fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
 -- > fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
 
-fromList :: Ord k => [(k,a)] -> Map k a 
-fromList xs       
+fromList :: Ord k => [(k,a)] -> Map k a
+fromList xs
   = foldlStrict ins empty xs
   where
     ins t (k,x) = insert k x t
@@ -1864,7 +1864,7 @@ fromList xs
 -- > fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
 -- > fromListWith (++) [] == empty
 
-fromListWith :: Ord k => (a -> a -> a) -> [(k,a)] -> Map k a 
+fromListWith :: Ord k => (a -> a -> a) -> [(k,a)] -> Map k a
 fromListWith f xs
   = fromListWithKey (\_ x y -> f x y) xs
 #if __GLASGOW_HASKELL__ >= 700
@@ -1877,8 +1877,8 @@ fromListWith f xs
 -- > fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]
 -- > fromListWithKey f [] == empty
 
-fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k,a)] -> Map k a 
-fromListWithKey f xs 
+fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k,a)] -> Map k a
+fromListWithKey f xs
   = foldlStrict ins empty xs
   where
     ins t (k,x) = insertWithKey f k x t
@@ -1916,8 +1916,8 @@ toDescList t  = foldlWithKey (\xs k x -> (k,x):xs) [] t
 
 {--------------------------------------------------------------------
   Building trees from ascending/descending lists can be done in linear time.
-  
-  Note that if [xs] is ascending that: 
+
+  Note that if [xs] is ascending that:
     fromAscList xs       == fromList xs
     fromAscListWith f xs == fromListWith f xs
 --------------------------------------------------------------------}
@@ -1929,7 +1929,7 @@ toDescList t  = foldlWithKey (\xs k x -> (k,x):xs) [] t
 -- > valid (fromAscList [(3,"b"), (5,"a"), (5,"b")]) == True
 -- > valid (fromAscList [(5,"a"), (3,"b"), (5,"b")]) == False
 
-fromAscList :: Eq k => [(k,a)] -> Map k a 
+fromAscList :: Eq k => [(k,a)] -> Map k a
 fromAscList xs
   = fromAscListWithKey (\_ x _ -> x) xs
 #if __GLASGOW_HASKELL__ >= 700
@@ -1943,7 +1943,7 @@ fromAscList xs
 -- > valid (fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")]) == True
 -- > valid (fromAscListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False
 
-fromAscListWith :: Eq k => (a -> a -> a) -> [(k,a)] -> Map k a 
+fromAscListWith :: Eq k => (a -> a -> a) -> [(k,a)] -> Map k a
 fromAscListWith f xs
   = fromAscListWithKey (\_ x y -> f x y) xs
 #if __GLASGOW_HASKELL__ >= 700
@@ -1959,7 +1959,7 @@ fromAscListWith f xs
 -- > valid (fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")]) == True
 -- > valid (fromAscListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False
 
-fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k,a)] -> Map k a 
+fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k,a)] -> Map k a
 fromAscListWithKey f xs
   = fromDistinctAscList (combineEq f xs)
   where
@@ -1986,15 +1986,15 @@ fromAscListWithKey f xs
 -- > valid (fromDistinctAscList [(3,"b"), (5,"a")])          == True
 -- > valid (fromDistinctAscList [(3,"b"), (5,"a"), (5,"b")]) == False
 
-fromDistinctAscList :: [(k,a)] -> Map k a 
+fromDistinctAscList :: [(k,a)] -> Map k a
 fromDistinctAscList xs
   = build const (length xs) xs
   where
     -- 1) use continuations so that we use heap space instead of stack space.
-    -- 2) special case for n==5 to build bushier trees. 
+    -- 2) special case for n==5 to build bushier trees.
     build c 0 xs'  = c Tip xs'
     build c 5 xs'  = case xs' of
-                       ((k1,x1):(k2,x2):(k3,x3):(k4,x4):(k5,x5):xx) 
+                       ((k1,x1):(k2,x2):(k3,x3):(k4,x4):(k5,x5):xx)
                             -> c (bin k4 x4 (bin k2 x2 (singleton k1 x1) (singleton k3 x3)) (singleton k5 x5)) xx
                        _ -> error "fromDistinctAscList build"
     build c n xs'  = seq nr $ build (buildR nr c) nl xs'
@@ -2155,7 +2155,7 @@ splitLookupWithKey k t = k `seq`
   Utility functions that maintain the balance properties of the tree.
   All constructors assume that all values in [l] < [k] and all values
   in [r] > [k], and that [l] and [r] are valid trees.
-  
+
   In order of sophistication:
     [Bin sz k x l r]  The type constructor.
     [bin k x l r]     Maintains the correct size, assumes that both [l]
@@ -2163,7 +2163,7 @@ splitLookupWithKey k t = k `seq`
     [balance k x l r] Restores the balance and size.
                       Assumes that the original tree was balanced and
                       that [l] or [r] has changed by at most one element.
-    [join k x l r]    Restores balance and size. 
+    [join k x l r]    Restores balance and size.
 
   Furthermore, we can construct a new tree from two trees. Both operations
   assume that all values in [l] < all values in [r] and that [l] and [r]
@@ -2173,15 +2173,15 @@ splitLookupWithKey k t = k `seq`
     [merge l r]       Merges two trees and restores balance.
 
   Note: in contrast to Adam's paper, we use (<=) comparisons instead
-  of (<) comparisons in [join], [merge] and [balance]. 
-  Quickcheck (on [difference]) showed that this was necessary in order 
-  to maintain the invariants. It is quite unsatisfactory that I haven't 
-  been able to find out why this is actually the case! Fortunately, it 
+  of (<) comparisons in [join], [merge] and [balance].
+  Quickcheck (on [difference]) showed that this was necessary in order
+  to maintain the invariants. It is quite unsatisfactory that I haven't
+  been able to find out why this is actually the case! Fortunately, it
   doesn't hurt to be a bit more conservative.
 --------------------------------------------------------------------}
 
 {--------------------------------------------------------------------
-  Join 
+  Join
 --------------------------------------------------------------------}
 join :: Ord k => k -> a -> Map k a -> Map k a -> Map k a
 join kx x Tip r  = insertMin kx x r
@@ -2196,7 +2196,7 @@ join kx x l@(Bin sizeL ky y ly ry) r@(Bin sizeR kz z lz rz)
 
 
 -- insertMin and insertMax don't perform potentially expensive comparisons.
-insertMax,insertMin :: k -> a -> Map k a -> Map k a 
+insertMax,insertMin :: k -> a -> Map k a -> Map k a
 insertMax kx x t
   = case t of
       Tip -> singleton kx x
@@ -2236,7 +2236,7 @@ merge l@(Bin sizeL kx x lx rx) r@(Bin sizeR ky y ly ry)
 glue :: Map k a -> Map k a -> Map k a
 glue Tip r = r
 glue l Tip = l
-glue l r   
+glue l r
   | size l > size r = let ((km,m),l') = deleteFindMax l in balanceR km m l' r
   | otherwise       = let ((km,m),r') = deleteFindMin r in balanceL km m l r'
 #if __GLASGOW_HASKELL__ >= 700
@@ -2246,11 +2246,11 @@ glue l r
 
 -- | /O(log n)/. Delete and find the minimal element.
 --
--- > deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) 
+-- > deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")])
 -- > deleteFindMin                                            Error: can not return the minimal element of an empty map
 
 deleteFindMin :: Map k a -> ((k,a),Map k a)
-deleteFindMin t 
+deleteFindMin t
   = case t of
       Bin _ k x Tip r -> ((k,x),r)
       Bin _ k x l r   -> let (km,l') = deleteFindMin l in (km,balanceR k x l' r)
@@ -2441,15 +2441,15 @@ bin k x l r
 
 
 {--------------------------------------------------------------------
-  Eq converts the tree to a list. In a lazy setting, this 
-  actually seems one of the faster methods to compare two trees 
+  Eq converts the tree to a list. In a lazy setting, this
+  actually seems one of the faster methods to compare two trees
   and it is certainly the simplest :-)
 --------------------------------------------------------------------}
 instance (Eq k,Eq a) => Eq (Map k a) where
   t1 == t2  = (size t1 == size t2) && (toAscList t1 == toAscList t2)
 
 {--------------------------------------------------------------------
-  Ord 
+  Ord
 --------------------------------------------------------------------}
 
 instance (Ord k, Ord v) => Ord (Map k v) where
@@ -2558,7 +2558,7 @@ showsTree showelem wide lbars rbars t
   = case t of
       Tip -> showsBars lbars . showString "|\n"
       Bin _ kx x Tip Tip
-          -> showsBars lbars . showString (showelem kx x) . showString "\n" 
+          -> showsBars lbars . showString (showelem kx x) . showString "\n"
       Bin _ kx x l r
           -> showsTree showelem wide (withBar rbars) (withEmpty rbars) r .
              showWide wide rbars .
@@ -2569,19 +2569,19 @@ showsTree showelem wide lbars rbars t
 showsTreeHang :: (k -> a -> String) -> Bool -> [String] -> Map k a -> ShowS
 showsTreeHang showelem wide bars t
   = case t of
-      Tip -> showsBars bars . showString "|\n" 
+      Tip -> showsBars bars . showString "|\n"
       Bin _ kx x Tip Tip
-          -> showsBars bars . showString (showelem kx x) . showString "\n" 
+          -> showsBars bars . showString (showelem kx x) . showString "\n"
       Bin _ kx x l r
-          -> showsBars bars . showString (showelem kx x) . showString "\n" . 
+          -> showsBars bars . showString (showelem kx x) . showString "\n" .
              showWide wide bars .
              showsTreeHang showelem wide (withBar bars) l .
              showWide wide bars .
              showsTreeHang showelem wide (withEmpty bars) r
 
 showWide :: Bool -> [String] -> String -> String
-showWide wide bars 
-  | wide      = showString (concat (reverse bars)) . showString "|\n" 
+showWide wide bars
+  | wide      = showString (concat (reverse bars)) . showString "|\n"
   | otherwise = id
 
 showsBars :: [String] -> ShowS
index be16749..81cb4cd 100644 (file)
@@ -147,7 +147,7 @@ import Control.DeepSeq (NFData(rnf))
 
 {-
 -- just for testing
-import QuickCheck 
+import QuickCheck
 import List (nub,sort)
 import qualified List
 -}
@@ -179,8 +179,8 @@ m1 \\ m2 = difference m1 m2
   Sets are size balanced trees
 --------------------------------------------------------------------}
 -- | A set of values @a@.
-data Set a    = Tip 
-              | Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a) 
+data Set a    = Tip
+              | Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a)
 
 type Size     = Int
 
@@ -200,7 +200,7 @@ instance Foldable.Foldable Set where
 #if __GLASGOW_HASKELL__
 
 {--------------------------------------------------------------------
-  A Data instance  
+  A Data instance
 --------------------------------------------------------------------}
 
 -- This instance preserves data abstraction at the cost of inefficiency.
@@ -393,7 +393,7 @@ deleteMax Tip             = Tip
 #endif
 
 {--------------------------------------------------------------------
-  Union. 
+  Union.
 --------------------------------------------------------------------}
 -- | The union of a list of sets: (@'unions' == 'foldl' 'union' 'empty'@).
 unions :: Ord a => [Set a] -> Set a
@@ -434,7 +434,7 @@ hedgeUnion blo bhi (Bin _ x l r) t2
 {--------------------------------------------------------------------
   Difference
 --------------------------------------------------------------------}
--- | /O(n+m)/. Difference of two sets. 
+-- | /O(n+m)/. Difference of two sets.
 -- The implementation uses an efficient /hedge/ algorithm comparable with /hedge-union/.
 difference :: Ord a => Set a -> Set a -> Set a
 difference Tip _   = Tip
@@ -523,9 +523,9 @@ partition p (Bin _ x l r) = case (partition p l, partition p r) of
   Map
 ----------------------------------------------------------------------}
 
--- | /O(n*log n)/. 
+-- | /O(n*log n)/.
 -- @'map' f s@ is the set obtained by applying @f@ to each element of @s@.
--- 
+--
 -- It's worth noting that the size of the result may be smaller if,
 -- for some @(x,y)@, @x \/= y && f x == f y@
 
@@ -535,13 +535,13 @@ map f = fromList . List.map f . toList
 {-# INLINABLE map #-}
 #endif
 
--- | /O(n)/. The 
+-- | /O(n)/. The
 --
 -- @'mapMonotonic' f s == 'map' f s@, but works only when @f@ is monotonic.
 -- /The precondition is not checked./
 -- Semi-formally, we have:
--- 
--- > and [x < y ==> f x < f y | x <- ls, y <- ls] 
+--
+-- > and [x < y ==> f x < f y | x <- ls, y <- ls]
 -- >                     ==> mapMonotonic f s == map f s
 -- >     where ls = toList s
 
@@ -613,7 +613,7 @@ foldl' f = go
 {-# INLINE foldl' #-}
 
 {--------------------------------------------------------------------
-  List variations 
+  List variations
 --------------------------------------------------------------------}
 -- | /O(n)/. The elements of a set.
 elems :: Set a -> [a]
@@ -623,7 +623,7 @@ elems = toList
 #endif
 
 {--------------------------------------------------------------------
-  Lists 
+  Lists
 --------------------------------------------------------------------}
 -- | /O(n)/. Convert the set to a list of elements.
 toList :: Set a -> [a]
@@ -640,7 +640,7 @@ toAscList = foldr (:) []
 #endif
 
 -- | /O(n*log n)/. Create a set from a list of elements.
-fromList :: Ord a => [a] -> Set a 
+fromList :: Ord a => [a] -> Set a
 fromList = foldlStrict ins empty
   where
     ins t x = insert x t
@@ -650,13 +650,13 @@ fromList = foldlStrict ins empty
 
 {--------------------------------------------------------------------
   Building trees from ascending/descending lists can be done in linear time.
-  
-  Note that if [xs] is ascending that: 
+
+  Note that if [xs] is ascending that:
     fromAscList xs == fromList xs
 --------------------------------------------------------------------}
 -- | /O(n)/. Build a set from an ascending list in linear time.
 -- /The precondition (input list is ascending) is not checked./
-fromAscList :: Eq a => [a] -> Set a 
+fromAscList :: Eq a => [a] -> Set a
 fromAscList xs
   = fromDistinctAscList (combineEq xs)
   where
@@ -678,15 +678,15 @@ fromAscList xs
 
 -- | /O(n)/. Build a set from an ascending list of distinct elements in linear time.
 -- /The precondition (input list is strictly ascending) is not checked./
-fromDistinctAscList :: [a] -> Set a 
+fromDistinctAscList :: [a] -> Set a
 fromDistinctAscList xs
   = build const (length xs) xs
   where
     -- 1) use continutations so that we use heap space instead of stack space.
-    -- 2) special case for n==5 to build bushier trees. 
+    -- 2) special case for n==5 to build bushier trees.
     build c 0 xs'  = c Tip xs'
     build c 5 xs'  = case xs' of
-                       (x1:x2:x3:x4:x5:xx) 
+                       (x1:x2:x3:x4:x5:xx)
                             -> c (bin x4 (bin x2 (singleton x1) (singleton x3)) (singleton x5)) xx
                        _ -> error "fromDistinctAscList build 5"
     build c n xs'  = seq nr $ build (buildR nr c) nl xs'
@@ -702,19 +702,19 @@ fromDistinctAscList xs
 #endif
 
 {--------------------------------------------------------------------
-  Eq converts the set to a list. In a lazy setting, this 
-  actually seems one of the faster methods to compare two trees 
+  Eq converts the set to a list. In a lazy setting, this
+  actually seems one of the faster methods to compare two trees
   and it is certainly the simplest :-)
 --------------------------------------------------------------------}
 instance Eq a => Eq (Set a) where
   t1 == t2  = (size t1 == size t2) && (toAscList t1 == toAscList t2)
 
 {--------------------------------------------------------------------
-  Ord 
+  Ord
 --------------------------------------------------------------------}
 
 instance Ord a => Ord (Set a) where
-    compare s1 s2 = compare (toAscList s1) (toAscList s2) 
+    compare s1 s2 = compare (toAscList s1) (toAscList s2)
 
 {--------------------------------------------------------------------
   Show
@@ -865,7 +865,7 @@ splitLookup x (Bin _ y l r)
   Utility functions that maintain the balance properties of the tree.
   All constructors assume that all values in [l] < [x] and all values
   in [r] > [x], and that [l] and [r] are valid trees.
-  
+
   In order of sophistication:
     [Bin sz x l r]    The type constructor.
     [bin x l r]       Maintains the correct size, assumes that both [l]
@@ -873,7 +873,7 @@ splitLookup x (Bin _ y l r)
     [balance x l r]   Restores the balance and size.
                       Assumes that the original tree was balanced and
                       that [l] or [r] has changed by at most one element.
-    [join x l r]      Restores balance and size. 
+    [join x l r]      Restores balance and size.
 
   Furthermore, we can construct a new tree from two trees. Both operations
   assume that all values in [l] < all values in [r] and that [l] and [r]
@@ -883,15 +883,15 @@ splitLookup x (Bin _ y l r)
     [merge l r]       Merges two trees and restores balance.
 
   Note: in contrast to Adam's paper, we use (<=) comparisons instead
-  of (<) comparisons in [join], [merge] and [balance]. 
-  Quickcheck (on [difference]) showed that this was necessary in order 
-  to maintain the invariants. It is quite unsatisfactory that I haven't 
-  been able to find out why this is actually the case! Fortunately, it 
+  of (<) comparisons in [join], [merge] and [balance].
+  Quickcheck (on [difference]) showed that this was necessary in order
+  to maintain the invariants. It is quite unsatisfactory that I haven't
+  been able to find out why this is actually the case! Fortunately, it
   doesn't hurt to be a bit more conservative.
 --------------------------------------------------------------------}
 
 {--------------------------------------------------------------------
-  Join 
+  Join
 --------------------------------------------------------------------}
 join :: a -> Set a -> Set a -> Set a
 join x Tip r  = insertMin x r
@@ -906,7 +906,7 @@ join x l@(Bin sizeL y ly ry) r@(Bin sizeR z lz rz)
 
 
 -- insertMin and insertMax don't perform potentially expensive comparisons.
-insertMax,insertMin :: a -> Set a -> Set a 
+insertMax,insertMin :: a -> Set a -> Set a
 insertMax x t
   = case t of
       Tip -> singleton x
@@ -946,7 +946,7 @@ merge l@(Bin sizeL x lx rx) r@(Bin sizeR y ly ry)
 glue :: Set a -> Set a -> Set a
 glue Tip r = r
 glue l Tip = l
-glue l r   
+glue l r
   | size l > size r = let (m,l') = deleteFindMax l in balanceR m l' r
   | otherwise       = let (m,r') = deleteFindMin r in balanceL m l r'
 #if __GLASGOW_HASKELL__ >= 700
@@ -955,11 +955,11 @@ glue l r
 
 
 -- | /O(log n)/. Delete and find the minimal element.
--- 
+--
 -- > deleteFindMin set = (findMin set, deleteMin set)
 
 deleteFindMin :: Set a -> (a,Set a)
-deleteFindMin t 
+deleteFindMin t
   = case t of
       Bin _ x Tip r -> (x,r)
       Bin _ x l r   -> let (xm,l') = deleteFindMin l in (xm,balanceR x l' r)
@@ -969,7 +969,7 @@ deleteFindMin t
 #endif
 
 -- | /O(log n)/. Delete and find the maximal element.
--- 
+--
 -- > deleteFindMax set = (findMax set, deleteMax set)
 deleteFindMax :: Set a -> (a,Set a)
 deleteFindMax t
@@ -1163,7 +1163,7 @@ showTree s
 > |  +--1
 > |  +--3
 > +--5
-> 
+>
 > Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1..5]
 > 4
 > |
@@ -1174,7 +1174,7 @@ showTree s
 > |  +--3
 > |
 > +--5
-> 
+>
 > Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1..5]
 > +--5
 > |
@@ -1197,7 +1197,7 @@ showsTree wide lbars rbars t
   = case t of
       Tip -> showsBars lbars . showString "|\n"
       Bin _ x Tip Tip
-          -> showsBars lbars . shows x . showString "\n" 
+          -> showsBars lbars . shows x . showString "\n"
       Bin _ x l r
           -> showsTree wide (withBar rbars) (withEmpty rbars) r .
              showWide wide rbars .
@@ -1208,19 +1208,19 @@ showsTree wide lbars rbars t
 showsTreeHang :: Show a => Bool -> [String] -> Set a -> ShowS
 showsTreeHang wide bars t
   = case t of
-      Tip -> showsBars bars . showString "|\n" 
+      Tip -> showsBars bars . showString "|\n"
       Bin _ x Tip Tip
-          -> showsBars bars . shows x . showString "\n" 
+          -> showsBars bars . shows x . showString "\n"
       Bin _ x l r
-          -> showsBars bars . shows x . showString "\n" . 
+          -> showsBars bars . shows x . showString "\n" .
              showWide wide bars .
              showsTreeHang wide (withBar bars) l .
              showWide wide bars .
              showsTreeHang wide (withEmpty bars) r
 
 showWide :: Bool -> [String] -> String -> String
-showWide wide bars 
-  | wide      = showString (concat (reverse bars)) . showString "|\n" 
+showWide wide bars
+  | wide      = showString (concat (reverse bars)) . showString "|\n"
   | otherwise = id
 
 showsBars :: [String] -> ShowS
index 609180d..21a29d6 100644 (file)
@@ -6,7 +6,7 @@
 -- Module      :  Data.Tree
 -- Copyright   :  (c) The University of Glasgow 2002
 -- License     :  BSD-style (see the file libraries/base/LICENSE)
--- 
+--
 -- Maintainer  :  libraries@haskell.org
 -- Stability   :  experimental
 -- Portability :  portable
diff --git a/LICENSE b/LICENSE
index a5564d9..8d8442b 100644 (file)
--- a/LICENSE
+++ b/LICENSE
@@ -1,5 +1,5 @@
 This library (libraries/containers) is derived from code from several
-sources: 
+sources:
 
   * Code from the GHC project which is largely (c) The University of
     Glasgow, and distributable under a BSD-style license (see below),
@@ -19,7 +19,7 @@ licenses are BSD-style or compatible.
 
 The Glasgow Haskell Compiler License
 
-Copyright 2004, The University Court of the University of Glasgow. 
+Copyright 2004, The University Court of the University of Glasgow.
 All rights reserved.
 
 Redistribution and use in source and binary forms, with or without
@@ -27,14 +27,14 @@ modification, are permitted provided that the following conditions are met:
 
 - Redistributions of source code must retain the above copyright notice,
 this list of conditions and the following disclaimer.
+
 - Redistributions in binary form must reproduce the above copyright notice,
 this list of conditions and the following disclaimer in the documentation
 and/or other materials provided with the distribution.
+
 - Neither name of the University nor the names of its contributors may be
 used to endorse or promote products derived from this software without
-specific prior written permission. 
+specific prior written permission.
 
 THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY COURT OF THE UNIVERSITY OF
 GLASGOW AND THE CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
index 0213256..5237310 100644 (file)
@@ -13,7 +13,7 @@ import Prelude hiding (lookup)
 
 instance (NFData a) => NFData (M.IntMap a) where
     rnf M.Nil = ()
-    rnf (M.Tip x y) = rnf x `seq` rnf y 
+    rnf (M.Tip x y) = rnf x `seq` rnf y
     rnf (M.Bin p m l r) = rnf p `seq` rnf m `seq` rnf l `seq` rnf r
 
 main = do
index 91fbcdd..d21804c 100644 (file)
@@ -3,11 +3,11 @@
 //
 // INSTANCE_TYPEABLEn(tc,tcname,"tc") defines
 //
-//     instance Typeable/n/ tc
-//     instance Typeable a => Typeable/n-1/ (tc a)
-//     instance (Typeable a, Typeable b) => Typeable/n-2/ (tc a b)
-//     ...
-//     instance (Typeable a1, ..., Typeable an) => Typeable (tc a1 ... an)
+//      instance Typeable/n/ tc
+//      instance Typeable a => Typeable/n-1/ (tc a)
+//      instance (Typeable a, Typeable b) => Typeable/n-2/ (tc a b)
+//      ...
+//      instance (Typeable a1, ..., Typeable an) => Typeable (tc a1 ... an)
 // --------------------------------------------------------------------------
 -}
 
index 76dbd81..58baff4 100644 (file)
@@ -480,7 +480,7 @@ test_toAscList = toAscList (fromList [(5,"a"), (3,"b")]) @?= [(3,"b"), (5,"a")]
 test_showTree :: Assertion
 test_showTree =
        (let t = fromDistinctAscList [(x,()) | x <- [1..5]]
-        in showTree t) @?= "*\n+--*\n|  +-- 1:=()\n|  +--*\n|     +-- 2:=()\n|     +-- 3:=()\n+--*\n   +-- 4:=()\n   +-- 5:=()\n" 
+        in showTree t) @?= "*\n+--*\n|  +-- 1:=()\n|  +--*\n|     +-- 2:=()\n|     +-- 3:=()\n+--*\n   +-- 4:=()\n   +-- 5:=()\n"
 
 test_fromAscList :: Assertion
 test_fromAscList = do
index c83fbb9..0fe4048 100644 (file)
@@ -538,7 +538,7 @@ test_showTree =
 test_showTree' :: Assertion
 test_showTree' =
        (let t = fromDistinctAscList [(x,()) | x <- [1..5]]
-        in s t ) @?= "+--5:=()\n|\n4:=()\n|\n|  +--3:=()\n|  |\n+--2:=()\n   |\n   +--1:=()\n" 
+        in s t ) @?= "+--5:=()\n|\n4:=()\n|\n|  +--3:=()\n|  |\n+--2:=()\n   |\n   +--1:=()\n"
    where
     showElem k x  = show k ++ ":=" ++ show x