// low-level use of references in C#
// a basic (single-linked) list, doing list reversal as main op
// Version 1: copying list reversal, leaving orig list unchanged

using System;

// the list class just identifies the root of the linked list
// and is otherwise just a wrapper to the LinkedListNode class
public class List {
    // Fields / properties
    public LinkedListNode Root { get ; set ; }

    // Constructors
    public List() { this.Root = null ; }
    public List(int x) { this.Root = new LinkedListNode(x); }
    public List(params int [] xs) { this.Root = mkList(xs); }

    // Building an entire list from an array
    public static LinkedListNode mkList (params int[] xs) {
	if (xs.Length == 0) {
	    return null;
	} else {
	    LinkedListNode root = new LinkedListNode(xs[0]);
	    LinkedListNode curr = root;
	    for (int i = 1 ; i<xs.Length; i++, curr = curr.Next) 
		curr.Next = new LinkedListNode(xs[i]);

	    return root;
	}
    }

    // -------------------------------------------------------
    // top-level list reversal 
    public List ListReversal () {
	if (this.Root == null) {
	    return null;
	} else {
	    List reversed = new List();
	    reversed.Root = this.Root.ListReversal();
	    return reversed;
	}
    }    

    /*
    // -------------------------------------------------------
    // top-level in-place list reversal 
    public List ListReversalInplace () {
	if (this.Root == null) {
	    return null;
	} else {
	    List reversed = new List();
	    reversed.Root = this.Root.ListReversalInplace();
	    return reversed;
	}
    }    
    // -------------------------------------------------------
    */
    
    // for printing a list
    public void ShowList6 () {  this.Root.ShowList6() ; }
    public void ShowList () {  this.Root.ShowList() ; }
	
}

// this class is the main one in the implementation, identifying
// one node in a single-linked list
public class LinkedListNode {

    // Fields  
    private LinkedListNode next;

    // Properties
    public LinkedListNode Next {
	get { return next; } 
	set { next = value; } 
    }
    public int Data { get ; set ;  }

    public LinkedListNode (int data) {
	this.Data = data;
	this.next = null;
    }

    /*
      EXERCISE: implement a method that returns the elements of the input list in reverse order
    */

    // -------------------------------------------------------
    // list reversal 
    public LinkedListNode ListReversal () {
	LinkedListNode start, end;
	return this.ListRev(out start, out end);
    }

    // helper function for list reversal
    // this generates a new list with elements in reverse order (NOT inplace)
    public LinkedListNode ListRev (/* (1) used out args */ out LinkedListNode start, out LinkedListNode end) {
	if (this.Next == null) { // finished: tie things together
	    // (2) don't forget to allocate
	    LinkedListNode curr = new LinkedListNode(this.Data);
	    curr.Data = this.Data;
	    start = curr;
	    end = curr;
	    return start;
	} else {
	    LinkedListNode reversed, tail;
	    LinkedListNode curr = new LinkedListNode(this.Data);
	    this.Next.ListRev(out reversed, out tail);
	    tail.Next = curr;
	    start = reversed;
	    end = curr;
	    return reversed;
	}
    }
    /*
       BEFORE:
                            tail     reversed 
                             |        |
                             v        v 
        +----    +----      +----    +----             
        |2| ---> |3| --->   |5| ---> |7| --|  
        +---     +---       +---     +---           
                  ^           
                  |
                 this 
       AFTER:
                            tail     reversed 
                             |        |
                             v        v 
        +----    +----      +----    +----             
        |2| ---> |3|  <--   |5|  <-- |7|   
        +---     +---       +---     +---           
                  ^           
                  |
                 this 
     */

    
    // -------------------------------------------------------
    // EXERCISE: modify the copying list reversal to an in-place one

    // -------------------------------------------------------
    // this version uses C# 6.0 null-conditional operators 
    public void ShowList6 () {
	Console.Write("{0} ",this.Data);
	this.next?.ShowList6();
    }

    public void ShowList () {
	Console.Write("{0}",this.Data);
	if (this.next == null) {
	    return; 
	} else {
	    Console.Write(" -> ");
	    this.next.ShowList();
	}
    }
}

// Test class with Main
public class Tester {
  public static void Main() {
      List l = new List(new int[] {2,3,5,7}) ;
      Console.WriteLine("Expect prime numbers < 10 ...");
      l.ShowList(); Console.WriteLine();
      Console.WriteLine("Testing list reversal (copying NOT inplace) ...");
      List lrev = l.ListReversal();
      Console.Write("Reversed list: ");
      lrev.ShowList(); Console.WriteLine();
      Console.Write("Original list: ");
      l.ShowList(); Console.WriteLine();
      /* in-place list reversal
      Console.WriteLine("Testing list reversal (inplace) ...");
      List lrev1 = l.ListReversalInplace();
      Console.Write("Reversed list: ");
      lrev1.ShowList(); Console.WriteLine();
      Console.Write("Original list: ");
      l.ShowList(); Console.WriteLine();
      */
  }

    /*
  public static void MainNOT() {
    LinkedListNode n1 = new LinkedListNode(1);
    Console.WriteLine("Expect a 1 element list with 1...");
    n1.ShowList6();
    // adding 3 at the end
    LinkedListNode n3 = new LinkedListNode(3);
    n1.Insert(n3);
    Console.WriteLine("Inserting 3 after 1 ...");
    Console.WriteLine("Expect a 2 element list with 1 3 ...");
    n1.ShowList6();
    Console.WriteLine("Testing showListReverse; expect a 2 element list with 3 1 ...");
    n3.ShowListReverse();
    // adding 2 btw 1 and 2
    LinkedListNode n2 = new LinkedListNode(2);
    n1.Insert(n2);        
    Console.WriteLine("Inserting 2 after 1 ...");
    Console.WriteLine("Expect a 3 element list with 1 2 3 ...");
    n1.ShowList6();
    Console.WriteLine("Testing showListReverse; expect a 3 element list with 3 2 1 ...");
    n3.ShowListReverse();
    // removing a node
    n2.Remove();        
    Console.WriteLine("Removing 2 ...");
    Console.WriteLine("Expect a 2 element list with 1 3 ...");
    n1.ShowList6();
    Console.WriteLine("Testing showListReverse; expect a 2 element list with 3 1 ...");
    n3.ShowListReverse();
    try {
      n3.RemoveBuggy();        
    } catch (NullReferenceException e) {
      Console.WriteLine("RemoveBuggy didn't check for null pointer, hence this exception: {0}", e.Message);
    }
    n3.Remove();        
    Console.WriteLine("Removing 3 ...");
    Console.WriteLine("Expect a 1 element list with 1 ... ");
    n1.ShowList6();
  }
  */
}