org.geotools.caching.grid.spatialindex
Class GridSpatialIndex

java.lang.Object
  extended by org.geotools.caching.spatialindex.AbstractSpatialIndex
      extended by org.geotools.caching.grid.spatialindex.GridSpatialIndex
All Implemented Interfaces:
EvictableTree, SpatialIndex

public class GridSpatialIndex
extends AbstractSpatialIndex
implements EvictableTree

A grid implementation of SpatialIndex. A grid is a regular division of space, and is implemented as a very simple tree. It has two levels, a top level consisting of one root node, and a bottom level of nodes of the same size forming a grid. Data is either inserted at the top level or at the bottom level, and may be inserted more than once, if data intersects more than one node. If data's shape is too big, it is inserted at the top level. For the grid to be efficient, data should evenly distributed in size and in space, and grid size should twice the mean size of data's shape.

Author:
Christophe Rousson, SoC 2007, CRG-ULAVAL

Field Summary
static java.lang.String GRID_CAPACITY_PROPERTY
           
static java.lang.String GRID_SIZE_PROPERTY
           
protected  int gridsize
           
protected  int MAX_INSERTION
           
protected  Region mbr
           
static java.lang.String ROOT_MBR_MAXX_PROPERTY
           
static java.lang.String ROOT_MBR_MAXY_PROPERTY
           
static java.lang.String ROOT_MBR_MINX_PROPERTY
           
static java.lang.String ROOT_MBR_MINY_PROPERTY
           
 
Fields inherited from class org.geotools.caching.spatialindex.AbstractSpatialIndex
ContainmentQuery, dimension, infiniteRegion, IntersectionQuery, root, rootNode, stats, store
 
Fields inherited from interface org.geotools.caching.spatialindex.SpatialIndex
EPSILON, INDEX_TYPE_PROPERTY
 
Constructor Summary
protected GridSpatialIndex()
           
  GridSpatialIndex(Region mbr, int gridsize, Storage store, int capacity)
          Constructor.
 
Method Summary
 void clear()
          Empty the index.
static SpatialIndex createInstance(java.util.Properties pset)
           
 void dispose()
           
 void evict(NodeIdentifier node)
          must deal with synchronization outside this method.
 java.util.List<NodeIdentifier>[] findMissingTiles(Region search)
          Searches the index for missing tiles Returns both the "valid" tiles and the "invalid" tiles
 NodeIdentifier findUniqueInstance(NodeIdentifier id)
           
 boolean getDoRecordAccess()
           
 EvictionPolicy getEvictionPolicy()
           
 int getEvictions()
           
 java.util.Properties getIndexProperties()
           
 GridRootNode getRootNode()
           
 GridSpatialIndexStatistics getStatistics()
           
 void initializeFromStorage(Storage storage)
          Initializes the spatial index from a storage instance.
protected  void insertData(NodeIdentifier n, java.lang.Object data, Shape shape)
          Insert new data into target node.
 void insertData(java.lang.Object data, Shape shape)
          This function assumes that you have a lock on the necessary nodes.
protected  void insertDataOutOfBounds(java.lang.Object data, Shape shape)
          Insert new data with shape not contained in the current index.
 boolean isIndexValid()
          Implementations may always return true.
protected  void rangeQuery(int type, Shape query, Visitor v)
          Common algorithm used by both intersection and containment queries.
 Node readNode(NodeIdentifier id)
           
 void setDoRecordAccess(boolean b)
           
protected  void visitData(Node n, Visitor v, Shape query, int type)
          Visit data associated with a node using given visitor.
 void writeNode(Node node)
          Assumes you have a write lock on the node you are writing.
 
Methods inherited from class org.geotools.caching.spatialindex.AbstractSpatialIndex
containmentQuery, deleteNode, flush, getStorage, intersectionQuery, nearestNeighborQuery, nearestNeighborQuery, pointLocationQuery
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

GRID_SIZE_PROPERTY

public static final java.lang.String GRID_SIZE_PROPERTY
See Also:
Constant Field Values

GRID_CAPACITY_PROPERTY

public static final java.lang.String GRID_CAPACITY_PROPERTY
See Also:
Constant Field Values

ROOT_MBR_MINX_PROPERTY

public static final java.lang.String ROOT_MBR_MINX_PROPERTY
See Also:
Constant Field Values

ROOT_MBR_MINY_PROPERTY

public static final java.lang.String ROOT_MBR_MINY_PROPERTY
See Also:
Constant Field Values

ROOT_MBR_MAXX_PROPERTY

public static final java.lang.String ROOT_MBR_MAXX_PROPERTY
See Also:
Constant Field Values

ROOT_MBR_MAXY_PROPERTY

