Appletti esittää Bubblesortin ja QuickSortin toiminnan graafisena.
Lisäksi vaihtoehtona myös tekstimuotoinen esitys (TextPresenter).

Applettia voi kokeilla osoitteessa:
http://users.utu.fi/hvkhut/koodit/sorterdemo/sorterdemo.html
Lähdekoodit zip-paketissa saa osoitteesta:
http://users.utu.fi/hvkhut/koodit/sorterdemo.zip

Copyright, Henrik Huttunen

AbstractPresenter.java

import java.util.List;

/**
 * Manipulator that shows somehow what client's are manipulating.
 */
public abstract class AbstractPresenter implements Manipulator{
    private Manipulator manipulator;


    public AbstractPresenter(Manipulator manipulator) {
        this.manipulator = manipulator;
    }
    protected abstract <T> void showComparison(int i, int j, List<T> list, String comparator, boolean result);
    protected abstract <T> void showSwapping(int i, int j, List<T> list);

    public <T> void swap(int i, int j, List<T> list) {
        //showSwapping(i, j, list);
        manipulator.swap(i, j, list);
        showSwapping(i, j, list);
    }
    public <T extends Comparable> boolean compareIsSmaller(int i, int j, List<T> list) {
        boolean result = manipulator.compareIsSmaller(i, j, list);
        showComparison(i, j, list, "<", result);
        return result;
    }

    public <T extends Comparable> boolean compareIsSmallerOrEquals(int i, int j, List<T> list) {
        boolean result = manipulator.compareIsSmallerOrEquals(i, j, list);
        showComparison(i, j, list, "<=", result);
        return result;
    }

    public <T extends Comparable> boolean compareEquals(int i, int j, List<T> list) {
        boolean result = manipulator.compareEquals(i, j, list);
        showComparison(i, j, list, "==", result);
        return result;
    }

    public <T extends Comparable> boolean compareDoesNotEqual(int i, int j, List<T> list) {
        boolean result = manipulator.compareDoesNotEqual(i, j, list);
        showComparison(i, j, list, "!=", result);
        return result;
    }

    public <T extends Comparable> boolean compareIsGreater(int i, int j, List<T> list) {
        boolean result = manipulator.compareIsGreater(i, j, list);
        showComparison(i, j, list, ">", result);
        return result;
    }
    public <T extends Comparable> boolean compareIsGreaterOrEquals(int i, int j, List<T> list) {
        boolean result = manipulator.compareIsGreaterOrEquals(i, j, list);
        showComparison(i, j, list, ">=", result);
        return result;
    }
}

BubbleSorter.java

import java.util.List;

/**
 * Bubblesort.
 */
public class BubbleSorter implements Sorter {
    private Manipulator manipulator;

    public <T extends Comparable<T>> void sort(List<T> list) {
        for(int i = 0; i<list.size();++i)
            for(int j=i+1;j<list.size();++j)
            {
                if( manipulator.compareIsGreater(i, j, list) )
                {
                    manipulator.swap(i, j, list);
                }
            }
    }

    public BubbleSorter(Manipulator manipulator) {
        this.manipulator = manipulator;
    }
}

DemonstrationApplet.java

import java.applet.Applet;
import java.awt.*;
import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;

/**
 * Graphical demonstration of sorting.
 */
public class DemonstrationApplet extends Applet implements Runnable, ActionListener {

    private GraphicalSortDemonstration demo;
    private Graph graph;
        private Image backbuffer;
    Thread thread;
    Button nextButton;
    Button autoPlayButton;
    Button manualPlayButton;

    private int waitTime = 500;

