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

namespace Huopahattu.Reittihaku
{
    class Program
    {
        /// <summary>
        /// Esimerkki koodi Reittihaun käyttämiseksi
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            //Luodaan reittihaku olio
            Reittihaku rh = new Reittihaku();
            //Asetetaan reittihaulle olio,
            //jolta reittihaku saa tietää polut haluamastaa risteyspisteestä
            rh.kartta = new Kartta();
            //Polkuja joihin voidaan mennä voi olla useita, mutta
            //jokaisesta risteyspisteestä neuvotaan reitti vain lyhyimmän
            //ajan päässä olevaa risteyspisteeseen. Tälläinen tilanne voisi olla,
            //kun halutaan vesisateelta karkuun nopeiten jonkun puun alle, niin
            //listattaisiin kaikki puut joiden alle voi mennä sateelta suojaan.
            //Yleensä reittihaussa tiedetään kohde jonne halutaan ja sen risteyspisteen polut
            //lisätään.
            rh.LisaaPolkuja(1);
            rh.LisaaPolkuja(3);
            //Käynnisteään ratkaisija
            rh.Ratkaise();
            //Tulostetaan saatu tieto
            for (int i = 1; i <= 6; i++)
            {
                //Kartassa tiedetään nyt olevan pisteen 1-6, joiden tunniste on integer tyyppiä
                //,niin risteyspisteen tiedot saadaaan for silmukalla, jonka incrementti annetaan
                //parametrina EtsiRisteys-metodille.
                Risteys r = rh.EtsiRisteys(i);
                //Seuraavaksi tulostetaan Risteyspisteen tiedot, eli omaID on se tunniste, jolla risteys
                //Kartasta löytyy. aika on se aika joka menee mentäessä lähimpää risteys pisteeseen.
                //tuloID on sen risteyspisteen tunniste, jonka suuntaan on mentävä, että päästään kohteeseen.
                //myös tuloID on tunnoste, jolla kartta tietää tuon risteyspisteen.
                Console.WriteLine("Risteyksessä:{0} lähdostä {1} tuloSuunta:{2}", r.omaID, r.aika,r.tuloID);
            }
            //Estetään komentokehotteen välähdys, pyytämäkkä napin painallus.
            object o = Console.ReadKey();


        }
    } //esimerkki luokalle

    /// <summary>
    /// Reittihaku luokalla etsitään nopein reitti haluttuun tai lähimpää mahdolliseen pisteeseen.
    /// </summary>
    class Reittihaku
    {
        /// <summary>
        /// kulkemattomatPolut sisältää polkujen tiedot listassa, jotka on nähty, mutta
        /// niitä pitkin ei ole vielä kuljettu.
        /// </summary>
        protected List<Polku> kulkemattomatPolut;
        /// <summary>
        /// kartta muuttuja toteuttaa IKartta rajapinnan. Tämän avulla saadaan tietää
        /// polut halutusta risteyskohdasta.
        /// </summary>
        public IKartta kartta;
        /// <summary>
        /// risteykset on järjestettylista risteyksistä joissa on käyty.
        /// Tähän listaan tallennetaan Risteysoliot, joissa on tiedot risteyksiin
        /// tulo ajasta ja suunnasta.
        /// </summary>
        protected SortedList<object, Risteys> risteykset;

        /// <summary>
        /// Reittihaun rakentajassa luodaan listat. Parametreja tämä ei oteta vastaan. Tarvittavat
        /// ulkoiset arvot voidaan antaa julkisiin muuttujiin. Tähän voi olla tarvetta tehdä muutos
        /// parantaaksi luokan turvallisuutta.
        /// </summary>
        public Reittihaku()
        {
            this.kulkemattomatPolut = new List<Polku>();
            this.risteykset = new SortedList<object, Risteys>();
        }

        /// <summary>
        /// LisaaPolkuja metodi pyytää halutusta risteyspisteestä näkyvät polut kartta oliolta.
        /// </summary>
        /// <param name="mista"></param>
        public void LisaaPolkuja(object mista)
        {
            foreach (Polku p in this.kartta.polut(mista))
            {
                // Console.WriteLine("Polku {0}, {1} ja {2}", p.lahtoPaikka,
                //    p.maaranpaaPaikka, p.aika);
                this.kulkemattomatPolut.Add(p);
            }
            this.EtsiRisteys(mista).aika = 0;
        }

        /// <summary>
        /// EtsiNopeinJaPoista käy läpi kaikki nähdyt polut joita pitkin ei olla kuljettu.
        /// Jokaiselle polulle on tallennettu aika mikä on kulunut kuljettaessa polun päähän,
        /// jostain niistä risteyspisteistä joita on kerrottu LisääPolkuja-metodilla.
        /// </summary>
        /// <returns>Palauttaa sen polun, jonka määränpäähän kulkemiseen menee vähiten aikaa.
        /// Huom., että aikaan on lisätty matkaaika, joka on kulunut ennenkuin kyseinen polku
        /// on löydetty.</returns>
        protected Polku EtsiNopeinJaPoista()
        {
            //aika muuttujaan tallennetaan nopeimman polun aika. Alustetaan aluksi maksimi
            //arvoo, jotta listassa olevat polut alittavat sen varmasti
            double aika = double.MaxValue;
            //nopein muuttujaan tallennetaan viite Polku olioon, joka on nopein
            Polku nopein = new Polku(new object(),new object(),double.MaxValue);
            //Käydään läpi kaikki polut, jotka ovat listassa kulkemattomatPolut
            //Kyseisessä listassa on ne polut jotka on nähty jostain tunnetusta
            //risteyspisteestä, mutta ei ole vielä kuljettu sitä pitkin.
            foreach(Polku p in this.kulkemattomatPolut)
            {
                if (aika >= p.aika)
                {
                    aika = p.aika;
                    nopein = p;
                }
            }
            //Seuraavaksi poistetaan nopein polku listasta, koska luultavasti
            //tätä metodia kutsuvassa koodissa on tarkoitus kulkea löydettyä polkua
            //pitkin.
            this.kulkemattomatPolut.Remove(nopein);
            //Palautetaan nopeimman polun tiedot
            return nopein;
        }
        /// <summary>
        /// Ratkaisee annetun kartan. Muista antaa polut,
        /// joita pitkin on mahdollista lähteä liikkeelle.
        /// Polut annetaan LisaaPolkuja metodila.
        /// </summary>
        public void Ratkaise()
        {
            Polku polku;
            Risteys kohde;
           
            while (this.kulkemattomatPolut.Count > 0)
            {
                //Etsitään 'nopein' polku, jonne seuraavaksi mennään
                //Poistetaan 'nopein' polku listasta samalla
                polku = this.EtsiNopeinJaPoista();
                //Console.WriteLine("Nopein polku {0}, {1} ja {2}", polku.lahtoPaikka, polku.maaranpaaPaikka, polku.aika);
                //Etsitään kohteen tiedot
                kohde = this.EtsiRisteys(polku.maaranpaaPaikka);
                //Tarkistetaan, että koteeseen ei ole nopeampaa reittiä tiedossa
                double aikaPerilla = polku.aika;
                //Console.WriteLine("Vertaa {0}<{1}", aikaPerilla, kohde.aika);
                if(aikaPerilla < kohde.aika)
                {
                    //Kerrotaan kohteelle kuinka kau'an sinne matka kestää
                   
                    kohde.aika = aikaPerilla;
                    //Kerrotaan minne suuntaan kohteesta on lähdettä mentäessä nollaa kohden
                    kohde.tuloID = polku.lahtoPaikka;
                    //Lisätään kulkemattomiinPolkuihin kohteesta lähtevät polut
                    foreach(Polku p in this.kartta.polut(kohde.omaID))
                    {
                        p.aika+=aikaPerilla;
                        //Console.WriteLine("Polku {0}, {1} ja {2}", p.lahtoPaikka, p.maaranpaaPaikka, p.aika);
                        this.kulkemattomatPolut.Add(p);
                    }
                }
            }
        }

        /// <summary>
        /// Antaa parametrina välitetyn tunnisteen perusteella risteyksen,
        /// jossa risteyksen tiedot tuloaika ja tulosuunta selviää.
        /// </summary>
        /// <param name="o">tunniste olio, jolla risteyspiste tunnistetaan kartta oliossa,
        /// jotta tämä tietää kertoa kyseisetä risteyspisteestä lähtevät polut. Risteys-metodi
        /// käyttää tunniste oliota risteystietojen tunnisteena, jonka EtsiRisteys-metodi palauttaa</param>
        /// <returns></returns>
        public Risteys EtsiRisteys(object o)
        {
            //Tarkistetaan onko risteys listassa
            if (this.risteykset.ContainsKey(o))
            {
                //listasta risteykset löytyy risteys, jolla kyseinen olio on tunnisteena
                //joten palautetaan se.
                return this.risteykset[o];
            }
            else
            {
                //Risteyspiste on uusi sitä ei löytynyt tunnettujen risteysten listalta, joten
                //lisätään se listaan ja palautetaan se.
                Risteys r = new Risteys(o);
                this.risteykset.Add(o, r);
                return r;
            }
        }
    } //reittihaku luokalle

    /// <summary>
    /// Risteys luokka sisältää tiedot siitä kuinka pitkä aika
    /// on kulunut tultaessa nopeinta reitti ajallisiste lyhimmästä laskennan
    /// aloitus kohdasta, joita reittihaussa kerrotaan LisääPolkuja-metodilla
    /// </summary>
    class Risteys
    {
        /// <summary>
        /// aika muuttujaan tallennetaan aika, joku risteykseen löytämiseen
        /// on kulunut. aika on double tyyppiä, jotta ajan voi esittää tarkasti
        /// desimaaleja käyttäen.
        /// </summary>
        public double aika;
        /// <summary>
        /// tuloID on risteyspisteen tulosuunnassa olevan risteyspisteen tunniste, jolla
        /// sijainti kartta oliossa tunnistetaan. tuloID:hen tallennettu olio voi olla esim.
        /// pelilaudaan ruudun olio tai string tyypin nimi tai vaikka numeerinen int tyypin arvo.
        /// </summary>
        public object tuloID;
        /// <summary>
        /// omaID on risteyspisteen oma tunniste, jolla piste tunnistetaan kartta oliossa.
        /// </summary>
        public object omaID;
        /// <summary>
        /// Risteyksen rakentaja ottaa vastaan parametrina tunniste olion, jolla kartta oliossa
        /// kyseinen risteyspiste voidaan tunnistaa. Tunniste otetaan rakentajassa, jotta sitä
        /// ei voi myöhemmin vahingossa vaihtaa. aika muuttujalle asetetaan oletuksena maksimi arvo,
        /// tätä tietoa voidaan käyttää reittihaussa tarkistamiseen onko risteys oikeasti löydetty,
        /// jolloin aika on luultavasti pienempi, kuin maksimi.
        /// </summary>
        /// <param name="omaID">Tunniste olio/rakenne, jolla kartta ja reittihaku
        /// tunnistaa pisteen</param>
        public Risteys(object omaID)
        {
            this.omaID = omaID;
            this.aika = double.MaxValue;
        }
       
    } //Polku luokalle

    /// <summary>
    /// IKartta rajapintaa, joka määrittää kuinka reittihaku voi kysyä
    /// kartalta halutusta risteyspisteestä lähtevät polut.
    /// </summary>
    interface IKartta
    {
        List<Polku> polut(object tunniste);
    }

    /// <summary>
    /// Kartta luokka on yksinkertainen testi luokka, jolla selvitetään ReittiHaun toimintaa
    /// </summary>
    class Kartta:IKartta
    {
        public Kartta()
        {

        }

        public List<Polku> polut(object tunniste)
        {
            //nyt tunnisteena käytetään structure int:iä. Structure muuttujat
            //sisältävät arvon eivät viitettä, joten niitä voidaan sisällön perusteella
            //verrata. Mikäli käytät olioita joihin viite on tallennettu muuttujaan on
            //tunnisteenkin viitattava samaan olioon.
            int i = (int)tunniste;
            //p on lista johon palautettaat polut tallennetaan
            List<Polku> p = new List<Polku>();
            //Risteyspisteet sijaitsevat samanlaisessa järjestyksessä, kuin
            //oikeanlaidan näppäimistön numerot 1-6 ja oletuksena on, että
            //vitos näppäimen kohdalla on mäki, jonka päälle kiipeämiseen kuluu
            //aikaa enempi ja alastulo on hiukan nopeampaa. Muiden pisteiden
            //aika eroon vaikuttaa pisteiden etäisyys etäisyys.
            if(i==1) {
                //Ykkösen vieressä on napit 2,5 ja 4, joista
                //vitoseen on pisin matka ja se mäki muihin
                //pisteisiin on lyhyt matka
                p.Add(new Polku(1,2,1));
                p.Add(new Polku(1,5,2));
                p.Add(new Polku(1,4,1));
            }
            if(i==2) {
                //Samalla periaatteella kuin ykkönenkin, mutta
                //nyt 4 ja 6 ovat kauempana, kuin 1, 5 ja 3, mutta
                //vitosen kohdalla on mäki jonka kiipeämiseen kuluu aikaa
                p.Add(new Polku(2,3,1));
                p.Add(new Polku(2,6,1.41));
                p.Add(new Polku(2,5,2));
                p.Add(new Polku(2,4,1.41));
                p.Add(new Polku(2,1,1));
            }
            if(i==3) {
                p.Add(new Polku(3,6,1));
                p.Add(new Polku(3,5,2));
                p.Add(new Polku(3,2,1));
            }
            if(i==4) {
                p.Add(new Polku(4,1,1));
                p.Add(new Polku(4,2,1.41));
                p.Add(new Polku(4,5,1.5));
            }
            if(i==5) {
                //Vitosen kohdalta alastullessa menee vähemmän aikaa, kuin
                //tasaisella maalla matkaamiseen.
                p.Add(new Polku(5,4,0.7));
                p.Add(new Polku(5,1,1));
                p.Add(new Polku(5,2,0.7));
                p.Add(new Polku(5,3,1));
                p.Add(new Polku(5,6,0.7));
            }
            if(i==6) {
                p.Add(new Polku(6,3,1));
                p.Add(new Polku(6,2,1.41));
                p.Add(new Polku(6,5,1.5));
            }
            //Palautetaan lista, jossa polut ovat.
            return p;

        }

       
    }//Kartta luokalle

} //nimiavaruudelle