001 //$HeadURL: svn+ssh://rbezema@svn.wald.intevation.org/deegree/base/branches/2.2_testing/src/org/deegree/ogcwebservices/wfs/FeatureDisambiguator.java $
002 /*---------------- FILE HEADER ------------------------------------------
003
004 This file is part of deegree.
005 Copyright (C) 2001-2008 by:
006 Department of Geography, University of Bonn
007 http://www.giub.uni-bonn.de/deegree/
008 lat/lon GmbH
009 http://www.lat-lon.de
010
011 This library is free software; you can redistribute it and/or
012 modify it under the terms of the GNU Lesser General Public
013 License as published by the Free Software Foundation; either
014 version 2.1 of the License, or (at your option) any later version.
015
016 This library is distributed in the hope that it will be useful,
017 but WITHOUT ANY WARRANTY; without even the implied warranty of
018 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
019 Lesser General Public License for more details.
020
021 You should have received a copy of the GNU Lesser General Public
022 License along with this library; if not, write to the Free Software
023 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
024
025 Contact:
026
027 Andreas Poth
028 lat/lon GmbH
029 Aennchenstraße 19
030 53177 Bonn
031 Germany
032 E-Mail: poth@lat-lon.de
033
034 Prof. Dr. Klaus Greve
035 Department of Geography
036 University of Bonn
037 Meckenheimer Allee 166
038 53115 Bonn
039 Germany
040 E-Mail: greve@giub.uni-bonn.de
041
042 ---------------------------------------------------------------------------*/
043 package org.deegree.ogcwebservices.wfs;
044
045 import java.util.ArrayList;
046 import java.util.Collection;
047 import java.util.HashMap;
048 import java.util.HashSet;
049 import java.util.List;
050 import java.util.Map;
051 import java.util.Set;
052 import java.util.UUID;
053
054 import org.deegree.framework.log.ILogger;
055 import org.deegree.framework.log.LoggerFactory;
056 import org.deegree.i18n.Messages;
057 import org.deegree.io.datastore.DatastoreException;
058 import org.deegree.io.datastore.schema.MappedFeatureType;
059 import org.deegree.io.datastore.schema.MappedPropertyType;
060 import org.deegree.model.feature.Feature;
061 import org.deegree.model.feature.FeatureCollection;
062 import org.deegree.model.feature.FeatureFactory;
063 import org.deegree.model.feature.FeatureProperty;
064 import org.deegree.model.feature.XLinkedFeatureProperty;
065 import org.deegree.model.feature.schema.PropertyType;
066 import org.deegree.model.spatialschema.Geometry;
067
068 /**
069 * Responsible for the normalization of feature collections that are going to be persisted (i.e.
070 * inserted into a {@link org.deegree.io.datastore Datastore}). This is necessary, because it is up
071 * to WFS clients whether feature ids (gml:id attribute) are provided in an insert/update request or
072 * not.
073 * <p>
074 * After processing, the resulting feature collection meets the following requirements:
075 * <ul>
076 * <li>Every member feature (and subfeature) has a unique feature id that disambiguates it. Note
077 * that this id is only momentarily valid, and that the final feature id is generated by the
078 * <code>FeatureIdAssigner</code> class in a later step.</li>
079 * <li>Features that are equal according to the annotated schema (deegreewfs:IdentityPart
080 * declarations) are represented by the same feature instance.</li>
081 * <li>Complex feature properties use xlink to specify their content if necessary.</li>
082 * <li>Root features in the feature collection never use xlinks.</li>
083 * </ul>
084 *
085 * @author <a href="mailto:schneider@lat-lon.de">Markus Schneider</a>
086 * @author last edited by: $Author: apoth $
087 *
088 * @version $Revision: 9345 $, $Date: 2007-12-27 17:22:25 +0100 (Do, 27 Dez 2007) $
089 */
090 class FeatureDisambiguator {
091
092 private static final ILogger LOG = LoggerFactory.getLogger( FeatureDisambiguator.class );
093
094 private FeatureCollection fc;
095
096 private Map<MappedFeatureType, Set<Feature>> ftMap;
097
098 // key: feature id, value: feature instance (representer for all features with same id)
099 private Map<String, Feature> representerMap = new HashMap<String, Feature>();
100
101 /**
102 * Creates a new <code>FeatureDisambiguator</code> to disambiguate the given feature
103 * collection.
104 *
105 * @param fc
106 * feature collection to disambiguate
107 */
108 FeatureDisambiguator( FeatureCollection fc ) {
109 this.fc = fc;
110 this.ftMap = buildFeatureTypeMap( fc );
111 }
112
113 /**
114 * Checks if any anonymous features (without id) are present in the feature collection.
115 *
116 * @return true, if one or more anonymous features are present, false otherwise
117 */
118 boolean checkForAnonymousFeatures() {
119 for ( MappedFeatureType ft : this.ftMap.keySet() ) {
120 for ( Feature feature : this.ftMap.get( ft ) ) {
121 if ( feature.getId() == null || feature.getId().equals( "" ) ) {
122 return true;
123 }
124 }
125 }
126 return false;
127 }
128
129 /**
130 * Merges all "equal" feature (and subfeature) instances in the associated feature collection
131 * that do not have a feature id. Afterwards, every feature (and subfeature) in the collection
132 * has a unique feature id.
133 * <p>
134 * It is considered an error if there is more than root feature with the same id after the
135 * identification of equal features.
136 * <p>
137 * Furthermore, there is always only one feature instance with a certain id, i.e. "equal"
138 * features are represented by the same feature instance.
139 *
140 * @return "merged" feature collection
141 * @throws DatastoreException
142 */
143 FeatureCollection mergeFeatures()
144 throws DatastoreException {
145
146 assignFIDsAndRepresenters();
147 checkForEqualRootFeatures();
148 replaceDuplicateFeatures();
149 return this.fc;
150 }
151
152 /**
153 * Assigns a (temporarily) feature id to every anonymous feature (or subfeature) of the given
154 * type in the feature collection.
155 * <p>
156 * Also builds the <code>representerMap</code>, so each feature id is mapped to the feature
157 * instance that is used as the single representer for all features instances with this id.
158 * <p>
159 * It is ensured that for each feature id that is associated with a root feature of the
160 * collection, the root feature is used as the representing feature instance. This is important
161 * to guarantee that the root features in the collection represent themselves and need not to be
162 * replaced in {@link #replaceDuplicateFeatures()}.
163 *
164 * @throws DatastoreException
165 */
166 private void assignFIDsAndRepresenters()
167 throws DatastoreException {
168
169 for ( MappedFeatureType ft : this.ftMap.keySet() ) {
170 assignFIDs( ft );
171 }
172
173 // ensure that every root feature is the "representer" for it's feature id
174 for ( int i = 0; i < this.fc.size(); i++ ) {
175 Feature rootFeature = this.fc.getFeature( i );
176 String fid = rootFeature.getId();
177 this.representerMap.put( fid, rootFeature );
178 }
179 }
180
181 /**
182 * Assigns a (temporarily) feature id to every anonymous feature (or subfeature) of the given
183 * type in the feature collection.
184 * <p>
185 * Also builds the <code>representerMap</code>, so every feature id is mapped to a single
186 * feature instance that will represent it everywhere in the collection.
187 *
188 * @param ft
189 * @throws DatastoreException
190 */
191 private void assignFIDs( MappedFeatureType ft )
192 throws DatastoreException {
193
194 Collection<Feature> features = this.ftMap.get( ft );
195
196 LOG.logDebug( "Identifying " + features.size() + " features of type '" + ft.getName() + "'." );
197
198 for ( Feature feature : features ) {
199 // only find features "equal" to feature, if feature does not have an id yet
200 if ( feature.getId() == null || "".equals( feature.getId() ) ) {
201 List<Feature> equalFeatures = new ArrayList<Feature>();
202 equalFeatures.add( feature );
203
204 for ( Feature otherFeature : features ) {
205 if ( compareFeatures( feature, otherFeature, new HashMap<Feature, List<Feature>>() ) ) {
206 LOG.logDebug( "Found matching features of type: '" + ft.getName() + "'." );
207 equalFeatures.add( otherFeature );
208 }
209 }
210 assignSameFID( equalFeatures );
211 }
212 }
213
214 for ( Feature feature : features ) {
215 String fid = feature.getId();
216 if ( this.representerMap.get( fid ) == null ) {
217 this.representerMap.put( fid, feature );
218 }
219 }
220 }
221
222 /**
223 * Assigns the same feature id to every feature in the given list of "equal" features.
224 * <p>
225 * If any feature in the list has a feature id assigned to it already, this feature id is used.
226 * If no feature has a feature id, a new feature id (a UUID) is generated.
227 *
228 * @param equalFeatures
229 * @throws DatastoreException
230 */
231 private void assignSameFID( List<Feature> equalFeatures )
232 throws DatastoreException {
233
234 LOG.logDebug( "Found " + equalFeatures.size() + " 'equal' features of type "
235 + equalFeatures.get( 0 ).getFeatureType().getName() );
236
237 String fid = null;
238
239 // check if any feature has a fid already
240 for ( Feature feature : equalFeatures ) {
241 String otherFid = feature.getId();
242 if ( otherFid != null && !otherFid.equals( "" ) ) {
243 if ( fid != null && !fid.equals( otherFid ) ) {
244 String msg = Messages.getMessage( "WFS_IDENTICAL_FEATURES", feature.getFeatureType().getName(),
245 fid, otherFid );
246 throw new DatastoreException( msg );
247 }
248 fid = otherFid;
249 }
250 }
251
252 if ( fid == null ) {
253 fid = UUID.randomUUID().toString();
254 this.representerMap.put( fid, equalFeatures.get( 0 ) );
255 }
256
257 // assign fid to every "equal" feature
258 for ( Feature feature : equalFeatures ) {
259 feature.setId( fid );
260 }
261 }
262
263 /**
264 * Determines whether two feature instances are "equal" according to the annotated schema
265 * (deegreewfs:IdentityPart declarations).
266 *
267 * @param feature1
268 * @param feature2
269 * @param compareMap
270 * @return true, if the two features are "equal", false otherwise
271 */
272 private boolean compareFeatures( Feature feature1, Feature feature2, Map<Feature, List<Feature>> compareMap ) {
273
274 LOG.logDebug( "feature1: " + feature1.getName() + " id=" + feature1.getId() + " hashCode="
275 + feature1.hashCode() );
276 LOG.logDebug( "feature2: " + feature2.getName() + " id=" + feature2.getId() + " hashCode="
277 + feature2.hashCode() );
278
279 // same feature instance? -> equal
280 if ( feature1 == feature2 ) {
281 return true;
282 }
283
284 // same feature id -> equal / different feature id -> not equal
285 String fid1 = feature1.getId();
286 String fid2 = feature2.getId();
287 if ( fid1 != null && fid2 != null && !"".equals( fid1 ) && !"".equals( fid2 ) ) {
288 return fid1.equals( fid2 );
289 }
290
291 // different feature types? -> not equal
292 MappedFeatureType ft = (MappedFeatureType) feature1.getFeatureType();
293 if ( feature2.getFeatureType() != ft ) {
294 return false;
295 }
296
297 // feature id is identity part? -> not equal (unique ids for all anonymous features)
298 if ( ft.getGMLId().isIdentityPart() ) {
299 return false;
300 }
301
302 // there is already a compareFeatures() call with these features on the stack
303 // -> end recursion
304 List<Feature> features = compareMap.get( feature1 );
305 if ( features == null ) {
306 features = new ArrayList<Feature>();
307 compareMap.put( feature1, features );
308 } else {
309 for ( Feature feature : features ) {
310 if ( feature2 == feature ) {
311 return true;
312 }
313 }
314 }
315 features.add( feature2 );
316
317 features = compareMap.get( feature2 );
318 if ( features == null ) {
319 features = new ArrayList<Feature>();
320 compareMap.put( feature2, features );
321 } else {
322 for ( Feature feature : features ) {
323 if ( feature1 == feature ) {
324 return true;
325 }
326 }
327 }
328 features.add( feature1 );
329
330 // check every "relevant" property for equality
331 PropertyType[] properties = ft.getProperties();
332 for ( int i = 0; i < properties.length; i++ ) {
333 MappedPropertyType propertyType = (MappedPropertyType) properties[i];
334 if ( propertyType.isIdentityPart() ) {
335 if ( !compareProperties( propertyType, feature1, feature2, compareMap ) ) {
336 LOG.logDebug( "Not equal: values for property '" + propertyType.getName() + " do not match." );
337 return false;
338 }
339 }
340 }
341 return true;
342 }
343
344 /**
345 * Determines whether two feature instances have the same content in the specified property.
346 *
347 * @param propertyType
348 * @param feature1
349 * @param feature2
350 * @param compareMap
351 * @return true, if the properties are "equal", false otherwise
352 */
353 private boolean compareProperties( MappedPropertyType propertyType, Feature feature1, Feature feature2,
354 Map<Feature, List<Feature>> compareMap ) {
355
356 FeatureProperty[] props1 = feature1.getProperties( propertyType.getName() );
357 FeatureProperty[] props2 = feature2.getProperties( propertyType.getName() );
358
359 if ( props1 != null && props2 != null ) {
360 if ( props1.length != props2.length ) {
361 return false;
362 }
363 // TODO handle different orders of multi properties
364 for ( int j = 0; j < props1.length; j++ ) {
365 Object value1 = props1[j].getValue();
366 Object value2 = props2[j].getValue();
367
368 if ( value1 == null && value2 == null ) {
369 continue;
370 } else if ( !( value1 != null && value2 != null ) ) {
371 return false;
372 }
373
374 if ( value1 instanceof Feature ) {
375 // complex valued property (subfeature)
376 if ( !( value2 instanceof Feature ) ) {
377 return false;
378 }
379 Feature subfeature1 = (Feature) value1;
380 Feature subfeature2 = (Feature) value2;
381
382 if ( !compareFeatures( subfeature1, subfeature2, compareMap ) ) {
383 return false;
384 }
385 } else {
386 if ( value1 instanceof Geometry ) {
387 String msg = "Check for equal geometry properties is not implemented yet. "
388 + "Do not set 'identityPart' to true in geometry property " + "definitions.";
389 throw new RuntimeException( msg );
390 }
391 // simple valued property
392 if ( !value1.equals( value2 ) ) {
393 return false;
394 }
395 }
396 }
397 } else if ( !( props1 == null && props2 == null ) ) {
398 return false;
399 }
400 return true;
401 }
402
403 /**
404 * Checks that there are no root features in the collection that are "equal".
405 * <p>
406 * After disambiguation these features have the same feature id.
407 *
408 * @throws DatastoreException
409 */
410 private void checkForEqualRootFeatures()
411 throws DatastoreException {
412 Set<String> rootFIDs = new HashSet<String>();
413 for ( int i = 0; i < fc.size(); i++ ) {
414 String fid = fc.getFeature( i ).getId();
415 if ( rootFIDs.contains( fid ) ) {
416 String msg = Messages.getMessage( "WFS_SAME_ROOT_FEATURE_ID" );
417 throw new DatastoreException( msg );
418 }
419 rootFIDs.add( fid );
420 }
421 }
422
423 /**
424 * Determines the feature type of all features (and subfeatures) in the given feature collection
425 * and builds a lookup map.
426 *
427 * @param fc
428 * @return lookup map that maps each feature instance to it's feature type
429 */
430 private Map<MappedFeatureType, Set<Feature>> buildFeatureTypeMap( FeatureCollection fc ) {
431 LOG.logDebug( "Building feature map." );
432 Map<MappedFeatureType, Set<Feature>> ftMap = new HashMap<MappedFeatureType, Set<Feature>>();
433 for ( int i = 0; i < fc.size(); i++ ) {
434 addToFeatureTypeMap( fc.getFeature( i ), ftMap );
435 }
436 return ftMap;
437 }
438
439 /**
440 * Recursively adds the given feature (and it's subfeatures) to the given map. To cope with
441 * cyclic features, the recursion ends if the feature instance is already present in the map.
442 *
443 * @param feature
444 * feature instance to add
445 * @param ftMap
446 */
447 private void addToFeatureTypeMap( Feature feature, Map<MappedFeatureType, Set<Feature>> ftMap ) {
448
449 MappedFeatureType ft = (MappedFeatureType) feature.getFeatureType();
450 Set<Feature> features = ftMap.get( ft );
451 if ( features == null ) {
452 features = new HashSet<Feature>();
453 ftMap.put( ft, features );
454 } else {
455 if ( features.contains( feature ) ) {
456 return;
457 }
458 }
459 features.add( feature );
460
461 // recurse into subfeatures
462 FeatureProperty[] properties = feature.getProperties();
463 for ( int i = 0; i < properties.length; i++ ) {
464 Object propertyValue = properties[i].getValue();
465 if ( propertyValue instanceof Feature ) {
466 Feature subFeature = (Feature) propertyValue;
467 addToFeatureTypeMap( subFeature, ftMap );
468 }
469 }
470 }
471
472 /**
473 * Ensures that all features with the same feature id refer to the same feature instance.
474 * <p>
475 * Xlinked content is used for every subfeature that has been encountered already (or is a root
476 * feature of the collection).
477 * <p>
478 * Root features are never replaced, because {@link #assignFIDsAndRepresenters()} ensures that
479 * root features always represent themselves.
480 */
481 private void replaceDuplicateFeatures() {
482
483 Set<String> xlinkFIDs = new HashSet<String>();
484
485 // ensure that root features are always referred to by xlink properties
486 for ( int i = 0; i < this.fc.size(); i++ ) {
487 Feature feature = this.fc.getFeature( i );
488 xlinkFIDs.add( feature.getId() );
489 }
490
491 for ( int i = 0; i < this.fc.size(); i++ ) {
492 Feature feature = this.fc.getFeature( i );
493 replaceDuplicateFeatures( feature, xlinkFIDs );
494 }
495 }
496
497 /**
498 * Replaces all subfeatures of the given feature instance by their "representers".
499 * <p>
500 * Xlinked content is used for every subfeature that has been encountered already (or that is a
501 * root feature of the collection).
502 *
503 * @param feature
504 * @param xlinkFIDs
505 */
506 private void replaceDuplicateFeatures( Feature feature, Set<String> xlinkFIDs ) {
507
508 LOG.logDebug( "Replacing in feature: '" + feature.getName() + "', " + feature.getId() );
509 xlinkFIDs.add( feature.getId() );
510
511 FeatureProperty[] properties = feature.getProperties();
512 for ( int i = 0; i < properties.length; i++ ) {
513 Object value = properties[i].getValue();
514 if ( value != null && value instanceof Feature ) {
515
516 Feature subfeature = (Feature) value;
517 String fid = subfeature.getId();
518 subfeature = this.representerMap.get( fid );
519
520 FeatureProperty oldProperty = properties[i];
521 FeatureProperty newProperty = null;
522
523 if ( !xlinkFIDs.contains( fid ) ) {
524 // first occurence in feature collection
525 LOG.logDebug( "Not-XLink feature property: " + fid );
526 newProperty = FeatureFactory.createFeatureProperty( oldProperty.getName(), subfeature );
527 replaceDuplicateFeatures( subfeature, xlinkFIDs );
528 } else {
529 // successive occurence in feature collection (use XLink)
530 LOG.logDebug( "XLink feature property: " + fid );
531 newProperty = new XLinkedFeatureProperty( oldProperty.getName(), fid );
532 newProperty.setValue( subfeature );
533 }
534 feature.replaceProperty( oldProperty, newProperty );
535 }
536 }
537 }
538 }