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; }

}