{-# OPTIONS_GHC -fglasgow-exts -fno-warn-unused-imports -fallow-undecidable-instances #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Trie.General.EitherGT
-- 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 mapL kL, GT mapR kR) => 'Either' kL kR@
--
-- N.B. For 'Either's ascending order is @['Left x','Right x']@
-----------------------------------------------------------------------------
module Data.Trie.General.EitherGT
(-- * EitherGT type
 EitherGT

 -- * Standard GT API for EitherGTs
 -- | These functions all have the same names as the corresponding GT class methods,
 -- but with the \"EitherGT\" suffix.
,emptyEitherGT
,singletonEitherGT
,fromAssocsAscendingEitherGT
,fromAssocsDescendingEitherGT
,fromAssocsAscendingLEitherGT
,fromAssocsDescendingLEitherGT
,pairEitherGT
,isEmptyEitherGT
,isSingletonEitherGT
,nonEmptyEitherGT
,statusEitherGT
,addSizeEitherGT
,lookupEitherGT
,lookupContEitherGT
,insertEitherGT
,insertEitherGT'
,insertEitherGT''
,insertMaybeEitherGT
,insertMaybeEitherGT'
,deleteEitherGT
,deleteMaybeEitherGT
,alterEitherGT
,unionEitherGT
,unionEitherGT'
,unionMaybeEitherGT
,intersectionEitherGT
,intersectionEitherGT'
,intersectionMaybeEitherGT
,differenceEitherGT
,differenceMaybeEitherGT
,isSubsetOfEitherGT
,isSubmapOfEitherGT
,mapEitherGT
,mapEitherGT'
,mapMaybeEitherGT
,mapWithKeyEitherGT
,mapWithKeyEitherGT'
,filterEitherGT
,foldrElemsAscendingEitherGT
,foldrElemsDescendingEitherGT
,foldrKeysAscendingEitherGT
,foldrKeysDescendingEitherGT
,foldrAssocsAscendingEitherGT
,foldrAssocsDescendingEitherGT
,foldrElemsAscendingEitherGT'
,foldrElemsDescendingEitherGT'
,foldrKeysAscendingEitherGT'
,foldrKeysDescendingEitherGT'
,foldrAssocsAscendingEitherGT'
,foldrAssocsDescendingEitherGT'
,foldElemsUINTEitherGT
,validEitherGT
) 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' mapL kL, 'GT' mapR kR) => 'Either' kL kR@.
data EitherGT mapL mapR a = EitherGT !(mapL a) !(mapR a)

-- Needs -fallow-undecidable-instances due to coverage condition
instance (GT mapL kL, GT mapR kR) => GT (EitherGT mapL mapR) (Either kL kR) where
 empty                 = emptyEitherGT
 singleton             = singletonEitherGT
 fromAssocsAscending   = fromAssocsAscendingEitherGT
 fromAssocsDescending  = fromAssocsDescendingEitherGT
 fromAssocsAscendingL  = fromAssocsAscendingLEitherGT
 fromAssocsDescendingL = fromAssocsDescendingLEitherGT
 pair                  = pairEitherGT
 isEmpty               = isEmptyEitherGT
 isSingleton           = isSingletonEitherGT
 nonEmpty              = nonEmptyEitherGT
 status                = statusEitherGT
 addSize               = addSizeEitherGT
 lookup                = lookupEitherGT
 lookupCont            = lookupContEitherGT
 insert                = insertEitherGT
 insert'               = insertEitherGT'
 insert''              = insertEitherGT''
 insertMaybe           = insertMaybeEitherGT
 insertMaybe'          = insertMaybeEitherGT'
 delete                = deleteEitherGT
 deleteMaybe           = deleteMaybeEitherGT
 alter                 = alterEitherGT
 union                 = unionEitherGT
 union'                = unionEitherGT'
 unionMaybe            = unionMaybeEitherGT
 intersection          = intersectionEitherGT
 intersection'         = intersectionEitherGT'
 intersectionMaybe     = intersectionMaybeEitherGT
 difference            = differenceEitherGT
 differenceMaybe       = differenceMaybeEitherGT
 isSubsetOf            = isSubsetOfEitherGT
 isSubmapOf            = isSubmapOfEitherGT
 map                   = mapEitherGT
 map'                  = mapEitherGT'
 mapMaybe              = mapMaybeEitherGT
 mapWithKey            = mapWithKeyEitherGT
 mapWithKey'           = mapWithKeyEitherGT'
 filter                = filterEitherGT
 foldrElemsAscending   = foldrElemsAscendingEitherGT
 foldrElemsDescending  = foldrElemsDescendingEitherGT
 foldrKeysAscending    = foldrKeysAscendingEitherGT
 foldrKeysDescending   = foldrKeysDescendingEitherGT
 foldrAssocsAscending  = foldrAssocsAscendingEitherGT
 foldrAssocsDescending = foldrAssocsDescendingEitherGT
 foldrElemsAscending'  = foldrElemsAscendingEitherGT'
 foldrElemsDescending' = foldrElemsDescendingEitherGT'
 foldrKeysAscending'   = foldrKeysAscendingEitherGT'
 foldrKeysDescending'  = foldrKeysDescendingEitherGT'
 foldrAssocsAscending' = foldrAssocsAscendingEitherGT'
 foldrAssocsDescending'= foldrAssocsDescendingEitherGT'
 foldElemsUINT         = foldElemsUINTEitherGT
 valid                 = validEitherGT

