QuadTree

gistfile1.txt

package pgdp.datastructures;

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Objects;

public class QuadTreeKnotenImpl implements QuadTreeKnoten {
    private int dimension;
    private int[][] colorValues;

    private QuadTreeKnoten topLeftKnoten;
    private QuadTreeKnoten topRightKnoten;
    private QuadTreeKnoten bottomLeftKnoten;
    private QuadTreeKnoten bottomRightKnoten;

    QuadTreeKnotenImpl(int[][] colorValues) {
        this.dimension = colorValues.length;
        this.colorValues = colorValues;
        this.rekursionUpdate();
    }

    void rekursionUpdate() {
        if (!isLeaf()) {
            this.topLeftKnoten = new QuadTreeKnotenImpl(Objects.requireNonNull(getSubKnotenColors(Direction.TOP_LEFT)));
            this.topRightKnoten = new QuadTreeKnotenImpl(Objects.requireNonNull(getSubKnotenColors(Direction.TOP_RIGHT)));
            this.bottomLeftKnoten = new QuadTreeKnotenImpl(Objects.requireNonNull(getSubKnotenColors(Direction.BOTTOM_LEFT)));
            this.bottomRightKnoten = new QuadTreeKnotenImpl(Objects.requireNonNull(getSubKnotenColors(Direction.BOTTOM_RIGHT)));
        }
    }

    // Method creates a new array with respect to the old color values
    private int[][] getSubKnotenColors(Direction dir) {
        int[][] subNodeColorValues = new int[dimension / 2][dimension / 2];

        switch (dir) {
            case TOP_LEFT:
                for (int i = 0; i < dimension / 2; i++) {
                    for (int j = 0; j < dimension / 2; j++) {
                        subNodeColorValues[i][j] = colorValues[i][j];
                    }
                }
                break;

            case BOTTOM_LEFT:
                for (int i = dimension / 2 ; i < dimension; i++) {
                    for (int j = 0; j < dimension / 2; j++)
                        subNodeColorValues[i % (dimension / 2)][j] = getRelativeColor(i, j);
                }
                break;

            case TOP_RIGHT:
                for (int i = 0; i < dimension / 2; i++) {
                    for (int j = dimension / 2; j < dimension; j++)
                        subNodeColorValues[i][j % (dimension / 2)]  = getRelativeColor(i,j);
                }
                break;

            case BOTTOM_RIGHT:
                for (int i = dimension / 2; i < dimension; i++) {
                    for (int j = dimension / 2; j < dimension; j++)
                        subNodeColorValues[i % (dimension / 2)][j % (dimension / 2)] = getRelativeColor(i, j);
                }
                break;

            default: return null;
        }
        return subNodeColorValues;
    }

    @Override
    public QuadTreeKnoten getTopLeft() {
        if (this.isLeaf())
            throw new NoSuchElementException("Fehler: Element ist Blatt!");

        return topLeftKnoten;
    }

    @Override
    public QuadTreeKnoten getTopRight() {
        if (this.isLeaf())
            throw new NoSuchElementException("Fehler: Element ist Blatt!");

        return topRightKnoten;
    }

    @Override
    public QuadTreeKnoten getBottomLeft() {
        if (this.isLeaf())
            throw new NoSuchElementException("Fehler: Element ist Blatt!");

        return bottomLeftKnoten;
    }

    @Override
    public QuadTreeKnoten getBottomRight() {
        if (this.isLeaf())
            throw new NoSuchElementException("Fehler: Element ist Blatt!");

        return bottomRightKnoten;
    }

    @Override
    public int getRelativeColor(int x, int y) {
        if (x < 0 || y < 0 || x >= this.getDimension() || y >= this.getDimension())
            throw new IllegalArgumentException("Fehlerhafte Koordinaten!");

        return colorValues[x][y];
    }

    @Override
    public void setRelativeColor(int x, int y, int color) {
        if (x < 0 || y < 0 || x >= this.getDimension() || y >= this.getDimension())
            throw new IllegalArgumentException("Fehlerhafte Koordinaten!");

        // Set point
        colorValues[x][y] = color;

        // Update tree depth
        rekursionUpdate();
    }

    @Override
    public int getDimension() {
        return dimension;
    }

    @Override
    public int getSize() {
        if (this.isLeaf())
            return 1;

        return topLeftKnoten.getSize() + topRightKnoten.getSize() + bottomLeftKnoten.getSize() + bottomRightKnoten.getSize() + 1;
    }

    @Override
    public boolean isLeaf() {
        for (int i = 0; i < dimension; i++) {
            for (int j = 0; j < dimension; j++) {
                if (colorValues[i][j] != this.colorValues[0][0]) return false;
            }
        }
        return true;
    }

    @Override
    public int[][] toArray() {
        return colorValues;
    }

    private static boolean isPowerOfTwo(int num) {
        if (num == 1)
            return true;

        while (num > 0) {
            num -= 2;
            if (num == 0)
                return true;
        }
        return false;
    }

    private static boolean isSquare(int[][] image) {
        return Arrays.stream(image).noneMatch(ints -> ints.length != image.length);
    }

    public static QuadTreeKnoten buildFromIntArray(int[][] image) {
        if (image == null)
            throw new NullPointerException("Fehler: Übergebens Bild ist null!");

        if (!isSquare(image))
            throw new IllegalArgumentException("Fehler: Bild ist nicht quadratisch!");

        if (image.length <= 0)
            throw new IllegalArgumentException("Fehler: Übergebenenes Bild muss mindestens einen Pixel groß sein!");

        if (!isPowerOfTwo(image.length))
            throw new IllegalArgumentException("Fehler: Bild ist keine Zweierpotenz!");

        return new QuadTreeKnotenImpl(image);
    }
}