/**********************************************************************
 * $Id: AbstractSTRtree.cpp 1820 2006-09-06 16:54:23Z mloskot $
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * Copyright (C) 2006 Refractions Research Inc.
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation. 
 * See the COPYING file for more information.
 *
 **********************************************************************/

#include <geos/index/strtree/AbstractSTRtree.h>
#include <geos/index/strtree/AbstractNode.h>
#include <geos/index/strtree/ItemBoundable.h>
#include <geos/index/ItemVisitor.h>

#include <algorithm>
#include <vector>
#include <typeinfo>
#include <cassert>

using namespace std;

namespace geos {
namespace index { // geos.index
namespace strtree { // geos.index.strtree


AbstractSTRtree::~AbstractSTRtree()
{
	assert(itemBoundables);

	for (size_t i=0, ibsize=itemBoundables->size(); i<ibsize; ++i)
		delete (*itemBoundables)[i];
	delete itemBoundables;

	assert(nodes);
	for (size_t i=0, nsize=nodes->size(); i<nsize; i++)
		delete (*nodes)[i];
	delete nodes;
}

/*public*/
void
AbstractSTRtree::build()
{
	assert(!built);
	root=(itemBoundables->empty()?createNode(0):createHigherLevels(itemBoundables,-1));
	built=true;
}

/*protected*/
vector<Boundable*>*
AbstractSTRtree::createParentBoundables(vector<Boundable*> *childBoundables,
		int newLevel)
{
	assert(!childBoundables->empty());
	vector<Boundable*> *parentBoundables=new vector<Boundable*>();
	parentBoundables->push_back(createNode(newLevel));
	vector<Boundable*> *sortedChildBoundables=sortBoundables(childBoundables);

	for(size_t i=0, scbsize=sortedChildBoundables->size(); i<scbsize; ++i)
	{
		//Boundable *childBoundable=static_cast<AbstractNode*>((*sortedChildBoundables)[i]);
		Boundable *childBoundable=(*sortedChildBoundables)[i];

		AbstractNode *last = lastNode(parentBoundables);
		if (last->getChildBoundables()->size() == nodeCapacity)
		{
			last=createNode(newLevel);
			parentBoundables->push_back(last);
		}
		last->addChildBoundable(childBoundable);
	}
	delete sortedChildBoundables;
	return parentBoundables;
}

/*private*/
AbstractNode*
AbstractSTRtree::createHigherLevels(vector<Boundable*> *boundablesOfALevel, int level)
{
	assert(!boundablesOfALevel->empty());
	vector<Boundable*> *parentBoundables=createParentBoundables(boundablesOfALevel,level+1);
	if (parentBoundables->size()==1) {
		AbstractNode *ret = (AbstractNode*)(*parentBoundables)[0];
		delete parentBoundables;
		return ret;
	}
	AbstractNode *ret = createHigherLevels(parentBoundables,level+1);
	delete parentBoundables;
	return ret;
}

/*protected*/
void
AbstractSTRtree::insert(const void* bounds,void* item)
{
	// Cannot insert items into an STR packed R-tree after it has been built
	assert(!built);
	itemBoundables->push_back(new ItemBoundable(bounds,item));
}

/*protected*/
void
AbstractSTRtree::query(const void* searchBounds, vector<void*>& matches)
{
	if (!built) build();

	if (itemBoundables->empty()) assert(root->getBounds()==NULL);

	if (getIntersectsOp()->intersects(root->getBounds(), searchBounds))
	{
		query(searchBounds,root, &matches);
	}
}

/*protected*/
void
AbstractSTRtree::query(const void* searchBounds, ItemVisitor& visitor)
{
	if (!built) build();

	if (itemBoundables->empty()) assert(root->getBounds()==NULL);
	
	if (getIntersectsOp()->intersects(root->getBounds(),searchBounds))
	{
		query(searchBounds, *root, visitor);
	}
}

/*protected*/
void
AbstractSTRtree::query(const void* searchBounds, AbstractNode& node,
		ItemVisitor& visitor)
{
	vector<Boundable*>& boundables = *(node.getChildBoundables());

	for (vector<Boundable*>::iterator i=boundables.begin(), e=boundables.end();
			i!=e; i++)
	{
		Boundable* childBoundable = *i;
		if (!getIntersectsOp()->intersects(childBoundable->getBounds(), searchBounds)) {
			continue;
		}

		if(AbstractNode *an=dynamic_cast<AbstractNode*>(childBoundable))
		{
			query(searchBounds, *an, visitor);
		}
		else if (ItemBoundable *ib=dynamic_cast<ItemBoundable *>(childBoundable))
		{
			visitor.visitItem(ib->getItem());
		}
		else
		{
			assert(0); // unsupported childBoundable type
		}
	}
}

/* protected */
bool
AbstractSTRtree::remove(const void* searchBounds, void* item)
{
	if (!built) build();
	if (itemBoundables->empty()) {
		assert(root->getBounds() == NULL);
	}
	if (getIntersectsOp()->intersects(root->getBounds(), searchBounds)) {
		return remove(searchBounds, *root, item);
	}
	return false;
}

/* private */
bool
AbstractSTRtree::remove(const void* searchBounds, AbstractNode& node, void* item)
{
	// first try removing item from this node
	if ( removeItem(node, item) ) return true;

	vector<Boundable*>& boundables = *(node.getChildBoundables());

	// next try removing item from lower nodes
	for (vector<Boundable*>::iterator i=boundables.begin(), e=boundables.end();
			i!=e; i++)
	{
		Boundable* childBoundable = *i;
		if (!getIntersectsOp()->intersects(childBoundable->getBounds(), searchBounds))
			continue;

		if (AbstractNode *an=dynamic_cast<AbstractNode*>(childBoundable))
		{
			// if found, record child for pruning and exit
			if ( remove(searchBounds, *an, item) )
			{
				if (an->getChildBoundables()->empty()) {
					boundables.erase(i);
				}
				return true;
			}
		}
	}

	return false;
}

/*private*/
bool
AbstractSTRtree::removeItem(AbstractNode& node, void* item)
{
	vector<Boundable*>& boundables = *(node.getChildBoundables());

	vector<Boundable*>::iterator childToRemove = boundables.end();

	for (vector<Boundable*>::iterator i=boundables.begin(),
			e=boundables.end();
			i!=e; i++)
	{
		Boundable* childBoundable = *i;
		if (ItemBoundable *ib=dynamic_cast<ItemBoundable*>(childBoundable))
		{
			if ( ib->getItem() == item) childToRemove = i;
		}
	}
	if (childToRemove != boundables.end()) {
		boundables.erase(childToRemove);
		return true;
	}
	return false;
}





/*public*/
void
AbstractSTRtree::query(const void* searchBounds,
	AbstractNode* node, vector<void*> *matches)
{
	vector<Boundable*> *vb=node->getChildBoundables();

	IntersectsOp *io=getIntersectsOp();
	size_t vbsize=vb->size();
	//cerr<<"AbstractSTRtree::query: childBoundables: "<<vbsize<<endl;
	for(size_t i=0;i<vbsize;i++)
	{
		Boundable *childBoundable=(*vb)[i];
		if (!io->intersects(childBoundable->getBounds(),searchBounds))
		{
			continue;
		}

		if(AbstractNode *an=dynamic_cast<AbstractNode*>(childBoundable))
		{
			query(searchBounds, an, matches);
		}
		else if (ItemBoundable *ib=dynamic_cast<ItemBoundable *>(childBoundable))
		{
			matches->push_back(ib->getItem());
		}
		else
		{
			assert(0); // unsupported childBoundable type
		}
	}
}

/*protected*/
vector<Boundable*>*
AbstractSTRtree::boundablesAtLevel(int level)
{
	vector<Boundable*> *boundables=new vector<Boundable*>();
	boundablesAtLevel(level,root,boundables);
	return boundables;
}

/*public*/
void
AbstractSTRtree::boundablesAtLevel(int level, AbstractNode* top,
		vector<Boundable*> *boundables)
{
	assert(level>-2);
	if (top->getLevel()==level)
	{
		boundables->push_back(top);
		return;
	}
	vector<Boundable*> *vb=top->getChildBoundables();
	for(size_t i=0, vbsize=vb->size(); i<vbsize; i++)
	{
		Boundable *boundable=(*vb)[i];
		if (typeid(*boundable)==typeid(AbstractNode))
		{
			boundablesAtLevel(level, (AbstractNode*)boundable,
				boundables);
		}
		else
		{
			assert(typeid(*boundable)==typeid(ItemBoundable));
			if (level==-1)
			{
				boundables->push_back(boundable);
			}
		}
	}
	return;
}

} // namespace geos.index.strtree
} // namespace geos.index
} // namespace geos

