{-# LANGUAGE UnboxedTuples #-}

{-# OPTIONS_HADDOCK not-home #-}

{-|
    Data structure internals, helper operations and unsafe functions.
 -}

module Data.Radix1Tree.Word8.Strict.Unsafe
  ( Radix1Tree (..)

    -- * Bit operations
  , Prefix
  , Key

    -- | === Compare
  , beyond
  , upper
  , lower

    -- | === Create
  , Mask
  , zeroBit
  , mask
  , branchingBit

    -- * Exceptions
  , MalformedTree (..)

    -- * Edges
    -- ** Lookup
  , Lookup1 (..)

    -- | === Min
  , unsafeLookupMin
  , unsafeLookupMinWithKey

    -- | === Max
  , unsafeLookupMax
  , unsafeLookupMaxWithKey

    -- ** Map
    -- | === Min
  , unsafeAdjustMin
  , unsafeAdjustMin'
  , unsafeAdjustMinWithKey
  , unsafeAdjustMinWithKey'

    -- | === Max
  , unsafeAdjustMax
  , unsafeAdjustMax'
  , unsafeAdjustMaxWithKey
  , unsafeAdjustMaxWithKey'

    -- ** Delete
  , unsafeDeleteMin
  , unsafeDeleteMax

    -- ** Update
    -- | === Min
  , unsafeUpdateMin
  , unsafeUpdateMinWithKey

    -- | === Max
  , unsafeUpdateMax
  , unsafeUpdateMaxWithKey

    -- ** View
    -- | === Min
  , ViewL1 (..)
  , unsafeMinView

    -- | === Max
  , ViewR1 (..)
  , unsafeMaxView

    -- * Full-tree
    -- ** Merge
  , merge
  ) where

import           Data.RadixNTree.Word8.Key
import           Data.RadixNTree.Word8.Common
import           Data.RadixNTree.Word8.Strict
import           Radix.Exception
import           Radix.Word.Foundation



-- | \(\mathcal{O}(k)\).
--   Look up a value at the leftmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeLookupMin :: Radix1Tree a -> (# a #)
unsafeLookupMin :: forall a. Radix1Tree a -> (# a #)
unsafeLookupMin = Radix1Tree a -> (# a #)
forall a. Radix1Tree a -> (# a #)
unsafeLookupMin1

-- | \(\mathcal{O}(k)\).
--   Look up a value at the leftmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeLookupMinWithKey :: Radix1Tree a -> Lookup1 a
unsafeLookupMinWithKey :: forall a. Radix1Tree a -> Lookup1 a
unsafeLookupMinWithKey = Radix1Tree a -> Lookup1 a
forall a. Radix1Tree a -> Lookup1 a
unsafeLookupMinWithKey1

-- | \(\mathcal{O}(k)\).
--   Delete a value at the leftmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeDeleteMin :: Radix1Tree a -> Radix1Tree a
unsafeDeleteMin :: forall a. Radix1Tree a -> Radix1Tree a
unsafeDeleteMin = Radix1Tree a -> Radix1Tree a
forall a. Radix1Tree a -> Radix1Tree a
unsafeDeleteMin1

-- | \(\mathcal{O}(k)\).
--   Update a value at the leftmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeAdjustMin :: (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMin :: forall a. (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMin = (a -> a) -> Radix1Tree a -> Radix1Tree a
forall a. (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMin1

-- | \(\mathcal{O}(k)\).
--   Update a value at the leftmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeAdjustMinWithKey :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMinWithKey :: forall a. (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMinWithKey = (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
forall a. (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMinWithKey1

-- | \(\mathcal{O}(k)\).
--   Update a value at the leftmost key in the tree.
--
--   New value is evaluated to WHNF.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeAdjustMin' :: (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMin' :: forall a. (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMin' = (a -> a) -> Radix1Tree a -> Radix1Tree a
forall a. (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMin1'

-- | \(\mathcal{O}(k)\).
--   Update a value at the leftmost key in the tree.
--
--   New value is evaluated to WHNF.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeAdjustMinWithKey' :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMinWithKey' :: forall a. (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMinWithKey' = (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
forall a. (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMinWithKey1'

-- | \(\mathcal{O}(k)\).
--   Update or delete a value at the leftmost key in the tree.
unsafeUpdateMin :: (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMin :: forall a. (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMin = (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
forall a. (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMin1

-- | \(\mathcal{O}(k)\).
--   Update or delete a value at the leftmost key in the tree.
unsafeUpdateMinWithKey :: (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMinWithKey :: forall a. (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMinWithKey = (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
forall a. (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMinWithKey1

-- | \(\mathcal{O}(\min(x,k))\).
--   Look up the leftmost value and return it alongside the tree without it.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeMinView :: Radix1Tree a -> ViewL1 a
unsafeMinView :: forall a. Radix1Tree a -> ViewL1 a
unsafeMinView = Radix1Tree a -> ViewL1 a
forall a. Radix1Tree a -> ViewL1 a
unsafeMinView1



-- | \(\mathcal{O}(k)\).
--   Look up a value at the rightmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeLookupMax :: Radix1Tree a -> (# a #)
unsafeLookupMax :: forall a. Radix1Tree a -> (# a #)
unsafeLookupMax = Radix1Tree a -> (# a #)
forall a. Radix1Tree a -> (# a #)
unsafeLookupMax1

-- | \(\mathcal{O}(k)\).
--   Look up a value at the rightmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeLookupMaxWithKey :: Radix1Tree a -> Lookup1 a
unsafeLookupMaxWithKey :: forall a. Radix1Tree a -> Lookup1 a
unsafeLookupMaxWithKey = Radix1Tree a -> Lookup1 a
forall a. Radix1Tree a -> Lookup1 a
unsafeLookupMaxWithKey1

-- | \(\mathcal{O}(k)\).
--   Delete a value at the rightmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeDeleteMax :: Radix1Tree a -> Radix1Tree a
unsafeDeleteMax :: forall a. Radix1Tree a -> Radix1Tree a
unsafeDeleteMax = Radix1Tree a -> Radix1Tree a
forall a. Radix1Tree a -> Radix1Tree a
unsafeDeleteMax1

-- | \(\mathcal{O}(k)\).
--   Update a value at the rightmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeAdjustMax :: (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMax :: forall a. (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMax = (a -> a) -> Radix1Tree a -> Radix1Tree a
forall a. (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMax1

-- | \(\mathcal{O}(k)\).
--   Update a value at the rightmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeAdjustMaxWithKey :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMaxWithKey :: forall a. (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMaxWithKey = (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
forall a. (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMaxWithKey1

-- | \(\mathcal{O}(k)\).
--   Update a value at the rightmost key in the tree.
--
--   New value is evaluated to WHNF.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeAdjustMax' :: (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMax' :: forall a. (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMax' = (a -> a) -> Radix1Tree a -> Radix1Tree a
forall a. (a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMax1'

-- | \(\mathcal{O}(k)\).
--   Update a value at the rightmost key in the tree.
--
--   New value is evaluated to WHNF.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeAdjustMaxWithKey' :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMaxWithKey' :: forall a. (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMaxWithKey' = (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
forall a. (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a
unsafeAdjustMaxWithKey1'

-- | \(\mathcal{O}(k)\).
--   Update or delete a value at the rightmost key in the tree.
unsafeUpdateMax :: (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMax :: forall a. (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMax = (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
forall a. (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMax1

-- | \(\mathcal{O}(k)\).
--   Update or delete a value at the rightmost key in the tree.
unsafeUpdateMaxWithKey :: (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMaxWithKey :: forall a. (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMaxWithKey = (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
forall a. (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a
unsafeUpdateMaxWithKey1

-- | \(\mathcal{O}(\min(x,k))\).
--   Look up the rightmost value and return it alongside the tree without it.
--
--   Throws 'MalformedTree' if the tree is empty.
unsafeMaxView :: Radix1Tree a -> ViewR1 a
unsafeMaxView :: forall a. Radix1Tree a -> ViewR1 a
unsafeMaxView = Radix1Tree a -> ViewR1 a
forall a. Radix1Tree a -> ViewR1 a
unsafeMaxView1



-- | \(\mathcal{O}(n_A k_A + n_B k_B)\).
--   General merge of two trees.
--
--   Resulting 'Maybe's and 'Radix1Tree's in argument functions are evaluated to WHNF.
--
--   This functions inlines when all argument functions are provided.
{-# INLINE merge #-}
merge
  :: (Build1 -> a -> b -> Maybe c)           -- ^ Single value collision
  -> (Build1 -> a -> Maybe c)                -- ^ Single left value
  -> (Build -> Radix1Tree a -> Radix1Tree c) -- ^ Left subtree
  -> (Build1 -> b -> Maybe c)                -- ^ Single right value
  -> (Build -> Radix1Tree b -> Radix1Tree c) -- ^ Right subtree
  -> Radix1Tree a
  -> Radix1Tree b
  -> Radix1Tree c
merge :: forall a b c.
(Build1 -> a -> b -> Maybe c)
-> (Build1 -> a -> Maybe c)
-> (Build -> Radix1Tree a -> Radix1Tree c)
-> (Build1 -> b -> Maybe c)
-> (Build -> Radix1Tree b -> Radix1Tree c)
-> Radix1Tree a
-> Radix1Tree b
-> Radix1Tree c
merge = (Build1 -> a -> b -> Maybe c)
-> (Build1 -> a -> Maybe c)
-> (Build -> Radix1Tree a -> Radix1Tree c)
-> (Build1 -> b -> Maybe c)
-> (Build -> Radix1Tree b -> Radix1Tree c)
-> Radix1Tree a
-> Radix1Tree b
-> Radix1Tree c
forall a b c.
(Build1 -> a -> b -> Maybe c)
-> (Build1 -> a -> Maybe c)
-> (Build -> Radix1Tree a -> Radix1Tree c)
-> (Build1 -> b -> Maybe c)
-> (Build -> Radix1Tree b -> Radix1Tree c)
-> Radix1Tree a
-> Radix1Tree b
-> Radix1Tree c
merge1