eclipse/visualisation/RectQuadTree.java

// BEGIN LICENSE BLOCK
// Version: CMPL 1.1
//
// The contents of this file are subject to the Cisco-style Mozilla Public
// License Version 1.1 (the "License"); you may not use this file except
// in compliance with the License.  You may obtain a copy of the License
// at www.eclipse-clp.org/license.
//
// Software distributed under the License is distributed on an "AS IS"
// basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
// the License for the specific language governing rights and limitations
// under the License.
//
// The Original Code is  The ECLiPSe Constraint Logic Programming System.
// The Initial Developer of the Original Code is  Cisco Systems, Inc.
// Portions created by the Initial Developer are
// Copyright (C) 2006 Cisco Systems, Inc.  All Rights Reserved.
//
// Contributor(s):
//
// END LICENSE BLOCK

package com.parctechnologies.eclipse.visualisation;

import java.util.*;
import java.awt.*;

/**
 * Spatial, recursive data structure for storing a set of components S whose
 * bounds fall within a given rectangle R. Allows efficient addition of
 * components to S and removal of components from S. Also allows efficient
 * lookup of which components in S intersect an arbitrary given rectangle
 * contained by R. Assumes that the bounds of the component do not change while
 * it is in the RectQuadTree. If the bounds are to change, the component should
 * be removed and added again once the new bounds are set.
 */

class RectQuadTree
{
  // for type INTERIOR, sub nodes covering four quadrants.
  private RectQuadTree [] child;

  // kind of node:
  // NONEMPTY_LEAF: some components intersect bounds. Either this node has max
  // depth == 0 or all intersecting components contain this node's bounds.
  // EMPTY_LEAF: nuff said
  // INTERIOR: some components intersect bounds, max depth > 0 and node has
  // children.
  private int type;
  // values for type
  private static final int NONEMPTY_LEAF = 0;
  private static final int EMPTY_LEAF = 1;
  private static final int INTERIOR = 2;

  private static final int DEFAULT_MIN_SIDE = 20;

  // for type NONEMPTY_LEAF: collection of components which intersect this node's
  // bounds.
  private Collection intersectingComponents;
  private Rectangle bounds;

  // maximum nesting level.
  private int maxDepth;

  /**
   * create empty tree, with max splitting depth maxDepth.
   */
  private RectQuadTree(Rectangle bounds, int maxDepth)
  {
    this.bounds = bounds;
    this.maxDepth = maxDepth;
    type = EMPTY_LEAF;
  }

  private static int depthGivenBounds(Rectangle bounds)
  {
    int smallestDim = Math.min(bounds.width, bounds.height);
    int maxDepth =
     (int) (Math.log((double) smallestDim / (double) DEFAULT_MIN_SIDE) /
     Math.log(2.0)) - 1;
    return(maxDepth);
  }

  /**
   * Creates empty tree with maxDepth such that the side of any node is at most
   * DEFAULT_MIN_SIDE
   */
  public RectQuadTree(Rectangle bounds)
  {
    this(bounds, depthGivenBounds(bounds));
  }


  // public level methods

  /**
   * Add a component to this RectQuadTree.
   */
  public void addComponent(Component c)
  {
    addComponent(c, c.getBounds());
  }

  /**
   * Remove a component from this RectQuadTree.
   */
  public void removeComponent(Component c)
  {
    removeComponent(c, c.getBounds());
  }

  /**
   * Return the set of components within this RectQuadTree which intersect
   * rectangle.
   */
  public Collection getComponentsWithin(Rectangle rectangle)
  {
    HashSet result = new HashSet();
    addIntersectingComponentsWithin(rectangle, result);
    return(result);
  }

