content: {-# LANGUAGE CPP #-}
  
  module Data.IntMap.Extra where
  
  #if !MIN_VERSION_containers(0,6,2)
  import Data.IntMap.Internal
  
  -- TODO We can remove this when support for GHC 8.6 is dropped.
  
  -- | /O(n+m)/. Check whether the key sets of two maps are disjoint
  -- (i.e. their 'intersection' is empty).
  --
  -- > disjoint (fromList [(2,'a')]) (fromList [(1,()), (3,())])   == True
  -- > disjoint (fromList [(2,'a')]) (fromList [(1,'a'), (2,'b')]) == False
  -- > disjoint (fromList [])        (fromList [])                 == True
  --
  -- > disjoint a b == null (intersection a b)
  --
  disjoint :: IntMap a -> IntMap b -> Bool
  disjoint Nil _ = True
  disjoint _ Nil = True
  disjoint (Tip kx _) ys = notMember kx ys
  disjoint xs (Tip ky _) = notMember ky xs
  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
  #endif
  