{-# OPTIONS_GHC -fglasgow-exts -fno-warn-orphans -fno-warn-unused-imports #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Trie.General.$TypeName$GT
-- Copyright   :  (c) Adrian Hey 2007
-- License     :  BSD3
--
-- Maintainer  :  http://homepages.nildram.co.uk/~ahey/em.png
-- Stability   :  provisional
-- Portability :  non-portable
--
-- This is a textual template to use to create new GT instances by Hand.
-- To use:
--  1- Define the appropriate GT type (see below).
--  2- Do appropriate global string substitutions as follows:
--     Basic Type or Class name: $TypeName$  E.G. "List"        ,"Ord"    ,"Bool"
--     Actual Type constructor:  $TypeCons$  E.G. "ListGT map k","OrdGT k","BoolGT"
--     Actual Key Type:          $TypeKey$   E.G. "[k]"         ,"k"      ,"Bool"
--  3- Write code, adding whatever class constraints mey be needed in type sigs.
--  4- Delete this header comment and write something sensible instead.
--
-----------------------------------------------------------------------------
module Data.Trie.General.$TypeName$GT
(-- * $TypeName$GT type
 $TypeName$GT

 -- * Standard GT API for $TypeName$GTs
 -- | These functions all have the same names as the corresponding GT class methods,
 -- but with the \"$TypeName$GT\" suffix.
,empty$TypeName$GT
,singleton$TypeName$GT
,fromAssocsAscending$TypeName$GT
,fromAssocsDescending$TypeName$GT
,fromAssocsAscendingL$TypeName$GT
,fromAssocsDescendingL$TypeName$GT
,pair$TypeName$GT
,isEmpty$TypeName$GT
,isSingleton$TypeName$GT
,nonEmpty$TypeName$GT
,status$TypeName$GT
,addSize$TypeName$GT
,lookup$TypeName$GT
,lookupCont$TypeName$GT
,insert$TypeName$GT
,insert$TypeName$GT'
,insert$TypeName$GT''
,insertMaybe$TypeName$GT
,insertMaybe$TypeName$GT'
,delete$TypeName$GT
,deleteMaybe$TypeName$GT
,alter$TypeName$GT
,union$TypeName$GT
,union$TypeName$GT'
,unionMaybe$TypeName$GT
,intersection$TypeName$GT
,intersection$TypeName$GT'
,intersectionMaybe$TypeName$GT
,difference$TypeName$GT
,differenceMaybe$TypeName$GT
,isSubsetOf$TypeName$GT
,isSubmapOf$TypeName$GT
,map$TypeName$GT
,map$TypeName$GT'
,mapMaybe$TypeName$GT
,mapWithKey$TypeName$GT
,mapWithKey$TypeName$GT'
,filter$TypeName$GT
,foldrElemsAscending$TypeName$GT
,foldrElemsDescending$TypeName$GT
,foldrKeysAscending$TypeName$GT
,foldrKeysDescending$TypeName$GT
,foldrAssocsAscending$TypeName$GT
,foldrAssocsDescending$TypeName$GT
,foldrElemsAscending$TypeName$GT'
,foldrElemsDescending$TypeName$GT'
,foldrKeysAscending$TypeName$GT'
,foldrKeysDescending$TypeName$GT'
,foldrAssocsAscending$TypeName$GT'
,foldrAssocsDescending$TypeName$GT'
,foldElemsUINT$TypeName$GT
,valid$TypeName$GT
) 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

-- | Put the Trie type definition here using data (or newtype)
data $TypeCons$ a

instance GT ($TypeCons$) ($TypeKey$) where
 empty                 = empty$TypeName$GT
 singleton             = singleton$TypeName$GT
 fromAssocsAscending   = fromAssocsAscending$TypeName$GT
 fromAssocsDescending  = fromAssocsDescending$TypeName$GT
 fromAssocsAscendingL  = fromAssocsAscendingL$TypeName$GT
 fromAssocsDescendingL = fromAssocsDescendingL$TypeName$GT
 pair                  = pair$TypeName$GT
 isEmpty               = isEmpty$TypeName$GT
 isSingleton           = isSingleton$TypeName$GT
 nonEmpty              = nonEmpty$TypeName$GT
 status                = status$TypeName$GT
 addSize               = addSize$TypeName$GT
 lookup                = lookup$TypeName$GT
 lookupCont            = lookupCont$TypeName$GT
 insert                = insert$TypeName$GT
 insert'               = insert$TypeName$GT'
 insert''              = insert$TypeName$GT''
 insertMaybe           = insertMaybe$TypeName$GT
 insertMaybe'          = insertMaybe$TypeName$GT'
 delete                = delete$TypeName$GT
 deleteMaybe           = deleteMaybe$TypeName$GT
 alter                 = alter$TypeName$GT
 union                 = union$TypeName$GT
 union'                = union$TypeName$GT'
 unionMaybe            = unionMaybe$TypeName$GT
 intersection          = intersection$TypeName$GT
 intersection'         = intersection$TypeName$GT'
 intersectionMaybe     = intersectionMaybe$TypeName$GT
 difference            = difference$TypeName$GT
 differenceMaybe       = differenceMaybe$TypeName$GT
 isSubsetOf            = isSubsetOf$TypeName$GT
 isSubmapOf            = isSubmapOf$TypeName$GT
 map                   = map$TypeName$GT
 map'                  = map$TypeName$GT'
 mapMaybe              = mapMaybe$TypeName$GT
 mapWithKey            = mapWithKey$TypeName$GT
 mapWithKey'           = mapWithKey$TypeName$GT'
 filter                = filter$TypeName$GT
 foldrElemsAscending   = foldrElemsAscending$TypeName$GT
 foldrElemsDescending  = foldrElemsDescending$TypeName$GT
 foldrKeysAscending    = foldrKeysAscending$TypeName$GT
 foldrKeysDescending   = foldrKeysDescending$TypeName$GT
 foldrAssocsAscending  = foldrAssocsAscending$TypeName$GT
 foldrAssocsDescending = foldrAssocsDescending$TypeName$GT
 foldrElemsAscending'  = foldrElemsAscending$TypeName$GT'
 foldrElemsDescending' = foldrElemsDescending$TypeName$GT'
 foldrKeysAscending'   = foldrKeysAscending$TypeName$GT'
 foldrKeysDescending'  = foldrKeysDescending$TypeName$GT'
 foldrAssocsAscending' = foldrAssocsAscending$TypeName$GT'
 foldrAssocsDescending'= foldrAssocsDescending$TypeName$GT'
 foldElemsUINT         = foldElemsUINT$TypeName$GT
 valid                 = valid$TypeName$GT

-- | See 'GT' class method 'empty'.
empty$TypeName$GT :: $TypeCons$ a
empty$TypeName$GT = undefined

-- | See 'GT' class method 'singleton'.
singleton$TypeName$GT :: $TypeKey$ -> a -> $TypeCons$ a
singleton$TypeName$GT = undefined

-- | See 'GT' class method 'fromAssocsAscending'.
fromAssocsAscending$TypeName$GT :: [($TypeKey$,a)] -> $TypeCons$ a
fromAssocsAscending$TypeName$GT = undefined

-- | See 'GT' class method 'fromAssocsDescending'.
fromAssocsDescending$TypeName$GT :: [($TypeKey$,a)] -> $TypeCons$ a
fromAssocsDescending$TypeName$GT = undefined

-- | See 'GT' class method 'fromAssocsAscendingL'.
fromAssocsAscendingL$TypeName$GT :: Int -> [($TypeKey$,a)] -> $TypeCons$ a
fromAssocsAscendingL$TypeName$GT = undefined

-- | See 'GT' class method 'fromAssocsDescendingL'.
fromAssocsDescendingL$TypeName$GT :: Int -> [($TypeKey$,a)] -> $TypeCons$ a
fromAssocsDescendingL$TypeName$GT = undefined

-- | See 'GT' class method 'pair'.
pair$TypeName$GT :: $TypeKey$ -> $TypeKey$ -> Maybe (a -> a -> $TypeCons$ a)
pair$TypeName$GT = undefined

-- | See 'GT' class method 'isEmpty'.
isEmpty$TypeName$GT :: $TypeCons$ a -> Bool
isEmpty$TypeName$GT = undefined

-- | See 'GT' class method 'isSingleton'.
isSingleton$TypeName$GT :: $TypeCons$ a -> Bool
isSingleton$TypeName$GT = undefined

-- | See 'GT' class method 'nonEmpty'.
nonEmpty$TypeName$GT :: $TypeCons$ a -> Maybe ($TypeCons$ a)
nonEmpty$TypeName$GT = undefined

-- | See 'GT' class method 'status'.
status$TypeName$GT :: $TypeCons$ a -> Status ($TypeKey$) a
status$TypeName$GT = undefined

-- | See 'GT' class method 'addSize'.
addSize$TypeName$GT :: $TypeCons$ a -> UINT -> UINT
addSize$TypeName$GT = undefined

-- | See 'GT' class method 'lookup'.
lookup$TypeName$GT :: $TypeKey$ -> $TypeCons$ a -> Maybe a
lookup$TypeName$GT = undefined

-- | See 'GT' class method 'lookupCont'.
lookupCont$TypeName$GT :: (a -> Maybe b) -> $TypeKey$ -> $TypeCons$ a -> Maybe b
lookupCont$TypeName$GT = undefined

-- | See 'GT' class method 'insert'.
insert$TypeName$GT :: (a -> a) -> $TypeKey$ -> a -> $TypeCons$ a -> $TypeCons$ a
insert$TypeName$GT = undefined

-- | See 'GT' class method 'insert''.
insert$TypeName$GT' :: (a -> a) -> $TypeKey$ -> a -> $TypeCons$ a -> $TypeCons$ a
insert$TypeName$GT' = undefined

-- | See 'GT' class method 'insert'''.
insert$TypeName$GT'' :: (a -> a) -> $TypeKey$ -> a -> $TypeCons$ a -> $TypeCons$ a
insert$TypeName$GT'' = undefined

-- | See 'GT' class method 'insertMaybe'.
insertMaybe$TypeName$GT :: (a -> Maybe a) -> $TypeKey$ -> a -> $TypeCons$ a -> $TypeCons$ a
insertMaybe$TypeName$GT = undefined

-- | See 'GT' class method 'insertMaybe''.
insertMaybe$TypeName$GT' :: (a -> Maybe a) -> $TypeKey$ -> a -> $TypeCons$ a -> $TypeCons$ a
insertMaybe$TypeName$GT' = undefined

-- | See 'GT' class method 'delete'.
delete$TypeName$GT :: $TypeKey$ -> $TypeCons$ a -> $TypeCons$ a
delete$TypeName$GT = undefined

-- | See 'GT' class method 'deleteMaybe'.
deleteMaybe$TypeName$GT :: (a -> Maybe a) -> $TypeKey$ -> $TypeCons$ a -> $TypeCons$ a
deleteMaybe$TypeName$GT = undefined

-- | See 'GT' class method 'alter'.
alter$TypeName$GT :: (Maybe a -> Maybe a) -> $TypeKey$ -> $TypeCons$ a -> $TypeCons$ a
alter$TypeName$GT = undefined

-- | See 'GT' class method 'union'.
union$TypeName$GT :: (a -> a -> a) -> $TypeCons$ a -> $TypeCons$ a -> $TypeCons$ a
union$TypeName$GT = undefined

-- | See 'GT' class method 'union''.
union$TypeName$GT' :: (a -> a -> a) -> $TypeCons$ a -> $TypeCons$ a -> $TypeCons$ a
union$TypeName$GT' = undefined

-- | See 'GT' class method 'unionMaybe'.
unionMaybe$TypeName$GT :: (a -> a -> Maybe a) -> $TypeCons$ a -> $TypeCons$ a -> $TypeCons$ a
unionMaybe$TypeName$GT = undefined

-- | See 'GT' class method 'intersection'.
intersection$TypeName$GT :: (a -> b -> c) -> $TypeCons$ a -> $TypeCons$ b -> $TypeCons$ c
intersection$TypeName$GT = undefined

-- | See 'GT' class method 'intersection''.
intersection$TypeName$GT' :: (a -> b -> c) -> $TypeCons$ a -> $TypeCons$ b -> $TypeCons$ c
intersection$TypeName$GT' = undefined

-- | See 'GT' class method 'intersectionMaybe'.
intersectionMaybe$TypeName$GT :: (a -> b -> Maybe c) -> $TypeCons$ a -> $TypeCons$ b -> $TypeCons$ c
intersectionMaybe$TypeName$GT = undefined

-- | See 'GT' class method 'difference'.
difference$TypeName$GT :: $TypeCons$ a -> $TypeCons$ b -> $TypeCons$ a
difference$TypeName$GT = undefined

-- | See 'GT' class method 'differenceMaybe'.
differenceMaybe$TypeName$GT :: (a -> b -> Maybe a) -> $TypeCons$ a -> $TypeCons$ b -> $TypeCons$ a
differenceMaybe$TypeName$GT = undefined

-- | See 'GT' class method 'isSubsetOf'.
isSubsetOf$TypeName$GT :: $TypeCons$ a -> $TypeCons$ b -> Bool
isSubsetOf$TypeName$GT = undefined

-- | See 'GT' class method 'isSubmapOf'.
isSubmapOf$TypeName$GT :: (a -> b -> Bool) -> $TypeCons$ a -> $TypeCons$ b -> Bool
isSubmapOf$TypeName$GT = undefined

-- | See 'GT' class method 'map'.
map$TypeName$GT :: (a -> b) -> $TypeCons$ a -> $TypeCons$ b
map$TypeName$GT = undefined

-- | See 'GT' class method 'map''.
map$TypeName$GT' :: (a -> b) -> $TypeCons$ a -> $TypeCons$ b
map$TypeName$GT' = undefined

-- | See 'GT' class method 'mapMaybe'.
mapMaybe$TypeName$GT :: (a -> Maybe b) -> $TypeCons$ a -> $TypeCons$ b
mapMaybe$TypeName$GT = undefined

-- | See 'GT' class method 'mapWithKey'.
mapWithKey$TypeName$GT :: ($TypeKey$ -> a -> b) -> $TypeCons$ a -> $TypeCons$ b
mapWithKey$TypeName$GT = undefined

-- | See 'GT' class method 'mapWithKey''.
mapWithKey$TypeName$GT' :: ($TypeKey$ -> a -> b) -> $TypeCons$ a -> $TypeCons$ b
mapWithKey$TypeName$GT' = undefined

-- | See 'GT' class method 'filter'.
filter$TypeName$GT :: (a -> Bool) -> $TypeCons$ a -> $TypeCons$ a
filter$TypeName$GT = undefined

-- | See 'GT' class method 'foldrElemsAscending'.
foldrElemsAscending$TypeName$GT :: (a -> b -> b) -> $TypeCons$ a -> b -> b
foldrElemsAscending$TypeName$GT = undefined

-- | See 'GT' class method 'foldrElemsDescending'.
foldrElemsDescending$TypeName$GT :: (a -> b -> b) -> $TypeCons$ a -> b -> b
foldrElemsDescending$TypeName$GT = undefined

-- | See 'GT' class method 'foldrKeysAscending'.
foldrKeysAscending$TypeName$GT :: ($TypeKey$ -> b -> b) -> $TypeCons$ a -> b -> b
foldrKeysAscending$TypeName$GT = undefined

-- | See 'GT' class method 'foldrKeysDescending'.
foldrKeysDescending$TypeName$GT :: ($TypeKey$ -> b -> b) -> $TypeCons$ a -> b -> b
foldrKeysDescending$TypeName$GT = undefined

-- | See 'GT' class method 'foldrAssocsAscending'.
foldrAssocsAscending$TypeName$GT :: ($TypeKey$ -> a -> b -> b) -> $TypeCons$ a -> b -> b
foldrAssocsAscending$TypeName$GT = undefined

-- | See 'GT' class method 'foldrAssocsDescending'.
foldrAssocsDescending$TypeName$GT :: ($TypeKey$ -> a -> b -> b) -> $TypeCons$ a -> b -> b
foldrAssocsDescending$TypeName$GT = undefined

-- | See 'GT' class method 'foldrElemsAscending''.
foldrElemsAscending$TypeName$GT' :: (a -> b -> b) -> $TypeCons$ a -> b -> b
foldrElemsAscending$TypeName$GT' = undefined

-- | See 'GT' class method 'foldrElemsDescending''.
foldrElemsDescending$TypeName$GT' :: (a -> b -> b) -> $TypeCons$ a -> b -> b
foldrElemsDescending$TypeName$GT' = undefined

-- | See 'GT' class method 'foldrKeysAscending''.
foldrKeysAscending$TypeName$GT' :: ($TypeKey$ -> b -> b) -> $TypeCons$ a -> b -> b
foldrKeysAscending$TypeName$GT' = undefined

-- | See 'GT' class method 'foldrKeysDescending''.
foldrKeysDescending$TypeName$GT' :: ($TypeKey$ -> b -> b) -> $TypeCons$ a -> b -> b
foldrKeysDescending$TypeName$GT' = undefined

-- | See 'GT' class method 'foldrAssocsAscending''.
foldrAssocsAscending$TypeName$GT' :: ($TypeKey$ -> a -> b -> b) -> $TypeCons$ a -> b -> b
foldrAssocsAscending$TypeName$GT' = undefined

-- | See 'GT' class method 'foldrAssocsDescending''.
foldrAssocsDescending$TypeName$GT' :: ($TypeKey$ -> a -> b -> b) -> $TypeCons$ a -> b -> b
foldrAssocsDescending$TypeName$GT' = undefined

-- | See 'GT' class method 'foldElemsUINT'.
foldElemsUINT$TypeName$GT :: (a -> UINT -> UINT) -> $TypeCons$ a -> UINT -> UINT
foldElemsUINT$TypeName$GT = undefined

-- | See 'GT' class method 'valid'.
valid$TypeName$GT :: $TypeCons$ a -> Maybe String
valid$TypeName$GT = undefined

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

--------
-- Eq --
--------
instance (Eq a) => Eq ($TypeCons$ a) where
 (==) = undefined

---------
-- Ord --
---------
instance (Ord a) => Ord ($TypeCons$ a) where
 compare = undefined

----------
-- Show --
----------
instance (Show a) => Show ($TypeCons$ a) where
  showsPrec d mp  = showParen (d > 10) $
    showString "fromAssocsAscending " . shows (assocsAscending mp)

----------
-- Read --
----------
#ifdef __GLASGOW_HASKELL__
instance (R.Read a) => R.Read ($TypeCons$ 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 (Read a) => Read ($TypeCons$ 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 ($TypeCons$) where
 typeOf1 _ = mkTyConApp (mkTyCon "Data.Trie.General.$TypeName$GT.$TypeName$GT") []
--------------
instance Typeable a => Typeable ($TypeCons$ a) where
 typeOf = typeOfDefault

-------------
-- Functor --
-------------
instance Functor ($TypeCons$) where
-- fmap :: (a -> b) -> $TypeCons$ a -> $TypeCons$ b
   fmap = map$TypeName$GT -- The lazy version

-----------------
-- Data.Monoid --
-----------------
instance (M.Monoid a) => M.Monoid ($TypeCons$ a) where
-- mempty :: $TypeCons$ a
   mempty = empty$TypeName$GT
-- mappend :: $TypeCons$ a -> $TypeCons$ a -> $TypeCons$ a
   mappend map0 map1 = union$TypeName$GT M.mappend map0 map1
-- mconcat :: [$TypeCons$ a] -> $TypeCons$ a
   mconcat maps = L.foldr (union$TypeName$GT M.mappend) empty$TypeName$GT maps

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