  /**
   * Assumes added component intersects bounds.
   *
     * type = empty leaf
     *
     * if(maxDepth == 0 OR c.bounds contains this.bounds)
     *    this.type -> NONEMPTY_LEAF
     *    initialise intersectingComponents.
     *    add c to self
     *
     * else
     *    this.type -> INTERIOR
     *    initialise child array
     *    add c to self
     *
     * ---
     *
     * type = nonempty leaf
     *
     * if(maxDepth == 0 OR c.bounds contains this.bounds)
     *    intersectingComponents.add(c)
     * else
     *    this.type -> INTERIOR
     *    initialise child array
     *    add all intersectingComponents to each child,
     *    intersectingComponents = null;
     *    add c to self.
     *
     * ---
     *
     * type = interior
     *
     * for each child:
     *    if(c.bounds intersects child.bounds)
     *      child.addComponent(c)
     *
     */
  private void addComponent(Component c, Rectangle cBounds)
  {
    if(type == EMPTY_LEAF)
    {
      if(maxDepth == 0 || cBounds.contains(bounds))
      {
        type = NONEMPTY_LEAF;
        initialiseIntersectingComponents();
        intersectingComponents.add(c);
      }
      else
      {
        type = INTERIOR;
        initialiseChild();
        addComponent(c, cBounds);
      }
      return;
    }
    if(type == NONEMPTY_LEAF)
    {
      if(maxDepth == 0 || cBounds.contains(bounds))
      {
        intersectingComponents.add(c);
      }
      else
      {
        type = INTERIOR;
        initialiseChild();
        for(int i = 0; i < child.length; i++)
        {
          child[i].type = NONEMPTY_LEAF;
          child[i].initialiseIntersectingComponents();
          child[i].intersectingComponents.addAll(intersectingComponents);
        }
        intersectingComponents = null;
        addComponent(c, cBounds);
      }
      return;
    }
    if(type == INTERIOR)
    {
      for(int i = 0; i < child.length; i++)
      {
        if(cBounds.intersects(child[i].bounds))
        {
          child[i].addComponent(c, cBounds);
        }
      }
    }
  }

  /**
   * type = empty leaf
   *    do nothing.
   *
   * type = nonempty leaf
   *    result.addAll(intersectingComponents)
   *
   * type = interior
   *   for i = 0 to 3
   *     child[i].addIntersectingComponents(result);
   */
  private void addIntersectingComponents(Collection result)
  {
    if(type == EMPTY_LEAF)
    {
      return;
    }
    if(type == NONEMPTY_LEAF)
    {
      result.addAll(intersectingComponents);
      return;
    }
    if(type == INTERIOR)
    {
      for(int i = 0; i < child.length; i++)
      {
        child[i].addIntersectingComponents(result);
      }
    }
  }

  /**
   * Add all components which are within this tree and which intersect rectangle
   * to result. Assumes rectangle intersects this.bounds.
   *
   * type = empty leaf
   *    do nothing
   *
   * type = nonempty leaf
   *    for each member of intersectingComponents x
   *       if x intersects rectangle
   *         result.add(x)
   *
   * type = interior
   *    for i = 0 to 3
   *      if rectangle contains child[i].bounds
   *          child[i].addIntersectingComponents(result))
   *          return
   *      else if rectangle intersects child[i].bounds
   *          child[i].addIntersectingComponents(rectangle, result)
   */

  private void addIntersectingComponentsWithin(Rectangle rectangle,
                                               Collection result)
  {
    if(type == EMPTY_LEAF)
    {
      return;
    }
    if(type == NONEMPTY_LEAF)
    {
      Iterator i = intersectingComponents.iterator();
      Component x;
      while(i.hasNext())
      {
        x = (Component) i.next();
        if(x.getBounds().intersects(rectangle))
        {
          result.add(x);
        }
      }
    }
    if(type == INTERIOR)
    {
      for(int i = 0; i < child.length; i++)
      {
        if(rectangle.contains(child[i].bounds))
        {
          child[i].addIntersectingComponents(result);
        }
        else
        {
          if(rectangle.intersects(child[i].bounds))
          {
            child[i].addIntersectingComponentsWithin(rectangle, result);
          }
        }
      }
    }
  }


