using System;
using System.Collections.Generic;
using System.Text;

namespace BinomialTrees
{
    class Program
    {
        /// <summary>
        /// Performs binomial trees and gives euro+american call+puts
        /// </summary>
        /// <param name="S">Initial Stock price</param>
        /// <param name="X">Strike Price</param>
        /// <param name="r">Annual Interest Rate</param>
        /// <param name="sigma">Annual Volatility</param>
        /// <param name="N">Number of time steps</param>
        /// <param name="T">Time to maturity in Annual</param>
        /// <param name="dt">Time Step in Annual</param>
        /// <returns></returns>
        static BinomialResult BinomialTrees(double S, double X, double r, double sigma, int N, double T )
        {
            Console.WriteLine( "Called with S={0}, X={1}, r={2}, sigma={3} N={4}, T={5}", S, X, r, sigma, N, T );

            ///the time step
            ///bare in mind most of the attributes are in annual, this is OK because the formulas
            ///multiply them by the time step
            double dt = T / N;

            ///we have a list of lists, the inner list contains BinomialNodes, these represent nodes in the tree
            ///the outer list represents time steps, we do this rather than using a graph structure because fu is
            ///simply the same node index in the next time step list, and fd is index+1 -- simple!
            List<List<BinomialNode>> TimeSteps = new List<List<BinomialNode>>();

			///we add one onto N, this is because the tree includes NOW as a time step
			N+=1;

            ///create the binomial tree structure with 2 nested nested for loops
            for (int n = 1; n < N + 1; n++)
            {
                ///this is the list of nodes for this time step
                List<BinomialNode> timestep = new List<BinomialNode>();

                for (int b = 0; b < n; b++)
                {
                    timestep.Add(new BinomialNode());
                }

                TimeSteps.Add(timestep);
            }

            ///calculate p,u,d
            double d = Math.Exp(-sigma * Math.Sqrt(dt));
            double u = Math.Exp(sigma * Math.Sqrt(dt));
            double p = (Math.Exp(r * dt) - d) / (u - d);

            ///start at the right hand side of the tree and work backwards
            ///n is ONE based
            for (int n = N; n > 0; n--)
            {
                ///get the list of nodes for this depth
                List<BinomialNode> nodes_timestep = TimeSteps[n - 1];

                ///work down through each node, top to bottom
                for (int l = 0; l < nodes_timestep.Count; l++)
                {
                    ///get a reference to the node we are working on
                    BinomialNode node = nodes_timestep[l];

                    ///calculate the "stock" price for this node by applying Us and Ds
                    int factor = (n - 1) - (l * 2);
                    node.StockPrice = S * Math.Pow(factor > 0 ? u : d, Math.Abs(factor));

                    ///calculate the intrinsic values for nodes, both for call and put
                    node.CallIntrinsicValue = Math.Max(0, node.StockPrice - X);
                    node.PutIntrinsicValue = Math.Max(0, X - node.StockPrice);

                    ///if we are on the lastg column, we set the option values to be the intrinsic
                    ///vales, this is so our right-referencing option prices can start as they mean to go on, right-to-left
                    if (n == N)
                    {
                        node.EuropeanCallOptionValue = node.CallIntrinsicValue;
                        node.EuropeanPutOptionValue = node.PutIntrinsicValue;
                    }

					
                    ////calculate option prices
                    ///if it is not the last row, then we start to calculate the option prices using the "f" formula
                    ///remember we are working across the tree from right to left
                    if (n < N)
                    {
                        node.EuropeanCallOptionValue
                            = Math.Exp(-r * dt) *
                                (p * TimeSteps[n][l].EuropeanCallOptionValue + ((1 - p)
                                * TimeSteps[n][l + 1].EuropeanCallOptionValue));

                        node.EuropeanPutOptionValue
                            = Math.Exp(-r * dt) *
                                (p * TimeSteps[n][l].EuropeanPutOptionValue + (1 - p)
                                * TimeSteps[n][l + 1].EuropeanPutOptionValue);

                        node.AmericanCallOptionValue = Math.Max(node.CallIntrinsicValue, node.EuropeanCallOptionValue);
                        node.AmericanPutOptionValue = Math.Max(node.PutIntrinsicValue, node.AmericanPutOptionValue);
                    }
                }
            }

            BinomialNode root = TimeSteps[0][0];

            return new BinomialResult{ RootNode=root, D=d, U=u, P=p, dt=dt };
        }

        static void Main(string[] args)
        {
            ///now write out the results

            BinomialResult result = BinomialTrees(100, 90, 0.05f, 0.318d, 60, 1d/6);

            Console.WriteLine("Details: p={0}, u={1}, d={2}, dt={3}", result.P, result.U, result.D, result.dt );

            Console.WriteLine("EuropeanCallOptionValue: {0}", result.RootNode.EuropeanCallOptionValue);
            Console.WriteLine("EuropeanPutOptionValue: {0}", result.RootNode.EuropeanPutOptionValue);
            Console.WriteLine("AmericanCallOptionValue: {0}", result.RootNode.AmericanCallOptionValue);
            Console.WriteLine("AmericanPutOptionValue: {0}", result.RootNode.AmericanPutOptionValue);
        }
    }

    public struct BinomialResult
    {
        public BinomialNode RootNode;
        public double P;
        public double U;
        public double D;
        public double dt;
    }

    public class BinomialNode
    {
        public double StockPrice;
        public double CallIntrinsicValue;
        public double PutIntrinsicValue;
        public double EuropeanCallOptionValue;
        public double EuropeanPutOptionValue;
        public double AmericanCallOptionValue;
        public double AmericanPutOptionValue;
    }
}