-- | See 'GT' class method 'empty'.
emptyEitherGT :: (GT mapL kL, GT mapR kR) => EitherGT mapL mapR a
emptyEitherGT = EitherGT empty empty

-- | See 'GT' class method 'singleton'.
singletonEitherGT :: (GT mapL kL, GT mapR kR) => Either kL kR -> a -> EitherGT mapL mapR a
singletonEitherGT (Left  kL) a = EitherGT (singleton kL a) empty
singletonEitherGT (Right kR) a = EitherGT empty (singleton kR a)

-- | See 'GT' class method 'fromAssocsAscending'.
fromAssocsAscendingEitherGT :: (GT mapL kL, GT mapR kR) => [(Either kL kR,a)] -> EitherGT mapL mapR a
fromAssocsAscendingEitherGT []                  = emptyEitherGT
fromAssocsAscendingEitherGT ((Left  kL,a):ekas) = fAL       L(1) [(kL,a)] ekas
fromAssocsAscendingEitherGT ((Right kR,a):ekas) = fAR empty L(1) [(kR,a)] ekas
-- Helpers for fromAssocsAscendingEitherGT
fAL :: (GT mapL kL, GT mapR kR) => UINT -> [(kL,a)] -> [(Either kL kR,a)] -> EitherGT mapL mapR a
fAL n kasL []                  = EitherGT (fromAssocsDescendingL ASINT(n) kasL) empty
fAL n kasL ((Left  kL,a):ekas) = fAL                                       INCINT1(n) ((kL,a):kasL) ekas
fAL n kasL ((Right kR,a):ekas) = fAR (fromAssocsDescendingL ASINT(n) kasL) L(1)       [(kR,a)]      ekas
fAR :: (GT mapL kL, GT mapR kR) => mapL a -> UINT -> [(kR,a)] -> [(Either kL kR,a)] -> EitherGT mapL mapR a
fAR mapL n kasR []                  = EitherGT mapL (fromAssocsDescendingL ASINT(n) kasR)
fAR mapL n kasR ((Right kR,a):ekas) = fAR mapL INCINT1(n) ((kR,a):kasR) ekas
fAR _     _ _   ((Left  _ ,_):_   ) = error "Data.Trie.General.EitherGT: Bad ascending association List."

-- | See 'GT' class method 'fromAssocsDescending'.
fromAssocsDescendingEitherGT :: (GT mapL kL, GT mapR kR) => [(Either kL kR,a)] -> EitherGT mapL mapR a
fromAssocsDescendingEitherGT []                  = emptyEitherGT
fromAssocsDescendingEitherGT ((Right kR,a):ekas) = fDR       L(1) [(kR,a)] ekas
fromAssocsDescendingEitherGT ((Left  kL,a):ekas) = fDL empty L(1) [(kL,a)] ekas
-- Helpers for fromAssocsDescendingEitherGT
fDR :: (GT mapL kL, GT mapR kR) => UINT -> [(kR,a)] -> [(Either kL kR,a)] -> EitherGT mapL mapR a
fDR n kasR []                  = EitherGT empty (fromAssocsAscendingL ASINT(n) kasR)
fDR n kasR ((Right kR,a):ekas) = fDR                                      INCINT1(n) ((kR,a):kasR) ekas
fDR n kasR ((Left  kL,a):ekas) = fDL (fromAssocsAscendingL ASINT(n) kasR) L(1)       [(kL,a)]      ekas
fDL :: (GT mapL kL, GT mapR kR) => mapR a -> UINT -> [(kL,a)] -> [(Either kL kR,a)] -> EitherGT mapL mapR a
fDL mapR n kasL []                  = EitherGT (fromAssocsAscendingL ASINT(n) kasL) mapR
fDL mapR n kasL ((Left  kL,a):ekas) = fDL mapR INCINT1(n) ((kL,a):kasL) ekas
fDL _     _ _   ((Right _ ,_):_   ) = error "Data.Trie.General.EitherGT: Bad descending association List."

