--
-- Mocninne rady
--

-- soucet 1. n clenu mocninne rady
soucetn::(Num a,Ord a )=> [a] -> a -> a -> a

soucetn  []    _  _   = 0
soucetn  rada  n  x 
     |  n > 0         = soucet1 rada n x 1
     |  otherwise     = 0

soucet1::Num a => [a] -> a -> a -> a -> a

soucet1  []  _  _  _  = 0
soucet1  _   0  _  _  = 0
soucet1 (x:xs) n a a1 = a1*x + soucet1 xs (n-1) a (a*a1)

-- soucin 2 mocninnych rad
soucin::(Num a, Ord a ) => [a] -> [a] -> [a]

soucin rada1 rada2    = soucin1 1 rada1 rada2

soucin1::(Num a, Ord a ) => a -> [a] -> [a] -> [a]

soucin1 n rada1 rada2 = suma (mapzip (*) (take1 n rada1) (reverse (take1 n rada2)) ):
                            soucin1 (n+1) rada1 rada2

suma::Num a => [a] -> a

suma  []              = 0
suma  (x:xs)          = x + suma xs

mapzip:: ( a -> b -> c ) -> [a] -> [b] -> [c]

mapzip _ []  []       =  []
mapzip f (x:xs) (y:ys)=  x `f` y : mapzip f xs ys 

take1::(Num a, Ord a ) => a -> [a] -> [a]

take1 n (x:xs)
   |  n > 0           = x:take1 (n-1) xs
   |  otherwise       = []


-- n-ta derivace

deriv::(Num a, Ord a ) => [a] -> a -> [a]

deriv (x:xs)  n 
   | n < 0     = error "spatne cislo derivace"
   | n == 0    = (x:xs)
   | otherwise = deriv (deriv1 xs 1) (n-1)

deriv1::(Num a, Ord a )=> [a] -> a -> [a]

deriv1 (x:xs) n = n*x:(deriv1 xs (n+1))



--
-- Stromy
--


-- bin. strom

data Tree a = Nil | Node (Tree a ) a (Tree a )

-- vyhozeni intervalu < c, d >

vyhod::Ord a => Tree a -> a -> a -> Tree a 

is_nil Nil           = True
is_nil _             = False

vyhod  Nil   _   _   = Nil
vyhod  (Node left a right) c d
       | a < c        = Node vyhl a right
       | a > d        = Node left a vyhr
       | otherwise    = slep vyhl vyhr
       where vyhl = vyhod left c d
             vyhr = vyhod right c d

slep::Ord a => Tree a -> Tree a ->  Tree a 

slep left Nil    = left
slep Nil  right  = right
slep left right  = Node left1 a right
     where (left1, a) = najdi_max left

najdi_max (Node left a Nil)   = (left, a)
najdi_max (Node left a right) = ((Node left a right1), b)
     where (right1,b) = najdi_max right

-- vypis stromu

instance (Show a) => Show (Tree a) where
    show Nil    = "."
    show (Node left a right) = "(" ++ show left ++ " " ++ show a ++ " " 
                               ++ show right ++ ")" 


-- uzel A ~t B, pokud A nad B nebo B nad A (A v podstromu B nebo naopak) 
-- zjistit ekvivalenci 2 stromu (tj. vztahy vsech uzlu )

ekviv::Eq a => Tree a -> Tree a -> Bool

ekviv first second                  = ekviv1 first second && 
                                      ekviv1 second first
ekviv1::Eq a => Tree a -> Tree a -> Bool
ekviv1 Nil _                        = True
ekviv1 _ Nil                        = False
ekviv1 (Node left a right) second   = test_eq a (get_nodes (left) []) second &&
                                      test_eq a (get_nodes (right) []) second &&
                                      ekviv1 left second &&
                                      ekviv1 right second

get_nodes::Tree a -> [a] -> [a]
get_nodes Nil s                     = s
get_nodes (Node left a right)  s    = a:(get_nodes left (get_nodes right s))

test_eq::Eq a => a -> [a] -> Tree a -> Bool
test_eq  a [] _                     = True
test_eq  a (x:xs) second            = member1 a (path_to x second) ||
                                      member1 x (path_to a second) 

path_to::Eq a => a -> Tree a -> [a]
path_to  a Nil                      = []
path_to  a (Node left x right) 
    |  a == x                       = [a]
    |  is_empty path_left && 
       is_empty path_right          = []
    |  is_empty path_left           = x:path_right
    |  otherwise                    = x:path_left
   where path_left = path_to a left
         path_right = path_to a right

