Ignore:
Timestamp:
2013-04-28T12:01:13+02:00 (12 years ago)
Author:
bastiK
Message:

applied #8643 - Very slow Purge command - O(N2) (patch by bilbo)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/command/PurgeCommand.java

    r5681 r5905  
    133133        List<OsmPrimitive> out = new ArrayList<OsmPrimitive>(in.size());
    134134
     135        // Nodes not deleted in the first pass
     136        Set<OsmPrimitive> remainingNodes = new HashSet<OsmPrimitive>(in.size());
     137
    135138        /**
    136139         *  First add nodes that have no way referrer.
     
    143146                    for (OsmPrimitive ref : n.getReferrers()) {
    144147                        if (ref instanceof Way && in.contains(ref)) {
     148                            it.remove();
     149                            remainingNodes.add(n);
    145150                            continue outer;
    146151                        }
     
    154159         * Then add all ways, each preceded by its (remaining) nodes.
    155160         */
    156         top: while (!in.isEmpty()) {
    157             for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
    158                 OsmPrimitive u = it.next();
    159                 if (u instanceof Way) {
    160                     Way w = (Way) u;
    161                     it.remove();
    162                     for (Node n : w.getNodes()) {
    163                         if (in.contains(n)) {
    164                             in.remove(n);
    165                             out.add(n);
    166                         }
    167                     }
    168                     out.add(w);
    169                     continue top;
    170                 }
    171             }
    172             break; // no more ways left
    173         }
     161        for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
     162            OsmPrimitive u = it.next();
     163            if (u instanceof Way) {
     164                Way w = (Way) u;
     165                it.remove();
     166                for (Node n : w.getNodes()) {
     167                    if (remainingNodes.contains(n)) {
     168                        remainingNodes.remove(n);
     169                        out.add(n);
     170                    }
     171                }
     172                out.add(w);
     173            }
     174        }
     175
     176        if (!remainingNodes.isEmpty())
     177            throw new AssertionError("topo sort algorithm failed (nodes remaining)");
    174178
    175179        /**
Note: See TracChangeset for help on using the changeset viewer.