    {-# 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