/*
Päivitetty 22.05.2003
    - poistin Sort-funktion virtuaalisuuden, koska en halunnut muuttaa yksityisiä jäseniä suojatuiksi
Päivitetty 21.05.2003
    - siirsin Node-luokan Lista-luokan sisälle
    - muutin funktioiden Node::GetValue():n, Lista::GetValue():n ja Lista::Size():n palautustyypit
      ei-vakioksi arvoksi (ennen vakioviittaus), näin vältytään pieniltä muistiriskeiltä
Päivitetty 20.05.2003
    - estin mahdollisuuden käyttää oletuskopiomuodostinta ja sijoitusoperaattoria esittelemällä ne
    - otin NULL-makrot pois (ei suositella C++:ssa)
    - siistin koodia (esim. poistin pari tyhmää alustusta silmukan sisällä)
Päivitetty 18.05.2003
    - lisäsin Change(const T &value)-jäsenfunktio Lista:an, jotta arvon (value) voi vaihtaa.
    - lisäsin Sort()-funktion
    - GiveCurrent() on nyt CurValue()
    - vaihdoin Give-etuliitteen Get:iksi funktioissa.

Linkitetty lista, jossa on alku- ja loppusolmujen osoitteet on tiedossa. Jos on vain yksi solmu,
alkusolmun osoitin osoittaa itseensä. Kyseessä on siis rengasmainen lista.
Näytän, miten malleja käytetään. Huomaa, että lista on mallien ansiosta yleinen; voit tehdä
vaikka listan omasta luokastasi. Mutta jos haluat cout:ata niiden arvot, sinun täytyy kirjoittaa oma
operator<<-funktio.
Tein myös yksinkertaisen virheenhavaitsemismekanismin try:n ja catch:in avulla.

cout:in käyttö on vain esimerkin takia. Myös Print()-funktio on debuggauksen ja ohjelman toiminnan näyttämistä
varten. Sitä ei kannata sisällyttää lopulliseen kirjastoon, sillä rajapinta pitää pitää mahdollisimman yksinkertaisena.
Last() ja First() eivät olisi välttämättömiä, mutta ne nopeuttavat huomattavasti käyttöä, kun ei tarvitse käyttää
siihen aina Next():iä.

Huomaa, että tämä linkitetty lista on vain lukuoikeuksinen, eli et voi käsitellä solmuja käsin, muuten kuin
jäsenfunktioita käyttämällä. Näin varmistetaan turvallisuus.

Jos huomaat bugin, kuinka pienen tahansa, niin ilmoita heti.

Copyright 2003, Henrik Huttunen a.k.a. egaga
*/

// lista.h

#ifndef LISTA
#define LISTA

#include <iostream>

// jos listassa ei ole solmuja, mutta pyydetään current-alkiota (value), aiheutuu poikkeus NoNodes
class NoNodes{};

// Listankäsittelysysteemi
template <class T>
class Lista
{
    private:

        // Solmu-luokka tiedon pitämistä varten
        template <class N>
        class Node
        {
            private:
                N value;
                Node<N> *next; // osoitin seuraavaan solmuun
            public:
                Node() : next(0), value(0) {};
                Node(Node<N> *n, const N &v) : next(n), value(v) {}
                Node<N> *GetNext(){ return next; }
                N GetValue() const { return value; }
                void SetValue(const N &value){ this->value = value; }
                void SetNext(Node<N> *next){ this->next = next; }
        };

        Node<T> *root; // juurisolmu (lista alkaa tästä solmusta)
        Node<T> *head; // päätesolmu (lista päättyy tähän solmuun)
        Node<T> *current;   // nykyinen solmu (kohta listassa jota MANUAALISESTI käsitellään)
                            // currentiin ei siis vaikuta AddNode(), mutta DelNode() tietysti vaikuttaa
        long count; // solmujen lukumäärä

        // estetään ei-toivottujen oletusfunktioiden käyttö esittelemällä ne ilman määritystä
        Lista(const Lista &); // kopiomuodostin
        Lista &operator=(const Lista &); // sijoitusoperaattori
    public:
        Lista();
        ~Lista();
        void AddNode(const T &value);
        void DelNode(); // poistaa solmun, jossa ollaan menossa, current siirtyy seuraavaan solmuun
        inline T CurValue() const;
        void Change(const T &value); // vaihtaa arvon currentin osoittaman arvon tilalle

        void Sort();
        long Size() const { return count; }

        // funktiot, joilla ohjaillaan current:ia
        int First();
        int Last();
        int Next();

        void Print() const; // tulosta kaikki solmut
};

