    {-# LANGUAGE CPP #-}
    {-# LANGUAGE DeriveGeneric #-}

    -- |
    --   IP routing table is a tree of 'AddrRange'
    --   to search one of them on the longest
    --   match base. It is a kind of TRIE with one
    --   way branching removed. Both IPv4 and IPv6
    --   are supported.
    module Data.IP.RouteTable.Internal where

    import Control.Applicative hiding (empty)
    import qualified Control.Applicative as A (empty)
    import Control.Monad
    import Data.Bits
    import Data.Foldable (Foldable (..))
    import Data.IP.Addr
    import Data.IP.Op
    import Data.IP.Range
    import Data.IntMap (IntMap, (!))
    import qualified Data.IntMap as IM (fromList)
    import Data.Monoid hiding ((<>))
    import Data.Semigroup
    import Data.Traversable
    import Data.Word
    import GHC.Generics (Generic, Generic1)
    import Prelude hiding (lookup)

    -- $setup
    -- >>> :set -XOverloadedStrings

    ----------------------------------------------------------------

    -- |
    --   A class to contain IPv4 and IPv6.
    class Addr a => Routable a where
        -- |
        --       The 'intToTBit' function takes 'Int' and returns an 'Routable' address
        --       whose only n-th bit is set.
        intToTBit :: Int -> a

        -- |
        --       The 'isZero' function takes an 'Routable' address and an test bit
        --       'Routable' address and returns 'True' is the bit is unset,
        --       otherwise returns 'False'.
        isZero :: a -> a -> Bool

    instance Routable IPv4 where
        intToTBit :: Int -> IPv4
    intToTBit = Int -> IPv4
    intToTBitIPv4
        isZero :: IPv4 -> IPv4 -> Bool
    isZero IPv4
    a IPv4
    b = IPv4
    a IPv4 -> IPv4 -> IPv4
    forall a. Addr a => a -> a -> a
    `masked` IPv4
    b IPv4 -> IPv4 -> Bool
    forall a. Eq a => a -> a -> Bool
    == Word32 -> IPv4
    IP4 Word32
    0

    instance Routable IPv6 where
        intToTBit :: Int -> IPv6
    intToTBit = Int -> IPv6
    intToTBitIPv6
        isZero :: IPv6 -> IPv6 -> Bool
    isZero IPv6
    a IPv6
    b = IPv6
    a IPv6 -> IPv6 -> IPv6
    forall a. Addr a => a -> a -> a
    `masked` IPv6
    b IPv6 -> IPv6 -> Bool
    forall a. Eq a => a -> a -> Bool
    == IPv6Addr -> IPv6
    IP6 (Word32
    0, Word32
    0, Word32
    0, Word32
    0)

    ----------------------------------------------------------------
    --
    -- Test Bit
    --

    intToTBitIPv4 :: Int -> IPv4
    intToTBitIPv4 :: Int -> IPv4
    intToTBitIPv4 Int
    len = Word32 -> IPv4
    IP4 (IntMap Word32
    intToTBitsIPv4 IntMap Word32 -> Int -> Word32
    forall a. IntMap a -> Int -> a
    ! Int
    len)

    intToTBitIPv6 :: Int -> IPv6
    intToTBitIPv6 :: Int -> IPv6
    intToTBitIPv6 Int
    len = IPv6Addr -> IPv6
    IP6 (IntMap IPv6Addr
    intToTBitsIPv6 IntMap IPv6Addr -> Int -> IPv6Addr
    forall a. IntMap a -> Int -> a
    ! Int
    len)

    intToTBitsWord32 :: [Word32]
    intToTBitsWord32 :: [Word32]
    intToTBitsWord32 = (Word32 -> Word32) -> Word32 -> [Word32]
    forall a. (a -> a) -> a -> [a]
    iterate (Word32 -> Int -> Word32
    forall a. Bits a => a -> Int -> a
    `shift` (-Int
    1)) Word32
    0x80000000

    intToTBitsIPv4 :: IntMap IPv4Addr
    intToTBitsIPv4 :: IntMap Word32
    intToTBitsIPv4 = [(Int, Word32)] -> IntMap Word32
    forall a. [(Int, a)] -> IntMap a
    IM.fromList ([(Int, Word32)] -> IntMap Word32)
    -> [(Int, Word32)] -> IntMap Word32
    forall a b. (a -> b) -> a -> b
    $ [Int] -> [Word32] -> [(Int, Word32)]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Int
    0 .. Int
    32] [Word32]
    intToTBitsWord32

    intToTBitsIPv6 :: IntMap IPv6Addr
    intToTBitsIPv6 :: IntMap IPv6Addr
    intToTBitsIPv6 = [(Int, IPv6Addr)] -> IntMap IPv6Addr
    forall a. [(Int, a)] -> IntMap a
    IM.fromList ([(Int, IPv6Addr)] -> IntMap IPv6Addr)
    -> [(Int, IPv6Addr)] -> IntMap IPv6Addr
    forall a b. (a -> b) -> a -> b
    $ [Int] -> [IPv6Addr] -> [(Int, IPv6Addr)]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [Int
    0 .. Int
    128] [IPv6Addr]
    bs
      where
        bs :: [IPv6Addr]
    bs = [IPv6Addr]
    b1 [IPv6Addr] -> [IPv6Addr] -> [IPv6Addr]
    forall a. [a] -> [a] -> [a]
    ++ [IPv6Addr]
    b2 [IPv6Addr] -> [IPv6Addr] -> [IPv6Addr]
    forall a. [a] -> [a] -> [a]
    ++ [IPv6Addr]
    b3 [IPv6Addr] -> [IPv6Addr] -> [IPv6Addr]
    forall a. [a] -> [a] -> [a]
    ++ [IPv6Addr]
    b4 [IPv6Addr] -> [IPv6Addr] -> [IPv6Addr]
    forall a. [a] -> [a] -> [a]
    ++ [IPv6Addr]
    b5
        b1 :: [IPv6Addr]
    b1 = (Word32 -> IPv6Addr) -> [Word32] -> [IPv6Addr]
    forall a b. (a -> b) -> [a] -> [b]
    map (\Word32
    vbit -> (Word32
    vbit, Word32
    all0, Word32
    all0, Word32
    all0)) [Word32]
    intToTBits
        b2 :: [IPv6Addr]
    b2 = (Word32 -> IPv6Addr) -> [Word32] -> [IPv6Addr]
    forall a b. (a -> b) -> [a] -> [b]
    map (\Word32
    vbit -> (Word32
    all0, Word32
    vbit, Word32
    all0, Word32
    all0)) [Word32]
    intToTBits
        b3 :: [IPv6Addr]
    b3 = (Word32 -> IPv6Addr) -> [Word32] -> [IPv6Addr]
    forall a b. (a -> b) -> [a] -> [b]
    map (\Word32
    vbit -> (Word32
    all0, Word32
    all0, Word32
    vbit, Word32
    all0)) [Word32]
    intToTBits
        b4 :: [IPv6Addr]
    b4 = (Word32 -> IPv6Addr) -> [Word32] -> [IPv6Addr]
    forall a b. (a -> b) -> [a] -> [b]
    map (\Word32
    vbit -> (Word32
    all0, Word32
    all0, Word32
    all0, Word32
    vbit)) [Word32]
    intToTBits
        b5 :: [IPv6Addr]
    b5 = [(Word32
    all0, Word32
    all0, Word32
    all0, Word32
    all0)]
        intToTBits :: [Word32]
    intToTBits = Int -> [Word32] -> [Word32]
    forall a. Int -> [a] -> [a]
    take Int
    32 [Word32]
    intToTBitsWord32
        all0 :: Word32
    all0 = Word32
    0x00000000

    ----------------------------------------------------------------

    -- |
    --   The Tree structure for IP routing table based on TRIE with
    --   one way branching removed. This is an abstract data type,
    --   so you cannot touch its inside. Please use 'insert' or 'lookup', instead.
    data IPRTable k a
        = Nil
        | Node !(AddrRange k) !k !(Maybe a) !(IPRTable k a) !(IPRTable k a)
        deriving (IPRTable k a -> IPRTable k a -> Bool
    (IPRTable k a -> IPRTable k a -> Bool)
    -> (IPRTable k a -> IPRTable k a -> Bool) -> Eq (IPRTable k a)
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    forall k a. (Eq k, Eq a) => IPRTable k a -> IPRTable k a -> Bool
    $c== :: forall k a. (Eq k, Eq a) => IPRTable k a -> IPRTable k a -> Bool
    == :: IPRTable k a -> IPRTable k a -> Bool
    $c/= :: forall k a. (Eq k, Eq a) => IPRTable k a -> IPRTable k a -> Bool
    /= :: IPRTable k a -> IPRTable k a -> Bool
    Eq, (forall x. IPRTable k a -> Rep (IPRTable k a) x)
    -> (forall x. Rep (IPRTable k a) x -> IPRTable k a)
    -> Generic (IPRTable k a)
    forall x. Rep (IPRTable k a) x -> IPRTable k a
    forall x. IPRTable k a -> Rep (IPRTable k a) x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    forall k a x. Rep (IPRTable k a) x -> IPRTable k a
    forall k a x. IPRTable k a -> Rep (IPRTable k a) x
    $cfrom :: forall k a x. IPRTable k a -> Rep (IPRTable k a) x
    from :: forall x. IPRTable k a -> Rep (IPRTable k a) x
    $cto :: forall k a x. Rep (IPRTable k a) x -> IPRTable k a
    to :: forall x. Rep (IPRTable k a) x -> IPRTable k a
    Generic, (forall a. IPRTable k a -> Rep1 (IPRTable k) a)
    -> (forall a. Rep1 (IPRTable k) a -> IPRTable k a)
    -> Generic1 (IPRTable k)
    forall a. Rep1 (IPRTable k) a -> IPRTable k a
    forall a. IPRTable k a -> Rep1 (IPRTable k) a
    forall k a. Rep1 (IPRTable k) a -> IPRTable k a
    forall k a. IPRTable k a -> Rep1 (IPRTable k) a
    forall k (f :: k -> *).
    (forall (a :: k). f a -> Rep1 f a)
    -> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
    $cfrom1 :: forall k a. IPRTable k a -> Rep1 (IPRTable k) a
    from1 :: forall a. IPRTable k a -> Rep1 (IPRTable k) a
    $cto1 :: forall k a. Rep1 (IPRTable k) a -> IPRTable k a
    to1 :: forall a. Rep1 (IPRTable k) a -> IPRTable k a
    Generic1, Int -> IPRTable k a -> ShowS
    [IPRTable k a] -> ShowS
    IPRTable k a -> String
    (Int -> IPRTable k a -> ShowS)
    -> (IPRTable k a -> String)
    -> ([IPRTable k a] -> ShowS)
    -> Show (IPRTable k a)
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    forall k a. (Show k, Show a) => Int -> IPRTable k a -> ShowS
    forall k a. (Show k, Show a) => [IPRTable k a] -> ShowS
    forall k a. (Show k, Show a) => IPRTable k a -> String
    $cshowsPrec :: forall k a. (Show k, Show a) => Int -> IPRTable k a -> ShowS
    showsPrec :: Int -> IPRTable k a -> ShowS
    $cshow :: forall k a. (Show k, Show a) => IPRTable k a -> String
    show :: IPRTable k a -> String
    $cshowList :: forall k a. (Show k, Show a) => [IPRTable k a] -> ShowS
    showList :: [IPRTable k a] -> ShowS
    Show)

    ----------------------------------------------------------------

    -- |
    --   The 'empty' function returns an empty IP routing table.
    --
    -- >>> (empty :: IPRTable IPv4 ()) == fromList []
    -- True
    empty :: Routable k => IPRTable k a
    empty :: forall k a. Routable k => IPRTable k a
    empty = IPRTable k a
    forall k a. IPRTable k a
    Nil

    instance Functor (IPRTable k) where
        fmap :: forall a b. (a -> b) -> IPRTable k a -> IPRTable k b
    fmap a -> b
    _ IPRTable k a
    Nil = IPRTable k b
    forall k a. IPRTable k a
    Nil
        fmap a -> b
    f (Node AddrRange k
    r k
    a Maybe a
    mv IPRTable k a
    b1 IPRTable k a
    b2) = AddrRange k
    -> k -> Maybe b -> IPRTable k b -> IPRTable k b -> IPRTable k b
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    r k
    a (a -> b
    f (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Maybe a
    mv) ((a -> b) -> IPRTable k a -> IPRTable k b
    forall a b. (a -> b) -> IPRTable k a -> IPRTable k b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    f IPRTable k a
    b1) ((a -> b) -> IPRTable k a -> IPRTable k b
    forall a b. (a -> b) -> IPRTable k a -> IPRTable k b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    f IPRTable k a
    b2)

    instance Foldable (IPRTable k) where
        foldMap :: forall m a. Monoid m => (a -> m) -> IPRTable k a -> m
    foldMap a -> m
    _ IPRTable k a
    Nil = m
    forall a. Monoid a => a
    mempty
        foldMap a -> m
    f (Node AddrRange k
    _ k
    _ Maybe a
    mv IPRTable k a
    b1 IPRTable k a
    b2) = (a -> m) -> Maybe a -> m
    forall m a. Monoid m => (a -> m) -> Maybe a -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap a -> m
    f Maybe a
    mv m -> m -> m
    forall a. Monoid a => a -> a -> a
    `mappend` (a -> m) -> IPRTable k a -> m
    forall m a. Monoid m => (a -> m) -> IPRTable k a -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap a -> m
    f IPRTable k a
    b1 m -> m -> m
    forall a. Monoid a => a -> a -> a
    `mappend` (a -> m) -> IPRTable k a -> m
    forall m a. Monoid m => (a -> m) -> IPRTable k a -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap a -> m
    f IPRTable k a
    b2

    instance Traversable (IPRTable k) where
        traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> IPRTable k a -> f (IPRTable k b)
    traverse a -> f b
    _ IPRTable k a
    Nil = IPRTable k b -> f (IPRTable k b)
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure IPRTable k b
    forall k a. IPRTable k a
    Nil
        traverse a -> f b
    f (Node AddrRange k
    r k
    a Maybe a
    mv IPRTable k a
    b1 IPRTable k a
    b2) = AddrRange k
    -> k -> Maybe b -> IPRTable k b -> IPRTable k b -> IPRTable k b
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    r k
    a (Maybe b -> IPRTable k b -> IPRTable k b -> IPRTable k b)
    -> f (Maybe b) -> f (IPRTable k b -> IPRTable k b -> IPRTable k b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (a -> f b) -> Maybe a -> f (Maybe b)
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable t, Applicative f) =>
    (a -> f b) -> t a -> f (t b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Maybe a -> f (Maybe b)
    traverse a -> f b
    f Maybe a
    mv f (IPRTable k b -> IPRTable k b -> IPRTable k b)
    -> f (IPRTable k b) -> f (IPRTable k b -> IPRTable k b)
    forall a b. f (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (a -> f b) -> IPRTable k a -> f (IPRTable k b)
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable t, Applicative f) =>
    (a -> f b) -> t a -> f (t b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> IPRTable k a -> f (IPRTable k b)
    traverse a -> f b
    f IPRTable k a
    b1 f (IPRTable k b -> IPRTable k b)
    -> f (IPRTable k b) -> f (IPRTable k b)
    forall a b. f (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (a -> f b) -> IPRTable k a -> f (IPRTable k b)
    forall (t :: * -> *) (f :: * -> *) a b.
    (Traversable t, Applicative f) =>
    (a -> f b) -> t a -> f (t b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> IPRTable k a -> f (IPRTable k b)
    traverse a -> f b
    f IPRTable k a
    b2

    -- | Note that Semigroup and Monoid instances are right-biased.
    --   That is, if both arguments have the same key, the value from the right
    --   argument will be used.
    --   Since: 1.7.5
    instance Routable k => Semigroup (IPRTable k a) where
        IPRTable k a
    a <> :: IPRTable k a -> IPRTable k a -> IPRTable k a
    <> IPRTable k a
    b = (IPRTable k a -> AddrRange k -> a -> IPRTable k a)
    -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall b k a.
    (b -> AddrRange k -> a -> b) -> b -> IPRTable k a -> b
    foldlWithKey (\IPRTable k a
    rt AddrRange k
    k a
    v -> AddrRange k -> a -> IPRTable k a -> IPRTable k a
    forall k a.
    Routable k =>
    AddrRange k -> a -> IPRTable k a -> IPRTable k a
    insert AddrRange k
    k a
    v IPRTable k a
    rt) IPRTable k a
    a IPRTable k a
    b
        stimes :: forall b. Integral b => b -> IPRTable k a -> IPRTable k a
    stimes = b -> IPRTable k a -> IPRTable k a
    forall b a. Integral b => b -> a -> a
    stimesIdempotent

    -- | Since: 1.7.5
    instance Routable k => Monoid (IPRTable k a) where
        mempty :: IPRTable k a
    mempty = IPRTable k a
    forall k a. Routable k => IPRTable k a
    empty
        mappend :: IPRTable k a -> IPRTable k a -> IPRTable k a
    mappend = IPRTable k a -> IPRTable k a -> IPRTable k a
    forall a. Semigroup a => a -> a -> a
    (<>)

    ----------------------------------------------------------------

    -- |
    --   The 'insert' function inserts a value with a key of 'AddrRange' to 'IPRTable'
    --   and returns a new 'IPRTable'.
    --
    -- >>> (insert ("127.0.0.1" :: AddrRange IPv4) () empty) == fromList [("127.0.0.1",())]
    -- True
    insert :: Routable k => AddrRange k -> a -> IPRTable k a -> IPRTable k a
    insert :: forall k a.
    Routable k =>
    AddrRange k -> a -> IPRTable k a -> IPRTable k a
    insert AddrRange k
    k1 a
    v1 IPRTable k a
    Nil = AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    k1 k
    tb1 (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v1) IPRTable k a
    forall k a. IPRTable k a
    Nil IPRTable k a
    forall k a. IPRTable k a
    Nil
      where
        tb1 :: k
    tb1 = AddrRange k -> k
    forall k. Routable k => AddrRange k -> k
    keyToTestBit AddrRange k
    k1
    insert AddrRange k
    k1 a
    v1 s :: IPRTable k a
    s@(Node AddrRange k
    k2 k
    tb2 Maybe a
    v2 IPRTable k a
    l IPRTable k a
    r)
        | AddrRange k
    k1 AddrRange k -> AddrRange k -> Bool
    forall a. Eq a => a -> a -> Bool
    == AddrRange k
    k2 = AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    k1 k
    tb1 (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v1) IPRTable k a
    l IPRTable k a
    r
        | AddrRange k
    k2 AddrRange k -> AddrRange k -> Bool
    forall a. Addr a => AddrRange a -> AddrRange a -> Bool
    >:> AddrRange k
    k1 =
            if AddrRange k -> k -> Bool
    forall k. Routable k => AddrRange k -> k -> Bool
    isLeft AddrRange k
    k1 k
    tb2
                then
                    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    k2 k
    tb2 Maybe a
    v2 (AddrRange k -> a -> IPRTable k a -> IPRTable k a
    forall k a.
    Routable k =>
    AddrRange k -> a -> IPRTable k a -> IPRTable k a
    insert AddrRange k
    k1 a
    v1 IPRTable k a
    l) IPRTable k a
    r
                else
                    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    k2 k
    tb2 Maybe a
    v2 IPRTable k a
    l (AddrRange k -> a -> IPRTable k a -> IPRTable k a
    forall k a.
    Routable k =>
    AddrRange k -> a -> IPRTable k a -> IPRTable k a
    insert AddrRange k
    k1 a
    v1 IPRTable k a
    r)
        | AddrRange k
    k1 AddrRange k -> AddrRange k -> Bool
    forall a. Addr a => AddrRange a -> AddrRange a -> Bool
    >:> AddrRange k
    k2 =
            if AddrRange k -> k -> Bool
    forall k. Routable k => AddrRange k -> k -> Bool
    isLeft AddrRange k
    k2 k
    tb1
                then
                    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    k1 k
    tb1 (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v1) IPRTable k a
    s IPRTable k a
    forall k a. IPRTable k a
    Nil
                else
                    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    k1 k
    tb1 (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v1) IPRTable k a
    forall k a. IPRTable k a
    Nil IPRTable k a
    s
        | Bool
    otherwise =
            let n :: IPRTable k a
    n = AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    k1 k
    tb1 (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v1) IPRTable k a
    forall k a. IPRTable k a
    Nil IPRTable k a
    forall k a. IPRTable k a
    Nil
             in IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    Routable k =>
    IPRTable k a -> IPRTable k a -> IPRTable k a
    link IPRTable k a
    n IPRTable k a
    s
      where
        tb1 :: k
    tb1 = AddrRange k -> k
    forall k. Routable k => AddrRange k -> k
    keyToTestBit AddrRange k
    k1

    link :: Routable k => IPRTable k a -> IPRTable k a -> IPRTable k a
    link :: forall k a.
    Routable k =>
    IPRTable k a -> IPRTable k a -> IPRTable k a
    link s1 :: IPRTable k a
    s1@(Node AddrRange k
    k1 k
    _ Maybe a
    _ IPRTable k a
    _ IPRTable k a
    _) s2 :: IPRTable k a
    s2@(Node AddrRange k
    k2 k
    _ Maybe a
    _ IPRTable k a
    _ IPRTable k a
    _)
        | AddrRange k -> k -> Bool
    forall k. Routable k => AddrRange k -> k -> Bool
    isLeft AddrRange k
    k1 k
    tbg = AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    kg k
    tbg Maybe a
    forall a. Maybe a
    Nothing IPRTable k a
    s1 IPRTable k a
    s2
        | Bool
    otherwise = AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    kg k
    tbg Maybe a
    forall a. Maybe a
    Nothing IPRTable k a
    s2 IPRTable k a
    s1
      where
        kg :: AddrRange k
    kg = Int -> AddrRange k -> AddrRange k -> AddrRange k
    forall k.
    Routable k =>
    Int -> AddrRange k -> AddrRange k -> AddrRange k
    glue Int
    0 AddrRange k
    k1 AddrRange k
    k2
        tbg :: k
    tbg = AddrRange k -> k
    forall k. Routable k => AddrRange k -> k
    keyToTestBit AddrRange k
    kg
    link IPRTable k a
    _ IPRTable k a
    _ = String -> IPRTable k a
    forall a. HasCallStack => String -> a
    error String
    "link"

    glue :: Routable k => Int -> AddrRange k -> AddrRange k -> AddrRange k
    glue :: forall k.
    Routable k =>
    Int -> AddrRange k -> AddrRange k -> AddrRange k
    glue Int
    n AddrRange k
    k1 AddrRange k
    k2
        | AddrRange k -> k
    forall a. AddrRange a -> a
    addr AddrRange k
    k1 k -> k -> k
    forall a. Addr a => a -> a -> a
    `masked` k
    mk k -> k -> Bool
    forall a. Eq a => a -> a -> Bool
    == AddrRange k -> k
    forall a. AddrRange a -> a
    addr AddrRange k
    k2 k -> k -> k
    forall a. Addr a => a -> a -> a
    `masked` k
    mk = Int -> AddrRange k -> AddrRange k -> AddrRange k
    forall k.
    Routable k =>
    Int -> AddrRange k -> AddrRange k -> AddrRange k
    glue (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1) AddrRange k
    k1 AddrRange k
    k2
        | Bool
    otherwise = k -> Int -> AddrRange k
    forall a. Addr a => a -> Int -> AddrRange a
    makeAddrRange (AddrRange k -> k
    forall a. AddrRange a -> a
    addr AddrRange k
    k1) (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1)
      where
        mk :: k
    mk = Int -> k
    forall a. Addr a => Int -> a
    intToMask Int
    n

    keyToTestBit :: Routable k => AddrRange k -> k
    keyToTestBit :: forall k. Routable k => AddrRange k -> k
    keyToTestBit = Int -> k
    forall a. Routable a => Int -> a
    intToTBit (Int -> k) -> (AddrRange k -> Int) -> AddrRange k -> k
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . AddrRange k -> Int
    forall a. AddrRange a -> Int
    mlen

    isLeft :: Routable k => AddrRange k -> k -> Bool
    isLeft :: forall k. Routable k => AddrRange k -> k -> Bool
    isLeft AddrRange k
    adr = k -> k -> Bool
    forall a. Routable a => a -> a -> Bool
    isZero (AddrRange k -> k
    forall a. AddrRange a -> a
    addr AddrRange k
    adr)

    ----------------------------------------------------------------

    -- |
    --   The 'delete' function deletes a value by a key of 'AddrRange' from 'IPRTable'
    --   and returns a new 'IPRTable'.
    --
    -- >>> delete "127.0.0.1" (insert "127.0.0.1" () empty) == (empty :: IPRTable IPv4 ())
    -- True
    delete :: Routable k => AddrRange k -> IPRTable k a -> IPRTable k a
    delete :: forall k a.
    Routable k =>
    AddrRange k -> IPRTable k a -> IPRTable k a
    delete AddrRange k
    _ IPRTable k a
    Nil = IPRTable k a
    forall k a. IPRTable k a
    Nil
    delete AddrRange k
    k1 s :: IPRTable k a
    s@(Node AddrRange k
    k2 k
    tb2 Maybe a
    v2 IPRTable k a
    l IPRTable k a
    r)
        | AddrRange k
    k1 AddrRange k -> AddrRange k -> Bool
    forall a. Eq a => a -> a -> Bool
    == AddrRange k
    k2 = AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    Routable k =>
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    node AddrRange k
    k2 k
    tb2 Maybe a
    forall a. Maybe a
    Nothing IPRTable k a
    l IPRTable k a
    r
        | AddrRange k
    k2 AddrRange k -> AddrRange k -> Bool
    forall a. Addr a => AddrRange a -> AddrRange a -> Bool
    >:> AddrRange k
    k1 =
            if AddrRange k -> k -> Bool
    forall k. Routable k => AddrRange k -> k -> Bool
    isLeft AddrRange k
    k1 k
    tb2
                then
                    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    Routable k =>
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    node AddrRange k
    k2 k
    tb2 Maybe a
    v2 (AddrRange k -> IPRTable k a -> IPRTable k a
    forall k a.
    Routable k =>
    AddrRange k -> IPRTable k a -> IPRTable k a
    delete AddrRange k
    k1 IPRTable k a
    l) IPRTable k a
    r
                else
                    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    Routable k =>
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    node AddrRange k
    k2 k
    tb2 Maybe a
    v2 IPRTable k a
    l (AddrRange k -> IPRTable k a -> IPRTable k a
    forall k a.
    Routable k =>
    AddrRange k -> IPRTable k a -> IPRTable k a
    delete AddrRange k
    k1 IPRTable k a
    r)
        | Bool
    otherwise = IPRTable k a
    s

    node
        :: Routable k
        => AddrRange k -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    node :: forall k a.
    Routable k =>
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    node AddrRange k
    _ k
    _ Maybe a
    Nothing IPRTable k a
    Nil IPRTable k a
    r = IPRTable k a
    r
    node AddrRange k
    _ k
    _ Maybe a
    Nothing IPRTable k a
    l IPRTable k a
    Nil = IPRTable k a
    l
    node AddrRange k
    k k
    tb Maybe a
    v IPRTable k a
    l IPRTable k a
    r = AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    forall k a.
    AddrRange k
    -> k -> Maybe a -> IPRTable k a -> IPRTable k a -> IPRTable k a
    Node AddrRange k
    k k
    tb Maybe a
    v IPRTable k a
    l IPRTable k a
    r

    ----------------------------------------------------------------

    -- |
    --   The 'lookup' function looks up 'IPRTable' with a key of 'AddrRange'.
    --   If a routing information in 'IPRTable' matches the key, its value
    --   is returned.
    --
    -- >>> let v4 = ["133.4.0.0/16","133.5.0.0/16","133.5.16.0/24","133.5.23.0/24"] :: [AddrRange IPv4]
    -- >>> let rt = fromList $ zip v4 v4
    -- >>> lookup "127.0.0.1" rt
    -- Nothing
    -- >>> lookup "133.3.0.1" rt
    -- Nothing
    -- >>> lookup "133.4.0.0" rt
    -- Just 133.4.0.0/16
    -- >>> lookup "133.4.0.1" rt
    -- Just 133.4.0.0/16
    -- >>> lookup "133.5.16.0" rt
    -- Just 133.5.16.0/24
    -- >>> lookup "133.5.16.1" rt
    -- Just 133.5.16.0/24
    lookup :: Routable k => AddrRange k -> IPRTable k a -> Maybe a
    lookup :: forall k a. Routable k => AddrRange k -> IPRTable k a -> Maybe a
    lookup AddrRange k
    k IPRTable k a
    s = ((AddrRange k, a) -> a) -> Maybe (AddrRange k, a) -> Maybe a
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (AddrRange k, a) -> a
    forall a b. (a, b) -> b
    snd (AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    forall k a.
    Routable k =>
    AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    search AddrRange k
    k IPRTable k a
    s Maybe (AddrRange k, a)
    forall a. Maybe a
    Nothing)

    -- |
    --   The 'lookupKeyValue' function looks up 'IPRTable' with a key of 'AddrRange'.
    --   If a routing information in 'IPRTable' matches the key, both key and value
    --   are returned.
    --
    -- >>> :set -XOverloadedStrings
    -- >>> let rt = fromList ([("192.168.0.0/24", 1), ("10.10.0.0/16", 2)] :: [(AddrRange IPv4, Int)])
    -- >>> lookupKeyValue "127.0.0.1" rt
    -- Nothing
    -- >>> lookupKeyValue "192.168.0.1" rt
    -- Just (192.168.0.0/24,1)
    -- >>> lookupKeyValue "10.10.0.1" rt
    -- Just (10.10.0.0/16,2)
    lookupKeyValue
        :: Routable k => AddrRange k -> IPRTable k a -> Maybe (AddrRange k, a)
    lookupKeyValue :: forall k a.
    Routable k =>
    AddrRange k -> IPRTable k a -> Maybe (AddrRange k, a)
    lookupKeyValue AddrRange k
    k IPRTable k a
    s = AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    forall k a.
    Routable k =>
    AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    search AddrRange k
    k IPRTable k a
    s Maybe (AddrRange k, a)
    forall a. Maybe a
    Nothing

    search
        :: Routable k
        => AddrRange k
        -> IPRTable k a
        -> Maybe (AddrRange k, a)
        -> Maybe (AddrRange k, a)
    search :: forall k a.
    Routable k =>
    AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    search AddrRange k
    _ IPRTable k a
    Nil Maybe (AddrRange k, a)
    res = Maybe (AddrRange k, a)
    res
    search AddrRange k
    k1 (Node AddrRange k
    k2 k
    tb2 Maybe a
    Nothing IPRTable k a
    l IPRTable k a
    r) Maybe (AddrRange k, a)
    res
        | AddrRange k
    k1 AddrRange k -> AddrRange k -> Bool
    forall a. Eq a => a -> a -> Bool
    == AddrRange k
    k2 = Maybe (AddrRange k, a)
    res
        | AddrRange k
    k2 AddrRange k -> AddrRange k -> Bool
    forall a. Addr a => AddrRange a -> AddrRange a -> Bool
    >:> AddrRange k
    k1 =
            if AddrRange k -> k -> Bool
    forall k. Routable k => AddrRange k -> k -> Bool
    isLeft AddrRange k
    k1 k
    tb2
                then
                    AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    forall k a.
    Routable k =>
    AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    search AddrRange k
    k1 IPRTable k a
    l Maybe (AddrRange k, a)
    res
                else
                    AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    forall k a.
    Routable k =>
    AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    search AddrRange k
    k1 IPRTable k a
    r Maybe (AddrRange k, a)
    res
        | Bool
    otherwise = Maybe (AddrRange k, a)
    res
    search AddrRange k
    k1 (Node AddrRange k
    k2 k
    tb2 (Just a
    vl) IPRTable k a
    l IPRTable k a
    r) Maybe (AddrRange k, a)
    res
        | AddrRange k
    k1 AddrRange k -> AddrRange k -> Bool
    forall a. Eq a => a -> a -> Bool
    == AddrRange k
    k2 = (AddrRange k, a) -> Maybe (AddrRange k, a)
    forall a. a -> Maybe a
    Just (AddrRange k
    k1, a
    vl)
        | AddrRange k
    k2 AddrRange k -> AddrRange k -> Bool
    forall a. Addr a => AddrRange a -> AddrRange a -> Bool
    >:> AddrRange k
    k1 =
            if AddrRange k -> k -> Bool
    forall k. Routable k => AddrRange k -> k -> Bool
    isLeft AddrRange k
    k1 k
    tb2
                then
                    AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    forall k a.
    Routable k =>
    AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    search AddrRange k
    k1 IPRTable k a
    l (Maybe (AddrRange k, a) -> Maybe (AddrRange k, a))
    -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    forall a b. (a -> b) -> a -> b
    $ (AddrRange k, a) -> Maybe (AddrRange k, a)
    forall a. a -> Maybe a
    Just (AddrRange k
    k2, a
    vl)
                else
                    AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    forall k a.
    Routable k =>
    AddrRange k
    -> IPRTable k a -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    search AddrRange k
    k1 IPRTable k a
    r (Maybe (AddrRange k, a) -> Maybe (AddrRange k, a))
    -> Maybe (AddrRange k, a) -> Maybe (AddrRange k, a)
    forall a b. (a -> b) -> a -> b
    $ (AddrRange k, a) -> Maybe (AddrRange k, a)
    forall a. a -> Maybe a
    Just (AddrRange k
    k2, a
    vl)
        | Bool
    otherwise = Maybe (AddrRange k, a)
    res

    -- |
    --   'lookupAll' is a version of 'lookup' that returns all entries matching the
    --    given key, not just the longest match.
    --
    -- >>> :set -XOverloadedStrings
    -- >>> let rt = fromList ([("192.168.0.0/24", 1), ("10.10.0.0/16", 2), ("10.0.0.0/8", 3)] :: [(AddrRange IPv4, Int)])
    -- >>> lookupAll "127.0.0.1" rt
    -- []
    -- >>> lookupAll "192.168.0.1" rt
    -- [(192.168.0.0/24,1)]
    -- >>> lookupAll "10.10.0.1" rt
    -- [(10.10.0.0/16,2),(10.0.0.0/8,3)]
    lookupAll :: Routable k => AddrRange k -> IPRTable k a -> [(AddrRange k, a)]
    lookupAll :: forall k a.
    Routable k =>
    AddrRange k -> IPRTable k a -> [(AddrRange k, a)]
    lookupAll AddrRange k
    range = [(AddrRange k, a)] -> IPRTable k a -> [(AddrRange k, a)]
    forall {b}.
    [(AddrRange k, b)] -> IPRTable k b -> [(AddrRange k, b)]
    go []
      where
        go :: [(AddrRange k, b)] -> IPRTable k b -> [(AddrRange k, b)]
    go [(AddrRange k, b)]
    acc IPRTable k b
    Nil = [(AddrRange k, b)]
    acc
        go [(AddrRange k, b)]
    acc (Node AddrRange k
    k k
    tb Maybe b
    Nothing IPRTable k b
    l IPRTable k b
    r)
            | AddrRange k
    k AddrRange k -> AddrRange k -> Bool
    forall a. Eq a => a -> a -> Bool
    == AddrRange k
    range = [(AddrRange k, b)]
    acc
            | AddrRange k
    k AddrRange k -> AddrRange k -> Bool
    forall a. Addr a => AddrRange a -> AddrRange a -> Bool
    >:> AddrRange k
    range = [(AddrRange k, b)] -> IPRTable k b -> [(AddrRange k, b)]
    go [(AddrRange k, b)]
    acc (IPRTable k b -> [(AddrRange k, b)])
    -> IPRTable k b -> [(AddrRange k, b)]
    forall a b. (a -> b) -> a -> b
    $ if AddrRange k -> k -> Bool
    forall k. Routable k => AddrRange k -> k -> Bool
    isLeft AddrRange k
    range k
    tb then IPRTable k b
    l else IPRTable k b
    r
            | Bool
    otherwise = [(AddrRange k, b)]
    acc
        go [(AddrRange k, b)]
    acc (Node AddrRange k
    k k
    tb (Just b
    v) IPRTable k b
    l IPRTable k b
    r)
            | AddrRange k
    k AddrRange k -> AddrRange k -> Bool
    forall a. Eq a => a -> a -> Bool
    == AddrRange k
    range = (AddrRange k
    k, b
    v) (AddrRange k, b) -> [(AddrRange k, b)] -> [(AddrRange k, b)]
    forall a. a -> [a] -> [a]
    : [(AddrRange k, b)]
    acc
            | AddrRange k
    k AddrRange k -> AddrRange k -> Bool
    forall a. Addr a => AddrRange a -> AddrRange a -> Bool
    >:> AddrRange k
    range = [(AddrRange k, b)] -> IPRTable k b -> [(AddrRange k, b)]
    go ((AddrRange k
    k, b
    v) (AddrRange k, b) -> [(AddrRange k, b)] -> [(AddrRange k, b)]
    forall a. a -> [a] -> [a]
    : [(AddrRange k, b)]
    acc) (IPRTable k b -> [(AddrRange k, b)])
    -> IPRTable k b -> [(AddrRange k, b)]
    forall a b. (a -> b) -> a -> b
    $ if AddrRange k -> k -> Bool
    forall k. Routable k => AddrRange k -> k -> Bool
    isLeft AddrRange k
    range k
    tb then IPRTable k b
    l else IPRTable k b
    r
            | Bool
    otherwise = [(AddrRange k, b)]
    acc

    ----------------------------------------------------------------

    -- |
    --   The 'findMatch' function looks up 'IPRTable' with a key of 'AddrRange'.
    --   If the key matches routing informations in 'IPRTable', they are
    --   returned.
    --
    -- >>> let v4 = ["133.4.0.0/16","133.5.0.0/16","133.5.16.0/24","133.5.23.0/24"] :: [AddrRange IPv4]
    -- >>> let rt = fromList $ zip v4 $ repeat ()
    -- >>> findMatch "133.4.0.0/15" rt :: [(AddrRange IPv4,())]
    -- [(133.4.0.0/16,()),(133.5.0.0/16,()),(133.5.16.0/24,()),(133.5.23.0/24,())]
    findMatch
        :: Alternative m => Routable k => AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    findMatch :: forall (m :: * -> *) k a.
    (Alternative m, Routable k) =>
    AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    findMatch AddrRange k
    _ IPRTable k a
    Nil = m (AddrRange k, a)
    forall a. m a
    forall (f :: * -> *) a. Alternative f => f a
    A.empty
    findMatch AddrRange k
    k1 (Node AddrRange k
    k2 k
    _ Maybe a
    Nothing IPRTable k a
    l IPRTable k a
    r)
        | AddrRange k
    k1 AddrRange k -> AddrRange k -> Bool
    forall a. Addr a => AddrRange a -> AddrRange a -> Bool
    >:> AddrRange k
    k2 = AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    forall (m :: * -> *) k a.
    (Alternative m, Routable k) =>
    AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    findMatch AddrRange k
    k1 IPRTable k a
    l m (AddrRange k, a) -> m (AddrRange k, a) -> m (AddrRange k, a)
    forall a. m a -> m a -> m a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    forall (m :: * -> *) k a.
    (Alternative m, Routable k) =>
    AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    findMatch AddrRange k
    k1 IPRTable k a
    r
        | AddrRange k
    k2 AddrRange k -> AddrRange k -> Bool
    forall a. Addr a => AddrRange a -> AddrRange a -> Bool
    >:> AddrRange k
    k1 = AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    forall (m :: * -> *) k a.
    (Alternative m, Routable k) =>
    AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    findMatch AddrRange k
    k1 IPRTable k a
    l m (AddrRange k, a) -> m (AddrRange k, a) -> m (AddrRange k, a)
    forall a. m a -> m a -> m a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    forall (m :: * -> *) k a.
    (Alternative m, Routable k) =>
    AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    findMatch AddrRange k
    k1 IPRTable k a
    r
        | Bool
    otherwise = m (AddrRange k, a)
    forall a. m a
    forall (f :: * -> *) a. Alternative f => f a
    A.empty
    findMatch AddrRange k
    k1 (Node AddrRange k
    k2 k
    _ (Just a
    vl) IPRTable k a
    l IPRTable k a
    r)
        | AddrRange k
    k1 AddrRange k -> AddrRange k -> Bool
    forall a. Addr a => AddrRange a -> AddrRange a -> Bool
    >:> AddrRange k
    k2 = (AddrRange k, a) -> m (AddrRange k, a)
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (AddrRange k
    k2, a
    vl) m (AddrRange k, a) -> m (AddrRange k, a) -> m (AddrRange k, a)
    forall a. m a -> m a -> m a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    forall (m :: * -> *) k a.
    (Alternative m, Routable k) =>
    AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    findMatch AddrRange k
    k1 IPRTable k a
    l m (AddrRange k, a) -> m (AddrRange k, a) -> m (AddrRange k, a)
    forall a. m a -> m a -> m a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    forall (m :: * -> *) k a.
    (Alternative m, Routable k) =>
    AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    findMatch AddrRange k
    k1 IPRTable k a
    r
        | AddrRange k
    k2 AddrRange k -> AddrRange k -> Bool
    forall a. Addr a => AddrRange a -> AddrRange a -> Bool
    >:> AddrRange k
    k1 = AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    forall (m :: * -> *) k a.
    (Alternative m, Routable k) =>
    AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    findMatch AddrRange k
    k1 IPRTable k a
    l m (AddrRange k, a) -> m (AddrRange k, a) -> m (AddrRange k, a)
    forall a. m a -> m a -> m a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    forall (m :: * -> *) k a.
    (Alternative m, Routable k) =>
    AddrRange k -> IPRTable k a -> m (AddrRange k, a)
    findMatch AddrRange k
    k1 IPRTable k a
    r
        | Bool
    otherwise = m (AddrRange k, a)
    forall a. m a
    forall (f :: * -> *) a. Alternative f => f a
    A.empty

    ----------------------------------------------------------------

    -- |
    --   The 'fromList' function creates a new IP routing table from
    --   a list of a pair of 'IPrange' and value.
    fromList :: Routable k => [(AddrRange k, a)] -> IPRTable k a
    fromList :: forall k a. Routable k => [(AddrRange k, a)] -> IPRTable k a
    fromList = (IPRTable k a -> (AddrRange k, a) -> IPRTable k a)
    -> IPRTable k a -> [(AddrRange k, a)] -> IPRTable k a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' (\IPRTable k a
    s (AddrRange k
    k, a
    v) -> AddrRange k -> a -> IPRTable k a -> IPRTable k a
    forall k a.
    Routable k =>
    AddrRange k -> a -> IPRTable k a -> IPRTable k a
    insert AddrRange k
    k a
    v IPRTable k a
    s) IPRTable k a
    forall k a. Routable k => IPRTable k a
    empty

    -- |
    --   The 'toList' function creates a list of a pair of 'AddrRange' and
    --   value from an IP routing table.
    toList :: Routable k => IPRTable k a -> [(AddrRange k, a)]
    toList :: forall k a. Routable k => IPRTable k a -> [(AddrRange k, a)]
    toList = (IPRTable k a -> [(AddrRange k, a)] -> [(AddrRange k, a)])
    -> [(AddrRange k, a)] -> IPRTable k a -> [(AddrRange k, a)]
    forall k a b. (IPRTable k a -> b -> b) -> b -> IPRTable k a -> b
    foldt IPRTable k a -> [(AddrRange k, a)] -> [(AddrRange k, a)]
    forall {k} {b}.
    IPRTable k b -> [(AddrRange k, b)] -> [(AddrRange k, b)]
    toL []
      where
        toL :: IPRTable k b -> [(AddrRange k, b)] -> [(AddrRange k, b)]
    toL IPRTable k b
    Nil [(AddrRange k, b)]
    xs = [(AddrRange k, b)]
    xs
        toL (Node AddrRange k
    _ k
    _ Maybe b
    Nothing IPRTable k b
    _ IPRTable k b
    _) [(AddrRange k, b)]
    xs = [(AddrRange k, b)]
    xs
        toL (Node AddrRange k
    k k
    _ (Just b
    a) IPRTable k b
    _ IPRTable k b
    _) [(AddrRange k, b)]
    xs = (AddrRange k
    k, b
    a) (AddrRange k, b) -> [(AddrRange k, b)] -> [(AddrRange k, b)]
    forall a. a -> [a] -> [a]
    : [(AddrRange k, b)]
    xs

    ----------------------------------------------------------------

    foldt :: (IPRTable k a -> b -> b) -> b -> IPRTable k a -> b
    foldt :: forall k a b. (IPRTable k a -> b -> b) -> b -> IPRTable k a -> b
    foldt IPRTable k a -> b -> b
    _ b
    v IPRTable k a
    Nil = b
    v
    foldt IPRTable k a -> b -> b
    func b
    v rt :: IPRTable k a
    rt@(Node AddrRange k
    _ k
    _ Maybe a
    _ IPRTable k a
    l IPRTable k a
    r) = (IPRTable k a -> b -> b) -> b -> IPRTable k a -> b
    forall k a b. (IPRTable k a -> b -> b) -> b -> IPRTable k a -> b
    foldt IPRTable k a -> b -> b
    func ((IPRTable k a -> b -> b) -> b -> IPRTable k a -> b
    forall k a b. (IPRTable k a -> b -> b) -> b -> IPRTable k a -> b
    foldt IPRTable k a -> b -> b
    func (IPRTable k a -> b -> b
    func IPRTable k a
    rt b
    v) IPRTable k a
    l) IPRTable k a
    r

    -- | /O(n)/. Fold the keys and values in the IPRTable using the given
    --   left-associative binary operator.
    --   This function is equivalent to Data.Map.foldlWithKey with necessary to
    --   IPRTable changes.
    --   Since: 1.7.5
    foldlWithKey :: (b -> AddrRange k -> a -> b) -> b -> IPRTable k a -> b
    foldlWithKey :: forall b k a.
    (b -> AddrRange k -> a -> b) -> b -> IPRTable k a -> b
    foldlWithKey b -> AddrRange k -> a -> b
    f b
    zr = b -> IPRTable k a -> b
    go b
    zr
      where
        go :: b -> IPRTable k a -> b
    go b
    z IPRTable k a
    Nil = b
    z
        go b
    z (Node AddrRange k
    _ k
    _ Maybe a
    Nothing IPRTable k a
    l IPRTable k a
    r) = b -> IPRTable k a -> b
    go (b -> IPRTable k a -> b
    go b
    z IPRTable k a
    l) IPRTable k a
    r
        go b
    z (Node AddrRange k
    n k
    _ (Just a
    v) IPRTable k a
    l IPRTable k a
    r) = b -> IPRTable k a -> b
    go (b -> AddrRange k -> a -> b
    f (b -> IPRTable k a -> b
    go b
    z IPRTable k a
    l) AddrRange k
    n a
    v) IPRTable k a
    r
    {-# INLINE foldlWithKey #-}

    -- | /O(n)/. Fold the keys and values in the IPRTable using the given
    --   right-associative binary operator.
    --   This function is equivalent to Data.Map.foldrWithKey with necessary to
    --   IPRTable changes.
    --   Since: 1.7.5
    foldrWithKey :: (AddrRange k -> a -> b -> b) -> b -> IPRTable k a -> b
    foldrWithKey :: forall k a b.
    (AddrRange k -> a -> b -> b) -> b -> IPRTable k a -> b
    foldrWithKey AddrRange k -> a -> b -> b
    f b
    zr = b -> IPRTable k a -> b
    go b
    zr
      where
        go :: b -> IPRTable k a -> b
    go b
    z IPRTable k a
    Nil = b
    z
        go b
    z (Node AddrRange k
    _ k
    _ Maybe a
    Nothing IPRTable k a
    l IPRTable k a
    r) = b -> IPRTable k a -> b
    go (b -> IPRTable k a -> b
    go b
    z IPRTable k a
    r) IPRTable k a
    l
        go b
    z (Node AddrRange k
    n k
    _ (Just a
    v) IPRTable k a
    l IPRTable k a
    r) = b -> IPRTable k a -> b
    go (AddrRange k -> a -> b -> b
    f AddrRange k
    n a
    v (b -> IPRTable k a -> b
    go b
    z IPRTable k a
    r)) IPRTable k a
    l
    {-# INLINE foldrWithKey #-}