Totally FITH everything

[ipdf/code.git] / src / quadtree.cpp

diff --git a/src/quadtree.cpp b/src/quadtree.cpp
index b0c0eb5..3d5dbee 100644 (file)
--- a/src/quadtree.cpp
+++ b/src/quadtree.cpp
@@ -1,5 +1,6 @@
 #ifndef QUADTREE_REMOVED
 #include "quadtree.h"
+#include "document.h"
 
 namespace IPDF {
 
@@ -47,7 +48,7 @@ bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
        if (src.y + src.h < dst.y) return false;
        if (src.x > dst.x + dst.w) return false;
        if (src.y > dst.y + dst.h) return false;
-       Debug("%s is contained in %s\n", src.Str().c_str(), dst.Str().c_str());
+       //Debug("%s is contained in %s\n", src.Str().c_str(), dst.Str().c_str());
        return true;
 }
 
@@ -59,16 +60,17 @@ bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
        if (src.y < dst.y) return false;
        if (src.x + src.w > dst.x + dst.w) return false;
        if (src.y + src.h > dst.y + dst.h) return false;
-       Debug("%s is contained in %s... \n", src.Str().c_str(), dst.Str().c_str());
+       //Debug("%s is contained in %s... \n", src.Str().c_str(), dst.Str().c_str());
        return true;
 }
 
 
 
-QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
+QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir, Document *addTo) const
 {
        if (!xdir && !ydir) return start;
 
+       QuadTreeIndex newNode;
        // Try moving to the right if that's easy.
        if (xdir > 0)
        {
@@ -76,23 +78,50 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
                {
                case QTC_TOP_LEFT:
                case QTC_BOTTOM_LEFT:
-                       QuadTreeIndex newNode;
+               {
                        if (nodes[start].child_type == QTC_TOP_LEFT)
-                               newNode = node[nodes[start].parent].top_right;
+                       {
+                               newNode = nodes[nodes[start].parent].top_right;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
+                               }
+                       }
                        else
-                               newNode = node[nodes[start].parent].bottom_right;
-                               
-                       return GetNeighbour(newNode, xdir - 1, ydir);
+                       {
+                               newNode = nodes[nodes[start].parent].bottom_right;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
+                               }
+                       }       
+                       return GetNeighbour(newNode, xdir - 1, ydir, addTo);
+               }
                case QTC_TOP_RIGHT:
                case QTC_BOTTOM_RIGHT:
-                       QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0);
+               {
+                       QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0, addTo);
                        if (right_parent == -1) return -1;
-                       QuadTreeIndex newNode;
                        if (nodes[start].child_type == QTC_TOP_RIGHT)
-                               newNode = node[right_parent].top_left;
+                       {
+                               newNode = nodes[right_parent].top_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(right_parent, QTC_TOP_LEFT);
+                               }
+                       }
                        else
-                               newNode = node[right_parent].bottom_left;
-                       return GetNeighbour(newNode, xdir - 1, ydir);
+                       {
+                               newNode = nodes[right_parent].bottom_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(right_parent, QTC_BOTTOM_LEFT);
+                               }
+                       }
+                       return GetNeighbour(newNode, xdir - 1, ydir, addTo);
+               }
+               default:
+                       return -1;
 
                }
        }
@@ -104,24 +133,51 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
                {
                case QTC_TOP_RIGHT:
                case QTC_BOTTOM_RIGHT:
-                       QuadTreeIndex newNode;
+               {
                        if (nodes[start].child_type == QTC_TOP_RIGHT)
-                               newNode = node[nodes[start].parent].top_left;
+                       {
+                               newNode = nodes[nodes[start].parent].top_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
+                               }
+                       }
                        else
-                               newNode = node[nodes[start].parent].bottom_left;
+                       {
+                               newNode = nodes[nodes[start].parent].bottom_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
+                               }
+                       }
                                
-                       return GetNeighbour(newNode, xdir + 1, ydir);
+                       return GetNeighbour(newNode, xdir + 1, ydir, addTo);
+               }
                case QTC_TOP_LEFT:
                case QTC_BOTTOM_LEFT:
