Scala QuadTrie for Android point of interest clustering.

Scala QuadTree

package com.utility

/*
Copyright (c) 2012 Watt P. 

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/

import android.graphics.Point
import android.graphics.{Rect => Rectangle}
import scala.math._
import scala.collection.mutable.Map
import scala.collection.mutable.ArrayBuffer
import com.shopme.utility.Implicits._

/**
 * Quadtree implementation for use in grouping points of interest on the map.
 * A quadtree is a tree data structure in which each internal node has exactly four children. 
 * 
 * Quadtrees are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. 
 * The regions may be square or rectangular, or may have arbitrary shapes. 
 * This data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974. 
 * A similar partitioning is also known as a Q-tree. All forms of quadtrees share some common features:
 * They decompose space into adaptable cells
 * Each cell (or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits
 * The tree directory follows the spatial decomposition of the quadtree.
 * 
 * @param rantangle   	- divided space containing points.
 * @param clusterDistance 	- how far each point should be before the space divides. 
 **/
class QuadTree[V](rectangle:Rectangle, clusterDistance:Int) extends Logger {
     
	 log("QuadTree @ " + rectangle)
	 
     lazy val root:Node[V] 						= new Node[V](rectangle, clusterDistance)
      
    /**
     * Insert a rectangle and a value into space.
     * 
     * @param point - the point of interest to be inserted
     * @param value - the value for the point to be stored
     * @throw 		- IntersectionException
     */
    @throws(classOf[IntersectionException])
    def insert(point:Point, value:V):Unit = {
        // look for an intersecting rectangle, and complain
        // loudly if one is found.
	    if (value == null) {
	      return
	    }

        root.insert(point, rectangle, ArrayBuffer[V](value), 0)
        // assign the current value to all nodes that lie within
        // or intersect the current rectangle.
        //root.assign(rectangle, ArrayBuffer[V](value))
    }
    
    /**
     * Find the value corresponding to a point in space.
     *
     *	@param point 	- point of interest
     * 	@return option object containing Array of value.  The value if found, otherwise null.
     */
    def find(point:Point):Option[ArrayBuffer[V]] = {
        // Find the target node by iteration rather
        // than recursion, saving a lot of time by
        // eliminating method calls and stack allocations.
        var current:Node[V] 				= root
        while (current.split) {
            if (!current.contains(point)) {
                return None
            }
        
            // This approach reduces the worst case number of 
            // comparisons needed from 16 to 2, which has to
            // be considered as a rather nice optimization. :)
            val rectangle:Rectangle  		= current.nodeRectangle
            if (point.x > rectangle.centerX) {
                if (point.y > rectangle.centerY) {
                    current = current.topRight
                } else {
                    current = current.bottomRight
                }
            } else {
                if (point.y > rectangle.centerY) {
                    current = current.topLeft
                } else {
                    current = current.bottomLeft
                }            
            }
        
            /*if (current.tl.contains(point)) {
                current = current.tl
            } else if (current.tr.contains(point)) {
                current = current.tr
            } else if (current.bl.contains(point)) {
                current = current.bl
            } else if (current.br.contains(point)) {
                current = current.br
            } else {
                return None
            }*/
        }
        
        // Figure out which of the rectangles that intersect
        // this node contains the requested value.
        for ((rectangle, value) <- current.values) {
            if (rectangle.contains(point.x, point.y)) {
                return Some(value)
            }
        }
        
        return None
    }
    
    /**
     * Find all values given rectangle.
     * 
     * @param rectangle 		- the specified area to get values from.
     * @param array of values 	- The array of values found within that rectangle.
     */
    def getAllValues(rectangle:Rectangle):ArrayBuffer[V] = {
      	if (!root.nodeRectangle.contains(rectangle)) return null
        var array:ArrayBuffer[V]			= ArrayBuffer[V]()
        root.find(rectangle) match {
      	  case Some(ab)						=> array ++ ab
          case _                  => log("error in getValues")          //TODO take care of the error
      	}
    	
    	return array
    }
    
