{-# OPTIONS_GHC -fglasgow-exts -fno-warn-orphans -fno-warn-unused-imports -fallow-undecidable-instances #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Trie.General.MaybeGT
-- Copyright   :  (c) Adrian Hey 2007
-- License     :  BSD3
--
-- Maintainer  :  http://homepages.nildram.co.uk/~ahey/em.png
-- Stability   :  provisional
-- Portability :  non-portable
--
-- A 'GT' instance for keys of type @GT map k => 'Maybe' k@
--
-- If a key type is an instance of GT then so is a 'Maybe' of this key.
--
-- N.B. For 'Maybe's ascending order is @['Nothing','Just' _]@
-----------------------------------------------------------------------------
module Data.Trie.General.MaybeGT
(-- * MaybeGT type
 MaybeGT

 -- * Standard GT API for MaybeGTs
 -- | These functions all have the same names as the corresponding GT class methods,
 -- but with the \"MaybeGT\" suffix.
,emptyMaybeGT
,singletonMaybeGT
,fromAssocsAscendingMaybeGT
,fromAssocsDescendingMaybeGT
,fromAssocsAscendingLMaybeGT
,fromAssocsDescendingLMaybeGT
,pairMaybeGT
,isEmptyMaybeGT
,isSingletonMaybeGT
,nonEmptyMaybeGT
,statusMaybeGT
,addSizeMaybeGT
,lookupMaybeGT
,lookupContMaybeGT
,insertMaybeGT
,insertMaybeGT'
,insertMaybeGT''
,insertMaybeMaybeGT
,insertMaybeMaybeGT'
,deleteMaybeGT
,deleteMaybeMaybeGT
,alterMaybeGT
,unionMaybeGT
,unionMaybeGT'
,unionMaybeMaybeGT
,intersectionMaybeGT
,intersectionMaybeGT'
,intersectionMaybeMaybeGT
,differenceMaybeGT
,differenceMaybeMaybeGT
,isSubsetOfMaybeGT
,isSubmapOfMaybeGT
,mapMaybeGT
,mapMaybeGT'
,mapMaybeMaybeGT
,mapWithKeyMaybeGT
,mapWithKeyMaybeGT'
,filterMaybeGT
,foldrElemsAscendingMaybeGT
,foldrElemsDescendingMaybeGT
,foldrKeysAscendingMaybeGT
,foldrKeysDescendingMaybeGT
,foldrAssocsAscendingMaybeGT
,foldrAssocsDescendingMaybeGT
,foldrElemsAscendingMaybeGT'
,foldrElemsDescendingMaybeGT'
,foldrKeysAscendingMaybeGT'
,foldrKeysDescendingMaybeGT'
,foldrAssocsAscendingMaybeGT'
,foldrAssocsDescendingMaybeGT'
,foldElemsUINTMaybeGT
,validMaybeGT
) where

import Prelude hiding (foldr,map,filter,lookup)
import Data.Trie.General.Types

import qualified Data.Monoid as M (Monoid(..))
import qualified Data.Foldable as F (Foldable(..))
import Data.Typeable
-- -fno-warn-unused-imports used because ghc currently gives spurious warning with this import
-- See Tickets 1074 and 1148
import qualified Data.List as L (foldr)

#ifdef __GLASGOW_HASKELL__
import GHC.Base hiding (map)
import qualified Text.Read as R (Read(..),Lexeme(..),parens,prec,lexP,readListPrecDefault)
#include "ghcdefs.h"
#else
#include "h98defs.h"
#endif

-- | The 'GT' type for keys of form @'GT' map k => 'Maybe' k@.
data MaybeGT map k a = MaybeGT !(Maybe a) !(map a)

instance GT map k => GT (MaybeGT map k) (Maybe k) where
 empty                 = emptyMaybeGT
 singleton             = singletonMaybeGT
 fromAssocsAscending   = fromAssocsAscendingMaybeGT
 fromAssocsDescending  = fromAssocsDescendingMaybeGT
 fromAssocsAscendingL  = fromAssocsAscendingLMaybeGT
 fromAssocsDescendingL = fromAssocsDescendingLMaybeGT
 pair                  = pairMaybeGT
 isEmpty               = isEmptyMaybeGT
 isSingleton           = isSingletonMaybeGT
 nonEmpty              = nonEmptyMaybeGT
 status                = statusMaybeGT
 addSize               = addSizeMaybeGT
 lookup                = lookupMaybeGT
 lookupCont            = lookupContMaybeGT
 insert                = insertMaybeGT
 insert'               = insertMaybeGT'
 insert''              = insertMaybeGT''
 insertMaybe           = insertMaybeMaybeGT
 insertMaybe'          = insertMaybeMaybeGT'
 delete                = deleteMaybeGT
 deleteMaybe           = deleteMaybeMaybeGT
 alter                 = alterMaybeGT
 union                 = unionMaybeGT
 union'                = unionMaybeGT'
 unionMaybe            = unionMaybeMaybeGT
 intersection          = intersectionMaybeGT
 intersection'         = intersectionMaybeGT'
 intersectionMaybe     = intersectionMaybeMaybeGT
 difference            = differenceMaybeGT
 differenceMaybe       = differenceMaybeMaybeGT
 isSubsetOf            = isSubsetOfMaybeGT
 isSubmapOf            = isSubmapOfMaybeGT
 map                   = mapMaybeGT
 map'                  = mapMaybeGT'
 mapMaybe              = mapMaybeMaybeGT
 mapWithKey            = mapWithKeyMaybeGT
 mapWithKey'           = mapWithKeyMaybeGT'
 filter                = filterMaybeGT
 foldrElemsAscending   = foldrElemsAscendingMaybeGT
 foldrElemsDescending  = foldrElemsDescendingMaybeGT
 foldrKeysAscending    = foldrKeysAscendingMaybeGT
 foldrKeysDescending   = foldrKeysDescendingMaybeGT
 foldrAssocsAscending  = foldrAssocsAscendingMaybeGT
 foldrAssocsDescending = foldrAssocsDescendingMaybeGT
 foldrElemsAscending'  = foldrElemsAscendingMaybeGT'
 foldrElemsDescending' = foldrElemsDescendingMaybeGT'
 foldrKeysAscending'   = foldrKeysAscendingMaybeGT'
 foldrKeysDescending'  = foldrKeysDescendingMaybeGT'
 foldrAssocsAscending' = foldrAssocsAscendingMaybeGT'
 foldrAssocsDescending'= foldrAssocsDescendingMaybeGT'
 foldElemsUINT         = foldElemsUINTMaybeGT
 valid                 = validMaybeGT

-- | See 'GT' class method 'empty'.
emptyMaybeGT :: GT map k => MaybeGT map k a
emptyMaybeGT = MaybeGT Nothing empty

-- | See 'GT' class method 'singleton'.
singletonMaybeGT :: GT map k => Maybe k -> a -> MaybeGT map k a
singletonMaybeGT Nothing  a = MaybeGT (Just a) empty
singletonMaybeGT (Just k) a = MaybeGT Nothing  (singleton k a)

-- | See 'GT' class method 'fromAssocsAscending'.
fromAssocsAscendingMaybeGT :: GT map k => [(Maybe k,a)] -> MaybeGT map k a
fromAssocsAscendingMaybeGT []                = emptyMaybeGT
fromAssocsAscendingMaybeGT ((Nothing,a):jas) = stripJAC (Just a) L(0) []      jas
fromAssocsAscendingMaybeGT ((Just k ,a):jas) = stripJAC Nothing  L(1) [(k,a)] jas
-- Helper for fromAssocsAscendingMaybeGT
stripJAC :: GT map k => Maybe a -> UINT -> [(k,a)] -> [(Maybe k, a)] -> MaybeGT map k a
stripJAC mba n kasR []                = MaybeGT mba (fromAssocsDescendingL ASINT(n) kasR)
stripJAC mba n kasR ((Just k, a):jas) = stripJAC mba INCINT1(n) ((k,a):kasR) jas
stripJAC _   _ _    _                 = error "Data.Trie.General.MaybeGT: Bad ascending association List."

-- | See 'GT' class method 'fromAssocsDescending'.
fromAssocsDescendingMaybeGT :: GT map k => [(Maybe k,a)] -> MaybeGT map k a
fromAssocsDescendingMaybeGT []         = emptyMaybeGT
fromAssocsDescendingMaybeGT (ja0:jas0) = sj L(0) [] ja0 jas0 where
 sj n kasR (Nothing, a) _        = MaybeGT (Just a) (fromAssocsAscendingL ASINT(n) kasR) -- Must be the last!
 sj n kasR (Just k , a) []       = MaybeGT Nothing  (fromAssocsAscendingL ASINT(INCINT1(n)) ((k,a):kasR))
 sj n kasR (Just k , a) (ja:jas) = sj INCINT1(n) ((k,a):kasR) ja jas

-- | See 'GT' class method 'fromAssocsAscendingL'.
fromAssocsAscendingLMaybeGT :: GT map k => Int -> [(Maybe k,a)] -> MaybeGT map k a
fromAssocsAscendingLMaybeGT _ jas = fromAssocsAscendingMaybeGT jas
{-# INLINE fromAssocsAscendingLMaybeGT #-}

-- | See 'GT' class method 'fromAssocsDescendingL'.
fromAssocsDescendingLMaybeGT :: GT map k => Int -> [(Maybe k,a)] -> MaybeGT map k a
fromAssocsDescendingLMaybeGT _ jas = fromAssocsDescendingMaybeGT jas
{-# INLINE fromAssocsDescendingLMaybeGT #-}

-- | See 'GT' class method 'pair'.
pairMaybeGT :: GT map k => Maybe k -> Maybe k -> Maybe (a -> a -> MaybeGT map k a)
pairMaybeGT Nothing   Nothing   = Nothing
pairMaybeGT (Just k0) Nothing   = Just (\a0 a1 -> MaybeGT (Just a1) (singleton k0 a0))
pairMaybeGT Nothing   (Just k1) = Just (\a0 a1 -> MaybeGT (Just a0) (singleton k1 a1))
pairMaybeGT (Just k0) (Just k1) = case pair k0 k1 of
                                  Nothing -> Nothing
                                  Just f  -> Just (\a0 a1 -> MaybeGT Nothing (f a0 a1))

-- | See 'GT' class method 'isEmpty'.
isEmptyMaybeGT :: GT map k => MaybeGT map k a -> Bool
isEmptyMaybeGT (MaybeGT (Just _) _ ) = False
isEmptyMaybeGT (MaybeGT Nothing  mp) = isEmpty mp

-- | See 'GT' class method 'isSingleton'.
isSingletonMaybeGT :: GT map k => MaybeGT map k a -> Bool
isSingletonMaybeGT (MaybeGT (Just _) mp) = isEmpty mp
isSingletonMaybeGT (MaybeGT Nothing  mp) = isSingleton mp

-- | See 'GT' class method 'nonEmpty'.
nonEmptyMaybeGT :: GT map k => MaybeGT map k a -> Maybe (MaybeGT map k a)
nonEmptyMaybeGT mgt@(MaybeGT (Just _) _ ) = Just mgt
nonEmptyMaybeGT mgt@(MaybeGT Nothing  mp) = if isEmpty mp then Nothing else Just mgt

-- | See 'GT' class method 'status'.
statusMaybeGT :: GT map k => MaybeGT map k a -> Status (Maybe k) a
statusMaybeGT (MaybeGT Nothing  mp) = case status mp of
                                      None    -> None
                                      One k a -> One (Just k) a
                                      Many    -> Many
statusMaybeGT (MaybeGT (Just a) mp) = if isEmpty mp then One Nothing a else Many

-- | See 'GT' class method 'addSize'.
addSizeMaybeGT :: GT map k => MaybeGT map k a -> UINT -> UINT
addSizeMaybeGT (MaybeGT Nothing  mp) n = addSize mp n
addSizeMaybeGT (MaybeGT (Just _) mp) n = addSize mp INCINT1(n)

-- | See 'GT' class method 'lookup'.
lookupMaybeGT :: GT map k => Maybe k -> MaybeGT map k a -> Maybe a
lookupMaybeGT Nothing  (MaybeGT mba _ ) = mba
lookupMaybeGT (Just k) (MaybeGT _   mp) = lookup k mp

-- | See 'GT' class method 'lookupCont'.
lookupContMaybeGT :: GT map k => (a -> Maybe b) -> Maybe k -> MaybeGT map k a -> Maybe b
lookupContMaybeGT _ Nothing  (MaybeGT Nothing  _ ) = Nothing
lookupContMaybeGT f Nothing  (MaybeGT (Just a) _ ) = f a
lookupContMaybeGT f (Just k) (MaybeGT _        mp) = lookupCont f k mp

-- | See 'GT' class method 'insert'.
insertMaybeGT :: GT map k => (a -> a) -> Maybe k -> a -> MaybeGT map k a -> MaybeGT map k a
insertMaybeGT _ Nothing  a (MaybeGT Nothing  mp) = MaybeGT (Just a    ) mp
insertMaybeGT f Nothing  _ (MaybeGT (Just a) mp) = MaybeGT (Just (f a)) mp
insertMaybeGT f (Just k) a (MaybeGT mba      mp) = MaybeGT mba          (insert f k a mp)

-- | See 'GT' class method 'insert''.
insertMaybeGT' :: GT map k => (a -> a) -> Maybe k -> a -> MaybeGT map k a -> MaybeGT map k a
insertMaybeGT' _ Nothing  a (MaybeGT Nothing  mp) =                          MaybeGT (Just a ) mp
insertMaybeGT' f Nothing  _ (MaybeGT (Just a) mp) = let a' = f a in a' `seq` MaybeGT (Just a') mp
insertMaybeGT' f (Just k) a (MaybeGT mba      mp) =                          MaybeGT mba (insert' f k a mp)

-- | See 'GT' class method 'insert'''.
insertMaybeGT'' :: GT map k => (a -> a) -> Maybe k -> a -> MaybeGT map k a -> MaybeGT map k a
insertMaybeGT'' _ Nothing  a (MaybeGT Nothing  mp) =                 a  `seq` MaybeGT (Just a ) mp
insertMaybeGT'' f Nothing  _ (MaybeGT (Just a) mp) = let a' = f a in a' `seq` MaybeGT (Just a') mp
insertMaybeGT'' f (Just k) a (MaybeGT mba      mp) =                          MaybeGT mba (insert'' f k a mp)

-- | See 'GT' class method 'insertMaybe'.
insertMaybeMaybeGT :: GT map k => (a -> Maybe a) -> Maybe k -> a -> MaybeGT map k a -> MaybeGT map k a
insertMaybeMaybeGT _ Nothing  a (MaybeGT Nothing  mp) = MaybeGT (Just a) mp
insertMaybeMaybeGT f Nothing  _ (MaybeGT (Just a) mp) = MaybeGT (f a)    mp
insertMaybeMaybeGT f (Just k) a (MaybeGT mba      mp) = MaybeGT mba      (insertMaybe f k a mp)

-- | See 'GT' class method 'insertMaybe''.
insertMaybeMaybeGT' :: GT map k => (a -> Maybe a) -> Maybe k -> a -> MaybeGT map k a -> MaybeGT map k a
insertMaybeMaybeGT' _ Nothing  a (MaybeGT Nothing  mp) = a  `seq` MaybeGT (Just a) mp
insertMaybeMaybeGT' f Nothing  _ (MaybeGT (Just a) mp) =          MaybeGT (f a)    mp
insertMaybeMaybeGT' f (Just k) a (MaybeGT mba      mp) =          MaybeGT mba      (insertMaybe' f k a mp)

-- | See 'GT' class method 'delete'.
deleteMaybeGT :: GT map k => Maybe k -> MaybeGT map k a -> MaybeGT map k a
deleteMaybeGT Nothing  (MaybeGT _   mp) = MaybeGT Nothing mp
deleteMaybeGT (Just k) (MaybeGT mba mp) = MaybeGT mba (delete k mp)

-- | See 'GT' class method 'deleteMaybe'.
deleteMaybeMaybeGT :: GT map k => (a -> Maybe a) -> Maybe k -> MaybeGT map k a -> MaybeGT map k a
deleteMaybeMaybeGT _ Nothing  mgt@(MaybeGT Nothing  _ ) = mgt
deleteMaybeMaybeGT f Nothing      (MaybeGT (Just a) mp) = MaybeGT (f a) mp
deleteMaybeMaybeGT f (Just k)     (MaybeGT mba      mp) = MaybeGT mba   (deleteMaybe f k mp)

-- | See 'GT' class method 'alter'.
alterMaybeGT :: GT map k => (Maybe a -> Maybe a) -> Maybe k -> MaybeGT map k a -> MaybeGT map k a
alterMaybeGT f Nothing  (MaybeGT mba mp) = MaybeGT (f mba) mp
alterMaybeGT f (Just k) (MaybeGT mba mp) = MaybeGT mba     (alter f k mp)

-- | See 'GT' class method 'union'.
unionMaybeGT :: GT map k => (a -> a -> a) -> MaybeGT map k a -> MaybeGT map k a -> MaybeGT map k a
unionMaybeGT f (MaybeGT mba0 mp0) (MaybeGT mba1 mp1) = MaybeGT (u mba0 mba1) (union f mp0 mp1)
 where u Nothing   mb1       = mb1
       u mb0       Nothing   = mb0
       u (Just a0) (Just a1) = Just (f a0 a1)

-- | See 'GT' class method 'union''.
unionMaybeGT' :: GT map k => (a -> a -> a) -> MaybeGT map k a -> MaybeGT map k a -> MaybeGT map k a
unionMaybeGT' f (MaybeGT mba0 mp0) (MaybeGT mba1 mp1) = MaybeGT (u mba0 mba1) (union' f mp0 mp1)
 where u Nothing   mb1       = mb1
       u mb0       Nothing   = mb0
       u (Just a0) (Just a1) = let a = f a0 a1 in a `seq` Just a

