Add function to check if two `IntSet`s are `disjoint`.
authorVíctor López Juan <victor@lopezjuan.com>
Sun, 1 Jan 2017 21:12:43 +0000 (22:12 +0100)
committerVíctor López Juan <victor@lopezjuan.com>
Sun, 21 Jan 2018 16:19:58 +0000 (17:19 +0100)
This function is equivalent to computing the intersection and checking
if it is empty. However, it is more efficient because the intersection
set does not need to be built in memory, and the computation can
be short-circuited as soon as two non-disjoint `Tip`s are found.

Benchmark intset-benchmarks: RUNNING...
[...]
benchmarking disjoint:false
time                 149.2 ns   (147.7 ns .. 150.6 ns)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 147.0 ns   (145.4 ns .. 148.6 ns)
std dev              5.281 ns   (4.234 ns .. 6.800 ns)
variance introduced by outliers: 54% (severely inflated)

benchmarking disjoint:true
time                 2.500 μs   (2.468 μs .. 2.533 μs)
                     0.999 R²   (0.999 R² .. 0.999 R²)
mean                 2.451 μs   (2.425 μs .. 2.477 μs)
std dev              81.58 ns   (69.22 ns .. 98.12 ns)
variance introduced by outliers: 44% (moderately inflated)

benchmarking null.intersection:false
time                 4.077 μs   (4.038 μs .. 4.122 μs)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 4.026 μs   (3.983 μs .. 4.090 μs)
std dev              170.3 ns   (121.3 ns .. 264.2 ns)
variance introduced by outliers: 54% (severely inflated)

benchmarking null.intersection:true
time                 2.527 μs   (2.468 μs .. 2.610 μs)
                     0.996 R²   (0.993 R² .. 0.999 R²)
mean                 2.490 μs   (2.459 μs .. 2.535 μs)
std dev              122.4 ns   (85.89 ns .. 180.2 ns)
variance introduced by outliers: 63% (severely inflated)

Data/IntSet.hs
Data/IntSet/Internal.hs
benchmarks/IntSet.hs
tests/intset-properties.hs

index 7100523..f47dccf 100644 (file)
@@ -74,6 +74,7 @@ module Data.IntSet (
             , lookupGE
             , isSubsetOf
             , isProperSubsetOf
+            , disjoint
 
             -- * Construction
             , empty
index ea1124e..3772bcd 100644 (file)
@@ -118,6 +118,7 @@ module Data.IntSet.Internal (
     , lookupGE
     , isSubsetOf
     , isProperSubsetOf
+    , disjoint
 
     -- * Construction
     , empty
@@ -660,6 +661,54 @@ isSubsetOf Nil _         = True
 
 
 {--------------------------------------------------------------------
+  Disjoint
+--------------------------------------------------------------------}
+-- | /O(n+m)/. Check whether two sets are disjoint (i.e. their intersection
+--   is empty).
+--
+-- > disjoint (fromList [2,4,6])   (fromList [1,3])     == True
+-- > disjoint (fromList [2,4,6,8]) (fromList [2,3,5,7]) == False
+-- > disjoint (fromList [1,2])     (fromList [1,2,3,4]) == False
+-- > disjoint (fromList [])        (fromList [])        == True
+--
+-- @since 0.5.11
+disjoint :: IntSet -> IntSet -> Bool
+disjoint t1@(Bin p1 m1 l1 r1) t2@(Bin p2 m2 l2 r2)
+  | shorter m1 m2  = disjoint1
+  | shorter m2 m1  = disjoint2
+  | p1 == p2       = disjoint l1 l2 && disjoint r1 r2
+  | otherwise      = True
+  where
+    disjoint1 | nomatch p2 p1 m1  = True
+              | zero p2 m1        = disjoint l1 t2
+              | otherwise         = disjoint r1 t2
+
+    disjoint2 | nomatch p1 p2 m2  = True
+              | zero p1 m2        = disjoint t1 l2
+              | otherwise         = disjoint t1 r2
+
+disjoint t1@(Bin _ _ _ _) (Tip kx2 bm2) = disjointBM t1
+  where disjointBM (Bin p1 m1 l1 r1) | nomatch kx2 p1 m1 = True
+                                     | zero kx2 m1       = disjointBM l1
+                                     | otherwise         = disjointBM r1
+        disjointBM (Tip kx1 bm1) | kx1 == kx2 = (bm1 .&. bm2) == 0
+                                 | otherwise = True
+        disjointBM Nil = True
+
+disjoint (Bin _ _ _ _) Nil = True
+
+disjoint (Tip kx1 bm1) t2 = disjointBM t2
+  where disjointBM (Bin p2 m2 l2 r2) | nomatch kx1 p2 m2 = True
+                                     | zero kx1 m2       = disjointBM l2
+                                     | otherwise         = disjointBM r2
+        disjointBM (Tip kx2 bm2) | kx1 == kx2 = (bm1 .&. bm2) == 0
+                                 | otherwise = True
+        disjointBM Nil = True
+
+disjoint Nil _ = True
+
+
+{--------------------------------------------------------------------
   Filter
 --------------------------------------------------------------------}
 -- | /O(n)/. Filter all elements that satisfy some predicate.
index 7288e2e..95d99d5 100644 (file)
@@ -32,6 +32,10 @@ main = do
         , bench "fromList" $ whnf S.fromList elems
         , bench "fromAscList" $ whnf S.fromAscList elems
         , bench "fromDistinctAscList" $ whnf S.fromDistinctAscList elems
+        , bench "disjoint:false" $ whnf (S.disjoint s) s_even
+        , bench "disjoint:true" $ whnf (S.disjoint s_odd) s_even
+        , bench "null.intersection:false" $ whnf (S.null. S.intersection s) s_even
+        , bench "null.intersection:true" $ whnf (S.null. S.intersection s_odd) s_even
         ]
   where
     elems = [1..2^12]
index 56283c0..eecb9eb 100644 (file)
@@ -54,6 +54,7 @@ main = defaultMain [ testCase "lookupLT" test_lookupLT
                    , testProperty "prop_isProperSubsetOf2" prop_isProperSubsetOf2
                    , testProperty "prop_isSubsetOf" prop_isSubsetOf
                    , testProperty "prop_isSubsetOf2" prop_isSubsetOf2
+                   , testProperty "prop_disjoint" prop_disjoint
                    , testProperty "prop_size" prop_size
                    , testProperty "prop_findMax" prop_findMax
                    , testProperty "prop_findMin" prop_findMin
@@ -202,7 +203,7 @@ prop_MemberFromList xs
         t = fromList abs_xs
 
 {--------------------------------------------------------------------
-  Union
+  Union, Difference and Intersection
 --------------------------------------------------------------------}
 prop_UnionInsert :: Int -> IntSet -> Property
 prop_UnionInsert x t =
@@ -233,6 +234,9 @@ prop_Int xs ys =
       valid t .&&.
       toAscList t === List.sort (nub ((List.intersect) (xs)  (ys)))
 
+prop_disjoint :: IntSet -> IntSet -> Bool
+prop_disjoint a b = a `disjoint` b == null (a `intersection` b)
+
 {--------------------------------------------------------------------
   Lists
 --------------------------------------------------------------------}
@@ -402,3 +406,4 @@ prop_bitcount a w = bitcount_orig a w == bitcount_new a w
             go a x = go (a + 1) (x .&. (x-1))
     bitcount_new a x = a + popCount x
 #endif
+