//---------------------------------------------------------------------
//  Sýnislausn á dæmi 4 á Vikublaði 5 í Tölvunarfræði 2, vor 2005
//
//  Hjálmtýr Hafsteinsson, febrúar 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; } 
};


// Prentar út eintengdan hringtengdan lista
void prentaHrLista( node *h )
{
	node *p;

	for( p = h; p->next != h; p = p->next )
		cout << p->item << " -> ";
	cout << p->item << " -v" << endl << endl;
}


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

	if( n < 1 ) return NULL;

    // Geyma bendi á aftasta hnútinn
    h = p = new node( rand()%rnd, NULL );

    for( i=1; i<n; i++ )
        p = new node( rand()%rnd, p );

	// Láta aftasta hnútinn benda á þann fremsta
	h->next = p;

    return p;
}


// Eyðir eintengdum hringtengdum lista (þ.e. skilar minni hans)
void eydaHrLista( node *h )
{
	node *t = h;

	// Hætta þegar við sjáum bendi á fyrst hnútinn
    while( h != t ) {
	    node *p = h;
        h = h->next;			// Flytja h yfir á næsta
        delete p;				// Eyða hnúti
    }
}
 

// Skilar fjölda hnúta sem eru á milli þeirra sem x og t benda á
// Skilar -1 ef annar hvor bendirinn er NULL
int teljaHrHnuta( node *x, node *t )
{
	int fjoldi = 0;

	// Villuathugun...
	if( x == NULL || t == NULL ) return -1;

	// Ef x og t benda á sama hnútinn þá er enginn hnútur á milli
	if( x == t ) return 0;

	// Hættum í lykkjunni þegar p->next == t, því við viljum bara
	//  telja þá hnúta sem eru Á MILLI þeirra sem x og t benda á
	for( node *p=x; p->next!=t; p=p->next )
		fjoldi ++;

	return fjoldi;
}


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

    // Búa til slembilist
    node *haus = buatilHrLista( 10, 100 );

    // Sýna listann...
    prentaHrLista( haus );

	// Telja fjölda hnúta...
	node *t = haus->next->next->next->next;
	cout << "Fjoldi hnuta a milli " << haus->item << " og " << t->item
		  << " er " << teljaHrHnuta( haus, t ) << endl;

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

    return 0;
}