Changeset 18977 in josm for trunk


Ignore:
Timestamp:
2024-02-13T15:58:15+01:00 (9 months ago)
Author:
taylor.smock
Message:

See #23468: Improve performance in the validator tree window

This fixes an issue where there was a difference in sorting algorithms between
the faster ASCII only sorting method and the sorting method used by non-ASCII
strings.

Location:
trunk
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/org/openstreetmap/josm/tools/AlphanumComparator.java

    r18973 r18977  
    3333import java.io.Serializable;
    3434import java.text.Collator;
     35import java.util.Arrays;
    3536import java.util.Comparator;
    3637
    … …  
    3940 * containing numbers: Instead of sorting numbers in ASCII order like a standard
    4041 * sort, this algorithm sorts numbers in numeric order.
    41  *
    42  * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
    43  *
     42 * <p>
     43 * The Alphanum Algorithm is discussed at
     44 * <a href="https://web.archive.org/web/20210602024123/http://www.davekoelle.com/alphanum.html">DaveKoelle.com</a>
     45 * <p>
    4446 * This is an updated version with enhancements made by Daniel Migowski, Andre
    4547 * Bogus, David Koelle and others.
    … …  
    5153
    5254    private static final AlphanumComparator INSTANCE = new AlphanumComparator();
     55    /**
     56     * A mapping from ASCII characters to the default {@link Collator} order.
     57     * At writing, the default rules can be found in {@link sun.util.locale.provider.CollationRules#DEFAULTRULES}.
     58     */
     59    private static final byte[] ASCII_MAPPING = new byte[128];
     60    static {
     61        for (int i = 0; i < ASCII_MAPPING.length; i++) {
     62            ASCII_MAPPING[i] = (byte) i; // This is kind of pointless, but it is the default ASCII ordering.
     63        }
     64        // The control characters are "ignored"
     65        Arrays.fill(ASCII_MAPPING, 0, 32, (byte) 0);
     66        ASCII_MAPPING[127] = 0; // DEL is ignored.
     67        // We have 37 order overrides for symbols; ASCII tables has control characters through 31. 32-47 are symbols.
     68        // After the symbols, we have 0-9, and then aA-zZ.
     69        // The character order
     70        final String order = " \r\t\n\f\u000b_,;:!?/.`^~'\"()[]{}@$*\\&#%+<=>|0123456789aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";
     71        for (int i = 0; i < order.length(); i++) {
     72            char c = order.charAt(i);
     73            ASCII_MAPPING[c] = (byte) (i + 1);
     74        }
     75    }
    5376
    5477    /**
    … …  
    6487     */
    6588    private AlphanumComparator() {
     89    }
     90
     91    /**
     92     * Compare two ASCII strings in a manner compatible with the default {@link Collator}
     93     * @param string1 The first string to compare
     94     * @param len1 The length of the first string
     95     * @param string2 The second string to compare
     96     * @param len2 The length of the second string
     97     * @return See {@link String#compareToIgnoreCase(String)} (e.g. {@code string1.compareToIgnoreCase(string2)}).
     98     */
     99    private static int compareString(String string1, int len1, String string2, int len2) {
     100        int lim = Math.min(len1, len2);
     101        int k = 0;
     102        while (k < lim) {
     103            final int c1 = ASCII_MAPPING[string1.charAt(k)];
     104            final int c2 = ASCII_MAPPING[string2.charAt(k)];
     105            if (c1 != c2) {
     106                return c1 - c2;
     107            }
     108            k++;
     109        }
     110        return len1 - len2;
    66111    }
    67112
    … …  
    107152        for (int i = 0; i < stringLength; i++) {
    108153            char c = string.charAt(i);
    109             if (c >= 128) {
     154            if (c > ASCII_MAPPING.length) {
    110155                return false;
    111156            }
    … …  
    139184            // Check if both chunks are ascii only
    140185            if (isAscii(thisChunk, thisChunkLength) && isAscii(thatChunk, thatChunkLength)) {
    141                 return thisChunk.compareTo(thatChunk);
     186                return Utils.clamp(compareString(thisChunk, thisChunkLength, thatChunk, thatChunkLength), -1, 1);
    142187            }
    143188            // Instantiate the collator

  • trunk/test/unit/org/openstreetmap/josm/data/osm/DefaultNameFormatterTest.java

    r18106 r18977  
    7979
    8080            // CHECKSTYLE.OFF: SingleSpaceSeparator
    81             assertEquals(comparator.compare(p1, p2), -1); // p1 < p2
    82             assertEquals(comparator.compare(p2, p1),  1); // p2 > p1
     81            assertEquals(-1, comparator.compare(p1, p2)); // p1 < p2
     82            assertEquals(1,  comparator.compare(p2, p1)); // p2 > p1
    8383
    84             assertEquals(comparator.compare(p1, p3), -1); // p1 < p3
    85             assertEquals(comparator.compare(p3, p1),  1); // p3 > p1
    86             assertEquals(comparator.compare(p2, p3),  1); // p2 > p3
    87             assertEquals(comparator.compare(p3, p2), -1); // p3 < p2
     84            assertEquals(-1, comparator.compare(p1, p3)); // p1 < p3
     85            assertEquals(1,  comparator.compare(p3, p1)); // p3 > p1
     86            assertEquals(1,  comparator.compare(p2, p3)); // p2 > p3
     87            assertEquals(-1, comparator.compare(p3, p2)); // p3 < p2
    8888            // CHECKSTYLE.ON: SingleSpaceSeparator
    8989
Note: See TracChangeset for help on using the changeset viewer.