Animazione Bubble Sort

Question

Ultimamente ho notato domande sull'animazione del codice che utilizza un algoritmo di loop. Per esempio:

1. Java: come utilizzare lo swing timer per ritardare le azioni
2. Come rallentare un ciclo for?

Il codice esistente funziona ma mostra solo il risultato finale. Quindi le persone vogliono animare ogni passaggio dell'algoritmo. Viene posta una domanda perché:

1. non sanno come farlo, o
2. un Thread.sleep (...) è stato aggiunto all'algoritmo, per consentire la pittura intermittente, ma il dipinto viene comunque aggiornato solo una volta terminato il ciclo. Ovviamente sappiamo che il problema è che non puoi usare Thread.sleep (...) su EDT.

In entrambi i casi il suggerimento era di utilizzare uno Swing Timer e la domanda è stata chiusa come un duplicato. Ma è così facile?

Il codice seguente mostra un semplice algoritmo Bubble Sort. La logica di ordinamento è semplice e autonoma in un unico metodo e indica dove deve avvenire l'animazione.

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.Timer;

public class BubbleSort extends JPanel
{
    private final static int BAR_WIDTH = 30;
    private final static int BAR_HEIGHT_MAX = 400;

    private int[]items;

    public BubbleSort(int[] items)
    {
        this.items = items;
    }

    public void setItems(int[] items)
    {
        this.items = items;
        repaint();
    }

    public void sort()
    {
        int n = items.length;
        int temp = 0;

        for (int i = 0; i < n; i++)
        {
            for (int j = 1; j < (n - i); j++)
            {
                if (items[j-1] > items[j])
                {
                    temp = items[j - 1];
                    items[j - 1] = items[j];
                    items[j] = temp;
                    
                    // paint current state for animation
                                                                        
                    repaint();
                    try { Thread.sleep(100); } catch (Exception e) {}
                }
            }
        }
    }

    @Override
    protected void paintComponent(Graphics g)
    {
        super.paintComponent(g);

        for (int i = 0; i < items.length; i++)
        {
            int x = i * BAR_WIDTH;
            int y = getHeight() - items[i];

            g.setColor( Color.RED );
            g.fillRect(x, y, BAR_WIDTH, items[i]);

            g.setColor( Color.BLUE );
            g.drawString("" + items[i], x, y);
        }
    }

    @Override
    public Dimension getPreferredSize()
    {
        return new Dimension(items.length * BAR_WIDTH, BAR_HEIGHT_MAX + 20);
    }

    public static int[]generateRandomNumbers()
    {
        int[] items = new int[10];

        for(int i = 0; i < items.length; i++)
        {
            items[i] = (int)(Math.random() * BubbleSort.BAR_HEIGHT_MAX);
        }

        return items;
    }

    private static void createAndShowGUI()
    {
        BubbleSort bubbleSort = new BubbleSort( BubbleSort.generateRandomNumbers() );

        JButton generate = new JButton("Generate Data");
        generate.addActionListener((e) -> bubbleSort.setItems( BubbleSort.generateRandomNumbers() ) );

        JButton sort = new JButton("Sort Data");
        sort.addActionListener((e) -> bubbleSort.sort());

        JPanel bottom = new JPanel();
        bottom.add( generate );
        bottom.add( sort );

        JFrame frame = new JFrame("SSCCE");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(bubbleSort, BorderLayout.CENTER);
        frame.add(bottom, BorderLayout.PAGE_END);
        frame.pack();
        frame.setLocationByPlatform( true );
        frame.setVisible( true );
    }

    public static void main(String[] args) throws Exception
    {
        EventQueue.invokeLater( () -> createAndShowGUI() );
    }
}

Quindi le domande sono:

1. Come si può modificare il codice per utilizzare uno Swing Timer? Quali suggerimenti / indicazioni hai?
2. Esistono altri approcci che possono essere utilizzati al posto dello Swing Timer?

Answer 1

Un altro approccio potrebbe essere quello di utilizzare uno SwingWorker.

SwingWorker crea sequenze nel proprio thread e consente di "pubblicare" risultati intermittenti da disegnare.

La chiave dell'approccio seguente è che una copia dei dati viene passata a SwingWorker. Ciò consente al lavoratore di ordinare i dati mentre i dati vengono ridipinti in modo da non doversi preoccupare che i dati nell'array siano in uno stato incoerente.

Dopo ogni iterazione del codice del ciclo, il nuovo stato dell'array viene aggiornato in modo che possa essere disegnato.

Ciò consente di spostare facilmente la logica di ordinamento in SwingWorker senza refactoring.

import java.awt.*;
import java.awt.event.*;
import java.util.Arrays;
import java.util.List;
import javax.swing.*;
import javax.swing.Timer;

public class BubbleSortWorker extends JPanel
{
    private final static int BAR_WIDTH = 30;
    private final static int BAR_HEIGHT_MAX = 400;

    private int[]items;

    public BubbleSortWorker(int[] items)
    {
        this.items = items;
    }

    public void setItems(int[] items)
    {
        this.items = items;
        repaint();
    }

    public void sort()
    {
        new SortWorker(items).execute();
    }

    @Override
    protected void paintComponent(Graphics g)
    {
        super.paintComponent(g);

        for (int i = 0; i < items.length; i++)
        {
            int x = i * BAR_WIDTH;
            int y = getHeight() - items[i];

            g.setColor( Color.RED );
            g.fillRect(x, y, BAR_WIDTH, items[i]);

            g.setColor( Color.BLUE );
            g.drawString("" + items[i], x, y);
        }
    }