-- | See 'GT' class method 'fromAssocsAscendingL'.
fromAssocsAscendingLEitherGT :: (GT mapL kL, GT mapR kR) => Int -> [(Either kL kR,a)] -> EitherGT mapL mapR a
fromAssocsAscendingLEitherGT _ assocs = fromAssocsAscendingEitherGT assocs
{-# INLINE fromAssocsAscendingLEitherGT #-}

-- | See 'GT' class method 'fromAssocsDescendingL'.
fromAssocsDescendingLEitherGT :: (GT mapL kL, GT mapR kR) => Int -> [(Either kL kR,a)] -> EitherGT mapL mapR a
fromAssocsDescendingLEitherGT _ assocs = fromAssocsDescendingEitherGT assocs
{-# INLINE fromAssocsDescendingLEitherGT #-}

-- | See 'GT' class method 'pair'.
pairEitherGT :: (GT mapL kL, GT mapR kR) => Either kL kR -> Either kL kR -> Maybe (a -> a -> EitherGT mapL mapR a)
pairEitherGT (Left  k0) (Left  k1) = case pair k0 k1 of
                                     Nothing -> Nothing
                                     Just f  -> Just (\a0 a1 -> EitherGT (f a0 a1) empty)
pairEitherGT (Left  kL) (Right kR) = Just (\aL aR -> EitherGT (singleton kL aL) (singleton kR aR))
pairEitherGT (Right kR) (Left  kL) = Just (\aR aL -> EitherGT (singleton kL aL) (singleton kR aR))
pairEitherGT (Right k0) (Right k1) = case pair k0 k1 of
                                     Nothing -> Nothing
                                     Just f  -> Just (\a0 a1 -> EitherGT empty (f a0 a1))

-- | See 'GT' class method 'isEmpty'.
isEmptyEitherGT :: (GT mapL kL, GT mapR kR) => EitherGT mapL mapR a -> Bool
isEmptyEitherGT (EitherGT mapL mapR) = isEmpty mapL && isEmpty mapR
{-# INLINE isEmptyEitherGT #-}

-- | See 'GT' class method 'isSingleton'.
isSingletonEitherGT :: (GT mapL kL, GT mapR kR) => EitherGT mapL mapR a -> Bool
isSingletonEitherGT (EitherGT mapL mapR) = (isSingleton mapL && isEmpty mapR) || (isEmpty mapL && isSingleton mapR)

-- | See 'GT' class method 'nonEmpty'.
nonEmptyEitherGT :: (GT mapL kL, GT mapR kR) => EitherGT mapL mapR a -> Maybe (EitherGT mapL mapR a)
nonEmptyEitherGT egt = if isEmptyEitherGT egt then Nothing else Just egt

-- | See 'GT' class method 'status'.
statusEitherGT :: (GT mapL kL, GT mapR kR) => EitherGT mapL mapR a -> Status (Either kL kR) a
statusEitherGT (EitherGT mapL mapR) = s (status mapL) (status mapR) where
 s None        None        = None
 s None        (One kR aR) = One (Right kR) aR
 s (One kL aL) None        = One (Left  kL) aL
 s _           _           = Many

-- | See 'GT' class method 'addSize'.
addSizeEitherGT :: (GT mapL kL, GT mapR kR) => EitherGT mapL mapR a -> UINT -> UINT
#ifdef __GLASGOW_HASKELL__
addSizeEitherGT (EitherGT mapL mapR) n = addSize mapL (addSize mapR n)
#else
addSizeEitherGT (EitherGT mapL mapR) n = addSize mapL $! addSize mapR n
#endif

-- | See 'GT' class method 'lookup'.
lookupEitherGT :: (GT mapL kL, GT mapR kR) => Either kL kR -> EitherGT mapL mapR a -> Maybe a
lookupEitherGT (Left  kL) (EitherGT mapL _   ) = lookup kL mapL
lookupEitherGT (Right kR) (EitherGT _    mapR) = lookup kR mapR

-- | See 'GT' class method 'lookupCont'.
lookupContEitherGT :: (GT mapL kL, GT mapR kR) => (a -> Maybe b) -> Either kL kR -> EitherGT mapL mapR a -> Maybe b
lookupContEitherGT f (Left  kL) (EitherGT mapL _   ) = lookupCont f kL mapL
lookupContEitherGT f (Right kR) (EitherGT _    mapR) = lookupCont f kR mapR

-- | See 'GT' class method 'insert'.
insertEitherGT :: (GT mapL kL, GT mapR kR) => (a -> a) -> Either kL kR -> a -> EitherGT mapL mapR a -> EitherGT mapL mapR a
insertEitherGT f (Left  kL) a (EitherGT mapL mapR) = EitherGT (insert f kL a mapL) mapR
insertEitherGT f (Right kR) a (EitherGT mapL mapR) = EitherGT mapL (insert f kR a mapR)

-- | See 'GT' class method 'insert''.
insertEitherGT' :: (GT mapL kL, GT mapR kR) => (a -> a) -> Either kL kR -> a -> EitherGT mapL mapR a -> EitherGT mapL mapR a
insertEitherGT' f (Left  kL) a (EitherGT mapL mapR) = EitherGT (insert' f kL a mapL) mapR
insertEitherGT' f (Right kR) a (EitherGT mapL mapR) = EitherGT mapL (insert' f kR a mapR)

-- | See 'GT' class method 'insert'''.
insertEitherGT'' :: (GT mapL kL, GT mapR kR) => (a -> a) -> Either kL kR -> a -> EitherGT mapL mapR a -> EitherGT mapL mapR a
insertEitherGT'' f (Left  kL) a (EitherGT mapL mapR) = EitherGT (insert'' f kL a mapL) mapR
insertEitherGT'' f (Right kR) a (EitherGT mapL mapR) = EitherGT mapL (insert'' f kR a mapR)

-- | See 'GT' class method 'insertMaybe'.
insertMaybeEitherGT :: (GT mapL kL, GT mapR kR) => (a -> Maybe a) -> Either kL kR -> a -> EitherGT mapL mapR a -> EitherGT mapL mapR a
insertMaybeEitherGT f (Left  kL) a (EitherGT mapL mapR) = EitherGT (insertMaybe f kL a mapL) mapR
insertMaybeEitherGT f (Right kR) a (EitherGT mapL mapR) = EitherGT mapL (insertMaybe f kR a mapR)

-- | See 'GT' class method 'insertMaybe''.
insertMaybeEitherGT' :: (GT mapL kL, GT mapR kR) => (a -> Maybe a) -> Either kL kR -> a -> EitherGT mapL mapR a -> EitherGT mapL mapR a
insertMaybeEitherGT' f (Left  kL) a (EitherGT mapL mapR) = EitherGT (insertMaybe' f kL a mapL) mapR
insertMaybeEitherGT' f (Right kR) a (EitherGT mapL mapR) = EitherGT mapL (insertMaybe' f kR a mapR)