  /**
   * Assumes that component is member of the set of intersecting components.
   *
   * type = emtpy leaf
   *    dp nothing.
   *
   * type = nonempty leaf
   *    intersectingComponents.remove(component).
   *    if intersectingComponents is empty
   *    intersectingComponents -> null
   *    type -> empty leaf
   *
   * type = interior
   *    int empty leaf children -> 0;
   *    int nonempty leaf children -> 0;
   *    for i = 0 to 3
   *       if component.bounds intersects child[i].bounds
   *          child[i].removeComponent(component)
   *       if child[i].type == empty leaf
   *          empty leaf children ++
   *       if child[i].type == nonempty leaf
   *          nonempty leaf children ++
   *    end for
   *    if empty leaf children == 4
   *      type -> empty
   *      child -> null
   *    if nonemtpy leaf children == 4 &&
   *      child[0].intersectingComponents.equals child[1].intersectingComponents &&
   *      child[1].intersectingComponents.equals child[2].intersectingComponents &&
   *      child[2].intersectingComponents.equals child[3].intersectingComponents &&
   *      foreach comp in child[0].intersectingComponents
   *        comp.bounds contains this.bounds.
   *       then
   *           type -> nonempty leaf
   *           intersectingComponents = child[0].intersectingComponents
   *           child -> null
   */
  private void removeComponent(Component c, Rectangle cBounds)
  {
    if(type == EMPTY_LEAF)
    {
      return;
    }
    if(type == NONEMPTY_LEAF)
    {
      intersectingComponents.remove(c);
      if(intersectingComponents.isEmpty())
      {
        intersectingComponents = null;
        type = EMPTY_LEAF;
      }
      return;
    }
    if(type == INTERIOR)
    {
      int emptyLeafChildren = 0;
      int nonEmptyLeafChildren = 0;
      for(int i = 0; i < child.length ; i++)
      {
        if(cBounds.intersects(child[i].bounds))
        {
          child[i].removeComponent(c, cBounds);
        }
        if(child[i].type == EMPTY_LEAF)
        {
          emptyLeafChildren++;
        }
        else
        {
          if(child[i].type == NONEMPTY_LEAF)
          {
            nonEmptyLeafChildren++;
          }
        }
      }
      if(emptyLeafChildren == child.length)
      {
        type = EMPTY_LEAF;
        child = null;
        return;
      }
      if(nonEmptyLeafChildren == child.length &&
         child[0].intersectingComponents.equals(child[1].intersectingComponents) &&
         child[1].intersectingComponents.equals(child[2].intersectingComponents) &&
         child[2].intersectingComponents.equals(child[3].intersectingComponents))
      {
        boolean allIntersectingComponentsContainBounds = true;
        Iterator i = child[0].intersectingComponents.iterator();
        Component c2;
        while(i.hasNext() && allIntersectingComponentsContainBounds)
        {
          c2 = (Component) i.next();
          if(!c2.getBounds().contains(bounds))
          {
            allIntersectingComponentsContainBounds = false;
          }
        }
        if(allIntersectingComponentsContainBounds)
        {
          type = NONEMPTY_LEAF;
          intersectingComponents = child[0].intersectingComponents;
          child = null;
        }
      }
    }
  }

  private void initialiseChild()
  {
    child = new RectQuadTree[4];
    int widthLeft = bounds.width/2;
    int widthRight = bounds.width - widthLeft;
    int heightTop = bounds.height/2;
    int heightBottom = bounds.height - heightTop;
    int newDepth = maxDepth - 1;
    child[0] =
      new RectQuadTree(new Rectangle(bounds.x, bounds.y,
                                     widthLeft, heightTop), newDepth);
    child[1] =
      new RectQuadTree(new Rectangle(bounds.x + widthLeft, bounds.y,
                                     widthRight, heightTop), newDepth);
    child[2] =
      new RectQuadTree(new Rectangle(bounds.x, bounds.y + heightTop,
                                     widthLeft, heightBottom), newDepth);
    child[3] =
      new RectQuadTree(new Rectangle(bounds.x + widthLeft, bounds.y + heightTop,
                                     widthRight, heightBottom), newDepth);
  }