-- | See 'GT' class method 'unionMaybe'.
unionMaybeMaybeGT :: GT map k => (a -> a -> Maybe a) -> MaybeGT map k a -> MaybeGT map k a -> MaybeGT map k a
unionMaybeMaybeGT f (MaybeGT mba0 mp0) (MaybeGT mba1 mp1) = MaybeGT (u mba0 mba1) (unionMaybe f mp0 mp1)
 where u Nothing   mb1       = mb1
       u mb0       Nothing   = mb0
       u (Just a0) (Just a1) = f a0 a1

-- | See 'GT' class method 'intersection'.
intersectionMaybeGT :: GT map k => (a -> b -> c) -> MaybeGT map k a -> MaybeGT map k b -> MaybeGT map k c
intersectionMaybeGT f (MaybeGT mba0 mp0) (MaybeGT mba1 mp1) = MaybeGT (i mba0 mba1) (intersection f mp0 mp1)
 where i Nothing  _        = Nothing
       i _        Nothing  = Nothing
       i (Just a) (Just b) = Just (f a b)

-- | See 'GT' class method 'intersection''.
intersectionMaybeGT' :: GT map k => (a -> b -> c) -> MaybeGT map k a -> MaybeGT map k b -> MaybeGT map k c
intersectionMaybeGT' f (MaybeGT mba0 mp0) (MaybeGT mba1 mp1) = MaybeGT (i mba0 mba1) (intersection' f mp0 mp1)
 where i Nothing  _        = Nothing
       i _        Nothing  = Nothing
       i (Just a) (Just b) = let c = f a b in c `seq` Just c

