node.cc

一个非常好的GIS开源新版本

// Spatial Index Library
//
// Copyright (C) 2002 Navel Ltd.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
//  Email:
//    [e-mail]

#include "../spatialindex/SpatialIndexImpl.h"

#include "RTree.h"
#include "Node.h"
#include "Index.h"

using std::stack;
using std::vector;
using namespace SpatialIndex::RTree;

//
// Tools::IObject interface
//
Tools::IObject* Node::clone()
{
	throw Tools::NotSupportedException("IObject::clone should never be called.");
}

//
// Tools::ISerializable interface
//
unsigned long Node::getByteArraySize()
{
	return
		(sizeof(long) +
		sizeof(long) +
		sizeof(long) +
		(m_children * (m_pTree->m_dimension * sizeof(double) * 2 + sizeof(long) + sizeof(unsigned long))) +
		m_totalDataLength +
		(2 * m_pTree->m_dimension * sizeof(double)));
}

void Node::loadFromByteArray(const byte* ptr)
{
	m_nodeMBR = m_pTree->m_infiniteRegion;

	// skip the node type information, it is not needed.
	ptr += sizeof(long);

	memcpy(&m_level, ptr, sizeof(long));
	ptr += sizeof(long);

	memcpy(&m_children, ptr, sizeof(long));
	ptr += sizeof(long);

	for (unsigned long cChild = 0; cChild < m_children; cChild++)
	{
		m_ptrMBR[cChild] = m_pTree->m_regionPool.acquire();
		*(m_ptrMBR[cChild]) = m_pTree->m_infiniteRegion;

		memcpy(m_ptrMBR[cChild]->m_pLow, ptr, m_pTree->m_dimension * sizeof(double));
		ptr += m_pTree->m_dimension * sizeof(double);
		memcpy(m_ptrMBR[cChild]->m_pHigh, ptr, m_pTree->m_dimension * sizeof(double));
		ptr += m_pTree->m_dimension * sizeof(double);
		memcpy(&(m_pIdentifier[cChild]), ptr, sizeof(long));
		ptr += sizeof(long);

		memcpy(&(m_pDataLength[cChild]), ptr, sizeof(unsigned long));
		ptr += sizeof(unsigned long);

		if (m_pDataLength[cChild] > 0)
		{
			m_totalDataLength += m_pDataLength[cChild];
			m_pData[cChild] = new byte[m_pDataLength[cChild]];
			memcpy(m_pData[cChild], ptr, m_pDataLength[cChild]);
			ptr += m_pDataLength[cChild];
		}
		else
		{
			m_pData[cChild] = 0;
		}

		//m_nodeMBR.combineRegion(*(m_ptrMBR[cChild]));
	}

	memcpy(m_nodeMBR.m_pLow, ptr, m_pTree->m_dimension * sizeof(double));
	ptr += m_pTree->m_dimension * sizeof(double);
	memcpy(m_nodeMBR.m_pHigh, ptr, m_pTree->m_dimension * sizeof(double));
	//ptr += m_pTree->m_dimension * sizeof(double);
}

void Node::storeToByteArray(byte** data, unsigned long& len)
{
	len = getByteArraySize();

	*data = new byte[len];
	byte* ptr = *data;

	long type;

	if (m_level == 0) type = PersistentLeaf;
	else type = PersistentIndex;

	memcpy(ptr, &type, sizeof(long));
	ptr += sizeof(long);

	memcpy(ptr, &m_level, sizeof(long));
	ptr += sizeof(long);

	memcpy(ptr, &m_children, sizeof(long));
	ptr += sizeof(long);

	for (unsigned long cChild = 0; cChild < m_children; cChild++)
	{
		memcpy(ptr, m_ptrMBR[cChild]->m_pLow, m_pTree->m_dimension * sizeof(double));
		ptr += m_pTree->m_dimension * sizeof(double);
		memcpy(ptr, m_ptrMBR[cChild]->m_pHigh, m_pTree->m_dimension * sizeof(double));
		ptr += m_pTree->m_dimension * sizeof(double);
		memcpy(ptr, &(m_pIdentifier[cChild]), sizeof(long));
		ptr += sizeof(long);

		memcpy(ptr, &(m_pDataLength[cChild]), sizeof(unsigned long));
		ptr += sizeof(unsigned long);

		if (m_pDataLength[cChild] > 0)
		{
			memcpy(ptr, m_pData[cChild], m_pDataLength[cChild]);
			ptr += m_pDataLength[cChild];
		}
	}

	// store the node MBR for efficiency. This increases the node size a little bit.
	memcpy(ptr, m_nodeMBR.m_pLow, m_pTree->m_dimension * sizeof(double));
	ptr += m_pTree->m_dimension * sizeof(double);
	memcpy(ptr, m_nodeMBR.m_pHigh, m_pTree->m_dimension * sizeof(double));
	//ptr += m_pTree->m_dimension * sizeof(double);

	assert(len == (ptr - *data) + m_pTree->m_dimension * sizeof(double));
}