is_empty::[a] -> Bool
is_empty []                         = True
is_empty _                          = False

member1::Eq a => a -> [a] -> Bool
member1 a []                         = False
member1 a (x:xs)
    |  a == x                       = True
    |  otherwise                    = member1 a xs



-- seznam uzlu stromu ( setridene podle vzdalenosti od listu )

sezn_list::Tree a -> [a]
sezn_list Nil                       = []
sezn_list (Node left a right)       = map strip_sec (sort1 (strip_sec 
                                                   (sezn_l1 (Node left a right))) )
    where strip_sec = (\(x,y) -> x )

sezn_l1::Tree a -> ([(a,Int)],Int)
sezn_l1 Nil                         = ([],-1)
sezn_l1 (Node Nil   a Nil )         = ([(a,0)],0)
sezn_l1 (Node left a right)         = ((left_b ++ [(a, min_d)] ++ right_b ),min_d)
    where  (left_b,d1) = sezn_l1 left
           (right_b,d2)= sezn_l1 right
           min_d       = (min1 d1 d2) + 1

head1::[(a,Int)] -> Int
head1    []                         = -1
head1   ((_, d):_)                  = d

min1::Int -> Int -> Int
min1    (-1)  x                     = x
min1     x   (-1)                   = x
min1     x   y 
    |   x >  y                      = y
    |   otherwise                   = x


sort1   seznam                      -- bubble
    |   nahr  == 0                  = pruch_sez
    |   otherwise                   = sort1 pruch_sez
    where (pruch_sez, nahr) = sort_pruchod seznam 0

sort_pruchod [(a,x)]  nahr          = ( [(a,x)], nahr )
sort_pruchod ((a1,x1):(a2,x2):xs) nahr
    |   x1  >  x2                   = ( (a2,x2):setr_x1, nahrc_x1 ) --stable
    |   otherwise                   = ( (a1,x1):setr_x2, nahrc_x2 )
    where (setr_x1, nahrc_x1 ) = sort_pruchod ((a1,x1):xs) (nahr + 1)
          (setr_x2, nahrc_x2 ) = sort_pruchod ((a2,x2):xs) nahr




--
-- Klouzavy prumer
--


-- "seznam klouzavych prumeru"
-- prumer vzdy n prvku za sebou v seznamu delky s

klouz:: [Double] -> Double -> [Double]

klouz seznam n                      = klouz1 cut_sez seznam suma n
	where (cut_sez, suma) = stripn seznam n

stripn:: [Double] -> Double -> ([Double],Double)
stripn sezn 0                       = (sezn,0)
stripn (x:xs) i                     = (cut_sez, suma+x)
        where (cut_sez, suma) = stripn xs (i-1)

klouz1:: [Double] -> [Double] -> Double -> Double -> [Double]
klouz1 []     (x:xs) sum n          = [(sum / n)]
klouz1 (c:cs) (x:xs) sum n          = (sum / n):(klouz1 cs xs (sum+c-x) n )



--
-- Polynomy
--


-- nasobeni polynomu 

type Clen    = (Double,Int)
type Polynom = [Clen]

nasob::Polynom -> Polynom -> Polynom
nasob  []     _                     = []
nasob  (x:xs) yP                    = secti (nasob1 x yP ) (nasob xs yP)

nasob1::Clen -> Polynom -> Polynom
nasob1 _      []                    = []
nasob1 (xkoef,xmoc)((ykoef,ymoc):ys)= pricti (xkoef*ykoef,xmoc+ymoc) 
                                        (nasob1 (xkoef,xmoc) ys)

pricti::Clen -> Polynom -> Polynom
pricti c      []                    = [c]
pricti (xkoef,xmoc) yP@((ykoef,ymoc):ys)
   |  xmoc > ymoc                   = (xkoef,xmoc):yP
   |  xmoc==ymoc && xkoef/= -ykoef  = (xkoef+ykoef, xmoc):ys
   |  xmoc == ymoc                  = ys
   |  otherwise                     = (ykoef,ymoc):(pricti (xkoef,xmoc) ys)

