Changeset 6609 in josm

Timestamp:

2014-01-03T12:30:28+01:00 (10 years ago)

Author:

simon04

Message:

see #9516 - MapCSS: greatly improve performance of spatial "element of" (was: "contains") expression

The current syntax is inner ∈ outer.

The order plus symbol has been changed since now the left side is matched in the end.

Location:

trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss

Files:

• MapCSSParser.jj (modified) (2 diffs)
• Selector.java (modified) (8 diffs)

trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSParser.jj

@@ -80 +80 @@
 |   < CARET: "^" >
 |   < FULLSTOP: "." >
-|   < CONTAINS: "∋" >
+|   < ELEMENT_OF: "∈" >
 |   < COMMENT_START: "/*" > : COMMENT
 |   < UNEXPECTED_CHAR : ~[] > // avoid TokenMgrErrors because they are hard to recover from
@@ -277 +277 @@
             ( ( c=condition(Context.LINK) | c=class_or_pseudoclass(Context.LINK) ) { conditions.add(c); } )*
         |
-            <CONTAINS> { type = Selector.ChildOrParentSelectorType.CONTAINS; }
+            <ELEMENT_OF> { type = Selector.ChildOrParentSelectorType.ELEMENT_OF; }
         )
         { selLink = new LinkSelector(conditions); }

trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Selector.java

@@ -2 +2 @@
 package org.openstreetmap.josm.gui.mappaint.mapcss;
 
+import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
@@ -9 +10 @@
 import org.openstreetmap.josm.data.osm.Node;
 import org.openstreetmap.josm.data.osm.OsmPrimitive;
+import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
 import org.openstreetmap.josm.data.osm.Relation;
 import org.openstreetmap.josm.data.osm.RelationMember;
@@ -15 +17 @@
 import org.openstreetmap.josm.gui.mappaint.Environment;
 import org.openstreetmap.josm.gui.mappaint.Range;
+import org.openstreetmap.josm.tools.CheckParameterUtil;
 import org.openstreetmap.josm.tools.Geometry;
 import org.openstreetmap.josm.tools.Pair;
@@ -36 +39 @@
 
     public static enum ChildOrParentSelectorType {
-        CHILD, PARENT, CONTAINS
+        CHILD, PARENT, ELEMENT_OF
     }
 