template <class T>
// Yksinkertainen järjestysalgoritmi (Huomaa, että omalle luokalle täytyy määrittää vertailuoperaattori operator< )
// Huomaa myös, ettei current muutu!
void Lista<T>::Sort()
{
    if( !root )
        return;
 
    Node<T>
        *i = root,
        *j;
    j = i->GetNext();
    T temp;
   
    do
    {
        while( j != root )
        {
            if( j->GetValue() < i->GetValue() )
            {
                // vaihdetaan i:n ja j:n sisältämät arvot (value)
                temp = i->GetValue();
                i->SetValue( j->GetValue() );
                j->SetValue(temp);
            }
            j = j->GetNext();
        }
        j = ( i = i->GetNext() )->GetNext(); // huomaa, ettei j ole koskaan i:tä edellä listassa tai sama kuin i
    }while( i != root );
    std::cout << "List is sorted" << std::endl;
}

template <class T>
// Vaihtaa arvon currentissa
void Lista<T>::Change(const T &value)
{
    if( !current )
        throw NoNodes();
    std::cout << "Changed value " << current->GetValue() << " to " << value << std::endl;     
    current->SetValue(value);
}   

template <class T>
// palauttaa currentin osoittaman solmun arvon
inline T Lista<T>::CurValue() const
{
    if( current )
        return current->GetValue();
    // aiheutetaan poikkeus, koska ei ole ollenkaan solmuja
    throw NoNodes();
}   

template <class T>
// Tulostaa listan kaikkien solmujen arvot (value)
// Kannattaa ottaa pois lopullisesta kirjastosta, koska ei ole tarpeellinen
// Minimalistista rajapintaa kannataa suosia, ellei jostakin funktiosta ole selvästi helpotusta
// Print() on kuitenkin kätevä debuggauksessa
void Lista<T>::Print() const
{
    if( !root )
        return;

    Node<T> *temp = root;
    do
    {
        std::cout << temp->GetValue() << " ";
        temp = temp->GetNext();
    }while( temp!=root ); // Huom! tempin testaaminen 0:lla ei käy, koska rengaslista
    std::cout << std::endl;
}

template <class T>
// Asettaa currentin osoittamaan viimeiseen solmuun listassa
int Lista<T>::Last()
{
    if( !head )
        return -1;
    current = head;
    return 0;
}

template <class T>
// Asettaa currentin osoittamaan ensimmäiseen solmuun listassa
int Lista<T>::First()
{
    if( !root )
        return -1;
    current = root;
    return 0;
}

template <class T>
// Asettaa currentin osoittamaan seuraavaan solmuun
// Palauttaa
//     -1   , jos ei ole yhtään solmua
//      0   , jos asetus onnistui eikä uusi solmu ole viimeinen solmu
//      1   , jos asetus onnistui ja uusi solmu on viimeinen solmu listassa
int Lista<T>::Next()
{
    if( !current )
        return -1;

    current = current->GetNext();
    if( current != head ) // jos solmu ei ole viimeinen
    {
        std::cout << "Current is moved to NEXT node in list" << std::endl;       
        return 0;
    }else
    {
        std::cout << "Current is moved to LAST node in list" << std::endl;
        return 1;
    }
}

template <class T>
// Luo uuden solmun listaan, parametrina arvon (value) viittaus
void Lista<T>::AddNode(const T &value)
{
    ++count;
    std::cout << "Added to list: " << value << ", total: " << count << std::endl;
    if( !root )
    {
        root = new Node<T>(root, value); // asetetaan solmun next osoittamaan itseensä
        current = root; // nykyinen solmu osoittaa tällä hetkellä sinne minne rootkin
        head = root; // alku- ja loppusolmu ovat samat
    }else // jos solmuja on jo olemassa
    {
        // next-osoitin osoittamaan listan alkuun, koska temp on viimeinen solmu
        Node<T> *temp = new Node<T>(root, value);
        head->SetNext(temp); // asetetaan äskeinen päätesolmu (head) osoittamaan uutta päätesolmua
        head = temp; // asetetaan head osoittamaan viimeiseen solmuun
    }
}

template <class T>
// Poistaa currentin osoittaman solmun
void Lista<T>::DelNode()
{
    if( !current )
        return;
    --count;
    std::cout << "Deleted from list: " << current->GetValue() << ", total: " << count << std::endl;
    if( current == root ) // jos poistetaan juurisolmua (on erikoistapaus, koska voi viitata itseensä)
    {
        Node<T> *temp = root;
        if( temp == ( root=root->GetNext() ) ) // jos on vain yksi solmu
        {
            // rootista tulee 0-osoitin, muuten root osoittaa seuraavaan solmuun
            root = head = current = 0;           
        }else
        {
            head->SetNext(root); // laitetaan listan pää osoittamaan listan uuteen alkusolmuun
            current = root;
        }
        delete temp;
    }else
    {
        Node<T>
            *temp = root, // etsintä alkaa juuresta
            *apu;
        while( ( apu = temp->GetNext() ) != current ) // etsitään current:ia edeltävää solmua
            temp = apu;
        if( current==head ) // jos poistetaan viimeinen solmu
            head = temp;
        // laitetaan tempin next osoittamaan poistettavaa solmua seuraavaan solmuun
        temp->SetNext(apu = current->GetNext());
        delete current;
        current = apu; // uusi current osoittaa poistettua solmua seuraavaa solmua
    }
}
template <class T>
Lista<T>::Lista() : root(0), current(0), head(0), count(0)
{
    std::cout << "Constructor" << ", total: " << count <<  std::endl;
}