secti::Polynom -> Polynom -> Polynom
secti  []     p                     = p
secti  p      []                    = p
secti  aP@((akoef,amoc):as) bP@((bkoef,bmoc):bs)           
   |  amoc > bmoc                   = (akoef,amoc):(secti as bP)
   |  amoc==bmoc && akoef /= -bkoef = (akoef+bkoef, amoc):(secti as bs)
   |  amoc == bmoc                  = (secti as bs )
   |  otherwise                     = (bkoef,bmoc):(secti bs aP)


-- deleni polynomu

vydel::Polynom -> Polynom -> Polynom
vydel xP    yP                      = reverse ((\(x,y) -> x)(vydel1 xP yP []))


zbytek::Polynom -> Polynom -> Polynom
zbytek xP    yP                     = (\(x,y) -> y)(vydel1 xP yP [])

vydel1::Polynom -> Polynom -> Polynom -> (Polynom,Polynom)
vydel1 []   _  c_vysl               = (c_vysl,[])
vydel1 xP@((xkoef,xmoc):xs) yP@((ykoef,ymoc):ys) c_vysl
   |  xmoc < ymoc                   = (c_vysl,xP)
   |  otherwise                     = vydel1 (odecti xP mezivysl) yP 
                                         (clen:c_vysl)
  where  clen     = (xkoef/ykoef, xmoc-ymoc)
         mezivysl = nasob1 clen yP

odecti::Polynom -> Polynom -> Polynom
odecti  x   y                       =  secti x neg_y
  where neg_y = map (\(x,y) -> (-x,y) ) y

-- hodnota polynomu v bode

hodnota::Polynom -> Double -> Double

hodnota []    _                     = 0
hodnota ((ai,koefi):pols)   x       = (ai * x^koefi ) + hodnota pols x


--
-- Pascaluv trojuhelnik
--

-- pascaluv trojuhelnik:

iterate1::(a->a) -> a -> [a] 
iterate1 f x                        = x :iterate1 f ( f x )

pascal                              = iterate1 next_row [1]
    where  next_row x               = mapzip (+) (0:x) (x++[0])



--
-- Kruskaluv algoritmus hledani min. kostry
--

-- kruskal

type Hrana  = (Int,Int,Int)
type Vrchol = (Int,Int)


kruskal graf                        = kruskal1 (getvrch graf [] 0 ) graf


getvrch  []   mn  _                 = mn
getvrch  ((v1,v2,w):es) mn  komp
    | (clen_v v1 mn) &&(clen_v v2 mn) = getvrch es mn komp
    | (clen_v v1 mn)                  = getvrch es ((v2,komp):mn) (komp+1)
    | (clen_v v2 mn)                  = getvrch es ((v1,komp):mn) (komp+1)
    | otherwise                       = getvrch es ((v1,komp):(v2,(komp+1)):mn) (komp+2)

clen_v  x []                          = False
clen_v  x    ((y,k):ys)              
    | y == x                        = True
    | otherwise                     = clen_v x ys

kruskal1 vrch []                    = []
kruskal1 vrch graf
        | x_komp == y_komp          = kruskal1 vrch graf1
        | otherwise                 = (x,y):kruskal1 (slijk vrch x_komp y_komp) graf1
        where (x,y,_)     = najdi_min_hranu graf
              graf1       = vyhod_hranu (x,y) graf
              x_komp      = get_komp vrch x
              y_komp      = get_komp vrch y

--je_jedna_komp  [(_,_)]              = True
--je_jedna_komp  ((x,xk):(y,yk):xs)             
--    |  xk == yk                     = je_jedna_komp ((y,yk):xs)
--    |  otherwise                    = false

najdi_min_hranu [(x,y,w)]           = (x,y,w)
najdi_min_hranu ((x1,y1,w1):xs)
    | w1 < w2                       = (x1,y1,w1)
    | otherwise                     = (x2,y2,w2)
    where (x2,y2,w2) = najdi_min_hranu  xs

vyhod_hranu (x,y) []                = []
vyhod_hranu (x,y) ((x0,y0,w0):xs)
    | x == x0 && y == y0            = xs
    | otherwise                     = (x0,y0,w0):(vyhod_hranu (x,y) xs)

get_komp  ((x1,k1):xs) x
    | x == x1                       = k1
    | otherwise                     = get_komp xs x


slijk  [] _ _                       = []
slijk  ((x,k):xs) k1 k2
    |  k == k2                      = (x,k1):(slijk xs k1 k2)
    |  otherwise                    = (x,k):(slijk xs k1 k2 )