//LinkedNodeRecursion.java
//Illustrates recursion applied to a sequence of linked nodes.
//We use recursion to build a sequence of linked nodes containing
//integer values, to display those values in order, to display
//the values in reverse order, and to reverse the actual order
//of the nodes themselves. We also give an iterative version of
//a method to reverse the actual order of the nodes.

/*  Note:
    To read in a number of integer values on the same line, we read
    the entire line as a string, create a Scanner for the line, and
    then use that Scanner to read the integers from the string.
*/

import java.util.Scanner;

public class LinkedNodeRecursion
{
    private static Scanner keyboard = new Scanner(System.in);
    private static Scanner lineScanner;
    private static Node head; //A reference to the first Node of the sequence

    public static void main(String[] args)
    {
        System.out.println
        (
            "\nThis program illustrates recursion in "
            + "the context of a sequence of linked\nnodes. It uses four "
            + "recursive functions to perform the following actions."
            + "\nThe program reads in a line of integers, and places "
            + "them into a sequence of \nlinked nodes. Next it displays "
            + "the contents of that sequence of linked nodes,\nfirst in "
            + "their input order, and then in the reverse of that order. "
            + "Then it\nreverses the contents of the nodes, and repeats "
            + "the above two displays."
        );
        LinkedNodeRecursion tester = new LinkedNodeRecursion();
        tester.runTests();
    }

    private void runTests()
    {
        System.out.println
        (
            "\nBegin by entering data values for the nodes "
            + "on the following line:"
        );
        String line = keyboard.nextLine();
        lineScanner = new Scanner(line);

        buildNodeSequenceFromKeyboard();

        System.out.println
        (
            "\nHere, from the linked nodes, are the "
            + "values read in:"
        );
        displaySequenceValues(head);
        System.out.print("\nPress Enter to continue ... ");
        keyboard.nextLine();

        System.out.println
        (
            "\nHere, again from the linked nodes, are the "
            + "values in reverse order:"
        );
        displaySequenceValuesInReverse(head);
        System.out.print("\nPress Enter to continue ... ");
        keyboard.nextLine();
        
        System.out.println
        (
            "\nNext we reverse the order of the actual "
            + "nodes themselves."
        );
        head = reversedSequenceRecursively(head);
        //head = reversedSequenceIteratively(head);
        System.out.print("\nPress Enter to continue ... ");
        keyboard.nextLine();

        System.out.println
        (
            "\nThen we first display them in their new  "
            + "(reversed) order. Here they are:"
        );
        displaySequenceValues(head);
        System.out.print("\nPress Enter to continue ... ");
        keyboard.nextLine();

        System.out.println
        (
            "\nFinally, we display the revised sequence in reverse order,"
            + "\nwhich will be the original order of the values. "
            + "Here they are:"
        );
        displaySequenceValuesInReverse(head);
        System.out.print("\nPress Enter to continue ... ");
        keyboard.nextLine();
    }

    //Build sequence of linked nodes with values read from keyboard
    private void buildNodeSequenceFromKeyboard()
    {
        if (lineScanner.hasNextInt())
        {
            int value = lineScanner.nextInt();
            buildNodeSequenceFromKeyboard();
            head = new Node(value, head);
        }
        else
        {
            head = null;
        }
    }

    private void displaySequenceValues(Node head)
    {
        if (head != null)
        {
            System.out.print(head.data + " ");
            displaySequenceValues(head.next);
        }
    }

    private void displaySequenceValuesInReverse(Node head)
    {
        if (head != null)
        {
            displaySequenceValuesInReverse(head.next);
            System.out.print(head.data + " ");
        }
    }

    private Node reversedSequenceRecursively(Node head)
    {
        if (head == null)
            return null; //since the sequence is empty
        if (head.next == null)
            return head; //since the sequence has only one Node

        //Reverse the order of all nodes but the first, and
        //then make the former first Node the last Node
        Node rest = head.next;
        rest = reversedSequenceRecursively(rest);
        head.next.next = head;
        head.next = null;

        return rest;
    }

    private Node reversedSequenceIteratively(Node head)
    {
        Node reversedSequence = null;
        Node current = null;

        while (head != null)
        {
            //Remove Node from incoming list
            current = head;
            head = head.next;

            //Insert Node into reversed list
            current.next = reversedSequence;
            reversedSequence = current;
        }
        return reversedSequence;
    }

    private class Node
    {
        private int  data; //Data in the node
        private Node next; //Link to next node

        //Two constructors
        public Node(int data)
        {
            this(data, null);
        }
        public Node(int data, Node next)
        {
            this.data = data;
            this.next = next;
        }
    }
}