{-# OPTIONS_GHC -fglasgow-exts #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Trie.General.Types
-- Copyright   :  (c) Adrian Hey 2007
-- License     :  BSD3
--
-- Maintainer  :  http://homepages.nildram.co.uk/~ahey/em.png
-- Stability   :  provisional
-- Portability :  Multi-parameter type classes, Functional dependencies
--
-- This module defines the Generalised Trie type class ('GT') and a few
-- helper types.
-----------------------------------------------------------------------------
module Data.Trie.General.Types
(-- * Classes
 GT(..)

 -- * Types
,Status(..)

 -- * GT Extra functions (common to all instances)
,write
,lookupM
,elemsAscending,elemsDescending
,assocsAscending,assocsDescending
,keysAscending,keysDescending
,size
,isProperSubsetOf,isProperSubmapOfBy
,addKeys,stripKeys
,insertAssocs,fromAssocs
,insertAssocs',fromAssocs'
,insertAssocsMaybe,insertAssocsMaybe'
,insertAssocsAscending,insertAssocsAscendingL
,insertAssocsAscending',insertAssocsAscendingL'
,insertAssocsAscendingMaybe,insertAssocsAscendingMaybeL
,insertAssocsDescending,insertAssocsDescendingL
,insertAssocsDescending',insertAssocsDescendingL'
,insertAssocsDescendingMaybe,insertAssocsDescendingMaybeL
,partition,partitionMaybe
,partitionAscendingList,partitionAscendingListMaybe
,partitionDescendingList,partitionDescendingListMaybe
,sortAscending,sortDescending
) where

{- ToDo:
Make sorts more efficient once some paths system has been worked out
-}


import Prelude hiding (map,filter,lookup)
import qualified Data.List as L (foldl')

#ifdef __GLASGOW_HASKELL__
import GHC.Base hiding (map)
#include "ghcdefs.h"
#else
#include "h98defs.h"
#endif

-------------------------------------------------------
----            GT Class Definition                ----
-------------------------------------------------------

-- | The Generalised Trie type class. This class defines a standardised map API that may be used
-- directly as a map in user code or may be used in the definition of 'GT' instances for other types
-- (recursively).
--
-- Despite it's name, it is not necessary that the underlying concrete implementation
-- is based on any kind of Trie (general or otherwise). Any implementation will do.
--
-- However, this API has been designed with Trie implementations in mind. Generally Tries /do not/
-- store copies of keys in their data structure. So if the actual key value is required for some
-- reason it usually has to be reconstructed from scratch. This is likely to be an expensive
-- heap burning activity for non-trivial keys so such operations should be avoided if possible.
-- Therefore various \"blahWithKeys\" methods found in other map APIs are not present here. If you
-- want to support such operations you should include the key value in the maps /associated values/.
-- The method 'mapWithKey' is the one exception to this rule and has been provided to help
-- you include keys in associated values retrospectively. Methods 'foldrAssocsAscending' and
-- 'foldrAssocsDescending' are also provided as these are required to implement the 'assocsAscending'
-- and 'assocsDescending' functions.
--
-- The module "Data.Trie.General.OrdGT" provides a default implementation of this API for any
-- key type (which is an instance of 'Ord') using AVL trees. This is intended a temporary solution until
-- the full automated derivation of more efficient Trie types for any key type is available.
--
-- A couple of notes regarding 'GT' and 'Ord':
--
-- * Instances of 'GT' are also instances of 'Ord' if the associated values
-- are instances of 'Ord'. All such instances must satisfy the law..
--
-- @'compare' map0 map1 = 'compare' ('assocsAscending' map0) ('assocsAscending' map1)@
--
-- * The 'GT' class has an 'Ord' constraint on keys. This is to provide meaningful ordering in
-- functions like 'assocsAscending' etc. However, most 'GT' instances (particularly any that
-- are derived automatically) will not actually use the 'Ord' class 'compare' method to achieve this.
-- The trie structure and corresponding functions will be designed to deliver this ordering without
-- any comparison or sorting operations on keys. But this will only work if the ordering is the same as
-- that that would be given by the default Haskell derived 'Ord' for the key type in question.
-- If the 'Ord' instance has been hand written (or derived some other way) to give a different
-- ordering then you must either rely on "Data.Trie.General.OrdGT" (which does actually use the 'compare'
-- method) or write a special instance of 'GT' that matches the ordering by hand
-- (yes, that is a lot of work).
--
class Ord k => GT map k | map -> k, k -> map where
-- Upsets Haddock 0.8: class Ord k => GT (map :: * -> *) k | map -> k where
 -- | The empty map.
 empty :: map a

 -- | Create a map with a single association.
 singleton :: k -> a -> map a

 -- | Create a map from a list of associations which /must/ be in ascending order of keys
 -- (with /no/ duplicate keys). If in doubt use one of the safer (but slower) 'fromAssocs' functions.
 fromAssocsAscending :: [(k,a)] -> map a

 -- | Create a map from a list of associations which /must/ be in descending order of keys
 -- (with /no/ duplicate keys). If in doubt use one of the safer (but slower) 'fromAssocs' functions.
 fromAssocsDescending :: [(k,a)] -> map a

 -- | Similar to 'fromAssocsAscending', for use with association lists of known length.
 -- This may be marginally faster for some GT implementations, but you
 -- should only use this if the length information comes \"for free\".
 -- Otherwise just use 'fromAssocsAscending' (implemetations which need the length will calculate
 -- it themselves).
 fromAssocsAscendingL :: Int -> [(k,a)] -> map a

 -- | Similar to 'fromAssocsDescending', for use with association lists of known length.
 -- This may be marginally faster for some GT implementations, but you
 -- should only use this if the length information comes \"for free\".
 -- Otherwise just use 'fromAssocsDescending' (implemetations which need the length will calculate
 -- it themselves).
 fromAssocsDescendingL :: Int -> [(k,a)] -> map a

 -- | Compare two keys and if they are /different/ return a function that will create
 -- a map with two associations (when supplied with the corresponding associated values).
 -- If the keys are the same then this function returns 'Nothing'.
 pair :: k -> k -> Maybe (a -> a -> map a)

 -- | Return 'True' if the map contains no associations.
 isEmpty :: map a -> Bool

 -- | Return 'True' if the map contains exactly one association.
 isSingleton :: map a -> Bool

 -- | Reject empty maps (return Nothing).
 nonEmpty :: map a -> Maybe (map a)

 -- | See the 'Status' type.
 -- This function provides a way to find out if a map is empty, a singleton,
 -- or contains more than one association.
 -- It is useful if empty or singleton maps require special treatment.
 status :: map a -> Status k a

 -- | Add the number of associations in a map to the supplied /unboxed/ Int (with GHC).
 -- Defaults to boxed Int for other Haskells.
 addSize :: map a -> UINT -> UINT

 -- | Return the value associated with the supplied key (if any).
 lookup :: k -> map a -> Maybe a

 -- | Find the value associated with the supplied key (if any) and return the result
 -- of applying the supplied continuation function to that value. Useful for nested lookup.
 lookupCont :: (a -> Maybe b) -> k -> map a -> Maybe b

 -- | Insert a new association in the map if there is currently no value associated with the key.
 -- If there is a value associated with the key then replace it with the result of
 -- applying the supplied function to that value.
 insert :: (a -> a) -> k -> a -> map a -> map a

 -- | Same as 'insert', but applies the supplied function strictly.
 insert' :: (a -> a) -> k -> a -> map a -> map a

 -- | Same as 'insert'', but also forces evaluation of new associated value (third argument)
 -- if the search fails. It /does not/ do this if the search succeeds (because it is discarded).
 insert'' :: (a -> a) -> k -> a -> map a -> map a

 -- | Similar to 'insert', but the association is deleted if the supplied function returns 'Nothing'.
 -- (The supplied function is always applied strictly.)
 insertMaybe :: (a -> Maybe a) -> k -> a -> map a -> map a

 -- | Same as 'insertMaybe', but also forces evaluation of new associated value (third argument)
 -- if the search fails. It /does not/ do this if the search succeeds (because it is discarded).
 insertMaybe' :: (a -> Maybe a) -> k -> a -> map a -> map a

 -- | Delete the association for the supplied key (if any).
 delete :: k -> map a -> map a

 -- | Find the value associated with the supplied key (if any) and apply the supplied function
 -- to that value. Delete the association if the result is 'Nothing'. Replace the old value with
 -- the new value if the result is ('Just' something).
 -- (The supplied function is always applied strictly.)
 deleteMaybe :: (a -> Maybe a) -> k -> map a -> map a

 -- | This is a combined insert\/modify\/delete operation. The argument to the supplied function
 -- is ('Just' a) if there is a value (a) associated with the supplied key, otherwise 'Nothing'.
 -- If the return value is ('Just' a'), a' becomes the new value associated with the supplied key.
 -- If the return value is 'Nothing', the association for the supplied key (if any) is deleted.
 alter :: (Maybe a -> Maybe a) -> k -> map a -> map a

 -- | Evaluate the union of two maps. If the maps contain common keys then combine the
 -- values associated with those keys using the supplied function. The value arguments
 -- to this function are supplied in the same order as the map arguments.
 union :: (a -> a -> a) -> map a -> map a -> map a

 -- | Same as 'union', but the combining function is applied strictly.
 union' :: (a -> a -> a) -> map a -> map a -> map a

 -- | Evaluate the union of two maps, but delete combined associations from the result map
 -- if the combining function returns 'Nothing'.
 -- (The combining function is always applied strictly.)
 unionMaybe :: (a -> a -> Maybe a) -> map a -> map a -> map a

 -- | Evaluate the intersection of two maps, combining common associations using the supplied function.
 intersection :: (a -> b -> c) -> map a -> map b -> map c

 -- | Same as 'intersection', but the combining function is applied strictly.
 intersection' :: (a -> b -> c) -> map a -> map b -> map c

 -- | Evaluate the intersection of two maps, but delete combined associations from the result map
 -- if the combining function returns 'Nothing'.
 -- (The combining function is always applied strictly.)
 intersectionMaybe :: (a -> b -> Maybe c) -> map a -> map b -> map c

 -- | Evaluate the difference between two maps. For any key occuring in the second map,
 -- the corresponding association (if any) is deleted from the first map.
 -- The associated values in the second map are irrelevant.
 difference :: map a -> map b -> map a

 -- | Difference with a combining function. If the combining function returns
 -- @Just a@ then the corresponding association is not deleted from the result map
 -- (it is retained with @a@ as the associated value).
 differenceMaybe :: (a -> b -> Maybe a) -> map a -> map b -> map a

 -- | Returns true if the keys in the first map are a subset of the keys in the second map.
 -- (This includes the case where the key sets are identical). Note that this function does
 -- not examine the associated values (which are irrelevant). See 'isSubmapOf' if you
 -- do want associated values examined.
 isSubsetOf :: map a -> map b -> Bool

 -- | Returns true if the keys in the first map are a subset of the keys in the second map
 -- and the corresponding function always returns true when applied to the values associated
 -- with matching keys.
 isSubmapOf :: (a -> b -> Bool) -> map a -> map b -> Bool

 -- | Apply the supplied function to every associated value in the map.
 map :: (a -> b) -> map a -> map b

 -- | Same as 'map', but the function is applied strictly.
 map' :: (a -> b) -> map a -> map b

 -- | Apply the supplied function to every associated value in the map.
 -- If the result is 'Nothing' then the delete the corresponding association.
 -- (The supplied function is always applied strictly.)
 mapMaybe :: (a -> Maybe b) -> map a -> map b

 -- | Apply the supplied function to every association in the map, and use the result
 -- as the new associated value for the corresponding key.
 mapWithKey :: (k -> a -> b) -> map a -> map b

 -- | Same as 'mapWithKey', but the function is applied strictly.
 mapWithKey' :: (k -> a -> b) -> map a -> map b

 -- | Delete associations for which the supplied predicate returns 'False' when applied to
 -- the associated value.
 filter :: (a -> Bool) -> map a -> map a

 -- | Fold right over the list of elements in ascending order of keys.
 -- See 'foldrElemsAscending'' for a strict version of this function.
 foldrElemsAscending :: (a -> b -> b) -> map a -> b -> b

 -- | Fold right over the list of elements in descending order of keys.
 -- See 'foldrElemsDescending'' for a strict version of this function.
 foldrElemsDescending :: (a -> b -> b) -> map a -> b -> b

 -- | Fold right over the list of keys in ascending order.
 -- See 'foldrKeysAscending'' for a strict version of this function.
 foldrKeysAscending :: (k -> b -> b) -> map a -> b -> b

 -- | Fold right over the list of keys in descending order.
 -- See 'foldrKeysDescending'' for a strict version of this function.
 foldrKeysDescending :: (k -> b -> b) -> map a -> b -> b

 -- | Fold right over the list of associations in ascending order of keys.
 -- See 'foldrAssocsAscending'' for a strict version of this function.
 foldrAssocsAscending :: (k -> a -> b -> b) -> map a -> b -> b

 -- | Fold right over the list of associations in descending order of keys.
 -- See 'foldrAssocsDescending'' for a strict version of this function.
 foldrAssocsDescending :: (k -> a -> b -> b) -> map a -> b -> b

 -- | A strict version of 'foldrElemsAscending' which should be used for
 -- accumulating functions which are strict in their second argument.
 foldrElemsAscending' :: (a -> b -> b) -> map a -> b -> b

 -- | A strict version of 'foldrElemsDescending' which should be used for
 -- accumulating functions which are strict in their second argument.
 foldrElemsDescending' :: (a -> b -> b) -> map a -> b -> b

 -- | A strict version of 'foldrKeysAscending' which should be used for
 -- accumulating functions which are strict in their second argument.
 foldrKeysAscending' :: (k -> b -> b) -> map a -> b -> b

 -- | A strict version of 'foldrKeysDescending' which should be used for
 -- accumulating functions which are strict in their second argument.
 foldrKeysDescending' :: (k -> b -> b) -> map a -> b -> b

 -- | A strict version of 'foldrAssocsAscending' which should be used for
 -- accumulating functions which are strict in their third argument.
 foldrAssocsAscending' :: (k -> a -> b -> b) -> map a -> b -> b

 -- | A strict version of 'foldrAssocsDescending' which should be used for
 -- accumulating functions which are strict in their third argument.
 foldrAssocsDescending' :: (k -> a -> b -> b) -> map a -> b -> b

 -- | Fold over elements in un-specified order using /unboxed/ Int accumulator (with GHC).
 -- Defaults to boxed Int for other Haskells. Typically used for counting functions.
 -- Implementations are free to traverse the Trie in any order.
 -- The folded function is always applied strictly.
 foldElemsUINT :: (a -> UINT -> UINT) -> map a -> UINT -> UINT

 -- | Test whatever underlying data structure is used to implement an
 -- instance of this class is valid. Used for debugging.
 -- 'Nothing' indicates the data structure is valid.
 valid :: map a -> Maybe String

-- | This is the return type for the 'status' method of the 'GT' class
data Status k a = None | One k a | Many
-------------------------------------------------------
----         GT Class Definition Ends              ----
-------------------------------------------------------


-------------------------------------------------------
---- GT Extra functions (common to all instances)  ----
-------------------------------------------------------
-- | Write a new association in the map, overwriting any value currently associated with the key.
write :: GT map k => k -> a -> map a -> map a
write k a mp = insert' (const a) k a mp -- Note use of strict insert'
{-# INLINE write #-}

-- | Monadic lookup.
lookupM :: (GT map k, Monad m) => k -> map a -> m a
lookupM k mp = case lookup k mp of
               Just a  -> return a
               Nothing -> fail "Data.Trie.General.lookupM: Key not found."
{-# SPECIALIZE lookupM :: GT map k => k -> map a -> Maybe a #-}

-- | List the elements in the map in ascending order of keys.
elemsAscending :: GT map k => map a -> [a]
elemsAscending mp = foldrElemsAscending (:) mp []
{-# INLINE elemsAscending #-}

-- | List the elements in the map in descending order of keys.
elemsDescending :: GT map k => map a -> [a]
elemsDescending mp = foldrElemsDescending (:) mp []
{-# INLINE elemsDescending #-}

-- | List all associations in the map in ascending order of keys.
assocsAscending :: GT map k => map a -> [(k,a)]
assocsAscending mp = foldrAssocsAscending (\k a assocs -> (k,a):assocs) mp []
{-# INLINE assocsAscending #-}

-- | List all associations in the map in descending order of keys.
assocsDescending :: GT map k => map a -> [(k,a)]
assocsDescending mp = foldrAssocsDescending (\k a assocs -> (k,a):assocs) mp []
{-# INLINE assocsDescending #-}

-- | List all keys in the map in ascending order.
keysAscending :: GT map k => map a -> [k]
keysAscending mp = foldrKeysAscending (:) mp []
{-# INLINE keysAscending #-}

-- | List all keys in the map in descending order.
keysDescending :: GT map k =>  map a -> [k]
keysDescending mp = foldrKeysDescending (:) mp []
{-# INLINE keysDescending #-}

-- | Count the number of associations in a map.
size :: GT map k => map a -> Int
size mp = ASINT(addSize mp L(0))
{-# INLINE size #-}

-- | Similar to 'isSubsetOf', but also requires that the size of the second map is
-- greater than the first (so does not include the case where the key sets are identical).
isProperSubsetOf :: GT map k =>  map a -> map b -> Bool
isProperSubsetOf mpa mpb = (size mpa < size mpb) && (isSubsetOf mpa mpb)
{-# INLINE isProperSubsetOf #-}

-- | Similar to 'isSubmapOf', but also requires that the size of the second map is
-- greater than the first (so does not include the case where the key sets are identical).
isProperSubmapOfBy :: GT map k =>  (a -> b -> Bool) -> map a -> map b -> Bool
isProperSubmapOfBy f mpa mpb = (size mpa < size mpb) && (isSubmapOf f mpa mpb)
{-# INLINE isProperSubmapOfBy #-}

-- | Include keys in the associated values. See also 'stripKeys'.
addKeys :: GT map k => map a -> map (k,a)
addKeys mp = mapWithKey' (\k a -> (k,a)) mp -- Note use of strict mapWithKey'
{-# INLINE addKeys #-}

-- | Remove keys from the associated values.
stripKeys :: GT map k => map (k,a) -> map a
stripKeys mp = map' (\(_,a) -> a) mp -- Note use of strict map'
{-# INLINE stripKeys #-}

-- | Insert the associations from an unsorted list of @(key,value)@ association
-- pairs into a map. If a key is already in present the map the new and old
-- associated values are (lazily) combined using the supplied function (@f@).
-- The application order is @(f new_value old_value)@.
-- See 'insertAssocs'' for a stricter version.
insertAssocs :: GT map k => (a -> a -> a) -> [(k,a)] -> map a -> map a
insertAssocs f assocs mp0 = L.foldl' ins mp0 assocs
 where ins mp (k,a) = insert (f a) k a mp

-- | Applies 'insertAssocs' to an empty map.
fromAssocs :: GT map k => (a -> a -> a) -> [(k,a)] -> map a
fromAssocs f assocs = insertAssocs f assocs empty
{-# INLINE fromAssocs #-}

-- | Same as 'insertAssocs', but the combining function is applied strictly.
insertAssocs' :: GT map k => (a -> a -> a) -> [(k,a)] -> map a -> map a
insertAssocs' f assocs mp0 = L.foldl' ins mp0 assocs
 where ins mp (k,a) = insert' (f a) k a mp

-- | Applies 'insertAssocs'' to an empty map.
fromAssocs' :: GT map k => (a -> a -> a) -> [(k,a)] -> map a
fromAssocs' f assocs = insertAssocs' f assocs empty
{-# INLINE fromAssocs' #-}

-- | Insert the associations from an unsorted list of @(key,value)@ association
-- pairs into a map. If a key is already in present the map the new and old
-- associated values are strictly combined using the supplied function (@f@).
-- If this function returns 'Nothing' then the corresponding association is deleted.
-- The application order is @(f new_value old_value)@.
-- See 'insertAssocsMaybe'' for a stricter version.
insertAssocsMaybe :: GT map k => (a -> a -> Maybe a) -> [(k,a)] -> map a -> map a
insertAssocsMaybe f assocs mp0 = L.foldl' ins mp0 assocs
 where ins mp (k,a) = insertMaybe (f a) k a mp

-- | Same as 'insertAssocsMaybe', but also forces evaluation of newly inserted associated
-- values, but only if they are /not/ combined (I.E. if the map does not already contain
-- a value associated with the corresponding key).
insertAssocsMaybe' :: GT map k => (a -> a -> Maybe a) -> [(k,a)] -> map a -> map a
insertAssocsMaybe' f assocs mp0 = L.foldl' ins mp0 assocs
 where ins mp (k,a) = insertMaybe' (f a) k a mp

-- | Insert the associations from a list of @(key,value)@ association pairs which
-- is /sorted in ascending order of keys/ into a map.
-- If a key is already in present the map the new and old
-- associated values are (lazily) combined using the supplied function (@f@).
-- The application order is @(f new_value old_value)@.
-- See 'insertAssocsAscending'' for a stricter version.
insertAssocsAscending :: GT map k => (a -> a -> a) -> [(k,a)] -> map a -> map a
insertAssocsAscending f assocs mp0 = union f (fromAssocsAscending assocs) mp0
{-# INLINE insertAssocsAscending #-}

-- | Similar to 'insertAssocsAscending', for use with association lists of known length.
-- This may be marginally faster for some GT implementations, but you
-- should only use this if the length information comes \"for free\".
-- Otherwise just use 'insertAssocsAscending' (implemetations which need the length will calculate
-- it themselves).
-- See 'insertAssocsAscendingL'' for a stricter version.
insertAssocsAscendingL :: GT map k => (a -> a -> a) -> Int -> [(k,a)] -> map a -> map a
insertAssocsAscendingL f n assocs mp0 = union f (fromAssocsAscendingL n assocs) mp0
{-# INLINE insertAssocsAscendingL #-}

-- | Same as 'insertAssocsAscending', but the combining function is applied strictly.
insertAssocsAscending' :: GT map k => (a -> a -> a) -> [(k,a)] -> map a -> map a
insertAssocsAscending' f assocs mp0 = union' f (fromAssocsAscending assocs) mp0
{-# INLINE insertAssocsAscending' #-}

-- | Same as 'insertAssocsAscendingL', but the combining function is applied strictly.
insertAssocsAscendingL' :: GT map k => (a -> a -> a) -> Int -> [(k,a)] -> map a -> map a
insertAssocsAscendingL' f n assocs mp0 = union' f (fromAssocsAscendingL n assocs) mp0
{-# INLINE insertAssocsAscendingL' #-}

-- | Insert the associations from a list of @(key,value)@ association pairs which
-- is /sorted in ascending order of keys/ into a map.
-- If a key is already in present the map the new and old
-- associated values are strictly combined using the supplied function (@f@).
-- If this function returns 'Nothing' then the corresponding association is deleted.
-- The application order is @(f new_value old_value)@.
insertAssocsAscendingMaybe :: GT map k => (a -> a -> Maybe a) -> [(k,a)] -> map a -> map a
insertAssocsAscendingMaybe f assocs mp0 = unionMaybe f (fromAssocsAscending assocs) mp0
{-# INLINE insertAssocsAscendingMaybe #-}

-- | Similar to 'insertAssocsAscendingMaybe', for use with association lists of known length.
-- This may be marginally faster for some GT implementations, but you
-- should only use this if the length information comes \"for free\".
-- Otherwise just use 'insertAssocsAscendingMaybe' (implemetations which need the length will calculate
-- it themselves).
insertAssocsAscendingMaybeL :: GT map k => (a -> a -> Maybe a) -> Int -> [(k,a)] -> map a -> map a
insertAssocsAscendingMaybeL f n assocs mp0 = unionMaybe f (fromAssocsAscendingL n assocs) mp0
{-# INLINE insertAssocsAscendingMaybeL #-}

-- | Insert the associations from a list of @(key,value)@ association pairs which
-- is /sorted in descending order of keys/ into a map.
-- If a key is already in present the map the new and old
-- associated values are (lazily) combined using the supplied function (@f@).
-- The application order is @(f new_value old_value)@.
-- See 'insertAssocsDescending'' for a stricter version.
insertAssocsDescending :: GT map k => (a -> a -> a) -> [(k,a)] -> map a -> map a
insertAssocsDescending f assocs mp0 = union f (fromAssocsDescending assocs) mp0
{-# INLINE insertAssocsDescending #-}

-- | Similar to 'insertAssocsDescending', for use with association lists of known length.
-- This may be marginally faster for some GT implementations, but you
-- should only use this if the length information comes \"for free\".
-- Otherwise just use 'insertAssocsDescending' (implemetations which need the length will calculate
-- it themselves).
-- See 'insertAssocsDescendingL'' for a stricter version.
insertAssocsDescendingL :: GT map k => (a -> a -> a) -> Int -> [(k,a)] -> map a -> map a
insertAssocsDescendingL f n assocs mp0 = union f (fromAssocsDescendingL n assocs) mp0
{-# INLINE insertAssocsDescendingL #-}

-- | Same as 'insertAssocsDescending', but the combining function is applied strictly.
insertAssocsDescending' :: GT map k => (a -> a -> a) -> [(k,a)] -> map a -> map a
insertAssocsDescending' f assocs mp0 = union' f (fromAssocsDescending assocs) mp0
{-# INLINE insertAssocsDescending' #-}

-- | Same as 'insertAssocsDescendingL', but the combining function is applied strictly.
insertAssocsDescendingL' :: GT map k => (a -> a -> a) -> Int -> [(k,a)] -> map a -> map a
insertAssocsDescendingL' f n assocs mp0 = union' f (fromAssocsDescendingL n assocs) mp0
{-# INLINE insertAssocsDescendingL' #-}

-- | Insert the associations from a list of @(key,value)@ association pairs which
-- is /sorted in descending order of keys/ into a map.
-- If a key is already in present the map the new and old
-- associated values are strictly combined using the supplied function (@f@).
-- If this function returns 'Nothing' then the corresponding association is deleted.
-- The application order is @(f new_value old_value)@.
insertAssocsDescendingMaybe :: GT map k => (a -> a -> Maybe a) -> [(k,a)] -> map a -> map a
insertAssocsDescendingMaybe f assocs mp0 = unionMaybe f (fromAssocsDescending assocs) mp0
{-# INLINE insertAssocsDescendingMaybe #-}

-- | Similar to 'insertAssocsDescendingMaybe', for use with association lists of known length.
-- This may be marginally faster for some GT implementations, but you
-- should only use this if the length information comes \"for free\".
-- Otherwise just use 'insertAssocsDescendingMaybe' (implemetations which need the length will calculate
-- it themselves).
insertAssocsDescendingMaybeL :: GT map k => (a -> a -> Maybe a) -> Int -> [(k,a)] -> map a -> map a
insertAssocsDescendingMaybeL f n assocs mp0 = unionMaybe f (fromAssocsDescendingL n assocs) mp0
{-# INLINE insertAssocsDescendingMaybeL #-}

-- | Applies the supplied function to every value in a map to create a new key (type @k1@). The
-- result is a map of new keys to a corresponding /non-empty/ map of old keys (type k0) to values.
partition :: (GT map0 k0, GT map1 k1) => (a -> k1) -> map0 a -> map1 (map0 a)
partition p map0 = map fromAssocsAscending (partitionAscendingList p map0) -- We use the lazy map here!!
{-# INLINE partition #-}

-- | Similar to 'partition', but associations with values yielding 'Nothing' are discarded.
partitionMaybe :: (GT map0 k0, GT map1 k1) => (a -> Maybe k1) -> map0 a -> map1 (map0 a)
partitionMaybe p map0 = map fromAssocsAscending (partitionAscendingListMaybe p map0) -- We use the lazy map here!!
{-# INLINE partitionMaybe #-}

-- | Applies the supplied function to every value in a map to create a new key (type @k1@). The
-- result is a map of new keys to a corresponding /non-empty/ list of old key\/value association pairs.
-- Each list is in ascending order of old keys (type k0).
partitionAscendingList :: (GT map0 k0, GT map1 k1) => (a -> k1) -> map0 a -> map1 [(k0,a)]
partitionAscendingList p map0 = foldrAssocsDescending' ins map0 empty  -- We use Descending!! (strict)
 where ins k0 a map1 = insert' ((k0,a):) (p a) [(k0,a)] map1           -- Note use of insert'

-- | Applies the supplied function to every value in a map to create a new key (type @k1@). The
-- result is a map of new keys to a corresponding /non-empty/ list of old key\/value association pairs.
-- Each list is in descending order of old keys (type k0).
partitionDescendingList :: (GT map0 k0, GT map1 k1) => (a -> k1) -> map0 a -> map1 [(k0,a)]
partitionDescendingList p map0 = foldrAssocsAscending' ins map0 empty  -- We use Ascending!! (strict)
 where ins k0 a map1 = insert' ((k0,a):) (p a) [(k0,a)] map1           -- Note use of insert'

-- | Similar to 'partitionAscendingList', but associations with values yielding 'Nothing' are discarded.
partitionAscendingListMaybe :: (GT map0 k0, GT map1 k1) => (a -> Maybe k1) -> map0 a -> map1 [(k0,a)]
partitionAscendingListMaybe p map0 = foldrAssocsDescending' ins map0 empty  -- We use Descending!! (strict)
 where ins k0 a map1 =  case p a of
                        Nothing -> map1
                        Just k1 -> insert' ((k0,a):) k1 [(k0,a)] map1       -- Note use of insert'

-- | Similar to 'partitionDescendingList', but associations with values yielding 'Nothing' are discarded.
partitionDescendingListMaybe :: (GT map0 k0, GT map1 k1) => (a -> Maybe k1) -> map0 a -> map1 [(k0,a)]
partitionDescendingListMaybe p map0 = foldrAssocsAscending' ins map0 empty  -- We use Ascending!! (strict)
 where ins k0 a map1 = case p a of
                       Nothing -> map1
                       Just k1 -> insert' ((k0,a):) k1 [(k0,a)] map1        -- Note use of insert'

-- | Use a Trie to sort a list of keys into ascending order (eliminating duplicates).
sortAscending :: GT map k => [k] -> [k]
sortAscending ks = keysAscending (L.foldl' ins empty ks)
 where ins mp k = insert id k () mp

-- | Use a Trie to sort a list of keys into descending order (eliminating duplicates).
sortDescending :: GT map k => [k] -> [k]
sortDescending ks = keysDescending (L.foldl' ins empty ks)
 where ins mp k = insert id k () mp