//---------------------------------------------------------------------
//  Sýnislausn á dæmi 5 á 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 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
    }
}
 

// Fallið víxlar hnútunum sem eru á eftir hnútunum sem t og u benda á
void vixlaHnutum( node *t, node *u )
{
	// Villuathugun...
	if( t == NULL || u == NULL ) return;
	if( t->next == NULL || u->next == NULL ) return;

	// Ef t og u benda á sama hnútinn þá gera ekkert
	if( t == u ) return;

	// Sértilfelli ef u-hnúturinn er strax á eftir t-hnútinum
	if( t->next == u ) {
		t->next = u->next;
		u->next = t->next->next;
		t->next->next = u;
	}
	// Sértilfelli ef t-hnúturinn er strax á eftir u-hnútinum
	else if( u->next == t ) {
		u->next = t->next;
		t->next = u->next->next;
		u->next->next = t;
	}
	// Almenna tilfellið...
	else {
		node *ot = t->next;
		node *ou = u->next;
		t->next = ou;
		u->next = ot;
		node *tmp = ou->next;		// 
		ou->next = ot->next;		// Víxla á ou->next og ot->next
		ot->next = tmp;				// 
	}

}


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

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

    // Sýna listann fyrir breytingu...
    prentaLista( haus );

	// Víxla hnútum...
	node *u = haus->next->next;
	cout << "Vixla a " << haus->next->next->item << " og " << u->next->item << "..." << endl;
	vixlaHnutum( haus->next, u );

    // Sýna listann eftir breytingu...
    prentaLista( haus );

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

    return 0;
}