001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.tools;
003
004import static org.openstreetmap.josm.tools.I18n.marktr;
005import static org.openstreetmap.josm.tools.I18n.tr;
006import static org.openstreetmap.josm.tools.I18n.trn;
007
008import java.awt.Color;
009import java.awt.Font;
010import java.awt.HeadlessException;
011import java.awt.Toolkit;
012import java.awt.datatransfer.Clipboard;
013import java.awt.datatransfer.ClipboardOwner;
014import java.awt.datatransfer.DataFlavor;
015import java.awt.datatransfer.StringSelection;
016import java.awt.datatransfer.Transferable;
017import java.awt.datatransfer.UnsupportedFlavorException;
018import java.awt.font.FontRenderContext;
019import java.awt.font.GlyphVector;
020import java.io.BufferedReader;
021import java.io.ByteArrayOutputStream;
022import java.io.Closeable;
023import java.io.File;
024import java.io.IOException;
025import java.io.InputStream;
026import java.io.InputStreamReader;
027import java.io.UnsupportedEncodingException;
028import java.lang.reflect.AccessibleObject;
029import java.net.MalformedURLException;
030import java.net.URL;
031import java.net.URLDecoder;
032import java.net.URLEncoder;
033import java.nio.charset.StandardCharsets;
034import java.nio.file.Files;
035import java.nio.file.Path;
036import java.nio.file.StandardCopyOption;
037import java.security.AccessController;
038import java.security.MessageDigest;
039import java.security.NoSuchAlgorithmException;
040import java.security.PrivilegedAction;
041import java.text.Bidi;
042import java.text.MessageFormat;
043import java.util.AbstractCollection;
044import java.util.AbstractList;
045import java.util.ArrayList;
046import java.util.Arrays;
047import java.util.Collection;
048import java.util.Collections;
049import java.util.Iterator;
050import java.util.List;
051import java.util.Locale;
052import java.util.Objects;
053import java.util.concurrent.Executor;
054import java.util.concurrent.ForkJoinPool;
055import java.util.concurrent.ForkJoinWorkerThread;
056import java.util.concurrent.ThreadFactory;
057import java.util.concurrent.atomic.AtomicLong;
058import java.util.regex.Matcher;
059import java.util.regex.Pattern;
060import java.util.zip.GZIPInputStream;
061import java.util.zip.ZipEntry;
062import java.util.zip.ZipFile;
063import java.util.zip.ZipInputStream;
064
065import javax.xml.XMLConstants;
066import javax.xml.parsers.DocumentBuilder;
067import javax.xml.parsers.DocumentBuilderFactory;
068import javax.xml.parsers.ParserConfigurationException;
069import javax.xml.parsers.SAXParser;
070import javax.xml.parsers.SAXParserFactory;
071
072import org.apache.commons.compress.compressors.bzip2.BZip2CompressorInputStream;
073import org.openstreetmap.josm.Main;
074import org.w3c.dom.Document;
075import org.xml.sax.InputSource;
076import org.xml.sax.SAXException;
077import org.xml.sax.helpers.DefaultHandler;
078
079/**
080 * Basic utils, that can be useful in different parts of the program.
081 */
082public final class Utils {
083
084    /** Pattern matching white spaces */
085    public static final Pattern WHITE_SPACES_PATTERN = Pattern.compile("\\s+");
086
087    private static final int MILLIS_OF_SECOND = 1000;
088    private static final int MILLIS_OF_MINUTE = 60000;
089    private static final int MILLIS_OF_HOUR = 3600000;
090    private static final int MILLIS_OF_DAY = 86400000;
091
092    /**
093     * A list of all characters allowed in URLs
094     */
095    public static final String URL_CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-._~:/?#[]@!$&'()*+,;=%";
096
097    private static final char[] DEFAULT_STRIP = {'\u200B', '\uFEFF'};
098
099    private static final String[] SIZE_UNITS = {"B", "kB", "MB", "GB", "TB", "PB", "EB", "ZB", "YB"};
100
101    private Utils() {
102        // Hide default constructor for utils classes
103    }
104
105    /**
106     * Tests whether {@code predicate} applies to at least one element from {@code collection}.
107     * @param <T> type of items
108     * @param collection the collection
109     * @param predicate the predicate
110     * @return {@code true} if {@code predicate} applies to at least one element from {@code collection}
111     */
112    public static <T> boolean exists(Iterable<? extends T> collection, Predicate<? super T> predicate) {
113        for (T item : collection) {
114            if (predicate.evaluate(item)) {
115                return true;
116            }
117        }
118        return false;
119    }
120
121    /**
122     * Tests whether {@code predicate} applies to all elements from {@code collection}.
123     * @param <T> type of items
124     * @param collection the collection
125     * @param predicate the predicate
126     * @return {@code true} if {@code predicate} applies to all elements from {@code collection}
127     */
128    public static <T> boolean forAll(Iterable<? extends T> collection, Predicate<? super T> predicate) {
129        return !exists(collection, Predicates.not(predicate));
130    }
131
132    /**
133     * Checks if an item that is an instance of clazz exists in the collection
134     * @param <T> The collection type.
135     * @param collection The collection
136     * @param clazz The class to search for.
137     * @return <code>true</code> if that item exists in the collection.
138     */
139    public static <T> boolean exists(Iterable<T> collection, Class<? extends T> clazz) {
140        return exists(collection, Predicates.<T>isInstanceOf(clazz));
141    }
142
143    /**
144     * Finds the first item in the iterable for which the predicate matches.
145     * @param <T> The iterable type.
146     * @param collection The iterable to search in.
147     * @param predicate The predicate to match
148     * @return the item or <code>null</code> if there was not match.
149     */
150    public static <T> T find(Iterable<? extends T> collection, Predicate<? super T> predicate) {
151        for (T item : collection) {
152            if (predicate.evaluate(item)) {
153                return item;
154            }
155        }
156        return null;
157    }
158
159    /**
160     * Finds the first item in the iterable which is of the given type.
161     * @param <T> The iterable type.
162     * @param collection The iterable to search in.
163     * @param clazz The class to search for.
164     * @return the item or <code>null</code> if there was not match.
165     */
166    @SuppressWarnings("unchecked")
167    public static <T> T find(Iterable<? extends Object> collection, Class<? extends T> clazz) {
168        return (T) find(collection, Predicates.<Object>isInstanceOf(clazz));
169    }
170
171    /**
172     * Creates a new {@link FilteredCollection}.
173     * @param <T> The collection type.
174     * @param collection The collection to filter.
175     * @param predicate The predicate to filter for.
176     * @return The new {@link FilteredCollection}
177     */
178    @SuppressWarnings("unused")
179    public static <T> Collection<T> filter(Collection<? extends T> collection, Predicate<? super T> predicate) {
180        // Diamond operator does not work with Java 9 here
181        return new FilteredCollection<T>(collection, predicate);
182    }
183
184    /**
185     * Returns the first element from {@code items} which is non-null, or null if all elements are null.
186     * @param <T> type of items
187     * @param items the items to look for
188     * @return first non-null item if there is one
189     */
190    @SafeVarargs
191    public static <T> T firstNonNull(T... items) {
192        for (T i : items) {
193            if (i != null) {
194                return i;
195            }
196        }
197        return null;
198    }
199
200    /**
201     * Filter a collection by (sub)class.
202     * This is an efficient read-only implementation.
203     * @param <S> Super type of items
204     * @param <T> type of items
205     * @param collection the collection
206     * @param clazz the (sub)class
207     * @return a read-only filtered collection
208     */
209    public static <S, T extends S> SubclassFilteredCollection<S, T> filteredCollection(Collection<S> collection, final Class<T> clazz) {
210        return new SubclassFilteredCollection<>(collection, Predicates.<S>isInstanceOf(clazz));
211    }
212
213    /**
214     * Find the index of the first item that matches the predicate.
215     * @param <T> The iterable type
216     * @param collection The iterable to iterate over.
217     * @param predicate The predicate to search for.
218     * @return The index of the first item or -1 if none was found.
219     */
220    public static <T> int indexOf(Iterable<? extends T> collection, Predicate<? super T> predicate) {
221        int i = 0;
222        for (T item : collection) {
223            if (predicate.evaluate(item))
224                return i;
225            i++;
226        }
227        return -1;
228    }
229
230    /**
231     * Returns the minimum of three values.
232     * @param   a   an argument.
233     * @param   b   another argument.
234     * @param   c   another argument.
235     * @return  the smaller of {@code a}, {@code b} and {@code c}.
236     */
237    public static int min(int a, int b, int c) {
238        if (b < c) {
239            if (a < b)
240                return a;
241            return b;
242        } else {
243            if (a < c)
244                return a;
245            return c;
246        }
247    }
248
249    /**
250     * Returns the greater of four {@code int} values. That is, the
251     * result is the argument closer to the value of
252     * {@link Integer#MAX_VALUE}. If the arguments have the same value,
253     * the result is that same value.
254     *
255     * @param   a   an argument.
256     * @param   b   another argument.
257     * @param   c   another argument.
258     * @param   d   another argument.
259     * @return  the larger of {@code a}, {@code b}, {@code c} and {@code d}.
260     */
261    public static int max(int a, int b, int c, int d) {
262        return Math.max(Math.max(a, b), Math.max(c, d));
263    }
264
265    /**
266     * Ensures a logical condition is met. Otherwise throws an assertion error.
267     * @param condition the condition to be met
268     * @param message Formatted error message to raise if condition is not met
269     * @param data Message parameters, optional
270     * @throws AssertionError if the condition is not met
271     */
272    public static void ensure(boolean condition, String message, Object...data) {
273        if (!condition)
274            throw new AssertionError(
275                    MessageFormat.format(message, data)
276            );
277    }
278
279    /**
280     * Return the modulus in the range [0, n)
281     * @param a dividend
282     * @param n divisor
283     * @return modulo (remainder of the Euclidian division of a by n)
284     */
285    public static int mod(int a, int n) {
286        if (n <= 0)
287            throw new IllegalArgumentException("n must be <= 0 but is "+n);
288        int res = a % n;
289        if (res < 0) {
290            res += n;
291        }
292        return res;
293    }
294
295    /**
296     * Joins a list of strings (or objects that can be converted to string via
297     * Object.toString()) into a single string with fields separated by sep.
298     * @param sep the separator
299     * @param values collection of objects, null is converted to the
300     *  empty string
301     * @return null if values is null. The joined string otherwise.
302     */
303    public static String join(String sep, Collection<?> values) {
304        CheckParameterUtil.ensureParameterNotNull(sep, "sep");
305        if (values == null)
306            return null;
307        StringBuilder s = null;
308        for (Object a : values) {
309            if (a == null) {
310                a = "";
311            }
312            if (s != null) {
313                s.append(sep).append(a);
314            } else {
315                s = new StringBuilder(a.toString());
316            }
317        }
318        return s != null ? s.toString() : "";
319    }
320
321    /**
322     * Converts the given iterable collection as an unordered HTML list.
323     * @param values The iterable collection
324     * @return An unordered HTML list
325     */
326    public static String joinAsHtmlUnorderedList(Iterable<?> values) {
327        StringBuilder sb = new StringBuilder(1024);
328        sb.append("<ul>");
329        for (Object i : values) {
330            sb.append("<li>").append(i).append("</li>");
331        }
332        sb.append("</ul>");
333        return sb.toString();
334    }
335
336    /**
337     * convert Color to String
338     * (Color.toString() omits alpha value)
339     * @param c the color
340     * @return the String representation, including alpha
341     */
342    public static String toString(Color c) {
343        if (c == null)
344            return "null";
345        if (c.getAlpha() == 255)
346            return String.format("#%06x", c.getRGB() & 0x00ffffff);
347        else
348            return String.format("#%06x(alpha=%d)", c.getRGB() & 0x00ffffff, c.getAlpha());
349    }
350
351    /**
352     * convert float range 0 &lt;= x &lt;= 1 to integer range 0..255
353     * when dealing with colors and color alpha value
354     * @param val float value between 0 and 1
355     * @return null if val is null, the corresponding int if val is in the
356     *         range 0...1. If val is outside that range, return 255
357     */
358    public static Integer color_float2int(Float val) {
359        if (val == null)
360            return null;
361        if (val < 0 || val > 1)
362            return 255;
363        return (int) (255f * val + 0.5f);
364    }
365
366    /**
367     * convert integer range 0..255 to float range 0 &lt;= x &lt;= 1
368     * when dealing with colors and color alpha value
369     * @param val integer value
370     * @return corresponding float value in range 0 &lt;= x &lt;= 1
371     */
372    public static Float color_int2float(Integer val) {
373        if (val == null)
374            return null;
375        if (val < 0 || val > 255)
376            return 1f;
377        return ((float) val) / 255f;
378    }
379
380    /**
381     * Returns the complementary color of {@code clr}.
382     * @param clr the color to complement
383     * @return the complementary color of {@code clr}
384     */
385    public static Color complement(Color clr) {
386        return new Color(255 - clr.getRed(), 255 - clr.getGreen(), 255 - clr.getBlue(), clr.getAlpha());
387    }
388
389    /**
390     * Copies the given array. Unlike {@link Arrays#copyOf}, this method is null-safe.
391     * @param <T> type of items
392     * @param array The array to copy
393     * @return A copy of the original array, or {@code null} if {@code array} is null
394     * @since 6221
395     */
396    public static <T> T[] copyArray(T[] array) {
397        if (array != null) {
398            return Arrays.copyOf(array, array.length);
399        }
400        return array;
401    }
402
403    /**
404     * Copies the given array. Unlike {@link Arrays#copyOf}, this method is null-safe.
405     * @param array The array to copy
406     * @return A copy of the original array, or {@code null} if {@code array} is null
407     * @since 6222
408     */
409    public static char[] copyArray(char[] array) {
410        if (array != null) {
411            return Arrays.copyOf(array, array.length);
412        }
413        return array;
414    }
415
416    /**
417     * Copies the given array. Unlike {@link Arrays#copyOf}, this method is null-safe.
418     * @param array The array to copy
419     * @return A copy of the original array, or {@code null} if {@code array} is null
420     * @since 7436
421     */
422    public static int[] copyArray(int[] array) {
423        if (array != null) {
424            return Arrays.copyOf(array, array.length);
425        }
426        return array;
427    }
428
429    /**
430     * Simple file copy function that will overwrite the target file.
431     * @param in The source file
432     * @param out The destination file
433     * @return the path to the target file
434     * @throws IOException if any I/O error occurs
435     * @throws IllegalArgumentException if {@code in} or {@code out} is {@code null}
436     * @since 7003
437     */
438    public static Path copyFile(File in, File out) throws IOException {
439        CheckParameterUtil.ensureParameterNotNull(in, "in");
440        CheckParameterUtil.ensureParameterNotNull(out, "out");
441        return Files.copy(in.toPath(), out.toPath(), StandardCopyOption.REPLACE_EXISTING);
442    }
443
444    /**
445     * Recursive directory copy function
446     * @param in The source directory
447     * @param out The destination directory
448     * @throws IOException if any I/O error ooccurs
449     * @throws IllegalArgumentException if {@code in} or {@code out} is {@code null}
450     * @since 7835
451     */
452    public static void copyDirectory(File in, File out) throws IOException {
453        CheckParameterUtil.ensureParameterNotNull(in, "in");
454        CheckParameterUtil.ensureParameterNotNull(out, "out");
455        if (!out.exists() && !out.mkdirs()) {
456            Main.warn("Unable to create directory "+out.getPath());
457        }
458        File[] files = in.listFiles();
459        if (files != null) {
460            for (File f : files) {
461                File target = new File(out, f.getName());
462                if (f.isDirectory()) {
463                    copyDirectory(f, target);
464                } else {
465                    copyFile(f, target);
466                }
467            }
468        }
469    }
470
471    /**
472     * Deletes a directory recursively.
473     * @param path The directory to delete
474     * @return  <code>true</code> if and only if the file or directory is
475     *          successfully deleted; <code>false</code> otherwise
476     */
477    public static boolean deleteDirectory(File path) {
478        if (path.exists()) {
479            File[] files = path.listFiles();
480            if (files != null) {
481                for (File file : files) {
482                    if (file.isDirectory()) {
483                        deleteDirectory(file);
484                    } else {
485                        deleteFile(file);
486                    }
487                }
488            }
489        }
490        return path.delete();
491    }
492
493    /**
494     * Deletes a file and log a default warning if the deletion fails.
495     * @param file file to delete
496     * @return {@code true} if and only if the file is successfully deleted; {@code false} otherwise
497     * @since 9296
498     */
499    public static boolean deleteFile(File file) {
500        return deleteFile(file, marktr("Unable to delete file {0}"));
501    }
502
503    /**
504     * Deletes a file and log a configurable warning if the deletion fails.
505     * @param file file to delete
506     * @param warnMsg warning message. It will be translated with {@code tr()}
507     * and must contain a single parameter <code>{0}</code> for the file path
508     * @return {@code true} if and only if the file is successfully deleted; {@code false} otherwise
509     * @since 9296
510     */
511    public static boolean deleteFile(File file, String warnMsg) {
512        boolean result = file.delete();
513        if (!result) {
514            Main.warn(tr(warnMsg, file.getPath()));
515        }
516        return result;
517    }
518
519    /**
520     * Creates a directory and log a default warning if the creation fails.
521     * @param dir directory to create
522     * @return {@code true} if and only if the directory is successfully created; {@code false} otherwise
523     * @since 9645
524     */
525    public static boolean mkDirs(File dir) {
526        return mkDirs(dir, marktr("Unable to create directory {0}"));
527    }
528
529    /**
530     * Creates a directory and log a configurable warning if the creation fails.
531     * @param dir directory to create
532     * @param warnMsg warning message. It will be translated with {@code tr()}
533     * and must contain a single parameter <code>{0}</code> for the directory path
534     * @return {@code true} if and only if the directory is successfully created; {@code false} otherwise
535     * @since 9645
536     */
537    public static boolean mkDirs(File dir, String warnMsg) {
538        boolean result = dir.mkdirs();
539        if (!result) {
540            Main.warn(tr(warnMsg, dir.getPath()));
541        }
542        return result;
543    }
544
545    /**
546     * <p>Utility method for closing a {@link java.io.Closeable} object.</p>
547     *
548     * @param c the closeable object. May be null.
549     */
550    public static void close(Closeable c) {
551        if (c == null) return;
552        try {
553            c.close();
554        } catch (IOException e) {
555            Main.warn(e);
556        }
557    }
558
559    /**
560     * <p>Utility method for closing a {@link java.util.zip.ZipFile}.</p>
561     *
562     * @param zip the zip file. May be null.
563     */
564    public static void close(ZipFile zip) {
565        if (zip == null) return;
566        try {
567            zip.close();
568        } catch (IOException e) {
569            Main.warn(e);
570        }
571    }
572
573    /**
574     * Converts the given file to its URL.
575     * @param f The file to get URL from
576     * @return The URL of the given file, or {@code null} if not possible.
577     * @since 6615
578     */
579    public static URL fileToURL(File f) {
580        if (f != null) {
581            try {
582                return f.toURI().toURL();
583            } catch (MalformedURLException ex) {
584                Main.error("Unable to convert filename " + f.getAbsolutePath() + " to URL");
585            }
586        }
587        return null;
588    }
589
590    private static final double EPSILON = 1e-11;
591
592    /**
593     * Determines if the two given double values are equal (their delta being smaller than a fixed epsilon)
594     * @param a The first double value to compare
595     * @param b The second double value to compare
596     * @return {@code true} if {@code abs(a - b) <= 1e-11}, {@code false} otherwise
597     */
598    public static boolean equalsEpsilon(double a, double b) {
599        return Math.abs(a - b) <= EPSILON;
600    }
601
602    /**
603     * Determines if two collections are equal.
604     * @param a first collection
605     * @param b second collection
606     * @return {@code true} if collections are equal, {@code false} otherwise
607     * @since 9217
608     */
609    public static boolean equalCollection(Collection<?> a, Collection<?> b) {
610        if (a == null) return b == null;
611        if (b == null) return false;
612        if (a.size() != b.size()) return false;
613        Iterator<?> itA = a.iterator();
614        Iterator<?> itB = b.iterator();
615        while (itA.hasNext()) {
616            if (!Objects.equals(itA.next(), itB.next()))
617                return false;
618        }
619        return true;
620    }
621
622    /**
623     * Copies the string {@code s} to system clipboard.
624     * @param s string to be copied to clipboard.
625     * @return true if succeeded, false otherwise.
626     */
627    public static boolean copyToClipboard(String s) {
628        try {
629            Toolkit.getDefaultToolkit().getSystemClipboard().setContents(new StringSelection(s), new ClipboardOwner() {
630                @Override
631                public void lostOwnership(Clipboard clpbrd, Transferable t) {
632                    // Do nothing
633                }
634            });
635            return true;
636        } catch (IllegalStateException | HeadlessException ex) {
637            Main.error(ex);
638            return false;
639        }
640    }
641
642    /**
643     * Extracts clipboard content as {@code Transferable} object.
644     * @param clipboard clipboard from which contents are retrieved
645     * @return clipboard contents if available, {@code null} otherwise.
646     * @since 8429
647     */
648    public static Transferable getTransferableContent(Clipboard clipboard) {
649        Transferable t = null;
650        for (int tries = 0; t == null && tries < 10; tries++) {
651            try {
652                t = clipboard.getContents(null);
653            } catch (IllegalStateException e) {
654                // Clipboard currently unavailable.
655                // On some platforms, the system clipboard is unavailable while it is accessed by another application.
656                try {
657                    Thread.sleep(1);
658                } catch (InterruptedException ex) {
659                    Main.warn("InterruptedException in "+Utils.class.getSimpleName()+" while getting clipboard content");
660                }
661            } catch (NullPointerException e) {
662                // JDK-6322854: On Linux/X11, NPE can happen for unknown reasons, on all versions of Java
663                Main.error(e);
664            }
665        }
666        return t;
667    }
668
669    /**
670     * Extracts clipboard content as string.
671     * @return string clipboard contents if available, {@code null} otherwise.
672     */
673    public static String getClipboardContent() {
674        try {
675            Transferable t = getTransferableContent(Toolkit.getDefaultToolkit().getSystemClipboard());
676            if (t != null && t.isDataFlavorSupported(DataFlavor.stringFlavor)) {
677                return (String) t.getTransferData(DataFlavor.stringFlavor);
678            }
679        } catch (UnsupportedFlavorException | IOException | HeadlessException ex) {
680            Main.error(ex);
681            return null;
682        }
683        return null;
684    }
685
686    /**
687     * Calculate MD5 hash of a string and output in hexadecimal format.
688     * @param data arbitrary String
689     * @return MD5 hash of data, string of length 32 with characters in range [0-9a-f]
690     */
691    public static String md5Hex(String data) {
692        MessageDigest md = null;
693        try {
694            md = MessageDigest.getInstance("MD5");
695        } catch (NoSuchAlgorithmException e) {
696            throw new RuntimeException(e);
697        }
698        byte[] byteData = data.getBytes(StandardCharsets.UTF_8);
699        byte[] byteDigest = md.digest(byteData);
700        return toHexString(byteDigest);
701    }
702
703    private static final char[] HEX_ARRAY = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
704
705    /**
706     * Converts a byte array to a string of hexadecimal characters.
707     * Preserves leading zeros, so the size of the output string is always twice
708     * the number of input bytes.
709     * @param bytes the byte array
710     * @return hexadecimal representation
711     */
712    public static String toHexString(byte[] bytes) {
713
714        if (bytes == null) {
715            return "";
716        }
717
718        final int len = bytes.length;
719        if (len == 0) {
720            return "";
721        }
722
723        char[] hexChars = new char[len * 2];
724        for (int i = 0, j = 0; i < len; i++) {
725            final int v = bytes[i];
726            hexChars[j++] = HEX_ARRAY[(v & 0xf0) >> 4];
727            hexChars[j++] = HEX_ARRAY[v & 0xf];
728        }
729        return new String(hexChars);
730    }
731
732    /**
733     * Topological sort.
734     * @param <T> type of items
735     *
736     * @param dependencies contains mappings (key -&gt; value). In the final list of sorted objects, the key will come
737     * after the value. (In other words, the key depends on the value(s).)
738     * There must not be cyclic dependencies.
739     * @return the list of sorted objects
740     */
741    public static <T> List<T> topologicalSort(final MultiMap<T, T> dependencies) {
742        MultiMap<T, T> deps = new MultiMap<>();
743        for (T key : dependencies.keySet()) {
744            deps.putVoid(key);
745            for (T val : dependencies.get(key)) {
746                deps.putVoid(val);
747                deps.put(key, val);
748            }
749        }
750
751        int size = deps.size();
752        List<T> sorted = new ArrayList<>();
753        for (int i = 0; i < size; ++i) {
754            T parentless = null;
755            for (T key : deps.keySet()) {
756                if (deps.get(key).isEmpty()) {
757                    parentless = key;
758                    break;
759                }
760            }
761            if (parentless == null) throw new RuntimeException();
762            sorted.add(parentless);
763            deps.remove(parentless);
764            for (T key : deps.keySet()) {
765                deps.remove(key, parentless);
766            }
767        }
768        if (sorted.size() != size) throw new RuntimeException();
769        return sorted;
770    }
771
772    /**
773     * Replaces some HTML reserved characters (&lt;, &gt; and &amp;) by their equivalent entity (&amp;lt;, &amp;gt; and &amp;amp;);
774     * @param s The unescaped string
775     * @return The escaped string
776     */
777    public static String escapeReservedCharactersHTML(String s) {
778        return s == null ? "" : s.replace("&", "&amp;").replace("<", "&lt;").replace(">", "&gt;");
779    }
780
781    /**
782     * Represents a function that can be applied to objects of {@code A} and
783     * returns objects of {@code B}.
784     * @param <A> class of input objects
785     * @param <B> class of transformed objects
786     */
787    public interface Function<A, B> {
788
789        /**
790         * Applies the function on {@code x}.
791         * @param x an object of
792         * @return the transformed object
793         */
794        B apply(A x);
795    }
796
797    /**
798     * Transforms the collection {@code c} into an unmodifiable collection and
799     * applies the {@link org.openstreetmap.josm.tools.Utils.Function} {@code f} on each element upon access.
800     * @param <A> class of input collection
801     * @param <B> class of transformed collection
802     * @param c a collection
803     * @param f a function that transforms objects of {@code A} to objects of {@code B}
804     * @return the transformed unmodifiable collection
805     */
806    public static <A, B> Collection<B> transform(final Collection<? extends A> c, final Function<A, B> f) {
807        return new AbstractCollection<B>() {
808
809            @Override
810            public int size() {
811                return c.size();
812            }
813
814            @Override
815            public Iterator<B> iterator() {
816                return new Iterator<B>() {
817
818                    private Iterator<? extends A> it = c.iterator();
819
820                    @Override
821                    public boolean hasNext() {
822                        return it.hasNext();
823                    }
824
825                    @Override
826                    public B next() {
827                        return f.apply(it.next());
828                    }
829
830                    @Override
831                    public void remove() {
832                        throw new UnsupportedOperationException();
833                    }
834                };
835            }
836        };
837    }
838
839    /**
840     * Transforms the list {@code l} into an unmodifiable list and
841     * applies the {@link org.openstreetmap.josm.tools.Utils.Function} {@code f} on each element upon access.
842     * @param <A> class of input collection
843     * @param <B> class of transformed collection
844     * @param l a collection
845     * @param f a function that transforms objects of {@code A} to objects of {@code B}
846     * @return the transformed unmodifiable list
847     */
848    public static <A, B> List<B> transform(final List<? extends A> l, final Function<A, B> f) {
849        return new AbstractList<B>() {
850
851            @Override
852            public int size() {
853                return l.size();
854            }
855
856            @Override
857            public B get(int index) {
858                return f.apply(l.get(index));
859            }
860        };
861    }
862
863    /**
864     * Returns a Bzip2 input stream wrapping given input stream.
865     * @param in The raw input stream
866     * @return a Bzip2 input stream wrapping given input stream, or {@code null} if {@code in} is {@code null}
867     * @throws IOException if the given input stream does not contain valid BZ2 header
868     * @since 7867
869     */
870    public static BZip2CompressorInputStream getBZip2InputStream(InputStream in) throws IOException {
871        if (in == null) {
872            return null;
873        }
874        return new BZip2CompressorInputStream(in, /* see #9537 */ true);
875    }
876
877    /**
878     * Returns a Gzip input stream wrapping given input stream.
879     * @param in The raw input stream
880     * @return a Gzip input stream wrapping given input stream, or {@code null} if {@code in} is {@code null}
881     * @throws IOException if an I/O error has occurred
882     * @since 7119
883     */
884    public static GZIPInputStream getGZipInputStream(InputStream in) throws IOException {
885        if (in == null) {
886            return null;
887        }
888        return new GZIPInputStream(in);
889    }
890
891    /**
892     * Returns a Zip input stream wrapping given input stream.
893     * @param in The raw input stream
894     * @return a Zip input stream wrapping given input stream, or {@code null} if {@code in} is {@code null}
895     * @throws IOException if an I/O error has occurred
896     * @since 7119
897     */
898    public static ZipInputStream getZipInputStream(InputStream in) throws IOException {
899        if (in == null) {
900            return null;
901        }
902        ZipInputStream zis = new ZipInputStream(in, StandardCharsets.UTF_8);
903        // Positions the stream at the beginning of first entry
904        ZipEntry ze = zis.getNextEntry();
905        if (ze != null && Main.isDebugEnabled()) {
906            Main.debug("Zip entry: "+ze.getName());
907        }
908        return zis;
909    }
910
911    /**
912     * An alternative to {@link String#trim()} to effectively remove all leading
913     * and trailing white characters, including Unicode ones.
914     * @param str The string to strip
915     * @return <code>str</code>, without leading and trailing characters, according to
916     *         {@link Character#isWhitespace(char)} and {@link Character#isSpaceChar(char)}.
917     * @see <a href="http://closingbraces.net/2008/11/11/javastringtrim/">Java’s String.trim has a strange idea of whitespace</a>
918     * @see <a href="https://bugs.openjdk.java.net/browse/JDK-4080617">JDK bug 4080617</a>
919     * @see <a href="https://bugs.openjdk.java.net/browse/JDK-7190385">JDK bug 7190385</a>
920     * @since 5772
921     */
922    public static String strip(final String str) {
923        if (str == null || str.isEmpty()) {
924            return str;
925        }
926        return strip(str, DEFAULT_STRIP);
927    }
928
929    /**
930     * An alternative to {@link String#trim()} to effectively remove all leading
931     * and trailing white characters, including Unicode ones.
932     * @param str The string to strip
933     * @param skipChars additional characters to skip
934     * @return <code>str</code>, without leading and trailing characters, according to
935     *         {@link Character#isWhitespace(char)}, {@link Character#isSpaceChar(char)} and skipChars.
936     * @since 8435
937     */
938    public static String strip(final String str, final String skipChars) {
939        if (str == null || str.isEmpty()) {
940            return str;
941        }
942        return strip(str, stripChars(skipChars));
943    }
944
945    private static String strip(final String str, final char[] skipChars) {
946
947        int start = 0;
948        int end = str.length();
949        boolean leadingSkipChar = true;
950        while (leadingSkipChar && start < end) {
951            char c = str.charAt(start);
952            leadingSkipChar = Character.isWhitespace(c) || Character.isSpaceChar(c) || stripChar(skipChars, c);
953            if (leadingSkipChar) {
954                start++;
955            }
956        }
957        boolean trailingSkipChar = true;
958        while (trailingSkipChar && end > start + 1) {
959            char c = str.charAt(end - 1);
960            trailingSkipChar = Character.isWhitespace(c) || Character.isSpaceChar(c) || stripChar(skipChars, c);
961            if (trailingSkipChar) {
962                end--;
963            }
964        }
965
966        return str.substring(start, end);
967    }
968
969    private static char[] stripChars(final String skipChars) {
970        if (skipChars == null || skipChars.isEmpty()) {
971            return DEFAULT_STRIP;
972        }
973
974        char[] chars = new char[DEFAULT_STRIP.length + skipChars.length()];
975        System.arraycopy(DEFAULT_STRIP, 0, chars, 0, DEFAULT_STRIP.length);
976        skipChars.getChars(0, skipChars.length(), chars, DEFAULT_STRIP.length);
977
978        return chars;
979    }
980
981    private static boolean stripChar(final char[] strip, char c) {
982        for (char s : strip) {
983            if (c == s) {
984                return true;
985            }
986        }
987        return false;
988    }
989
990    /**
991     * Runs an external command and returns the standard output.
992     *
993     * The program is expected to execute fast.
994     *
995     * @param command the command with arguments
996     * @return the output
997     * @throws IOException when there was an error, e.g. command does not exist
998     */
999    public static String execOutput(List<String> command) throws IOException {
1000        if (Main.isDebugEnabled()) {
1001            Main.debug(join(" ", command));
1002        }
1003        Process p = new ProcessBuilder(command).start();
1004        try (BufferedReader input = new BufferedReader(new InputStreamReader(p.getInputStream(), StandardCharsets.UTF_8))) {
1005            StringBuilder all = null;
1006            String line;
1007            while ((line = input.readLine()) != null) {
1008                if (all == null) {
1009                    all = new StringBuilder(line);
1010                } else {
1011                    all.append('\n');
1012                    all.append(line);
1013                }
1014            }
1015            return all != null ? all.toString() : null;
1016        }
1017    }
1018
1019    /**
1020     * Returns the JOSM temp directory.
1021     * @return The JOSM temp directory ({@code <java.io.tmpdir>/JOSM}), or {@code null} if {@code java.io.tmpdir} is not defined
1022     * @since 6245
1023     */
1024    public static File getJosmTempDir() {
1025        String tmpDir = System.getProperty("java.io.tmpdir");
1026        if (tmpDir == null) {
1027            return null;
1028        }
1029        File josmTmpDir = new File(tmpDir, "JOSM");
1030        if (!josmTmpDir.exists() && !josmTmpDir.mkdirs()) {
1031            Main.warn("Unable to create temp directory " + josmTmpDir);
1032        }
1033        return josmTmpDir;
1034    }
1035
1036    /**
1037     * Returns a simple human readable (hours, minutes, seconds) string for a given duration in milliseconds.
1038     * @param elapsedTime The duration in milliseconds
1039     * @return A human readable string for the given duration
1040     * @throws IllegalArgumentException if elapsedTime is &lt; 0
1041     * @since 6354
1042     */
1043    public static String getDurationString(long elapsedTime) {
1044        if (elapsedTime < 0) {
1045            throw new IllegalArgumentException("elapsedTime must be >= 0");
1046        }
1047        // Is it less than 1 second ?
1048        if (elapsedTime < MILLIS_OF_SECOND) {
1049            return String.format("%d %s", elapsedTime, tr("ms"));
1050        }
1051        // Is it less than 1 minute ?
1052        if (elapsedTime < MILLIS_OF_MINUTE) {
1053            return String.format("%.1f %s", elapsedTime / (double) MILLIS_OF_SECOND, tr("s"));
1054        }
1055        // Is it less than 1 hour ?
1056        if (elapsedTime < MILLIS_OF_HOUR) {
1057            final long min = elapsedTime / MILLIS_OF_MINUTE;
1058            return String.format("%d %s %d %s", min, tr("min"), (elapsedTime - min * MILLIS_OF_MINUTE) / MILLIS_OF_SECOND, tr("s"));
1059        }
1060        // Is it less than 1 day ?
1061        if (elapsedTime < MILLIS_OF_DAY) {
1062            final long hour = elapsedTime / MILLIS_OF_HOUR;
1063            return String.format("%d %s %d %s", hour, tr("h"), (elapsedTime - hour * MILLIS_OF_HOUR) / MILLIS_OF_MINUTE, tr("min"));
1064        }
1065        long days = elapsedTime / MILLIS_OF_DAY;
1066        return String.format("%d %s %d %s", days, trn("day", "days", days), (elapsedTime - days * MILLIS_OF_DAY) / MILLIS_OF_HOUR, tr("h"));
1067    }
1068
1069    /**
1070     * Returns a human readable representation (B, kB, MB, ...) for the given number of byes.
1071     * @param bytes the number of bytes
1072     * @param locale the locale used for formatting
1073     * @return a human readable representation
1074     * @since 9274
1075     */
1076    public static String getSizeString(long bytes, Locale locale) {
1077        if (bytes < 0) {
1078            throw new IllegalArgumentException("bytes must be >= 0");
1079        }
1080        int unitIndex = 0;
1081        double value = bytes;
1082        while (value >= 1024 && unitIndex < SIZE_UNITS.length) {
1083            value /= 1024;
1084            unitIndex++;
1085        }
1086        if (value > 100 || unitIndex == 0) {
1087            return String.format(locale, "%.0f %s", value, SIZE_UNITS[unitIndex]);
1088        } else if (value > 10) {
1089            return String.format(locale, "%.1f %s", value, SIZE_UNITS[unitIndex]);
1090        } else {
1091            return String.format(locale, "%.2f %s", value, SIZE_UNITS[unitIndex]);
1092        }
1093    }
1094
1095    /**
1096     * Returns a human readable representation of a list of positions.
1097     * <p>
1098     * For instance, {@code [1,5,2,6,7} yields "1-2,5-7
1099     * @param positionList a list of positions
1100     * @return a human readable representation
1101     */
1102    public static String getPositionListString(List<Integer> positionList) {
1103        Collections.sort(positionList);
1104        final StringBuilder sb = new StringBuilder(32);
1105        sb.append(positionList.get(0));
1106        int cnt = 0;
1107        int last = positionList.get(0);
1108        for (int i = 1; i < positionList.size(); ++i) {
1109            int cur = positionList.get(i);
1110            if (cur == last + 1) {
1111                ++cnt;
1112            } else if (cnt == 0) {
1113                sb.append(',').append(cur);
1114            } else {
1115                sb.append('-').append(last);
1116                sb.append(',').append(cur);
1117                cnt = 0;
1118            }
1119            last = cur;
1120        }
1121        if (cnt >= 1) {
1122            sb.append('-').append(last);
1123        }
1124        return sb.toString();
1125    }
1126
1127    /**
1128     * Returns a list of capture groups if {@link Matcher#matches()}, or {@code null}.
1129     * The first element (index 0) is the complete match.
1130     * Further elements correspond to the parts in parentheses of the regular expression.
1131     * @param m the matcher
1132     * @return a list of capture groups if {@link Matcher#matches()}, or {@code null}.
1133     */
1134    public static List<String> getMatches(final Matcher m) {
1135        if (m.matches()) {
1136            List<String> result = new ArrayList<>(m.groupCount() + 1);
1137            for (int i = 0; i <= m.groupCount(); i++) {
1138                result.add(m.group(i));
1139            }
1140            return result;
1141        } else {
1142            return null;
1143        }
1144    }
1145
1146    /**
1147     * Cast an object savely.
1148     * @param <T> the target type
1149     * @param o the object to cast
1150     * @param klass the target class (same as T)
1151     * @return null if <code>o</code> is null or the type <code>o</code> is not
1152     *  a subclass of <code>klass</code>. The casted value otherwise.
1153     */
1154    @SuppressWarnings("unchecked")
1155    public static <T> T cast(Object o, Class<T> klass) {
1156        if (klass.isInstance(o)) {
1157            return (T) o;
1158        }
1159        return null;
1160    }
1161
1162    /**
1163     * Returns the root cause of a throwable object.
1164     * @param t The object to get root cause for
1165     * @return the root cause of {@code t}
1166     * @since 6639
1167     */
1168    public static Throwable getRootCause(Throwable t) {
1169        Throwable result = t;
1170        if (result != null) {
1171            Throwable cause = result.getCause();
1172            while (cause != null && !cause.equals(result)) {
1173                result = cause;
1174                cause = result.getCause();
1175            }
1176        }
1177        return result;
1178    }
1179
1180    /**
1181     * Adds the given item at the end of a new copy of given array.
1182     * @param <T> type of items
1183     * @param array The source array
1184     * @param item The item to add
1185     * @return An extended copy of {@code array} containing {@code item} as additional last element
1186     * @since 6717
1187     */
1188    public static <T> T[] addInArrayCopy(T[] array, T item) {
1189        T[] biggerCopy = Arrays.copyOf(array, array.length + 1);
1190        biggerCopy[array.length] = item;
1191        return biggerCopy;
1192    }
1193
1194    /**
1195     * If the string {@code s} is longer than {@code maxLength}, the string is cut and "..." is appended.
1196     * @param s String to shorten
1197     * @param maxLength maximum number of characters to keep (not including the "...")
1198     * @return the shortened string
1199     */
1200    public static String shortenString(String s, int maxLength) {
1201        if (s != null && s.length() > maxLength) {
1202            return s.substring(0, maxLength - 3) + "...";
1203        } else {
1204            return s;
1205        }
1206    }
1207
1208    /**
1209     * If the string {@code s} is longer than {@code maxLines} lines, the string is cut and a "..." line is appended.
1210     * @param s String to shorten
1211     * @param maxLines maximum number of lines to keep (including including the "..." line)
1212     * @return the shortened string
1213     */
1214    public static String restrictStringLines(String s, int maxLines) {
1215        if (s == null) {
1216            return null;
1217        } else {
1218            return join("\n", limit(Arrays.asList(s.split("\\n")), maxLines, "..."));
1219        }
1220    }
1221
1222    /**
1223     * If the collection {@code elements} is larger than {@code maxElements} elements,
1224     * the collection is shortened and the {@code overflowIndicator} is appended.
1225     * @param <T> type of elements
1226     * @param elements collection to shorten
1227     * @param maxElements maximum number of elements to keep (including including the {@code overflowIndicator})
1228     * @param overflowIndicator the element used to indicate that the collection has been shortened
1229     * @return the shortened collection
1230     */
1231    public static <T> Collection<T> limit(Collection<T> elements, int maxElements, T overflowIndicator) {
1232        if (elements == null) {
1233            return null;
1234        } else {
1235            if (elements.size() > maxElements) {
1236                final Collection<T> r = new ArrayList<>(maxElements);
1237                final Iterator<T> it = elements.iterator();
1238                while (r.size() < maxElements - 1) {
1239                    r.add(it.next());
1240                }
1241                r.add(overflowIndicator);
1242                return r;
1243            } else {
1244                return elements;
1245            }
1246        }
1247    }
1248
1249    /**
1250     * Fixes URL with illegal characters in the query (and fragment) part by
1251     * percent encoding those characters.
1252     *
1253     * special characters like &amp; and # are not encoded
1254     *
1255     * @param url the URL that should be fixed
1256     * @return the repaired URL
1257     */
1258    public static String fixURLQuery(String url) {
1259        if (url == null || url.indexOf('?') == -1)
1260            return url;
1261
1262        String query = url.substring(url.indexOf('?') + 1);
1263
1264        StringBuilder sb = new StringBuilder(url.substring(0, url.indexOf('?') + 1));
1265
1266        for (int i = 0; i < query.length(); i++) {
1267            String c = query.substring(i, i + 1);
1268            if (URL_CHARS.contains(c)) {
1269                sb.append(c);
1270            } else {
1271                sb.append(encodeUrl(c));
1272            }
1273        }
1274        return sb.toString();
1275    }
1276
1277    /**
1278     * Translates a string into <code>application/x-www-form-urlencoded</code>
1279     * format. This method uses UTF-8 encoding scheme to obtain the bytes for unsafe
1280     * characters.
1281     *
1282     * @param   s <code>String</code> to be translated.
1283     * @return  the translated <code>String</code>.
1284     * @see #decodeUrl(String)
1285     * @since 8304
1286     */
1287    public static String encodeUrl(String s) {
1288        final String enc = StandardCharsets.UTF_8.name();
1289        try {
1290            return URLEncoder.encode(s, enc);
1291        } catch (UnsupportedEncodingException e) {
1292            throw new IllegalStateException(e);
1293        }
1294    }
1295
1296    /**
1297     * Decodes a <code>application/x-www-form-urlencoded</code> string.
1298     * UTF-8 encoding is used to determine
1299     * what characters are represented by any consecutive sequences of the
1300     * form "<code>%<i>xy</i></code>".
1301     *
1302     * @param s the <code>String</code> to decode
1303     * @return the newly decoded <code>String</code>
1304     * @see #encodeUrl(String)
1305     * @since 8304
1306     */
1307    public static String decodeUrl(String s) {
1308        final String enc = StandardCharsets.UTF_8.name();
1309        try {
1310            return URLDecoder.decode(s, enc);
1311        } catch (UnsupportedEncodingException e) {
1312            throw new IllegalStateException(e);
1313        }
1314    }
1315
1316    /**
1317     * Determines if the given URL denotes a file on a local filesystem.
1318     * @param url The URL to test
1319     * @return {@code true} if the url points to a local file
1320     * @since 7356
1321     */
1322    public static boolean isLocalUrl(String url) {
1323        if (url.startsWith("http://") || url.startsWith("https://") || url.startsWith("resource://"))
1324            return false;
1325        return true;
1326    }
1327
1328    /**
1329     * Determines if the given URL is valid.
1330     * @param url The URL to test
1331     * @return {@code true} if the url is valid
1332     * @since 10294
1333     */
1334    public static boolean isValidUrl(String url) {
1335        try {
1336            new URL(url);
1337            return true;
1338        } catch (MalformedURLException | NullPointerException e) {
1339            return false;
1340        }
1341    }
1342
1343    /**
1344     * Creates a new {@link ThreadFactory} which creates threads with names according to {@code nameFormat}.
1345     * @param nameFormat a {@link String#format(String, Object...)} compatible name format; its first argument is a unique thread index
1346     * @param threadPriority the priority of the created threads, see {@link Thread#setPriority(int)}
1347     * @return a new {@link ThreadFactory}
1348     */
1349    public static ThreadFactory newThreadFactory(final String nameFormat, final int threadPriority) {
1350        return new ThreadFactory() {
1351            final AtomicLong count = new AtomicLong(0);
1352            @Override
1353            public Thread newThread(final Runnable runnable) {
1354                final Thread thread = new Thread(runnable, String.format(Locale.ENGLISH, nameFormat, count.getAndIncrement()));
1355                thread.setPriority(threadPriority);
1356                return thread;
1357            }
1358        };
1359    }
1360
1361    /**
1362     * Returns a {@link ForkJoinPool} with the parallelism given by the preference key.
1363     * @param pref The preference key to determine parallelism
1364     * @param nameFormat see {@link #newThreadFactory(String, int)}
1365     * @param threadPriority see {@link #newThreadFactory(String, int)}
1366     * @return a {@link ForkJoinPool}
1367     */
1368    public static ForkJoinPool newForkJoinPool(String pref, final String nameFormat, final int threadPriority) {
1369        int noThreads = Main.pref.getInteger(pref, Runtime.getRuntime().availableProcessors());
1370        return new ForkJoinPool(noThreads, new ForkJoinPool.ForkJoinWorkerThreadFactory() {
1371            final AtomicLong count = new AtomicLong(0);
1372            @Override
1373            public ForkJoinWorkerThread newThread(ForkJoinPool pool) {
1374                final ForkJoinWorkerThread thread = ForkJoinPool.defaultForkJoinWorkerThreadFactory.newThread(pool);
1375                thread.setName(String.format(Locale.ENGLISH, nameFormat, count.getAndIncrement()));
1376                thread.setPriority(threadPriority);
1377                return thread;
1378            }
1379        }, null, true);
1380    }
1381
1382    /**
1383     * Returns an executor which executes commands in the calling thread
1384     * @return an executor
1385     */
1386    public static Executor newDirectExecutor() {
1387        return new Executor() {
1388            @Override
1389            public void execute(Runnable command) {
1390                command.run();
1391            }
1392        };
1393    }
1394
1395    /**
1396     * Updates a given system property.
1397     * @param key The property key
1398     * @param value The property value
1399     * @return the previous value of the system property, or {@code null} if it did not have one.
1400     * @since 7894
1401     */
1402    public static String updateSystemProperty(String key, String value) {
1403        if (value != null) {
1404            String old = System.setProperty(key, value);
1405            if (!key.toLowerCase(Locale.ENGLISH).contains("password")) {
1406                Main.debug("System property '" + key + "' set to '" + value + "'. Old value was '" + old + '\'');
1407            } else {
1408                Main.debug("System property '" + key + "' changed.");
1409            }
1410            return old;
1411        }
1412        return null;
1413    }
1414
1415    /**
1416     * Returns a new secure DOM builder, supporting XML namespaces.
1417     * @return a new secure DOM builder, supporting XML namespaces
1418     * @throws ParserConfigurationException if a parser cannot be created which satisfies the requested configuration.
1419     * @throws ParserConfigurationException if a parser cannot be created which satisfies the requested configuration.
1420     * @since 10404
1421     */
1422    public static DocumentBuilder newSafeDOMBuilder() throws ParserConfigurationException {
1423        DocumentBuilderFactory builderFactory = DocumentBuilderFactory.newInstance();
1424        builderFactory.setFeature(XMLConstants.FEATURE_SECURE_PROCESSING, true);
1425        builderFactory.setNamespaceAware(true);
1426        builderFactory.setValidating(false);
1427        return builderFactory.newDocumentBuilder();
1428    }
1429
1430    /**
1431     * Parse the content given {@link InputStream} as XML.
1432     * This method uses a secure DOM builder, supporting XML namespaces.
1433     *
1434     * @param is The InputStream containing the content to be parsed.
1435     * @return the result DOM document
1436     * @throws ParserConfigurationException if a parser cannot be created which satisfies the requested configuration.
1437     * @throws IOException if any IO errors occur.
1438     * @throws SAXException for SAX errors.
1439     * @since 10404
1440     */
1441    public static Document parseSafeDOM(InputStream is) throws ParserConfigurationException, IOException, SAXException {
1442        long start = System.currentTimeMillis();
1443        if (Main.isDebugEnabled()) {
1444            Main.debug("Starting DOM parsing of " + is);
1445        }
1446        Document result = newSafeDOMBuilder().parse(is);
1447        if (Main.isDebugEnabled()) {
1448            Main.debug("DOM parsing done in " + getDurationString(System.currentTimeMillis() - start));
1449        }
1450        return result;
1451    }
1452
1453    /**
1454     * Returns a new secure SAX parser, supporting XML namespaces.
1455     * @return a new secure SAX parser, supporting XML namespaces
1456     * @throws ParserConfigurationException if a parser cannot be created which satisfies the requested configuration.
1457     * @throws SAXException for SAX errors.
1458     * @since 8287
1459     */
1460    public static SAXParser newSafeSAXParser() throws ParserConfigurationException, SAXException {
1461        SAXParserFactory parserFactory = SAXParserFactory.newInstance();
1462        parserFactory.setFeature(XMLConstants.FEATURE_SECURE_PROCESSING, true);
1463        parserFactory.setNamespaceAware(true);
1464        return parserFactory.newSAXParser();
1465    }
1466
1467    /**
1468     * Parse the content given {@link org.xml.sax.InputSource} as XML using the specified {@link org.xml.sax.helpers.DefaultHandler}.
1469     * This method uses a secure SAX parser, supporting XML namespaces.
1470     *
1471     * @param is The InputSource containing the content to be parsed.
1472     * @param dh The SAX DefaultHandler to use.
1473     * @throws ParserConfigurationException if a parser cannot be created which satisfies the requested configuration.
1474     * @throws SAXException for SAX errors.
1475     * @throws IOException if any IO errors occur.
1476     * @since 8347
1477     */
1478    public static void parseSafeSAX(InputSource is, DefaultHandler dh) throws ParserConfigurationException, SAXException, IOException {
1479        long start = System.currentTimeMillis();
1480        if (Main.isDebugEnabled()) {
1481            Main.debug("Starting SAX parsing of " + is + " using " + dh);
1482        }
1483        newSafeSAXParser().parse(is, dh);
1484        if (Main.isDebugEnabled()) {
1485            Main.debug("SAX parsing done in " + getDurationString(System.currentTimeMillis() - start));
1486        }
1487    }
1488
1489    /**
1490     * Determines if the filename has one of the given extensions, in a robust manner.
1491     * The comparison is case and locale insensitive.
1492     * @param filename The file name
1493     * @param extensions The list of extensions to look for (without dot)
1494     * @return {@code true} if the filename has one of the given extensions
1495     * @since 8404
1496     */
1497    public static boolean hasExtension(String filename, String... extensions) {
1498        String name = filename.toLowerCase(Locale.ENGLISH).replace("?format=raw", "");
1499        for (String ext : extensions) {
1500            if (name.endsWith('.' + ext.toLowerCase(Locale.ENGLISH)))
1501                return true;
1502        }
1503        return false;
1504    }
1505
1506    /**
1507     * Determines if the file's name has one of the given extensions, in a robust manner.
1508     * The comparison is case and locale insensitive.
1509     * @param file The file
1510     * @param extensions The list of extensions to look for (without dot)
1511     * @return {@code true} if the file's name has one of the given extensions
1512     * @since 8404
1513     */
1514    public static boolean hasExtension(File file, String... extensions) {
1515        return hasExtension(file.getName(), extensions);
1516    }
1517
1518    /**
1519     * Reads the input stream and closes the stream at the end of processing (regardless if an exception was thrown)
1520     *
1521     * @param stream input stream
1522     * @return byte array of data in input stream
1523     * @throws IOException if any I/O error occurs
1524     */
1525    public static byte[] readBytesFromStream(InputStream stream) throws IOException {
1526        try {
1527            ByteArrayOutputStream bout = new ByteArrayOutputStream(stream.available());
1528            byte[] buffer = new byte[2048];
1529            boolean finished = false;
1530            do {
1531                int read = stream.read(buffer);
1532                if (read >= 0) {
1533                    bout.write(buffer, 0, read);
1534                } else {
1535                    finished = true;
1536                }
1537            } while (!finished);
1538            if (bout.size() == 0)
1539                return null;
1540            return bout.toByteArray();
1541        } finally {
1542            stream.close();
1543        }
1544    }
1545
1546    /**
1547     * Returns the initial capacity to pass to the HashMap / HashSet constructor
1548     * when it is initialized with a known number of entries.
1549     *
1550     * When a HashMap is filled with entries, the underlying array is copied over
1551     * to a larger one multiple times. To avoid this process when the number of
1552     * entries is known in advance, the initial capacity of the array can be
1553     * given to the HashMap constructor. This method returns a suitable value
1554     * that avoids rehashing but doesn't waste memory.
1555     * @param nEntries the number of entries expected
1556     * @param loadFactor the load factor
1557     * @return the initial capacity for the HashMap constructor
1558     */
1559    public static int hashMapInitialCapacity(int nEntries, double loadFactor) {
1560        return (int) Math.ceil(nEntries / loadFactor);
1561    }
1562
1563    /**
1564     * Returns the initial capacity to pass to the HashMap / HashSet constructor
1565     * when it is initialized with a known number of entries.
1566     *
1567     * When a HashMap is filled with entries, the underlying array is copied over
1568     * to a larger one multiple times. To avoid this process when the number of
1569     * entries is known in advance, the initial capacity of the array can be
1570     * given to the HashMap constructor. This method returns a suitable value
1571     * that avoids rehashing but doesn't waste memory.
1572     *
1573     * Assumes default load factor (0.75).
1574     * @param nEntries the number of entries expected
1575     * @return the initial capacity for the HashMap constructor
1576     */
1577    public static int hashMapInitialCapacity(int nEntries) {
1578        return hashMapInitialCapacity(nEntries, 0.75d);
1579    }
1580
1581    /**
1582     * Utility class to save a string along with its rendering direction
1583     * (left-to-right or right-to-left).
1584     */
1585    private static class DirectionString {
1586        public final int direction;
1587        public final String str;
1588
1589        DirectionString(int direction, String str) {
1590            this.direction = direction;
1591            this.str = str;
1592        }
1593    }
1594
1595    /**
1596     * Convert a string to a list of {@link GlyphVector}s. The string may contain
1597     * bi-directional text. The result will be in correct visual order.
1598     * Each element of the resulting list corresponds to one section of the
1599     * string with consistent writing direction (left-to-right or right-to-left).
1600     *
1601     * @param string the string to render
1602     * @param font the font
1603     * @param frc a FontRenderContext object
1604     * @return a list of GlyphVectors
1605     */
1606    public static List<GlyphVector> getGlyphVectorsBidi(String string, Font font, FontRenderContext frc) {
1607        List<GlyphVector> gvs = new ArrayList<>();
1608        Bidi bidi = new Bidi(string, Bidi.DIRECTION_DEFAULT_LEFT_TO_RIGHT);
1609        byte[] levels = new byte[bidi.getRunCount()];
1610        DirectionString[] dirStrings = new DirectionString[levels.length];
1611        for (int i = 0; i < levels.length; ++i) {
1612            levels[i] = (byte) bidi.getRunLevel(i);
1613            String substr = string.substring(bidi.getRunStart(i), bidi.getRunLimit(i));
1614            int dir = levels[i] % 2 == 0 ? Bidi.DIRECTION_LEFT_TO_RIGHT : Bidi.DIRECTION_RIGHT_TO_LEFT;
1615            dirStrings[i] = new DirectionString(dir, substr);
1616        }
1617        Bidi.reorderVisually(levels, 0, dirStrings, 0, levels.length);
1618        for (int i = 0; i < dirStrings.length; ++i) {
1619            char[] chars = dirStrings[i].str.toCharArray();
1620            gvs.add(font.layoutGlyphVector(frc, chars, 0, chars.length, dirStrings[i].direction));
1621        }
1622        return gvs;
1623    }
1624
1625    /**
1626     * Sets {@code AccessibleObject}(s) accessible.
1627     * @param objects objects
1628     * @see AccessibleObject#setAccessible
1629     * @since 10223
1630     */
1631    public static void setObjectsAccessible(final AccessibleObject ... objects) {
1632        if (objects != null && objects.length > 0) {
1633            AccessController.doPrivileged(new PrivilegedAction<Object>() {
1634                @Override
1635                public Object run() {
1636                    for (AccessibleObject o : objects) {
1637                        o.setAccessible(true);
1638                    }
1639                    return null;
1640                }
1641            });
1642        }
1643    }
1644}