rtree.cc

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

		m_leafPool.setCapacity(var.m_val.ulVal);
	}

	// region pool capacity
	var = ps.getProperty("RegionPoolCapacity");
	if (var.m_varType != Tools::VT_EMPTY)
	{
		if (var.m_varType != Tools::VT_ULONG) throw Tools::IllegalArgumentException("initOld: Property RegionPoolCapacity must be Tools::VT_ULONG");

		m_regionPool.setCapacity(var.m_val.ulVal);
	}

	// point pool capacity
	var = ps.getProperty("PointPoolCapacity");
	if (var.m_varType != Tools::VT_EMPTY)
	{
		if (var.m_varType != Tools::VT_ULONG) throw Tools::IllegalArgumentException("initOld: Property PointPoolCapacity must be Tools::VT_ULONG");

		m_pointPool.setCapacity(var.m_val.ulVal);
	}

	m_infiniteRegion.makeInfinite(m_dimension);
}

void SpatialIndex::RTree::RTree::storeHeader()
{
	const long headerSize =
		sizeof(long) +							// m_rootID
		sizeof(long) +							// m_treeVariant
		sizeof(double) +						// m_fillFactor
		sizeof(unsigned long) +					// m_indexCapacity
		sizeof(unsigned long) +					// m_leafCapacity
		sizeof(unsigned long) +					// m_nearMinimumOverlapFactor
		sizeof(double) +						// m_splitDistributionFactor
		sizeof(double) +						// m_reinsertFactor
		sizeof(unsigned long) +					// m_dimension
		sizeof(char) +							// m_bTightMBRs
		sizeof(unsigned long) +					// m_stats.m_nodes
		sizeof(unsigned long) +					// m_stats.m_data
		sizeof(unsigned long) +					// m_stats.m_treeHeight
		m_stats.m_treeHeight * sizeof(unsigned long); // m_stats.m_nodesInLevel

	byte* header = new byte[headerSize];
	byte* ptr = header;

	memcpy(ptr, &m_rootID, sizeof(long));
	ptr += sizeof(long);
	memcpy(ptr, &m_treeVariant, sizeof(long));
	ptr += sizeof(long);
	memcpy(ptr, &m_fillFactor, sizeof(double));
	ptr += sizeof(double);
	memcpy(ptr, &m_indexCapacity, sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	memcpy(ptr, &m_leafCapacity, sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	memcpy(ptr, &m_nearMinimumOverlapFactor, sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	memcpy(ptr, &m_splitDistributionFactor, sizeof(double));
	ptr += sizeof(double);
	memcpy(ptr, &m_reinsertFactor, sizeof(double));
	ptr += sizeof(double);
	memcpy(ptr, &m_dimension, sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	char c = (char) m_bTightMBRs;
	memcpy(ptr, &c, sizeof(char));
	ptr += sizeof(char);
	memcpy(ptr, &(m_stats.m_nodes), sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	memcpy(ptr, &(m_stats.m_data), sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	memcpy(ptr, &(m_stats.m_treeHeight), sizeof(unsigned long));
	ptr += sizeof(unsigned long);

	for (unsigned long cLevel = 0; cLevel < m_stats.m_treeHeight; cLevel++)
	{
		memcpy(ptr, &(m_stats.m_nodesInLevel[cLevel]), sizeof(unsigned long));
		ptr += sizeof(unsigned long);
	}

	assert(headerSize == (ptr - header));

	m_pStorageManager->storeByteArray(m_headerID, headerSize, header);

	delete[] header;
}

void SpatialIndex::RTree::RTree::loadHeader()
{
	unsigned long headerSize;
	byte* header = 0;
	m_pStorageManager->loadByteArray(m_headerID, headerSize, &header);

	byte* ptr = header;

	memcpy(&m_rootID, ptr, sizeof(long));
	ptr += sizeof(long);
	memcpy(&m_treeVariant, ptr, sizeof(long));
	ptr += sizeof(long);
	memcpy(&m_fillFactor, ptr, sizeof(double));
	ptr += sizeof(double);
	memcpy(&m_indexCapacity, ptr, sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	memcpy(&m_leafCapacity, ptr, sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	memcpy(&m_nearMinimumOverlapFactor, ptr, sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	memcpy(&m_splitDistributionFactor, ptr, sizeof(double));
	ptr += sizeof(double);
	memcpy(&m_reinsertFactor, ptr, sizeof(double));
	ptr += sizeof(double);
	memcpy(&m_dimension, ptr, sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	char c;
	memcpy(&c, ptr, sizeof(char));
	m_bTightMBRs = c!=0;
	ptr += sizeof(char);
	memcpy(&(m_stats.m_nodes), ptr, sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	memcpy(&(m_stats.m_data), ptr, sizeof(unsigned long));
	ptr += sizeof(unsigned long);
	memcpy(&(m_stats.m_treeHeight), ptr, sizeof(unsigned long));
	ptr += sizeof(unsigned long);

	for (unsigned long cLevel = 0; cLevel < m_stats.m_treeHeight; cLevel++)
	{
		unsigned long cNodes;
		memcpy(&cNodes, ptr, sizeof(unsigned long));
		ptr += sizeof(unsigned long);
		m_stats.m_nodesInLevel.push_back(cNodes);
	}

	delete[] header;
}

void SpatialIndex::RTree::RTree::insertData_impl(unsigned long dataLength, byte* pData, Region& mbr, long id)
{
	assert(mbr.getDimension() == m_dimension);

	stack<long> pathBuffer;
	byte* overflowTable = 0;

	try
	{
		NodePtr root = readNode(m_rootID);

		overflowTable = new byte[root->m_level];
		memset(overflowTable, 0, root->m_level);

		NodePtr l = root->chooseSubtree(mbr, 0, pathBuffer);
		if (l.get() == root.get())
		{
			assert(root.unique());
			root.relinquish();
		}
		l->insertData(dataLength, pData, mbr, id, pathBuffer, overflowTable);

		delete[] overflowTable;
		m_stats.m_data++;
	}
	catch (...)
	{
		delete[] overflowTable;
		throw;
	}
}

void SpatialIndex::RTree::RTree::insertData_impl(unsigned long dataLength, byte* pData, Region& mbr, long id, unsigned long level, byte* overflowTable)
{
	assert(mbr.getDimension() == m_dimension);

	stack<long> pathBuffer;
	NodePtr root = readNode(m_rootID);
	NodePtr n = root->chooseSubtree(mbr, level, pathBuffer);

	assert(n->m_level == level);

	if (n.get() == root.get())
	{
		assert(root.unique());
		root.relinquish();
	}
	n->insertData(dataLength, pData, mbr, id, pathBuffer, overflowTable);
}

bool SpatialIndex::RTree::RTree::deleteData_impl(const Region& mbr, long id)
{
	assert(mbr.m_dimension == m_dimension);

	stack<long> pathBuffer;
	NodePtr root = readNode(m_rootID);
	NodePtr l = root->findLeaf(mbr, id, pathBuffer);
	if (l.get() == root.get())
	{
		assert(root.unique());
		root.relinquish();
	}

	if (l.get() != 0)
	{
		Leaf* pL = static_cast<Leaf*>(l.get());
		pL->deleteData(id, pathBuffer);
		m_stats.m_data--;
		return true;
	}

	return false;
}

long SpatialIndex::RTree::RTree::writeNode(Node* n)
{
	byte* buffer;
	unsigned long dataLength;
	n->storeToByteArray(&buffer, dataLength);

	long page;
	if (n->m_identifier < 0) page = StorageManager::NewPage;
	else page = n->m_identifier;

	try
	{
		m_pStorageManager->storeByteArray(page, dataLength, buffer);
		delete[] buffer;
	}
	catch (Tools::InvalidPageException& e)
	{
		delete[] buffer;
		std::cerr << e.what() << std::endl;
		//std::cerr << *this << std::endl;
		throw Tools::IllegalStateException("writeNode: failed with Tools::InvalidPageException");
	}

	if (n->m_identifier < 0)
	{
		n->m_identifier = page;
		m_stats.m_nodes++;

#ifndef NDEBUG
		try
		{
			m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel.at(n->m_level) + 1;
		}
		catch(...)
		{
			throw Tools::IllegalStateException("writeNode: writing past the end of m_nodesInLevel.");
		}
#else
		m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel[n->m_level] + 1;
#endif
	}

	m_stats.m_writes++;

	for (unsigned long cIndex = 0; cIndex < m_writeNodeCommands.size(); cIndex++)
	{
		m_writeNodeCommands[cIndex]->execute(*n);
	}

	return page;
}

SpatialIndex::RTree::NodePtr SpatialIndex::RTree::RTree::readNode(unsigned long id)
{
	unsigned long dataLength;
	byte* buffer;

	try
	{
		m_pStorageManager->loadByteArray(id, dataLength, &buffer);
	}
	catch (Tools::InvalidPageException& e)
	{
		std::cerr << e.what() << std::endl;
		//std::cerr << *this << std::endl;
		throw Tools::IllegalStateException("readNode: failed with Tools::InvalidPageException");
	}

	try
	{
		long nodeType;
		memcpy(&nodeType, buffer, sizeof(long));

		NodePtr n;

		if (nodeType == PersistentIndex) n = m_indexPool.acquire();
		else if (nodeType == PersistentLeaf) n = m_leafPool.acquire();
		else throw Tools::IllegalStateException("readNode: failed reading the correct node type information");

		if (n.get() == 0)
		{
			if (nodeType == PersistentIndex) n = NodePtr(new Index(this, -1, 0), &m_indexPool);
			else if (nodeType == PersistentLeaf) n = NodePtr(new Leaf(this, -1), &m_leafPool);
		}

		//n->m_pTree = this;
		n->m_identifier = id;
		n->loadFromByteArray(buffer);

		m_stats.m_reads++;

		for (unsigned long cIndex = 0; cIndex < m_readNodeCommands.size(); cIndex++)
		{
			m_readNodeCommands[cIndex]->execute(*n);
		}

		delete[] buffer;
		return n;
	}
	catch (...)
	{
		delete[] buffer;
		throw;
	}
}

void SpatialIndex::RTree::RTree::deleteNode(Node* n)
{
	try
	{
		m_pStorageManager->deleteByteArray(n->m_identifier);
	}
	catch (Tools::InvalidPageException& e)
	{
		std::cerr << e.what() << std::endl;
		//std::cerr << *this << std::endl;
		throw Tools::IllegalStateException("deleteNode: failed with Tools::InvalidPageException");
	}

	m_stats.m_nodes--;
	m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel[n->m_level] - 1;

	for (unsigned long cIndex = 0; cIndex < m_deleteNodeCommands.size(); cIndex++)
	{
		m_deleteNodeCommands[cIndex]->execute(*n);
	}
}

void SpatialIndex::RTree::RTree::rangeQuery(RangeQueryType type, const IShape& query, IVisitor& v)
{
#ifdef PTHREADS
	Tools::SharedLock lock(&m_rwLock);
#else
	if (m_rwLock == false) m_rwLock = true;
	else throw Tools::ResourceLockedException("rangeQuery: cannot acquire a shared lock");
#endif

	try
	{
		stack<NodePtr> st;
		NodePtr root = readNode(m_rootID);

		if (root->m_children > 0 && query.intersectsShape(root->m_nodeMBR)) st.push(root);

		while (! st.empty())
		{
			NodePtr n = st.top(); st.pop();

			if (n->m_level == 0)
			{
				v.visitNode(*n);

				for (unsigned long cChild = 0; cChild < n->m_children; cChild++)
				{
					bool b;
					if (type == ContainmentQuery) b = query.containsShape(*(n->m_ptrMBR[cChild]));
					else b = query.intersectsShape(*(n->m_ptrMBR[cChild]));

					if (b)
					{
						Data data = Data(n->m_pDataLength[cChild], n->m_pData[cChild], *(n->m_ptrMBR[cChild]), n->m_pIdentifier[cChild]);
						v.visitData(data);
						m_stats.m_queryResults++;
					}
				}
			}
			else
			{
				v.visitNode(*n);

				for (unsigned long cChild = 0; cChild < n->m_children; cChild++)
				{
					if (query.intersectsShape(*(n->m_ptrMBR[cChild]))) st.push(readNode(n->m_pIdentifier[cChild]));
				}
			}
		}

#ifndef PTHREADS
		m_rwLock = false;
#endif
	}
	catch (...)
	{
#ifndef PTHREADS
		m_rwLock = false;
#endif
		throw;
	}
}

void SpatialIndex::RTree::RTree::selfJoinQuery(long id1, long id2, const Region& r, IVisitor& vis)
{
	NodePtr n1 = readNode(id1);
	NodePtr n2 = readNode(id2);
	vis.visitNode(*n1);
	vis.visitNode(*n2);

	for (unsigned long cChild1 = 0; cChild1 < n1->m_children; cChild1++)
	{
		if (r.intersectsRegion(*(n1->m_ptrMBR[cChild1])))
		{
			for (unsigned long cChild2 = 0; cChild2 < n2->m_children; cChild2++)
			{
				if (
					r.intersectsRegion(*(n2->m_ptrMBR[cChild2])) &&
					n1->m_ptrMBR[cChild1]->intersectsRegion(*(n2->m_ptrMBR[cChild2])))
				{
					if (n1->m_level == 0)
					{
						if (n1->m_pIdentifier[cChild1] != n2->m_pIdentifier[cChild2])
						{
							assert(n2->m_level == 0);

							std::vector<const IData*> v;
							Data e1(n1->m_pDataLength[cChild1], n1->m_pData[cChild1], *(n1->m_ptrMBR[cChild1]), n1->m_pIdentifier[cChild1]);
							Data e2(n2->m_pDataLength[cChild2], n2->m_pData[cChild2], *(n2->m_ptrMBR[cChild2]), n2->m_pIdentifier[cChild2]);
							v.push_back(&e1);
							v.push_back(&e2);
							vis.visitData(v);
						}
					}
					else
					{
						Region rr = r.getIntersectingRegion(n1->m_ptrMBR[cChild1]->getIntersectingRegion(*(n2->m_ptrMBR[cChild2])));
						selfJoinQuery(n1->m_pIdentifier[cChild1], n2->m_pIdentifier[cChild2], rr, vis);
					}
				}
			}
		}
	}
}

std::ostream& SpatialIndex::RTree::operator<<(std::ostream& os, const RTree& t)
{
	using std::endl;

	os	<< "Dimension: " << t.m_dimension << endl
		<< "Fill factor: " << t.m_fillFactor << endl
		<< "Index capacity: " << t.m_indexCapacity << endl
		<< "Leaf capacity: " << t.m_leafCapacity << endl
		<< "Tight MBRs: " << ((t.m_bTightMBRs) ? "enabled" : "disabled") << endl;

	if (t.m_treeVariant == RV_RSTAR)
	{
		os	<< "Near minimum overlap factor: " << t.m_nearMinimumOverlapFactor << endl
			<< "Reinsert factor: " << t.m_reinsertFactor << endl
			<< "Split distribution factor: " << t.m_splitDistributionFactor << endl;
	}

	if (t.m_stats.getNumberOfNodesInLevel(0) > 0)
		os	<< "Utilization: " << 100 * t.m_stats.getNumberOfData() / (t.m_stats.getNumberOfNodesInLevel(0) * t.m_leafCapacity) << "%" << endl
			<< t.m_stats;

	#ifndef NDEBUG
	os	<< "Leaf pool hits: " << t.m_leafPool.m_hits << endl
		<< "Leaf pool misses: " << t.m_leafPool.m_misses << endl
		<< "Index pool hits: " << t.m_indexPool.m_hits << endl
		<< "Index pool misses: " << t.m_indexPool.m_misses << endl
		<< "Region pool hits: " << t.m_regionPool.m_hits << endl
		<< "Region pool misses: " << t.m_regionPool.m_misses << endl
		<< "Point pool hits: " << t.m_pointPool.m_hits << endl
		<< "Point pool misses: " << t.m_pointPool.m_misses << endl;
	#endif

	return os;
}