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