Quadtree

package pgdp.datastructures;

import java.util.NoSuchElementException;

public class QuadTreeKnotenImpl implements QuadTreeKnoten {
  private QuadTreeKnoten topLeft = null;
  private QuadTreeKnoten topRight = null;
  private QuadTreeKnoten bottomRight = null;
  private QuadTreeKnoten bottomLeft = null;
  private int dimension;
  private int color;

  private QuadTreeKnotenImpl() {
  }

  public QuadTreeKnotenImpl(int dimension, int color) {
    this.dimension = dimension;
    this.color = color;
  }

  @Override
  public QuadTreeKnoten getTopLeft() {
    if (topLeft.isLeaf()) {
      throw new NoSuchElementException();
    }
    return topLeft;
  }

  @Override
  public QuadTreeKnoten getTopRight() {
    if (topRight.isLeaf()) {
      throw new NoSuchElementException();
    }
    return topRight;
  }

  @Override
  public QuadTreeKnoten getBottomLeft() {
    if (bottomLeft.isLeaf()) {
      throw new NoSuchElementException();
    }
    return bottomLeft;
  }

  @Override
  public QuadTreeKnoten getBottomRight() {
    if (bottomRight.isLeaf()) {
      throw new NoSuchElementException();
    }
    return bottomRight;
  }

  @Override
  public int getRelativeColor(int x, int y) {
    if (x < 0 || y < 0 || x >= dimension || y >= dimension) {
      throw new IllegalArgumentException();
    }
    if (isLeaf()) {
      return color;
    }
    ChildAndCoordinates child = getChildByCoordinates(x, y);
    return child.child.getRelativeColor(child.x, child.y);
  }

  @Override
  public void setRelativeColor(int x, int y, int color) {
    if (x < 0 || y < 0 || x >= dimension || y >= dimension) {
      throw new IllegalArgumentException();
    }
    if (isLeaf() && this.color == color) {
      return;
    }
    if (dimension == 1) {
      this.color = color;
      return;
    }
    ChildAndCoordinates child = getChildByCoordinates(x, y);
    child.child.setRelativeColor(child.x, child.y, color);
    if (topLeft.isLeaf() && topRight.isLeaf() &&
      bottomLeft.isLeaf() && bottomRight.isLeaf()) {
      int child_color = topLeft.getRelativeColor(0, 0);
      if (topRight.getRelativeColor(0, 0) == child_color &&
        bottomLeft.getRelativeColor(0, 0) == child_color &&
        bottomRight.getRelativeColor(0, 0) == child_color) {
        this.color = child_color;
        topLeft = null;
        topRight = null;
        bottomLeft = null;
        bottomRight = null;
      }
    }
  }

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

  @Override
  public int getSize() {
    int count = 1;
    if (topRight != null) {
      count += topRight.getSize();
      count += topLeft.getSize();
      count += bottomRight.getSize();
      count += bottomLeft.getSize();
    }
    return count;
  }

  @Override
  public boolean isLeaf() {
    if (this.getBottomLeft() == null && this.getBottomRight() == null
      && this.getTopLeft() == null && this.getTopRight() == null)
      return true;
    return false;
  }

  @Override
  public int[][] toArray() {
    int[][] image = new int[dimension][dimension];
    for (int i = 0; i < image.length; i++) {
      for (int j = 0; j < image.length; j++) {
        try {
          image[i][j] = getRelativeColor(i, j);
        } catch (IllegalArgumentException ex) {
          continue;
        }
      }
    }
    return image;
  }

  public static QuadTreeKnoten buildFromIntArray(int[][] image) {
    // set node
    // get color from array image
    // set color in tree
    // return root

    return null;
  }

  private class ChildAndCoordinates {
    public QuadTreeKnoten child = null;
    public int x;
    public int y;

    ChildAndCoordinates(QuadTreeKnoten child, int x, int y) {
      this.child = child;
      this.x = x;
      this.y = y;
    }
  }

  private ChildAndCoordinates getChildByCoordinates(int x, int y) {
    if (isLeaf()) {
      topLeft = new QuadTreeKnotenImpl(dimension / 2, color);
      topRight = new QuadTreeKnotenImpl(dimension / 2, color);
      bottomLeft = new QuadTreeKnotenImpl(dimension / 2, color);
      bottomRight = new QuadTreeKnotenImpl(dimension / 2, color);
    }

    int midPoint = getDimension() / 2;
    if (x < midPoint) {
      if (y < midPoint) {
        return new ChildAndCoordinates(topLeft, x, y);
      } else {
        return new ChildAndCoordinates(bottomLeft, x, y - midPoint);
      }
    } else {
      if (y < midPoint) {
        return new ChildAndCoordinates(topRight, x - midPoint, y);
      } else {
        return new ChildAndCoordinates(bottomRight, x - midPoint, y - midPoint);
      }
    }
  }
}