-- | See 'GT' class method 'delete'.
deleteEitherGT :: (GT mapL kL, GT mapR kR) => Either kL kR -> EitherGT mapL mapR a -> EitherGT mapL mapR a
deleteEitherGT (Left  kL) (EitherGT mapL mapR) = EitherGT (delete kL mapL) mapR
deleteEitherGT (Right kR) (EitherGT mapL mapR) = EitherGT mapL (delete kR mapR)

-- | See 'GT' class method 'deleteMaybe'.
deleteMaybeEitherGT :: (GT mapL kL, GT mapR kR) => (a -> Maybe a) -> Either kL kR -> EitherGT mapL mapR a -> EitherGT mapL mapR a
deleteMaybeEitherGT f (Left  kL) (EitherGT mapL mapR) = EitherGT (deleteMaybe f kL mapL) mapR
deleteMaybeEitherGT f (Right kR) (EitherGT mapL mapR) = EitherGT mapL (deleteMaybe f kR mapR)

-- | See 'GT' class method 'alter'.
alterEitherGT :: (GT mapL kL, GT mapR kR) => (Maybe a -> Maybe a) -> Either kL kR -> EitherGT mapL mapR a -> EitherGT mapL mapR a
alterEitherGT f (Left  kL) (EitherGT mapL mapR) = EitherGT (alter f kL mapL) mapR
alterEitherGT f (Right kR) (EitherGT mapL mapR) = EitherGT mapL (alter f kR mapR)

