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    }