001 //$HeadURL: svn+ssh://rbezema@svn.wald.intevation.org/deegree/base/branches/2.2_testing/src/org/deegree/io/rtree/NoneLeafNode.java $
002 //
003 // RTree implementation.
004 // Copyright (C) 2002-2004 Wolfgang Baer - WBaer@gmx.de
005 //
006 // This library is free software; you can redistribute it and/or
007 // modify it under the terms of the GNU Lesser General Public
008 // License as published by the Free Software Foundation; either
009 // version 2.1 of the License, or (at your option) any later version.
010 //
011 // This library is distributed in the hope that it will be useful,
012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014 // Lesser General Public License for more details.
015 //
016 // You should have received a copy of the GNU Lesser General Public
017 // License along with this library; if not, write to the Free Software
018 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019
020 package org.deegree.io.rtree;
021
022
023 /**
024 * <p>
025 * Implementation of a NoneLeafNode.
026 * Inherits methods from the abstract class Node filling
027 * the defined abstract methods with life.
028 * </p>
029 * @author Wolfgang Baer - WBaer@gmx.de
030 */
031 class NoneLeafNode extends Node {
032
033 protected int[] childNodes;
034
035 /**
036 * Constructor.
037 * @param pageNumber - number of this node in page file
038 * @param file - the PageFile of this node
039 */
040 protected NoneLeafNode( int pageNumber, PageFile file ) {
041 super( pageNumber, file );
042 childNodes = new int[file.getCapacity()];
043
044 for ( int i = 0; i < file.getCapacity(); i++ )
045 childNodes[i] = -1;
046 }
047
048 /**
049 * @see Node#getData(int)
050 */
051 protected Object getData( int index ) {
052 Object obj = null;
053
054 try {
055 obj = file.readNode( childNodes[index] );
056 } catch ( PageFileException e ) {
057 // PageFileException NoneLeafNode.getData
058 e.printStackTrace();
059 }
060
061 return obj;
062 }
063
064 /**
065 * @see Node#insertData(java.lang.Object, HyperBoundingBox)
066 */
067 protected void insertData(Object node, HyperBoundingBox box) {
068 childNodes[counter] = ( (Node)node ).getPageNumber();
069 hyperBBs[counter] = box;
070 unionMinBB = unionMinBB.unionBoundingBox( box );
071 ( (Node)node ).parentNode = this.pageNumber;
072 ( (Node)node ).place = this.counter;
073 counter++;
074
075 try {
076 file.writeNode( (Node)node );
077 } catch ( PageFileException e ) {
078 //PageFileException NoneLeafNode.insertData - at writeNode(Node)
079 e.printStackTrace();
080 }
081 }
082
083 /**
084 * @see Node#insertData(java.lang.Object, HyperBoundingBox)
085 */
086 protected void deleteData(int index) {
087
088 if ( this.getUsedSpace() == 1 ) {
089 // only one element is a special case.
090 hyperBBs[0] = HyperBoundingBox.getNullHyperBoundingBox( file.getDimension() );
091 childNodes[0] = -1;
092 counter--;
093 }
094 else {
095 System.arraycopy( hyperBBs, index + 1, hyperBBs, index, counter - index - 1 );
096 System.arraycopy( childNodes, index + 1, childNodes, index, counter - index - 1 );
097 hyperBBs[counter - 1] = HyperBoundingBox.getNullHyperBoundingBox( file.getDimension() );
098 childNodes[counter - 1] = -1;
099 counter--;
100
101 for ( int i = 0; i < counter; i++ ) {
102 Node help = (Node)this.getData( i );
103 help.place = i;
104
105 try {
106 file.writeNode( help );
107 } catch ( PageFileException e ) {
108 // "PageFileException NoneLeafNode.deleteData - at writeNode(Node)
109 e.printStackTrace();
110 }
111 }
112 }
113
114 updateNodeBoundingBox();
115 }
116
117 /**
118 * Computes the index of the entry with least enlargement if the given
119 * HyperBoundingBox would be added.
120 * @param box - HyperBoundingBox to be added
121 * @return int - index of entry with least enlargement
122 */
123 protected int getLeastEnlargement(HyperBoundingBox box) {
124
125 double[] area = new double[counter];
126
127 for ( int i = 0; i < counter; i++ )
128 area[i] = ( hyperBBs[i].unionBoundingBox( box ) ).getArea() - hyperBBs[i].getArea();
129
130 double min = area[0];
131 int minnr = 0;
132
133 for ( int i = 1; i < counter; i++ ) {
134 if ( area[i] < min ) {
135 min = area[i];
136 minnr = i;
137 }
138 }
139
140 return minnr;
141 }
142
143 /**
144 * @see Node#clone()
145 */
146 protected Object clone() {
147 NoneLeafNode clone = new NoneLeafNode( this.pageNumber, this.file );
148 clone.counter = this.counter;
149 clone.place = this.place;
150 clone.unionMinBB = (HyperBoundingBox)this.unionMinBB.clone();
151 clone.parentNode = this.parentNode;
152
153 for ( int i = 0; i < file.getCapacity(); i++ )
154 clone.hyperBBs[i] = (HyperBoundingBox)this.hyperBBs[i].clone();
155
156 return clone;
157 }
158 }