Week 8 done

6 files changed, 237 insertions, 10 deletions

diff --git a/Week8/src/qtrees/BlackLeaf.java b/Week8/src/qtrees/BlackLeaf.java
new file mode 100644
index 0000000..ec48997
--- /dev/null
+++ b/Week8/src/qtrees/BlackLeaf.java
@@ -0,0 +1,24 @@
+package qtrees;
+
+import java.io.IOException;
+import java.io.Writer;
+
+/**
+ * @author Camil Staps, s4498062
+ */
+public class BlackLeaf extends QTNode {
+
+    @Override
+    public void fillBitmap(int x, int y, int width, Bitmap bitmap) {
+        int old_x = x, old_y = y;
+        for (; x < old_x + width; x++)
+            for (; y < old_y + width; y++)
+                bitmap.setBit(x, y, false);
+    }
+
+    @Override
+    public void writeNode(Writer out) throws IOException {
+        out.write("00");
+    }
+    
+}
diff --git a/Week8/src/qtrees/GreyNode.java b/Week8/src/qtrees/GreyNode.java
new file mode 100644
index 0000000..326b0af
--- /dev/null
+++ b/Week8/src/qtrees/GreyNode.java
@@ -0,0 +1,59 @@
+package qtrees;
+
+import java.io.IOException;
+import java.io.Writer;
+
+/**
+ * A "grey" node (contains both black and white leaves)
+ *
+ * @author Camil Staps, s4498062
+ */
+public class GreyNode extends QTNode {
+
+    /** The four children, starting at North West, counting clockwise */
+    private final QTNode children[];
+
+    public GreyNode() {
+        children = new QTNode[4];
+    }
+
+    @Override
+    public void fillBitmap(int x, int y, int width, Bitmap bitmap) {
+        children[0].fillBitmap(x, y, width / 2, bitmap);
+        children[1].fillBitmap(x + width / 2, y, width / 2, bitmap);
+        children[2].fillBitmap(x + width / 2, y + width / 2, width / 2, bitmap);
+        children[3].fillBitmap(x, y + width / 2, width / 2, bitmap);
+    }
+
+    @Override
+    public void writeNode(Writer out) throws IOException {
+        out.write("1");
+        for (QTNode child : children)
+            child.writeNode(out);
+    }
+
+    /**
+     * Set one of the children nodes
+     * @param index the position of the child: 0 = NW; 1 = NE; 2 = SE; 3 = SW
+     * @param child the child node
+     */
+    public void setChild(int index, QTNode child) {
+        assert (index >= 0 && index <= 3);
+
+        children[index] = child;
+    }
+
+    /**
+     * Compress the current node
+     * @return a BlackLeaf if all the children are black, a WhiteLeaf if all the 
+     * children are white, or itself otherwise.
+     */
+    QTNode compress() {
+        if (children[0].getClass() == children[1].getClass() 
+                && children[1].getClass() == children[2].getClass() 
+                && children[2].getClass() == children[3].getClass())
+            return children[0];
+        return this;
+    }
+
+}
diff --git a/Week8/src/qtrees/QTNode.java b/Week8/src/qtrees/QTNode.java
index 4498dff..26cf9e1 100644
--- a/Week8/src/qtrees/QTNode.java
+++ b/Week8/src/qtrees/QTNode.java
@@ -1,18 +1,40 @@
-

 package qtrees;

 

