import plp.collection.*;

public class TestSTree {
    private static STree sortedInsert(STree t, Comparable data) {
	try {
	    return (t.isEmpty() 
		    ? new STree(data) 
		    : (data.compareTo(t.data()) > 0 
		       ? new STree(t.left(), t.data(), sortedInsert(t.right(), data))
		       : new STree(sortedInsert(t.left(), data), t.data(), t.right())));
	} catch (EmptyTreeException e) {
	    throw new InternalError();
	}
    }
    
    public static SList sort(Comparable [] data) {
	STree t = STree.EMPTY;

	for (int i = 0; i < data.length; ++i) {
	    t = sortedInsert(t, data[i]);
	}
	return t.depthFirstSearch();
    }
    
    public static Object [] sortToArray(Comparable [] data) {
	STree t = STree.EMPTY;

	for (int i = 0; i < data.length; ++i) {
	    t = sortedInsert(t, data[i]);
	}
	return t.depthFirstSearchToArray();
    }
    
    public static void main(String [] args) {
	System.out.println(sort(args));

	Object [] sa = sortToArray(args);
	for (int i = 0; i < sa.length - 1; ++i) {
	    System.out.print(sa[i] + " ");
	}
	System.out.println(sa[sa.length - 1]);
    }
}