Index: src/Common/NetTopologySuite/Index/Quadtree/NodeBase.cs
===================================================================
diff -u -r8f6ae890fed8e8eae3a32f9c0498a10f82e0ddf9 -r5fc71a385897af92ccb092f2f969b5709afab85a
--- src/Common/NetTopologySuite/Index/Quadtree/NodeBase.cs (.../NodeBase.cs) (revision 8f6ae890fed8e8eae3a32f9c0498a10f82e0ddf9)
+++ src/Common/NetTopologySuite/Index/Quadtree/NodeBase.cs (.../NodeBase.cs) (revision 5fc71a385897af92ccb092f2f969b5709afab85a)
@@ -7,33 +7,7 @@
/// The base class for nodes in a Quadtree.
///
public abstract class NodeBase
- {
- ///
- /// Returns the index of the subquad that wholly contains the given envelope.
- /// If none does, returns -1.
- ///
- ///
- ///
- public static int GetSubnodeIndex(IEnvelope env, ICoordinate centre)
- {
- int subnodeIndex = -1;
- if (env.MinX >= centre.X)
- {
- if (env.MinY >= centre.Y)
- subnodeIndex = 3;
- if (env.MaxY <= centre.Y)
- subnodeIndex = 1;
- }
- if (env.MaxX <= centre.X)
- {
- if (env.MinY >= centre.Y)
- subnodeIndex = 2;
- if (env.MaxY <= centre.Y)
- subnodeIndex = 0;
- }
- return subnodeIndex;
- }
-
+ {
///
///
///
@@ -50,7 +24,7 @@
///
///
///
- public NodeBase() { }
+ public NodeBase() {}
///
///
@@ -72,107 +46,220 @@
{
// return !items.IsEmpty;
if (items.Count == 0)
+ {
return false;
- return true;
+ }
+ return true;
}
}
///
///
///
- ///
- public void Add(object item)
+ public bool IsPrunable
{
- items.Add(item);
+ get
+ {
+ return !(HasChildren || HasItems);
+ }
}
- ///
- /// Removes a single item from this subtree.
+ ///
+ ///
///
- /// The envelope containing the item.
- /// The item to remove.
- /// true if the item was found and removed.
- public bool Remove(IEnvelope itemEnv, object item)
+ public bool HasChildren
{
- // use envelope to restrict nodes scanned
- if (!IsSearchMatch(itemEnv))
+ get
+ {
+ for (int i = 0; i < 4; i++)
+ {
+ if (subnode[i] != null)
+ {
+ return true;
+ }
+ }
return false;
+ }
+ }
- bool found = false;
- for (int i = 0; i < 4; i++)
+ ///
+ ///
+ ///
+ public bool IsEmpty
+ {
+ get
{
- if (subnode[i] != null)
+ bool isEmpty = true;
+ if (items.Count != 0)
{
- found = subnode[i].Remove(itemEnv, item);
- if (found)
+ isEmpty = false;
+ }
+ for (int i = 0; i < 4; i++)
+ {
+ if (subnode[i] != null)
{
- // trim subtree if empty
- if (subnode[i].IsPrunable)
- subnode[i] = null;
- break;
+ if (!subnode[i].IsEmpty)
+ {
+ isEmpty = false;
+ }
}
}
+ return isEmpty;
}
-
- // if item was found lower down, don't need to search for it here
- if (found)
- return found;
-
- // otherwise, try and remove the item from the list of items in this node
- if(items.Contains(item))
- {
- items.Remove(item);
- found = true;
- }
- return found;
}
///
///
///
- public bool IsPrunable
+ public int Depth
{
get
{
- return !(HasChildren || HasItems);
+ int maxSubDepth = 0;
+ for (int i = 0; i < 4; i++)
+ {
+ if (subnode[i] != null)
+ {
+ int sqd = subnode[i].Depth;
+ if (sqd > maxSubDepth)
+ {
+ maxSubDepth = sqd;
+ }
+ }
+ }
+ return maxSubDepth + 1;
}
}
///
///
///
- public bool HasChildren
+ public int Count
{
get
{
+ int subSize = 0;
for (int i = 0; i < 4; i++)
{
if (subnode[i] != null)
- return true;
+ {
+ subSize += subnode[i].Count;
+ }
}
- return false;
+ return subSize + items.Count;
}
}
///
///
///
- public bool IsEmpty
+ public int NodeCount
{
get
{
- bool isEmpty = true;
- if(items.Count != 0)
- isEmpty = false;
+ int subSize = 0;
for (int i = 0; i < 4; i++)
+ {
if (subnode[i] != null)
- if (!subnode[i].IsEmpty)
- isEmpty = false;
- return isEmpty;
+ {
+ subSize += subnode[i].Count;
+ }
+ }
+ return subSize + 1;
}
}
-
+
+ ///
+ /// Returns the index of the subquad that wholly contains the given envelope.
+ /// If none does, returns -1.
+ ///
+ ///
+ ///
+ public static int GetSubnodeIndex(IEnvelope env, ICoordinate centre)
+ {
+ int subnodeIndex = -1;
+ if (env.MinX >= centre.X)
+ {
+ if (env.MinY >= centre.Y)
+ {
+ subnodeIndex = 3;
+ }
+ if (env.MaxY <= centre.Y)
+ {
+ subnodeIndex = 1;
+ }
+ }
+ if (env.MaxX <= centre.X)
+ {
+ if (env.MinY >= centre.Y)
+ {
+ subnodeIndex = 2;
+ }
+ if (env.MaxY <= centre.Y)
+ {
+ subnodeIndex = 0;
+ }
+ }
+ return subnodeIndex;
+ }
+
///
+ ///
+ ///
+ ///
+ public void Add(object item)
+ {
+ items.Add(item);
+ }
+
+ ///
+ /// Removes a single item from this subtree.
+ ///
+ /// The envelope containing the item.
+ /// The item to remove.
+ /// true if the item was found and removed.
+ public bool Remove(IEnvelope itemEnv, object item)
+ {
+ // use envelope to restrict nodes scanned
+ if (!IsSearchMatch(itemEnv))
+ {
+ return false;
+ }
+
+ bool found = false;
+ for (int i = 0; i < 4; i++)
+ {
+ if (subnode[i] != null)
+ {
+ found = subnode[i].Remove(itemEnv, item);
+ if (found)
+ {
+ // trim subtree if empty
+ if (subnode[i].IsPrunable)
+ {
+ subnode[i] = null;
+ }
+ break;
+ }
+ }
+ }
+
+ // if item was found lower down, don't need to search for it here
+ if (found)
+ {
+ return found;
+ }
+
+ // otherwise, try and remove the item from the list of items in this node
+ if (items.Contains(item))
+ {
+ items.Remove(item);
+ found = true;
+ }
+ return found;
+ }
+
+ ///
/// Insert items in this into the parameter!
///
/// IList for adding items.
@@ -182,39 +269,46 @@
// this node may have items as well as subnodes (since items may not
// be wholely contained in any single subnode
// resultItems.addAll(this.items);
- foreach (object o in this.items)
+ foreach (object o in items)
+ {
resultItems.Add(o);
- for (int i = 0; i < 4; i++)
+ }
+ for (int i = 0; i < 4; i++)
+ {
if (subnode[i] != null)
- subnode[i].AddAllItems(ref resultItems);
+ {
+ subnode[i].AddAllItems(ref resultItems);
+ }
+ }
return resultItems;
}
///
///
///
///
- ///
- protected abstract bool IsSearchMatch(IEnvelope searchEnv);
-
- ///
- ///
- ///
- ///
///
public void AddAllItemsFromOverlapping(IEnvelope searchEnv, ref IList resultItems)
{
if (!IsSearchMatch(searchEnv))
+ {
return;
+ }
// this node may have items as well as subnodes (since items may not
// be wholely contained in any single subnode
- foreach (object o in this.items)
+ foreach (object o in items)
+ {
resultItems.Add(o);
+ }
- for (int i = 0; i < 4; i++)
+ for (int i = 0; i < 4; i++)
+ {
if (subnode[i] != null)
- subnode[i].AddAllItemsFromOverlapping(searchEnv, ref resultItems);
+ {
+ subnode[i].AddAllItemsFromOverlapping(searchEnv, ref resultItems);
+ }
+ }
}
///
@@ -225,78 +319,42 @@
public void Visit(IEnvelope searchEnv, IItemVisitor visitor)
{
if (!IsSearchMatch(searchEnv))
+ {
return;
+ }
// this node may have items as well as subnodes (since items may not
// be wholely contained in any single subnode
VisitItems(searchEnv, visitor);
for (int i = 0; i < 4; i++)
- if (subnode[i] != null)
- subnode[i].Visit(searchEnv, visitor);
- }
-
- ///
- ///
- ///
- ///
- ///
- private void VisitItems(IEnvelope searchEnv, IItemVisitor visitor)
- {
- // would be nice to filter items based on search envelope, but can't until they contain an envelope
- for (IEnumerator i = items.GetEnumerator(); i.MoveNext(); )
- visitor.VisitItem(i.Current);
- }
-
- ///
- ///
- ///
- public int Depth
- {
- get
{
- int maxSubDepth = 0;
- for (int i = 0; i < 4; i++)
+ if (subnode[i] != null)
{
- if (subnode[i] != null)
- {
- int sqd = subnode[i].Depth;
- if (sqd > maxSubDepth)
- maxSubDepth = sqd;
- }
+ subnode[i].Visit(searchEnv, visitor);
}
- return maxSubDepth + 1;
}
}
///
///
///
- public int Count
- {
- get
- {
- int subSize = 0;
- for (int i = 0; i < 4; i++)
- if (subnode[i] != null)
- subSize += subnode[i].Count;
- return subSize + items.Count;
- }
- }
+ ///
+ ///
+ protected abstract bool IsSearchMatch(IEnvelope searchEnv);
///
///
///
- public int NodeCount
+ ///
+ ///
+ private void VisitItems(IEnvelope searchEnv, IItemVisitor visitor)
{
- get
+ // would be nice to filter items based on search envelope, but can't until they contain an envelope
+ for (IEnumerator i = items.GetEnumerator(); i.MoveNext();)
{
- int subSize = 0;
- for (int i = 0; i < 4; i++)
- if (subnode[i] != null)
- subSize += subnode[i].Count;
- return subSize + 1;
+ visitor.VisitItem(i.Current);
}
}
}
-}
+}
\ No newline at end of file