I am trying to code a sorting algorithm visualizer. I put almost everything into one class called visualizer and I was wondering how I can move my "insertionSort" and "bubbleSort" methods into separate classes without breaking my code?
I want to do this because when I integrate merge sort and quick sort I want to keep them in the same class as there helper methods.
public class Visualizer extends JPanel implements ActionListener{
//Initialize Variables
final int SCREEN_WIDTH = 1280;
final int SCREEN_HEIGHT = 720;
final int BAR_HEIGHT = SCREEN_HEIGHT * 4/5;
final int BAR_WIDTH = 5;
final int NUM_BARS = SCREEN_WIDTH/BAR_WIDTH;
JButton bubbleSort = new JButton();
JButton insertSort = new JButton();
SwingWorker<Void,Void> shuffler, sorter;
int[] array = new int[NUM_BARS];
int current;
int traverse;
public Visualizer() {
setBackground(Color.darkGray);
setPreferredSize(new Dimension());
//Initialize Bar Height
for (int i = 0; i < NUM_BARS; i ) {
array[i] = i * BAR_HEIGHT / NUM_BARS;
}
//InsertionSort Button
insertSort.setText("Insertion Sort");
this.add(insertSort);
insertSort.addActionListener(this);
//BubbleSort Button
bubbleSort.setText("Bubble Sort");
this.add(bubbleSort);
bubbleSort.addActionListener(this);
}
public void shuffleArray() {
shuffler = new SwingWorker<Void, Void>() {
@Override
protected Void doInBackground() throws InterruptedException {
Random random = new Random();
for (int i = 0; i < NUM_BARS; i ) {
int swap = random.nextInt(NUM_BARS - 1);
swap(i, swap);
Thread.sleep(10);
repaint();
}
return null;
}
@Override
public void done() {
super.done();
sorter.execute();
}
};
shuffler.execute();
}
public void insertionSort() {
sorter = new SwingWorker<Void, Void>() {
@Override
public Void doInBackground() throws InterruptedException {
for (current = 1; current < NUM_BARS; current ) {
traverse = current;
while (traverse > 0 && array[traverse] < array[traverse - 1]) {
swap(traverse, traverse - 1);
traverse--;
Thread.sleep(1);
repaint();
}
}
current = 0;
traverse = 0;
return null;
}
};
}
public void bubbleSort() {
sorter = new SwingWorker<Void, Void>() {
@Override
public Void doInBackground() throws InterruptedException {
for(current = 0; current < NUM_BARS; current ) {
for(traverse = 1; traverse < (NUM_BARS - current); traverse ) {
if(array[traverse-1] > array[traverse]) {
swap(traverse, traverse-1);
traverse--;
Thread.sleep(1);
repaint();
}
}
}
current = 0;
traverse = 0;
return null;
}
};
}
public void quickSort() {
sorter = new SwingWorker<Void, Void>() {
@Override
public Void doInBackground() throws InterruptedException {
return null;
}
};
}
public void swap(int indexOne, int indexTwo) {
int temp = array[indexOne];
array[indexOne] = array[indexTwo];
array[indexTwo] = temp;
}
@Override
public void paintComponent(Graphics g) {
Graphics2D graphics = (Graphics2D)g;
super.paintComponent(graphics);
g.setColor(Color.white);
for(int i = 0; i < NUM_BARS; i ) {
graphics.fillRect(i * BAR_WIDTH,SCREEN_HEIGHT-array[i],BAR_WIDTH,array[i]);
}
g.setColor(Color.green);
graphics.fillRect(current*BAR_WIDTH,SCREEN_HEIGHT-array[current], BAR_WIDTH, array[current]);
g.setColor(Color.red);
graphics.fillRect(traverse*BAR_WIDTH,SCREEN_HEIGHT-array[traverse], BAR_WIDTH, array[traverse]);
}
@Override
public void actionPerformed(ActionEvent e) {
if (e.getSource() == insertSort) {
insertionSort();
shuffleArray();
}
else if (e.getSource() == bubbleSort) {
bubbleSort();
shuffleArray();
}
}
}
CodePudding user response：
This is not as easy as it might seem, but, the basic answer comes down to making use of models and observers (something like the "model-view-controller" concept), so you can decouple the workflows in a more meaningful way.
One important note to make is, Swing is NOT thread save. This means that you should not be modifying the UI or any state the UI relies on from out side the context the Event Dispatching Thread. Under your current workflow it's possible for the SwingWorker to modify the state of the array (and other state values) while the UI is been painted, this could cause no end of issues.
The core functionality of a sorter is basically the same, it needs some values, needs to be able to swap those values and needs to deliver notifications to interested parties that some kind of state has changed.
public interface Sorter {
public interface Observer {
public void swap(int from, int to);
public void setCurrent(int current);
public void setTraverse(int traverse);
}
public int[] sort(int[] values, Observer observer);
}
Okay, pretty basic, but the nice idea behind this anything that changes the values can be used, for example, we can shuffle the values through the interface...
public class ShuffleSorter extends AbstractSorter {
@Override
public int[] sort(int[] original, Observer observer) {
int[] values = Arrays.copyOf(original, original.length);
Random random = new Random();
for (int i = 0; i < values.length; i ) {
int swap = random.nextInt(values.length - 1);
fireSetCurrent(observer, i);
fireSetTraverse(observer, i);
Helper.swap(values, i, swap);
fireSwap(observer, i, swap);
try {
Thread.sleep(5);
} catch (InterruptedException ex) {
}
}
return values;
}
}
And the insertion sorter...
public class InsertionSorter extends AbstractSorter {
@Override
public int[] sort(int[] original, Observer observer) {
int[] values = Arrays.copyOf(original, original.length);
for (int current = 1; current < values.length; current ) {
int traverse = current;
fireSetCurrent(observer, current);
fireSetTraverse(observer, traverse);
while (traverse > 0 && values[traverse] < values[traverse - 1]) {
Helper.swap(values, traverse, traverse - 1);
fireSwap(observer, traverse, traverse - 1);
traverse--;
fireSetTraverse(observer, traverse);
try {
Thread.sleep(5);
} catch (InterruptedException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
fireSetCurrent(observer, values.length - 1);
fireSetTraverse(observer, values.length - 1);
return values;
}
}
The idea here is the sorters will generate events telling what's changed, so you can apply those changes to the view independently of the sorters, so you don't risk dirty updates.
And finally, the SwingWorker
public class SortWorker extends SwingWorker<Void, Void> {
private Sorter sorter;
private int[] values;
private Sorter.Observer observer;
public SortWorker(int[] values, Sorter sorter, Sorter.Observer observer) {
this.sorter = sorter;
this.values = values;
this.observer = observer;
}
@Override
protected Void doInBackground() throws Exception {
int[] shuffled = new ShuffleSorter().sort(values, observer);
sorter.sort(shuffled, observer);
return null;
}
}
Now, this will shuffle the values and the re-sort them as a single unit of work.
Runnable example...
import java.awt.Color;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.beans.PropertyChangeEvent;
import java.beans.PropertyChangeListener;
import java.util.Arrays;
import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
import javax.swing.SwingWorker;
public class Main {
public static void main(String[] args) {
new Main();
}
public Main() {
EventQueue.invokeLater(new Runnable() {
@Override
public void run() {
JFrame frame = new JFrame();
frame.add(new SortPane());
frame.pack();
frame.setLocationRelativeTo(null);
frame.setVisible(true);
}
});
}
public class SortPane extends JPanel {
final int SCREEN_WIDTH = 1280;
final int SCREEN_HEIGHT = 720;
final int BAR_HEIGHT = SCREEN_HEIGHT * 4 / 5;
final int BAR_WIDTH = 5;
final int NUM_BARS = SCREEN_WIDTH / BAR_WIDTH;
private JButton bubbleSort = new JButton();
private JButton insertSort = new JButton();
private int[] values = new int[NUM_BARS];
private int current = 0;
private int traverse = 0;
public SortPane() {
for (int i = 0; i < NUM_BARS; i ) {
values[i] = i * BAR_HEIGHT / NUM_BARS;
}
//InsertionSort Button
insertSort.setText("Insertion Sort");
this.add(insertSort);
insertSort.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
insertSort.setEnabled(false);
bubbleSort.setEnabled(false);
current = 0;
traverse = 0;
SortWorker sortWorker = new SortWorker(values, new InsertionSorter(), new Sorter.Observer() {
@Override
public void swap(int from, int to) {
SwingUtilities.invokeLater(() -> {
Helper.swap(values, from, to);
repaint();
});
}
@Override
public void setCurrent(int current) {
SwingUtilities.invokeLater(() -> {
SortPane.this.current = current;
repaint();
});
}
@Override
public void setTraverse(int traverse) {
SwingUtilities.invokeLater(() -> {
SortPane.this.traverse = traverse;
repaint();
});
}
});
sortWorker.addPropertyChangeListener(new PropertyChangeListener() {
@Override
public void propertyChange(PropertyChangeEvent evt) {
if (sortWorker.getState() == SwingWorker.StateValue.DONE) {
insertSort.setEnabled(true);
bubbleSort.setEnabled(true);
}
}
});
sortWorker.execute();
}
});
//BubbleSort Button
bubbleSort.setText("Bubble Sort");
this.add(bubbleSort);
bubbleSort.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
}
});
}
@Override
public Dimension getPreferredSize() {
return new Dimension(SCREEN_WIDTH, SCREEN_HEIGHT);
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2d = (Graphics2D) g.create();
g.setColor(Color.white);
for (int i = 0; i < values.length; i ) {
g2d.fillRect(i * BAR_WIDTH, SCREEN_HEIGHT - values[i], BAR_WIDTH, values[i]);
}
g2d.setColor(Color.green);
g2d.fillRect(current * BAR_WIDTH, SCREEN_HEIGHT - values[current], BAR_WIDTH, values[current]);
g2d.setColor(Color.red);
g2d.fillRect(traverse * BAR_WIDTH, SCREEN_HEIGHT - values[traverse], BAR_WIDTH, values[traverse]);
g2d.dispose();
}
}
public class Helper {
public static void swap(int[] values, int indexOne, int indexTwo) {
int temp = values[indexOne];
values[indexOne] = values[indexTwo];
values[indexTwo] = temp;
}
}
public interface Sorter {
public interface Observer {
public void swap(int from, int to);
public void setCurrent(int current);
public void setTraverse(int traverse);
}
public int[] sort(int[] values, Observer observer);
}
public abstract class AbstractSorter implements Sorter {
protected void fireSwap(Observer obserer, int from, int to) {
obserer.swap(from, to);
}
protected void fireSetCurrent(Observer obserer, int current) {
obserer.setCurrent(current);
}
protected void fireSetTraverse(Observer obserer, int traverse) {
obserer.setTraverse(traverse);
}
}
public class ShuffleSorter extends AbstractSorter {
@Override
public int[] sort(int[] original, Observer observer) {
int[] values = Arrays.copyOf(original, original.length);
Random random = new Random();
for (int i = 0; i < values.length; i ) {
int swap = random.nextInt(values.length - 1);
fireSetCurrent(observer, i);
fireSetTraverse(observer, i);
Helper.swap(values, i, swap);
fireSwap(observer, i, swap);
try {
Thread.sleep(5);
} catch (InterruptedException ex) {
}
}
return values;
}
}
public class InsertionSorter extends AbstractSorter {
@Override
public int[] sort(int[] original, Observer observer) {
int[] values = Arrays.copyOf(original, original.length);
for (int current = 1; current < values.length; current ) {
int traverse = current;
fireSetCurrent(observer, current);
fireSetTraverse(observer, traverse);
while (traverse > 0 && values[traverse] < values[traverse - 1]) {
Helper.swap(values, traverse, traverse - 1);
fireSwap(observer, traverse, traverse - 1);
traverse--;
fireSetTraverse(observer, traverse);
try {
Thread.sleep(5);
} catch (InterruptedException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
fireSetCurrent(observer, values.length - 1);
fireSetTraverse(observer, values.length - 1);
return values;
}
}
public class SortWorker extends SwingWorker<Void, Void> {
private Sorter sorter;
private int[] values;
private Sorter.Observer observer;
public SortWorker(int[] values, Sorter sorter, Sorter.Observer observer) {
this.sorter = sorter;
this.values = values;
this.observer = observer;
}
@Override
protected Void doInBackground() throws Exception {
int[] shuffled = new ShuffleSorter().sort(values, observer);
sorter.sort(shuffled, observer);
return null;
}
}
}
Food for thought...
A different approach would be to sort the values and in the process generate a series of "events" which describe what actions are been carried out. This would allow you to take the same starting data and apply those actions in a more controlled manner (using a Swing Timer for example). This would reduce some of the overhead of having to copy the array data each time an update occurs.
If you're interested, I've done an example here
CodePudding user response：
An slightly simpler alternative to (though based on an intermediate state of) MadProgrammer's answer - the intention is to use as few custom notification patterns/classes as possible (== zero :)
The collaborators:
- an immutable SorterModel to encapsulate the current sort progress (same as intermediate in the other answer)
- a custom Worker does the sorting in the background and publishes intermediate sort states as property changes: there's a base class for doing the bookkeeping and notification, subclasses are specialized on a concrete actual (un-) sort algorithm
- a custom panel to visualize a SorterModel and logic to trigger a sort and to update itself according to the changes reported from the worker
The Worker is very similar to the intermediate in the other answer, differs in how it publishes its values: here it uses its own property change api to notify interested parties.
@Override
protected void process(List<SorterModel> chunks) {
SorterModel last = chunks.get(chunks.size() - 1);
firePropertyChange("value", null, last);
}
Subclasses simply use the standard mechanism to publish intermediate result
@Override
protected SorterModel doInBackground() throws Exception {
// do sorting step
publish(new SorterModel(<current state>));
..
}
The custom panel is very similar to the other answer, except for the logic to start sorting / update visual state. Now that's extracted (from the button's action listeners) into a separate method to configure a specialized worker, register a property change listener and update the view's model (and related state like button enable) in that listener:
private void process(SortWorker worker, SortWorker next) {
updateEnabled(false);
worker.setModel(getSorterModel());
worker.addPropertyChangeListener(new PropertyChangeListener() {
@Override
public void propertyChange(PropertyChangeEvent evt) {
if ("value".equals(evt.getPropertyName())) {
setSorterModel((SorterModel) evt.getNewValue());
}
if (SwingWorker.StateValue.DONE == evt.getNewValue()) {
try {
setSorterModel(worker.get());
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
if (next != null) {
process(next, null);
} else {
updateEnabled(true);
}
}
}
});
worker.execute();
}
It's usage from a buttons action might be:
insertSort.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
process(new ShuffleWorker(), new InsertionSortWorker());
}
});
Note:
- the sort classes (worker/model) are unaware of who is using them and do not require a custom observer/n
- the sort trigger/update logic is decoupled from the view - all it needs is a source/target for the model and some enablement toggle. It still resides in the view, though - being lazy, and we had to subclass anyway for custom painting.
Pulling all together into a runnable example:
package so.notfx.swing;
public class SortAnimation {
public class SortPane extends JPanel {
final int SCREEN_WIDTH = 800;
final int SCREEN_HEIGHT = 600;
final int BAR_HEIGHT = SCREEN_HEIGHT * 4 / 5;
final int BAR_WIDTH = 5;
final int NUM_BARS = SCREEN_WIDTH / BAR_WIDTH;
private JButton shuffle = new JButton();
private JButton bubbleSort = new JButton();
private JButton insertSort = new JButton();
private int[] values = new int[NUM_BARS];
private SorterModel model;
public SortPane() {
for (int i = 0; i < NUM_BARS; i ) {
values[i] = i * BAR_HEIGHT / NUM_BARS;
}
model = new SorterModel(values, 0, 0);
// shuffle button to trigger random values
shuffle.setText("Shuffle Values");
add(shuffle);
shuffle.addActionListener(e -> {
process(new ShuffleWorker(), null);
});
// InsertionSort Button
insertSort.setText("Insertion Sort");
this.add(insertSort);
insertSort.addActionListener(e -> {
process(new ShuffleWorker(), new InsertionSortWorker());
});
// BubbleSort Button
bubbleSort.setText("Bubble Sort");
this.add(bubbleSort);
bubbleSort.addActionListener(e -> {
// NYI
});
}
//--------------- sort related
public void setSorterModel(SorterModel model) {
this.model = model;
repaint();
}
public SorterModel getSorterModel() {
return model;
}
private void updateEnabled(boolean enabled) {
shuffle.setEnabled(enabled);
insertSort.setEnabled(enabled);
bubbleSort.setEnabled(enabled);
}
private void process(SortWorker worker, SortWorker next) {
updateEnabled(false);
worker.setModel(getSorterModel());
worker.addPropertyChangeListener(new PropertyChangeListener() {
@Override
public void propertyChange(PropertyChangeEvent evt) {
if ("value".equals(evt.getPropertyName())) {
setSorterModel((SorterModel) evt.getNewValue());
}
if (SwingWorker.StateValue.DONE == evt.getNewValue()) {
try {
setSorterModel(worker.get());
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
if (next != null) {
process(next, null);
} else {
updateEnabled(true);
}
}
}
});
worker.execute();
}
//------------------------
@Override
public Dimension getPreferredSize() {
return new Dimension(SCREEN_WIDTH, SCREEN_HEIGHT);
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2d = (Graphics2D) g.create();
g.setColor(Color.white);
for (int i = 0; i < model.length(); i ) {
g2d.fillRect(i * BAR_WIDTH, SCREEN_HEIGHT - model.valueAt(i), BAR_WIDTH, model.valueAt(i));
}
int current = model.getCurrent();
g2d.setColor(Color.green);
g2d.fillRect(current * BAR_WIDTH, SCREEN_HEIGHT - model.valueAt(current), BAR_WIDTH,
model.valueAt(current));
int traverse = model.getTraverse();
g2d.setColor(Color.red);
g2d.fillRect(traverse * BAR_WIDTH, SCREEN_HEIGHT - model.valueAt(traverse), BAR_WIDTH,
model.valueAt(traverse));
g2d.dispose();
}
}
public static void main(String[] args) {
new SortAnimation();
}
public SortAnimation() {
EventQueue.invokeLater(new Runnable() {
@Override
public void run() {
JFrame frame = new JFrame();
frame.add(new SortPane());
frame.pack();
frame.setLocationRelativeTo(null);
frame.setVisible(true);
}
});
}
}
which is using the support class:
package so.notfx.swing;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import javax.swing.SwingWorker;
/**
* Utility class for sort animation.
* Contains a SorterModel with current sort state and workers that are doing
* the sorting on the background thread and publishing intermediate results
* as property changes with name "value".
*/
public class SortAnimationSupport {
/**
* Base class: bookkeeping, helper and publish a property change for its value. Subclasses are supposed to
* implement the actual sorting in the background and publish a new SorterModel with the current sort
* state when appropriate.
*/
public static abstract class SortWorker extends SwingWorker<SorterModel, SorterModel> {
int[] values;
public void setModel(SorterModel model) {
if (getState() != StateValue.PENDING)
throw new IllegalStateException("model must not be modified after starting the worker");
values = Arrays.copyOf(model.getValues(), model.getValues().length);
}
@Override
protected void process(List<SorterModel> chunks) {
SorterModel last = chunks.get(chunks.size() - 1);
firePropertyChange("value", null, last);
}
protected void swap(int indexOne, int indexTwo) {
int temp = values[indexOne];
values[indexOne] = values[indexTwo];
values[indexTwo] = temp;
}
}
/**
* Use insertion sort.
*/
public static class InsertionSortWorker extends SortWorker {
@Override
protected SorterModel doInBackground() throws Exception {
for (int current = 1; current < values.length; current ) {
int traverse = current;
while (traverse > 0 && values[traverse] < values[traverse - 1]) {
swap(traverse, traverse - 1);
traverse--;
publish(new SorterModel(values, current, traverse));
Thread.sleep(5);
}
}
SorterModel model = new SorterModel(values, values.length - 1, values.length - 1);
publish(model);
return model;
}
}
/**
* Unsort.
*/
public static class ShuffleWorker extends SortWorker {
@Override
protected SorterModel doInBackground() throws Exception {
Random random = new Random();
for (int i = 0; i < values.length; i ) {
int swap = random.nextInt(values.length - 1);
swap(i, swap);
publish(new SorterModel(values, i, 0));
Thread.sleep(5);
}
SorterModel model = new SorterModel(values, values.length - 1, 0);
publish(model);
return model;
}
}
/**
* SorterModel: encapsulates the state of a sort process.
* Note: it has to keep its values immutable, so copying the array
*/
public static class SorterModel {
protected int[] values;
protected int current;
protected int traverse;
public SorterModel(int[] array, int current, int traverse) {
this.values = Arrays.copyOf(array, array.length);
this.current = current;
this.traverse = traverse;
}
public int[] getValues() {
return Arrays.copyOf(values, values.length);
}
public int length() {
return values.length;
}
public int valueAt(int index) {
return values[index];
}
public int getCurrent() {
return current;
}
public int getTraverse() {
return traverse;
}
}
private SortAnimationSupport() {
}
}