package com.planet_ink.coffee_mud.core.collections;
import java.lang.ref.WeakReference;
import java.util.*;
import java.util.Map.Entry;
import com.planet_ink.coffee_mud.core.interfaces.BoundedObject;
import com.planet_ink.coffee_mud.core.interfaces.BoundedObject.BoundedCube;
/**
* 2D R-Tree implementation for Android.
* Uses algorithms from: http://www.sai.msu.su/~megera/postgres/gist/papers/Rstar3.pdf
* @author Colonel32
* @author cnvandev
*
* Adapted to 3d by:
* @author Bo Zimmerman
*
* Found at:
* https://github.com/pruby/xppylons/blob/master/src/com/untamedears/xppylons/rtree/AABB.java
* (No license found)
*/
public class RTree<T extends BoundedObject>
{
private RTreeNode root;
private int maxSize;
private int minSize;
private SLinkedHashtable<T,List<WeakReference<TrackingVector<T>>>> trackMap;
private QuadraticNodeSplitter splitter;
public class RTreeNode implements BoundedObject
{
RTreeNode parent;
BoundedCube box;
Vector<RTreeNode> children;
TrackingVector<T> data;
final RTreeNode me=this;
public RTreeNode()
{
}
public RTreeNode(final boolean isLeaf)
{
if (isLeaf)
{
data = new TrackingVector<T>(trackMap,maxSize+1,new TrackingVector.TrackBack<T>()
{
@Override
public void removed(final T o)
{
me.computeMBR(true);
}
});
}
else
{
children = new Vector<RTreeNode>(maxSize+1);
}
}
public boolean isLeaf()
{
return data != null;
}
public boolean isRoot()
{
return parent == null;
}
public void addTo(final RTreeNode parent)
{
assert(parent.children != null);
parent.children.add(this);
this.parent = parent;
computeMBR();
splitter.split(parent);
}
public void computeMBR()
{
computeMBR(true);
}
public void computeMBR(final boolean doParents)
{
if (box == null)
box = new BoundedCube();
if (!isLeaf())
{
if (children.isEmpty())
return;
box.set(children.get(0).box);
for (int i = 1; i < children.size(); i++)
{
box.union(children.get(i).box);
}
}
else
{
if (data.isEmpty())
return;
box.set(data.get(0).getBounds());
for (int i = 1; i < data.size(); i++)
{
box.union(data.get(i).getBounds());
}
}
if (doParents && parent != null)
parent.computeMBR();
}
public void remove()
{
if (parent == null)
{
assert(root == this);
root = null;
return;
}
parent.children.remove(this);
if (parent.children.isEmpty())
{
parent.remove();
}
else
{
parent.computeMBR();
}
}
public Vector<? extends BoundedObject> getSubItems()
{
return isLeaf() ? data : children;
}
@Override
public BoundedCube getBounds()
{
return box;
}
public boolean contains(final long px, final long py, final int pz)
{
return box.contains(px, py, pz);
}
public int size()
{
return isLeaf() ? data.size() : children.size();
}
public int depth()
{
RTreeNode n = this;
int d = 0;
while(n != null)
{
n = n.parent;
d++;
}
return d;
}
@Override
public String toString()
{
return "Depth: "+depth()+", size: "+size();
}
}
private class QuadraticNodeSplitter {
public void split(final RTreeNode n)
{
if (n.size() <= maxSize) return;
final boolean isleaf = n.isLeaf();
// Choose seeds. Would write a function for this, but it requires returning 2 objects
BoundedObject seed1 = null, seed2 = null;
Vector<? extends BoundedObject> list;
if (isleaf)
list = n.data;
else
list = n.children;
long maxD = Long.MIN_VALUE;
final BoundedCube box = new BoundedCube();
for (int i = 0; i < list.size(); i++)
{
for (int j=0; j<list.size(); j++)
{
if (i == j) continue;
final BoundedObject n1 = list.get(i), n2 = list.get(j);
box.set(n1.getBounds());
box.union(n2.getBounds());
final long d = area(box) - area(n1.getBounds()) - area(n2.getBounds());
if (d > maxD)
{
maxD = d;
seed1 = n1;
seed2 = n2;
}
}
}
if((seed1==null)||(seed2==null))
{
assert(seed1 != null && seed2 != null);
return;
}
// Distribute
final RTreeNode group1 = new RTreeNode(isleaf);
group1.box = new BoundedCube(seed1.getBounds());
final RTreeNode group2 = new RTreeNode(isleaf);
group2.box = new BoundedCube(seed2.getBounds());
if (isleaf)
distributeLeaves(n, group1, group2);
else
distributeBranches(n, group1, group2);
RTreeNode parent = n.parent;
if (parent == null)
{
parent = new RTreeNode(false);
root = parent;
}
else
{
parent.children.remove(n);
}
group1.parent = parent;
parent.children.add(group1);
group1.computeMBR();
split(parent);
group2.parent = parent;
parent.children.add(group2);
group2.computeMBR();
split(parent);
}
private void distributeBranches(final RTreeNode n, final RTreeNode g1, final RTreeNode g2)
{
assert(!(n.isLeaf() || g1.isLeaf() || g2.isLeaf()));
while(!n.children.isEmpty() && g1.children.size() < maxSize - minSize + 1 && g2.children.size() < maxSize - minSize + 1)
{
// Pick next
int difmax = Integer.MIN_VALUE;
int nmax_index = -1;
for (int i = 0; i < n.children.size(); i++)
{
final RTreeNode node = n.children.get(i);
final int expansion1 = expansionNeeded(node.box, g1.box);
final int expansion2 = expansionNeeded(node.box, g2.box);
final int dif = Math.abs(expansion1 - expansion2);
if (dif > difmax)
{
difmax = dif;
nmax_index = i;
}
}
assert(nmax_index != -1);
// Distribute Entry
final RTreeNode nmax = n.children.remove(nmax_index);
RTreeNode parent = null;
// ... to the one with the least expansion
final int overlap1 = expansionNeeded(nmax.box, g1.box);
final int overlap2 = expansionNeeded(nmax.box, g2.box);
if (overlap1 > overlap2)
{
parent = g1;
}
else
if (overlap2 > overlap1)
{
parent = g2;
}
else
{
// Or the one with the lowest area
final long area1 = area(g1.box);
final long area2 = area(g2.box);
if (area1 > area2)
parent = g2;
else
if (area2 > area1)
parent = g1;
else
{
// Or the one with the least items
if (g1.children.size() < g2.children.size())
parent = g1;
else
parent = g2;
}
}
assert(parent != null);
parent.children.add(nmax);
nmax.parent = parent;
}
if (!n.children.isEmpty())
{
RTreeNode parent = null;
if (g1.children.size() == maxSize - minSize + 1)
parent = g2;
else
parent = g1;
for (int i = 0; i < n.children.size(); i++)
{
parent.children.add(n.children.get(i));
n.children.get(i).parent = parent;
}
n.children.clear();
}
}
private void distributeLeaves(final RTreeNode n, final RTreeNode g1, final RTreeNode g2)
{
// Same process as above; just different types.
assert(n.isLeaf() && g1.isLeaf() && g2.isLeaf());
while(!n.data.isEmpty() && g1.data.size() < maxSize - minSize + 1 && g2.data.size() < maxSize - minSize + 1)
{
// Pick next
int difmax = Integer.MIN_VALUE;
int nmax_index = -1;
for (int i = 0; i < n.data.size(); i++)
{
final T node = n.data.get(i);
final int d1 = expansionNeeded(node.getBounds(), g1.box);
final int d2 = expansionNeeded(node.getBounds(), g2.box);
final int dif = Math.abs(d1 - d2);
if (dif > difmax)
{
difmax = dif;
nmax_index = i;
}
}
assert(nmax_index != -1);
// Distribute Entry
final T nmax = n.data.remove(nmax_index);
// ... to the one with the least expansion
final int overlap1 = expansionNeeded(nmax.getBounds(), g1.box);
final int overlap2 = expansionNeeded(nmax.getBounds(), g2.box);
if (overlap1 > overlap2)
{
g1.data.add(nmax);
}
else
if (overlap2 > overlap1)
{
g2.data.add(nmax);
}
else
{
final long area1 = area(g1.box);
final long area2 = area(g2.box);
if (area1 > area2)
{
g2.data.add(nmax);
}
else
if (area2 > area1)
{
g1.data.add(nmax);
}
else
{
if (g1.data.size() < g2.data.size())
{
g1.data.add(nmax);
}
else
{
g2.data.add(nmax);
}
}
}
}
if (!n.data.isEmpty())
{
if (g1.data.size() == maxSize - minSize + 1)
{
g2.data.addAll(n.data);
}
else
{
g1.data.addAll(n.data);
}
n.data.clear();
}
}
}
/**
* Default constructor.
*/
public RTree()
{
this(2, 12);
}
/**
* Creates an R-Tree. Sets the splitting algorithm to quadratic splitting.
* @param minChildren Minimum children in a node. {@code 2 <= minChildren <= maxChildren/2}
* @param maxChildren Maximum children in a node. Node splits at this number + 1
*/
public RTree(final int minChildren, final int maxChildren)
{
trackMap = new SLinkedHashtable<T,List<WeakReference<TrackingVector<T>>>>();
if (minChildren < 2 || minChildren > maxChildren/2)
throw new IllegalArgumentException("2 <= minChildren <= maxChildren/2");
splitter = new QuadraticNodeSplitter();
this.minSize = minChildren;
this.maxSize = maxChildren;
root = null;
}
public void clear()
{
splitter = new QuadraticNodeSplitter();
root = null;
}
/**
* Adds items whose AABB intersects the query AABB to results
* @param results A collection to store the query results
*/
public void query(final Collection<T> results)
{
final BoundedCube box = new BoundedCube(Long.MIN_VALUE, Long.MAX_VALUE, Long.MIN_VALUE, Long.MAX_VALUE, Long.MIN_VALUE, Long.MAX_VALUE);
query(results, box, root);
}
public void query(final Collection<T> results, final BoundedCube box)
{
query(results, box, root);
}
private void query(final Collection<T> results, final BoundedCube box, final RTreeNode node)
{
if (node == null) return;
if (node.isLeaf())
{
for (int i = 0; i < node.data.size(); i++)
if (node.data.get(i).getBounds().intersects(box))
results.add(node.data.get(i));
}
else
{
for (int i = 0; i < node.children.size(); i++)
{
if (node.children.get(i).box.intersects(box))
{
query(results, box, node.children.get(i));
}
}
}
}
/**
* Returns one item that intersects the query box, or null if nothing intersects
* the query box.
* @param box the area to look up
* @return the first thing in that area
*/
public T queryOne(final BoundedCube box)
{
return queryOne(box,root);
}
private T queryOne(final BoundedCube box, final RTreeNode node)
{
if (node == null) return null;
if (node.isLeaf())
{
for (int i = 0; i < node.data.size(); i++)
{
if (node.data.get(i).getBounds().intersects(box))
{
return node.data.get(i);
}
}
return null;
}
else
{
for (int i = 0; i < node.children.size(); i++)
{
if (node.children.get(i).box.intersects(box))
{
final T result = queryOne(box,node.children.get(i));
if (result != null) return result;
}
}
return null;
}
}
/**
* Returns items whose Rect contains the specified point.
* @param results A collection to store the query results.
* @param px Point X coordinate
* @param py Point Y coordinate
* @param pz Point Z coordinate
*/
public void query(final Collection<T> results, final long px, final long py, final long pz)
{
query(results, px, py, pz, root);
}
private void query(final Collection<T> results, final long px, final long py, final long pz, final RTreeNode node)
{
if (node == null) return;
if (node.isLeaf())
{
for (int i = 0; i < node.data.size(); i++)
{
if (node.data.get(i).getBounds().contains(px, py, pz))
{
results.add(node.data.get(i));
}
}
}
else
{
for (int i = 0; i < node.children.size(); i++)
{
if (node.children.get(i).box.contains(px, py, pz))
{
query(results, px, py, pz, node.children.get(i));
}
}
}
}
/**
* Returns one item that intersects the query point, or null if no items intersect that point.
* @param px Point X coordinate
* @param py Point Y coordinate
* @param pz Point Z coordinate
* @return the first object in that area
*/
public T queryOne(final long px, final long py, final long pz)
{
return queryOne(px, py, pz, root);
}
private T queryOne(final long px, final long py, final long pz, final RTreeNode node)
{
if (node == null) return null;
if (node.isLeaf())
{
for (int i = 0; i < node.data.size(); i++)
{
if (node.data.get(i).getBounds().contains(px, py, pz))
{
return node.data.get(i);
}
}
return null;
}
else
{
for (int i = 0; i < node.children.size(); i++)
{
if (node.children.get(i).box.contains(px, py, pz))
{
final T result = queryOne(px, py, pz, node.children.get(i));
if (result != null) return result;
}
}
return null;
}
}
/**
* Removes the specified object if it is in the tree.
* @param o the object to remove
* @return true if it was there to remove, false otherwise
*/
public boolean remove(final T o)
{
if(root==null)
return false;
boolean removed=false;
TrackingVector<T> v=null;
synchronized(trackMap)
{
final List<WeakReference<TrackingVector<T>>> nodes = trackMap.get(o);
if(nodes!=null)
{
int i=0;
while((v==null)&&(i<nodes.size()))
{
final WeakReference<TrackingVector<T>> r = nodes.get(i++);
if(r!=null)
v=r.get();
}
}
}
if(v!=null)
{
v.removeAllTrackedEntries(o);
removed=true;
}
return removed;
}
/**
* Inserts object o into the tree. Note that if the value of o.getBounds() changes
* while in the R-tree, the result is undefined.
* @param o the object to insert into the tree
* @throws NullPointerException If o == null
*/
public void insert(final T o)
{
if (o == null) throw new NullPointerException("Cannot store null object");
if (root == null)
root = new RTreeNode(true);
final RTreeNode n = chooseLeaf(o, root);
assert(n.isLeaf());
if(!n.data.contains(o))
{
n.data.add(o);
n.computeMBR();
splitter.split(n);
}
}
/**
* Returns whether the given object is in the tree
* @param o the object to look for
* @return true if it is in there, false otherwise
*/
public boolean contains(final T o)
{
if (o == null)
return false;
if (root == null)
return false;
return trackMap.containsKey(o);
}
public Enumeration<T> objects()
{
return trackMap.keys();
}
public Enumeration<Entry<T, List<WeakReference<TrackingVector<T>>>>> objectEntries()
{
return trackMap.entries();
}
public boolean leafSearch(final T o)
{
if (o == null)
return false;
if (root == null)
return false;
return firstLeafSearch(o, root)!=null;
}
/**
* Counts the number of items in the tree.
* @return the number of items
*/
public int count()
{
if (root == null) return 0;
return count(root);
}
private int count(final RTreeNode n)
{
assert(n != null);
if (n.isLeaf())
{
return n.data.size();
}
else
{
int sum = 0;
for (int i = 0; i < n.children.size(); i++)
sum += count(n.children.get(i));
return sum;
}
}
private RTreeNode chooseLeaf(final T o, final RTreeNode n)
{
assert(n != null);
if (n.isLeaf())
{
return n;
}
else
{
final BoundedCube box = o.getBounds();
int maxOverlap = Integer.MAX_VALUE;
RTreeNode maxnode = null;
for (int i = 0; i < n.children.size(); i++)
{
final int overlap = expansionNeeded(n.children.get(i).box, box);
if ((overlap < maxOverlap) || (overlap == maxOverlap)
&& ((maxnode!=null)&&(area(n.children.get(i).box) < area(maxnode.box))))
{
maxOverlap = overlap;
maxnode = n.children.get(i);
}
}
if (maxnode == null) // Not sure how this could occur
return null;
return chooseLeaf(o, maxnode);
}
}
private RTreeNode firstLeafSearch(final T o, final RTreeNode n)
{
assert(n != null);
if (n.isLeaf())
{
return n.data.contains(o)?n:null;
}
else
{
for (int i = 0; i < n.children.size(); i++)
{
final RTreeNode n2=n.children.get(i);
if(n2.isLeaf() && n2.data.contains(o))
return n2;
final RTreeNode n3=firstLeafSearch(o,n2);
if(n3!=null)
return n3;
}
return null;
}
}
/**
* Returns the amount that other will need to be expanded to fit this.
*/
private static int expansionNeeded(final BoundedCube one, final BoundedCube two)
{
int total = 0;
if(two.lx < one.lx)
total += one.lx - two.lx;
if(two.rx > one.rx)
total += two.rx - one.rx;
if(two.ty < one.ty)
total += one.ty - two.ty;
if(two.by > one.by)
total += two.by - one.by;
if(two.iz < one.iz)
total += one.iz - two.iz;
if(two.oz > one.oz)
total += two.oz - one.oz;
return total;
}
private static long area(final BoundedCube rect)
{
return rect.width() * rect.height() * rect.depth();
}
}