//
// SpatialIndex::IEntry interface
//
long Node::getIdentifier() const
{
	return m_identifier;
}

void Node::getShape(IShape** out) const
{
	*out = new Region(m_nodeMBR);
}

//
// SpatialIndex::INode interface
//
unsigned long Node::getChildrenCount() const
{
	return m_children;
}

long Node::getChildIdentifier(unsigned long index) const
{
	if (index < 0 || index >= m_children) throw Tools::IndexOutOfBoundsException(index);

	return m_pIdentifier[index];
}

void Node::getChildShape(unsigned long index, IShape** out) const
{
	if (index < 0 || index >= m_children) throw Tools::IndexOutOfBoundsException(index);

	*out = new Region(*(m_ptrMBR[index]));
}

unsigned long Node::getLevel() const
{
	return m_level;
}

bool Node::isLeaf() const
{
	return (m_level == 0);
}

bool Node::isIndex() const
{
	return (m_level != 0);
}

//
// Internal
//

Node::Node() :
	m_pTree(0),
	m_level(0),
	m_identifier(-1),
	m_children(0),
	m_capacity(0),
	m_pData(0),
	m_ptrMBR(0),
	m_pIdentifier(0),
	m_pDataLength(0),
	m_totalDataLength(0)
{
}

#ifdef _MSC_VER
	// MSVC seems to find RTree* pTree ambiguous
	Node::Node(SpatialIndex::RTree::RTree* pTree, long id, unsigned long level, unsigned long capacity) :
#else
	Node::Node(RTree* pTree, long id, unsigned long level, unsigned long capacity) :
#endif//_MSC_VER
	m_pTree(pTree),
	m_level(level),
	m_identifier(id),
	m_children(0),
	m_capacity(capacity),
	m_pData(0),
	m_ptrMBR(0),
	m_pIdentifier(0),
	m_pDataLength(0),
	m_totalDataLength(0)
{
	m_nodeMBR.makeInfinite(m_pTree->m_dimension);

	try
	{
		m_pDataLength = new unsigned long[m_capacity + 1];
		m_pData = new byte*[m_capacity + 1];
		m_ptrMBR = new RegionPtr[m_capacity + 1];
		m_pIdentifier = new long[m_capacity + 1];
	}
	catch (...)
	{
		delete[] m_pDataLength;
		delete[] m_pData;
		delete[] m_ptrMBR;
		delete[] m_pIdentifier;
		throw;
	}
}

Node::~Node()
{
	if (m_pData != 0)
	{
		for (unsigned long cChild = 0; cChild < m_children; cChild++)
		{
			if (m_pData[cChild] != 0) delete[] m_pData[cChild];
		}

		delete[] m_pData;
	}

	delete[] m_pDataLength;
	delete[] m_ptrMBR;
	delete[] m_pIdentifier;
}

Node& Node::operator=(const Node& n)
{
	throw Tools::IllegalStateException("operator =: This should never be called.");
}

void Node::insertEntry(unsigned long dataLength, byte* pData, Region& mbr, long id)
{
	assert(m_children < m_capacity);

	m_pDataLength[m_children] = dataLength;
	m_pData[m_children] = pData;
	m_ptrMBR[m_children] = m_pTree->m_regionPool.acquire();
	*(m_ptrMBR[m_children]) = mbr;
	m_pIdentifier[m_children] = id;

	m_totalDataLength += dataLength;
	m_children++;

	m_nodeMBR.combineRegion(mbr);
}

