Package org.h2.mvstore.rtree

Class MVRTreeMap<V>

java.lang.Object

java.util.AbstractMap<K,V>

org.h2.mvstore.MVMap<Spatial,V>

org.h2.mvstore.rtree.MVRTreeMap<V>

Type Parameters:

V - the value class

All Implemented Interfaces:

java.util.concurrent.ConcurrentMap<Spatial,V>, java.util.Map<Spatial,V>

public final class MVRTreeMap<V>
extends MVMap<Spatial,V>

An r-tree implementation. It supports both the linear and the quadratic split algorithm.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	MVRTreeMap.Builder<V>	A builder for this class.
private static class	MVRTreeMap.ContainsRTreeCursor<V>
private static class	MVRTreeMap.IntersectsRTreeCursor<V>
static class	MVRTreeMap.RTreeCursor<V>	A cursor to iterate over a subset of the keys.

Nested classes/interfaces inherited from class org.h2.mvstore.MVMap

MVMap.BasicBuilder<M extends MVMap<K,V>,K,V>, MVMap.Decision, MVMap.DecisionMaker<V>, MVMap.MapBuilder<M extends MVMap<K,V>,K,V>

Nested classes/interfaces inherited from class java.util.AbstractMap

java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,V extends java.lang.Object>

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K extends java.lang.Object,V extends java.lang.Object>

Field Summary

Fields

Modifier and Type	Field	Description
private SpatialDataType	keyType	The spatial key type.
private boolean	quadraticSplit

Fields inherited from class org.h2.mvstore.MVMap

store

Constructor Summary

Constructors

Modifier	Constructor	Description
	MVRTreeMap(java.util.Map<java.lang.String,java.lang.Object> config, SpatialDataType keyType, DataType<V> valueType)
private	MVRTreeMap(MVRTreeMap<V> source)

Method Summary

Modifier and Type	Method	Description
void	add(Spatial key, V value)	Add a given key-value pair.
void	addNodeKeys(java.util.ArrayList<Spatial> list, Page<Spatial,V> p)	Add all node keys (including internal bounds) to the given list.
MVRTreeMap<V>	cloneIt()	Clone the current map.
private boolean	contains(Page<Spatial,V> p, int index, java.lang.Object key)
MVRTreeMap.RTreeCursor<V>	findContainedKeys(Spatial x)	Iterate over all keys that are fully contained within the given rectangle.
MVRTreeMap.RTreeCursor<V>	findIntersectingKeys(Spatial x)	Iterate over all keys that have an intersection with the given rectangle.
V	get(Page<Spatial,V> p, Spatial key)	Get the object for the given key.
private Spatial	getBounds(Page<Spatial,V> x)
protected int	getChildPageCount(Page<Spatial,V> p)	Get the child page count for this page.
java.lang.String	getType()	Get the map type.
boolean	isQuadraticSplit()
private static <V> void	move(Page<Spatial,V> source, Page<Spatial,V> target, int sourceIndex)
private Page<Spatial,V>	newPage(boolean leaf)
private V	operate(Page<Spatial,V> p, Spatial key, V value, MVMap.DecisionMaker<? super V> decisionMaker, java.util.Collection<Page<Spatial,V>> removedPages)
V	operate(Spatial key, V value, MVMap.DecisionMaker<? super V> decisionMaker)	Add, replace or remove a key-value pair.
V	put(Spatial key, V value)	Add or replace a key-value pair.
V	remove(java.lang.Object key)	Remove a key-value pair, if the key exists.
void	setQuadraticSplit(boolean quadraticSplit)
private Page<Spatial,V>	split(Page<Spatial,V> p)
private Page<Spatial,V>	splitLinear(Page<Spatial,V> p)
private Page<Spatial,V>	splitQuadratic(Page<Spatial,V> p)

Methods inherited from class org.h2.mvstore.MVMap

append, asString, beforeWrite, ceilingKey, clear, containsKey, createEmptyLeaf, createEmptyNode, cursor, cursor, cursor, entrySet, equals, firstKey, floorKey, flushAndGetRoot, get, getId, getKey, getKeyIndex, getKeyType, getName, getRoot, getRootPage, getStore, getValueType, getVersion, hashCode, higherKey, higherKey, isClosed, isEmpty, isPersistent, isReadOnly, isVolatile, keyIterator, keyIteratorReverse, keyList, keySet, lastKey, lowerKey, lowerKey, openVersion, putIfAbsent, remove, replace, replace, setVolatile, size, sizeAsLong, toString, trimLast, tryLock, unlockRoot, updateRoot