-- | See 'GT' class method 'intersectionMaybe'.
intersectionMaybeMaybeGT :: GT map k => (a -> b -> Maybe c) -> MaybeGT map k a -> MaybeGT map k b -> MaybeGT map k c
intersectionMaybeMaybeGT f (MaybeGT mba0 mp0) (MaybeGT mba1 mp1) = MaybeGT (i mba0 mba1) (intersectionMaybe f mp0 mp1)
 where i Nothing  _        = Nothing
       i _        Nothing  = Nothing
       i (Just a) (Just b) = f a b

-- | See 'GT' class method 'difference'.
differenceMaybeGT :: GT map k => MaybeGT map k a -> MaybeGT map k b -> MaybeGT map k a
differenceMaybeGT (MaybeGT mba0 mp0) (MaybeGT mba1 mp1) = MaybeGT (d mba0 mba1) (difference mp0 mp1)
 where d mba Nothing  = mba
       d _   (Just _) = Nothing

-- | See 'GT' class method 'differenceMaybe'.
differenceMaybeMaybeGT :: GT map k => (a -> b -> Maybe a) -> MaybeGT map k a -> MaybeGT map k b -> MaybeGT map k a
differenceMaybeMaybeGT f (MaybeGT mba0 mp0) (MaybeGT mba1 mp1) = MaybeGT (d mba0 mba1) (differenceMaybe f mp0 mp1)
 where d mba      Nothing  = mba
       d Nothing  (Just _) = Nothing
       d (Just a) (Just b) = f a b

