    001    //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.4_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    }