diff options
Diffstat (limited to 'labs')
44 files changed, 3907 insertions, 0 deletions
diff --git a/labs/lab01_pair/.Pair.java.swp b/labs/lab01_pair/.Pair.java.swp Binary files differnew file mode 100644 index 0000000..6cd3b15 --- /dev/null +++ b/labs/lab01_pair/.Pair.java.swp diff --git a/labs/lab01_pair/GraphComponent.java b/labs/lab01_pair/GraphComponent.java new file mode 100644 index 0000000..089b76a --- /dev/null +++ b/labs/lab01_pair/GraphComponent.java @@ -0,0 +1,139 @@ +import java.awt.Color; +import java.awt.Graphics; +import java.awt.Graphics2D; +import java.awt.geom.Line2D; +import java.util.ArrayList; +import javax.swing.JComponent; + +@SuppressWarnings("serial") +public class GraphComponent extends JComponent +{ + private int leftMargin = 10; + private int rightMargin = 10; + private int topMargin = 10; + private int bottomMargin = 10; + private double largest; + private double largestX; + private double smallestX; + private double largestY; + private double smallestY; + private int numData; + private int width; + private int height; + private ArrayList<PairInterface<Double,Double>> data; + + public GraphComponent(ArrayList<PairInterface<Double,Double>> aData) + { + data = aData; + numData = data.size(); + PairInterface<Double,Double> tempData = data.get(0); + + largestX = tempData.fst(); + smallestX = largestX; + largestY = tempData.snd(); + smallestY = largestY; + + for(int i = 1; i < numData; i++) + { + tempData = data.get(i); + + if(largestX < tempData.fst()) + { + largestX = tempData.fst(); + } + + if(smallestX > tempData.fst()) + { + smallestX = tempData.fst(); + } + + if(largestY < tempData.snd()) + { + largestY = tempData.snd(); + } + + if(smallestY > tempData.snd()) + { + smallestY = tempData.snd(); + } + } + + if(Math.abs(largestX) < Math.abs(smallestX)) + { + largestX = Math.abs(smallestX); + } + else + { + largestX = Math.abs(largestX); + } + + if(Math.abs(largestY) < Math.abs(smallestY)) + { + largestY = Math.abs(smallestY); + } + else + { + largestY = Math.abs(largestY); + } + + if(largestX > largestY) + { + largest = largestX; + } + else + { + largest = largestY; + } + } + + public void paintComponent(Graphics g) + { + Graphics2D g2 = (Graphics2D) g; + + width = this.getWidth(); + height = this.getHeight(); + + + + Line2D.Double line = new Line2D.Double(0,0,0,0); + + // Draw Axis; + + g2.setColor(Color.BLACK); + + line.setLine(getX(0),getY(0),getX(-largest),getY(0)); + g2.draw(line); + line.setLine(getX(0),getY(0),getX(0),getY(largest)); + g2.draw(line); + line.setLine(getX(0),getY(0),getX(largest),getY(0)); + g2.draw(line); + line.setLine(getX(0),getY(0),getX(0),getY(-largest)); + g2.draw(line); + + // Draw frequency the graph + + g2.setColor(Color.GREEN); + + for(int i = 0; i < numData - 1; i++) + { + line.setLine(getX(data.get(i).fst()), getY(data.get(i).snd()), getX(data.get(i + 1).fst()), getY(data.get(i + 1).snd())); + g2.draw(line); + } + } + + public int getX(double aValue) + { + int numberOfPixels = width - (leftMargin + rightMargin); + double range = largest + largest; + double deltaWidth = numberOfPixels / range; + return (int) ((aValue + largest) * deltaWidth) + leftMargin; + } + + public int getY(double aValue) + { + int numberOfPixels = height - (topMargin + bottomMargin); + double range = largest + largest; + double deltaWidth = numberOfPixels / range; + return (int) ((-aValue + largest) * deltaWidth) + topMargin; + } +} diff --git a/labs/lab01_pair/Pair.java b/labs/lab01_pair/Pair.java new file mode 100644 index 0000000..ef49c76 --- /dev/null +++ b/labs/lab01_pair/Pair.java @@ -0,0 +1,83 @@ + +public class Pair<T1,T2> implements PairInterface<T1,T2> +{ + // TO DO: Instance Variables + T1 one; + T2 two; + + public Pair(T1 aFirst, T2 aSecond) + { + one = aFirst; + two = aSecond; + } + + /** + * Gets the first element of this pair. + * @return the first element of this pair. + */ + public T1 fst() + { + return one; + } + + /** + * Gets the second element of this pair. + * @return the second element of this pair. + */ + public T2 snd() + { + return two; + } + + /** + * Sets the first element to aFirst. + * @param aFirst the new first element + */ + public void setFst(T1 aFirst) + { + one = aFirst; + } + + /** + * Sets the second element to aSecond. + * @param aSecond the new second element + */ + public void setSnd(T2 aSecond) + { + two = aSecond; + } + + /** + * Checks whether two pairs are equal. Note that the pair + * (a,b) is equal to the pair (x,y) if and only if a is + * equal to x and b is equal to y. + * @return true if this pair is equal to aPair. Otherwise + * return false. + */ + public boolean equals(Object otherObject) + { + if(otherObject == null) + { + return false; + } + + if(getClass() != otherObject.getClass()) + { + return false; + } + Pair pairObject = (Pair) otherObject; + return one.equals(pairObject.fst()) && two.equals(pairObject.snd()); + } + + /** + * Generates a string representing this pair. Note that + * the String representing the pair (x,y) is "(x,y)". There + * is no whitespace unless x or y or both contain whitespace + * themselves. + * @return a string representing this pair. + */ + public String toString() + { + return "(" + one.toString() + "," + two.toString() + ")"; + } +} diff --git a/labs/lab01_pair/PairInterface.java b/labs/lab01_pair/PairInterface.java new file mode 100644 index 0000000..b3d78fa --- /dev/null +++ b/labs/lab01_pair/PairInterface.java @@ -0,0 +1,55 @@ + +public interface PairInterface<T1,T2> +{ + /** + * Gets the first element of this pair. + * @return the first element of this pair. + */ + public T1 fst(); + + /** + * Gets the second element of this pair. + * @return the second element of this pair. + */ + public T2 snd(); + + /** + * Sets the first element to aFirst. + * @param aFirst the new first element + */ + public void setFst(T1 aFirst); + + /** + * Sets the second element to aSecond. + * @param aSecond the new second element + */ + public void setSnd(T2 aSecond); + + /** + * Checks whether two pairs are equal. Note that the pair + * (a,b) is equal to the pair (x,y) if and only if a is + * equal to x and b is equal to y. + * + * Note that if you forget to implement this method, your + * compiler will not complain since your class inherits this + * method from the class Object. + * + * @return true if this pair is equal to aPair. Otherwise + * return false. + */ + public boolean equals(Object otherObject); + + /** + * Generates a string representing this pair. Note that + * the String representing the pair (x,y) is "(x,y)". There + * is no whitespace unless x or y or both contain whitespace + * themselves. + * + * Note that if you forget to implement this method, your + * compiler will not complain since your class inherits this + * method from the class Object. + * + * @return a string representing this pair. + */ + public String toString(); +} diff --git a/labs/lab01_pair/PairTester.java b/labs/lab01_pair/PairTester.java new file mode 100644 index 0000000..a1d3d50 --- /dev/null +++ b/labs/lab01_pair/PairTester.java @@ -0,0 +1,286 @@ +import java.util.Random; + +public class PairTester +{ + public static void main(String[] args) + { + int point = 0; + Random rand = new Random(); + + // Test a pair of string and integer + + System.out.print("Testing Pair<String,Integer>: "); + + int l1 = rand.nextInt(10) + 10; + String s1 = randomString(l1); + PairInterface<String,Integer> p1 = new Pair<String,Integer>(s1,l1); + + if(checkFromToString("(" + s1 + "," + l1 + ")", p1.toString())) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + // Test a pair of integer and string + + System.out.print("Testing Pair<Integer,String>: "); + int l2 = rand.nextInt(10) + 10; + String s2 = randomString(l2); + PairInterface<Integer,String> p2 = new Pair<Integer,String>(l2,s2); + if(checkFromToString("(" + l2 + "," + s2 + ")", p2.toString())) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + // Test a pair of String and pair + + System.out.print("Testing Pair<String,Pair<Integer,String>>: "); + int l3_1 = rand.nextInt(10) + 10; + int l3_2 = rand.nextInt(10) + 10; + String s3_1 = randomString(l3_1); + String s3_2 = randomString(l3_2); + PairInterface<Integer,String> p3_1 = new Pair<Integer,String>(l3_1 + l3_2, s3_1); + PairInterface<String, PairInterface<Integer,String>> p3_2 = new Pair<String, PairInterface<Integer,String>>(s3_2, p3_1); + if(checkFromToString("(" + s3_2 + ",(" + (l3_1 + l3_2) + "," + s3_1 + "))", p3_2.toString())) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + // Test a pair of pair and Integer + + System.out.print("Testing Pair<String,Pair<Integer,String>>: "); + int l4_1 = rand.nextInt(10) + 10; + int l4_2 = rand.nextInt(10) + 10; + String s4 = randomString(l4_1 + l4_2); + PairInterface<String,Integer> p4_1 = new Pair<String,Integer>(s4,l4_1); + Pair<Integer, PairInterface<String,Integer>> p4_2 = new Pair<Integer, PairInterface<String,Integer>>(l4_2, p4_1); + if(checkFromToString("(" + l4_2 + ",(" + s4 + "," + l4_1 + "))", p4_2.toString())) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + // Test 5-tuple + + System.out.print("Testing 5-tuple (e.g., (1,(2,(3,(4,5))))): "); + int[] l5 = new int[5]; + for(int i = 0; i < 5; i++) + { + l5[i] = rand.nextInt(10) + 10; + } + String s5 = "(" + l5[0] + ",(" + l5[1] + ",(" + l5[2] + ",(" + l5[3] + "," + l5[4] + "))))"; + PairInterface<Integer,Integer> p5_1 = new Pair<Integer,Integer>(l5[3],l5[4]); + PairInterface<Integer,PairInterface<Integer,Integer>> p5_2 = new Pair<Integer,PairInterface<Integer,Integer>>(l5[2],p5_1); + PairInterface<Integer,PairInterface<Integer,PairInterface<Integer,Integer>>> p5_3 = + new Pair<Integer,PairInterface<Integer,PairInterface<Integer,Integer>>>(l5[1],p5_2); + PairInterface<Integer,PairInterface<Integer,PairInterface<Integer,PairInterface<Integer,Integer>>>> p5_4 = + new Pair<Integer,PairInterface<Integer,PairInterface<Integer,PairInterface<Integer,Integer>>>>(l5[0],p5_3); + if(checkFromToString(s5, p5_4.toString())) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + if(point != 5) + { + System.out.println("This test class will use variables generated in"); + System.out.println("previous tests. Your class Pair fails one or more"); + System.out.println("test(s). This test class will terminated. Fix"); + System.out.println("your class Pair first and run the test class again."); + System.out.println("Your current point is " + point + ".\n"); + return; + } + + // Testing the method equals() + + System.out.println("Testing the method equals()"); + + PairInterface<String,Integer> p6 = new Pair<String,Integer>(s1,l1); + + System.out.print("Test whether " + p1 + " is equals to " + p6 + ": "); + if(!p1.equals(p6)) + { + System.out.println("FAIL"); + System.out.println("The pair " + p1 + " and the pair " + p6 + " are equal."); + System.out.println("But your method equals() returned false."); + System.out.println("Fix your method equals() first and run the test class again."); + System.out.println("Your current point is " + point + ".\n"); + return; + } + else + { + System.out.println("PASS"); + } + + PairInterface<String,Integer> p6_2 = new Pair<String,Integer>(s1.substring(1,s1.length()), l1); + System.out.print("Test whether " + p1 + " is equals to " + p6_2 + ": "); + if(p1.equals(p6_2)) + { + System.out.println("FAIL"); + System.out.println("The pair " + p1 + " and the pair " + p6_2 + " are not equal."); + System.out.println("But your method equals() returned true."); + System.out.println("Fix your method equals() first and run the test class again."); + System.out.println("Your current point is " + point + ".\n"); + return; + } + else + { + System.out.println("PASS"); + } + + PairInterface<String,Integer> p6_3 = new Pair<String,Integer>(s1, l1 + 1); + System.out.print("Test whether " + p1 + " is equals to " + p6_3 + ": "); + if(p1.equals(p6_3)) + { + System.out.println("FAIL"); + System.out.println("The pair " + p1 + " and the pair " + p6_3 + " are not equal."); + System.out.println("But your method equals() returned true."); + System.out.println("Fix your method equals() first and run the test class again."); + System.out.println("Your current point is " + point + ".\n"); + return; + } + else + { + System.out.println("PASS"); + } + + point++; + System.out.println("Your current point is " + point + ".\n"); + + + + System.out.print("Testing the method equals() (x,(y,z)) = (x,(y,z)): "); + PairInterface<Integer,String> p7_1 = new Pair<Integer,String>(l3_1 + l3_2, s3_1); + Pair<String, PairInterface<Integer,String>> p7_2 = new Pair<String, PairInterface<Integer,String>>(s3_2, p7_1); + if(!p3_2.equals(p7_2)) + { + System.out.println("FAIL"); + System.out.println("The pair " + p3_2 + " and the pair " + p7_2 + " are equal."); + System.out.println("But your method equals() returned false."); + System.out.println("Fix your method equals() first and run the test class again."); + System.out.println("Your current point is " + point + ".\n"); + return; + } + else + { + System.out.println("PASS"); + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + // Testing the method fst() + + System.out.print("Testing the method fst(): "); + if(!s1.equals(p1.fst())) + { + System.out.println("FAIL"); + System.out.println("First element of the pair " + p1 + " is " + s1 + "."); + System.out.println("But the method fst() of your class returned " + p1.fst() + ".\n"); + } + else + { + System.out.println("PASS"); + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + // Testing the method snd() + + System.out.print("Testing the method snd(): "); + if(!s2.equals(p2.snd())) + { + System.out.println("FAIL"); + System.out.println("Second element of the pair " + p2 + " is " + s2 + "."); + System.out.println("But the method snd() of your class returned " + p2.fst() + ".\n"); + } + else + { + System.out.println("PASS"); + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + // Test setFst() and setSnd() + + System.out.print("Testing the methods setFst() and setSnd(): "); + PairInterface<String,Integer> p10_1 = new Pair<String,Integer>("Hello",123); + PairInterface<String,Integer> p10_2 = new Pair<String,Integer>("How are you?",54321); + + p10_1.setFst("How are you?"); + p10_1.setSnd(54321); + + if(!p10_1.equals(p10_2)) + { + System.out.println("FAIL"); + System.out.println("The pair p10_1 was constructed using the following statement:"); + System.out.println(" PairInterface<String,Integer> p10_1 = new Pair<String,Integer>(\"Hello\",123);"); + System.out.println("Then the folloiwng statements are executed:"); + System.out.println(" p10_1.setFst(\"How are you?\");"); + System.out.println(" p10_1.setSnd(54321);"); + System.out.println("After above statements, the pair p10_1 should be " + p10_2 + "."); + System.out.println("But the method toString() of our pair p10_1 is returns " + p10_1 + ".\n"); + } + else + { + System.out.println("PASS"); + point++; + } + System.out.println("Your final point is " + point + ".\n"); + + if(point == 10) + { + System.out.println("Contratulation! Your class Pair works perfectly (I guess)."); + System.out.println("You can run ParabolaFrame to see how Pair can be used in a program."); + } + else + { + System.out.println("There is one or more errors in your class."); + System.out.println("Fix your bugs to get more points."); + } + } + + public static boolean checkFromToString(String s1, String s2) + { + if(s1.equals(s2)) + { + System.out.println("PASS"); + return true; + } + else + { + System.out.println("FAILED"); + System.out.println("The method toString() should to return: " + s1); + System.out.println("But your method toString() returns : " + s2); + return false; + } + } + + public static String randomString(int length) + { + String result = ""; + + for(int i = 0; i < length; i++) + { + result = result + randomChar(); + } + + return result; + } + + public static char randomChar() + { + Random rand = new Random(); + int modifier = rand.nextInt(26); + + if(rand.nextBoolean()) + { + return (char) ('a' + modifier); + } + else + { + return (char) ('A' + modifier); + } + } +} diff --git a/labs/lab01_pair/ParabolaFrame.java b/labs/lab01_pair/ParabolaFrame.java new file mode 100644 index 0000000..7d77c72 --- /dev/null +++ b/labs/lab01_pair/ParabolaFrame.java @@ -0,0 +1,36 @@ +import java.awt.BorderLayout; +import java.util.ArrayList; +import javax.swing.JFrame; +import javax.swing.JLabel; +import javax.swing.SwingConstants; + +public class ParabolaFrame +{ + public static void main(String[] args) + { + // Create an empty list of points (x,y) using Pair<Double,Double> + + ArrayList<PairInterface<Double,Double>> data = new ArrayList<PairInterface<Double,Double>>(); + + // Generate (x,y) points: y = (8/25)x^2 - 3 from -5.0 to 5.0 at + // at every 0.01. + + for(double i = -5.0; i <= 5.0; i = i + 0.01) + { + data.add(new Pair<Double,Double>(i,(((i*i)*8)/25)-3)); + } + + // Show the Parabola graph + + GraphComponent gc = new GraphComponent(data); + JLabel label = new JLabel("Good Job!!!"); + label.setHorizontalAlignment(SwingConstants.CENTER); + JFrame frame = new JFrame(); + frame.setTitle("Example of Using Pair"); + frame.setSize(500,500); + frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); + frame.add(gc); + frame.add(label, BorderLayout.SOUTH); + frame.setVisible(true); + } +} diff --git a/labs/lab01_pair/lab01_pair.pdf b/labs/lab01_pair/lab01_pair.pdf Binary files differnew file mode 100644 index 0000000..8cdc686 --- /dev/null +++ b/labs/lab01_pair/lab01_pair.pdf diff --git a/labs/lab02_simpleRGB/ImageViewer.java b/labs/lab02_simpleRGB/ImageViewer.java new file mode 100644 index 0000000..ecab621 --- /dev/null +++ b/labs/lab02_simpleRGB/ImageViewer.java @@ -0,0 +1,85 @@ +import java.io.File; +import java.io.IOException; +import java.awt.event.ActionEvent; +import java.awt.event.ActionListener; +import java.awt.image.BufferedImage; +import java.awt.BorderLayout; +import java.awt.Color; +import java.awt.GridLayout; +import javax.imageio.ImageIO; +import javax.swing.JButton; +import javax.swing.JFrame; +import javax.swing.JPanel; + +public class ImageViewer +{ + public static void main(String[] args) throws IOException + { + File file = new File("pgh_640x480.jpg"); + BufferedImage originalImage = ImageIO.read(file); + + int width = originalImage.getWidth(); + int height = originalImage.getHeight(); + + final SimpleRGB[] rgb = new SimpleRGB[5]; + rgb[0] = new SimpleRGB(width, height); + + for(int i = 0; i < height; i++) + { + for(int j = 0; j < width; j++) + { + Color c = new Color(originalImage.getRGB(j,i)); + rgb[0].setRed(j, i, c.getRed()); + rgb[0].setGreen(j, i, c.getGreen()); + rgb[0].setBlue(j, i, c.getBlue()); + } + } + + rgb[1] = rgb[0].getRedImage(); + rgb[2] = rgb[0].getGreenImage(); + rgb[3] = rgb[0].getBlueImage(); + rgb[4] = rgb[0].getGreyImage(); + + final RGBComponent rgbc = new RGBComponent(rgb[0]); + + JPanel buttonPanel = new JPanel(); + buttonPanel.setLayout(new GridLayout(1,5)); + + JButton[] button = new JButton[5]; + button[0] = new JButton("RGB"); + button[1] = new JButton("Red"); + button[2] = new JButton("Green"); + button[3] = new JButton("Blue"); + button[4] = new JButton("Greyscale"); + + class colorButtonListener implements ActionListener + { + private int index; + + public colorButtonListener(int anIndex) + { + index = anIndex; + } + + public void actionPerformed(ActionEvent arg0) + { + rgbc.setImage(rgb[index]); + } + } + + ActionListener[] cbl = new colorButtonListener[5]; + for(int i = 0; i < 5; i++) + { + cbl[i] = new colorButtonListener(i); + button[i].addActionListener(cbl[i]); + buttonPanel.add(button[i]); + } + + JFrame frame = new JFrame("Image Viewer"); + frame.setSize(642,534); + frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); + frame.add(rgbc); + frame.add(buttonPanel, BorderLayout.SOUTH); + frame.setVisible(true); + } +} diff --git a/labs/lab02_simpleRGB/RGBComponent.java b/labs/lab02_simpleRGB/RGBComponent.java new file mode 100644 index 0000000..8a1576e --- /dev/null +++ b/labs/lab02_simpleRGB/RGBComponent.java @@ -0,0 +1,46 @@ +import java.awt.Color; +import java.awt.Graphics; +import java.awt.Graphics2D; +import java.awt.geom.Line2D; + +import javax.swing.JComponent; + +@SuppressWarnings("serial") +public class RGBComponent extends JComponent +{ + private SimpleRGB image; + private int width; + private int height; + + public RGBComponent(SimpleRGB anImage) + { + image = anImage; + width = image.getWidth(); + height = image.getHeight(); + } + + public void paintComponent(Graphics g) + { + Graphics2D g2 = (Graphics2D) g; + + Line2D.Double line = new Line2D.Double(0,0,0,0); + + // Draw the Board + + for(int w = 0; w < width; w++) + { + for(int h = 0; h < height; h++) + { + g2.setColor(new Color(image.getRed(w, h), image.getGreen(w, h), image.getBlue(w, h))); + line.setLine(w, h, w, h); + g2.draw(line); + } + } + } + + public void setImage(SimpleRGB anImage) + { + image = anImage; + repaint(); + } +} diff --git a/labs/lab02_simpleRGB/SimpleRGB.java b/labs/lab02_simpleRGB/SimpleRGB.java new file mode 100644 index 0000000..5efc0bd --- /dev/null +++ b/labs/lab02_simpleRGB/SimpleRGB.java @@ -0,0 +1,190 @@ + +public class SimpleRGB +{ + // TO DO: Instant Variables + private int width; + private int height; + private int[] reds; + private int[] blues; + private int[] greens; + + public SimpleRGB(int aWidth, int aHeight) + { + this.width = aWidth; + this.height = aHeight; + reds = new int[width*height]; + blues = new int[width*height]; + greens = new int[width*height]; + } + + /** + * Gets the width of this image. + * @return the width of this image. + */ + public int getWidth() + { + return this.width; + } + + /** + * Gets the height of this image. + * @return the height of this image. + */ + public int getHeight() + { + return this.height; + } + + /** + * Sets the red value at coordinate (x,y) to aRed. + * @param x the x coordinate of this image. + * @param y the y coordinate of this image. + * @param aRed the red value (0 - 255) + */ + public void setRed(int x, int y, int aRed) + { + reds[(y*this.width) + x] = aRed; + } + + /** + * Sets the green value at coordinate (x,y) to aGreen. + * @param x the x coordinate of this image. + * @param y the y coordinate of this image. + * @param aGreen the green value (0 - 255) + */ + public void setGreen(int x, int y, int aGreen) + { + greens[(y*this.width)+x] = aGreen; + } + + /** + * Sets the blue value at coordinate (x,y) to aBlue. + * @param x the x coordinate of this image. + * @param y the y coordinate of this image. + * @param aBlue the blue value (0 - 255) + */ + public void setBlue(int x, int y, int aBlue) + { + blues[(y*this.width)+x] = aBlue; + } + + /** + * Gets the red value at coordinate (x,y). + * @param x the x coordinate of this image. + * @param y the y coordinate of this image. + * @return the value of red at coordinate (x,y). + */ + public int getRed(int x, int y) + { + return reds[(y*this.width) + x]; + } + + /** + * Gets the green value at coordinate (x,y). + * @param x the x coordinate of this image. + * @param y the y coordinate of this image. + * @return the value of green at coordinate (x,y). + */ + public int getGreen(int x, int y) + { + return greens[(y*this.width)+x]; + } + + /** + * Gets the blue value at coordinate (x,y). + * @param x the x coordinate of this image. + * @param y the y coordinate of this image. + * @return the value of blue at coordinate (x,y). + */ + public int getBlue(int x, int y) + { + return blues[(y*this.width) + x]; + } + + /** + * Get the NEW image containing only the red color. + * The red values of this new image should be exactly + * the same as red value of this image. The green and + * blue values of this new image should be 0s. + * @return the NEW image (SimpleRGB) containing only + * the red color of this image. + */ + public SimpleRGB getRedImage() + { + SimpleRGB output = new SimpleRGB(this.width,this.height); + for(int i = 0; i < reds.length; i++) + { + output.setRed(i%this.width,(i/this.width),reds[i]); + } + return output; + } + + /** + * Get the NEW image containing only the green color. + * The green values of this new image should be exactly + * the same as green value of this image. The red and + * blue values of this new image should be 0s. + * @return the NEW image (SimpleRGB) containing only + * the green color of this image. + */ + public SimpleRGB getGreenImage() + { + SimpleRGB output = new SimpleRGB(this.width,this.height); + for(int i = 0; i < greens.length; i++) + { + output.setGreen(i%this.width,(i/this.width),greens[i]); + } + return output; + } + + /** + * Get the NEW image containing only the blue color. + * The blue values of this new image should be exactly + * the same as blue value of this image. The red and + * green values of this new image should be 0s. + * @return the NEW image (SimpleRGB) containing only + * the blue color of this image. + */ + public SimpleRGB getBlueImage() + { + SimpleRGB output = new SimpleRGB(this.width,this.height); + for(int i = 0; i < blues.length; i++) + { + output.setBlue(i%this.width,(i/this.width),blues[i]); + } + return output; + } + + /** + * Get the NEW image representing the greyscale of this + * image. The grey colors are colors that the red, green + * and blue value are exactly the same. To convert an RGB + * image into a greyscale image, use the following formula + * to calculate the new value. + * (0.21 * red) + (0.72 * green) + (0.07 * blue) + * For example, suppose the (R,G,B) value of this image at + * coordinate (10,20) are (10,100,200), since + * (0.21 * 10) + (0.72 * 100) + (0.07 * 200) = 88 + * the (R,G,B) value of the new greyscale image at (10,20) + * should be (88,88,88). + * @return the NEW image representing the greyscale of this + * image. + */ + /** + *We're not british! + *It's grEy in England, + *and grAy in America! + */ + public SimpleRGB getGreyImage() + { + SimpleRGB output = new SimpleRGB(this.width,this.height); + for(int i = 0; i < reds.length; i++) + { + int gray = (int) ((reds[i]*0.21) + (greens[i]*0.72) + (blues[i]*0.07)); + output.setRed(i%this.width,(i/this.width),gray); + output.setGreen(i%this.width,(i/this.width),gray); + output.setBlue(i%this.width,(i/this.width),gray); + } + return output; + } +} diff --git a/labs/lab02_simpleRGB/SimpleRGBTester.java b/labs/lab02_simpleRGB/SimpleRGBTester.java new file mode 100644 index 0000000..2357f52 --- /dev/null +++ b/labs/lab02_simpleRGB/SimpleRGBTester.java @@ -0,0 +1,228 @@ + +public class SimpleRGBTester +{ + public static void main(String[] args) + { + int width = 500; + int height = 650; + int x = 123; + int y = 321; + int red = 1; + int green = 11; + int blue = 111; + int point = 0; + SimpleRGB rgb = new SimpleRGB(width, height); + + System.out.println("Constructing an SimpleRGB object using the following statement:"); + System.out.println(" SimpleRGB rgb = new SimpleRGB(" + width + "," + height + ");"); + + // Testing the method getWidth() + + System.out.print("Testing the method getWidth(): "); + + if(rgb.getWidth() != width) + { + System.out.println("FAIL"); + System.out.println("You method getWidth() should return " + width + "."); + System.out.println("But your method getWidth() return " + rgb.getWidth() + ".\n"); + } + else + { + point++; + System.out.println("PASS"); + } + System.out.println("You current point is " + point + ".\n"); + + // Testing the method getHeight() + + System.out.print("Testing the method getHeight(): "); + + if(rgb.getHeight() != height) + { + System.out.println("FAIL"); + System.out.println("You method getHeight() should return " + height + "."); + System.out.println("But your method getHeight() return " + rgb.getHeight() + ".\n"); + } + else + { + point++; + System.out.println("PASS"); + } + System.out.println("You current point is " + point + ".\n"); + + // Testing methods setRed() and getRed() + + System.out.print("Testing method setRed() and getRed(): "); + + rgb.setRed(x, y, red); + + if(rgb.getRed(x,y) != red) + { + System.out.println("FAIL"); + System.out.println("After calling rgb.setRed(" + x + "," + y + "," + red + ")"); + System.out.println("The method rgb.getRed(" + x + "," + y + ") should return " + red + "."); + System.out.println("But your method rgb.getRed(" + x + "," + y + ") return " + rgb.getRed(x, y) + ".\n"); + } + else + { + point += 1; + System.out.println("PASS"); + } + System.out.println("You current point is " + point + ".\n"); + + // Testing methods setGreen() and getGreen() + + System.out.print("Testing method setGreen() and getGreen(): "); + + rgb.setGreen(x, y, green); + + if(rgb.getGreen(x,y) != green) + { + System.out.println("FAIL"); + System.out.println("After calling rgb.setGreen(" + x + "," + y + "," + green + ")"); + System.out.println("The method rgb.getGreen(" + x + "," + y + ") should return " + green + "."); + System.out.println("But your method rgb.getGreen(" + x + "," + y + ") return " + rgb.getGreen(x, y) + ".\n"); + } + else + { + point += 1; + System.out.println("PASS"); + } + System.out.println("You current point is " + point + ".\n"); + + // Testing methods setBlue() and getBlue() + + System.out.print("Testing method setBlue() and getBlue(): "); + + rgb.setBlue(x, y, blue); + + if(rgb.getBlue(x,y) != blue) + { + System.out.println("FAIL"); + System.out.println("After calling rgb.setBlue(" + x + "," + y + "," + blue + ")"); + System.out.println("The method rgb.getBlue(" + x + "," + y + ") should return " + blue + "."); + System.out.println("But your method rgb.getBlue(" + x + "," + y + ") return " + rgb.getBlue(x, y) + ".\n"); + } + else + { + point += 1; + System.out.println("PASS"); + } + System.out.println("You current point is " + point + ".\n"); + + // getRedImage(); + + System.out.print("Testing method getRedImage(): "); + + SimpleRGB redImage = rgb.getRedImage(); + + if(redImage.getRed(x, y) != red || redImage.getGreen(x,y) != 0 || redImage.getBlue(x,y) != 0) + { + System.out.println("FAIL"); + System.out.println("The variable redImage of type SimpleRGB was initialized using the following statement:"); + System.out.println(" SimpleRGB redImage = rgb.getRedImage();"); + System.out.println("The (R,G,B) values of the rgb image at (" + x + "," + y + ") are (" + red + "," + green + "," + blue + ")."); + System.out.println("The (R,G,B) values of the redImage at (" + x + "," + y + ") should be (" + red + ",0,0)."); + System.out.println("But your method"); + System.out.println(" redImage.getRed(" + x + "," + y + ") returns " + redImage.getRed(x,y) + "."); + System.out.println(" redImage.getGreen(" + x + "," + y + ") returns " + redImage.getGreen(x,y) + "."); + System.out.println(" redImage.getBlue(" + x + "," + y + ") returns " + redImage.getBlue(x,y) + "."); + } + else + { + point += 1; + System.out.println("PASS"); + } + System.out.println("You current point is " + point + ".\n"); + + // getGreenImage(); + + System.out.print("Testing method getGreenImage(): "); + + SimpleRGB greenImage = rgb.getGreenImage(); + + if(greenImage.getRed(x, y) != 0 || greenImage.getGreen(x,y) != green || greenImage.getBlue(x,y) != 0) + { + System.out.println("FAIL"); + System.out.println("The variable greenImage of type SimpleRGB was initialized using the following statement:"); + System.out.println(" SimpleRGB greenImage = rgb.getGreenImage();"); + System.out.println("The (R,G,B) values of the rgb image at (" + x + "," + y + ") are (" + red + "," + green + "," + blue + ")."); + System.out.println("The (R,G,B) values of the greenImage at (" + x + "," + y + ") should be (0," + green + ",0)."); + System.out.println("But your method"); + System.out.println(" greenImage.getRed(" + x + "," + y + ") returns " + greenImage.getRed(x,y) + "."); + System.out.println(" greenImage.getGreen(" + x + "," + y + ") returns " + greenImage.getGreen(x,y) + "."); + System.out.println(" greenImage.getBlue(" + x + "," + y + ") returns " + greenImage.getBlue(x,y) + "."); + } + else + { + point += 1; + System.out.println("PASS"); + } + System.out.println("You current point is " + point + ".\n"); + + // getBlueImage(); + + System.out.print("Testing method getBlueImage(): "); + + SimpleRGB blueImage = rgb.getBlueImage(); + + if(blueImage.getRed(x, y) != 0 || blueImage.getGreen(x,y) != 0 || blueImage.getBlue(x,y) != blue) + { + System.out.println("FAIL"); + System.out.println("The variable blueImage of type SimpleRGB was initialized using the following statement:"); + System.out.println(" SimpleRGB blueImage = rgb.getBlueImage();"); + System.out.println("The (R,G,B) values of the rgb image at (" + x + "," + y + ") are (" + red + "," + green + "," + blue + ")."); + System.out.println("The (R,G,B) values of the blueImage at (" + x + "," + y + ") should be (0,0," + blue + ")."); + System.out.println("But your method"); + System.out.println(" blueImage.getRed(" + x + "," + y + ") returns " + blueImage.getRed(x,y) + "."); + System.out.println(" blueImage.getGreen(" + x + "," + y + ") returns " + blueImage.getGreen(x,y) + "."); + System.out.println(" blueImage.getBlue(" + x + "," + y + ") returns " + blueImage.getBlue(x,y) + "."); + } + else + { + point += 1; + System.out.println("PASS"); + } + System.out.println("You current point is " + point + ".\n"); + + // getGreyImage(); + + System.out.print("Testing method getGreyImage(): "); + + SimpleRGB greyImage = rgb.getGreyImage(); + + int greyValue = (int) ((0.21 * rgb.getRed(x, y)) + (0.72 * rgb.getGreen(x,y)) + (0.07 * rgb.getBlue(x,y))); + + if(greyImage.getRed(x, y) != greyValue || greyImage.getGreen(x,y) != greyValue || greyImage.getBlue(x,y) != greyValue) + { + System.out.println("FAIL"); + System.out.println("The variable greyImage of type SimpleRGB was initialized using the following statement:"); + System.out.println(" SimpleRGB greyImage = rgb.getGreyImage();"); + System.out.println("The (R,G,B) values of the rgb image at (" + x + "," + y + ") is (" + red + "," + green + "," + blue + ")."); + System.out.println("The (R,G,B) values of the greyImage at (" + x + "," + y + ") should be (" + greyValue + "," + greyValue + "," + greyValue + ")."); + System.out.println("But your method"); + System.out.println(" greyImage.getRed(" + x + "," + y + ") returns " + greyImage.getRed(x,y) + "."); + System.out.println(" greyImage.getGreen(" + x + "," + y + ") returns " + greyImage.getGreen(x,y) + "."); + System.out.println(" greyImage.getBlue(" + x + "," + y + ") returns " + greyImage.getBlue(x,y) + "."); + } + else + { + point += 2; + System.out.println("PASS"); + } + System.out.println("You current point is " + point + ".\n"); + + System.out.println("Your final point is " + point + "."); + + if(point == 10) + { + System.out.println("Contratulation! Your class SimpleRGB works perfectly (I guess)."); + System.out.println("You can run ImageViewer to see how SimpleRGB can be used in a program."); + } + else + { + System.out.println("There is one or more errors in your class."); + System.out.println("Fix your bugs to get more points."); + } + } +} diff --git a/labs/lab02_simpleRGB/lab02_simpleRGB.pdf b/labs/lab02_simpleRGB/lab02_simpleRGB.pdf Binary files differnew file mode 100644 index 0000000..8558e16 --- /dev/null +++ b/labs/lab02_simpleRGB/lab02_simpleRGB.pdf diff --git a/labs/lab02_simpleRGB/pgh_640x480.jpg b/labs/lab02_simpleRGB/pgh_640x480.jpg Binary files differnew file mode 100644 index 0000000..12894c8 --- /dev/null +++ b/labs/lab02_simpleRGB/pgh_640x480.jpg diff --git a/labs/lab03_dll/DLinkedList.java b/labs/lab03_dll/DLinkedList.java new file mode 100644 index 0000000..ef0f495 --- /dev/null +++ b/labs/lab03_dll/DLinkedList.java @@ -0,0 +1,190 @@ + +public class DLinkedList<T> +{ + private Node firstNode; + private Node lastNode; + private Node middleNode; + private int numberOfEntries; + private int middlePosition; + + public DLinkedList() + { + firstNode = null; + lastNode = null; + middleNode = null; + numberOfEntries = 0; + middlePosition = 0; + } + + public void add(T newEntry) + { + if(firstNode == null) + { + firstNode = new Node(null, newEntry, null); + lastNode = firstNode; + } + else + { + Node newNode = new Node(lastNode, newEntry, null); + lastNode.next = newNode; + lastNode = newNode; + } + + numberOfEntries++; + + if(numberOfEntries % 2 == 1) + { + if(middleNode == null) + { + middleNode = firstNode; + } + else + { + middleNode = middleNode.next; + } + middlePosition++; + } + } + + public T getEntry(int givenPosition) + { + T result = null; + + if((givenPosition >= 1) && (givenPosition <= numberOfEntries)) + { + result = (getNodeAt(givenPosition)).data; + } + + return result; + } + + private Node getNodeAt(int givenPosition) + { + Node currentNode = firstNode; + + for(int counter = 1; counter < givenPosition; counter++) + { + currentNode = currentNode.next; + } + + return currentNode; + } + + public T getEntry1(int givenPosition) + { + T result = null; + + if((givenPosition >= 1) && (givenPosition <= numberOfEntries)) + { + result = (getNodeAt1(givenPosition)).data; + } + + return result; + } + + /** + * Modify this method according to the Solution 1 + */ + private Node getNodeAt1(int givenPosition) + { + if(givenPosition > middlePosition) + { + //start from end, go backwars + Node temp = lastNode; + for(int i = 0;i<numberOfEntries - givenPosition;i++) + { + temp = temp.previous; + } + return temp; + } + else + { + //start from front, forwards + Node temp = firstNode; + for(int i = 1; i < givenPosition;i++) + { + temp = temp.next; + } + return temp; + } + } + + public T getEntry2(int givenPosition) + { + T result = null; + + if((givenPosition >= 1) && (givenPosition <= numberOfEntries)) + { + result = (getNodeAt2(givenPosition)).data; + } + + return result; + } + + /** + * Modify this method according to the Solution 2 + */ + private Node getNodeAt2(int givenPosition) + { + if(givenPosition < middlePosition) + { + if(givenPosition < middlePosition/2) + { + //STart from the front, go forwards + Node temp = firstNode; + for(int i = 1;i < givenPosition;i++) + { + temp = temp.next; + } + return temp; + } + else + { + //Start from the middle, backwards + Node temp = middleNode; + for(int i = middlePosition; i > givenPosition;i--) + { + temp = temp.previous; + } + return temp; + } + } + else + { + if(givenPosition < numberOfEntries*(3.0/4)) + { + //Start from the middle, go forwards + Node temp = middleNode; + for(int i = middlePosition; i < givenPosition; i++) + { + temp = temp.next; + } + return temp; + } + else + { + //Start from the end, go backwards + Node temp = lastNode; + for(int i = numberOfEntries; i >givenPosition; i--) + { + temp = temp.previous; + } + return temp; + } + } + } + + private class Node + { + private Node previous; + private T data; + private Node next; + + private Node(Node previousNode, T aData, Node nextNode) + { + previous = previousNode; + data = aData; + next = nextNode; + } + } +} diff --git a/labs/lab03_dll/DLinkedListTester.java b/labs/lab03_dll/DLinkedListTester.java new file mode 100644 index 0000000..b583e84 --- /dev/null +++ b/labs/lab03_dll/DLinkedListTester.java @@ -0,0 +1,168 @@ +import java.util.Random; + +public class DLinkedListTester +{ + public static void main(String[] args) + { + // Construct a list and add entries + + int numberOfData = 100000; // number of data to add to the list + int maxDataValue = 10000; // number of different values to add to the list + int numSampling = 10000; // number of calling the method getEntry + int dryRunReps = numSampling / 1000; + + DLinkedList<Integer> list = new DLinkedList<Integer>(); + + Random rand = new Random(); + rand.setSeed(System.nanoTime()); + + System.out.print("Adding data into the list: "); + + for(int i = 0; i < numberOfData; i++) + { + list.add(rand.nextInt(maxDataValue)); + } + + System.out.println("DONE"); + + int[] positions = new int[numSampling]; + int[] returnValues = new int[numSampling]; + + System.out.print("Dry run for the method getEntry(): "); + + // Dry run for the method getEntry1 (no timer) + // Also store all result for testing the method getEntry2() + + for(int i = 0; i < numSampling; i++) + { + int aPosition = rand.nextInt(numberOfData) + 1; + positions[i] = aPosition; + returnValues[i] = list.getEntry(aPosition); + } + + System.out.println("DONE"); + + double startTime; // Start time millisecond + double endTime; // End time millisecond + + System.out.print("Time the method getEntry(): "); + + // Timing the method getEntry() + + startTime = System.currentTimeMillis(); + + for(int i = 0; i < numSampling; i++) + { + if(returnValues[i] != list.getEntry(positions[i])) + { + System.out.println("There is something wrong."); + System.out.println("The entry in position " + positions[i] + " should be " + returnValues[i] + "."); + System.out.println("But the method getEntry(" + positions[i] + ") returns " + list.getEntry(positions[i]) + "."); + System.out.println("Fix the method getNodeAt() first."); + return; + } + } + + endTime = System.currentTimeMillis(); + + double getEntryTime = endTime - startTime; + + System.out.println("DONE"); + + // getEntry1() - Solution 1 + + // Dry run (no timer) + + System.out.print("Dry run for the method getEntry1(): "); + + for(int i = 0; i < dryRunReps; i++) + { + if(returnValues[i] != list.getEntry1(positions[i])) + { + System.out.println("There is something wrong."); + System.out.println("The entry in position " + positions[i] + " should be " + returnValues[i] + "."); + System.out.println("But the method getEntry1(" + positions[i] + ") returns " + list.getEntry1(positions[i]) + "."); + System.out.println("Fix the method getNodeAt1() first."); + return; + } + } + + System.out.println("DONE"); + + // Timing the method getEntry1() + + System.out.print("Time the method getEntry1(): "); + + startTime = System.currentTimeMillis(); + + for(int i = 0; i < numSampling; i++) + { + if(returnValues[i] != list.getEntry1(positions[i])) + { + System.out.println("There is something wrong."); + System.out.println("The entry in position " + positions[i] + " should be " + returnValues[i] + "."); + System.out.println("But the method getEntry1(" + positions[i] + ") returns " + list.getEntry1(positions[i]) + "."); + System.out.println("Fix the method getNodeAt1() first."); + return; + } + } + + endTime = System.currentTimeMillis(); + + double getEntry1Time = endTime - startTime; + + System.out.println("DONE"); + + // getEntry2() - Solution 2 + + // Dry run (no timer) + + System.out.print("Dry run for the method getEntry2(): "); + + for(int i = 0; i < dryRunReps; i++) + { + if(returnValues[i] != list.getEntry2(positions[i])) + { + System.out.println("There is something wrong."); + System.out.println("The entry in position " + positions[i] + " should be " + returnValues[i] + "."); + System.out.println("But the method getEntry2(" + positions[i] + ") returns " + list.getEntry2(positions[i]) + "."); + System.out.println("Fix the method getNodeAt2() first."); + return; + } + } + + System.out.println("DONE"); + + // Timing the method getEntry2() + + System.out.print("Time the method getEntry2(): "); + + startTime = System.currentTimeMillis(); + + for(int i = 0; i < numSampling; i++) + { + if(returnValues[i] != list.getEntry2(positions[i])) + { + System.out.println("There is something wrong."); + System.out.println("The entry in position " + positions[i] + " should be " + returnValues[i] + "."); + System.out.println("But the method getEntry2(" + positions[i] + ") returns " + list.getEntry2(positions[i]) + "."); + System.out.println("Fix the method getNodeAt2() first."); + return; + } + } + + endTime = System.currentTimeMillis(); + + double getEntry2Time = endTime - startTime; + + System.out.println("Done\n"); + + + System.out.println("The method getEntry() took " + getEntryTime + " millisecond."); + System.out.println("The method getEntry1() took " + getEntry1Time + " millisecond."); + System.out.println("The method getEntry2() took " + getEntry2Time + " millisecond.\n"); + + System.out.println("If getEntry1() took roughly about half the time of getEntry(), you get 5 points."); + System.out.println("If getEntry2() took roughly about a quarter the time of getEntry(), you get 5 points."); + } +} diff --git a/labs/lab03_dll/lab03_dll.pdf b/labs/lab03_dll/lab03_dll.pdf Binary files differnew file mode 100644 index 0000000..8789c66 --- /dev/null +++ b/labs/lab03_dll/lab03_dll.pdf diff --git a/labs/lab04_recurionll/RecursionLLTester.java b/labs/lab04_recurionll/RecursionLLTester.java new file mode 100644 index 0000000..e93ef3d --- /dev/null +++ b/labs/lab04_recurionll/RecursionLLTester.java @@ -0,0 +1,232 @@ +import java.util.Random; + + +public class RecursionLLTester +{ + public static void main(String[] args) + { + RecursionLinkedList rll = new RecursionLinkedList(); + int point = 0; + boolean isError = false; + + System.out.println("Create an empty RecursionLinkedList named rll."); + + System.out.print("Test the method contains() on an empty RecursionLinkedList: "); + if(rll.contains(5) != false) + { + System.out.println("FAIL"); + System.out.println("Nothing is added into RecursionLinkedList rll."); + System.out.println("rll.contains(5) should return 0."); + System.out.println("But your rll.contains(5) returns " + rll.contains(5) + "."); + } + else + { + System.out.println("PASS"); + point++; + } + + System.out.print("Test the method getFrequencyOf() on an empty RecursionLinkedList: "); + if(rll.getFrequencyOf(5) != 0) + { + System.out.println("FAIL"); + System.out.println("Nothing is added into RecursionLinkedList rll."); + System.out.println("rll.getFrequencyOf(5) should return 0."); + System.out.println("But your rll.getFrequencyOf(5) returns " + rll.getFrequencyOf(5) + "."); + } + else + { + System.out.println("PASS"); + point++; + } + + Random rand = new Random(); + int num = 20; + int[] array = new int[5]; + for(int i = 0; i < 5; i++) + { + array[i] = 0; + } + + System.out.println("Add the following integer into rll:"); + String s = "]"; + + for(int i = 0; i < num - 1; i++) + { + int temp = rand.nextInt(5); + System.out.print(temp + " "); + s = "," + temp + s; + array[temp]++; + rll.add(temp); + } + int temp = rand.nextInt(5); + System.out.println(temp); + s = "[" + temp + s; + array[temp]++; + rll.add(temp); + + + System.out.println("\nTest the method contains() on a non-empty RecursionLinkedList"); + System.out.print(" - Test rll.contains(-1): "); + if(rll.contains(-1) != false) + { + System.out.println("FAIL"); + System.out.println("No -1 has been added into the RecursionLinkedList rll."); + System.out.println("rll.contains(-1) should return 0."); + System.out.println("But your rll.contains(-1) returns " + rll.contains(-1)); + } + else + { + System.out.println("PASS"); + point++; + } + + for(int i = 0; i < 5; i++) + { + System.out.print(" - Test rll.contains(" + i + "): "); + if(rll.contains(i) != (array[i] != 0)) + { + System.out.println("FAIL"); + System.out.println("There are " + array[i] + " in RecursiveLinkedList rll."); + System.out.println("rll.contains(" + i + ") should return " + (array[i] != 0)); + System.out.println("But your rll.contains(" + i + ") returns " + rll.contains(i)); + isError = true; + } + else + { + System.out.println("PASS"); + } + } + + if(!isError) + { + point++; + isError = false; + } + + System.out.print(" - Test rll.contains(5): "); + if(rll.contains(5) != false) + { + System.out.println("FAIL"); + System.out.println("No 5 has been added into the RecursionLinkedList rll."); + System.out.println("rll.contains(5) should return 0."); + System.out.println("But your rll.contains(5) returns " + rll.contains(5)); + } + else + { + System.out.println("PASS"); + point++; + } + + System.out.println("Test the method getFrequencyOf() on a non-empty RecursionLinkedList"); + System.out.print(" - Test rll.getFrequencyOf(-1): "); + if(rll.getFrequencyOf(-1) != 0) + { + System.out.println("FAIL"); + System.out.println("No -1 has been added into the RecursionLinkedList rll."); + System.out.println("rll.getFrequencyOf(-1) should return 0."); + System.out.println("But your rll.getFrequencyOf(-1) returns " + rll.getFrequencyOf(-1)); + } + else + { + System.out.println("PASS"); + point++; + } + + for(int i = 0; i < 5; i++) + { + System.out.print(" - Test rll.getFrequencyOf(" + i + "): "); + if(rll.getFrequencyOf(i) != array[i]) + { + System.out.println("FAIL"); + System.out.println(i + " has been added to the RecursionLinkedList " + array[i] + " times."); + System.out.println("rll.getFrequencyOf(" + i + ") should return " + array[i] + "."); + System.out.println("But your rll.getFrequencyOf(" + i + ") returns " + rll.getFrequencyOf(i)); + isError = true; + } + else + { + System.out.println("PASS"); + } + } + + if(!isError) + { + point++; + isError = false; + } + + System.out.print(" - Test rll.getFrequencyOf(5): "); + if(rll.getFrequencyOf(5) != 0) + { + System.out.println("FAIL"); + System.out.println("No 5 has been added into the RecursionLinkedList rll."); + System.out.println("rll.getFrequencyOf(5) should return 0."); + System.out.println("But your rll.getFrequencyOf(5) returns " + rll.getFrequencyOf(5)); + } + else + { + System.out.println("PASS"); + point++; + } + + System.out.print("Test the method toString(): "); + if(!s.equals(rll.toString())) + { + System.out.println("FAIL"); + System.out.println("rll.toString() should return the string \"" + s + "\"."); + System.out.println("But your rll.toString() returns the string \"" + rll.toString() + "\"."); + } + else + { + System.out.println("PASS"); + point++; + } + + + System.out.println("Test the method getIndexOf()"); + System.out.println("Currently the rll is " + rll + "."); + + String[] str = rll.toString().split(","); + str[0] = str[0].substring(1); + str[str.length - 1] = str[str.length - 1].substring(0, 1); + + for(int i = -1; i <= 5; i++) + { + System.out.print("Test the method getIndexOf(" + i + "): "); + if(getIndex(str,i) != rll.getIndexOf(i)) + { + System.out.println("FAIL"); + System.out.println("The index of " + i + " should be " + getIndex(str,i) + "."); + System.out.println("But your rll.getIndexOf(" + i + ") returns " + rll.getIndexOf(i) + "."); + isError = true; + } + else + { + System.out.println("PASS"); + } + } + + if(!isError) + { + point++; + isError = false; + } + + System.out.println("Your current point is " + point + "."); + } + + public static int getIndex(String[] str, int s) + { + int result = -1; + + for(int i = 0; i < str.length; i++) + { + if(s == Integer.parseInt(str[i])) + { + return i; + } + } + + return result; + } +} diff --git a/labs/lab04_recurionll/RecursionLinkedList.java b/labs/lab04_recurionll/RecursionLinkedList.java new file mode 100644 index 0000000..bd1f3c5 --- /dev/null +++ b/labs/lab04_recurionll/RecursionLinkedList.java @@ -0,0 +1,164 @@ + +public class RecursionLinkedList +{ + private Node firstNode; + private int numberOfEntries; + + public RecursionLinkedList() + { + firstNode = null; + numberOfEntries = 0; + } + + public void add(int aData) + { + if(numberOfEntries == 0) + { + firstNode = new Node(aData); + } + else + { + firstNode = new Node(aData, firstNode); + } + + numberOfEntries++; + } + + /** + * boolean contains(int aData) + * + * See whether this RecursionLinkedList contains aData + * @param aData a data to be located + * @return true if this RecursionLinkedList contains aData, + * or false otherwise. + */ + public boolean contains(int aData) + { + return containsHelper(firstNode,aData); + } + private boolean containsHelper(Node thisnode, int aData) + { + if(thisnode == null) + { + return false; + } + else if(thisnode.data == aData) + { + return true; + } + else + { + return containsHelper(thisnode.next, aData); + } + } + + /** + * int getFrequencyOf(int aData) + * + * Counts the number of times a given data appears in this + * RecursionLinkedList. + * + * @param aData the data to be counted + * @return the number of times aData appears in this RecursionLinkedList + */ + public int getFrequencyOf(int aData) + { + return getFrequencyOfHelper(firstNode,aData); + } + private int getFrequencyOfHelper(Node thisnode, int aData) + { + if(thisnode == null) + { + return 0; + } + else if(thisnode.data == aData) + { + return getFrequencyOfHelper(thisnode.next, aData) + 1; + } + else + { + return getFrequencyOfHelper(thisnode.next, aData); + } + } + + /** + * String toString() + * + * Return a string representation of this RecursionLinkedList. For example, + * if this RecursionLinkedList contains 1, 2, 3, 5, 2 and 3 from the first + * index to the last index, the returned string should be + * "[1,2,3,5,2,3]" + * @return the string representation of this RecursionLinkedList. + */ + public String toString() + { + return "[" + firstNode.data + toStringHelper(firstNode.next) + "]"; + } + private String toStringHelper(Node thisnode) + { + if(thisnode == null) + { + return ""; + } + else + { + return "," + thisnode.data + toStringHelper(thisnode.next); + } + } + /** + * int getIndexOf(int aData) + * + * Return the index of the first aData where the first index of + * the first item in this RecursionLinkedList is 0. + * + * @param aData the data to be located + * @return the index of the first aData. + */ + public int getIndexOf(int aData) + { + int p = getIndexOfHelper(firstNode,aData); + /* + if(p==numberOfEntries+1) + { + return -1; + } + else + { + return p; + } + */ + return p==numberOfEntries+1?-1:p; + } + private int getIndexOfHelper(Node thisnode, int aData) + { + if(thisnode == null) + { + return 1; + } + else if(thisnode.data == aData) + { + return 0; + } + else + { + return getIndexOfHelper(thisnode.next,aData) + 1; + } + } + + private class Node + { + private int data; + private Node next; + + private Node(int aData, Node nextNode) + { + data = aData; + next = nextNode; + } + + private Node(int aData) + { + this(aData, null); + } + } +} diff --git a/labs/lab04_recurionll/lab04_rll.pdf b/labs/lab04_recurionll/lab04_rll.pdf Binary files differnew file mode 100644 index 0000000..0ec1faa --- /dev/null +++ b/labs/lab04_recurionll/lab04_rll.pdf diff --git a/labs/lab05_permutation/Permutation.java b/labs/lab05_permutation/Permutation.java new file mode 100644 index 0000000..b0cc541 --- /dev/null +++ b/labs/lab05_permutation/Permutation.java @@ -0,0 +1,51 @@ +import java.util.ArrayList; + + +public class Permutation +{ + public static ArrayList<ArrayList<Integer>> permutation(final ArrayList<Integer> olist) + { + ArrayList<Integer> list = new ArrayList<Integer>(); + for(Integer i : olist) + { + list.add(i); + } + //System.out.println("[ME]Permutateing " + list); + ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>(); + //System.out.println("[ME] Size is " + list.size()); + if(list.size() <= 1) + { + output.add(list); + } + + else + { + ArrayList<Integer> newlist = list; + for(Integer i=0; i < list.size(); i++) + { + //System.out.println("[ME]First element for this permutation is " + newlist.get(0)); + Integer firstEntry = newlist.remove(0); + for(ArrayList<Integer> l : permutation(newlist)) + { + //System.out.println("[ME]This arraylist" + l); + ArrayList<Integer> tmp1 = new ArrayList<Integer>(); + //ArrayList<Integer> tmp2 = new ArrayList<Integer>(); + tmp1.add(firstEntry); + for(Integer i2 : l) + { + tmp1.add(i2); + //tmp2.add(i2); + } + //tmp2.add(firstEntry); + //System.out.println("[ME] This full permutation is " + tmp1 + ", i is " + i + " and size is " + list.size()); + output.add(tmp1); + //output.add(tmp2); + } + newlist.add(firstEntry); + } + } + + //System.out.println("[ME] Returning " + output); + return output; + } +} diff --git a/labs/lab05_permutation/PermutationTester.java b/labs/lab05_permutation/PermutationTester.java new file mode 100644 index 0000000..2c56d3b --- /dev/null +++ b/labs/lab05_permutation/PermutationTester.java @@ -0,0 +1,129 @@ +import java.util.ArrayList; + + +public class PermutationTester +{ + public static void main(String[] args) + { + int point = 0; + ArrayList<Integer> list = new ArrayList<Integer>(); + ArrayList<ArrayList<Integer>> result; + + for(int i = 1; i <= 5; i++) + { + System.out.println("Testing permutation with " + i + " element(s)"); + list.add(i); + /*Take this out*///System.out.println("[ME]Before" + list); + result = Permutation.permutation(list); + /*Take this out*///System.out.println("[ME]After" + list); + System.out.println("Your code said, the permutation of " + list + " is as follows:"); + System.out.println(result); + + boolean result1 = checkPermutationSize(list, result); + boolean result2 = checkPermutation(list, result); + if(result1 && result2) + { + point += 2; + System.out.println("Your current point is " + point + "."); + System.out.println(); + } + else + { + System.out.println("Your current point is " + point + "."); + System.out.println("There is someting wrong with your method permutation()."); + System.out.println("Fix your code and run this tester class again."); + break; + } + } + } + + private static int factorial(int n) + { + if(n == 0) + return 1; + else + return n * factorial(n - 1); + } + + private static boolean checkPermutation(ArrayList<Integer> list, ArrayList<ArrayList<Integer>> result) + { + int numberOfElements = list.size(); + int numberOfResults = result.size(); + + System.out.print("Check the size of each element: "); + for(int i = 0; i < numberOfResults; i++) + { + if(result.get(i).size() != list.size()) + { + System.out.println("FAIL"); + System.out.println("Every element in your result should contains " + numberOfElements + " elements."); + System.out.println("But an element of your result contains " + result.get(i).size() + " elements."); + return false; + } + } + + System.out.println("PASS"); + + System.out.print("Check for duplicate elements: "); + + for(int i = 0; i < numberOfResults; i++) + { + ArrayList<Integer> temp = result.get(i); + + for(int j = i + 1; j < numberOfResults; j++) + { + if(temp.equals(result.get(j))) + { + System.out.println("FAIL"); + System.out.println("Your result contains duplicate items which is " + temp + "."); + return false; + } + } + } + + System.out.println("PASS"); + + System.out.print("Check each element: "); + for(int i = 0; i < numberOfResults; i++) + { + ArrayList<Integer> temp = result.get(i); + + for(int j = 0; j < numberOfElements; j++) + { + int aNumber = list.get(j); + + if(!temp.contains(aNumber)) + { + System.out.println("FAIL"); + System.out.println("The element " + temp + " in your result does not contain every element in " + list + "."); + } + } + } + + System.out.println("PASS"); + + return true; + } + + private static boolean checkPermutationSize(ArrayList<Integer> list, ArrayList<ArrayList<Integer>> result) + { + System.out.print("Check the size of the result: "); + + int numberOfElements = list.size(); + int numberOfResults = result.size(); + + if(factorial(numberOfElements) != numberOfResults) + { + System.out.println("FAIL"); + System.out.println(" The list " + list + " contains " + numberOfElements + " elements."); + System.out.println(" Permutation of " + list + " should contains " + factorial(numberOfElements) + "elements."); + System.out.println(" But your result contains " + numberOfResults + " elements."); + return false; + } + else + { + System.out.println("PASS"); + return true; + } + } +}
\ No newline at end of file diff --git a/labs/lab05_permutation/lab05_permutation.pdf b/labs/lab05_permutation/lab05_permutation.pdf Binary files differnew file mode 100644 index 0000000..fffd055 --- /dev/null +++ b/labs/lab05_permutation/lab05_permutation.pdf diff --git a/labs/lab07_tohSolver/THComponent.java b/labs/lab07_tohSolver/THComponent.java new file mode 100644 index 0000000..3a61dc5 --- /dev/null +++ b/labs/lab07_tohSolver/THComponent.java @@ -0,0 +1,113 @@ +import java.awt.Color; +import java.awt.Graphics; +import java.awt.Graphics2D; +import java.awt.geom.Rectangle2D; +import java.util.Random; + +import javax.swing.JComponent; + +@SuppressWarnings("serial") +public class THComponent extends JComponent +{ + private int width; + private int height; + private int leftMargin = 10; + private int rightMargin = 10; + private int topMargin = 10; + private int bottomMargin = 10; + private int baseHeight = 10; + private double poleWidth = 10; + private TowerOfHanoi towers; + private int numberOfDiscs; + private double largestDiscSize; + private double smallestDiscSize = 20; + private double defaultReductionSize = 20.0; + private double defaultDiscHeight = 20.0; + private double[] discSizes; + + public THComponent(TowerOfHanoi aTowers) + { + towers = aTowers; + numberOfDiscs = towers.getNumberOfDiscs(); + discSizes = new double[numberOfDiscs]; + } + + public void paintComponent(Graphics g) + { + Graphics2D g2 = (Graphics2D) g; + + width = this.getWidth(); + height = this.getHeight(); + + int drawingWidth = width - (leftMargin + rightMargin); + int drawingHeight = height - (topMargin + bottomMargin); + + // draw the base; + + Rectangle2D.Double rect = new Rectangle2D.Double(leftMargin , height - (bottomMargin + baseHeight), drawingWidth, baseHeight); + g2.draw(rect); + + // draw poles; + + double halfDistance = ((double) drawingWidth / 6); + largestDiscSize = (halfDistance * 2) - poleWidth; + + for(int i = 1; i <= 5; i = i + 2) + { + rect.setRect((leftMargin + (halfDistance * i)) - (poleWidth / 2), topMargin, poleWidth, drawingHeight - baseHeight); + g2.draw(rect); + } + + // draw discs + + double totalReduction = (largestDiscSize - smallestDiscSize) / (numberOfDiscs - 1); + double actualReduction; + + if(totalReduction > defaultReductionSize) + { + actualReduction = defaultReductionSize; + } + else + { + actualReduction = totalReduction; + } + + double totalHeight = drawingHeight - baseHeight; + double tempDiscHeight = totalHeight / (numberOfDiscs + 1); + double actualDiscHeight; + + if(tempDiscHeight > defaultDiscHeight) + { + actualDiscHeight = defaultDiscHeight; + } + else + { + actualDiscHeight = tempDiscHeight; + } + + for(int i = 0; i < numberOfDiscs; i++) + { + discSizes[i] = largestDiscSize - (actualReduction * ((numberOfDiscs - 1) - i)); + } + + int[][] t = new int[3][]; + for(int i = 0; i < 3; i++) + { + t[i] = towers.getArrayOfDiscs(i); + } + + for(int i = 0; i <= 2; i++) + { + for(int j = 0; j < t[i].length; j++) + { + double x = (leftMargin + (halfDistance * (1 + (2 * i)))) - (discSizes[t[i][j]] / 2); + double y = ((topMargin + drawingHeight) - baseHeight) - (actualDiscHeight * (j + 1)); + rect.setRect(x,y,discSizes[t[i][j]],actualDiscHeight); + g2.setColor(Color.GREEN); + g2.fill(rect); + g2.setColor(Color.BLACK); + g2.draw(rect); + } + } + } +} diff --git a/labs/lab07_tohSolver/THFrame.java b/labs/lab07_tohSolver/THFrame.java new file mode 100644 index 0000000..0c672e2 --- /dev/null +++ b/labs/lab07_tohSolver/THFrame.java @@ -0,0 +1,84 @@ +import javax.swing.JFrame; + +public class THFrame +{ + public static void main(String[] args) throws InterruptedException + { + int numDiscs = 4; + TowerOfHanoi towers = new TowerOfHanoi(numDiscs); + THComponent thc = new THComponent(towers); + + + JFrame frame = new JFrame(); + frame.setTitle("Tower of Hanoi"); + frame.setSize(500,500); + frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); + + frame.add(thc); + + frame.setVisible(true); + + Thread.sleep(5000); + + towers.moveTopDisc(0, 1); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(1, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 1); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(2, 0); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(2, 1); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 1); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(1, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(1, 0); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(2, 0); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(1, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 1); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(1, 2); + thc.repaint(); + Thread.sleep(500); + + } +} diff --git a/labs/lab07_tohSolver/THSolverFrame.java b/labs/lab07_tohSolver/THSolverFrame.java new file mode 100644 index 0000000..53a15bb --- /dev/null +++ b/labs/lab07_tohSolver/THSolverFrame.java @@ -0,0 +1,70 @@ +/*Alexander Pickering + *Data Structures Mon. Wed. @ 09:30 + *Lab 7 + */ +import javax.swing.JFrame; + +public class THSolverFrame +{ + public static void main(String[] args) throws InterruptedException + { + int numberOfDiscs = 10; + TowerOfHanoi towers = new TowerOfHanoi(numberOfDiscs); + THComponent thc = new THComponent(towers); + + + JFrame frame = new JFrame(); + frame.setTitle("Tower of Hanoi"); + frame.setSize(500,500); + frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); + + frame.add(thc); + + frame.setVisible(true); + + //Thread.sleep(5000); + + solveTower(towers, thc,numberOfDiscs); + + System.out.println("DONE!!!"); + } + + public static void solveTower(TowerOfHanoi towers, THComponent thc, int numPlates) throws InterruptedException + { + movePlateAndUp(towers,0,numPlates,2,thc); + } + private static void movePlateAndUp(TowerOfHanoi towers, int towerfrom, int depth, int towerto, THComponent thc) throws InterruptedException + { + if(depth == 1) + { + //We are the top block + towers.moveTopDisc(towerfrom,towerto); + animate(thc); + } + else + { + //Find a tower to put everything on top of + int unusedTower = 0; + if(towerfrom == 0 || towerto == 0) + { + unusedTower = 1; + if(towerfrom == 1 || towerto == 1) + { + unusedTower = 2; + } + } + //Move everything on top of what we want to move somewhere else + movePlateAndUp(towers,towerfrom,depth-1,unusedTower,thc); + //Move us + towers.moveTopDisc(towerfrom,towerto); + animate(thc); + //Move everything that was on top of use back on top of us + movePlateAndUp(towers,unusedTower,depth-1,towerto,thc); + } + } + private static void animate(THComponent thc) throws InterruptedException + { + thc.repaint(); + Thread.sleep(50); + } +} diff --git a/labs/lab07_tohSolver/TowerOfHanoi.java b/labs/lab07_tohSolver/TowerOfHanoi.java new file mode 100644 index 0000000..76b673d --- /dev/null +++ b/labs/lab07_tohSolver/TowerOfHanoi.java @@ -0,0 +1,170 @@ + +public class TowerOfHanoi +{ + // TO DO: Instance Variables + private HStack towers[] = new HStack[3]; + private int numDiscs; + /* Construct the Towers of Hanoi (3 towers) with aNumDisc + * on the first tower. Each tower can be identified by an + * integer number (0 for the first tower, 1 for the second + * tower, and 2 for the third tower). Each disc can be identified + * by an integer number starting from 0 (for the smallest disc) + * and (aNumDisc - 1) for the largest disc. + */ + public TowerOfHanoi(int aNumDiscs) + { + towers[0] = new HStack(); + towers[1] = new HStack(); + towers[2] = new HStack(); + for(int i = 1; i <= aNumDiscs; i++) + { + towers[0].push(aNumDiscs-i); + } + numDiscs = aNumDiscs; + } + + /* Returns an array of integer representing the order of + * discs on the tower (from bottom up). The bottom disc should + * be the first element in the array and the top disc should be + * the last element of the array. The size of the array MUST + * be the number of discs on the tower. For example, suppose + * the tower 0 contains the following discs 0,1,4,6,7,8 (from top + * to bottom). This method should return the array [8,7,6,4,1,0] + * (from first to last). + * @param tower the integer identify the tower number. + * @return an array of integer representing the order of discs. + */ + public int[] getArrayOfDiscs(int tower) + { + return towers[tower].toArray(); + } + + /* Gets the total number of discs in this Towers of Hanoi + * @return the total number of discs in this Towers of Hanoi + */ + public int getNumberOfDiscs() + { + // TO DO + return numDiscs; + } + + /* Gets the number of discs on a tower. + * @param tower the tower identifier (0, 1, or 2) + * @return the number of discs on the tower. + */ + public int getNumberOfDiscs(int tower) + { + return towers[tower].getLength(); + } + + /* Moves the top disc from fromTower to toTower. Note that + * this operation has to follow the rule of the Tower of Hanoi + * puzzle. First fromTower must have at least one disc and second + * the top disc of toTower must not be smaller than the top disc + * of the fromTower. + * @param fromTower the source tower + * @param toTower the destination tower + * @return ture if successfully move the top disc from + * fromTower to toTower. + */ + public boolean moveTopDisc(int fromTower, int toTower) + { + if(towers[fromTower].getLength() == 0) + { + return false; + } + if(towers[toTower].getLength() == 0) + { + towers[toTower].push(towers[fromTower].pop()); + return true; + } + else if(towers[fromTower].peek() < towers[toTower].peek()) + { + towers[toTower].push(towers[fromTower].pop()); + return true; + } + else + { + return false; + } + } + + public String toString() + { + String s = "[" + towers[0].toString() + "," + towers[1].toString() + "," + towers[2].toString() + "]"; + return s; + } + + public class HStack + { + private HNode head; + private int length; + public HStack() + { + length = 0; + } + public int peek() + { + return head.getData(); + } + public int pop() + { + int output = head.getData(); + head = head.getNext(); + length--; + return output; + } + public void push(int i) + { + head = new HNode(i,head); + length++; + } + public boolean hasNext() + { + return head != null; + } + public int getLength() + { + return length; + } + public String toString() + { + String output = ""; + for(HNode tmp = head; tmp != null; tmp=tmp.getNext()) + { + output += tmp.getData() + " "; + } + return output; + } + public int[] toArray() + { + int[] output = new int[length]; + int i = length-1; + for(HNode tmp = head; tmp != null; tmp = tmp.getNext()) + { + output[i] = tmp.getData(); + i--; + } + return output; + } + + } + public class HNode + { + private HNode next = null; + private int data; + public HNode(int d, HNode n) + { + data = d; + next = n; + } + public int getData() + { + return data; + } + public HNode getNext() + { + return next; + } + } +} diff --git a/labs/lab07_tohSolver/lab07_solveTower.pdf b/labs/lab07_tohSolver/lab07_solveTower.pdf Binary files differnew file mode 100644 index 0000000..c8d02f9 --- /dev/null +++ b/labs/lab07_tohSolver/lab07_solveTower.pdf diff --git a/labs/lab08_gnome_sort/SortingFrame.java b/labs/lab08_gnome_sort/SortingFrame.java new file mode 100644 index 0000000..6ceb49e --- /dev/null +++ b/labs/lab08_gnome_sort/SortingFrame.java @@ -0,0 +1,106 @@ +import java.util.Random; + +import javax.swing.JFrame; + +public class SortingFrame +{ + public static void main(String[] args) throws InterruptedException + { + JFrame frame = new JFrame(); + + int[] data = randomIntArray(40); + VisualSortingComponent vsc = new VisualSortingComponent(data); + frame.setTitle("Sorting Visualization"); + frame.setSize(500,500); + frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); + frame.add(vsc); + frame.setVisible(true); + + Thread.sleep(50); + + //bubbleSort(data,vsc); + gnomeSort(data,vsc); + + } + + public static void bubbleSort(int[] data, VisualSortingComponent vsc) throws InterruptedException + { + int size = data.length; + + for(int i = 0; i < size; i++) + { + for(int j = 0; j < size - 1; j++) + { + if(data[j] > data[j + 1]) + { + int temp = data[j]; + data[j] = data[j + 1]; + data[j + 1] = temp; + vsc.repaint(); + Thread.sleep(10); + } + } + } + } + + public static void gnomeSort(int[] data, VisualSortingComponent vsc) throws InterruptedException + { + int last = data[0]; + for(int i = 1; i < data.length; i++) + { + //System.out.println("Sorting " + i); + if(data[i] < last) + { + //System.out.println("\tDoing work"); + //The data is out of order, do some work + int j = i; + while(j>0) + { + if(data[j-1]>data[j]) + { + //System.out.println("\tSwaping " + (j-1) + " and " + j); + data = swap(data,j-1,j); + j--; + vsc.repaint(); + Thread.sleep(10); + } + else + { + break; + } + } + } + last = data[i]; + } + } + private static int[] swap(int[] data, int ind1, int ind2) + { + int tmp = data[ind1]; + data[ind1] = data[ind2]; + data[ind2] = tmp; + return data; + } + + public static int[] randomIntArray(int size) + { + int[] result = new int[size]; + + for(int i = 1; i <= size; i++) + { + result[i - 1] = i; + } + + Random rand = new Random(); + + for(int i = 0; i < size * 100; i++) + { + int first = rand.nextInt(size); + int second = rand.nextInt(size); + int temp = result[first]; + result[first] = result[second]; + result[second] = temp; + } + + return result; + } +} diff --git a/labs/lab08_gnome_sort/VisualSortingComponent.java b/labs/lab08_gnome_sort/VisualSortingComponent.java new file mode 100644 index 0000000..92152b8 --- /dev/null +++ b/labs/lab08_gnome_sort/VisualSortingComponent.java @@ -0,0 +1,78 @@ +import java.awt.Color; +import java.awt.Graphics; +import java.awt.Graphics2D; +import java.awt.geom.Line2D; +import java.awt.geom.Rectangle2D; +import javax.swing.JComponent; + +@SuppressWarnings("serial") +public class VisualSortingComponent extends JComponent +{ + private int leftMargin = 10; + private int rightMargin = 10; + private int topMargin = 10; + private int bottomMargin = 10; + private int max; + private int min; + private int width; + private int height; + private int[] data; + private int numData; + + public VisualSortingComponent(int[] aData) + { + data = aData; + numData = data.length; + + if(numData > 0) + { + max = data[0]; + min = data[0]; + + for(int i = 1; i < numData; i++) + { + if(data[i] > max) + { + max = data[i]; + } + + if(min > data[i]) + { + min = data[i]; + } + } + } + } + + public void paintComponent(Graphics g) + { + Graphics2D g2 = (Graphics2D) g; + + width = this.getWidth(); + height = this.getHeight(); + + double dataWidth = (width - (leftMargin + rightMargin)) / numData; + double heightFactor = (height - (topMargin + bottomMargin)) / numData; + + // draw the base; + + Line2D.Double line = new Line2D.Double(leftMargin, height - bottomMargin, width - leftMargin, height - bottomMargin); + g2.draw(line); + + // draw aata + + Rectangle2D.Double rect = new Rectangle2D.Double(0,0,0,0); + + for(int i = 0; i < numData; i++) + { + double x = leftMargin + (dataWidth * i); + double y = (height - bottomMargin) - (heightFactor * data[i]); + rect.setRect(x,y,dataWidth,data[i] * heightFactor); + + g2.setColor(Color.GREEN); + g2.fill(rect); + g2.setColor(Color.BLACK); + g2.draw(rect); + } + } +} diff --git a/labs/lab08_gnome_sort/lab08_gnome_sort.pdf b/labs/lab08_gnome_sort/lab08_gnome_sort.pdf Binary files differnew file mode 100644 index 0000000..24d7d01 --- /dev/null +++ b/labs/lab08_gnome_sort/lab08_gnome_sort.pdf diff --git a/labs/lab09_iterator/Iterator.java b/labs/lab09_iterator/Iterator.java new file mode 100644 index 0000000..4d64f9e --- /dev/null +++ b/labs/lab09_iterator/Iterator.java @@ -0,0 +1,7 @@ + +public interface Iterator<T> +{ + public boolean hasNext(); + public T next(); + public T remove(); +} diff --git a/labs/lab09_iterator/SListIterator.java b/labs/lab09_iterator/SListIterator.java new file mode 100644 index 0000000..e58ea6d --- /dev/null +++ b/labs/lab09_iterator/SListIterator.java @@ -0,0 +1,88 @@ +import java.util.NoSuchElementException; + + +public class SListIterator<T> +{ + private Node firstNode; + private int numberOfEntries; + + public SListIterator() + { + firstNode = null; + numberOfEntries = 0; + } + + public void addToFirst(T aData) + { + firstNode = new Node(aData, firstNode); + numberOfEntries++; + } + + public T getEntry(int givenPosition) + { + T result = null; + + if((givenPosition >= 1) && (givenPosition <= numberOfEntries)) + { + result = (getNodeAt(givenPosition)).data; + } + + return result; + } + + private Node getNodeAt(int givenPosition) + { + Node currentNode = firstNode; + + for(int counter = 1; counter < givenPosition; counter++) + { + currentNode = currentNode.next; + } + + return currentNode; + } + + public Iterator<T> getIterator() + { + return new IteratorForSList(); + } + + private class IteratorForSList implements Iterator<T> + { + Node node; + + private IteratorForSList() + { + node = firstNode; + } + + public boolean hasNext() + { + return node != null; + } + + public T next() + { + T temp = node.data; + node = node.next; + return temp; + } + + public T remove() + { + throw new UnsupportedOperationException("remove() is not supported by this iterator"); + } + } + + private class Node + { + private T data; + private Node next; + + private Node(T aData, Node nextNode) + { + data = aData; + next = nextNode; + } + } +} diff --git a/labs/lab09_iterator/SListIteratorTester.java b/labs/lab09_iterator/SListIteratorTester.java new file mode 100644 index 0000000..b6960b5 --- /dev/null +++ b/labs/lab09_iterator/SListIteratorTester.java @@ -0,0 +1,83 @@ +import java.util.Random; + +public class SListIteratorTester +{ + public static void main(String[] args) + { + // Construct a list and add entries + + int numberOfData = 50000; // number of data to add to the list + int maxDataValue = 10; // number of different values to add to the list + int[] getEntryArray = new int[numberOfData]; + int[] iteratorArray = new int[numberOfData]; + + SListIterator<Integer> list = new SListIterator<Integer>(); + + Random rand = new Random(); + rand.setSeed(System.nanoTime()); + + System.out.print("Adding data into the list: "); + + for(int i = 0; i < numberOfData; i++) + { + list.addToFirst(rand.nextInt(maxDataValue)); + } + + System.out.println("Done"); + + System.out.print("Dry run for the method getEntry(): "); + for(int i = 1; i <= 10; i++) + { + list.getEntry(i); + } + System.out.println("Done"); + + + double startTime; // Start time millisecond + double endTime; // End time millisecond + + System.out.print("Time the method getEntry(): "); + + // Timing the method getEntry() + + startTime = System.currentTimeMillis(); + + for(int i = 1; i <= numberOfData; i++) + { + getEntryArray[i - 1] = list.getEntry(i); + } + + endTime = System.currentTimeMillis(); + System.out.println("Done"); + double getEntryTime = endTime - startTime; + + System.out.print("Time the iterator: "); + + Iterator<Integer> iterator = list.getIterator(); + + startTime = System.currentTimeMillis(); + + int index = 0; + + while(iterator.hasNext()) + { + iteratorArray[index] = iterator.next(); + index++; + } + + endTime = System.currentTimeMillis(); + System.out.println("Done"); + double iteratorTime = endTime - startTime; + + for(int i = 0; i < numberOfData; i++) + { + if(getEntryArray[i] != iteratorArray[i]) + { + System.out.println("There is something wrong with your iterator."); + } + } + + System.out.println("The method getEntry() took " + getEntryTime + " milliseconds."); + System.out.println("Using iterator took " + iteratorTime + " milliseconds."); + } +}
\ No newline at end of file diff --git a/labs/lab09_iterator/lab09_iterator.pdf b/labs/lab09_iterator/lab09_iterator.pdf Binary files differnew file mode 100644 index 0000000..c9a43f1 --- /dev/null +++ b/labs/lab09_iterator/lab09_iterator.pdf diff --git a/labs/lab10_tree/BinaryNode.java b/labs/lab10_tree/BinaryNode.java new file mode 100644 index 0000000..d498b8e --- /dev/null +++ b/labs/lab10_tree/BinaryNode.java @@ -0,0 +1,100 @@ + +public class BinaryNode<T> implements BinaryNodeInterface<T> +{ + private T data; + private BinaryNode<T> left; + private BinaryNode<T> right; + + public BinaryNode(T dataPortion, BinaryNode<T> leftChild, BinaryNode<T> rightChild) + { + data = dataPortion; + left = leftChild; + right = rightChild; + } + + public BinaryNode(T dataPortion) + { + this(dataPortion, null, null); + } + + public BinaryNode() + { + this(null); + } + + public T getData() + { + return data; + } + + public void setData(T newData) + { + data = newData; + } + + public BinaryNodeInterface<T> getLeftChild() + { + return left; + } + + public BinaryNodeInterface<T> getRightChild() + { + return right; + } + + public void setLeftChild(BinaryNodeInterface<T> leftChild) + { + left = (BinaryNode<T>) leftChild; + } + + public void setRightChild(BinaryNodeInterface<T> rightChild) + { + right = (BinaryNode<T>) rightChild; + } + + public boolean hasLeftChild() + { + return left != null; + } + + public boolean hasRightChild() + { + return right != null; + } + + public boolean isLeaf() + { + return left == null && right == null; + } + + public int getNumberOfNodes() + { + int leftNumber = 0; + int rightNumber = 0; + + if(left != null) + leftNumber = left.getNumberOfNodes(); + + if(right != null) + rightNumber = right.getNumberOfNodes(); + + return 1 + leftNumber + rightNumber; + } + + public int getHeight() + { + return getHeight(this); + } + + private int getHeight(BinaryNode<T> node) + { + int height = 0; + + if(node != null) + { + height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); + } + + return height; + } +} diff --git a/labs/lab10_tree/BinaryNodeInterface.java b/labs/lab10_tree/BinaryNodeInterface.java new file mode 100644 index 0000000..f3ac7c1 --- /dev/null +++ b/labs/lab10_tree/BinaryNodeInterface.java @@ -0,0 +1,15 @@ + +public interface BinaryNodeInterface<T> +{ + public T getData(); + public void setData(T newData); + public BinaryNodeInterface<T> getLeftChild(); + public BinaryNodeInterface<T> getRightChild(); + public void setLeftChild(BinaryNodeInterface<T> leftChild); + public void setRightChild(BinaryNodeInterface<T> rightChild); + public boolean hasLeftChild(); + public boolean hasRightChild(); + public boolean isLeaf(); + public int getNumberOfNodes(); + public int getHeight(); +} diff --git a/labs/lab10_tree/ShowPath.java b/labs/lab10_tree/ShowPath.java new file mode 100644 index 0000000..d7ad05f --- /dev/null +++ b/labs/lab10_tree/ShowPath.java @@ -0,0 +1,293 @@ +/*Alexander Pickering + *Doctor Tan + *4-10-15 +*/ + +import java.util.Random; + + +public class ShowPath +{ + public static void main(String[] args) + { + int point = 0; + BinaryNodeInterface<Character> root = generateTree(); + + System.out.println("Your string returned from the method getAllPaths() is as follows:"); + String str = getAllPaths(root); + System.out.println(str); + + System.out.println("Your result of using the method getPathTo() for every character is as follows:"); + for(int i = 0; i < 52; i++) + { + if(i < 26) + { + System.out.println("Path to " + (char) ('a' + i) + " " + getPathTo(root, (char) ('a' + i))); + } + else + { + System.out.println("Path to " + (char) ('A' + (i - 26)) + " " + getPathTo(root, (char) ('A' + (i - 26)))); + } + } + + System.out.println(); + + if(!checkGetAllPaths(root, str)) + { + point = point + 5; + } + + System.out.println("Your current point is " + point + "."); + + if(!checkGetPathTo(root)) + { + point = point + 5; + } + + System.out.println("Your total point is " + point + "."); + } + + private static String getAllPaths(final BinaryNodeInterface<Character> root) + { + return getAllPathsHelper(root,""); + } + private static String getAllPathsHelper(final BinaryNodeInterface<Character> root,String pre) + { + String output = "\n"; + if(root != null) + { + output += root.getData() + " " + pre; + } + if(root.hasLeftChild()) + { + output += getAllPathsHelper(root.getLeftChild(),pre+"0"); + } + if(root.hasRightChild()) + { + output += getAllPathsHelper(root.getRightChild(),pre+"1"); + } + return output; + } + + private static String getPathTo(final BinaryNodeInterface<Character> root, char c) + { + return getPathToHelper(root,c,""); + } + private static String getPathToHelper(final BinaryNodeInterface<Character> root, char c,String cur) + { + String output = ""; + if(root != null) + { + if(root.getData() == c) + { + return cur; + } + } + if(root.hasLeftChild()) + { + output = getPathToHelper(root.getLeftChild(),c,cur+"0"); + if(output != "") + { + return output; + } + } + if(root.hasRightChild()) + { + output = getPathToHelper(root.getRightChild(),c,cur+"1"); + if(output != "") + { + return output; + } + } + return output; + } + + private static boolean checkGetAllPaths(BinaryNodeInterface<Character> root, String str) + { + boolean error = false; + String[] list = str.split("\n"); + + // check for duplicate characters and number of character + + for(int i = 0; i < list.length; i++) + { + if(!list[i].equals("")) + { + char c = list[i].charAt(0); + + for(int j = i + 1; j < list.length; j++) + { + if(!list[j].equals("")) + { + if(c == list[j].charAt(0)) + { + System.out.println("There are more than one character '" + c + "' in your output string."); + error = true; + } + } + } + } + } + + // Check paths + + for(int i = 0; i < list.length; i++) + { + String temp = list[i]; + + if(!temp.equals("")) + { + char c = temp.charAt(0); + String path = temp.substring(2); + BinaryNodeInterface<Character> currentNode = root; + + for(int j = 0; j < path.length(); j++) + { + if(path.charAt(j) == '0') + { + currentNode = currentNode.getLeftChild(); + } + else + { + currentNode = currentNode.getRightChild(); + } + } + + char nodeCharacter = currentNode.getData(); + + if(c != nodeCharacter) + { + System.out.println("The line \"" + list[i] + "\" says the path to the character " + c + " is " + path + "."); + System.out.println("But the path " + path + " goes to the node containing the character " + nodeCharacter + "."); + error = true; + } + } + } + + System.out.print("Testing the method getAllPath(): "); + + if(!error) + { + System.out.println("PASS"); + } + else + { + System.out.println("FAIL"); + } + + return error; + } + + private static boolean checkGetPathTo(BinaryNodeInterface<Character> root) + { + boolean error = false; + + for(int i = 0; i < 52; i++) + { + char c; + + if(i < 26) + { + c = (char) ('a' + i); + } + else + { + c = (char) ('A' + (i - 26)); + } + + String path = getPathTo(root, c); + BinaryNodeInterface<Character> currentNode = root; + + for(int j = 0; j < path.length(); j++) + { + if(path.charAt(j) == '0') + { + currentNode = currentNode.getLeftChild(); + } + else + { + currentNode = currentNode.getRightChild(); + } + } + + char nodeCharacter = currentNode.getData(); + + if(c != nodeCharacter) + { + System.out.println("Your method getPathTo() says the path to the character " + c + " is " + path + "."); + System.out.println("But the path " + path + " goes to the node containing the character " + nodeCharacter + "."); + error = true; + } + } + + System.out.print("Testing the method getPathTo(): "); + + if(!error) + { + System.out.println("PASS"); + } + else + { + System.out.println("FAIL"); + } + + return error; + } + + private static BinaryNodeInterface<Character> generateTree() + { + char[] charList = new char[52]; + + for(int i = 0; i < 52; i++) + { + if(i < 26) + { + charList[i] = (char) ('a' + i); + } + else + { + charList[i] = (char) ('A' + (i - 26)); + } + } + + Random rand = new Random(); + rand.setSeed(System.currentTimeMillis()); + + for(int i = 0; i < 1000; i++) + { + int index1 = rand.nextInt(52); + int index2 = rand.nextInt(52); + char temp = charList[index1]; + charList[index1] = charList[index2]; + charList[index2] = temp; + } + + BinaryNodeInterface<Character> root = new BinaryNode<Character>(charList[0]); + SimpleQueue<BinaryNodeInterface<Character>> queue = new SimpleQueue<BinaryNodeInterface<Character>>(); + queue.enqueue(root); + + for(int i = 1; i < 52; i++) + { + BinaryNodeInterface<Character> currentNode = queue.getFront(); + BinaryNodeInterface<Character> newNode = new BinaryNode<Character>(charList[i]); + + if(!currentNode.hasLeftChild()) + { + currentNode.setLeftChild(newNode); + } + else if(!currentNode.hasRightChild()) + { + currentNode.setRightChild(newNode); + } + else + { + queue.dequeue(); + currentNode = queue.getFront(); + currentNode.setLeftChild(newNode); + } + queue.enqueue(newNode); + } + + return root; + } +} diff --git a/labs/lab10_tree/SimpleQueue.java b/labs/lab10_tree/SimpleQueue.java new file mode 100644 index 0000000..64d7c11 --- /dev/null +++ b/labs/lab10_tree/SimpleQueue.java @@ -0,0 +1,72 @@ + +public class SimpleQueue<T> +{ + private Node firstNode; + private Node lastNode; + + public SimpleQueue() + { + firstNode = null; + lastNode = null; + } + + public void enqueue(T newEntry) + { + Node newNode = new Node(newEntry); + + if(firstNode == null) + { + firstNode = newNode; + lastNode = newNode; + } + else + { + lastNode.next = newNode; + lastNode = newNode; + } + } + + public T dequeue() + { + T result = null; + + if(firstNode != null) + { + result = firstNode.data; + if(lastNode == firstNode) + { + lastNode = null; + } + firstNode = firstNode.next; + } + + return result; + } + + public T getFront() + { + if(firstNode != null) + { + return firstNode.data; + } + + return null; + } + + private class Node + { + private T data; + private Node next; + + public Node(T aData, Node nextNode) + { + data = aData; + next = nextNode; + } + + public Node(T aData) + { + this(aData, null); + } + } +} diff --git a/labs/lab10_tree/lab10_tree.pdf b/labs/lab10_tree/lab10_tree.pdf Binary files differnew file mode 100644 index 0000000..06dcb2a --- /dev/null +++ b/labs/lab10_tree/lab10_tree.pdf diff --git a/labs/lab6_toh/THComponent.java b/labs/lab6_toh/THComponent.java new file mode 100644 index 0000000..3a61dc5 --- /dev/null +++ b/labs/lab6_toh/THComponent.java @@ -0,0 +1,113 @@ +import java.awt.Color; +import java.awt.Graphics; +import java.awt.Graphics2D; +import java.awt.geom.Rectangle2D; +import java.util.Random; + +import javax.swing.JComponent; + +@SuppressWarnings("serial") +public class THComponent extends JComponent +{ + private int width; + private int height; + private int leftMargin = 10; + private int rightMargin = 10; + private int topMargin = 10; + private int bottomMargin = 10; + private int baseHeight = 10; + private double poleWidth = 10; + private TowerOfHanoi towers; + private int numberOfDiscs; + private double largestDiscSize; + private double smallestDiscSize = 20; + private double defaultReductionSize = 20.0; + private double defaultDiscHeight = 20.0; + private double[] discSizes; + + public THComponent(TowerOfHanoi aTowers) + { + towers = aTowers; + numberOfDiscs = towers.getNumberOfDiscs(); + discSizes = new double[numberOfDiscs]; + } + + public void paintComponent(Graphics g) + { + Graphics2D g2 = (Graphics2D) g; + + width = this.getWidth(); + height = this.getHeight(); + + int drawingWidth = width - (leftMargin + rightMargin); + int drawingHeight = height - (topMargin + bottomMargin); + + // draw the base; + + Rectangle2D.Double rect = new Rectangle2D.Double(leftMargin , height - (bottomMargin + baseHeight), drawingWidth, baseHeight); + g2.draw(rect); + + // draw poles; + + double halfDistance = ((double) drawingWidth / 6); + largestDiscSize = (halfDistance * 2) - poleWidth; + + for(int i = 1; i <= 5; i = i + 2) + { + rect.setRect((leftMargin + (halfDistance * i)) - (poleWidth / 2), topMargin, poleWidth, drawingHeight - baseHeight); + g2.draw(rect); + } + + // draw discs + + double totalReduction = (largestDiscSize - smallestDiscSize) / (numberOfDiscs - 1); + double actualReduction; + + if(totalReduction > defaultReductionSize) + { + actualReduction = defaultReductionSize; + } + else + { + actualReduction = totalReduction; + } + + double totalHeight = drawingHeight - baseHeight; + double tempDiscHeight = totalHeight / (numberOfDiscs + 1); + double actualDiscHeight; + + if(tempDiscHeight > defaultDiscHeight) + { + actualDiscHeight = defaultDiscHeight; + } + else + { + actualDiscHeight = tempDiscHeight; + } + + for(int i = 0; i < numberOfDiscs; i++) + { + discSizes[i] = largestDiscSize - (actualReduction * ((numberOfDiscs - 1) - i)); + } + + int[][] t = new int[3][]; + for(int i = 0; i < 3; i++) + { + t[i] = towers.getArrayOfDiscs(i); + } + + for(int i = 0; i <= 2; i++) + { + for(int j = 0; j < t[i].length; j++) + { + double x = (leftMargin + (halfDistance * (1 + (2 * i)))) - (discSizes[t[i][j]] / 2); + double y = ((topMargin + drawingHeight) - baseHeight) - (actualDiscHeight * (j + 1)); + rect.setRect(x,y,discSizes[t[i][j]],actualDiscHeight); + g2.setColor(Color.GREEN); + g2.fill(rect); + g2.setColor(Color.BLACK); + g2.draw(rect); + } + } + } +} diff --git a/labs/lab6_toh/THFrame.java b/labs/lab6_toh/THFrame.java new file mode 100644 index 0000000..0c672e2 --- /dev/null +++ b/labs/lab6_toh/THFrame.java @@ -0,0 +1,84 @@ +import javax.swing.JFrame; + +public class THFrame +{ + public static void main(String[] args) throws InterruptedException + { + int numDiscs = 4; + TowerOfHanoi towers = new TowerOfHanoi(numDiscs); + THComponent thc = new THComponent(towers); + + + JFrame frame = new JFrame(); + frame.setTitle("Tower of Hanoi"); + frame.setSize(500,500); + frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); + + frame.add(thc); + + frame.setVisible(true); + + Thread.sleep(5000); + + towers.moveTopDisc(0, 1); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(1, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 1); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(2, 0); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(2, 1); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 1); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(1, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(1, 0); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(2, 0); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(1, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 1); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(0, 2); + thc.repaint(); + Thread.sleep(500); + + towers.moveTopDisc(1, 2); + thc.repaint(); + Thread.sleep(500); + + } +} diff --git a/labs/lab6_toh/TowerOfHanoi.java b/labs/lab6_toh/TowerOfHanoi.java new file mode 100644 index 0000000..51a394c --- /dev/null +++ b/labs/lab6_toh/TowerOfHanoi.java @@ -0,0 +1,164 @@ + +public class TowerOfHanoi +{ + // TO DO: Instance Variables + private HStack towers[] = new HStack[3]; + private int numDiscs; + /* Construct the Towers of Hanoi (3 towers) with aNumDisc + * on the first tower. Each tower can be identified by an + * integer number (0 for the first tower, 1 for the second + * tower, and 2 for the third tower). Each disc can be identified + * by an integer number starting from 0 (for the smallest disc) + * and (aNumDisc - 1) for the largest disc. + */ + public TowerOfHanoi(int aNumDiscs) + { + towers[0] = new HStack(); + towers[1] = new HStack(); + towers[2] = new HStack(); + for(int i = 1; i <= aNumDiscs; i++) + { + towers[0].push(aNumDiscs-i); + } + numDiscs = aNumDiscs; + } + + /* Returns an array of integer representing the order of + * discs on the tower (from bottom up). The bottom disc should + * be the first element in the array and the top disc should be + * the last element of the array. The size of the array MUST + * be the number of discs on the tower. For example, suppose + * the tower 0 contains the following discs 0,1,4,6,7,8 (from top + * to bottom). This method should return the array [8,7,6,4,1,0] + * (from first to last). + * @param tower the integer identify the tower number. + * @return an array of integer representing the order of discs. + */ + public int[] getArrayOfDiscs(int tower) + { + return towers[tower].toArray(); + } + + /* Gets the total number of discs in this Towers of Hanoi + * @return the total number of discs in this Towers of Hanoi + */ + public int getNumberOfDiscs() + { + // TO DO + return numDiscs; + } + + /* Gets the number of discs on a tower. + * @param tower the tower identifier (0, 1, or 2) + * @return the number of discs on the tower. + */ + public int getNumberOfDiscs(int tower) + { + return towers[tower].getLength(); + } + + /* Moves the top disc from fromTower to toTower. Note that + * this operation has to follow the rule of the Tower of Hanoi + * puzzle. First fromTower must have at least one disc and second + * the top disc of toTower must not be smaller than the top disc + * of the fromTower. + * @param fromTower the source tower + * @param toTower the destination tower + * @return ture if successfully move the top disc from + * fromTower to toTower. + */ + public boolean moveTopDisc(int fromTower, int toTower) + { + if(towers[fromTower].getLength() == 0) + { + return false; + } + if(towers[toTower].getLength() == 0) + { + towers[toTower].push(towers[fromTower].pop()); + return true; + } + else if(towers[fromTower].peek() < towers[toTower].peek()) + { + towers[toTower].push(towers[fromTower].pop()); + return true; + } + else + { + return false; + } + } + + public class HStack + { + private HNode head; + private int length; + public HStack() + { + length = 0; + } + public int peek() + { + return head.getData(); + } + public int pop() + { + int output = head.getData(); + head = head.getNext(); + length--; + return output; + } + public void push(int i) + { + head = new HNode(i,head); + length++; + } + public boolean hasNext() + { + return head != null; + } + public int getLength() + { + return length; + } + public String toString() + { + String output = ""; + for(HNode tmp = head; tmp != null; tmp=tmp.getNext()) + { + output += tmp.getData() + " "; + } + return output; + } + public int[] toArray() + { + int[] output = new int[length]; + int i = length-1; + for(HNode tmp = head; tmp != null; tmp = tmp.getNext()) + { + output[i] = tmp.getData(); + i--; + } + return output; + } + + } + public class HNode + { + private HNode next = null; + private int data; + public HNode(int d, HNode n) + { + data = d; + next = n; + } + public int getData() + { + return data; + } + public HNode getNext() + { + return next; + } + } +} diff --git a/labs/lab6_toh/TowersTester.java b/labs/lab6_toh/TowersTester.java new file mode 100644 index 0000000..c8aed2f --- /dev/null +++ b/labs/lab6_toh/TowersTester.java @@ -0,0 +1,185 @@ + +public class TowersTester +{ + public static void main(String[] args) + { + int numDiscs = 7; + int point = 0; + + TowerOfHanoi t = new TowerOfHanoi(numDiscs); + + // Testing the method getNumberOfDiscs() + + System.out.println("Construct the Table of Hanoi puzzle with 7 disks using the following statement:"); + System.out.println(" TowerOfHanoi t = new TowerOfHanoi(7);"); + System.out.println("All test will be base on results of manipulating TowerOfHanoi t.\n"); + + System.out.print("Testing the method getNumberOfDiscs(): "); + + if(t.getNumberOfDiscs() != numDiscs) + { + System.out.println("FAIL"); + System.out.println("The method getNumberOfDiscs() should return " + numDiscs + "."); + System.out.println("But your method getNumberOfDiscs() returns " + t.getNumberOfDiscs() + ".\n"); + } + else + { + point++; + System.out.println("PASS"); + } + System.out.println("Your current point is " + point + ".\n"); + + // Testing initial puzzle + + System.out.println("Testing initial puzzle"); + + int[][] tower0 = {{6,5,4,3,2,1,0},{},{}}; + + int[] nd0 = {7,0,0}; + + if(testPuzzle(t, nd0, tower0)) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + System.out.println("Move top disc from tower 0 to tower 1"); + if(testMTD(t.moveTopDisc(0, 1), true, 0, 1)) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + System.out.println("Testing the current puzzle"); + int[][] tower1 = {{6,5,4,3,2,1},{0},{}}; + int[] nd1 = {6,1,0}; + if(testPuzzle(t, nd1, tower1)) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + // Move + + System.out.println("Move top disc from tower 0 to tower 2"); + if(testMTD(t.moveTopDisc(0, 2), true, 0, 2)) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + System.out.println("Testing the current puzzle"); + int[][] tower2 = {{6,5,4,3,2},{0},{1}}; + int[] nd2 = {5,1,1}; + if(testPuzzle(t, nd2, tower2)) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + // Move + + System.out.println("Move top disc from tower 1 to tower 2"); + if(testMTD(t.moveTopDisc(1, 2), true, 1, 2)) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + System.out.println("Testing the current puzzle"); + int[][] tower3 = {{6,5,4,3,2},{},{1,0}}; + int[] nd3 = {5,0,2}; + if(testPuzzle(t, nd3, tower3)) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + // Move (false) + + System.out.println("Move top disc from tower 0 to tower 2 (MUST RETURN FALSE)"); + if(testMTD(t.moveTopDisc(0, 2), false, 0, 2)) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + System.out.println("Testing the current puzzle (MUST REMAIN UNCHANGED FROM PREVIOUS TEST)"); + if(testPuzzle(t, nd3, tower3)) + { + point++; + } + System.out.println("Your current point is " + point + ".\n"); + + } + + private static boolean testMTD(boolean aResult, boolean eResult, int fromTower, int toTower) + { + System.out.print("Test return value of the method moveTopDisc(): "); + if(aResult != eResult) + { + System.out.println("FAIL"); + System.out.println("t.moveTopDisc(" + fromTower + "," + toTower + ") should return " + eResult + "."); + System.out.println("But your method moveTopDisc(" + fromTower + "," + toTower + ") return " + aResult + "."); + } + else + { + System.out.println("PASS"); + } + + return aResult == eResult; + } + + private static boolean testPuzzle(TowerOfHanoi t, int[] numDiscs, int[][] tower) + { + boolean result = true; + + for(int i = 0; i < 3; i++) + { + System.out.print("Testing the method getNumberOfDiscs(" + i + "): "); + + if(t.getNumberOfDiscs(i) != numDiscs[i]) + { + System.out.println("FAIL"); + System.out.println("The method getNumberOfDiscs(" + i + ") should return " + numDiscs[i] + "."); + System.out.println("But your method getNumberOfDiscs(" + i + ") returns " + t.getNumberOfDiscs(i) + ".\n"); + result = false; + } + else + { + System.out.println("PASS"); + } + + // Testing the method getArrayOfDiscs(0) + + System.out.print("Testing the method getArrayOfDiscs(" + i + "): "); + + if(!arrayToString(tower[i]).equals(arrayToString(t.getArrayOfDiscs(i)))) + { + System.out.println("FAIL"); + System.out.println("The method getArrayOfDiscs(" + i + ") should return the array " + arrayToString(tower[i]) + "."); + System.out.println("But your method getArrayOfDiscs(" + i + ") returns the array " + arrayToString(t.getArrayOfDiscs(i)) + ".\n"); + result = false; + } + else + { + System.out.println("PASS"); + } + } + + return result; + } + + private static String arrayToString(int[] array) + { + String result = "["; + + if(array.length > 0) + { + for(int i = 0; i < array.length - 1; i++) + { + result = result + array[i] + ","; + } + + result = result + array[array.length - 1]; + } + + return result + "]"; + } +} diff --git a/labs/lab6_toh/lab06_towers_of_hanoi.pdf b/labs/lab6_toh/lab06_towers_of_hanoi.pdf Binary files differnew file mode 100644 index 0000000..6ae3eb0 --- /dev/null +++ b/labs/lab6_toh/lab06_towers_of_hanoi.pdf |