    public void init(){
        if(thread != null)
            return;
        thread = new Thread(this);
        this.removeAll();
        initButtons();
    }
    private void startDemo(Waiter waiter)
    {
        initDemo(waiter);
        initThread();
    }
    private void initDemo(Waiter waiter){
        backbuffer = createImage( getSize().width, getSize().height );
        graph = new GraphImpl( backbuffer.getGraphics(), this );
        demo = new GraphicalSortDemonstration(graph, thread, waiter);
    }
    private void initThread()
    {
        thread.start();
    }
    private void initButtons()
    {
        nextButton = new Button("Next step");
        manualPlayButton = new Button("Manual play");
        autoPlayButton = new Button("Auto play");
        nextButton.addActionListener(this);
        autoPlayButton.addActionListener(this);
        manualPlayButton.addActionListener(this);
        add(autoPlayButton);
        add(manualPlayButton);
    }
        public void update(Graphics graphics)
        {
                graphics.drawImage( backbuffer, 0, 0, this );
        }
        public void paint(Graphics graphics)
        {
        update(graphics);
        }
    public void run() {
        demo.run();
    }
    public void actionPerformed(ActionEvent event) {
        if(event.getSource() == nextButton) {
            synchronized(thread){
                thread.notify();
            }
        }else if(event.getSource() == autoPlayButton)
        {
            remove(autoPlayButton);
            remove(manualPlayButton);
            startDemo( new TimeWaiter( waitTime ));
        }else if(event.getSource() == manualPlayButton)
        {
            remove(autoPlayButton);
            remove(manualPlayButton);
            add(nextButton);
            startDemo( new NotifyWaiter( thread ) );
            this.paintAll(getGraphics());
        }
    }
}

Graph.java

import java.awt.*;

/**
 * Interface for drawing.
 */
public interface Graph {
    public void drawLine(Point p1, Point p2, Color color);
    public void drawText(String text, Point p1, Color color);
    public void drawRectangle(Point p1, Point p2, Color color);
    public void update();
}

GraphicalPresenter.java

import java.util.List;
import java.awt.*;
import java.applet.Applet;

/**
 * Shows graphically what client's are manipulating.
 */
public class GraphicalPresenter extends AbstractPresenter{

    private Waiter waiter;
    private Graph graph;
    private Point upperLeft = new Point(0, 60);
    private Point lowerRight = new Point(400, 400);
    private int leftBorder = 100;
    private int topBorder = 100;
    private int textHeight = 10;
    private int lineWidth = 30;
    private int lineDifference = 10; // kuinka kaukana viivan alku on listasta

    public GraphicalPresenter(Manipulator manipulator, Graph graph, Waiter waiter) {
        super(manipulator);
        this.graph = graph;
        this.waiter = waiter;
    }
    protected void waitForNextStep()
    {
        waiter.waitForNext();
    }
    private <T> void drawList(List<T> list)
    {
        graph.drawRectangle(upperLeft, lowerRight, Color.WHITE);
        for(int i=0; i<list.size(); ++i)
        {
            graph.drawText(list.get(i).toString(), new Point(leftBorder, topBorder+i*textHeight), Color.BLACK);
        }
    }
    private <T> void drawText(int index, List<T> list, Color color)
    {
        graph.drawText(list.get(index).toString(), new Point(leftBorder, topBorder+index*textHeight), color);
    }
    private <T> void drawLine(int index, Color color)
    {
        graph.drawLine(new Point(leftBorder-lineWidth, leftBorder-5+index*textHeight), new Point(leftBorder-lineDifference, topBorder-5+index*textHeight), color);
    }
    private <T> void drawVerticalLine(int i, int j, Color color)
    {
        graph.drawLine(new Point(leftBorder-lineWidth, topBorder-5+i*textHeight), new Point(leftBorder-lineWidth, topBorder-5+j*textHeight), color);
    }

    private <T> void drawListWithLines(int i, int j, List<T> list, Color color)
    {
        drawList(list);
        drawText(i, list, color);
        drawText(j, list, color);
        drawLine(i, color);
        drawLine(j, color);
    }
    private <T> void drawComparison(int i, int j, List<T> list, String comparator, boolean result, Color color)
    {
        graph.drawText(list.get(i) + " " + comparator + " " + list.get(j) + ": " + result, new Point(100, 80), color);
    }
    private <T> void drawSwapping(int i, int j, List<T> list, Color color)
    {
        graph.drawText(list.get(i) + " <-> " + list.get(j) + " (swapped)", new Point(100, 80), color);
    }
    protected <T> void showComparison(int i, int j, List<T> list, String comparator, boolean result) {
        if(result)
        {
            drawListWithLines(i, j, list, Color.BLUE);
            drawComparison(i, j, list, comparator, result, Color.BLUE);
        }
        else
        {
            drawListWithLines(i, j, list, Color.RED);
            drawComparison(i, j, list, comparator, result, Color.RED);
        }
        graph.update();
        waitForNextStep();
    }

    protected <T> void showSwapping(int i, int j, List<T> list) {
        drawListWithLines(i, j, list, Color.BLUE);
        drawVerticalLine(i, j, Color.BLUE);
        drawSwapping(i, j, list, Color.BLUE);
        graph.update();
        waitForNextStep();
    }
}