void Node::deleteEntry(unsigned long index)
{
	assert(index >= 0 && index < m_children);

	// cache it, since I might need it for "touches" later.
	RegionPtr ptrR = m_ptrMBR[index];

	m_totalDataLength -= m_pDataLength[index];
	if (m_pData[index] != 0) delete[] m_pData[index];

	if (m_children > 1 && index != m_children - 1)
	{
		m_pDataLength[index] = m_pDataLength[m_children - 1];
		m_pData[index] = m_pData[m_children - 1];
		m_ptrMBR[index] = m_ptrMBR[m_children - 1];
		m_pIdentifier[index] = m_pIdentifier[m_children - 1];
	}

	m_children--;

	// WARNING: index has now changed. Do not use it below here.

	if (m_children == 0)
	{
		m_nodeMBR = m_pTree->m_infiniteRegion;
	}
	else if (m_pTree->m_bTightMBRs && m_nodeMBR.touchesRegion(*ptrR))
	{
		for (unsigned long cDim = 0; cDim < m_nodeMBR.m_dimension; cDim++)
		{
			m_nodeMBR.m_pLow[cDim] = std::numeric_limits<double>::max();
			m_nodeMBR.m_pHigh[cDim] = -std::numeric_limits<double>::max();

			for (unsigned long cChild = 0; cChild < m_children; cChild++)
			{
				m_nodeMBR.m_pLow[cDim] = std::min(m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->m_pLow[cDim]);
				m_nodeMBR.m_pHigh[cDim] = std::max(m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->m_pHigh[cDim]);
			}
		}
	}
}