-- | See 'GT' class method 'isSubsetOf'.
isSubsetOfMaybeGT :: GT map k => MaybeGT map k a -> MaybeGT map k b -> Bool
isSubsetOfMaybeGT (MaybeGT Nothing  mp0) (MaybeGT _         mp1) = isSubsetOf mp0 mp1
isSubsetOfMaybeGT (MaybeGT (Just _) _  ) (MaybeGT Nothing   _  ) = False
isSubsetOfMaybeGT (MaybeGT (Just _) mp0) (MaybeGT (Just _)  mp1) = isSubsetOf mp0 mp1

-- | See 'GT' class method 'isSubmapOf'.
isSubmapOfMaybeGT :: GT map k => (a -> b -> Bool) -> MaybeGT map k a -> MaybeGT map k b -> Bool
isSubmapOfMaybeGT f (MaybeGT Nothing  mp0) (MaybeGT _         mp1) = isSubmapOf f mp0 mp1
isSubmapOfMaybeGT _ (MaybeGT (Just _) _  ) (MaybeGT Nothing   _  ) = False
isSubmapOfMaybeGT f (MaybeGT (Just a) mp0) (MaybeGT (Just b)  mp1) = if f a b then isSubmapOf f mp0 mp1
                                                                              else False

-- | See 'GT' class method 'map'.
mapMaybeGT :: GT map k => (a -> b) -> MaybeGT map k a -> MaybeGT map k b
mapMaybeGT f (MaybeGT Nothing  mp) = MaybeGT Nothing      (map f mp)
mapMaybeGT f (MaybeGT (Just a) mp) = MaybeGT (Just (f a)) (map f mp)

