module Language.Preprocessor.Cpphs.SymTab
( SymTab
, emptyST
, insertST
, deleteST
, lookupST
, definedST
, flattenST
, IndTree
) where
type SymTab v = IndTree [(String,v)]
emptyST :: SymTab v
insertST :: (String,v) -> SymTab v -> SymTab v
deleteST :: String -> SymTab v -> SymTab v
lookupST :: String -> SymTab v -> Maybe v
definedST :: String -> SymTab v -> Bool
flattenST :: SymTab v -> [v]
emptyST :: forall v. SymTab v
emptyST = forall a. Int -> a -> IndTree a
itgen Int
maxHash []
insertST :: forall v. (String, v) -> SymTab v -> SymTab v
insertST (String
s,v
v) SymTab v
ss = forall a b. Int -> (a -> a) -> IndTree a -> (IndTree a -> b) -> b
itiap (forall a. Hashable a => a -> Int
hash String
s) ((String
s,v
v)forall a. a -> [a] -> [a]
:) SymTab v
ss forall a. a -> a
id
deleteST :: forall v. String -> SymTab v -> SymTab v
deleteST String
s SymTab v
ss = forall a b. Int -> (a -> a) -> IndTree a -> (IndTree a -> b) -> b
itiap (forall a. Hashable a => a -> Int
hash String
s) (forall a. (a -> Bool) -> [a] -> [a]
filter ((forall a. Eq a => a -> a -> Bool
/=String
s)forall b c a. (b -> c) -> (a -> b) -> a -> c
.forall a b. (a, b) -> a
fst)) SymTab v
ss forall a. a -> a
id
lookupST :: forall v. String -> SymTab v -> Maybe v
lookupST String
s SymTab v
ss = let vs :: [(String, v)]
vs = forall a. (a -> Bool) -> [a] -> [a]
filter ((forall a. Eq a => a -> a -> Bool
==String
s)forall b c a. (b -> c) -> (a -> b) -> a -> c
.forall a b. (a, b) -> a
fst) ((forall a. Int -> IndTree a -> a
itind (forall a. Hashable a => a -> Int
hash String
s)) SymTab v
ss)
in if forall (t :: * -> *) a. Foldable t => t a -> Bool
null [(String, v)]
vs then forall a. Maybe a
Nothing
else (forall a. a -> Maybe a
Just forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. [a] -> a
head) [(String, v)]
vs
definedST :: forall v. String -> SymTab v -> Bool
definedST String
s SymTab v
ss = let vs :: [(String, v)]
vs = forall a. (a -> Bool) -> [a] -> [a]
filter ((forall a. Eq a => a -> a -> Bool
==String
s)forall b c a. (b -> c) -> (a -> b) -> a -> c
.forall a b. (a, b) -> a
fst) ((forall a. Int -> IndTree a -> a
itind (forall a. Hashable a => a -> Int
hash String
s)) SymTab v
ss)
in (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) a. Foldable t => t a -> Bool
null) [(String, v)]
vs
flattenST :: forall v. SymTab v -> [v]
flattenST SymTab v
ss = forall a b. (a -> b) -> (b -> b -> b) -> IndTree a -> b
itfold (forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd) forall a. [a] -> [a] -> [a]
(++) SymTab v
ss
data IndTree t = Leaf t | Fork Int (IndTree t) (IndTree t)
deriving Int -> IndTree t -> ShowS
forall t. Show t => Int -> IndTree t -> ShowS
forall t. Show t => [IndTree t] -> ShowS
forall t. Show t => IndTree t -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [IndTree t] -> ShowS
$cshowList :: forall t. Show t => [IndTree t] -> ShowS
show :: IndTree t -> String
$cshow :: forall t. Show t => IndTree t -> String
showsPrec :: Int -> IndTree t -> ShowS
$cshowsPrec :: forall t. Show t => Int -> IndTree t -> ShowS
Show
itgen :: Int -> a -> IndTree a
itgen :: forall a. Int -> a -> IndTree a
itgen Int
1 a
x = forall t. t -> IndTree t
Leaf a
x
itgen Int
n a
x =
let n' :: Int
n' = Int
n forall a. Integral a => a -> a -> a
`div` Int
2
in forall t. Int -> IndTree t -> IndTree t -> IndTree t
Fork Int
n' (forall a. Int -> a -> IndTree a
itgen Int
n' a
x) (forall a. Int -> a -> IndTree a
itgen (Int
nforall a. Num a => a -> a -> a
-Int
n') a
x)
itiap ::
Int -> (a->a) -> IndTree a -> (IndTree a -> b) -> b
itiap :: forall a b. Int -> (a -> a) -> IndTree a -> (IndTree a -> b) -> b
itiap Int
_ a -> a
f (Leaf a
x) IndTree a -> b
k = let fx :: a
fx = a -> a
f a
x in (IndTree a -> b
k (forall t. t -> IndTree t
Leaf a
fx))
itiap Int
i a -> a
f (Fork Int
n IndTree a
lt IndTree a
rt) IndTree a -> b
k =
if Int
iforall a. Ord a => a -> a -> Bool
<Int
n then
forall a b. Int -> (a -> a) -> IndTree a -> (IndTree a -> b) -> b
itiap Int
i a -> a
f IndTree a
lt forall a b. (a -> b) -> a -> b
$ \IndTree a
lt' -> IndTree a -> b
k (forall t. Int -> IndTree t -> IndTree t -> IndTree t
Fork Int
n IndTree a
lt' IndTree a
rt)
else forall a b. Int -> (a -> a) -> IndTree a -> (IndTree a -> b) -> b
itiap (Int
iforall a. Num a => a -> a -> a
-Int
n) a -> a
f IndTree a
rt forall a b. (a -> b) -> a -> b
$ \IndTree a
rt' -> IndTree a -> b
k (forall t. Int -> IndTree t -> IndTree t -> IndTree t
Fork Int
n IndTree a
lt IndTree a
rt')
itind :: Int -> IndTree a -> a
itind :: forall a. Int -> IndTree a -> a
itind Int
_ (Leaf a
x) = a
x
itind Int
i (Fork Int
n IndTree a
lt IndTree a
rt) = if Int
iforall a. Ord a => a -> a -> Bool
<Int
n then forall a. Int -> IndTree a -> a
itind Int
i IndTree a
lt else forall a. Int -> IndTree a -> a
itind (Int
iforall a. Num a => a -> a -> a
-Int
n) IndTree a
rt
itfold :: (a->b) -> (b->b->b) -> IndTree a -> b
itfold :: forall a b. (a -> b) -> (b -> b -> b) -> IndTree a -> b
itfold a -> b
leaf b -> b -> b
_fork (Leaf a
x) = a -> b
leaf a
x
itfold a -> b
leaf b -> b -> b
fork (Fork Int
_ IndTree a
l IndTree a
r) = b -> b -> b
fork (forall a b. (a -> b) -> (b -> b -> b) -> IndTree a -> b
itfold a -> b
leaf b -> b -> b
fork IndTree a
l) (forall a b. (a -> b) -> (b -> b -> b) -> IndTree a -> b
itfold a -> b
leaf b -> b -> b
fork IndTree a
r)
maxHash :: Int
maxHash :: Int
maxHash = Int
101
class Hashable a where
hashWithMax :: Int -> a -> Int
hash :: a -> Int
hash = forall a. Hashable a => Int -> a -> Int
hashWithMax Int
maxHash
instance Enum a => Hashable [a] where
hashWithMax :: Int -> [a] -> Int
hashWithMax Int
m = forall a. Enum a => Int -> [a] -> Int
h Int
0
where h :: Int -> [a] -> Int
h Int
a [] = Int
a
h Int
a (a
c:[a]
cs) = Int -> [a] -> Int
h ((Int
17forall a. Num a => a -> a -> a
*(forall a. Enum a => a -> Int
fromEnum a
c)forall a. Num a => a -> a -> a
+Int
19forall a. Num a => a -> a -> a
*Int
a)forall a. Integral a => a -> a -> a
`rem`Int
m) [a]
cs