    /**
     * Return all contained points with their respective array of values.
     * 
     * @param rectangle 		- the specified area to get all the points found within it.
     * @return map  			- hashtable of points and array of values found within the rectangle.
     */
    def getAllPoints(rectangle:Rectangle):Map[Point, ArrayBuffer[V]] = {
       val map:Map[Point, ArrayBuffer[V]]	= Map[Point, ArrayBuffer[V]]()
       if (!root.nodeRectangle.contains(rectangle)) return map
       val allPoints:ArrayBuffer[Point]		= root.getAllPoints()
       for (point <- allPoints) {
         log("point in allPoints " + point)
       }
       for (point <- allPoints) {
           find(point) match {
             case Some(ab) if ab != null	=> map += (point -> ab)
            		 							log("ab.size " + ab.size)
             case _							=> 
           }
        }
       log("getAllPoints map size " + map.size)
       return map
    }
    
    /**
     * Clear all the info and the nodes for the QuadTree.
     * 
     */
    def clear():Unit = {
      root.values.clear()
    }
    
    /**
     * Node class to represent the rectangle within the QuadTree.
     */
    class Node[V](val nodeRectangle:Rectangle, clusterDistance:Int) {
	        // nodeRectangle - The rectangle covered by this node.
    		log("node " + nodeRectangle)
	        // the sub rectangle that is associated
	        // with the value. might span multiple nodes.
	        var valueRectangle:Rectangle 				= null
	        // The corner of an rectangle that lies within
	        // this node. Used by insert when subdividing
	        // space further.
	        var valuePoint:Point 						= null
	        // All values present in this node. Several 
	        // rectangles can overlap a single node without
	        // ever overlapping each other, which forces us
	        // to keep track of several possible values.
	        var values:Map[Rectangle, ArrayBuffer[V]]	= Map.empty[Rectangle, ArrayBuffer[V]]
    		//contains all the points that have values for this node.
	        var points:ArrayBuffer[Point]				= new ArrayBuffer[Point]()
	        // top left, top right
	        var topLeft:Node[V] 						= null
	        var topRight:Node[V]						= null
	        // bottom left, bottom right
	        var bottomLeft:Node[V]						= null 
	        var bottomRight:Node[V]						= null
	        
	        // Indicates whether or not this node has been further
	        // divided or not. If this value is true, this node will
	        // never contain a value itself, so it's used as a criteria
	        // for continuing searching.
	        var split:Boolean							= false

	     /**
	      * Find the distance between two points. 
	      * 
	      * @param first 		- the first point
	      * @param second 		- the second point
	      * @return boolean 	- yes if the points are within the specified clusterDistance.  Else no.
	      */
	     private[this] def areWithinClusterDistance(first:Point, second:Point):Boolean = {
	        return sqrt(pow((abs(second.x - first.x) + abs(second.y - first.y)), 2)) <= clusterDistance
	     }
	        
	     /**
	      * Checks whether or not a point is contained in this node. 
	      * 
	      * param point 		- the point to check if it is within the node rectangle.
	      * return boolean 		- yes if it is within the node's rectangle.  Else no.
	      */
	     def contains(point:Point):Boolean = {
	            return nodeRectangle.contains(point.x, point.y)
	     }
	        
	    /**
	     * Checks whether or not a rectangle intersects this node.
	     * 
	     * @param rectangle 	- the rectangle to check if it intersects with the node's rectangle.
	     * @return boolean 		- yes if the point intersects with node's rectangle.  Else no.
	     */
	    def intersects(rectangle:Rectangle):Boolean = {
	        return nodeRectangle.intersect(rectangle)
	    }
	    