GraphicalSortDemonstration.java

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.applet.Applet;
import java.awt.*;

/**
 * A demonstration of sorting.
 */
public class GraphicalSortDemonstration{
    private Graph graph;
    private Waiter waiter;
    private List<Sorter> sorters = new ArrayList<Sorter>();
    private Manipulator manipulator;
    private Manipulator presenter;
    private Random random = new Random();
    private final int listSize = 12;
    private final int maxNumber = 1000;
    private final int waitTime = 500;

    List<Integer> intList = new ArrayList<Integer>();

    public GraphicalSortDemonstration(Graph graph, Thread thread, Waiter waiter)
    {
        this.graph = graph;
        this.waiter = waiter;
    }
    private void setUp()
    {
        manipulator = new ManipulatorImpl();
        //presenter = new TextPresenter(manipulator);
        presenter = new GraphicalPresenter(manipulator, graph, waiter);
        sorters.add( new BubbleSorter(presenter) );
        sorters.add( new QuickSorter(presenter) );
        setUpList();
    }
    private void setUpList()
    {
        for(int i=0;i<listSize;++i)
        {
            intList.add( random.nextInt(maxNumber) );
        }
    }
    public void run() {
        setUp();
        for(Sorter sorter: sorters)
        {
            graph.drawRectangle(new Point(0, 0), new Point(500, 500), Color.WHITE);
            graph.drawText("Sorting list with " + sorter.getClass().getName(), new Point(50, 50), Color.BLACK);
            sorter.sort(ToolBox.makeACopy(intList));
        }
    }
}

GraphImpl.java

import java.awt.*;
import java.applet.Applet;

/**
 * Implementation of Graph.
 */
public class GraphImpl implements Graph {
    Graphics graphics;
    Applet applet;

    public GraphImpl(Graphics graphics, Applet applet)
    {
        this.graphics = graphics;
        this.applet = applet;
    }
    public void update(){
        applet.repaint();
    }
    public void drawLine(Point p1, Point p2, Color color) {
        graphics.setColor(color);
        graphics.drawLine(p1.getX(), p1.getY(), p2.getX(), p2.getY());
    }

    public void drawText(String text, Point p1, Color color) {
        graphics.setColor(color);
        graphics.drawString(text, p1.getX(), p1.getY());
    }

    // p2.x >= p1.x & p2.y >= p1.y
    public void drawRectangle(Point p1, Point p2, Color color) {
        graphics.setColor(color);
        graphics.fillRect (p1.getX(), p1.getY(), p2.getX()-p1.getX(), p2.getY()-p1.getY());
    }
}

Manipulator.java

import java.util.List;

/**
 * Compares and swaps nodes of the list.
 */
public interface Manipulator {
    public <T> void swap(int i, int j, List<T> list);
    public <T extends Comparable> boolean compareIsSmaller(int i, int j, List<T> list);
    public <T extends Comparable> boolean compareIsSmallerOrEquals(int i, int j, List<T> list);
    public <T extends Comparable> boolean compareEquals(int i, int j, List<T> list);
    public <T extends Comparable> boolean compareDoesNotEqual(int i, int j, List<T> list);
    public <T extends Comparable> boolean compareIsGreater(int i, int j, List<T> list);
    public <T extends Comparable> boolean compareIsGreaterOrEquals(int i, int j, List<T> list);
}

ManipulatorImpl.java

import java.util.List;

/**
 * Implementation of Manipulator.
 */
public class ManipulatorImpl implements Manipulator {
    public <T> void swap(int i, int j, List<T> list) {
        T temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }

    private <T extends Comparable> int compareTo(int i, int j, List<T> list)
    {
        return list.get(i).compareTo(list.get(j));
    }
    public <T extends Comparable> boolean compareIsSmaller(int i, int j, List<T> list) {
         return compareTo(i, j, list) < 0;
    }
    public <T extends Comparable> boolean compareEquals(int i, int j, List<T> list) {
        return compareTo(i, j, list) == 0;
    }
    public <T extends Comparable> boolean compareIsGreater(int i, int j, List<T> list) {
        return compareTo(i, j, list) > 0;
    }
    public <T extends Comparable> boolean compareIsSmallerOrEquals(int i, int j, List<T> list) {
        return compareTo(i, j, list) <= 0;
    }
    public <T extends Comparable> boolean compareDoesNotEqual(int i, int j, List<T> list) {
        return compareTo(i, j, list) != 0;
    }
    public <T extends Comparable> boolean compareIsGreaterOrEquals(int i, int j, List<T> list) {
        return compareTo(i, j, list) >= 0;
    }
}

