module Auxil where
import Key
data Key = K String Char Char Int {- String, end letters, length of string -}
data HashSet = H (Maybe Int) (Maybe Int) [Int]
type HashFun = [(Char,Int)] {- Association list of Character to values -}
--1.3:data Maybe a = Nothing | Just a deriving Text
ends :: Key -> String
ends (K _ a z _) = [a,z]
morefreq :: Key -> Key -> Bool
morefreq (K _ a x _) (K _ b y _) = freq a + freq x > freq b + freq y
freq :: Char -> Int
freq c = assoc c freqtab
assoc :: (Eq a) => a -> [(a,b)] -> b
assoc x ((y,z):yzs) = if x == y then z else assoc x yzs
assocm :: (Eq a) => a -> [(a,b)] -> Maybe b
assocm x [] = Nothing
assocm x ((y,z):yzs) = if x == y then Just z else assocm x yzs
freqtab :: [(Char, Int)]
freqtab = histo (concat (map ends attribkeys))
histo :: (Eq a) => [a] -> [(a,Int)]
histo = foldr histins []
where
histins x [] = [(x,1)]
histins x (yn@(y,n):yns) = if x==y then (y,n+1):yns
else yn:histins x yns
maxval :: Int
maxval = length (freqtab)
subset :: (Eq a) => [a] -> [a] -> Bool
subset xs ys = all (\x -> member x ys) xs
--partain: in the prelude
--all :: (a->Bool) -> [a] -> Bool
--all p = foldr (\x -> \b ->(p x && b)) True
union :: (Eq a) => [a] -> [a] -> [a]
union xs ys = xs ++ [y | y <- ys, not (member y xs)]
attribkeys :: [Key]
attribkeys = map (\k->(K k (head k) (last k) (length k))) keys
hinsert :: Int -> HashSet -> Maybe HashSet
hinsert h (H lo hi hs) =
if member h hs || 1 + hi'- lo' > numberofkeys then Nothing
else Just (H (Just lo') (Just hi') (h:hs))
where
lo' = minm lo h
hi' = maxm hi h
minm, maxm :: Maybe Int -> Int -> Int
minm Nothing y = y
minm (Just x) y = min x y
maxm Nothing y = y
maxm (Just x) y = max x y
member :: (Eq a) => a -> [a] -> Bool
member _ [] = False
member x (y:ys) = x == y || member x ys
hash :: HashFun -> Key -> Int
hash cvs (K _ a z n) = n + assoc a cvs + assoc z cvs
numberofkeys :: Int
numberofkeys = length keys
partition' :: (a->Bool) -> [a] -> ([a],[a])
partition' p = foldr select ([],[])
where select x (ts,fs) | p x = (x:ts,fs)
| otherwise = (ts,x:fs)
freqsorted :: [Key] -> [Key]
freqsorted =
\x->x
{-foldr freqins []
where
freqins x [] = [x]
freqins x (y:ys) = if morefreq x y then x:y:ys else y:freqins x ys-}
blocked :: [Key] -> [Key]
blocked = blocked' []
blocked' ds [] = []
blocked' ds (k : ks) = k : det ++ blocked' ds' rest
where
(det,rest) = partition' (\x->subset (ends x) ds') ks
ds' = union ds (ends k)
|