Changeset 2166 in josm


Ignore:
Timestamp:
2009-09-20T11:07:46+02:00 (12 years ago)
Author:
stoecker
Message:

see #3475 - patch by Petr Dlouhý - improve speed

Location:
trunk/src/org/openstreetmap/josm
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/actions/CreateCircleAction.java

    r2017 r2166  
    172172                // if it is, delete it
    173173                CollectBackReferencesVisitor refs = new CollectBackReferencesVisitor(getCurrentDataSet());
     174                refs.initialize();
    174175                refs.visit(n1);
    175                 if (refs.data.isEmpty() || ((refs.data.size() == 1) && (refs.data.contains(existingWay)))) {
     176                if (refs.getData().isEmpty() || ((refs.getData().size() == 1) && (refs.getData().contains(existingWay)))) {
    176177                    cmds.add(new DeleteCommand(n1));
    177178                }
  • trunk/src/org/openstreetmap/josm/actions/search/SearchAction.java

    r2145 r2166  
    182182               searchText = (((Filter)s).inverted ? "-" : "") + "(" +  searchText + ")";
    183183            }
    184             System.out.println(searchText);
     184            /*System.out.println(searchText);*/
    185185            SearchCompiler.Match matcher = SearchCompiler.compile(searchText, s.caseSensitive, s.regexSearch);
    186186            foundMatches = 0;
  • trunk/src/org/openstreetmap/josm/actions/search/SearchCompiler.java

    r2070 r2166  
    3333    private String  rxErrorMsg = marktr("The regex \"{0}\" had a parse error at offset {1}, full error:\n\n{2}");
    3434    private PushbackTokenizer tokenizer;
     35    private static CollectBackReferencesVisitor childBackRefs;
    3536
    3637    public SearchCompiler(boolean caseSensitive, boolean regexSearch, PushbackTokenizer tokenizer) {
     
    3839        this.regexSearch = regexSearch;
    3940        this.tokenizer = tokenizer;
     41        childBackRefs = new CollectBackReferencesVisitor(Main.main.getCurrentDataSet());
    4042    }
    4143
     
    481483
    482484            boolean isChild = false;
    483             CollectBackReferencesVisitor backRefs = new CollectBackReferencesVisitor(Main.main.getCurrentDataSet());
    484             osm.visit(backRefs);
    485             for (OsmPrimitive p : backRefs.data) {
     485            childBackRefs.initialize();
     486            osm.visit(childBackRefs);
     487            for (OsmPrimitive p : childBackRefs.getData()) {
    486488                isChild |= parent.match(p);
    487489            }
  • trunk/src/org/openstreetmap/josm/command/DeleteCommand.java

    r2070 r2166  
    163163    public static Command deleteWithReferences(OsmDataLayer layer, Collection<? extends OsmPrimitive> selection, boolean simulate) {
    164164        CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data);
     165        v.initialize();
    165166        for (OsmPrimitive osm : selection) {
    166167            osm.visit(v);
    167168        }
    168         v.data.addAll(selection);
    169         if (v.data.isEmpty())
     169        v.getData().addAll(selection);
     170        if (v.getData().isEmpty())
    170171            return null;
    171         if (!checkAndConfirmOutlyingDeletes(layer,v.data) && !simulate)
     172        if (!checkAndConfirmOutlyingDeletes(layer,v.getData()) && !simulate)
    172173            return null;
    173         return new DeleteCommand(layer,v.data);
     174        return new DeleteCommand(layer,v.getData());
    174175    }
    175176
     
    239240    protected static Collection<Node> computeNodesToDelete(OsmDataLayer layer, Collection<OsmPrimitive> primitivesToDelete) {
    240241        Collection<Node> nodesToDelete = new HashSet<Node>();
     242        CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data, false);
    241243        for (OsmPrimitive osm : primitivesToDelete) {
    242244            if (! (osm instanceof Way) ) {
     
    247249                    continue;
    248250                }
    249                 CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data, false);
     251                v.initialize();
    250252                n.visit(v);
    251                 v.data.removeAll(primitivesToDelete);
    252                 if (v.data.isEmpty()) {
     253                v.getData().removeAll(primitivesToDelete);
     254                if (v.getData().isEmpty()) {
    253255                    nodesToDelete.add(n);
    254256                }
     
    297299            return null;
    298300
     301        CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data, false);
    299302        for (OsmPrimitive osm : primitivesToDelete) {
    300             CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data, false);
     303            v.initialize();
    301304            osm.visit(v);
    302             for (OsmPrimitive ref : v.data) {
     305            for (OsmPrimitive ref : v.getData()) {
    303306                if (primitivesToDelete.contains(ref)) {
    304307                    continue;
     
    328331                primitivesToDelete.add(w);
    329332
    330                 CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(layer.data, false);
     333                v.initialize();
    331334                w.visit(v);
    332                 for (OsmPrimitive ref : v.data) {
     335                for (OsmPrimitive ref : v.getData()) {
    333336                    if (primitivesToDelete.contains(ref)) {
    334337                        continue;
  • trunk/src/org/openstreetmap/josm/data/osm/visitor/CollectBackReferencesVisitor.java

    r2070 r2166  
    44import java.util.Collection;
    55import java.util.HashSet;
     6import java.util.HashMap;
     7import java.util.Map;
    68
    79import org.openstreetmap.josm.data.osm.DataSet;
     
    1719 * Deleted objects are not collected.
    1820 *
    19  * @author imi
     21 * @author imi, Petr Dlouhý
    2022 */
    2123public class CollectBackReferencesVisitor extends AbstractVisitor {
     
    2426    private final boolean indirectRefs;
    2527
    26     /**
    27      * The result list of primitives stored here.
    28      */
    29     public final Collection<OsmPrimitive> data = new HashSet<OsmPrimitive>();
     28    private Collection<OsmPrimitive> data = new HashSet<OsmPrimitive>();
     29    private Map<OsmPrimitive, Collection<OsmPrimitive>> lookupTable = new HashMap<OsmPrimitive, Collection<OsmPrimitive>>();
    3030
    3131
    3232    /**
    3333     * Construct a back reference counter.
     34     * has time complexity O(n) - so it is appropriate not to call it in cycle
    3435     * @param ds The dataset to operate on.
    3536     */
    3637    public CollectBackReferencesVisitor(DataSet ds) {
    37         this.ds = ds;
    38         this.indirectRefs = true;
     38       this(ds, true);
    3939    }
    4040
     41    /**
     42     * Construct a back reference counter.
     43     * has time complexity O(n) - so it is appropriate not to call it in cycle
     44     * @param ds The dataset to operate on.
     45     * @param indirectRefs Make also indirect references?
     46     */
    4147    public CollectBackReferencesVisitor(DataSet ds, boolean indirectRefs) {
    42         this.ds = ds;
    43         this.indirectRefs = indirectRefs;
     48       this.ds = ds;
     49       this.indirectRefs = indirectRefs;
     50       if(ds != null)
     51          makeLookupTable();
     52    }
     53   
     54    private void makeLookupTable(){
     55       for (Way w : ds.ways) {
     56          for (Node n : w.getNodes()) {
     57             if(!lookupTable.containsKey(n)) lookupTable.put(n, new HashSet<OsmPrimitive>());
     58             lookupTable.get(n).add(w);
     59          }
     60       }
     61       for (Relation r : ds.relations) {
     62          for (RelationMember m : r.getMembers()) {
     63             OsmPrimitive o = m.getMember();
     64             if(!lookupTable.containsKey(o)) lookupTable.put(o, new HashSet<OsmPrimitive>());
     65             lookupTable.get(o).add(r);
     66          }
     67       }
    4468    }
    4569
     70    /**
     71     * Get the result collection
     72     */
     73    public Collection<OsmPrimitive> getData(){
     74       return data;
     75    }
     76
     77    /**
     78     * Initialize data before associated visit calls
     79     */
     80    public void initialize(){
     81       data = new HashSet<OsmPrimitive>();
     82    }
     83
     84    public void visit(OsmPrimitive o) {
     85       if(lookupTable.containsKey(o)){
     86          Collection<OsmPrimitive> c = lookupTable.get(o);
     87          Collection<OsmPrimitive> oldData = new HashSet<OsmPrimitive>(data);
     88          data.addAll(c);
     89          if(indirectRefs)
     90             for(OsmPrimitive oo : c)
     91                if(!oldData.contains(oo))
     92                   visit(oo);
     93       }
     94    }
     95   
    4696    public void visit(Node n) {
    47         for (Way w : ds.ways) {
    48             if (w.isDeleted() || w.incomplete) {
    49                 continue;
    50             }
    51             for (Node n2 : w.getNodes()) {
    52                 if (n == n2) {
    53                     data.add(w);
    54                     if (indirectRefs) {
    55                         visit(w);
    56                     }
    57                 }
    58             }
    59         }
    60         checkRelationMembership(n);
     97       visit((OsmPrimitive)n);
    6198    }
    6299
    63100    public void visit(Way w) {
    64         checkRelationMembership(w);
     101       visit((OsmPrimitive)w);
    65102    }
    66103
    67104    public void visit(Relation r) {
    68         checkRelationMembership(r);
    69     }
    70 
    71     private void checkRelationMembership(OsmPrimitive p) {
    72         // FIXME - this might be a candidate for optimisation
    73         // if OSM primitives are made to hold a list of back
    74         // references.
    75         for (Relation r : ds.relations) {
    76             if (r.incomplete || r.isDeleted()) {
    77                 continue;
    78             }
    79             for (RelationMember m : r.getMembers()) {
    80                 if (m.getMember() == p) {
    81                     if (!data.contains(r)) {
    82                         data.add(r);
    83                         if (indirectRefs) {
    84                             // move up the tree (there might be relations
    85                             // referring to this relation)
    86                             checkRelationMembership(r);
    87                         }
    88                     }
    89                     break;
    90                 }
    91             }
    92         }
     105       visit((OsmPrimitive)r);
    93106    }
    94107}
Note: See TracChangeset for help on using the changeset viewer.