Index: trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSRule.java =================================================================== --- trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSRule.java (revision 7137) +++ trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSRule.java (revision 7138) @@ -7,5 +7,12 @@ import org.openstreetmap.josm.tools.Utils; -public class MapCSSRule { +/** + * A MapCSS rule. + * + * A MapCSS style is simply a list of MapCSS rules. Each rule has a selector + * and a declaration. Whenever the selector matches the primitive, the + * declaration block is executed for this primitive. + */ +public class MapCSSRule implements Comparable { public final Selector selector; @@ -49,4 +56,9 @@ @Override + public int compareTo(MapCSSRule o) { + return declaration.idx - o.declaration.idx; + } + + @Override public String toString() { return selector + " {\n " + Utils.join("\n ", declaration.instructions) + "\n}"; Index: trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSStyleSource.java =================================================================== --- trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSStyleSource.java (revision 7137) +++ trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSStyleSource.java (revision 7138) @@ -12,6 +12,12 @@ import java.text.MessageFormat; import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.HashMap; +import java.util.HashSet; import java.util.List; +import java.util.Map; import java.util.Map.Entry; +import java.util.Set; import java.util.zip.ZipEntry; import java.util.zip.ZipFile; @@ -28,6 +34,8 @@ import org.openstreetmap.josm.gui.mappaint.Range; import org.openstreetmap.josm.gui.mappaint.StyleSource; +import org.openstreetmap.josm.gui.mappaint.mapcss.Condition.SimpleKeyValueCondition; import org.openstreetmap.josm.gui.mappaint.mapcss.Selector.ChildOrParentSelector; import org.openstreetmap.josm.gui.mappaint.mapcss.Selector.GeneralSelector; +import org.openstreetmap.josm.gui.mappaint.mapcss.Selector.OptimizedGeneralSelector; import org.openstreetmap.josm.gui.mappaint.mapcss.parsergen.MapCSSParser; import org.openstreetmap.josm.gui.mappaint.mapcss.parsergen.ParseException; @@ -49,14 +57,103 @@ // all rules public final List rules = new ArrayList<>(); - // rules filtered by primitive type - public final List nodeRules = new ArrayList<>(); - public final List wayRules = new ArrayList<>(); - public final List relationRules = new ArrayList<>(); - public final List multipolygonRules = new ArrayList<>(); - public final List canvasRules = new ArrayList<>(); + // rule indices, filtered by primitive type + public final MapCSSRuleIndex nodeRules = new MapCSSRuleIndex(); + public final MapCSSRuleIndex wayRules = new MapCSSRuleIndex(); + public final MapCSSRuleIndex relationRules = new MapCSSRuleIndex(); + public final MapCSSRuleIndex multipolygonRules = new MapCSSRuleIndex(); + public final MapCSSRuleIndex canvasRules = new MapCSSRuleIndex(); private Color backgroundColorOverride; private String css = null; private ZipFile zipFile; + + /** + * A collection of {@link MapCSSRule}s, that are indexed by tag key and value. + * + * Speeds up the process of finding all rules that match a certain primitive. + * + * Rules with a {@link SimpleKeyValueCondition} [key=value] are indexed by + * key and value in a HashMap. Now you only need to loop the tags of a + * primitive to retrieve the possibly matching rules. + * + * Rules with no SimpleKeyValueCondition in the selector have to be + * checked separately. + * + * The order of rules gets mixed up by this and needs to be sorted later. + */ + public static class MapCSSRuleIndex { + /* all rules for this index */ + public final List rules = new ArrayList<>(); + /* tag based index */ + public final Map>> index = new HashMap<>(); + /* rules without SimpleKeyValueCondition */ + public final Set remaining = new HashSet<>(); + + public void add(MapCSSRule rule) { + rules.add(rule); + } + + /** + * Initialize the index. + */ + public void initIndex() { + for (MapCSSRule r: rules) { + // find the rightmost selector, this must be a GeneralSelector + Selector selRightmost = r.selector; + while (selRightmost instanceof ChildOrParentSelector) { + selRightmost = ((ChildOrParentSelector) selRightmost).right; + } + OptimizedGeneralSelector s = (OptimizedGeneralSelector) selRightmost; + if (s.conds == null) { + remaining.add(r); + continue; + } + List sk = new ArrayList<>(Utils.filteredCollection(s.conds, SimpleKeyValueCondition.class)); + if (sk.isEmpty()) { + remaining.add(r); + continue; + } + SimpleKeyValueCondition c = sk.get(sk.size() - 1); + Map> rulesWithMatchingKey = index.get(c.k); + if (rulesWithMatchingKey == null) { + rulesWithMatchingKey = new HashMap<>(); + index.put(c.k, rulesWithMatchingKey); + } + Set rulesWithMatchingKeyValue = rulesWithMatchingKey.get(c.v); + if (rulesWithMatchingKeyValue == null) { + rulesWithMatchingKeyValue = new HashSet<>(); + rulesWithMatchingKey.put(c.v, rulesWithMatchingKeyValue); + } + rulesWithMatchingKeyValue.add(r); + } + } + + /** + * Get a subset of all rules that might match the primitive. + * @param osm the primitive to match + * @return a Collection of rules that filters out most of the rules + * that cannot match, based on the tags of the primitive + */ + public Collection getRuleCandidates(OsmPrimitive osm) { + List ruleCandidates = new ArrayList<>(remaining); + for (Map.Entry e : osm.getKeys().entrySet()) { + Map> v = index.get(e.getKey()); + if (v != null) { + Set rs = v.get(e.getValue()); + if (rs != null) { + ruleCandidates.addAll(rs); + } + } + } + Collections.sort(ruleCandidates); + return ruleCandidates; + } + + public void clear() { + rules.clear(); + index.clear(); + remaining.clear(); + } + } public MapCSSStyleSource(String url, String name, String shortdescription) { @@ -161,6 +258,11 @@ } } - } - + nodeRules.initIndex(); + wayRules.initIndex(); + relationRules.initIndex(); + multipolygonRules.initIndex(); + canvasRules.initIndex(); + } + @Override public InputStream getSourceInputStream() throws IOException { @@ -253,24 +355,24 @@ public void apply(MultiCascade mc, OsmPrimitive osm, double scale, OsmPrimitive multipolyOuterWay, boolean pretendWayIsClosed) { Environment env = new Environment(osm, mc, null, this); - List matchingRules; + MapCSSRuleIndex matchingRuleIndex; if (osm instanceof Node) { - matchingRules = nodeRules; + matchingRuleIndex = nodeRules; } else if (osm instanceof Way) { - matchingRules = wayRules; + matchingRuleIndex = wayRules; } else { if (((Relation) osm).isMultipolygon()) { - matchingRules = multipolygonRules; + matchingRuleIndex = multipolygonRules; } else if (osm.hasKey("#canvas")) { - matchingRules = canvasRules; + matchingRuleIndex = canvasRules; } else { - matchingRules = relationRules; - } - } - + matchingRuleIndex = relationRules; + } + } + // the declaration indices are sorted, so it suffices to save the // last used index int lastDeclUsed = -1; - for (MapCSSRule r : matchingRules) { + for (MapCSSRule r : matchingRuleIndex.getRuleCandidates(osm)) { env.clearSelectorMatchingInformation(); if (r.selector.matches(env)) { // as side effect env.parent will be set (if s is a child selector) Index: trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Selector.java =================================================================== --- trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Selector.java (revision 7137) +++ trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Selector.java (revision 7138) @@ -34,5 +34,5 @@ * The selector decides, if the declaration block gets applied or not. * - * Currently all implementing classes of Selector are immutable. + * All implementing classes of Selector are immutable. */ public interface Selector {