-- | See 'GT' class method 'union'.
unionEitherGT :: (GT mapL kL, GT mapR kR) => (a -> a -> a) -> EitherGT mapL mapR a -> EitherGT mapL mapR a -> EitherGT mapL mapR a
unionEitherGT f (EitherGT mapL0 mapR0) (EitherGT mapL1 mapR1) =
 EitherGT (union f mapL0 mapL1) (union f mapR0 mapR1)

-- | See 'GT' class method 'union''.
unionEitherGT' :: (GT mapL kL, GT mapR kR) => (a -> a -> a) -> EitherGT mapL mapR a -> EitherGT mapL mapR a -> EitherGT mapL mapR a
unionEitherGT' f (EitherGT mapL0 mapR0) (EitherGT mapL1 mapR1) =
 EitherGT (union' f mapL0 mapL1) (union' f mapR0 mapR1)

-- | See 'GT' class method 'unionMaybe'.
unionMaybeEitherGT :: (GT mapL kL, GT mapR kR) => (a -> a -> Maybe a) -> EitherGT mapL mapR a -> EitherGT mapL mapR a -> EitherGT mapL mapR a
unionMaybeEitherGT f (EitherGT mapL0 mapR0) (EitherGT mapL1 mapR1) =
 EitherGT (unionMaybe f mapL0 mapL1) (unionMaybe f mapR0 mapR1)

-- | See 'GT' class method 'intersection'.
intersectionEitherGT :: (GT mapL kL, GT mapR kR) => (a -> b -> c) -> EitherGT mapL mapR a -> EitherGT mapL mapR b -> EitherGT mapL mapR c
intersectionEitherGT f (EitherGT mapL0 mapR0) (EitherGT mapL1 mapR1) =
 EitherGT (intersection f mapL0 mapL1) (intersection f mapR0 mapR1)

-- | See 'GT' class method 'intersection''.
intersectionEitherGT' :: (GT mapL kL, GT mapR kR) => (a -> b -> c) -> EitherGT mapL mapR a -> EitherGT mapL mapR b -> EitherGT mapL mapR c
intersectionEitherGT' f (EitherGT mapL0 mapR0) (EitherGT mapL1 mapR1) =
 EitherGT (intersection' f mapL0 mapL1) (intersection' f mapR0 mapR1)

-- | See 'GT' class method 'intersectionMaybe'.
intersectionMaybeEitherGT :: (GT mapL kL, GT mapR kR) => (a -> b -> Maybe c) -> EitherGT mapL mapR a -> EitherGT mapL mapR b -> EitherGT mapL mapR c
intersectionMaybeEitherGT f (EitherGT mapL0 mapR0) (EitherGT mapL1 mapR1) =
 EitherGT (intersectionMaybe f mapL0 mapL1) (intersectionMaybe f mapR0 mapR1)

-- | See 'GT' class method 'difference'.
differenceEitherGT :: (GT mapL kL, GT mapR kR) => EitherGT mapL mapR a -> EitherGT mapL mapR b -> EitherGT mapL mapR a
differenceEitherGT (EitherGT mapL0 mapR0) (EitherGT mapL1 mapR1) =
 EitherGT (difference mapL0 mapL1) (difference mapR0 mapR1)

-- | See 'GT' class method 'differenceMaybe'.
differenceMaybeEitherGT :: (GT mapL kL, GT mapR kR) => (a -> b -> Maybe a) -> EitherGT mapL mapR a -> EitherGT mapL mapR b -> EitherGT mapL mapR a
differenceMaybeEitherGT f (EitherGT mapL0 mapR0) (EitherGT mapL1 mapR1) =
 EitherGT (differenceMaybe f mapL0 mapL1) (differenceMaybe f mapR0 mapR1)

