content: --module Aux 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)
  
  