-                       QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0);
+               {
+                       QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0, addTo);
                        if (left_parent == -1) return -1;
-                       QuadTreeIndex newNode;
                        if (nodes[start].child_type == QTC_TOP_LEFT)
-                               newNode = node[left_parent].top_right;
+                       {
+                               newNode = nodes[left_parent].top_right;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(left_parent, QTC_TOP_RIGHT);
+                               }
+                       }
                        else
-                               newNode = node[left_parent].bottom_right;
-                       return GetNeighbour(newNode, xdir + 1, ydir);
-
+                       {
+                               newNode = nodes[left_parent].bottom_right;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(left_parent, QTC_BOTTOM_RIGHT);
+                               }
+                       }
+                       return GetNeighbour(newNode, xdir + 1, ydir, addTo);
+               }
+               default:
+                       return -1;
                }
        }
        
@@ -132,24 +188,50 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
                {
                case QTC_TOP_LEFT:
                case QTC_TOP_RIGHT:
-                       QuadTreeIndex newNode;
+               {
                        if (nodes[start].child_type == QTC_TOP_LEFT)
-                               newNode = node[nodes[start].parent].bottom_left;
+                       {
+                               newNode = nodes[nodes[start].parent].bottom_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
+                               }
+                       }
                        else
-                               newNode = node[nodes[start].parent].bottom_right;
-                               
-                       return GetNeighbour(newNode, xdir, ydir - 1);
+                       {
+                               newNode = nodes[nodes[start].parent].bottom_right;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
+                               }
+                       }       
+                       return GetNeighbour(newNode, xdir, ydir - 1, addTo);
+               }
                case QTC_BOTTOM_LEFT:
                case QTC_BOTTOM_RIGHT:
-                       QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1);
+               {
+                       QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1, addTo);
                        if (bottom_parent == -1) return -1;
-                       QuadTreeIndex newNode;
                        if (nodes[start].child_type == QTC_BOTTOM_LEFT)
-                               newNode = node[bottom__parent].top_left;
+                       {
+                               newNode = nodes[bottom_parent].top_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_LEFT);
+                               }
+                       }
                        else
-                               newNode = node[bottom_parent].top_right;
-                       return GetNeighbour(newNode, xdir, ydir - 1);
-
+                       {
+                               newNode = nodes[bottom_parent].top_right;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_RIGHT);
+                               }
+                       }
+                       return GetNeighbour(newNode, xdir, ydir - 1, addTo);
+               }
+               default:
+                       return -1;
                }
        }
 
@@ -160,24 +242,50 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
                {
                case QTC_BOTTOM_LEFT:
                case QTC_BOTTOM_RIGHT:
-                       QuadTreeIndex newNode;
+               {
                        if (nodes[start].child_type == QTC_BOTTOM_LEFT)
-                               newNode = node[nodes[start].parent].top_left;
+                       {
+                               newNode = nodes[nodes[start].parent].top_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
+                               }
+                       }
                        else
-                               newNode = node[nodes[start].parent].top_right;
-                               
-                       return GetNeighbour(newNode, xdir, ydir + 1);
+                       {
+                               newNode = nodes[nodes[start].parent].top_right;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
+                               }
+                       }       
+                       return GetNeighbour(newNode, xdir, ydir + 1, addTo);
+               }
                case QTC_TOP_LEFT:
-               case QTC_BOTTOM_LEFT:
-                       QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1);
+               case QTC_TOP_RIGHT:
+               {
+                       QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1, addTo);
                        if (top_parent == -1) return -1;
-                       QuadTreeIndex newNode;
                        if (nodes[start].child_type == QTC_TOP_LEFT)
-                               newNode = node[top_parent].bottom_left;
+                       {
+                               newNode = nodes[top_parent].bottom_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_LEFT);
+                               }
+                       }
                        else
-                               newNode = node[top_parent].bottom_right;
-                       return GetNeighbour(newNode, xdir, ydir + 1);
-
+                       {
+                               newNode = nodes[top_parent].bottom_right;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_RIGHT);
+                               }
+                       }
+                       return GetNeighbour(newNode, xdir, ydir + 1, addTo);
+               }
+               default:
+                       return -1;
                }
        }
        return -1;