template <class T>
// Destruktori. Poistaa kaikki solmut.
Lista<T>::~Lista()
{
    count = 0;
    std::cout << "Destructor" << ", total will be: " << count <<  std::endl;
    if( !root )
        return;
    Node<T>
        *apu = root,
        *temp;
    do
    {
        temp = apu->GetNext();
        std::cout << "Deleted from list: " << apu->GetValue() << std::endl;
        delete apu;
        apu = temp;
    }while( temp!=root ); // käydään kaikki solmut läpi
}

#endif

// main.cpp

#include <iostream>
#include <string>
#include "lista.h"

int main(){

    Lista<int> *kolikot = new Lista<int>; // lista kolikkojen määrästä eri lompakoissa ja säästöpossuissa
    kolikot->DelNode(); // yritetään poistaa current-value:ta, vaikka listassa ei ole yhtään solmua (toimii)
    kolikot->AddNode(53);
    kolikot->AddNode(23);
    kolikot->AddNode(67);
    kolikot->AddNode(13);
    kolikot->Sort(); // järjestetään lista
    kolikot->Print(); // näytetään rahat, mitä meillä on eri paikoista
    kolikot->DelNode(); // poistetaan ensimmäiseksi laitettu arvo (value), koska current:ia ei ole muutettu
    kolikot->Print();
    kolikot->Next(); // siirretään currentia seuraavaan solmuun (käsitellään seuraavaa lompakkoa (tai possua))
    kolikot->Change(35); // vaihdetaan currentin arvo 35:ksi
    kolikot->AddNode(3);
    kolikot->Print();
    kolikot->DelNode(); // poistetaan arvo, johon current osoittaa
    kolikot->Print();
     
    std::cout << std::endl << "luuppi alkoi" << std::endl;
    // demonstrointi: käydään läpi rahalähteitämme, niin että kuljetaan listassa jonkin verraan "ympäri"
    for(int i=0, t; i<6; ++i)
    {
        // next palauttaa arvon, joka riippuu, missä kohdin listaa olemme ja siirtää sisäistä osoitinta seuraavaan solmuun
        t = kolikot->Next(); // t kertoisi, ollaanko listan lopussa tai jos lista on tyhjä, mutta emme tarvitse sitä nyt
        std::cout << kolikot->CurValue() << std::endl;
    }
    std::cout << "luuppi loppui" << std::endl;

    delete kolikot; // poistetaan kaikki rahalähteemme

    // tehdään lista kavereista
    Lista<std::string> *kaverit = new Lista<std::string>;

    kaverit->AddNode("Mari");
    kaverit->AddNode("Jorma");
    kaverit->AddNode("Teppo");
    kaverit->Print();

    while( kaverit->Next() != 1 ); // etsitään viimeinen solmu (Teppo)
    //voitaisiin kirjoittaa paremmin kaverit->Last() jos tarvitaan vain nopea pääsy viimeiseen arvoon
    //tarkoitus on kuitenkin osoittaa, kuinka voit käydä läpi listaa
   
    kaverit->DelNode(); // Teppo oli liaan itsekeskeinen ollakseen minun kaveri, potkitaan hänet pellolle
    kaverit->Print();
    kaverit->DelNode(); // Mari jätti (taisin olla liian ruma)
    kaverit->Print();
    kaverit->DelNode(); // Jorma olikin töissä Microsoftissa, eikä sellaisten ihmisten kanssa voi kaveerata
    kaverit->Print(); // näyttää ettei ole yhtään kaveria jäljellä :(

    // tähän asti ei ole ollut virheenkäsittelyä; seuraavaksi näytän, miten poikkeus siepataan
   
    try
    {
        // yritetään tulostaa current-value (jota ei ole)
        std::cout << kaverit->CurValue() << std::endl; // CurValue() aiheuttaa NoNodes-tyyppisen poikkeuksen
        std::cout << "Tätä ei tule näkymään ruudulla." << std::endl;
    }
    catch( NoNodes ) // catch sieppaa NoNodes-tyyppisen olion
    {
        std::cout << "No values to print!" << std::endl; // nyt voit täällä käsitellä virheen
    }   
    delete kaverit;

    std::string temp;
    std::cout << "Kirjoita \"end\" ja paina enter lopettaaksesi." << std::endl;
    while( cin >> temp )
        if( temp=="end" )
            break;
    return 0;
}