* 13.10.2017
 * Linked List in Java
 * Author: underscores
 */


 /*
  * (23:48:58) Sindre: so tell that guy to stick it and do it properly with submodules
  */

  import java.util.Random;
  import java.util.concurrent.TimeUnit;

public class LinkedList {

    private Node head;

    public LinkedList () {

        this.head = null;

    }

    public int pop() {

        int value;

        if(head.hasNext()) {
            value = head.getValue();
            head = head.getNext();
            return value;
        }

        else if (head != null) {
            value = head.getValue();
            head = null;
            return value;
        }

        else {
            System.out.println("Error");
            return 0;
        }

    }

    public void iter() {

        Node cur = head;
        int val;

        if(head == null) {
            System.out.println("Nothing to show, list is empty");
            return;
        }

        do {
            val = cur.getValue();
            cur = cur.getNext();
            System.out.println("Value :" + val);
        } while(cur != null);

    }

    public void push(int n) {

        Node newNode = new Node(n);

        newNode.setNext(head);
        head = newNode;

    }

    public void add(int n) {

        Node newNode = new Node(n);
        Node current = head;

        if(head == null) {
            head = newNode;
        }

        else {

        while(current.hasNext()) {
            current = current.getNext();
        }

        current.setNext(newNode);

        }

    }

    public void bubble() {

        Node sorted = null;

        while(sorted != head.getNext()) {

            Node prev = null;
            Node temp = head;

            while(sorted != temp.getNext()) {

                if(temp.getValue() > temp.getNext().getValue()) {
                    if(prev == null) {
                        head = temp.getNext();
                        temp.setNext(temp.getNext().getNext());
                        head.setNext(temp);

                    }
                    else{
                        prev.setNext(temp.getNext());
                        temp.setNext(prev.getNext().getNext());
                        prev.getNext().setNext(temp);
                        prev = prev.getNext();
                    }

                }

                else {
                    prev = temp;
                    temp = temp.getNext();

                }
            }

            sorted = temp;
        }
    }

    public static void main(String [] args) {

        LinkedList l = new LinkedList();
        Random randomGenerator = new Random();
        int randomint;
        for(int i = 1; i<=200000; i++) {
            randomint = randomGenerator.nextInt(200000);
            l.add(randomint);
        }
        System.out.println("Bubble started");
        long startTime = System.nanoTime();
        l.bubble();
        l.iter();
        long difference = System.nanoTime() - startTime;
        System.out.println("Execution time: " + String.format("%d min, %d sec", TimeUnit.NANOSECONDS.toHours(difference), TimeUnit.NANOSECONDS.toSeconds(difference) - TimeUnit.MINUTES.toSeconds(TimeUnit.NANOSECONDS.toMinutes(difference))));
        System.out.println("Bubble ended");

    }

}

class Node {

    private int value;
    Node next;

    public Node(int n) {

        this.value = n;

    }

    public int getValue() {

        return value;

    }

    public void setNext(Node n) {

        this.next = n;

    }

    public Node getNext() {

        return next;

    }

    public boolean hasNext() {

        return next != null;

    }

}