NotifyWaiter.java

/**
 * Waits until thread is notified.
 */
public class NotifyWaiter implements Waiter {
    private Thread thread;

    public NotifyWaiter(Thread thread)
    {
        this.thread = thread;
    }
    public void waitForNext() {
       synchronized (thread) {
            try{
                thread.wait();
            }catch(InterruptedException e){}
         }
    }
}

Point.java

/**
 * Combining x and y value.
 */
public class Point {
    private int x;
    private int y;

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
    public int getX(){ return x; }
    public int getY(){ return y; }
}

QuickSorter.java

import java.util.List;

/**
 * Quicksort.
 */
public class QuickSorter implements Sorter{

    Manipulator manipulator;
    public QuickSorter(Manipulator manipulator)
    {
        this.manipulator = manipulator;
    }
        /**
         * Sorts list with Quicksort.<br>
         * Average case: O( n log n ).<br>
         * Worst case: n^2.
         */
        public <T extends Comparable<T>> void sort(List<T> list) {
                quickSort(0, list.size()-1, list);
        }
        private <T extends Comparable<T>> void quickSort(int left, int right, List<T> list)
        {
                if(left < right)
                {
                        int middle = partition(left, right, list);

                        quickSort(left, middle - 1, list);
                        quickSort(middle + 1, right, list);
                }
        }
        private <T extends Comparable<T>> int partition(int left, int right, List<T> list)
        {
                int pivot = right;
                int addPlace = left;

                for(int i = left; i < right; ++i)
                {
                        if( manipulator.compareIsSmallerOrEquals(i, pivot, list) )
                        {
                                manipulator.swap(addPlace, i, list);
                                ++addPlace;
                        }
                }
                manipulator.swap(addPlace, right, list);
                return addPlace;
        }
}
Sorter.java

import java.util.List;

/**
 * Sorts list ascending.
 */
public interface Sorter {
    public <T extends Comparable<T>> void sort(List<T> list);
}
TextPresenter.java

import java.util.List;

/**
 * Shows textually what client's are manipulating.
 */
public class TextPresenter extends AbstractPresenter{

    public TextPresenter(Manipulator manipulator) {
        super(manipulator);
    }
    private <T> void printList(int i, int j, List<T> list)
    {
        for(int index=0; index<list.size(); ++index)
        {
            if(index != i & index != j)
            {
                System.out.print(list.get(index)+" ");
            } else{
                System.out.print("|"+list.get(index)+"| ");
            }
        }
    }
    protected <T> void showComparison(int i, int j, List<T> list, String comparator, boolean result) {
        printList(i, j, list);
        System.out.println("[#] " + list.get(i) + " " + comparator + " " + list.get(j) + ": " + result);
    }

    protected <T> void showSwapping(int i, int j, List<T> list) {
        printList(i, j, list);
        System.out.println("[#] " + list.get(i) + " <-> " + list.get(j) + " (swap)");
    }
}

TimeWaiter.java

/**
 * Waits for given time.
 */
public class TimeWaiter implements Waiter{
    private int time;

    public TimeWaiter(int time)
    {
        this.time = time;
    }
    public void waitForNext()
    {
        try{
            Thread.sleep(time);
        }catch(InterruptedException e){}
    }
}

ToolBox.java

import java.util.ArrayList;
import java.util.List;

/**
 * Useful methods.
 */
public class ToolBox {
        /**
         *
         * @param copyableList List to be copied.
         * @return A shallow copy of the given list.
         */
        public static <T> List<T> makeACopy(List<T> copyableList)
        {
                List<T> result = new ArrayList<T>();
                for(T value: copyableList)
                        result.add(value);
                return result;
        }
        /**
         *
         * @param list List to be checked.
         * @return Is list values sorted ascending.
         */
        public static <T extends Comparable<T>> boolean isSortedAscending(List<T> list)
        {
                for(int i=0;i<list.size()-1;++i)
                {
                        if( list.get(i).compareTo(list.get(i+1)) > 0 )
                                return false;
                }
                return true;
        }
}

Waiter.java

/**
 * For waiting different ways.
 */
public interface Waiter {
    public void waitForNext();
}