// Demonstrates use of pointers to make a linked list.
// Also deletes the list. 
// Works even if the list has zero elements.
// This version uses blah->blip liberally instead of (*blah).blip

#include <iostream>
using namespace std;

// create a structure for an 'item' in the linked list
typedef struct item {
  int value ; 
  item *next ;
};
#define ENDOFLIST 0


// This function carries out the key manipulation: inserting
//  a new item into an existing list at the place pointed to
//  by p.  We pass the pointer p
//  by reference so that we can change where it points!
void add_new_item_after( int v , item * &p ) {
  // save the address[+] that this pointer currently points to
  item *current ;
  current = p ;
  // Now create memory for the new item, and
  // overwrite that address[+] with the address of the new item
  p = new item ; // new returns a pointer to the memory location
  p->value = v ; 
  p->next = current ; 
}

// This function's job is to make sure the quantity
// v gets inserted somewhere in the linked list, either
// here or somewhere later in the list.
// It achieves this by checking to see if here is the
// right place, and if not, using recursion to get
// v inserted later. 
void insert_here_or_later( int v , item * &h ) {
  if ( (h == ENDOFLIST) || v <= h->value ) {
    add_new_item_after( v , h ) ;
  } else {
    insert_here_or_later(  v , h->next ) ;
  }
}

// This function uses recursion to print a linked list.
void print_list( item *h ) {
  if ( h == ENDOFLIST ) { 
    cout << "end of list\n" ;
  } else {
    printf( "%9d\n" , h->value ) ;
    print_list( h->next ) ;
  }
}

// This function uses recursion to free all the memory
// occupied by a linked list, "starting from here".
// The memory is actually freed in order from the tail
// back to "here", because we delete the rest of this list
// "n" first, before we delete "here" ("h"). 
void delete_list( item *h ) {
  if ( h == ENDOFLIST ) { 
    cout << "list deleted\n" ;
  } else {
    item *n ;
    n = h->next ;
    delete_list( n ) ;
    printf( "deleting item with value %9d\n" , h->value ) ;
    delete h ; 
  }
}

// a recursive function
//   get_nth_value_from_list( start, n )
// such that 
//   get_nth_value_from_list( start, 4 )
//   returns the value of the 4th item in the list,
//   or complains if the list is found not to have 4 items.
int get_nth_value_from_list( item *h , int n ) {
  if( h == ENDOFLIST ) {
    cout.flush();
    cerr << "Error, requested too big value for index in list\n" ;
    cerr.flush();
    return -1 ;
  }
  if ( n == 1 ) {
    return h->value ;
  } else {
    return get_nth_value_from_list( h->next , n-1 ) ; 
  }
}

// Make N random numbers;
//  put them into a linked list, using Insertion Sort
//  so that they are in ascending order;
//  print the linked list;
//  then delete the linked list.
int main ()
{
  int N = 10 ;
  int range = 1<<20 ; // 1 million, roughly
  int *a ;
  int seed = 123;

  a = new int[N] ; // allocates memory for
                   // a[0]..a[N-1]
  srandom(seed);
  // make N random numbers
  for ( int n = 0 ; n < N ; n ++ ) {
    a[n] = random() % range ; // returns a number in 0..range-1
  }
  cout << "UNSORTED-\n" ; 
  for ( int n = 0 ; n < N ; n ++ ) {
    printf( "%9d\n" , a[n] ) ; 
  }
  cout << "---------\n" ;
  
  item *start ;
  start = ENDOFLIST ; // empty list
  for ( int n=0; n < N ; n ++ ) {
    insert_here_or_later( a[n] , start ) ; 
  }
  print_list( start ) ;

  if( N >= 4 ) {
    cout << "\nIllustration of a possible use of this list: \n" 
	 << "The 1st item in the list is: \n" 
	 << "start->value = " 
	 << start->value << endl << endl 
	 << "The 2nd item in the list is: \n" 
	 << "start->next->value = " 
	 << start->next->value << endl << endl 
	 << "The 4th item in the list is: \n" 
	 << "start->next->next->next->value = " 
	 << start->next->next->next->value << endl << endl ;
    cout << "(This style (->->->) of coding is not recommended... "
	 << "it's just an illustration\n" ;
  }
  if( N >= 4 ) {
    cout << "\n \n" 
	 << "Using   get_nth_value_from_list(,)  \n" 
	 << "The 1st item in the list is: \n" 
	 << "start->value = " 
	 << get_nth_value_from_list( start, 1 ) << endl << endl ;
    cout << "The 2nd item in the list is: \n" 
	 << "start->next->value = " 
	 << get_nth_value_from_list( start, 2 ) << endl << endl ;
    cout << "The 4th item in the list is: \n" 
	 << "start->next->next->next->value = " 
	 << get_nth_value_from_list( start, 4 ) << endl << endl ;
    cout << "The 14th item in the list is: \n" 
	 << "start->next->...->next->value = " 
	 << get_nth_value_from_list( start, 14 ) << endl << endl 
	 << endl ; 
  }
  
  delete_list( start ) ;
}