package algs51; // section 5.1 import java.awt.Color; import algs13.Queue; import stdlib.*; /* ********************************************************************************* * TODO: Implement a modified version of LSD radix sort * that sorts the input tones in O(N) time. * HINT: Consider grouping multiple bits ***********************************************************************************/ public class hw6 { static class RadixSort { public static int[] SortLSD(int[] keys) { // TODO: Implement LSD Radix Sort return keys; } } class SortSounds { private int elements; private int halfWidth; private int scaledHeight; private int step; private static final int HEIGHT = 512; private static final int WIDTH = 1024; /** Lowest and highest frequency sounds that will be played. */ private static final int LOW_TONE = 400; private static final int HIGH_TONE = 800; /** Number of samples to play for each play() operation. Program pauses * while samples are played. As you decrease this number, the animation * will run faster, but eventually you'll start getting ugly sound * artifacts. */ private static final int SAMPLES_TO_PLAY = 1000; /** Number of samples before an instrument is killed. The number of * tones audible at once is MAX_SOUND_AGE / SAMPLES_TO_PLAY. */ private static final int MAX_SOUND_AGE = 1000; /** Default number of items in the array. */ private static final int NUMBER_OF_ITEMS = 64; private int[] toSort; /** Contains all currently active sounds. */ private Queue soundQueue = new Queue(); /** * Default constructor. Initializes visualization with 32 item */ public SortSounds() { this(NUMBER_OF_ITEMS); } /** * Constructor for SortSounds. * @param N number of elements that will be sorted */ public SortSounds(int N) { elements = N; halfWidth = WIDTH / (elements * 2); scaledHeight = HEIGHT /(elements * 2); step = (HIGH_TONE - LOW_TONE) / elements; toSort = new int[elements]; for (int i = 0; i < elements; i++) { toSort[i] = i; } } /** * Draws a rectangle for the visualization. Rectangle is based on the * element of the toSort array at index i * @param c Color of the rectangle * @param i index of the array that is being sorted */ void drawRectangle(Color c, int i) { StdDraw.setPenColor(StdDraw.BLACK); StdDraw.rectangle(halfWidth + halfWidth * 2 * i, toSort[i] * scaledHeight, halfWidth, scaledHeight * (toSort[i] + 1)); StdDraw.setPenColor(c); StdDraw.filledRectangle(halfWidth + halfWidth * 2 * i, toSort[i] * scaledHeight, halfWidth - 0.5, scaledHeight * (toSort[i] + 1) - 0.5); } /** * Clears the rectangle on the visualization. Rectangle is based on the * element of the toSort array at index i * @param i index of the array that is being sorted */ void clearRectangle(int i) { StdDraw.setPenColor(StdDraw.WHITE); StdDraw.rectangle(halfWidth + halfWidth * 2 * i, toSort[i] * scaledHeight, halfWidth, scaledHeight * (toSort[i] + 1)); StdDraw.filledRectangle(halfWidth + halfWidth * 2 * i, toSort[i] * scaledHeight, halfWidth + 0.5, scaledHeight * (toSort[i] + 1) + 0.5); } /** * Adds a new SoundGenerator to the sound queue with frequency given * by the element in position i. Also plays SAMPLES_TO_PLAY of all * sounds in the sound queue. * @param i index of the array */ void play(int i) { double frequency = LOW_TONE + toSort[i] * step; SoundGenerator x = new SoundGenerator(0.1, frequency, MAX_SOUND_AGE); soundQueue.enqueue(x); for (int j = 0; j < SAMPLES_TO_PLAY; j += 1) { double sample = 0; int numberToRemove = 0; for (SoundGenerator gs : soundQueue) { if (gs.age() > MAX_SOUND_AGE) { numberToRemove += 1; } sample += gs.sample(); gs.tic(); } StdAudio.play(sample); for (int k = 0; k < numberToRemove; k += 1) { soundQueue.dequeue(); } } } /** * Initializes the visualization. Sets the order of the elements in the toSort array * Draws the initial rectangles and plays their sounds. Write the current sort on the * top of the screen. */ private void initialize() { StdDraw.clear(); StdRandom.shuffle(toSort); StdDraw.setPenColor(StdDraw.BLACK); StdDraw.show(1000); for (int i = 0; i < elements; i++) { drawRectangle(StdDraw.CYAN, i); StdDraw.show(5); play(i); } } /** * Finishes the visualization by drawing a rainbow of rectangles * and plays their sounds */ private void finish() { StdDraw.clear(); for (int i = 0; i < elements; i++) { if (i % 4 == 3) { drawRectangle(StdDraw.BLUE, i); } else if (i % 4 == 2) { drawRectangle(StdDraw.GREEN, i); } else if (i % 4 == 1) { drawRectangle(StdDraw.YELLOW, i); } else { drawRectangle(StdDraw.RED, i); } play(i); StdDraw.show(5); } } } public class SoundGenerator { private double frequency; private double amplitude; private int lifespan; private int fade_in; private int fade_out; /* Number of times the string has ticced. */ private int age = 0; /* Create a sine wave of the given amplitude and frequency and lifespan in samples. */ public SoundGenerator(double a, double f, int l) { amplitude = a; frequency = f; lifespan = l; fade_in = lifespan / 20; fade_out = lifespan / 20; } /* Returns scaling factor to reduce arrival pop. */ private double envelope() { if (age < fade_in) { return ((double) age) / fade_in; } int lifeLeft = lifespan - age; if (lifeLeft < fade_out) { return ((double) lifeLeft) / fade_out; } return 1; } /* Advance the simulation one time step by increasing age. */ public void tic() { age += 1; } /* Return the double at the front of the buffer. */ public double sample() { return envelope() * amplitude * Math.sin(2 * Math.PI * age * frequency / StdAudio.SAMPLE_RATE); } /* Number of times this string has ticked. */ public int age() { return age; } } /** * Runs the program */ public static void main(String[] args) { int w = SortSounds.WIDTH; int h = SortSounds.HEIGHT; SortSounds ss = new hw6().new SortSounds(256); StdDraw.setCanvasSize(w,h); StdDraw.setXscale(0,w); StdDraw.setYscale(0,h); StdDraw.show(1); ss.initialize(); ss.toSort = RadixSort.SortLSD(ss.toSort); ss.finish(); } }