using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Data.SqlClient;
using System.Drawing;
using System.IO;
using System.Text;
using System.Threading;
using System.Windows.Forms;
using skmDataStructures.Graph;

namespace TrafficMan
{
    public partial class frmTrafficMan : Form
    {
        Graph virginia = new Graph();
        private Hashtable Dist = new Hashtable();
        private Hashtable Route = new Hashtable();
        int mincount = 0;
        int mintime = 0;
        string start;
        string end;

        private intersect[] intersectionList = new intersect[4];

        public frmTrafficMan()
        {
            InitializeComponent();
        }

        private struct intersect
        {
            public string intersectId;
            public string intersectName;
        }

        private void frmTrafficMan_Load(object sender, EventArgs e)
        {
            intersectionList[0].intersectId = "32012";
            intersectionList[0].intersectName = "Rolling Green";
            intersectionList[1].intersectId = "5402";
            intersectionList[1].intersectName = "Woodland Park";
            intersectionList[2].intersectId = "10230";
            intersectionList[2].intersectName = "Fairview Park Dr.";
            intersectionList[3].intersectId = "45206";
            intersectionList[3].intersectName = "Ridge Heights";
            intersectionList[4].intersectId = "45206";
            intersectionList[4].intersectName = "Ridge Heights";

            btnRun.Enabled = false;
            btnCancel.Enabled = true;
            bwLoadPoints.RunWorkerAsync();
            reloadListBox(false);
        }

        private void worker_DoWork(object sender, DoWorkEventArgs e)
        {
            BackgroundWorker worker = (BackgroundWorker)sender;

            //loads data from sql into graph nodes
            virginia.Clear();
            Dist.Clear();
            Route.Clear();

            // get data from ms sql
            SqlConnection myConnection = new SqlConnection("user id=tiger;" +
                                       "password=tiger;server=computername\\SQLEXPRESS;" +
                                       "Trusted_Connection=yes;" +
                                       "database=tiger; " +
                                       "connection timeout=5");
            try
            {
                myConnection.Open();
            }
            catch (Exception ex)
            {
                MessageBox.Show("There was an exception: " + ex.Message);
            }

            try
            {
                int total = 0;
                SqlDataReader myReader = null;
                SqlCommand myCommand2 = new SqlCommand("SELECT COUNT(*) AS cnt FROM links", myConnection);
                myReader = myCommand2.ExecuteReader();

                while (myReader.Read())
                {
                    total = (int)myReader["cnt"];
                }
                myReader.Close();

                if (rbSpeedLimit.Checked)
                {
                    SqlCommand myCommand = new SqlCommand("SELECT intersectionId1, intersectionId2, time FROM links", myConnection);
                }
                myReader = myCommand.ExecuteReader();

                int count = 0;

                while (myReader.Read())
                {
                    // get values from sql
                    String intersectionId1 = myReader["intersectionId1"].ToString();
                    String intersectionId2 = myReader["intersectionId2"].ToString();
                    int time = (int)myReader["time"];

                    // add values to nodes
                    if (!virginia.Contains(intersectionId1))
                        virginia.AddNode(new Node(intersectionId1, null));
                    if ( !virginia.Contains(intersectionId2))
                        virginia.AddNode(new Node(intersectionId2, null));
                    virginia.AddUndirectedEdge(intersectionId1, intersectionId2, time);

                    //
                    if (count % 10000 == 0)
                    {
                        if (worker.CancellationPending)
                        {
                            e.Cancel = true;
                            break;
                        }
                        else
                        {
                            worker.ReportProgress((int)count * 100 / total);
                        }
                    }

                    count++;
                }
                e.Result = total;
                myReader.Close();
            }
            catch (Exception ex)
            {
                MessageBox.Show("There was an exception(2)" + ex.Message);
            }
            myConnection.Close();
        }

        private void reloadListBox(bool sql)
        {
            if (sql == false)
            {
                for (int a = 0; a < intersectionList.GetLength(0); a++)
                {
                    lbStart.Items.Add(intersectionList[a].intersectName);
                    lbEnd.Items.Add(intersectionList[a].intersectName);
                }
            }
            else
            {
                reloadListBox();
            }
        }

