001: /*
002: * The JTS Topology Suite is a collection of Java classes that
003: * implement the fundamental operations required to validate a given
004: * geo-spatial data set to a known topological specification.
005: *
006: * Copyright (C) 2001 Vivid Solutions
007: *
008: * This library is free software; you can redistribute it and/or
009: * modify it under the terms of the GNU Lesser General Public
010: * License as published by the Free Software Foundation; either
011: * version 2.1 of the License, or (at your option) any later version.
012: *
013: * This library is distributed in the hope that it will be useful,
014: * but WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * Lesser General Public License for more details.
017: *
018: * You should have received a copy of the GNU Lesser General Public
019: * License along with this library; if not, write to the Free Software
020: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
021: *
022: * For more information, contact:
023: *
024: * Vivid Solutions
025: * Suite #1A
026: * 2328 Government Street
027: * Victoria BC V8T 5G5
028: * Canada
029: *
030: * (250)385-6040
031: * www.vividsolutions.com
032: */
033: package com.vividsolutions.jts.index.bintree;
034:
035: import java.util.ArrayList;
036: import java.util.Collection;
037: import java.util.List;
038:
039: /**
040: * The base class for nodes in a {@link Bintree}.
041: *
042: * @version 1.7
043: */
044: public abstract class NodeBase {
045:
046: /**
047: * Returns the index of the subnode that wholely contains the given interval.
048: * If none does, returns -1.
049: */
050: public static int getSubnodeIndex(Interval interval, double centre) {
051: int subnodeIndex = -1;
052: if (interval.min >= centre)
053: subnodeIndex = 1;
054: if (interval.max <= centre)
055: subnodeIndex = 0;
056: return subnodeIndex;
057: }
058:
059: protected List items = new ArrayList();
060:
061: /**
062: * subnodes are numbered as follows:
063: *
064: * 0 | 1
065: */
066: protected Node[] subnode = new Node[2];
067:
068: public NodeBase() {
069: }
070:
071: public List getItems() {
072: return items;
073: }
074:
075: public void add(Object item) {
076: items.add(item);
077: }
078:
079: public List addAllItems(List items) {
080: items.addAll(this .items);
081: for (int i = 0; i < 2; i++) {
082: if (subnode[i] != null) {
083: subnode[i].addAllItems(items);
084: }
085: }
086: return items;
087: }
088:
089: protected abstract boolean isSearchMatch(Interval interval);
090:
091: public List addAllItemsFromOverlapping(Interval interval,
092: Collection resultItems) {
093: if (!isSearchMatch(interval))
094: return items;
095:
096: // some of these may not actually overlap - this is allowed by the bintree contract
097: resultItems.addAll(items);
098:
099: for (int i = 0; i < 2; i++) {
100: if (subnode[i] != null) {
101: subnode[i].addAllItemsFromOverlapping(interval,
102: resultItems);
103: }
104: }
105: return items;
106: }
107:
108: int depth() {
109: int maxSubDepth = 0;
110: for (int i = 0; i < 2; i++) {
111: if (subnode[i] != null) {
112: int sqd = subnode[i].depth();
113: if (sqd > maxSubDepth)
114: maxSubDepth = sqd;
115: }
116: }
117: return maxSubDepth + 1;
118: }
119:
120: int size() {
121: int subSize = 0;
122: for (int i = 0; i < 2; i++) {
123: if (subnode[i] != null) {
124: subSize += subnode[i].size();
125: }
126: }
127: return subSize + items.size();
128: }
129:
130: int nodeSize() {
131: int subSize = 0;
132: for (int i = 0; i < 2; i++) {
133: if (subnode[i] != null) {
134: subSize += subnode[i].nodeSize();
135: }
136: }
137: return subSize + 1;
138: }
139:
140: }
|