!-----------------------------------------------------------------------!
!   A program to calculate an european put option using a binomial tree
!   Taken orignally from Hull (page 346)
!
!
! formulas used:
!        u = 1 / d
!        a = exp(r*\delta t)
!        p = (a-d)/(u-d)
!        u = exp(\sigma*sqrt(\delta t) 
!        d = exp(-\sigma*sqrt(\delta t) 
!-----------------------------------------------------------------------!
module bitree
   type tree
      real*8,dimension(:),pointer :: t
   end type tree
end module bitree


program btree 
use bitree
implicit none

real*8                                     :: SIGMA, S, X, T, R
integer                                    :: n ! n=  total number of intervals 
type(tree),dimension(:),save,allocatable   :: f,stock

integer                                    :: i,j
real*8                                     :: u,a,d,p,delt,ert

interface
   subroutine bin(stock,f,n)
   use bitree
   implicit none
   integer                  :: n
   type(tree),dimension(:)  :: f,stock
   end subroutine bin
end interface




   open(20,file='american.in')
   read(20,*) S
   read(20,*) X
   read(20,*) R
   read(20,*) T
   read(20,*) SIGMA 
   read(20,*) n
   close(20)

   allocate(f(0:n),stock(0:n))
   do i = 0 , n
      allocate(f(i)%t(0:n))
      allocate(stock(i)%t(0:n))
   end do

   delt = T/n
   u = exp(sigma*sqrt(delt))
   d = exp(-sigma*sqrt(delt))
   a = exp(R*delt)
   p = (a-d)/(u-d)
   ert = exp(-R*delt)

! now loop on the tree
   do i = n , 0, -1
      do j = 0, i
          stock(i)%t(j) = S*u**j * d**(i-j)
      end do
   end do

! now calculate the option prices
   do i = n , 0, -1
      do j = 0, i
         if (i.eq.n) then
            f(i)%t(j) = max(X-stock(i)%t(j),0)
         else
            f(i)%t(j) =  ert*(p*f(i+1)%t(j+1) + (1-p)*f(i+1)%t(j) )
         end if

      end do
   end do

   open(66,file='tree_euro.out')
   i = 0
   j = 0
	write(6,*) i,j,stock(i)%t(j),f(i)%t(j)
   do i = 0 , n 
      do j = i, 0, -1
         write(66,100) i,j,stock(i)%t(j),f(i)%t(j)
      end do
      write(66,*)
   end do
   close(66)

80 format(8f.2)


! what about binning these stock prices and option prices?

	call bin(stock,f,n)

100  format(2i3,2f7.2)

stop
end

subroutine bin(stock,f,n)
use bitree
implicit none
integer                  :: n
type(tree),dimension(:)  :: f,stock
real*8                   :: mins,maxs,sums
real*8                   :: minf,maxf,sumf
integer                  :: i,j
min = 99.99d99
max =-99.99d99
   do i = n , 0, -1
      do j = 0, i
			if (f(i)%t(j).le.minf)) minf= f(i)%t(j)               
			if (stock(i)%t(j).le.mins)) mins= stock(i)%t(j)        

		end do
	end do


return
end
