public class BasicQuadTree<T> extends BitSetQuadTreeFilter implements Iterable<T>
BitSetQuadTreeFilter.FindIntersectingBitsOp| Modifier and Type | Field and Description |
|---|---|
protected T |
currentItem |
protected String |
currentName |
protected Map<String,List<T>> |
items |
protected ArrayList<double[]> |
levelZeroCells |
protected HashMap<String,T> |
nameMap |
bits, levelSizes, maxLevel, numLevels, path, powersOf4| Constructor and Description |
|---|
BasicQuadTree(int numLevels,
Sector sector,
Map<String,List<T>> itemMap)
Constructs a quadtree of a specified level and spanning a specified region.
|
| Modifier and Type | Method and Description |
|---|---|
void |
add(T item,
double[] itemCoords)
Add an item to the quadtree.
|
void |
add(T item,
double[] itemCoords,
String itemName)
Add a named item to the quadtree.
|
protected void |
addItem(T item,
double[] itemCoords,
String name) |
protected Set<T> |
buildItemSet(List<Integer> bitIds,
Set<T> outItems)
Adds the items identified by a list of bit IDs to the set returned by the get methods.
|
void |
clear()
Removes all items from the tree.
|
boolean |
contains(T item)
Indicates whether an item is contained in the tree.
|
protected boolean |
doOperation(int level,
int position,
double[] cellRegion,
double[] itemCoords)
Performs the add operation of the quadtree.
|
T |
getByName(String name)
Returns a named item.
|
Set<T> |
getItemsAtLocation(Iterable<LatLon> locations,
Set<T> outItems)
Finds and returns the items within tree cells containing specified locations.
|
Set<T> |
getItemsAtLocation(LatLon location,
Set<T> outItems)
Finds and returns the items within a tree cell containing a specified location.
|
Set<T> |
getItemsInRegion(Sector testSector,
Set<T> outItems)
Finds and returns the items intersecting a specified sector.
|
Set<T> |
getItemsInRegions(Iterable<Sector> testSectors,
Set<T> outItems)
Finds and returns the items intersecting a specified collection of sectors.
|
Set<T> |
getItemsInRegions(SectorGeometryList geometryList,
Set<T> outItems)
Finds and returns the items intersecting a specified collection of
SectorGeometry. |
boolean |
hasItems()
Indicates whether the tree contains any items.
|
Iterator<T> |
iterator()
Returns an iterator over the items in the tree.
|
protected void |
makeLevelZeroCells(Sector sector)
Creates the quadtree's level-zero cells.
|
void |
remove(T item)
Removes an item from the tree.
|
void |
removeByName(String name)
Removes an item from the tree by name.
|
computeBitPosition, computeLevelSizes, getNumLevels, intersects, testAndDoprotected T currentItem
protected String currentName
protected ArrayList<double[]> levelZeroCells
public BasicQuadTree(int numLevels,
Sector sector,
Map<String,List<T>> itemMap)
numLevels - the number of levels in the quadtree. The more levels there are the more discriminating searches
will be, but at the cost of some performance.sector - the region the tree spans.itemMap - a Map to hold the items added to the quadtree. May be null, in which case a new map is
created.IllegalArgumentException - if numLevels is less than 1.public void add(T item, double[] itemCoords)
item - the item to add.itemCoords - an array specifying the region or location of the item. If the array's length is 2 it
represents a location in [latitude, longitude]. If its length is 4 it represents a region, with
the same layout as the nodeRegion argument.IllegalArgumentException - if either item or itemCoords is null.public void add(T item, double[] itemCoords, String itemName)
item - the item to add.itemCoords - an array specifying the region or location of the item. If the array's length is 2 it
represents a location in [latitude, longitude]. If its length is 4 it represents a region, with
the same layout as the nodeRegion argument.itemName - the item name. If null, the item is added without a name.IllegalArgumentException - if either item or itemCoords is null.protected Set<T> buildItemSet(List<Integer> bitIds, Set<T> outItems)
bitIds - the bit numbers of the cells containing the items to return.outItems - a Set in which to place the items. If null, a new set is created.outItems is returned.public void clear()
public boolean contains(T item)
item - the item to check. If null, false is returned.protected boolean doOperation(int level,
int position,
double[] cellRegion,
double[] itemCoords)
doOperation in class BitSetQuadTreeFilterlevel - the quadtree level currently being traversed.position - the position of the cell in its parent cell, either 0, 1, 2, or 3. Cell positions starts with 0
at the southwest corner of the parent cell and increment counter-clockwise: cell 1 is SE, cell
2 is NE and cell 3 is NW.cellRegion - an array specifying the coordinates of the cell's region. The first two entries are the minimum
and maximum values on the Y axis (typically latitude). The last two entries are the minimum and
maximum values on the X axis, (typically longitude).itemCoords - an array specifying the region or location of the intersecting item. If the array's length is 2
it represents a location in [latitude, longitude]. If its length is 4 it represents a region,
with the same layout as the nodeRegion argument.public T getByName(String name)
name - the item name. If null, null is returned.public Set<T> getItemsAtLocation(Iterable<LatLon> locations, Set<T> outItems)
locations - the locations of interest.outItems - a Set in which to place the items. If null, a new set is created.outItems argument is returned, or
a new set if that argument is null.IllegalArgumentException - if locations is null.public Set<T> getItemsAtLocation(LatLon location, Set<T> outItems)
location - the location of interest.outItems - a Set in which to place the items. If null, a new set is created.outItems argument is returned, or
a new set if that argument is null.IllegalArgumentException - if location is null.public Set<T> getItemsInRegion(Sector testSector, Set<T> outItems)
testSector - the sector of interest.outItems - a Set in which to place the items. If null, a new set is created.outItems argument is returned, or
a new set if that argument is null.IllegalArgumentException - if testSector is null.public Set<T> getItemsInRegions(Iterable<Sector> testSectors, Set<T> outItems)
testSectors - the sectors of interest.outItems - a Set in which to place the items. If null, a new set is created.outItems argument is returned, or
a new set if that argument is null.IllegalArgumentException - if testSectors is null.public Set<T> getItemsInRegions(SectorGeometryList geometryList, Set<T> outItems)
SectorGeometry.
This method is a convenience for finding the items intersecting the current visible regions.geometryList - the list of sector geometry.outItems - a Set in which to place the items. If null, a new set is created.outItems argument is returned, or
a new set if that argument is null.IllegalArgumentException - if geometryList is null.public boolean hasItems()
public Iterator<T> iterator()
Iterator.remove() operation is not supported.protected void makeLevelZeroCells(Sector sector)
sector - the sector to subdivide to create the cells.public void remove(T item)
item - the item to remove. If null, no item is removed.public void removeByName(String name)
name - the name of the item to remove. If null, no item is removed.