        private void reloadListBox()
        {
            // reload the combo boxes
            lbStart.Items.Clear();
            lbEnd.Items.Clear();

            foreach (Node n in virginia.Nodes)
            {
                lbStart.Items.Add(n.Key);
                lbEnd.Items.Add(n.Key);
            }

            if (lbStart.Items.Count > 0)
                lbStart.SelectedIndex = 0;
            if (lbEnd.Items.Count > 1)
                lbEnd.SelectedIndex = 1;
            else if (lbEnd.Items.Count > 0)
                lbEnd.SelectedIndex = 0;
        }

        private string getIntersectionID(String name)
        {
            for (int a = 0; a < intersectionList.GetLength(0); a++)
            {
                if (intersectionList[a].intersectName == name)
                    return intersectionList[a].intersectId;
            }
            return null;
        }

        private void writeRoute(Hashtable route, String start, String end, String filename)
        {
            Stack traceBackSteps = new Stack();
            Node current = new Node(end, null);
            Node prev = null;

            if (File.Exists(filename))
                File.Delete(filename);

            do
            { 
                prev = current;
                current = (Node)route[current.Key];

                String[] coord = getLatLong(current.Key);

                String temp = coord[0] + "," + coord[1];
                traceBackSteps.Push(temp);                

            } while (current.Key != start);

            StreamWriter sw = new StreamWriter(filename);
            while (traceBackSteps.Count > 0)
                sw.WriteLine((string)traceBackSteps.Pop());

            sw.Close();
        }

        private void InitDistRouteTables(String start, ref Hashtable dist, ref Hashtable route)
        {
            // set the initial distance and route for each city in the graph
            int total = virginia.Nodes.Count;
            foreach (Node n in virginia.Nodes)
            {
                //if (dist.Contains(n.Key))
                  //  dist[n.Key] = Int32.MaxValue;
                //else
                dist.Add(n.Key, Int32.MaxValue);

                //if (route.Contains(n.Key))
                //    route[n.Key] = null;
                //else
                route.Add(n.Key, null);
            }

            // set the initial distance of start to 0
            dist[start] = 0;
        }

        /// <summary>
        /// Relaxes the edge from the Node uCity to vCity.
        /// </summary>
        /// <param name="cost">The distance between uCity and vCity.</param>
        private void Relax(Node minNode, Node minNodeNeighbors, int cost, ref Hashtable dist, ref Hashtable route)
        //private void Relax(Node minNode, Node minNodeNeighbors, int cost, ref Hashtable dist, ref Hashtable route)
        {
            int distTouCity = (int)dist[minNode.Key];
            int distTovCity = (int)dist[minNodeNeighbors.Key];

            if (distTovCity > distTouCity + cost)
            {
                // update distance and route
                dist[minNodeNeighbors.Key] = distTouCity + cost;
                route[minNodeNeighbors.Key] = minNode;
            }
        }

        /// <summary>
        /// Retrieves the Node from the passed-in NodeList that has the <i>smallest</i> value in the distance table.
        /// </summary>
        /// <remarks>This method of grabbing the smallest Node gives Dijkstra's Algorithm a running time of
        /// O(<i>n</i><sup>2</sup>), where <i>n</i> is the number of nodes in the graph.  A better approach is to
        /// use a <i>priority queue</i> data structure to store the nodes, rather than an array.  Using a priority queue
        /// will improve Dijkstra's running time to O(E lg <i>n</i>), where E is the number of edges.  This approach is
        /// preferred for sparse graphs.  For more information on this, consult the README included in the download.</remarks>
        private Node GetMin(NodeList nodes, Hashtable dist, String end)
        {
            // find the node in nodes with the smallest distance value
            int minDist = Int32.MaxValue;
            Node minNode = null;
            foreach (Node n in nodes)
            {
                if (((int)dist[n.Key]) <= minDist)
                {
                    minDist = (int)dist[n.Key];
                    minNode = n;
                }
            }

            return minNode;
        }

