AbstractSTRtree.h
/**********************************************************************
*
* GEOS - Geometry Engine Open Source
* http://geos.osgeo.org
*
* Copyright (C) 2006 Refractions Research 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.
*
**********************************************************************/
#pragma once
#include <geos/export.h>
#include <geos/index/strtree/AbstractNode.h> // for inlines
#include <vector>
#include <list>
#include <memory> // for unique_ptr
#include <cassert> // for inlines
#include <algorithm>
// Forward declarations
namespace geos {
namespace index {
class ItemVisitor;
namespace strtree {
class Boundable;
class AbstractNode;
}
}
}
namespace geos {
namespace index { // geos::index
namespace strtree { // geos::index::strtree
typedef std::vector<Boundable*> BoundableList;
class ItemsList;
class ItemsListItem {
public:
enum type {
item_is_geometry,
item_is_list
};
ItemsListItem(void* item_)
: t(item_is_geometry)
{
item.g = item_;
}
ItemsListItem(ItemsList* item_)
: t(item_is_list)
{
item.l = item_;
}
type
get_type() const
{
return t;
}
void*
get_geometry() const
{
assert(t == item_is_geometry);
return item.g;
}
ItemsList*
get_itemslist() const
{
assert(t == item_is_list);
return item.l;
}
type t;
union {
void* g;
ItemsList* l;
} item;
};
class ItemsList : public std::vector<ItemsListItem> {
private:
typedef std::vector<ItemsListItem> base_type;
static void
delete_item(ItemsListItem& item)
{
if(ItemsListItem::item_is_list == item.t) {
delete item.item.l;
}
}
public:
~ItemsList()
{
std::for_each(begin(), end(), &ItemsList::delete_item);
}
// lists of items need to be deleted in the end
void
push_back(void* item)
{
this->base_type::push_back(ItemsListItem(item));
}
// lists of items need to be deleted in the end
void
push_back_owned(ItemsList* itemList)
{
this->base_type::push_back(ItemsListItem(itemList));
}
};
class GEOS_DLL AbstractSTRtree {
private:
bool built;
BoundableList* itemBoundables;
virtual AbstractNode* createHigherLevels(
BoundableList* boundablesOfALevel,
int level);
std::unique_ptr<BoundableList> sortBoundablesY(const BoundableList* input);
bool remove(const void* searchBounds, AbstractNode& node, void* item);
bool removeItem(AbstractNode& node, void* item);
ItemsList* itemsTree(AbstractNode* node);
AbstractSTRtree(const AbstractSTRtree&) = delete;
AbstractSTRtree& operator=(const AbstractSTRtree&) = delete;
protected:
class GEOS_DLL IntersectsOp {
public:
virtual bool intersects(const void* aBounds,
const void* bBounds) = 0;
virtual
~IntersectsOp() {}
};
AbstractNode* root;
std::vector <AbstractNode*>* nodes;
// Ownership to caller (TODO: return by unique_ptr)
virtual AbstractNode* createNode(int level) = 0;
virtual std::unique_ptr<BoundableList> createParentBoundables(
BoundableList* childBoundables, int newLevel);
virtual AbstractNode*
lastNode(BoundableList* nodeList)
{
assert(!nodeList->empty());
// Cast from Boundable to AbstractNode
return static_cast<AbstractNode*>(nodeList->back());
}
virtual AbstractNode*
getRoot()
{
assert(built);
return root;
}
virtual void insert(const void* bounds, void* item);
void query(const void* searchBounds, std::vector<void*>& foundItems);
void query(const void* searchBounds, ItemVisitor& visitor);
void query(const void* searchBounds, const AbstractNode& node, ItemVisitor& visitor);
bool remove(const void* itemEnv, void* item);
std::unique_ptr<BoundableList> boundablesAtLevel(int level);
// @@ should be size_t, probably
std::size_t nodeCapacity;
virtual IntersectsOp* getIntersectsOp() = 0;
public:
AbstractSTRtree(std::size_t newNodeCapacity)
:
built(false),
itemBoundables(new BoundableList()),
nodes(new std::vector<AbstractNode *>()),
nodeCapacity(newNodeCapacity)
{
assert(newNodeCapacity > 1);
}
virtual ~AbstractSTRtree();
virtual void build();
virtual std::size_t
getNodeCapacity()
{
return nodeCapacity;
}
virtual void query(const void* searchBounds, const AbstractNode* node, std::vector<void*>* matches);
void iterate(ItemVisitor& visitor);
virtual void boundablesAtLevel(int level, AbstractNode* top,
BoundableList* boundables);
ItemsList* itemsTree();
};
} // namespace geos::index::strtree
} // namespace geos::index
} // namespace geos
geos::index::ItemVisitor
A visitor for items in an index.
Definition ItemVisitor.h:28
geos::index::strtree::AbstractNode
A node of the STR tree.
Definition AbstractNode.h:43
geos::index::strtree::AbstractSTRtree::IntersectsOp
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have diff...
Definition AbstractSTRtree.h:175
geos::index::strtree::AbstractSTRtree::IntersectsOp::intersects
virtual bool intersects(const void *aBounds, const void *bBounds)=0
geos::index::strtree::AbstractSTRtree
Base class for STRtree and SIRtree.
Definition AbstractSTRtree.h:138
geos::index::strtree::AbstractSTRtree::iterate
void iterate(ItemVisitor &visitor)
geos::index::strtree::AbstractSTRtree::insert
virtual void insert(const void *bounds, void *item)
Also builds the tree, if necessary.
geos::index::strtree::AbstractSTRtree::query
void query(const void *searchBounds, ItemVisitor &visitor)
Also builds the tree, if necessary.
geos::index::strtree::AbstractSTRtree::AbstractSTRtree
AbstractSTRtree(std::size_t newNodeCapacity)
Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have.
Definition AbstractSTRtree.h:255
geos::index::strtree::AbstractSTRtree::remove
bool remove(const void *itemEnv, void *item)
Also builds the tree, if necessary.
geos::index::strtree::AbstractSTRtree::query
void query(const void *searchBounds, std::vector< void * > &foundItems)
Also builds the tree, if necessary.
geos::index::strtree::AbstractSTRtree::createParentBoundables
virtual std::unique_ptr< BoundableList > createParentBoundables(BoundableList *childBoundables, int newLevel)
Sorts the childBoundables then divides them into groups of size M, where M is the node capacity.
geos::index::strtree::AbstractSTRtree::getNodeCapacity
virtual std::size_t getNodeCapacity()
Returns the maximum number of child nodes that a node may have.
Definition AbstractSTRtree.h:281
geos::index::strtree::AbstractSTRtree::itemsTree
ItemsList * itemsTree()
Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in thi...
geos::index::strtree::AbstractSTRtree::boundablesAtLevel
virtual void boundablesAtLevel(int level, AbstractNode *top, BoundableList *boundables)
geos::index::strtree::AbstractSTRtree::build
virtual void build()
Creates parent nodes, grandparent nodes, and so forth up to the root node, for the data that has been...
geos::index::strtree::AbstractSTRtree::getIntersectsOp
virtual IntersectsOp * getIntersectsOp()=0
geos::index::strtree::Boundable
A spatial object in an AbstractSTRtree.
Definition Boundable.h:24
geos::index::strtree
Contains 2-D and 1-D versions of the Sort-Tile-Recursive (STR) tree, a query-only R-tree.
Definition AbstractNode.h:31
geos::index::strtree::BoundableList
std::vector< Boundable * > BoundableList
A list of boundables. TODO: use a list.
Definition AbstractSTRtree.h:43
geos::index
Provides classes for various kinds of spatial indexes.
Definition CleanCoverage.h:39
geos
Basic namespace for all GEOS functionalities.
Definition geos.h:38