    @Override
    public Dimension getPreferredSize()
    {
        return new Dimension(items.length * BAR_WIDTH, BAR_HEIGHT_MAX + 20);
    }

    class SortWorker extends SwingWorker<Void, int[]>
    {
        private int[] items;

        public SortWorker(int[] unsortedItems)
        {
            items = Arrays.copyOf(unsortedItems, unsortedItems.length);
        }

        @Override
        protected Void doInBackground()
        {
            int n = items.length;
            int temp = 0;

            for (int i = 0; i < n; i++)
            {
                for (int j = 1; j < (n - i); j++)
                {
                    if (items[j-1] > items[j])
                    {
                        temp = items[j - 1];
                        items[j - 1] = items[j];
                        items[j] = temp;

                        //repaint();
                        publish( Arrays.copyOf(items, items.length) );

                        try { Thread.sleep(100); } catch (Exception e) {}
                    }
                }
            }

            return null;
        }

        @Override
        protected void process(List<int[]> list)
        {
            int[] items = list.get(list.size() - 1);
            setItems( items );
        }

        @Override
        protected void done() {}
    }

    public static int[]generateRandomNumbers()
    {
        int[] items = new int[10];

        for(int i = 0; i < items.length; i++)
        {
            items[i] = (int)(Math.random() * BubbleSortWorker.BAR_HEIGHT_MAX);
        }

        return items;
    }

    private static void createAndShowGUI()
    {
        BubbleSortWorker bubbleSort = new BubbleSortWorker( BubbleSortWorker.generateRandomNumbers() );

        JButton generate = new JButton("Generate Data");
        generate.addActionListener((e) -> bubbleSort.setItems( BubbleSortWorker.generateRandomNumbers() ) );

        JButton sort = new JButton("Sort Data");
        sort.addActionListener((e) -> bubbleSort.sort());

        JPanel bottom = new JPanel();
        bottom.add( generate );
        bottom.add( sort );

        JFrame frame = new JFrame("SSCCE");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(bubbleSort, BorderLayout.CENTER);
        frame.add(bottom, BorderLayout.PAGE_END);
        frame.pack();
        frame.setLocationByPlatform( true );
        frame.setVisible( true );
    }

    public static void main(String[] args) throws Exception
    {
        EventQueue.invokeLater( () -> createAndShowGUI() );
    }
}

Answer 2

Uno Swing Timer funziona su codice basato su eventi. Pertanto il codice iterativo deve essere sottoposto a refactoring in codice basato su eventi.

Alcune cose da considerare durante questo processo:

1. lo stato deve essere aggiunto all'algoritmo. Ciò significa che tutte le variabili locali utilizzate per controllare l'algoritmo di looping devono essere convertite in variabili di istanza della classe.

2. l'algoritmo di looping deve essere suddiviso in due metodi, il primo per impostare lo stato iniziale dell'algoritmo e avviare il timer, e il secondo metodo per aggiornare lo stato e arrestare il timer.

Utilizzando il suggerimento sopra, il refactoring del codice potrebbe essere qualcosa di simile:

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class BubbleSortTimer extends JPanel
{
    private final static int BAR_WIDTH = 30;
    private final static int BAR_HEIGHT_MAX = 400;

    private int[]items;
    private int i, j, n;
    private Timer timer;

    public BubbleSortTimer(int[] items)
    {
        this.items = items;

        timer = new Timer(100, (e) -> nextIteration());
    }

    public void setItems(int[] items)
    {
        this.items = items;
        repaint();
    }

    public void sort()
    {
        i = 0;
        j = 1;
        n = items.length;

        timer.start();
    }

    public void nextIteration()
    {
        if (items[j - 1] > items[j])
        {
            int temp = items[j - 1];
            items[j - 1] = items[j];
            items[j] = temp;

            repaint();
        }

        j++;

        if (j >= n - i)
        {
            j = 1;
            i++;
        }

        if (i == n)
            timer.stop();
    }

    @Override
    protected void paintComponent(Graphics g)
    {
        super.paintComponent(g);

        for (int i = 0; i < items.length; i++)
        {
            int x = i * BAR_WIDTH;
            int y = getHeight() - items[i];

            g.setColor( Color.RED );
            g.fillRect(x, y, BAR_WIDTH, items[i]);

            g.setColor( Color.BLUE );
            g.drawString("" + items[i], x, y);
        }
    }

    @Override
    public Dimension getPreferredSize()
    {
        return new Dimension(items.length * BAR_WIDTH, BAR_HEIGHT_MAX + 20);
    }

    public static int[]generateRandomNumbers()
    {
        int[] items = new int[10];

        for(int i = 0; i < items.length; i++)
        {
            items[i] = (int)(Math.random() * BubbleSortTimer.BAR_HEIGHT_MAX);
        }

        return items;
    }

    private static void createAndShowGUI()
    {
        BubbleSortTimer bubbleSort = new BubbleSortTimer( BubbleSortTimer.generateRandomNumbers() );

        JButton generate = new JButton("Generate Data");
        generate.addActionListener((e) -> bubbleSort.setItems( BubbleSortTimer.generateRandomNumbers() ) );

        JButton sort = new JButton("Sort Data");
        sort.addActionListener((e) -> bubbleSort.sort());

        JPanel bottom = new JPanel();
        bottom.add( generate );
        bottom.add( sort );

        JFrame frame = new JFrame("SSCCE");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(bubbleSort, BorderLayout.CENTER);
        frame.add(bottom, BorderLayout.PAGE_END);
        frame.pack();
        frame.setLocationByPlatform( true );
        frame.setVisible( true );
    }

    public static void main(String[] args) throws Exception
    {
        EventQueue.invokeLater( () -> createAndShowGUI() );
    }
}