//---------------------------------------------------------------------
//  Sýnislausn á dæmi 3 á Vikublaði 8 í Tölvunarfræði 2, vor 2005
//
//  Hjálmtýr Hafsteinsson, mars 2005
//---------------------------------------------------------------------
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

// Hnútur, ásamt smið
struct node {
	int item;
	node* next; 

	node(int x, node* t) 
		{ item = x; next = t; } 
};

// Min-fallið sem við þurfum hér að neðan
int min(int A, int B) 
{
	if( A < B ) return A;
	else return B;
}


// Prentar út eintengdan lista
void prentaLista( node *h )
{
	for( node *p = h; p != NULL; p = p->next )
		cout << p->item << " -> ";
	cout << "NULL" << endl << endl;
}


// Fallið býr til eintengdan lista með n hnútum og slembigildum
//  frá 0 og upp að rnd.  Skilar bendi á fremsta hnútinn
node *buatilLista( int n, int rnd )
{
    int i;
    node *p;

    // Búa eintengdan lista með slembigildum...
    p = NULL;
    for( i=0; i<n; i++ )
        p = new node( rand()%rnd, p );

    return p;
}


// Eyðir eintengdum lista (þ.e. skilar minni hans)
void eydaLista( node *h )
{
    while( h != NULL ) {
	    node *p = h;
        h = h->next;			// Flytja h yfir á næsta
        delete p;				// Eyða hnúti
    }
}
 

//////////////////// Sýnislausnir á dæmi 3 á vikublaði 8 ////////////////////

// Dæmi 3 a):  Skilar lengd lista
int length( node *p )
{
	if( p==NULL ) return 0;			// length( [] )  =  0
	else return (1+length( p->next ));	// length( a::L )  =  1 + length( L )
}


// Dæmi 3 b):  Skilar i-ta stakinu í listanum ef hann er nógu langur, annars "too short"
int nth( int i, node *p )
{
	if( i<=0 ) {				// n-th( 0, L )  =  error
		cout << "Error" << endl;
		return -1;
	}
	if( p==NULL ) {				// n-th( i, [] )  =  too short
		cout << "Too short" << endl;
		return -1;
	}
	if( i==1 ) return p->item;		// n-th( 1, a::L )  =  a

	return nth( i-1, p->next );		// n-th( i+1, a::L )  =  n-th( i, L )
}


// Dæmi 3 c):  Skilar minnsta stakinu í listanum
int least( node *p )
{
	if( p==NULL ) {				// least( [] )  =  error
		cout << "Error" << endl;
		return -1;
	}
	if( p->next==NULL ) return p->item;	// least( a::[] )  =  a

	return min( p->item, least( p->next ) );	// least( a::b::L )  =  min( a, least( b::L ) )
}


////////////////////////////////////////////////////////////////////////////

int main()
{
	// Upphafsstilla slemibitölugjafa
	srand( (unsigned)time( NULL ) );

    // Búa til slembilista
    node *haus = buatilLista( 10, 100 );

    // Sýna slembilistann...
    prentaLista( haus );

	// Finna lengd hans...
	cout << "Lengd listans er " << length( haus ) << endl << endl;

	// Finna n-ta stak hans...
	cout << "5-ta stak listans er " << nth( 5, haus ) << endl << endl;

	// Finna minnsta stak listans...
	cout << "Minnsta stak listans er " << least( haus ) << endl << endl;

    // Skila aftur minninu...
    eydaLista( haus );

    return 0;
}