+import java.io.IOException;

 import java.io.Writer;

 

 /**

- *

+ * Representation of a node in a QTree

  * @author Sjaak Smetsers

- * @version 18-03-2014

+ * @author Camil Staps, s4498062

+ * 

+ * Note: the version by Sjaak Smetsers contained a sameLeaf method. This seems to be reduntant though, so I removed it.

  */

 public abstract class QTNode {

+    /**

+     * Fill a (part of a) bitmap with this node

+     * @param x the x coordinate of the top left corner

+     * @param y the y coordinate of the top left corner

+     * @param width the width of the part of the bitmap to fill

+     * @param bitmap the bitmap to fill

+     */

     public abstract void fillBitmap( int x, int y, int width, Bitmap bitmap );

-    public abstract void writeNode( Writer out );

-    public abstract boolean sameLeaf( QTNode other_node );

+    

+    /**

+     * Write a node as bitstream

+     * @param out Writer to write to

+     * @throws IOException is passed on from Writer

+     */

+    public abstract void writeNode( Writer out ) throws IOException;

 

+    /**

+     * Fill a complete area of a bitmap with a particular value

+     * @param x the x coordinate of the top left corner

+     * @param y the y coordinate of the top left corner

+     * @param width the width (and height) of the area to fill

+     * @param bitmap the bitmap to fill

+     * @param val the value to fill the area with

+     */

     public static void fillArea( int x, int y, int width, Bitmap bitmap, boolean val ){

         for (int i = 0; i < width; i++) {

             for (int j = 0; j < width; j++) {

diff --git a/Week8/src/qtrees/QTree.java b/Week8/src/qtrees/QTree.java
index ab11898..24fa5e0 100644
--- a/Week8/src/qtrees/QTree.java
+++ b/Week8/src/qtrees/QTree.java
@@ -3,32 +3,100 @@ package qtrees;
 import java.io.IOException;

 import java.io.Reader;

 import java.io.Writer;

+import java.util.logging.Level;

+import java.util.logging.Logger;

 

+/**

+ * Representation of a Quad-tree

+ * @author Camil Staps, s4498062

+ */

 public class QTree {

+    /** the root of the tree */

     QTNode root;

     

+    /**

+     * Construct the tree based on an ASCII representation of a bitstream on a reader

+     * @param input the reader

+     */

     public QTree( Reader input ) {

         root = readQTree( input );

     }

     

+    /**

+     * Construct the tree based on a bitmap

+     * @param bitmap the bitmap

+     */

     public QTree( Bitmap bitmap ) {

         root = bitmap2QTree( 0, 0,  bitmap.getWidth(), bitmap );

     }

 

+    /**

+     * Fill a bitmap based on this tree

+     * @param bitmap the bitmap

+     */

     public void fillBitmap ( Bitmap bitmap ) {

         root.fillBitmap(0, 0, bitmap.getWidth(), bitmap);

     }

 

-    public void writeQTree( Writer sb ) {

+    /**

+     * Write the quad-tree as compressed bitstream

+     * @param sb the Writer to write to

+     * @throws IOException is passed on from Writer

+     */

+    public void writeQTree( Writer sb ) throws IOException {

         root.writeNode( sb );

     }

     

+    /**

+     * Read a Quad-tree node based on an ASCII representation of a bitstream on a Reader

+     * @param input the Reader

+     * @return the node

+     */

     private static QTNode readQTree( Reader input ) {

-        return null;

+        try {

+            int read = input.read();

+            if (read == '1') {

+                GreyNode node = new GreyNode();

+                for (int i = 0; i < 4; i++)

+                    node.setChild(i, readQTree(input));

+                return node;

+            } else {

+                read = input.read();

+                if (read == '1') {

+                    return new WhiteLeaf();

+                } else {

+                    return new BlackLeaf();

+                }

+            }

+        } catch (IOException ex) {

+            Logger.getLogger(QTree.class.getName()).log(Level.SEVERE, null, ex);

+            return null;

+        }

     }

     

+    /**

+     * Get a (compressed) node from a (part of a) bitmap

+     * @param x the x coordinate of the top left corner

+     * @param y the y coordinate of the top left corner

+     * @param width the width of the part to read

+     * @param bitmap the bitmap

+     * @return the (compressed) node

+     */

     public static QTNode bitmap2QTree( int x, int y, int width, Bitmap bitmap ) {

-        return null;

+        if (width == 1) {

+            if (bitmap.getBit(x,y)) {

+                return new WhiteLeaf();

+            } else {

+                return new BlackLeaf();

+            }

+        } else {

+            GreyNode node = new GreyNode();

+            node.setChild(0, bitmap2QTree(x, y, width / 2, bitmap));

+            node.setChild(1, bitmap2QTree(x + width / 2, y, width / 2, bitmap));

+            node.setChild(2, bitmap2QTree(x + width / 2, y + width / 2, width / 2, bitmap));

+            node.setChild(3, bitmap2QTree(x, y + width / 2, width / 2, bitmap));

+            return node.compress();

+        }

     }

 

 }

diff --git a/Week8/src/qtrees/Qtrees.java b/Week8/src/qtrees/Qtrees.java
index 7bd018e..91783f7 100644
--- a/Week8/src/qtrees/Qtrees.java
+++ b/Week8/src/qtrees/Qtrees.java
@@ -1,24 +1,54 @@
 package qtrees;

 

+import java.io.IOException;

+import java.io.OutputStreamWriter;

 import java.io.StringReader;

+import java.io.Writer;

 

 /**

- *

+ * Demonstration class for Quad-trees

  * @author Sjaak

+ * @author Camil Staps, s4498062

  */

 public class Qtrees {

 

     /**

+     * Example features of the QTree:

+     * Constucts and outputs the same tree in all possible ways. The output should

+     * therefore repeat itself.

+     * 

      * @param args the command line arguments

+     * @throws java.io.IOException shouldn't happen with System.out anyway

      */

-    public static void main(String[] args) {

+    public static void main(String[] args) throws IOException {

+        // Example: reading in a bitstream

         String test_tekst = "10011010001010010001010101100011000101000000";

         StringReader input = new StringReader(test_tekst);

         QTree qt = new QTree( input );

+        

+        // Example: filling a bitmap

         Bitmap bitmap = new Bitmap(8, 8);

         qt.fillBitmap( bitmap );

         System.out.println(bitmap);

+        

+        // Example: writing a bitstream

+        Writer out = new OutputStreamWriter(System.out);

+        qt.writeQTree(out);

+        out.write("\n");

+        out.flush( );

 

+        // Example: reading a bitmap

+        QTree qt2 = new QTree(bitmap);

+        

+        // Example: filling a bitmap

+        Bitmap bm2 = new Bitmap(8,8);

+        qt2.fillBitmap(bm2);

+        System.out.println(bm2);

+        

+        // Example: writing a bitstream

+        qt2.writeQTree(out);

+        out.write("\n");

+        out.flush( );

     }

 

 }

diff --git a/Week8/src/qtrees/WhiteLeaf.java b/Week8/src/qtrees/WhiteLeaf.java
new file mode 100644
index 0000000..31be533
--- /dev/null
+++ b/Week8/src/qtrees/WhiteLeaf.java
@@ -0,0 +1,24 @@
+package qtrees;
+
+import java.io.IOException;
+import java.io.Writer;
+
+/**
+ * @author Camil Staps, s4498062
+ */
+public class WhiteLeaf extends QTNode {
+
+    @Override
+    public void fillBitmap(int x, int y, int width, Bitmap bitmap) {
+        int old_x = x, old_y = y;
+        for (; x < old_x + width; x++)
+            for (y = old_y; y < old_y + width; y++)
+                bitmap.setBit(x, y, true);
+    }
+
+    @Override
+    public void writeNode(Writer out) throws IOException {
+        out.write("01");
+    }
+    
+}