001 //$HeadURL: svn+ssh://rbezema@svn.wald.intevation.org/deegree/base/tags/2.1/src/org/deegree/ogcwebservices/wfs/FeatureDisambiguator.java $
002 /*---------------- FILE HEADER ------------------------------------------
003
004 This file is part of deegree.
005 Copyright (C) 2001-2006 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: 7897 $, $Date: 2007-08-06 10:11:35 +0200 (Mo, 06 Aug 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
199 for ( Feature feature : features ) {
200 // only find features "equal" to feature, if feature does not have an id yet
201 if ( feature.getId() == null || "".equals( feature.getId() ) ) {
202 List<Feature> equalFeatures = new ArrayList<Feature>();
203 equalFeatures.add( feature );
204
205 for ( Feature otherFeature : features ) {
206 if ( compareFeatures( feature, otherFeature,
207 new HashMap<Feature, List<Feature>>() ) ) {
208 LOG.logDebug( "Found matching features of type: '" + ft.getName() + "'." );
209 equalFeatures.add( otherFeature );
210 }
211 }
212 assignSameFID( equalFeatures );
213 }
214 }
215
216 for ( Feature feature : features ) {
217 String fid = feature.getId();
218 if ( this.representerMap.get( fid ) == null ) {
219 this.representerMap.put( fid, feature );
220 }
221 }
222 }
223
224 /**
225 * Assigns the same feature id to every feature in the given list of "equal" features.
226 * <p>
227 * If any feature in the list has a feature id assigned to it already, this feature id is used.
228 * If no feature has a feature id, a new feature id (a UUID) is generated.
229 *
230 * @param equalFeatures
231 * @throws DatastoreException
232 */
233 private void assignSameFID( List<Feature> equalFeatures )
234 throws DatastoreException {
235
236 LOG.logDebug( "Found " + equalFeatures.size() + " 'equal' features of type "
237 + equalFeatures.get( 0 ).getFeatureType().getName() );
238
239 String fid = null;
240
241 // check if any feature has a fid already
242 for ( Feature feature : equalFeatures ) {
243 String otherFid = feature.getId();
244 if ( otherFid != null && !otherFid.equals( "" ) ) {
245 if ( fid != null && !fid.equals( otherFid ) ) {
246 String msg = Messages.getMessage( "WFS_IDENTICAL_FEATURES",
247 feature.getFeatureType().getName(), fid,
248 otherFid );
249 throw new DatastoreException( msg );
250 }
251 fid = otherFid;
252 }
253 }
254
255 if ( fid == null ) {
256 fid = UUID.randomUUID().toString();
257 this.representerMap.put( fid, equalFeatures.get( 0 ) );
258 }
259
260 // assign fid to every "equal" feature
261 for ( Feature feature : equalFeatures ) {
262 feature.setId( fid );
263 }
264 }
265
266 /**
267 * Determines whether two feature instances are "equal" according to the annotated schema
268 * (deegreewfs:IdentityPart declarations).
269 *
270 * @param feature1
271 * @param feature2
272 * @param compareMap
273 * @return true, if the two features are "equal", false otherwise
274 */
275 private boolean compareFeatures( Feature feature1, Feature feature2,
276 Map<Feature, List<Feature>> compareMap ) {
277
278 LOG.logDebug( "feature1: " + feature1.getName() + " id=" + feature1.getId() + " hashCode="
279 + feature1.hashCode() );
280 LOG.logDebug( "feature2: " + feature2.getName() + " id=" + feature2.getId() + " hashCode="
281 + feature2.hashCode() );
282
283 // same feature instance? -> equal
284 if ( feature1 == feature2 ) {
285 return true;
286 }
287
288 // same feature id -> equal / different feature id -> not equal
289 String fid1 = feature1.getId();
290 String fid2 = feature2.getId();
291 if ( fid1 != null && fid2 != null && !"".equals( fid1 ) && !"".equals( fid2 ) ) {
292 return fid1.equals( fid2 );
293 }
294
295 // different feature types? -> not equal
296 MappedFeatureType ft = (MappedFeatureType) feature1.getFeatureType();
297 if ( feature2.getFeatureType() != ft ) {
298 return false;
299 }
300
301 // feature id is identity part? -> not equal (unique ids for all anonymous features)
302 if ( ft.getGMLId().isIdentityPart() ) {
303 return false;
304 }
305
306 // there is already a compareFeatures() call with these features on the stack
307 // -> end recursion
308 List<Feature> features = compareMap.get( feature1 );
309 if ( features == null ) {
310 features = new ArrayList<Feature>();
311 compareMap.put( feature1, features );
312 } else {
313 for ( Feature feature : features ) {
314 if ( feature2 == feature ) {
315 return true;
316 }
317 }
318 }
319 features.add( feature2 );
320
321 features = compareMap.get( feature2 );
322 if ( features == null ) {
323 features = new ArrayList<Feature>();
324 compareMap.put( feature2, features );
325 } else {
326 for ( Feature feature : features ) {
327 if ( feature1 == feature ) {
328 return true;
329 }
330 }
331 }
332 features.add( feature1 );
333
334 // check every "relevant" property for equality
335 PropertyType[] properties = ft.getProperties();
336 for ( int i = 0; i < properties.length; i++ ) {
337 MappedPropertyType propertyType = (MappedPropertyType) properties[i];
338 if ( propertyType.isIdentityPart() ) {
339 if ( !compareProperties( propertyType, feature1, feature2, compareMap ) ) {
340 LOG.logDebug( "Not equal: values for property '" + propertyType.getName()
341 + " do not match." );
342 return false;
343 }
344 }
345 }
346 return true;
347 }
348
349 /**
350 * Determines whether two feature instances have the same content in the specified property.
351 *
352 * @param propertyType
353 * @param feature1
354 * @param feature2
355 * @param compareMap
356 * @return true, if the properties are "equal", false otherwise
357 */
358 private boolean compareProperties( MappedPropertyType propertyType, Feature feature1,
359 Feature feature2, Map<Feature, List<Feature>> compareMap ) {
360
361 FeatureProperty[] props1 = feature1.getProperties( propertyType.getName() );
362 FeatureProperty[] props2 = feature2.getProperties( propertyType.getName() );
363
364 if ( props1 != null && props2 != null ) {
365 if ( props1.length != props2.length ) {
366 return false;
367 }
368 // TODO handle different orders of multi properties
369 for ( int j = 0; j < props1.length; j++ ) {
370 Object value1 = props1[j].getValue();
371 Object value2 = props2[j].getValue();
372
373 if ( value1 == null && value2 == null ) {
374 continue;
375 } else if ( !( value1 != null && value2 != null ) ) {
376 return false;
377 }
378
379 if ( value1 instanceof Feature ) {
380 // complex valued property (subfeature)
381 if ( !( value2 instanceof Feature ) ) {
382 return false;
383 }
384 Feature subfeature1 = (Feature) value1;
385 Feature subfeature2 = (Feature) value2;
386
387 if ( !compareFeatures( subfeature1, subfeature2, compareMap ) ) {
388 return false;
389 }
390 } else {
391 if ( value1 instanceof Geometry ) {
392 String msg = "Check for equal geometry properties is not implemented yet. "
393 + "Do not set 'identityPart' to true in geometry property "
394 + "definitions.";
395 throw new RuntimeException( msg );
396 }
397 // simple valued property
398 if ( !value1.equals( value2 ) ) {
399 return false;
400 }
401 }
402 }
403 } else if ( !( props1 == null && props2 == null ) ) {
404 return false;
405 }
406 return true;
407 }
408
409 /**
410 * Checks that there are no root features in the collection that are "equal".
411 * <p>
412 * After disambiguation these features have the same feature id.
413 *
414 * @throws DatastoreException
415 */
416 private void checkForEqualRootFeatures()
417 throws DatastoreException {
418 Set<String> rootFIDs = new HashSet<String>();
419 for ( int i = 0; i < fc.size(); i++ ) {
420 String fid = fc.getFeature( i ).getId();
421 if ( rootFIDs.contains( fid ) ) {
422 String msg = Messages.getMessage( "WFS_SAME_ROOT_FEATURE_ID" );
423 throw new DatastoreException( msg );
424 }
425 rootFIDs.add( fid );
426 }
427 }
428
429 /**
430 * Determines the feature type of all features (and subfeatures) in the given feature collection
431 * and builds a lookup map.
432 *
433 * @param fc
434 * @return lookup map that maps each feature instance to it's feature type
435 */
436 private Map<MappedFeatureType, Set<Feature>> buildFeatureTypeMap( FeatureCollection fc ) {
437 LOG.logDebug( "Building feature map." );
438 Map<MappedFeatureType, Set<Feature>> ftMap = new HashMap<MappedFeatureType, Set<Feature>>();
439 for ( int i = 0; i < fc.size(); i++ ) {
440 addToFeatureTypeMap( fc.getFeature( i ), ftMap );
441 }
442 return ftMap;
443 }
444
445 /**
446 * Recursively adds the given feature (and it's subfeatures) to the given map. To cope with
447 * cyclic features, the recursion ends if the feature instance is already present in the map.
448 *
449 * @param feature
450 * feature instance to add
451 * @param ftMap
452 */
453 private void addToFeatureTypeMap( Feature feature, Map<MappedFeatureType, Set<Feature>> ftMap ) {
454
455 MappedFeatureType ft = (MappedFeatureType) feature.getFeatureType();
456 Set<Feature> features = ftMap.get( ft );
457 if ( features == null ) {
458 features = new HashSet<Feature>();
459 ftMap.put( ft, features );
460 } else {
461 if ( features.contains( feature ) ) {
462 return;
463 }
464 }
465 features.add( feature );
466
467 // recurse into subfeatures
468 FeatureProperty[] properties = feature.getProperties();
469 for ( int i = 0; i < properties.length; i++ ) {
470 Object propertyValue = properties[i].getValue();
471 if ( propertyValue instanceof Feature ) {
472 Feature subFeature = (Feature) propertyValue;
473 addToFeatureTypeMap( subFeature, ftMap );
474 }
475 }
476 }
477
478 /**
479 * Ensures that all features with the same feature id refer to the same feature instance.
480 * <p>
481 * Xlinked content is used for every subfeature that has been encountered already (or is a root
482 * feature of the collection).
483 * <p>
484 * Root features are never replaced, because {@link #assignFIDsAndRepresenters()} ensures that
485 * root features always represent themselves.
486 */
487 private void replaceDuplicateFeatures() {
488
489 Set<String> xlinkFIDs = new HashSet<String>();
490
491 // ensure that root features are always referred to by xlink properties
492 for ( int i = 0; i < this.fc.size(); i++ ) {
493 Feature feature = this.fc.getFeature( i );
494 xlinkFIDs.add( feature.getId() );
495 }
496
497 for ( int i = 0; i < this.fc.size(); i++ ) {
498 Feature feature = this.fc.getFeature( i );
499 replaceDuplicateFeatures( feature, xlinkFIDs );
500 }
501 }
502
503 /**
504 * Replaces all subfeatures of the given feature instance by their "representers".
505 * <p>
506 * Xlinked content is used for every subfeature that has been encountered already (or that is a
507 * root feature of the collection).
508 *
509 * @param feature
510 * @param xlinkFIDs
511 */
512 private void replaceDuplicateFeatures( Feature feature, Set<String> xlinkFIDs ) {
513
514 LOG.logDebug( "Replacing in feature: '" + feature.getName() + "', " + feature.getId() );
515 xlinkFIDs.add( feature.getId() );
516
517 FeatureProperty[] properties = feature.getProperties();
518 for ( int i = 0; i < properties.length; i++ ) {
519 Object value = properties[i].getValue();
520 if ( value != null && value instanceof Feature ) {
521
522 Feature subfeature = (Feature) value;
523 String fid = subfeature.getId();
524 subfeature = this.representerMap.get( fid );
525
526 FeatureProperty oldProperty = properties[i];
527 FeatureProperty newProperty = null;
528
529 if ( !xlinkFIDs.contains( fid ) ) {
530 // first occurence in feature collection
531 LOG.logDebug( "Not-XLink feature property: " + fid );
532 newProperty = FeatureFactory.createFeatureProperty( oldProperty.getName(),
533 subfeature );
534 replaceDuplicateFeatures( subfeature, xlinkFIDs );
535 } else {
536 // successive occurence in feature collection (use XLink)
537 LOG.logDebug( "XLink feature property: " + fid );
538 newProperty = new XLinkedFeatureProperty( oldProperty.getName(), fid );
539 newProperty.setValue( subfeature );
540 }
541 feature.replaceProperty( oldProperty, newProperty );
542 }
543 }
544 }
545 }