Changeset 7138 in josm for trunk


Ignore:
Timestamp:
2014-05-18T13:20:42+02:00 (10 years ago)
Author:
bastiK
Message:

see #9691 - add tag based index (speed-up of factor 3 in single thread mode)

Location:
trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSRule.java

    r7069 r7138  
    77import org.openstreetmap.josm.tools.Utils;
    88
    9 public class MapCSSRule {
     9/**
     10 * A MapCSS rule.
     11 *
     12 * A MapCSS style is simply a list of MapCSS rules. Each rule has a selector
     13 * and a declaration. Whenever the selector matches the primitive, the
     14 * declaration block is executed for this primitive.
     15 */
     16public class MapCSSRule implements Comparable<MapCSSRule> {
    1017
    1118    public final Selector selector;
     
    4956
    5057    @Override
     58    public int compareTo(MapCSSRule o) {
     59        return declaration.idx - o.declaration.idx;
     60    }
     61
     62    @Override
    5163    public String toString() {
    5264        return selector + " {\n  " + Utils.join("\n  ", declaration.instructions) + "\n}";
  • trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSStyleSource.java

    r7125 r7138  
    1212import java.text.MessageFormat;
    1313import java.util.ArrayList;
     14import java.util.Collection;
     15import java.util.Collections;
     16import java.util.HashMap;
     17import java.util.HashSet;
    1418import java.util.List;
     19import java.util.Map;
    1520import java.util.Map.Entry;
     21import java.util.Set;
    1622import java.util.zip.ZipEntry;
    1723import java.util.zip.ZipFile;
     
    2834import org.openstreetmap.josm.gui.mappaint.Range;
    2935import org.openstreetmap.josm.gui.mappaint.StyleSource;
     36import org.openstreetmap.josm.gui.mappaint.mapcss.Condition.SimpleKeyValueCondition;
    3037import org.openstreetmap.josm.gui.mappaint.mapcss.Selector.ChildOrParentSelector;
    3138import org.openstreetmap.josm.gui.mappaint.mapcss.Selector.GeneralSelector;
     39import org.openstreetmap.josm.gui.mappaint.mapcss.Selector.OptimizedGeneralSelector;
    3240import org.openstreetmap.josm.gui.mappaint.mapcss.parsergen.MapCSSParser;
    3341import org.openstreetmap.josm.gui.mappaint.mapcss.parsergen.ParseException;
     
    4957    // all rules
    5058    public final List<MapCSSRule> rules = new ArrayList<>();
    51     // rules filtered by primitive type
    52     public final List<MapCSSRule> nodeRules = new ArrayList<>();
    53     public final List<MapCSSRule> wayRules = new ArrayList<>();
    54     public final List<MapCSSRule> relationRules = new ArrayList<>();
    55     public final List<MapCSSRule> multipolygonRules = new ArrayList<>();
    56     public final List<MapCSSRule> canvasRules = new ArrayList<>();
     59    // rule indices, filtered by primitive type
     60    public final MapCSSRuleIndex nodeRules = new MapCSSRuleIndex();
     61    public final MapCSSRuleIndex wayRules = new MapCSSRuleIndex();
     62    public final MapCSSRuleIndex relationRules = new MapCSSRuleIndex();
     63    public final MapCSSRuleIndex multipolygonRules = new MapCSSRuleIndex();
     64    public final MapCSSRuleIndex canvasRules = new MapCSSRuleIndex();
    5765
    5866    private Color backgroundColorOverride;
    5967    private String css = null;
    6068    private ZipFile zipFile;
     69
     70    /**
     71     * A collection of {@link MapCSSRule}s, that are indexed by tag key and value.
     72     *
     73     * Speeds up the process of finding all rules that match a certain primitive.
     74     *
     75     * Rules with a {@link SimpleKeyValueCondition} [key=value] are indexed by
     76     * key and value in a HashMap. Now you only need to loop the tags of a
     77     * primitive to retrieve the possibly matching rules.
     78     *
     79     * Rules with no SimpleKeyValueCondition in the selector have to be
     80     * checked separately.
     81     *
     82     * The order of rules gets mixed up by this and needs to be sorted later.
     83     */
     84    public static class MapCSSRuleIndex {
     85        /* all rules for this index */
     86        public final List<MapCSSRule> rules = new ArrayList<>();
     87        /* tag based index */
     88        public final Map<String,Map<String,Set<MapCSSRule>>> index = new HashMap<>();
     89        /* rules without SimpleKeyValueCondition */
     90        public final Set<MapCSSRule> remaining = new HashSet<>();
     91       
     92        public void add(MapCSSRule rule) {
     93            rules.add(rule);
     94        }
     95
     96        /**
     97         * Initialize the index.
     98         */
     99        public void initIndex() {
     100            for (MapCSSRule r: rules) {
     101                // find the rightmost selector, this must be a GeneralSelector
     102                Selector selRightmost = r.selector;
     103                while (selRightmost instanceof ChildOrParentSelector) {
     104                    selRightmost = ((ChildOrParentSelector) selRightmost).right;
     105                }
     106                OptimizedGeneralSelector s = (OptimizedGeneralSelector) selRightmost;
     107                if (s.conds == null) {
     108                    remaining.add(r);
     109                    continue;
     110                }
     111                List<SimpleKeyValueCondition> sk = new ArrayList<>(Utils.filteredCollection(s.conds, SimpleKeyValueCondition.class));
     112                if (sk.isEmpty()) {
     113                    remaining.add(r);
     114                    continue;
     115                }
     116                SimpleKeyValueCondition c = sk.get(sk.size() - 1);
     117                Map<String,Set<MapCSSRule>> rulesWithMatchingKey = index.get(c.k);
     118                if (rulesWithMatchingKey == null) {
     119                    rulesWithMatchingKey = new HashMap<>();
     120                    index.put(c.k, rulesWithMatchingKey);
     121                }
     122                Set<MapCSSRule> rulesWithMatchingKeyValue = rulesWithMatchingKey.get(c.v);
     123                if (rulesWithMatchingKeyValue == null) {
     124                    rulesWithMatchingKeyValue = new HashSet<>();
     125                    rulesWithMatchingKey.put(c.v, rulesWithMatchingKeyValue);
     126                }
     127                rulesWithMatchingKeyValue.add(r);
     128            }
     129        }
     130       
     131        /**
     132         * Get a subset of all rules that might match the primitive.
     133         * @param osm the primitive to match
     134         * @return a Collection of rules that filters out most of the rules
     135         * that cannot match, based on the tags of the primitive
     136         */
     137        public Collection<MapCSSRule> getRuleCandidates(OsmPrimitive osm) {
     138            List<MapCSSRule> ruleCandidates = new ArrayList<>(remaining);
     139            for (Map.Entry<String,String> e : osm.getKeys().entrySet()) {
     140                Map<String,Set<MapCSSRule>> v = index.get(e.getKey());
     141                if (v != null) {
     142                    Set<MapCSSRule> rs = v.get(e.getValue());
     143                    if (rs != null)  {
     144                        ruleCandidates.addAll(rs);
     145                    }
     146                }
     147            }
     148            Collections.sort(ruleCandidates);
     149            return ruleCandidates;
     150        }
     151
     152        public void clear() {
     153            rules.clear();
     154            index.clear();
     155            remaining.clear();
     156        }
     157    }
    61158
    62159    public MapCSSStyleSource(String url, String name, String shortdescription) {
     
    161258            }
    162259        }
    163     }
    164 
     260        nodeRules.initIndex();
     261        wayRules.initIndex();
     262        relationRules.initIndex();
     263        multipolygonRules.initIndex();
     264        canvasRules.initIndex();
     265    }
     266   
    165267    @Override
    166268    public InputStream getSourceInputStream() throws IOException {
     
    253355    public void apply(MultiCascade mc, OsmPrimitive osm, double scale, OsmPrimitive multipolyOuterWay, boolean pretendWayIsClosed) {
    254356        Environment env = new Environment(osm, mc, null, this);
    255         List<MapCSSRule> matchingRules;
     357        MapCSSRuleIndex matchingRuleIndex;
    256358        if (osm instanceof Node) {
    257             matchingRules = nodeRules;
     359            matchingRuleIndex = nodeRules;
    258360        } else if (osm instanceof Way) {
    259             matchingRules = wayRules;
     361            matchingRuleIndex = wayRules;
    260362        } else {
    261363            if (((Relation) osm).isMultipolygon()) {
    262                 matchingRules = multipolygonRules;
     364                matchingRuleIndex = multipolygonRules;
    263365            } else if (osm.hasKey("#canvas")) {
    264                 matchingRules = canvasRules;
     366                matchingRuleIndex = canvasRules;
    265367            } else {
    266                 matchingRules = relationRules;
    267             }
    268         }
    269 
     368                matchingRuleIndex = relationRules;
     369            }
     370        }
     371       
    270372        // the declaration indices are sorted, so it suffices to save the
    271373        // last used index
    272374        int lastDeclUsed = -1;
    273375
    274         for (MapCSSRule r : matchingRules) {
     376        for (MapCSSRule r : matchingRuleIndex.getRuleCandidates(osm)) {
    275377            env.clearSelectorMatchingInformation();
    276378            if (r.selector.matches(env)) { // as side effect env.parent will be set (if s is a child selector)
  • trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Selector.java

    r7055 r7138  
    3434 * The selector decides, if the declaration block gets applied or not.
    3535 *
    36  * Currently all implementing classes of Selector are immutable.
     36 * All implementing classes of Selector are immutable.
    3737 */
    3838public interface Selector {
Note: See TracChangeset for help on using the changeset viewer.