	    /**
	     * Recursively find the matching rectangle of a point.
	     * No longer used in favor of a faster iterative approach.
	     * 
	     * @param point 						- the point to get all the values found within the same rectangle.
	     * @return optiion of array of value 	- the array of values or null.
	     */
	    def find(point:Point):Option[ArrayBuffer[V]] = {
	        if (!split) {
	            for ((rectangle, value) <- values) {
	                if (rectangle.contains(point.x, point.y)) {
	                    return Some(value)
	                }
	            }
	        }
	    
	        if (topLeft.contains(point)) {
	            return topLeft.find(point)
	        } else if (topRight.contains(point)) {
	            return topRight.find(point)
	        } else if (bottomLeft.contains(point)) {
	            return bottomLeft.find(point)
	        } else if (bottomRight.contains(point)) {
	            return bottomRight.find(point)
	        } else {
	          return None
	        }
	    }
	    
	    /**
	     * Recursively find the matching rectangle.
	     * 
	     * @param rectangle 					- the rectangle to match against.
	     * @return option of array of values 	- array of values found within the matched rectangle
	     */
	    def find(rectangle:Rectangle):Option[ArrayBuffer[V]] = {
	        if (!split) {
	            for ((rectangle, value) <- values) {
	                if (nodeRectangle.contains(rectangle)) {
	                    return Some(value)
	                }
	            }
	        }
	    
	        if (topLeft.nodeRectangle.contains(rectangle)) {
	            return topLeft.find(rectangle)
	        } else if (topRight.nodeRectangle.contains(rectangle)) {
	            return topRight.find(rectangle)
	        } else if (bottomLeft.nodeRectangle.contains(rectangle)) {
	            return bottomLeft.find(rectangle)
	        } else if (bottomRight.nodeRectangle.contains(rectangle)) {
	            return bottomRight.find(rectangle)
	        } else {
	          return None
	        }
	    }
	    
	    /**
	     * This allows to get all points stored in this node - root + subnodes
	     * 
	     * @return array of points 				- all points found within the node's rectangle.
	     */
	    def getAllPoints():ArrayBuffer[Point] = {
	    	if (!split) {
	    	  return points
	    	}
	    	
	    	var array:ArrayBuffer[Point]			= ArrayBuffer[Point]()
	    	array 									++= topRight.getAllPoints() ++= topLeft.getAllPoints() ++= bottomLeft.getAllPoints() ++= bottomRight.getAllPoints()
	    	return array
	    }
	    
	    /**
	     * This linearly search the rectangle for the values found within the node's rectangle that contains the given point.
	     * 
	     *  @param data							- hashmap of rectangle key and array of values.
	     *  @param point 						- point to match the rectangle.
	     */
	    def linearSearch(data:Map[Rectangle, ArrayBuffer[V]], point:Point):ArrayBuffer[V] = {
	        for ((rectangle, value) <- data) {
	            if (rectangle.contains(point.x, point.y)) {
	                return value
	            }
	        }
	        
	        return null
	    }
	    
