001package algs22;
002import stdlib.*;
003
004// PROBLEM 2.2.17
005public class MyLinkedSort {
006    static class Node {
007        public Node() { }
008        public double item;
009        public Node next;
010    }
011
012    int N;
013    Node first;
014    
015    private void sort() { 
016        // TODO 
017    }
018    
019    public MyLinkedSort () {
020        first = null;
021        N = 0;
022        checkInvariants ();
023    }
024
025    private void myassert (String s, boolean b) { if (!b) throw new Error ("Assertion failed: " + s); }
026    private void checkInvariants() {
027        myassert("Empty <==> first==null", (N == 0) == (first == null));
028        Node x = first;
029        for (int i = 0; i < N; i++) {
030            if (x==null) {
031                throw new Error ("List too short!");
032            }
033            x = x.next;
034        }
035        myassert("EndOfList == null", x == null);
036    }
037
038    public boolean isEmpty () { return first == null; }
039    public int size () { return N; }
040    public void add (double item) {
041        Node newfirst = new Node ();
042        newfirst.item = item;
043        newfirst.next = first;
044        first = newfirst;
045        N++;
046    }
047
048    private static void print (String s, MyLinkedSort b) {
049        StdOut.print (s + ": ");
050        for (Node x = b.first; x != null; x = x.next)
051            StdOut.print (x.item + " ");
052        StdOut.println ();
053    }
054    private static void print (String s, MyLinkedSort b, double i) {
055        StdOut.print (s + ": ");
056        for (Node x = b.first; x != null; x = x.next)
057            StdOut.print (x.item + " ");
058        StdOut.println (": " + i);
059    }
060
061    public static void main (String args[]) {
062        int[] a1 = new int[20];
063                for (int i = 0; i < a1.length; i++)
064                        a1[i] = i;
065                StdRandom.shuffle (a1);
066        MyLinkedSort b1 = new MyLinkedSort ();
067        for (int i:a1) b1.add(i);
068        MyLinkedSort.print("before sort",b1);
069        b1.sort();
070        MyLinkedSort.print("after sort",b1);
071
072        int[] a2 = new int[200];
073                for (int i = 0; i < a2.length; i++)
074                        a2[i] = i;
075                StdRandom.shuffle (a2);
076        MyLinkedSort b2 = new MyLinkedSort ();
077        for (int i:a1) b2.add(i);
078        MyLinkedSort.print("before sort",b2);
079        b2.sort();
080        MyLinkedSort.print("after sort",b2);
081         
082    }
083}
084
085