-- | See 'GT' class method 'isSubsetOf'.
isSubsetOfEitherGT :: (GT mapL kL, GT mapR kR) => EitherGT mapL mapR a -> EitherGT mapL mapR b -> Bool
isSubsetOfEitherGT (EitherGT mapL0 mapR0) (EitherGT mapL1 mapR1) =
 isSubsetOf mapL0 mapL1 && isSubsetOf mapR0 mapR1

-- | See 'GT' class method 'isSubmapOf'.
isSubmapOfEitherGT :: (GT mapL kL, GT mapR kR) => (a -> b -> Bool) -> EitherGT mapL mapR a -> EitherGT mapL mapR b -> Bool
isSubmapOfEitherGT f (EitherGT mapL0 mapR0) (EitherGT mapL1 mapR1) =
 isSubmapOf f mapL0 mapL1 && isSubmapOf f mapR0 mapR1

-- | See 'GT' class method 'map'.
mapEitherGT :: (GT mapL kL, GT mapR kR) => (a -> b) -> EitherGT mapL mapR a -> EitherGT mapL mapR b
mapEitherGT f (EitherGT mapL mapR) = EitherGT (map f mapL) (map f mapR)

-- | See 'GT' class method 'map''.
mapEitherGT' :: (GT mapL kL, GT mapR kR) => (a -> b) -> EitherGT mapL mapR a -> EitherGT mapL mapR b
mapEitherGT' f (EitherGT mapL mapR) = EitherGT (map' f mapL) (map' f mapR)

-- | See 'GT' class method 'mapMaybe'.
mapMaybeEitherGT :: (GT mapL kL, GT mapR kR) => (a -> Maybe b) -> EitherGT mapL mapR a -> EitherGT mapL mapR b
mapMaybeEitherGT f (EitherGT mapL mapR) = EitherGT (mapMaybe f mapL) (mapMaybe f mapR)

-- | See 'GT' class method 'mapWithKey'.
mapWithKeyEitherGT :: (GT mapL kL, GT mapR kR) => (Either kL kR -> a -> b) -> EitherGT mapL mapR a -> EitherGT mapL mapR b
mapWithKeyEitherGT f (EitherGT mapL mapR) =
 EitherGT (mapWithKey (\kL a -> f (Left kL) a) mapL) (mapWithKey (\kR a -> f (Right kR) a) mapR)

-- | See 'GT' class method 'mapWithKey''.
mapWithKeyEitherGT' :: (GT mapL kL, GT mapR kR) => (Either kL kR -> a -> b) -> EitherGT mapL mapR a -> EitherGT mapL mapR b
mapWithKeyEitherGT' f (EitherGT mapL mapR) =
 EitherGT (mapWithKey' (\kL a -> f (Left kL) a) mapL) (mapWithKey' (\kR a -> f (Right kR) a) mapR)

-- | See 'GT' class method 'filter'.
filterEitherGT :: (GT mapL kL, GT mapR kR) => (a -> Bool) -> EitherGT mapL mapR a -> EitherGT mapL mapR a
filterEitherGT p (EitherGT mapL mapR) = EitherGT (filter p mapL) (filter p mapR)

-- | See 'GT' class method 'foldrElemsAscending'.
foldrElemsAscendingEitherGT :: (GT mapL kL, GT mapR kR) => (a -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrElemsAscendingEitherGT f (EitherGT mapL mapR) b =
 foldrElemsAscending f mapL (foldrElemsAscending f mapR b)

-- | See 'GT' class method 'foldrElemsDescending'.
foldrElemsDescendingEitherGT :: (GT mapL kL, GT mapR kR) => (a -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrElemsDescendingEitherGT f (EitherGT mapL mapR) b =
 foldrElemsDescending f mapR (foldrElemsDescending f mapL b)

-- | See 'GT' class method 'foldrKeysAscending'.
foldrKeysAscendingEitherGT :: (GT mapL kL, GT mapR kR) => (Either kL kR -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrKeysAscendingEitherGT f (EitherGT mapL mapR) b0 =
 foldrKeysAscending (\kL b -> f (Left kL) b) mapL (foldrKeysAscending (\kR b -> f (Right kR) b) mapR b0)

-- | See 'GT' class method 'foldrKeysDescending'.
foldrKeysDescendingEitherGT :: (GT mapL kL, GT mapR kR) => (Either kL kR -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrKeysDescendingEitherGT f (EitherGT mapL mapR) b0 =
 foldrKeysDescending (\kR b -> f (Right kR) b) mapR (foldrKeysDescending (\kL b -> f (Left kL) b) mapL b0)

-- | See 'GT' class method 'foldrAssocsAscending'.
foldrAssocsAscendingEitherGT :: (GT mapL kL, GT mapR kR) => (Either kL kR -> a -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrAssocsAscendingEitherGT f (EitherGT mapL mapR) b0 =
 foldrAssocsAscending (\kL a b -> f (Left kL) a b) mapL (foldrAssocsAscending (\kR a b -> f (Right kR) a b) mapR b0)

-- | See 'GT' class method 'foldrAssocsDescending'.
foldrAssocsDescendingEitherGT :: (GT mapL kL, GT mapR kR) => (Either kL kR -> a -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrAssocsDescendingEitherGT f (EitherGT mapL mapR) b0 =
 foldrAssocsDescending (\kR a b -> f (Right kR) a b) mapR (foldrAssocsDescending (\kL a b -> f (Left kL) a b) mapL b0)

-- | See 'GT' class method 'foldrElemsAscending''.
foldrElemsAscendingEitherGT' :: (GT mapL kL, GT mapR kR) => (a -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrElemsAscendingEitherGT' f (EitherGT mapL mapR) b =
 foldrElemsAscending' f mapL $! foldrElemsAscending' f mapR b

-- | See 'GT' class method 'foldrElemsDescending''.
foldrElemsDescendingEitherGT' :: (GT mapL kL, GT mapR kR) => (a -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrElemsDescendingEitherGT' f (EitherGT mapL mapR) b =
 foldrElemsDescending' f mapR $! foldrElemsDescending' f mapL b

-- | See 'GT' class method 'foldrKeysAscending''.
foldrKeysAscendingEitherGT' :: (GT mapL kL, GT mapR kR) => (Either kL kR -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrKeysAscendingEitherGT' f (EitherGT mapL mapR) b0 =
 foldrKeysAscending' (\kL b -> f (Left kL) b) mapL $! foldrKeysAscending' (\kR b -> f (Right kR) b) mapR b0

-- | See 'GT' class method 'foldrKeysDescending''.
foldrKeysDescendingEitherGT' :: (GT mapL kL, GT mapR kR) => (Either kL kR -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrKeysDescendingEitherGT' f (EitherGT mapL mapR) b0 =
 foldrKeysDescending' (\kR b -> f (Right kR) b) mapR $! foldrKeysDescending' (\kL b -> f (Left kL) b) mapL b0

-- | See 'GT' class method 'foldrAssocsAscending''.
foldrAssocsAscendingEitherGT' :: (GT mapL kL, GT mapR kR) => (Either kL kR -> a -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrAssocsAscendingEitherGT' f (EitherGT mapL mapR) b0 =
 foldrAssocsAscending' (\kL a b -> f (Left kL) a b) mapL $! foldrAssocsAscending' (\kR a b -> f (Right kR) a b) mapR b0

-- | See 'GT' class method 'foldrAssocsDescending''.
foldrAssocsDescendingEitherGT' :: (GT mapL kL, GT mapR kR) => (Either kL kR -> a -> b -> b) -> EitherGT mapL mapR a -> b -> b
foldrAssocsDescendingEitherGT' f (EitherGT mapL mapR) b0 =
 foldrAssocsDescending' (\kR a b -> f (Right kR) a b) mapR $! foldrAssocsDescending' (\kL a b -> f (Left kL) a b) mapL b0

-- | See 'GT' class method 'foldElemsUINT'.
foldElemsUINTEitherGT :: (GT mapL kL, GT mapR kR) => (a -> UINT -> UINT) -> EitherGT mapL mapR a -> UINT -> UINT
#ifdef __GLASGOW_HASKELL__
foldElemsUINTEitherGT f (EitherGT mapL mapR) n = foldElemsUINT f mapL (foldElemsUINT f mapR n)
#else
foldElemsUINTEitherGT f (EitherGT mapL mapR) n = foldElemsUINT f mapL $! foldElemsUINT f mapR n
#endif

-- | See 'GT' class method 'valid'.
validEitherGT :: (GT mapL kL, GT mapR kR) => EitherGT mapL mapR a -> Maybe String
validEitherGT (EitherGT mapL mapR) = case valid mapL of
                                     Nothing -> valid mapR
                                     j       -> j

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

--------
-- Eq --
--------
instance (Eq (mapL a), Eq (mapR a)) => Eq (EitherGT mapL mapR a) where
 EitherGT mapL0 mapR0 == EitherGT mapL1 mapR1 = (mapL0 == mapL1) && (mapR0 == mapR1)

---------
-- Ord --
---------
instance (GT mapL kL, GT mapR kR, Ord (mapL a), Ord (mapR a)) => Ord (EitherGT mapL mapR a) where
 compare (EitherGT mapL0 mapR0) (EitherGT mapL1 mapR1) = c (isEmpty mapL0) (isEmpty mapL1) where
  c True  True  = compare mapR0 mapR1
  c True  False = if isEmpty mapR0 then LT else GT
  c False True  = if isEmpty mapR1 then GT else LT
  c False False = case compare mapL0 mapL1 of
                  LT -> LT
                  EQ -> compare mapR0 mapR1
                  GT -> GT

----------
-- Show --
----------
instance (GT mapL kL, GT mapR kR, Show kL, Show kR, Show a) => Show (EitherGT mapL mapR a) where
  showsPrec d mp  = showParen (d > 10) $
    showString "fromAssocsAscending " . shows (assocsAscending mp)

----------
-- Read --
----------
#ifdef __GLASGOW_HASKELL__
instance (GT mapL kL, GT mapR kR, R.Read kL, R.Read kR, R.Read a) => R.Read (EitherGT mapL mapR 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 mapL kL, GT mapR kR, Read kL, Read kR, Read a) => Read (EitherGT mapL mapR 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 (Typeable1 mapL, Typeable1 mapR) => Typeable1 (EitherGT mapL mapR) where
 typeOf1 m = mkTyConApp (mkTyCon "Data.Trie.General.EitherGT.EitherGT") [typeOf1 mapL, typeOf1 mapR]
  where EitherGT mapL mapR = m -- This is just to get types for mapL & mapR !!
--------------
instance (Typeable1 (EitherGT mapL mapR), Typeable a) => Typeable (EitherGT mapL mapR a) where
 typeOf = typeOfDefault

-------------
-- Functor --
-------------
instance (GT mapL kL, GT mapR kR) => Functor (EitherGT mapL mapR) where
-- fmap :: (a -> b) -> EitherGT mapL mapR a -> EitherGT mapL mapR b
   fmap = mapEitherGT -- The lazy version

-----------------
-- Data.Monoid --
-----------------
instance (GT mapL kL, GT mapR kR, M.Monoid a) => M.Monoid (EitherGT mapL mapR a) where
-- mempty :: EitherGT mapL mapR a
   mempty = emptyEitherGT
-- mappend :: EitherGT mapL mapR a -> EitherGT mapL mapR a -> EitherGT mapL mapR a
   mappend map0 map1 = unionEitherGT M.mappend map0 map1
-- mconcat :: [EitherGT mapL mapR a] -> EitherGT mapL mapR a
   mconcat maps = L.foldr (unionEitherGT M.mappend) emptyEitherGT maps

-------------------
-- Data.Foldable --
-------------------
instance (GT mapL kL, GT mapR kR) => F.Foldable (EitherGT mapL mapR) where
-- fold :: Monoid m => EitherGT mapL mapR m -> m
   fold mp = foldrElemsAscendingEitherGT M.mappend mp M.mempty
-- foldMap :: Monoid m => (a -> m) -> EitherGT mapL mapR a -> m
   foldMap f mp = foldrElemsAscendingEitherGT (\a b -> M.mappend (f a) b) mp M.mempty
-- foldr :: (a -> b -> b) -> b -> EitherGT mapL mapR a -> b
   foldr f b0 mp = foldrElemsAscendingEitherGT f mp b0
-- foldl :: (a -> b -> a) -> a -> EitherGT mapL mapR b -> a
   foldl f b0 mp = foldrElemsDescendingEitherGT (flip f) mp b0
{- ToDo: Implement properly. Meantime Foldable class has suitable defaults via lists.
-- foldr1 :: (a -> a -> a) -> EitherGT mapL mapR a -> a
   foldr1 = undefined
-- foldl1 :: (a -> a -> a) -> EitherGT mapL mapR a -> a
   foldl1 = undefined
-}