        private void btnRun_Click(object sender, EventArgs e)
        {
            lblStatus.Text = "In progress...";
            DateTime currentSystemTime = DateTime.Now;
            shortestPath();
            TimeSpan diff = DateTime.Now.Subtract(currentSystemTime);
            lblStatus.Text = "Complete";
            double avgtime = diff.TotalMilliseconds / mincount;
            avgtime = Math.Round(avgtime, 3);
            MessageBox.Show("Total time or distance: " + Dist[end] + ". Execution time: " + diff.ToString() + " seconds. " + mincount + " iterations.  Average time: " + avgtime + " milliseconds.");
        }

        private String[] getLatLong(String intersectionID)
        {
            String[] ret = new String[2];

            SqlConnection myConnection = new SqlConnection("user id=tiger;" +
                                       "password=tiger;server=computername\\SQLEXPRESS;" +
                                       "Trusted_Connection=yes;" +
                                       "database=tiger; " +
                                       "connection timeout=5");
            try
            {
                myConnection.Open();
            }
            catch (Exception e)
            {
                MessageBox.Show("Error getting lat/long: " + e.Message);
            }

            SqlDataReader myReader = null; 
            SqlCommand myCommand = new SqlCommand("SELECT TOP 1 lat/1000000.0 AS lat, long/1000000.0 AS lon FROM intersections WHERE intersectionId = " + intersectionID, myConnection);
            myReader = myCommand.ExecuteReader();
            while (myReader.Read())
            {
                ret[0] = myReader["lat"].ToString();
                ret[1] = myReader["lon"].ToString();
                myReader.Close();
                myConnection.Close();
                return ret;
            }
            myReader.Close();
            myConnection.Close();
            return null;
        }

        private void worker_ProgressChanged(object sender, ProgressChangedEventArgs e)
        {
            pbStatus.Value = e.ProgressPercentage;
        }

        private void worker_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
        {
            if (e.Error != null)
                MessageBox.Show( this, "Background processing completed with errors: " + e.Error.Message, "ERROR!");
            else if (e.Cancelled)
            {
                lblPoints.Text = null;
                pbStatus.Value = 0;
            }
            else
            {
                lblPoints.Text = e.Result.ToString();
                pbStatus.Value = 0;
            }
            btnRun.Enabled = true;
            btnCancel.Enabled = false;
        }

        private void btnCancel_Click(object sender, EventArgs e)
        {
            // Cancel asynchronous processing
            if (bwLoadPoints.IsBusy)
                bwLoadPoints.CancelAsync();

            if (bwShortestPath.IsBusy)
                bwShortestPath.CancelAsync();
        }

        private void bwShortestPath_DoWork(object sender, DoWorkEventArgs e)
        {

        }

        private void shortestPath()
        {
            start = getIntersectionID(lbStart.Text);
            end = getIntersectionID(lbEnd.Text);

            InitDistRouteTables(start, ref Dist, ref Route);		// initialize the route & distance tables

            NodeList startNodes = virginia.Nodes;	// nodes == Q

            int total = new int();
            total = startNodes.Count;

            bool done = false;

            /**** START DIJKSTRA ****/
            while (done == false)
            {
                DateTime currenttime = DateTime.Now;
                Node u = GetMin(startNodes, Dist, end);		// get the minimum node
                TimeSpan diff = DateTime.Now.Subtract(currenttime);
                mintime =+ diff.Milliseconds;
                mincount++;

                Dist.Remove(u.Key);
                startNodes.Remove(u);			// remove it from the set Q

                // iterate through all of u's neighbors
                foreach(EdgeToNeighbor edge in u.Neighbors)
		{
		    Relax(u, edge.Neighbor, edge.Cost); // relax each edge

                    if (startEdge.Neighbor.Key == end) // if this is the last node, end process
                        done = true;
                }

                if (startNodes.Count == 0) // end after runs out of nodes
                    done = true;

            }	// repeat until Q is empty
            /**** END DIJKSTRA ****/

            // write file
            writeRoute(Route, start, end, "c:\\route.csv");
        }
    }
}