  private void initialiseIntersectingComponents()
  {
    intersectingComponents = new HashSet();
  }


  // testing code
  private static void test()
  {
    int MAX_DEPTH = 7;
    int COMPONENTS = 50;
    int COMPONENTS_TO_REPLACE = 25;
    int TESTS = 2000;
    int width = 2000;
    int height = 2000;
    int cHeight, cWidth;
    int replacement_index;
    Random random = new Random(1);
    Component[] component = new Component[COMPONENTS];
    RectQuadTree rqt =
      new RectQuadTree(new Rectangle(0,0,width, height), MAX_DEPTH);

    for(int i = 0; i < COMPONENTS; i++)
    {
      component[i] = new Label("");
      cWidth = random.nextInt(width/2);
      cHeight = random.nextInt(height/2);
      component[i].
        setBounds(random.nextInt(width - cWidth),
                  random.nextInt(height - cHeight),
                  cWidth, cHeight);
      rqt.addComponent(component[i]);
      System.out.println("added component to rqt with bounds "+component[i].getBounds());
    }

    System.out.println("Tests for 20 x 20: "+tests(rqt, TESTS, component, 20, 20));
    System.out.println("Tests for 20 x 500: "+tests(rqt, TESTS, component, 20, 500));
    System.out.println("Tests for 500 x 20: "+tests(rqt, TESTS, component, 500, 20));
    System.out.println("Tests for 500 x 500: "+tests(rqt, TESTS, component, 500, 500));

    for(int i = 0; i < COMPONENTS_TO_REPLACE; i++)
    {
      replacement_index = random.nextInt(COMPONENTS);
      rqt.removeComponent(component[replacement_index]);
      cWidth = random.nextInt(width/2);
      cHeight = random.nextInt(height/2);
      component[replacement_index] = new Label("");
      component[replacement_index].
        setBounds(random.nextInt(width - cWidth),
                  random.nextInt(height - cHeight),
                  cWidth, cHeight);
      rqt.addComponent(component[replacement_index]);
      System.out.println("replaced component : new one has bounds "+
        component[replacement_index].getBounds());
    }
    System.out.println("Post-replacement tests for 20 x 20: "+tests(rqt, TESTS, component, 20, 20));
    System.out.println("Post-replacement tests for 20 x 500: "+tests(rqt, TESTS, component, 20, 500));
    System.out.println("Post-replacement tests for 500 x 20: "+tests(rqt, TESTS, component, 500, 20));
    System.out.println("Post-replacement tests for 500 x 500: "+tests(rqt, TESTS, component, 500, 500));
  }

  private static boolean tests(RectQuadTree rqt, int tests,
                               Component[] component, int testWidth, int testHeight)
  {
    Rectangle testRect;
    Random random = new Random(2);
    boolean allTestsSucceeded = true;

    for(int i = 0; i < tests; i++)
    {
      testRect = new Rectangle(random.nextInt(rqt.bounds.width - testWidth),
                               random.nextInt(rqt.bounds.height - testHeight),
                               testWidth, testHeight);
      if(!test(rqt, testRect, component))
      {
        System.out.println("test failed for testRect = "+testRect);
        allTestsSucceeded = false;
      }
    }
    return(allTestsSucceeded);
  }

  private static boolean test(RectQuadTree rqt, Rectangle testRect,
                              Component[] component)
  {
    Collection rqtResults = rqt.getComponentsWithin(testRect);
    Collection naiveResults = new HashSet();
    for(int i = 0 ; i < component.length; i++)
    {
      if(component[i].getBounds().intersects(testRect))
      {
        naiveResults.add(component[i]);
      }
    }
    //System.out.println("Rqt results: "+rqtResults);
    //System.out.println("Naive results: "+naiveResults);
    return(rqtResults.equals(naiveResults));
  }
}