7 files changed, 377 insertions, 0 deletions
diff --git a/Week8 Quadtrees/src/qtrees/Bitmap.java b/Week8 Quadtrees/src/qtrees/Bitmap.java
new file mode 100644
index 0000000..551c4c4
--- /dev/null
+++ b/Week8 Quadtrees/src/qtrees/Bitmap.java
@@ -0,0 +1,73 @@
+package qtrees;
+
+/**
+ * Bitmap: A class for representing bitmap;
+ * @author Sjaak Smetsers
+ * @version 18-03-2015
+ */
+public class Bitmap {
+    // each bit is stored into an two dimensional array
+    private final boolean[][] raster;
+    private final int bmWidth, bmHeight;
+    
+    /**
+     * Creates an empty bitmap of size width * height
+     * @param width
+     * @param height 
+     */
+    public Bitmap( int width, int height ) {
+        raster   = new boolean[width][height];
+        bmWidth  = width;
+        bmHeight = height;
+    }
+
+    /**
+     * Gets a bit at the specified position
+     * @param x: x coordinate
+     * @param y: y coordinate
+     */
+    public boolean getBit( int x, int y ) {
+        return raster[x][y];
+    }
+    
+    /**
+     * Sets a bit at the specified position
+     * @param x: x coordinate
+     * @param y: y coordinate
+     * @param val: the bit value 
+     */
+    public void setBit( int x, int y, boolean val ){
+        raster[x][y] = val;
+    }
+    
+    /**
+     * Converts a bitmap into a string
+     * 1 is represented by '*'; 0 by 'O'
+     * @return the string representation
+     */
+    @Override
+    public String toString() {
+        StringBuilder sb = new StringBuilder();
+        for (int y = 0; y < bmHeight; y++) {
+            for (int x = 0; x < bmWidth; x++) {
+               sb.append( raster[x][y] ?  '*' : 'O' );
+            }
+            sb.append( '\n' );
+        }
+        return sb.toString();
+    }
+    
+    /**
+     * @return the width of the bitmap
+     */
+    public int getWidth() {
+        return bmWidth;
+    }
+
+    /**
+     * @return the height of the bitmap
+     */
+    public int getHeight() {
+        return bmHeight;
+    }
+}
diff --git a/Week8 Quadtrees/src/qtrees/BlackLeaf.java b/Week8 Quadtrees/src/qtrees/BlackLeaf.java
new file mode 100644
index 0000000..0f7e71e
--- /dev/null
+++ b/Week8 Quadtrees/src/qtrees/BlackLeaf.java
@@ -0,0 +1,13 @@
+package qtrees;
+
+/**
+ * @author Camil Staps, s4498062
+ */
+public class BlackLeaf extends QTNode {
+    
+    public BlackLeaf () {
+        boolean_value = false;
+        string_value = "0";
+    }
+    
+}
diff --git a/Week8 Quadtrees/src/qtrees/GreyNode.java b/Week8 Quadtrees/src/qtrees/GreyNode.java
new file mode 100644
index 0000000..326b0af
--- /dev/null
+++ b/Week8 Quadtrees/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 Quadtrees/src/qtrees/QTNode.java b/Week8 Quadtrees/src/qtrees/QTNode.java
new file mode 100644
index 0000000..e2ad7e5
--- /dev/null
+++ b/Week8 Quadtrees/src/qtrees/QTNode.java
@@ -0,0 +1,63 @@
+package qtrees;
+
+import java.io.IOException;
+import java.io.Writer;
+
+/**
+ * Representation of a node in a QTree
+ * @author Sjaak Smetsers
+ * @author Camil Staps, s4498062
+ * 
+ * Note: the version by Sjaak Smetsers contained a sameLeaf method. This seems to be redundant though, so I removed it.
+ */
+public abstract class QTNode {
+    protected boolean boolean_value;
+    protected String string_value;
+    
+    /**
+     * Fill a (part of a) bitmap with this node
+     * In the template this was an abstract method. However, then we would use
+     * essentially the same code in BlackLeaf and WhiteLeaf. Using a concrete
+     * function here that depends on static properties is much more flexible. In
+     * GreyNode we still override this function.
+     * @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 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, boolean_value);
+    }
+    
+    /**
+     * Write a node as bitstream
+     * In the template this was an abstract method. However, then we would use
+     * essentially the same code in BlackLeaf and WhiteLeaf. Using a concrete
+     * function here that depends on static properties is much more flexible. In
+     * GreyNode we still override this function.
+     * @param out Writer to write to
+     * @throws IOException is passed on from Writer
+     */
+    public void writeNode( Writer out ) throws IOException {
+        out.write("0" + string_value);
+    }
+
+    /**
+     * 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++) {
+                bitmap.setBit(x+i, y+j, val);
+            }
+        }
+    }
+}
diff --git a/Week8 Quadtrees/src/qtrees/QTree.java b/Week8 Quadtrees/src/qtrees/QTree.java
new file mode 100644
index 0000000..24fa5e0
--- /dev/null
+++ b/Week8 Quadtrees/src/qtrees/QTree.java
@@ -0,0 +1,102 @@
+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);
+    }
+
+    /**
+     * 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 ) {
+        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 ) {
+        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 Quadtrees/src/qtrees/Qtrees.java b/Week8 Quadtrees/src/qtrees/Qtrees.java
new file mode 100644
index 0000000..91783f7
--- /dev/null
+++ b/Week8 Quadtrees/src/qtrees/Qtrees.java
@@ -0,0 +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) 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 Quadtrees/src/qtrees/WhiteLeaf.java b/Week8 Quadtrees/src/qtrees/WhiteLeaf.java
new file mode 100644
index 0000000..57cb591
--- /dev/null
+++ b/Week8 Quadtrees/src/qtrees/WhiteLeaf.java
@@ -0,0 +1,13 @@
+package qtrees;
+
+/**
+ * @author Camil Staps, s4498062
+ */
+public class WhiteLeaf extends QTNode {
+    
+    public WhiteLeaf() {
+        boolean_value = true;
+        string_value = "1";
+    }
+    
+}