	     /**
	     * Insert a new rectangle and corresponding value. Recursively
	     * splits space as needed.  This is the main method that sets up the space and split it when
	     * the points are over the cluster distance.
	     * 
	     * @param point 						- point to match the node's rectangle.
	     * @param value 						- array of values to intert into the space.
	     * @param depth 						- the depth of the space that has been split.
	     */
	    @throws(classOf[IntersectionException])
	    def insert(point:Point, rectangle:Rectangle , value:ArrayBuffer[V], depth:Int):Unit = {
	        // this node doesn't matche the point
	        if (!nodeRectangle.contains(point.x, point.y)) {
	            //System.out.println(nodeRectangle + " does not match " + point)
	            return
	        }
	        // no value has been assigned to this
	        // node, so we don't have to split it
	        
	        if (this.valuePoint == null && !split) {
	            if (!values.contains(rectangle)) {
	            	values						+= (rectangle -> value)
	            } else {
	            	values(rectangle) 			++= value
	            }
	            valueRectangle 					= rectangle
	            valuePoint 						= point
	            points							+= point
	            return
	        } else if (this.valuePoint != null && !split && areWithinClusterDistance(point, valuePoint)) {
	           //log("(this.valuePoint != null && !split &&  array.size < maxItemsPerPoint && areWithinClusterDistance(point, valuePoint)")
	           if (!values.contains(rectangle)) {
	            	values 						+= (rectangle -> value)
	        	    //log("!values.contains(rectangle) values size " + values.size) 
	            } else {
	            	values(rectangle) 			++= value
	            	//log("values.contains(rectangle) values size " + values.size) 
	            }
	            valueRectangle 					= rectangle
	            val midPoint					= new Point((point.x+valuePoint.x)/2, (point.y+valuePoint.y)/2)
	            points							-= valuePoint 						
	            valuePoint						= midPoint
	            points							+= valuePoint
	            return
	        }
	        
	        // initialize subnodes
	        if (!split) {
	            //System.out.println("splitting")
	            val totalWidth:Long 			= nodeRectangle.width()
	            val totalHeight:Long			= nodeRectangle.height()
	            val w1:Int 						= (totalWidth / 2).asInstanceOf[Int]
	            val h1:Int 						= (totalHeight / 2).asInstanceOf[Int]
	            val w2:Int 						= (totalWidth - w1).asInstanceOf[Int]
	            val h2:Int 						= (totalHeight - h1).asInstanceOf[Int]
	            
	            topLeft = new Node[V](new Rectangle(nodeRectangle.left, nodeRectangle.top, 
	                nodeRectangle.left + w1, nodeRectangle.top - h1), clusterDistance)
	            //System.out.println(topLeft.nodeRectangle)
	            topRight = new Node[V](new Rectangle(nodeRectangle.left + w1, nodeRectangle.top, 
	                nodeRectangle.left + w1 + w2, nodeRectangle.top - h1), clusterDistance)
	            //System.out.println(topRight.nodeRectangle)
	            bottomLeft = new Node[V](new Rectangle(nodeRectangle.left, nodeRectangle.top - h1,
	                nodeRectangle.left + w1, nodeRectangle.top - h1 - h2), clusterDistance)
	            //System.out.println(bottomLeft.nodeRectangle)
	            bottomRight = new Node[V](new Rectangle(nodeRectangle.left + w1, nodeRectangle.top - h1,
	                nodeRectangle.left + w1 + w2, nodeRectangle.top - h1 - h2),  clusterDistance)
	            //System.out.println(bottomRight.nodeRectangle)
	                
	            split = true
	
	            // move current value to subsection
	            val value:ArrayBuffer[V] 		= values(valueRectangle)
	            if (topLeft.contains(valuePoint)) {
	                topLeft.insert(this.valuePoint, this.valueRectangle, value, depth+1)
	            } else if (topRight.contains(valuePoint)) {
	                topRight.insert(this.valuePoint, this.valueRectangle, value, depth+1)
	            } else if (bottomLeft.contains(valuePoint)) {
	                bottomLeft.insert(this.valuePoint, this.valueRectangle, value, depth+1)
	            } else if (bottomRight.contains(valuePoint)) {
	                bottomRight.insert(this.valuePoint, this.valueRectangle, value, depth+1)
	            } else {
	                throw new IllegalStateException(this.valuePoint + " is not " + 
	                    "in " + topLeft.nodeRectangle + "\n" + 
	                    "or " + topRight.nodeRectangle + "\n" + 
	                    "or " + bottomLeft.nodeRectangle + "\n" + 
	                    "or " + bottomRight.nodeRectangle)
	            }
	            
	            // transfer all rectangles that intersect this node and
	            // their corresponding values to the new subnodes
	            for ((candidate, value) <- values) {
	                if (topLeft.intersects(candidate)) {
	                	if (!topLeft.values.contains(candidate)) {
	                	  topLeft.values 			+= (candidate -> value)
	                	} else {
	                	  topLeft.values(candidate) ++ value
	                	}
	                    
	                } 
	                if (topRight.intersects(candidate)) {
	                    if (!topRight.values.contains(candidate)) {
	                	  topRight.values 			+= (candidate -> value)
	                	} else {
	                	  topRight.values(candidate) ++= value
	                	}
	                } 
	                if (bottomLeft.intersects(candidate)) {
	                    if (!bottomLeft.values.contains(candidate)) {
	                	  bottomLeft.values 			+= (candidate -> value)
	                	} else {
	                	  bottomLeft.values(candidate) ++= value
	                	}
	                } 
	                if (bottomRight.intersects(candidate)) {
	                    if (!bottomRight.values.contains(candidate)) {
	                	  bottomRight.values 			+= (candidate -> value)
	                	} else {
	                	  bottomRight.values(candidate) ++= value
	                	}
	                }
	            }
	        }
	        
	        // insert new value
	        if (topLeft.contains(point)) {
	            topLeft.insert(point, rectangle, value, depth+1)
	        } else if (topRight.contains(point)) {
	            topRight.insert(point, rectangle, value, depth+1)
	        } else if (bottomLeft.contains(point)) {
	            bottomLeft.insert(point, rectangle, value, depth+1)
	        } else if (bottomRight.contains(point)) {
	            bottomRight.insert(point, rectangle, value, depth+1)
	        } else {
	            throw new IllegalStateException(point + " is not in " + topLeft.nodeRectangle + "\n" + 
	                "or " + topRight.nodeRectangle + "\n" + 
	                "or " + bottomLeft.nodeRectangle + "\n" + 
	                "or " + bottomRight.nodeRectangle)
	        }
	        
	        values.clear()
	        valueRectangle = null
	        valuePoint = null
	        points.clear()
	    }
	    