@@ -149 +152 @@
         private class ContainsFinder extends AbstractVisitor {
             private final Environment e;
-            private final List<Node> nodes;
 
             private ContainsFinder(Environment e) {
                 this.e = e;
-                if (e.osm instanceof Node) {
-                    nodes = Collections.singletonList((Node) e.osm);
-                } else if (e.osm instanceof Way) {
-                    nodes = ((Way) e.osm).getNodes();
-                } else {
-                    throw new IllegalArgumentException("Relations not supported");
-                }
+                CheckParameterUtil.ensureThat(!(e.osm instanceof Node), "Nodes not supported");
             }
 
             @Override
             public void visit(Node n) {
+                if (e.parent == null && right.matches(e.withPrimitive(n))) {
+                    if (e.osm instanceof Way && Geometry.nodeInsidePolygon(n, ((Way) e.osm).getNodes())
+                            || e.osm instanceof Relation && ((Relation) e.osm).isMultipolygon() && Geometry.isNodeInsideMultiPolygon(n, (Relation) e.osm, null)) {
+                        e.parent = n;
+                    }
+                }
             }
 
             @Override
             public void visit(Way w) {
-                if (e.parent == null && left.matches(e.withPrimitive(w))) {
-                    if (nodes.size() == 1
-                            ? Geometry.nodeInsidePolygon(nodes.get(0), w.getNodes())
-                            : Geometry.PolygonIntersection.FIRST_INSIDE_SECOND.equals(Geometry.polygonIntersection(nodes, w.getNodes()))) {
+                if (e.parent == null && right.matches(e.withPrimitive(w))) {
+                    if (e.osm instanceof Way && Geometry.PolygonIntersection.FIRST_INSIDE_SECOND.equals(Geometry.polygonIntersection(w.getNodes(), ((Way) e.osm).getNodes()))
+                            || e.osm instanceof Relation && ((Relation) e.osm).isMultipolygon() && Geometry.isPolygonInsideMultiPolygon(w.getNodes(), (Relation) e.osm, null)) {
                         e.parent = w;
-                        e.index = 0;
                     }
                 }
@@ -180 +180 @@
             @Override
             public void visit(Relation r) {
-                if (e.parent == null && left.matches(e.withPrimitive(r))) {
-                    if (r.isMultipolygon() && Geometry.isPolygonInsideMultiPolygon(nodes, r, null)) {
-                        e.parent = r;
-                        e.index = 0;
+            }
+
+            public void visit(Collection<? extends OsmPrimitive> primitives) {
+                for (OsmPrimitive p : primitives) {
+                    if (e.parent != null) {
+                        // abort if first match has been found
+                        break;
+                    } else if (!e.osm.equals(p)) {
+                        p.accept(this);
                     }
                 }
@@ -191 +196 @@
         @Override
         public boolean matches(Environment e) {
+
             if (!right.matches(e))
                 return false;
 
-            if (ChildOrParentSelectorType.CONTAINS.equals(type)) {
-                final OsmPrimitive rightPrimitive = e.osm;
+            if (ChildOrParentSelectorType.ELEMENT_OF.equals(type)) {
+
+                if (e.osm instanceof Node) {
+                    // nodes cannot contain elements
+                    return false;
+                }
+                e.child = e.osm;
+
                 final ContainsFinder containsFinder = new ContainsFinder(e);
-                for (final OsmPrimitive p : rightPrimitive.getDataSet().allPrimitives()) {
-                    if (rightPrimitive.equals(p)) {
-                        continue;
-                    }
-                    p.accept(containsFinder);
-                    if (e.parent != null) {
-                        e.osm = rightPrimitive;
-                        return true;
-                    }
-                }
+                if (right instanceof GeneralSelector) {
+                    if (((GeneralSelector) right).matchesBase(OsmPrimitiveType.NODE)) {
+                        containsFinder.visit(e.osm.getDataSet().searchNodes(e.osm.getBBox()));
+                    }
+                    if (((GeneralSelector) right).matchesBase(OsmPrimitiveType.WAY)) {
+                        containsFinder.visit(e.osm.getDataSet().searchWays(e.osm.getBBox()));
+                    }
+                } else {
+                    // use slow test
+                    containsFinder.visit(e.osm.getDataSet().allPrimitives());
+                }
+
+                return e.parent != null;
+
             } else if (ChildOrParentSelectorType.CHILD.equals(type)) {
                 MatchingReferrerFinder collector = new MatchingReferrerFinder(e);
@@ -357 +373 @@
         }
 
-        public boolean matchesBase(Environment e){
-            if (e.osm instanceof Node) {
+        public boolean matchesBase(OsmPrimitiveType type) {
+            if (OsmPrimitiveType.NODE.equals(type)) {
                 return base.equals("node") || base.equals("*");
-            } else if (e.osm instanceof Way) {
+            } else if (OsmPrimitiveType.WAY.equals(type)) {
                 return base.equals("way") || base.equals("area") || base.equals("*");
-            } else if (e.osm instanceof Relation) {
-                if (base.equals("area")) {
-                    return ((Relation) e.osm).isMultipolygon();
-                } else if (base.equals("relation")) {
-                    return true;
-                } else if (base.equals("canvas")) {
-                    return e.osm.get("#canvas") != null;
-                }
+            } else if (OsmPrimitiveType.RELATION.equals(type)) {
+                return base.equals("area") || base.equals("relation") || base.equals("canvas");
             }
             return false;
+        }
+
+        public boolean matchesBase(OsmPrimitive p) {
+            if (!matchesBase(p.getType())) {
+                return false;
+            } else {
+                if (p instanceof Relation) {
+                    if (base.equals("area")) {
+                        return ((Relation) p).isMultipolygon();
+                    } else if (base.equals("canvas")) {
+                        return p.get("#canvas") != null;
+                    }
+                }
+                return true;
+            }
+        }
+
+        public boolean matchesBase(Environment e) {
+            return matchesBase(e.osm);
         }