-- | See 'GT' class method 'map''.
mapMaybeGT' :: GT map k => (a -> b) -> MaybeGT map k a -> MaybeGT map k b
mapMaybeGT' f (MaybeGT Nothing  mp) =                          MaybeGT Nothing   (map' f mp)
mapMaybeGT' f (MaybeGT (Just a) mp) = let a' = f a in a' `seq` MaybeGT (Just a') (map' f mp)

-- | See 'GT' class method 'mapMaybe'.
mapMaybeMaybeGT :: GT map k => (a -> Maybe b) -> MaybeGT map k a -> MaybeGT map k b
mapMaybeMaybeGT f (MaybeGT Nothing  mp) = MaybeGT Nothing (mapMaybe f mp)
mapMaybeMaybeGT f (MaybeGT (Just a) mp) = MaybeGT (f a)   (mapMaybe f mp)

-- | See 'GT' class method 'mapWithKey'.
mapWithKeyMaybeGT :: GT map k => (Maybe k -> a -> b) -> MaybeGT map k a -> MaybeGT map k b
mapWithKeyMaybeGT f (MaybeGT Nothing  mp) = MaybeGT Nothing              (mapWithKey (\k a' -> f (Just k) a') mp)
mapWithKeyMaybeGT f (MaybeGT (Just a) mp) = MaybeGT (Just (f Nothing a)) (mapWithKey (\k a' -> f (Just k) a') mp)

-- | See 'GT' class method 'mapWithKey''.
mapWithKeyMaybeGT' :: GT map k => (Maybe k -> a -> b) -> MaybeGT map k a -> MaybeGT map k b
mapWithKeyMaybeGT' f (MaybeGT Nothing  mp) = MaybeGT Nothing (mapWithKey' (\k a' -> f (Just k) a') mp)
mapWithKeyMaybeGT' f (MaybeGT (Just a) mp) = let a'' = f Nothing a
                                             in  a'' `seq` MaybeGT (Just a'') (mapWithKey' (\k a' -> f (Just k) a') mp)

-- | See 'GT' class method 'filter'.
filterMaybeGT :: GT map k => (a -> Bool) -> MaybeGT map k a -> MaybeGT map k a
filterMaybeGT p (MaybeGT    Nothing  mp) =             MaybeGT Nothing (filter p mp)
filterMaybeGT p (MaybeGT ja@(Just a) mp) = if p a then MaybeGT ja      (filter p mp)
                                                  else MaybeGT Nothing (filter p mp)

-- | See 'GT' class method 'foldrElemsAscending'.
foldrElemsAscendingMaybeGT :: GT map k => (a -> b -> b) -> MaybeGT map k a -> b -> b
foldrElemsAscendingMaybeGT f (MaybeGT Nothing  mp) b =      foldrElemsAscending f mp b
foldrElemsAscendingMaybeGT f (MaybeGT (Just a) mp) b = f a (foldrElemsAscending f mp b)

-- | See 'GT' class method 'foldrElemsDescending'.
foldrElemsDescendingMaybeGT :: GT map k => (a -> b -> b) -> MaybeGT map k a -> b -> b
foldrElemsDescendingMaybeGT f (MaybeGT Nothing  mp) b = foldrElemsDescending f mp b
foldrElemsDescendingMaybeGT f (MaybeGT (Just a) mp) b = foldrElemsDescending f mp (f a b)

-- | See 'GT' class method 'foldrKeysAscending'.
foldrKeysAscendingMaybeGT :: GT map k => (Maybe k -> b -> b) -> MaybeGT map k a -> b -> b
foldrKeysAscendingMaybeGT f (MaybeGT mba mp) b = case mba of
                                                 Nothing ->            foldrKeysAscending f' mp b
                                                 Just _  -> f Nothing (foldrKeysAscending f' mp b)
 where f' k b' = f (Just k) b'

-- | See 'GT' class method 'foldrKeysDescending'.
foldrKeysDescendingMaybeGT :: GT map k => (Maybe k -> b -> b) -> MaybeGT map k a -> b -> b
foldrKeysDescendingMaybeGT f (MaybeGT mba mp) b = case mba of
                                                  Nothing -> foldrKeysDescending f' mp b
                                                  Just _  -> foldrKeysDescending f' mp (f Nothing b)
 where f' k b' = f (Just k) b'

-- | See 'GT' class method 'foldrAssocsAscending'.
foldrAssocsAscendingMaybeGT :: GT map k => (Maybe k -> a -> b -> b) -> MaybeGT map k a -> b -> b
foldrAssocsAscendingMaybeGT f (MaybeGT mba mp) b = case mba of
                                                   Nothing ->              foldrAssocsAscending f' mp b
                                                   Just a  -> f Nothing a (foldrAssocsAscending f' mp b)
 where f' k a b' = f (Just k) a b'

-- | See 'GT' class method 'foldrAssocsDescending'.
foldrAssocsDescendingMaybeGT :: GT map k => (Maybe k -> a -> b -> b) -> MaybeGT map k a -> b -> b
foldrAssocsDescendingMaybeGT f (MaybeGT mba mp) b = case mba of
                                                    Nothing -> foldrAssocsDescending f' mp b
                                                    Just a  -> foldrAssocsDescending f' mp (f Nothing a b)
 where f' k a b' = f (Just k) a b'

-- | See 'GT' class method 'foldrElemsAscending''.
foldrElemsAscendingMaybeGT' :: GT map k => (a -> b -> b) -> MaybeGT map k a -> b -> b
foldrElemsAscendingMaybeGT' f (MaybeGT Nothing  mp) b =        foldrElemsAscending' f mp b
foldrElemsAscendingMaybeGT' f (MaybeGT (Just a) mp) b = f a $! foldrElemsAscending' f mp b

-- | See 'GT' class method 'foldrElemsDescending''.
foldrElemsDescendingMaybeGT' :: GT map k => (a -> b -> b) -> MaybeGT map k a -> b -> b
foldrElemsDescendingMaybeGT' f (MaybeGT Nothing  mp) b = foldrElemsDescending' f mp b
foldrElemsDescendingMaybeGT' f (MaybeGT (Just a) mp) b = foldrElemsDescending' f mp $! f a b

-- | See 'GT' class method 'foldrKeysAscending''.
foldrKeysAscendingMaybeGT' :: GT map k => (Maybe k -> b -> b) -> MaybeGT map k a -> b -> b
foldrKeysAscendingMaybeGT' f (MaybeGT mba mp) b = case mba of
                                                  Nothing ->              foldrKeysAscending' f' mp b
                                                  Just _  -> f Nothing $! foldrKeysAscending' f' mp b
 where f' k b' = f (Just k) b'

-- | See 'GT' class method 'foldrKeysDescending''.
foldrKeysDescendingMaybeGT' :: GT map k => (Maybe k -> b -> b) -> MaybeGT map k a -> b -> b
foldrKeysDescendingMaybeGT' f (MaybeGT mba mp) b = case mba of
                                                   Nothing -> foldrKeysDescending' f' mp b
                                                   Just _  -> foldrKeysDescending' f' mp $! f Nothing b
 where f' k b' = f (Just k) b'

-- | See 'GT' class method 'foldrAssocsAscending''.
foldrAssocsAscendingMaybeGT' :: GT map k => (Maybe k -> a -> b -> b) -> MaybeGT map k a -> b -> b
foldrAssocsAscendingMaybeGT' f (MaybeGT mba mp) b = case mba of
                                                    Nothing ->                foldrAssocsAscending' f' mp b
                                                    Just a  -> f Nothing a $! foldrAssocsAscending' f' mp b
 where f' k a b' = f (Just k) a b'

-- | See 'GT' class method 'foldrAssocsDescending''.
foldrAssocsDescendingMaybeGT' :: GT map k => (Maybe k -> a -> b -> b) -> MaybeGT map k a -> b -> b
foldrAssocsDescendingMaybeGT' f (MaybeGT mba mp) b = case mba of
                                                     Nothing -> foldrAssocsDescending' f' mp b
                                                     Just a  -> foldrAssocsDescending' f' mp $! f Nothing a b
 where f' k a b' = f (Just k) a b'

-- | See 'GT' class method 'foldElemsUINT'.
foldElemsUINTMaybeGT :: GT map k => (a -> UINT -> UINT) -> MaybeGT map k a -> UINT -> UINT
foldElemsUINTMaybeGT f (MaybeGT Nothing  mp) n = foldElemsUINT f mp n
#ifdef __GLASGOW_HASKELL__
foldElemsUINTMaybeGT f (MaybeGT (Just a) mp) n = foldElemsUINT f mp (f a n)
#else
foldElemsUINTMaybeGT f (MaybeGT (Just a) mp) n = foldElemsUINT f mp $! f a n
#endif

-- | See 'GT' class method 'valid'.
validMaybeGT :: GT map k => MaybeGT map k a -> Maybe String
validMaybeGT (MaybeGT _ mp) = valid mp

--------------------------------------------------------------------------
--                         OTHER INSTANCES                              --
--------------------------------------------------------------------------

--------
-- Eq --
--------
instance (Eq k, Eq a, Eq (map a)) => Eq (MaybeGT map k a) where
 MaybeGT mba0 mp0 == MaybeGT mba1 mp1 = (mba0 == mba1) && (mp0 == mp1)

---------
-- Ord --
---------
instance (GT map k, Ord a, Ord (map a)) => Ord (MaybeGT map k a) where
 compare (MaybeGT Nothing   mp0) (MaybeGT Nothing   mp1) = compare mp0 mp1
 compare (MaybeGT Nothing   mp0) (MaybeGT (Just _ ) _  ) = if isEmpty mp0 then LT else GT
 compare (MaybeGT (Just _ ) _  ) (MaybeGT Nothing   mp1) = if isEmpty mp1 then GT else LT
 compare (MaybeGT (Just a0) mp0) (MaybeGT (Just a1) mp1) = case compare a0 a1 of
                                                           LT -> LT
                                                           EQ -> compare mp0 mp1
                                                           GT -> GT

----------
-- Show --
----------
instance (GT map k, Show k, Show a) => Show (MaybeGT map k a) where
  showsPrec d mp  = showParen (d > 10) $
    showString "fromAssocsAscending " . shows (assocsAscending mp)

----------
-- Read --
----------
#ifdef __GLASGOW_HASKELL__
instance (GT map k, R.Read k, R.Read a) => R.Read (MaybeGT map k a) where
 readPrec = R.parens $ R.prec 10 $ do R.Ident "fromAssocsAscending" <- R.lexP
                                      xs <- R.readPrec
                                      return (fromAssocsAscending xs)
 readListPrec = R.readListPrecDefault
#else
instance (GT map k, Read k, Read a) => Read (MaybeGT map k a) where
  readsPrec p = readParen (p > 10) $ \ r -> do ("fromAssocsAscending",s) <- lex r
                                               (xs,t) <- reads s
                                               return (fromAssocsAscending xs,t)
#endif

------------------------
-- Typeable/Typeable1 --
------------------------
instance (GT map k,Typeable1 map,Typeable k) => Typeable1 (MaybeGT map k) where
 typeOf1 mp = mkTyConApp (mkTyCon "Data.Trie.General.MaybeGT.MaybeGT") [typeOf1 m, typeOf k]
  where MaybeGT _ m = mp  -- This is just to get types for k & m !!
        [(k,_)] = assocsAscending m
--------------
instance (Typeable1 (MaybeGT map k), Typeable a) => Typeable (MaybeGT map k a) where
 typeOf = typeOfDefault

-------------
-- Functor --
-------------
instance GT map k => Functor (MaybeGT map k) where
-- fmap :: (a -> b) -> MaybeGT map k a -> MaybeGT map k b
   fmap = mapMaybeGT -- The lazy version

-----------------
-- Data.Monoid --
-----------------
instance (GT map k, M.Monoid a) => M.Monoid (MaybeGT map k a) where
-- mempty :: MaybeGT map k a
   mempty = emptyMaybeGT
-- mappend :: MaybeGT map k a -> MaybeGT map k a -> MaybeGT map k a
   mappend map0 map1 = unionMaybeGT M.mappend map0 map1
-- mconcat :: [MaybeGT map k a] -> MaybeGT map k a
   mconcat maps = L.foldr (unionMaybeGT M.mappend) emptyMaybeGT maps

-------------------
-- Data.Foldable --
-------------------
instance GT map k => F.Foldable (MaybeGT map k) where
-- fold :: Monoid m => MaybeGT map k m -> m
   fold mp = foldrElemsAscendingMaybeGT M.mappend mp M.mempty
-- foldMap :: Monoid m => (a -> m) -> MaybeGT map k a -> m
   foldMap f mp = foldrElemsAscendingMaybeGT (\a b -> M.mappend (f a) b) mp M.mempty
-- foldr :: (a -> b -> b) -> b -> MaybeGT map k a -> b
   foldr f b0 mp = foldrElemsAscendingMaybeGT f mp b0
-- foldl :: (a -> b -> a) -> a -> MaybeGT map k b -> a
   foldl f b0 mp = foldrElemsDescendingMaybeGT (flip f) mp b0
{- ToDo: Implement properly. Meantime Foldable class has suitable defaults via lists.
-- foldr1 :: (a -> a -> a) -> MaybeGT map k a -> a
   foldr1 = undefined
-- foldl1 :: (a -> a -> a) -> MaybeGT map k a -> a
   foldl1 = undefined
-}