	     /**
	     * Find out if any rectangle currently in the tree intersects
	     * the passed rectangle. Used by insert() to prevent overlapping
	     * rectangles from being inserted.
	     * 
	     * @param rectangle 							- the rectangle to check if it intersects with the node's rectangle.
	     * @return boolean 								- yes if it intersects.  Else no.
	     */
	    def findIntersections(rectangle:Rectangle):Boolean = {
	        if (!split) {
	            for ((candidate, value) <- values) {
	                if (candidate.intersect(rectangle)) {
	                    return true
	                }
	            }
	            return false
	        }
	    
	        		if 	(topLeft.intersects(rectangle) 		&& topLeft.findIntersections(rectangle)) {
	            return true
	        } else 	if 	(topRight.intersects(rectangle) 	&& topRight.findIntersections(rectangle)) {
	            return true
	        } else 	if 	(bottomLeft.intersects(rectangle) 	&& bottomRight.findIntersections(rectangle)) {
	            return true
	        } else	if 	(bottomRight.intersects(rectangle) 	&& bottomRight.findIntersections(rectangle)) {
	            return true
	        }
	        
	        return false
	    }
	    
	    /**
	     * Find all nodes/nodes within a specified rectangle, and assign
	     * a specified value to them. This is used to speed up lookup for
	     * nodes that completely lies inside a rectangle, and thus won't
	     * have their value set by Node.insert().
	     * 
	     * @param rectangle 							- the rectangle that will be used to assigned or store the value.
	     * @param value 								- the array of values to store at this rectangle.
	     */
	    def assign(rectangle:Rectangle, value:ArrayBuffer[V]):Unit = {
	        if (!split) {
	        	if (!values.contains(rectangle)) {
	        		values						+= (rectangle -> value)
	        		return
	        	} else {
	        		values(rectangle) 			++= value
	        		return
	        	}
	        
	        }
	        if (topLeft.intersects(rectangle)) {
	            topLeft.assign(rectangle, value)
	        } 
	        if (topRight.intersects(rectangle)) {
	            topRight.assign(rectangle, value)
	        } 
	        if (bottomLeft.intersects(rectangle)) {
	            bottomLeft.assign(rectangle, value)
	        } 
	        if (bottomRight.intersects(rectangle)) {
	            bottomRight.assign(rectangle, value)
	        }
	    }
     }  
}

/**
 * The exception class to wrap and throw errors found in the operation.
 */
class IntersectionException(exception:String) extends Exception(exception) {
  def this() = this("")
}