public static final java.lang.String ROOT_MBR_MAXY_PROPERTY
See Also:
Constant Field Values

MAX_INSERTION

protected int MAX_INSERTION

gridsize

protected int gridsize

mbr

protected Region mbr
Constructor Detail

GridSpatialIndex

public GridSpatialIndex(Region mbr,
                        int gridsize,
                        Storage store,
                        int capacity)
Constructor. Creates a new Grid covering space given by mbr and with at least capacity nodes.

Parameters:
mbr -
capacity - - the number of tiles in the index
store - - the backend index storage

GridSpatialIndex

protected GridSpatialIndex()
Method Detail

createInstance

public static SpatialIndex createInstance(java.util.Properties pset)

getRootNode

public GridRootNode getRootNode()
Returns:
the root node of the grid

dispose

public void dispose()

visitData

protected void visitData(Node n,
                         Visitor v,
                         Shape query,
                         int type)
Description copied from class: AbstractSpatialIndex
Visit data associated with a node using given visitor. At this stage, we only know that node's MBR intersects query. This method is reponsible for iterating over node's data, if any, and for checking if data is actually part of the query result. Then it uses the visitor's visit() method on the selected data.

Specified by:
visitData in class AbstractSpatialIndex
type - of query, either containement or intersection (@see AbstractSpatialIndex)

clear

public void clear()
           throws java.lang.IllegalStateException
Description copied from interface: SpatialIndex
Empty the index.

Specified by:
clear in interface SpatialIndex
Throws:
java.lang.IllegalStateException

getIndexProperties

public java.util.Properties getIndexProperties()
Specified by:
getIndexProperties in interface SpatialIndex
Returns:

insertData

protected void insertData(NodeIdentifier n,
                          java.lang.Object data,
                          Shape shape)
Description copied from class: AbstractSpatialIndex
Insert new data into target node. Node may delegate to child nodes, if required. Implementation note : it is assumed arguments verify : node.getShape().contains(shape) So this must be checked before calling this method.

Specified by:
insertData in class AbstractSpatialIndex
shape - of data

insertDataOutOfBounds

protected void insertDataOutOfBounds(java.lang.Object data,
                                     Shape shape)
Description copied from class: AbstractSpatialIndex
Insert new data with shape not contained in the current index. Some indexes may require to recreate the root or the index, depending on the type of index ...

Specified by:
insertDataOutOfBounds in class AbstractSpatialIndex

isIndexValid

public boolean isIndexValid()
Description copied from interface: SpatialIndex
Implementations may always return true.

Specified by:
isIndexValid in interface SpatialIndex
Returns:
true if index is valid. TODO: define what is a valid index.

findUniqueInstance

public NodeIdentifier findUniqueInstance(NodeIdentifier id)

initializeFromStorage

public void initializeFromStorage(Storage storage)
Description copied from interface: SpatialIndex
Initializes the spatial index from a storage instance.

This allows caches to be saved to storage and reused.

Specified by:
initializeFromStorage in interface SpatialIndex

rangeQuery

protected void rangeQuery(int type,
                          Shape query,
                          Visitor v)
Common algorithm used by both intersection and containment queries.

Overrides:
rangeQuery in class AbstractSpatialIndex
Parameters:
type -
query -
v -

findMissingTiles

public java.util.List<NodeIdentifier>[] findMissingTiles(Region search)
Searches the index for missing tiles Returns both the "valid" tiles and the "invalid" tiles

Parameters:
search - must be within the mbr of the index
Returns:

getEvictions

public int getEvictions()

getEvictionPolicy

public EvictionPolicy getEvictionPolicy()

evict

public void evict(NodeIdentifier node)
must deal with synchronization outside this method. This will blindly evict the node.

Specified by:
evict in interface EvictableTree

readNode

public Node readNode(NodeIdentifier id)
Overrides:
readNode in class AbstractSpatialIndex

getStatistics

public GridSpatialIndexStatistics getStatistics()
Specified by:
getStatistics in interface SpatialIndex
Overrides:
getStatistics in class AbstractSpatialIndex
Returns:
statistics about the index.

writeNode

public void writeNode(Node node)
Assumes you have a write lock on the node you are writing.

Overrides:
writeNode in class AbstractSpatialIndex

getDoRecordAccess

public boolean getDoRecordAccess()

setDoRecordAccess

public void setDoRecordAccess(boolean b)

insertData

public void insertData(java.lang.Object data,
                       Shape shape)
This function assumes that you have a lock on the necessary nodes.

Specified by:
insertData in interface SpatialIndex
Overrides:
insertData in class AbstractSpatialIndex
Parameters:
data - to insert
shape - associated with data


Copyright © 1996-2010 Geotools. All Rights Reserved.