// Program to test solutions to problem #9 on the cse143 final, spring 2010.
// Fill in your solution to compressDuplicates, then compile and run the
// program

import java.util.*;

class LinkedIntList {
    public void compressDuplicates() {
        // fill in your solution here
    }

    private ListNode front;  // first value in the list

    // this is the sample solution
    public void compressDuplicates2() {
        if (front != null) {
            int count = 1;
            while (front.next != null && front.data == front.next.data) {
                count++;
                front = front.next;
            }
            front = new ListNode(count, front);
            ListNode current = front.next;
            while (current.next != null) {
                count = 1;
                while (current.next.next != null &&
                       current.next.data == current.next.next.data) {
                    count++;
                    current.next = current.next.next;
                }
                current.next = new ListNode(count, current.next);
                current = current.next.next;
            }
        }
    }

    // post: constructs an empty list
    public LinkedIntList() {
        front = null;
    }

    // post: creates a comma-separated, bracketed version of the list
    public String toString() {
        if (front == null)
            return "[]";
        else {
            String result = "[" + front.data;
            ListNode current = front.next;
            while (current != null) {
                result += ", " + current.data;
                current = current.next;
            }
            result += "]";
            return result;
        }
    }

    // post: appends the given value to the end of the list
    public void add(int value) {
        if (front == null)
            front = new ListNode(value);
        else {
            ListNode current = front;
            while (current.next != null)
                current = current.next;
            current.next = new ListNode(value);
        }
    }
}

public class FinalTest9 {
    public static void main(String[] args) {
        test(new int[] {2, 2, 2, 2, 2, -5, -5, 3, 3, 3, 3, 4, 4, 1, 0, 17, 17});
        test(new int[] {10, 20, 10, 20, 10, 20});
        test(new int[] {});
        test(new int[] {1});
        test(new int[] {8, 7});
        test(new int[] {9, 12, 15});
        test(new int[] {3, 8, 2, 5});
        test(new int[] {17, 4, 3, 9, 18});
        test(new int[] {4, 4});
        test(new int[] {15, 15, 15});
        test(new int[] {-8, -8, -8, -8});
        test(new int[] {7, 3, 3});
        test(new int[] {14, 5, 5, 5});

        Random r = new Random();
        for (int i = 0; i <= 10; i++) {
            int[] data = new int[20];
            int index = 0;
            while (index < 20) {
                int n = r.nextInt(10);
                int times = Math.min(1 + r.nextInt(4), 20 - index);
                for (int j = 0; j < times; j++)
                    data[index++] = n;
            }
            test(data);
        }
    }

    public static void test(int[] data) {
        LinkedIntList list1 = new LinkedIntList();
        LinkedIntList list2 = new LinkedIntList();
        for (int num : data) {
            list1.add(num);
            list2.add(num);
        }
        boolean fail = false;
        System.out.println("list     = " + list1);
        list1.compressDuplicates2();
        System.out.println("expected = " + list1);
        try {
            list2.compressDuplicates();
        } catch (RuntimeException e) {
            System.out.println("    threw " + e + " with list = " + list2);
            fail = true;
        }
        if (!fail && !list1.toString().equals(list2.toString())) {
            System.out.println("actual   = " + list2);
            fail = true;
        }
        if (fail)
            System.out.println("failed");
        else
            System.out.println("passed");
        System.out.println();
    }
}

class ListNode {
    public int data;       // data stored in this node
    public ListNode next;  // link to next node in the list

    // post: constructs a node with data 0 and null link
    public ListNode() {
        this(0, null);
    }

    // post: constructs a node with given data and null link
    public ListNode(int data) {
        this(data, null);
    }

    // post: constructs a node with given data and given link
    public ListNode(int data, ListNode next) {
        this.data = data;
        this.next = next;
    }
}