001: import java.awt.Color;
002: import java.awt.Graphics2D;
003: import java.awt.geom.Line2D;
004: import java.util.concurrent.locks.Lock;
005: import java.util.concurrent.locks.ReentrantLock;
006: import javax.swing.JComponent;
007: 
008: /**
009:    This class sorts an array, using the selection sort 
010:    algorithm.
011: */
012: public class SelectionSorter
013: {
014:    /**
015:       Constructs a selection sorter.
016:       @param anArray the array to sort
017:       @param aComponent the component to be repainted when the animation 
018:       pauses
019:    */
020:    public SelectionSorter(int[] anArray, JComponent aComponent)
021:    {
022:       a = anArray;
023:       sortStateLock = new ReentrantLock();
024:       component = aComponent;
025:    }
026: 
027:    /**
028:       Sorts the array managed by this selection sorter.
029:    */
030:    public void sort() 
031:          throws InterruptedException
032:    {  
033:       for (int i = 0; i < a.length - 1; i++)
034:       {  
035:          int minPos = minimumPosition(i);
036:          sortStateLock.lock();
037:          try
038:          {
039:             swap(minPos, i);
040:             // For animation
041:             alreadySorted = i;
042:          }
043:          finally
044:          {
045:             sortStateLock.unlock();
046:          }
047:          pause(2);
048:       }
049:    }
050: 
051:    /**
052:       Finds the smallest element in a tail range of the array
053:       @param from the first position in a to compare
054:       @return the position of the smallest element in the
055:       range a[from]...a[a.length - 1]
056:    */
057:    private int minimumPosition(int from)
058:          throws InterruptedException
059:    {  
060:       int minPos = from;
061:       for (int i = from + 1; i < a.length; i++)
062:       {
063:          sortStateLock.lock();
064:          try
065:          {
066:             if (a[i] < a[minPos]) minPos = i;
067:             // For animation
068:             markedPosition = i;
069:          }
070:          finally
071:          {
072:             sortStateLock.unlock();
073:          }
074:          pause(2);
075:       }
076:       return minPos;
077:    }
078: 
079:    /**
080:       Swaps two entries of the array.
081:       @param i the first position to swap
082:       @param j the second position to swap
083:    */
084:    private void swap(int i, int j)
085:    {
086:       int temp = a[i];
087:       a[i] = a[j];
088:       a[j] = temp;
089:    }
090: 
091:    /**
092:       Draws the current state of the sorting algorithm.
093:       @param g2 the graphics context
094:    */
095:    public void draw(Graphics2D g2)
096:    {
097:       sortStateLock.lock();
098:       try
099:       {
100:          int deltaX = component.getWidth() / a.length;
101:          for (int i = 0; i < a.length; i++)
102:          {
103:             if (i == markedPosition)
104:                g2.setColor(Color.RED);
105:             else if (i <= alreadySorted)
106:                g2.setColor(Color.BLUE);
107:             else
108:                g2.setColor(Color.BLACK);
109:             g2.draw(new Line2D.Double(i * deltaX, 0, 
110:                   i * deltaX, a[i]));
111:          }
112:       }
113:       finally
114:       {
115:          sortStateLock.unlock();
116:       }
117:    }
118: 
119:    /**
120:       Pauses the animation.
121:       @param steps the number of steps to pause
122:    */
123:    public void pause(int steps) 
124:          throws InterruptedException
125:    {
126:       component.repaint();
127:       Thread.sleep(steps * DELAY);
128:    }
129: 
130:    private int[] a;
131:    private Lock sortStateLock;
132: 
133:    // The component is repainted when the animation is paused
134:    private JComponent component;   
135:    
136:    // These fields are needed for drawing 
137:    private int markedPosition = -1;
138:    private int alreadySorted = -1;
139: 
140:    private static final int DELAY = 100;
141: }