Class MVRTreeMap<V>

Type Parameters:
V - the value class
All Implemented Interfaces:
ConcurrentMap<Spatial,V>, 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.
  • Field Details

    • keyType

      private final SpatialDataType keyType
      The spatial key type.
    • quadraticSplit

      private boolean quadraticSplit
  • Constructor Details

  • Method Details

    • 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, 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(Object key)
      Remove a key-value pair, if the key exists.
      Specified by:
      remove in interface 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, 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 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(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 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