/**********************************************************************
 * $Log$
 * Revision 1.30  2006/06/12 10:49:43  strk
 * unsigned int => size_t
 *
 * Revision 1.29  2006/03/21 10:47:34  strk
 * indexStrtree.h split
 *
 * Revision 1.28  2006/03/03 10:46:21  strk
 * Removed 'using namespace' from headers, added missing headers in .cpp files, removed useless includes in headers (bug#46)
 *
 * Revision 1.27  2006/02/23 11:54:20  strk
 * - MCIndexPointSnapper
 * - MCIndexSnapRounder
 * - SnapRounding BufferOp
 * - ScaledNoder
 * - GEOSException hierarchy cleanups
 * - SpatialIndex memory-friendly query interface
 * - GeometryGraph::getBoundaryNodes memory-friendly
 * - NodeMap::getBoundaryNodes memory-friendly
 * - Cleanups in geomgraph::Edge
 * - Added an XML test for snaprounding buffer (shows leaks, working on it)
 *
 * Revision 1.26  2006/02/20 21:04:37  strk
 * - namespace geos::index
 * - SpatialIndex interface synced
 *
 * Revision 1.25  2006/02/20 10:14:18  strk
 * - namespaces geos::index::*
 * - Doxygen documentation cleanup
 *
 * Revision 1.24  2005/02/15 17:15:13  strk
 * Inlined most Envelope methods, reserved() memory for some vectors when
 * the usage was known a priori.
 *
 * Revision 1.23  2005/01/31 15:41:03  strk
 * Small optimizations.
 *
 * Revision 1.22  2004/12/08 13:54:43  strk
 * gcc warnings checked and fixed, general cleanups.
 *
 * Revision 1.21  2004/11/08 15:58:13  strk
 * More performance tuning.
 *
 * Revision 1.20  2004/11/04 19:08:07  strk
 * Cleanups, initializers list, profiling.
 *
 * Revision 1.19  2004/11/01 16:43:04  strk
 * Added Profiler code.
 * Temporarly patched a bug in DoubleBits (must check drawbacks).
 * Various cleanups and speedups.
 *
 * Revision 1.18  2004/07/27 16:35:46  strk
 * Geometry::getEnvelopeInternal() changed to return a const Envelope *.
 * This should reduce object copies as once computed the envelope of a
 * geometry remains the same.
 *
 * Revision 1.17  2004/07/13 08:33:52  strk
 * Added missing virtual destructor to virtual classes.
 * Fixed implicit unsigned int -> int casts
 *
 * Revision 1.16  2004/07/02 13:28:27  strk
 * Fixed all #include lines to reflect headers layout change.
 * Added client application build tips in README.
 *
 * Revision 1.15  2004/05/06 15:00:59  strk
 * Boundable destructor made virtual.
 * Added vector <AbstractNode *> *nodes member in AbstractSTRTree,
 * used to keep track of created node to cleanly delete them at
 * destruction time.
 *
 * Revision 1.14  2004/05/06 08:59:19  strk
 * memory leak fixed
 *
 * Revision 1.13  2004/05/05 17:42:06  strk
 * AbstractNode destructor made virtual. AbstractNode::bounds made protected.
 * SIRAbstractNode and STRAbstractNode destructors added to get rid of
 * AbstractNode::bounds in the right way (is a void * casted to appropriate
 * Class in the subClasses).
 *
 * Revision 1.12  2004/05/03 22:56:44  strk
 * leaks fixed, exception specification omitted.
 *
 * Revision 1.11  2004/05/03 16:29:21  strk
 * Added sortBoundables(const vector<Boundable *>) pure virtual in AbstractSTRtree,
 * implemented in SIRtree and STRtree. Comparator funx made static in STRtree.cpp
 * and SIRtree.cpp.
 *
 * Revision 1.10  2004/05/03 13:17:55  strk
 * Fixed comparator function to express StrictWeakOrdering.
 *
 * Revision 1.9  2004/04/28 14:58:47  strk
 * Made AbstractSTRtree::query use dynamic_cast<> to simulate java's
 * instanceof. Previous typeid(*) use missed to catch an STRAbstractNode
 * as a class derived from AbstractNode. Still have to check if this
 * is the correct semantic with Martin, but at least lots of SIGABORT
 * are no more raised.
 *
 * Revision 1.8  2004/04/26 12:37:19  strk
 * Some leaks fixed.
 *
 * Revision 1.7  2004/04/14 12:28:43  strk
 * shouldNeverReachHere exceptions made more verbose
 *
 * Revision 1.6  2004/03/25 02:23:55  ybychkov
 * All "index/" packages upgraded to JTS 1.4
 *
 * Revision 1.5  2003/11/07 01:23:42  pramsey
 * Add standard CVS headers licence notices and copyrights to all cpp and h
 * files.
 *
 *
 **********************************************************************/