Methods inherited from class java.util.AbstractMap

clone, containsValue, putAll, values

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.concurrent.ConcurrentMap

compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, replaceAll

Methods inherited from interface java.util.Map

containsValue, putAll, values

Field Detail

keyType

private final SpatialDataType keyType

The spatial key type.

quadraticSplit

private boolean quadraticSplit

Constructor Detail

MVRTreeMap

public MVRTreeMap(java.util.Map<java.lang.String,java.lang.Object> config,
                  SpatialDataType keyType,
                  DataType<V> valueType)

MVRTreeMap

private MVRTreeMap(MVRTreeMap<V> source)

Method Detail

cloneIt

public MVRTreeMap<V> cloneIt()

Description copied from class: MVMap

Clone the current map.

Overrides:

cloneIt in class MVMap<Spatial,V>

Returns:

clone of this.

findIntersectingKeys

public MVRTreeMap.RTreeCursor<V> findIntersectingKeys(Spatial x)

Iterate over all keys that have an intersection with the given rectangle.

Parameters:

x - the rectangle

Returns:

the iterator

findContainedKeys

public MVRTreeMap.RTreeCursor<V> findContainedKeys(Spatial x)

Iterate over all keys that are fully contained within the given rectangle.

Parameters:

x - the rectangle

Returns:

the iterator

contains

private boolean contains(Page<Spatial,V> p,
                         int index,
                         java.lang.Object key)

get

public V get(Page<Spatial,V> p,
             Spatial key)

Get the object for the given key. An exact match is required.

Overrides:

get in class MVMap<Spatial,V>

Parameters:

p - the page

key - the key

Returns:

the value, or null if not found

remove

public V remove(java.lang.Object key)

Remove a key-value pair, if the key exists.

Specified by:

remove in interface java.util.Map<Spatial,V>

Overrides:

remove in class MVMap<Spatial,V>

Parameters:

key - the key (may not be null)

Returns:

the old value if the key existed, or null otherwise

operate

public V operate(Spatial key,
                 V value,
                 MVMap.DecisionMaker<? super V> decisionMaker)

Description copied from class: MVMap

Add, replace or remove a key-value pair.

Overrides:

operate in class MVMap<Spatial,V>

Parameters:

key - the key (may not be null)

value - new value, it may be null when removal is intended

decisionMaker - command object to make choices during transaction.

Returns:

previous value, if mapping for that key existed, or null otherwise

operate

private V operate(Page<Spatial,V> p,
                  Spatial key,
                  V value,
                  MVMap.DecisionMaker<? super V> decisionMaker,
                  java.util.Collection<Page<Spatial,V>> removedPages)

getBounds

private Spatial getBounds(Page<Spatial,V> x)

put

public V put(Spatial key,
             V value)

Description copied from class: MVMap

Add or replace a key-value pair.

Specified by:

put in interface java.util.Map<Spatial,V>

Overrides:

put in class MVMap<Spatial,V>

Parameters:

key - the key (may not be null)

value - the value (may not be null)

Returns:

the old value if the key existed, or null otherwise

add

public void add(Spatial key,
                V value)

Add a given key-value pair. The key should not exist (if it exists, the result is undefined).

Parameters:

key - the key

value - the value

split

private Page<Spatial,V> split(Page<Spatial,V> p)

splitLinear

private Page<Spatial,V> splitLinear(Page<Spatial,V> p)

splitQuadratic

private Page<Spatial,V> splitQuadratic(Page<Spatial,V> p)

newPage

private Page<Spatial,V> newPage(boolean leaf)

move

private static <V> void move(Page<Spatial,V> source,
                             Page<Spatial,V> target,
                             int sourceIndex)

addNodeKeys

public void addNodeKeys(java.util.ArrayList<Spatial> list,
                        Page<Spatial,V> p)

Add all node keys (including internal bounds) to the given list. This is mainly used to visualize the internal splits.

Parameters:

list - the list

p - the root page

isQuadraticSplit

public boolean isQuadraticSplit()

setQuadraticSplit

public void setQuadraticSplit(boolean quadraticSplit)

getChildPageCount

protected int getChildPageCount(Page<Spatial,V> p)

Description copied from class: MVMap

Get the child page count for this page. This is to allow another map implementation to override the default, in case the last child is not to be used.

Overrides:

getChildPageCount in class MVMap<Spatial,V>

Parameters:

p - the page

Returns:

the number of direct children

getType

public java.lang.String getType()

Description copied from class: MVMap

Get the map type. When opening an existing map, the map type must match.

Overrides:

getType in class MVMap<Spatial,V>

Returns:

the map type