//
// ITIOQTrees.js
// Date: 11/10/2007
// QTree code for subdividing a geographocal region

// QTNode is an object representing a node of a quadtree
// To make a quadtree, create a root node of type QTNode.

// Data is held in containers of type QTLocation
// Each QTLocation must have a its Lat and Lng specified by the constructor, the
// object is then saved in the final argument of the QTLocation constructor.  

// Complete QTLocation objects may then be inserted into a Quadtree
// Doing so populates the QuadTree accordingly.

// To retreive objects from the QuadTree, a GLatLngBounds object should be passed to
// QTNode.GetBoundedLocations(...), the return value is an array of all Location within
// the specified bounds
function QTNode(Bounds,nMaxLocationsPerNode) //Create a new QuadTree node with the specified bounds(lat/lon)
{
  var SW,Span;

  // Data
  this.Bounds = Bounds;
  this.MaxLocationsPerNode = nMaxLocationsPerNode;

  //Calculating Midpoints
  SW = Bounds.getSouthWest();
  Span = Bounds.toSpan();
  this.Midpoint = new GLatLng( 
      (Span.lat() / 2.0)+SW.lat(),
      (Span.lng() / 2.0)+SW.lng()
    );

  //An array of the 4 Child Nodes under this Node
  this.aChildNodes = null;
  
  //Contains location based items
  this.aLocations = null;
  
  // Methods
  this.GetQuadIndex = QTGetQuadIndex;
  this.AddObject = QTAddObject;
  this.AddLocation = QTAddLocation;
  this.Subdivide = QTSubdivide;
  this.GetBoundedLocations=QTGetBoundedLocations;
  this.GetBoundedChildNodes=QTGetBoundedChildNodes;
}


//Object to hold Locations/Data
function QTLocation( Coord, Object )
{
  this.Coord = Coord;
  this.Object = Object;
  
  //methods here
  this.GetCoordinates = function(){ return this.Coord };
  this.GetObject = function(){ return this.Object };
  this.SetCoordinates = function ( Coordinates ) { this.Coord = Coordinates; };
  this.SetObject = function ( oObject ) { this.Object = oObject; };;
}

function QTGetQuadIndex(Location)
{
var Coords = Location.GetCoordinates();
var nQuadIndex = -1;

  if( (Coords.lng())	> (this.Midpoint.lng())	)
  {
    if(	(Coords.lat()) >	(this.Midpoint.lat()) )
    {
      //position 0
      nQuadIndex = 0;
    }
    else
    {
      //position 1
      nQuadIndex = 1;
    }
  }
  else
  {
    if(	(Coords.lat()) >	(this.Midpoint.lat()) )
    {
      //position 3
      nQuadIndex = 3;
    }
    else
    {
      //position 2
      nQuadIndex = 2;
    }
  }
  return nQuadIndex;
}

function QTAddObject( nLattitude, nLongitude, oObject )
{
  this.AddLocation(new QTLocation(new GLatLng(nLattitude, nLongitude), oObject));
}

function QTAddLocation( Location )
{
  if( this.aChildNodes != null )//Region is already divided, just add the node under one of the subregions
  {
    this.aChildNodes[this.GetQuadIndex(Location)].AddLocation( Location );
  }
  else if( this.aLocations == null )//allocate storage for items and add here
  {
    this.aLocations = [Location];
  }
  else if( this.aLocations.length < this.MaxLocationsPerNode )//we can add more to this region
  {
    this.aLocations[this.aLocations.length] = Location; //this.aLocations.concat([item]);
  }
  else //divide this region into 4 regions and add to the appropiate quad
  {
    this.Subdivide();
    this.AddLocation(Location);  
  }
}


function QTSubdivide()
{  
var nLoop, tmpLocation, SW, NE, N, E, S, W;

  SW = this.Bounds.getSouthWest();
  NE = this.Bounds.getNorthEast();
  N = new GLatLng( NE.lat(), this.Midpoint.lng() );
  E = new GLatLng( this.Midpoint.lat(), NE.lng() );
  S = new GLatLng( SW.lat(), this.Midpoint.lng() );
  W = new GLatLng( this.Midpoint.lat(), SW.lng() );


  this.aChildNodes = [ new QTNode(new GLatLngBounds(this.Midpoint,NE), this.MaxLocationsPerNode),
      new QTNode(new GLatLngBounds(S,E), this.MaxLocationsPerNode),
      new QTNode(new GLatLngBounds(SW,this.Midpoint), this.MaxLocationsPerNode),
      new QTNode(new GLatLngBounds(W,N), this.MaxLocationsPerNode)
  ];

  //relocate the data to one of the child nodes
  for( nLoop = 0; nLoop < this.aLocations.length; nLoop++ )
  {
    tmpLocation = this.aLocations[nLoop];
    this.AddLocation( tmpLocation );
  }
  this.aLocations = null;
}

//returns a list of Locations that intersect a certain bounds
function QTGetBoundedLocations( Bounds ) //only traverse quads within the bounds
{
var nLoop = 0;
var aLocations = [];
var aChildNodes = this.GetBoundedChildNodes(Bounds);

  //loop though the child nodes returning the locations within
  for( nLoop = 0; nLoop < aChildNodes.length; nLoop++ )
  {
    if( aChildNodes[nLoop].aLocations != null )
    {
      //add the data to our items
      aLocations = aLocations.concat( aChildNodes[nLoop].aLocations );
    }
  }
  return aLocations;
}

//returns a list of QTNodes that intersect a certain bounds
function QTGetBoundedChildNodes( Bounds ) //only traverse quads within the bounds
{
var aLocations = null;
var tmpALocations = null;
var nLoop = 0;

  if( this.Bounds.intersects(Bounds) )//it intersects
  {
    if(this.aChildNodes != null)//its a divided cell traverse its children
    {
      aLocations = [];
      //check each child node
      for(nLoop = 0; nLoop < 4; nLoop++)
      {
        tmpALocations = this.aChildNodes[nLoop].GetBoundedChildNodes(Bounds);
        if(tmpALocations != null)
        {
          aLocations = aLocations.concat(tmpALocations);
        }
      }
    }
    else //its a leaf node return itself
    {
      aLocations = [this];
    }
  }
  else //no intersection, return an empty array
  {
    aLocations = [];
  }

  return aLocations;
}