bool Node::insertData(unsigned long dataLength, byte* pData, Region& mbr, long id, stack<long>& pathBuffer, byte* overflowTable)
{
	if (m_children < m_capacity)
	{
		bool adjusted = false;

		// this has to happen before insertEntry modifies m_nodeMBR.
		bool b = m_nodeMBR.containsRegion(mbr);

		insertEntry(dataLength, pData, mbr, id);
		m_pTree->writeNode(this);

		if ((! b) && (! pathBuffer.empty()))
		{
			long cParent = pathBuffer.top(); pathBuffer.pop();
			NodePtr ptrN = m_pTree->readNode(cParent);
			Index* p = static_cast<Index*>(ptrN.get());
			p->adjustTree(this, pathBuffer);
			adjusted = true;
		}

		return adjusted;
	}
	else if (m_pTree->m_treeVariant == RV_RSTAR && (! pathBuffer.empty()) && overflowTable[m_level] == 0)
	{
		overflowTable[m_level] = 1;

		vector<long> vReinsert, vKeep;
		reinsertData(dataLength, pData, mbr, id, vReinsert, vKeep);

		unsigned long lReinsert = vReinsert.size();
		unsigned long lKeep = vKeep.size();

		byte** reinsertdata = 0;
		RegionPtr* reinsertmbr = 0;
		long* reinsertid = 0;
		unsigned long* reinsertlen = 0;
		byte** keepdata = 0;
		RegionPtr* keepmbr = 0;
		long* keepid = 0;
		unsigned long* keeplen = 0;

		try
		{
			reinsertdata = new byte*[lReinsert];
			reinsertmbr = new RegionPtr[lReinsert];
			reinsertid = new long[lReinsert];
			reinsertlen = new unsigned long[lReinsert];

			keepdata = new byte*[m_capacity + 1];
			keepmbr = new RegionPtr[m_capacity + 1];
			keepid = new long[m_capacity + 1];
			keeplen = new unsigned long[m_capacity + 1];
		}
		catch (...)
		{
			delete[] reinsertdata;
			delete[] reinsertmbr;
			delete[] reinsertid;
			delete[] reinsertlen;
			delete[] keepdata;
			delete[] keepmbr;
			delete[] keepid;
			delete[] keeplen;
			throw;
		}

		unsigned long cIndex;

		for (cIndex = 0; cIndex < lReinsert; cIndex++)
		{
			reinsertlen[cIndex] = m_pDataLength[vReinsert[cIndex]];
			reinsertdata[cIndex] = m_pData[vReinsert[cIndex]];
			reinsertmbr[cIndex] = m_ptrMBR[vReinsert[cIndex]];
			reinsertid[cIndex] = m_pIdentifier[vReinsert[cIndex]];
		}

		for (cIndex = 0; cIndex < lKeep; cIndex++)
		{
			keeplen[cIndex] = m_pDataLength[vKeep[cIndex]];
			keepdata[cIndex] = m_pData[vKeep[cIndex]];
			keepmbr[cIndex] = m_ptrMBR[vKeep[cIndex]];
			keepid[cIndex] = m_pIdentifier[vKeep[cIndex]];
		}

		delete[] m_pDataLength;
		delete[] m_pData;
		delete[] m_ptrMBR;
		delete[] m_pIdentifier;

		m_pDataLength = keeplen;
		m_pData = keepdata;
		m_ptrMBR = keepmbr;
		m_pIdentifier = keepid;
		m_children = lKeep;
		m_totalDataLength = 0;

		for (unsigned long cChild = 0; cChild < m_children; cChild++) m_totalDataLength += m_pDataLength[cChild];

		for (unsigned long cDim = 0; cDim < m_nodeMBR.m_dimension; cDim++)
		{
			m_nodeMBR.m_pLow[cDim] = std::numeric_limits<double>::max();
			m_nodeMBR.m_pHigh[cDim] = -std::numeric_limits<double>::max();

			for (unsigned long cChild = 0; cChild < m_children; cChild++)
			{
				m_nodeMBR.m_pLow[cDim] = std::min(m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->m_pLow[cDim]);
				m_nodeMBR.m_pHigh[cDim] = std::max(m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->m_pHigh[cDim]);
			}
		}

		m_pTree->writeNode(this);

		// Divertion from R*-Tree algorithm here. First adjust
		// the path to the root, then start reinserts, to avoid complicated handling
		// of changes to the same node from multiple insertions.
		long cParent = pathBuffer.top(); pathBuffer.pop();
		NodePtr ptrN = m_pTree->readNode(cParent);
		Index* p = static_cast<Index*>(ptrN.get());
		p->adjustTree(this, pathBuffer);

		for (cIndex = 0; cIndex < lReinsert; cIndex++)
		{
			m_pTree->insertData_impl(
				reinsertlen[cIndex], reinsertdata[cIndex],
				*(reinsertmbr[cIndex]), reinsertid[cIndex],
				m_level, overflowTable);
		}

		delete[] reinsertdata;
		delete[] reinsertmbr;
		delete[] reinsertid;
		delete[] reinsertlen;

		return true;
	}
	else
	{
		NodePtr n;
		NodePtr nn;
		split(dataLength, pData, mbr, id, n, nn);

		if (pathBuffer.empty())
		{
			n->m_level = m_level;
			nn->m_level = m_level;
			n->m_identifier = -1;
			nn->m_identifier = -1;
			m_pTree->writeNode(n.get());
			m_pTree->writeNode(nn.get());

			NodePtr ptrR = m_pTree->m_indexPool.acquire();
			if (ptrR.get() == 0)
			{
				ptrR = NodePtr(new Index(m_pTree, m_pTree->m_rootID, m_level + 1), &(m_pTree->m_indexPool));
			}
			else
			{
				//ptrR->m_pTree = m_pTree;
				ptrR->m_identifier = m_pTree->m_rootID;
				ptrR->m_level = m_level + 1;
				ptrR->m_nodeMBR = m_pTree->m_infiniteRegion;
			}

			ptrR->insertEntry(0, 0, n->m_nodeMBR, n->m_identifier);
			ptrR->insertEntry(0, 0, nn->m_nodeMBR, nn->m_identifier);

			m_pTree->writeNode(ptrR.get());

			m_pTree->m_stats.m_nodesInLevel[m_level] = 2;
			m_pTree->m_stats.m_nodesInLevel.push_back(1);
			m_pTree->m_stats.m_treeHeight = m_level + 2;
		}
		else
		{
			n->m_level = m_level;
			nn->m_level = m_level;
			n->m_identifier = m_identifier;
			nn->m_identifier = -1;

			m_pTree->writeNode(n.get());
			m_pTree->writeNode(nn.get());

			long cParent = pathBuffer.top(); pathBuffer.pop();
			NodePtr ptrN = m_pTree->readNode(cParent);
			Index* p = static_cast<Index*>(ptrN.get());
			p->adjustTree(n.get(), nn.get(), pathBuffer, overflowTable);
		}

		return true;
	}
}

void Node::reinsertData(unsigned long dataLength, byte* pData, Region& mbr, long id, vector<long>& reinsert, vector<long>& keep)
{
	ReinsertEntry** v = new ReinsertEntry*[m_capacity + 1];