cldr/util/CollationMapMaker.java

/*
 **********************************************************************
 * Copyright (c) 2006-2007, Google and others.  All Rights Reserved.
 **********************************************************************
 * Author: Mark Davis
 **********************************************************************
 */
package org.unicode.cldr.util;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

import org.unicode.cldr.util.VariantFolder.CaseVariantFolder;

import com.ibm.icu.dev.util.UnicodeMap;
import com.ibm.icu.impl.Utility;
import com.ibm.icu.lang.UCharacter;
import com.ibm.icu.text.CanonicalIterator;
import com.ibm.icu.text.CollationElementIterator;
import com.ibm.icu.text.Collator;
import com.ibm.icu.text.Normalizer;
import com.ibm.icu.text.RawCollationKey;
import com.ibm.icu.text.RuleBasedCollator;
import com.ibm.icu.text.Transliterator;
import com.ibm.icu.text.UTF16;
import com.ibm.icu.text.UnicodeSet;
import com.ibm.icu.text.UnicodeSetIterator;
import com.ibm.icu.util.ULocale;

public class CollationMapMaker {

    public static final boolean SHOW_DEBUG = false;

    /**
     * Used to pick the "best" sample from a set for using as the canonical form.
     *
     * @author markdavis
     *
     */
    static class ExemplarComparator implements java.util.Comparator {
        Comparator comp;

        @Override
        public int compare(Object o1, Object o2) {
            String s1 = (String) o1;
            String s2 = (String) o2;
            int result;

            // sort normalized first
            int n1 = Normalizer.isNormalized(s1, Normalizer.DECOMP_COMPAT, 0) ? 0 : 1;
            int n2 = Normalizer.isNormalized(s2, Normalizer.DECOMP_COMPAT, 0) ? 0 : 1;
            if ((result = n1 - n2) != 0) {
                return result;
            }

            // choose the shortest
            result = UTF16.countCodePoint(s2) - UTF16.countCodePoint(s1);
            if (result != 0) { // special fix to make zero be first
                if (s1.length() == 0)
                    return -1;
                if (s2.length() == 0)
                    return 1;
                return result;
            }
            result = comp.compare(s1, s2);
            if (result != 0)
                return result;
            return s1.compareTo(s2);
        }

        public ExemplarComparator(Comparator comp) {
            this.comp = comp;
        }

    }

    public static class Folder implements Cloneable {
        private UnicodeMap m = new UnicodeMap();

        @Override
        public Object clone() {
            try {
                Folder result = (Folder) super.clone();
                result.m = m.cloneAsThawed();
                return result;
            } catch (CloneNotSupportedException e) {
                throw new InternalError("Clone problem");
            }
        }

        public Object getValue(int i) {
            return m.getValue(i);
        }

        public UnicodeSet keySet() {
            return m.keySet();
        }

        public Folder put(int cp, String result) {
            m.put(cp, result);
            return this;
        }

        public Folder putAll(UnicodeSet set, String result) {
            m.putAll(set, result);
            return this;
        }

        public UnicodeSet getCharactersMapped() {
            return m.keySet();
        }

        public void minimalize() {
            UnicodeMap newMap = (m.cloneAsThawed());

            for (UnicodeSetIterator i = new UnicodeSetIterator(m.keySet()); i.next();) {
                String s = (String) m.getValue(i.codepoint);
                newMap.put(i.codepoint, null);
                String t = newMap.transform(newMap.transform(i.getString()));
                if (!t.equals(s)) { // restore
                    newMap.put(i.codepoint, s);
                }
            }
        }

        public void complete() {
            while (fixNeeded())
                ;
        }

        public boolean fixNeeded() {
            UnicodeMap newMap = new UnicodeMap();
            UnicodeSet values = m.keySet();
            boolean changed = false;
            for (UnicodeSetIterator i = new UnicodeSetIterator(values); i.next();) {
                String result = (String) m.getValue(i.codepoint);
                String newResult = fold(result);
                if (!newResult.equals(result)) {
                    changed = true;
                    if (SHOW_DEBUG) {
                        System.out.println(i.getString());
                        System.out.println("->\t" + result);
                        System.out.println("=>\t" + newResult);
                    }
                }
                newMap.put(i.codepoint, newResult);
            }
            m = newMap;
            return changed;
        }

        public String fold(String s) {
            return m.transform(s);
        }

        /**
         * Re
         *
         * @param toRemove
         * @param addIdentity
         *            TODO
         * @param old
         * @return
         */
        Folder removeEquals(Folder toRemove, boolean addIdentity) {
            UnicodeMap result = new UnicodeMap();
            for (int i = 0; i <= 0x10FFFF; ++i) {
                Object x = m.getValue(i);
                Object y = toRemove.m.getValue(i);
                if (!UnicodeMap.areEqual(x, y)) {
                    if (x != null) {
                        result.put(i, x);
                    } else if (addIdentity) {
                        result.put(i, UTF16.valueOf(i)); // have to add mapping
                    }
                }
            }
            m = result;
            return this;
        }

        static Transliterator FullWidthKana = Transliterator
            .getInstance("fullwidth-halfwidth; [[:script=katakana:][:script=hangul:]] halfwidth-fullwidth; katakana-hiragana");

        static String getSpecialFolded(String a) {
            String result = a;
            result = Normalizer.normalize(result, Normalizer.NFKC);
            result = FullWidthKana.transliterate(result);
            result = UCharacter.foldCase(result, true);
            result = Normalizer.normalize(result, Normalizer.NFKC);
            return result;
        }

        public UnicodeMap getUnicodeMap() {
            return m.cloneAsThawed();

        }

    }

    static final boolean showDetails = false;
    static final RuleBasedCollator uca = (RuleBasedCollator) Collator.getInstance(ULocale.ROOT);
    static final UnicodeSet filteredChars = new UnicodeSet(
        "[{ss}[^[:Co:][:Cf:][:Cc:][:Cn:][:Cs:][:script=Han:][:script=Hangul:]-[:nfkcquickcheck=no:]]]").freeze(); // skip
    // a
    // bunch
    // of
    // stuff,
    // but
    // include
    // the
    // items
    // that
    // are
    // not
    // nfkc

    RuleBasedCollator equivalenceClassCollator;
    Comparator exemplarComparator;
    Map<String, String> reasonMap = new TreeMap();
    XEquivalenceMap equivMap = new XEquivalenceMap();

    public Map<CharSequence, String> generateCollatorFolding(RuleBasedCollator equivalenceClassCollator,
        Map<CharSequence, String> mapping) {
        this.equivalenceClassCollator = equivalenceClassCollator;
        try {
            RuleBasedCollator exemplarCollator = (RuleBasedCollator) equivalenceClassCollator.clone();
            exemplarCollator.setStrength(Collator.IDENTICAL);
            exemplarCollator.setDecomposition(Collator.CANONICAL_DECOMPOSITION);
            exemplarCollator.setUpperCaseFirst(false);
            exemplarCollator.setAlternateHandlingShifted(false);
            exemplarCollator.setNumericCollation(false);
            exemplarCollator.setCaseLevel(false);
            exemplarCollator.setFrenchCollation(false);
            exemplarCollator.setHiraganaQuaternary(false);
            exemplarComparator = new ExemplarComparator(exemplarCollator);
        } catch (CloneNotSupportedException e) {
        } // will never happen

        UnicodeSet expansions = new UnicodeSet();
        UnicodeSet contractions = new UnicodeSet();
        try {
            equivalenceClassCollator.getContractionsAndExpansions(contractions, expansions, true);
        } catch (Exception e) {
        }

        UnicodeSet trialCharacters = new UnicodeSet(filteredChars).addAll(equivalenceClassCollator.getTailoredSet())
            .addAll(contractions).addAll(expansions);

        for (UnicodeSetIterator i = new UnicodeSetIterator(trialCharacters); i.next();) {
            String item = i.getString();
            addItems(item);
        }

        for (UnicodeSetIterator i = new UnicodeSetIterator(getFullExpansions()); i.next();) {
            String item = i.getString();
            addItems(item);
        }

        closeUnderFolding();

        if (showDetails) Log.getLog().println("Printing Values: " + equivMap.size());
        int count = 0;
        int countMapped = 0;

        // Now process the results to figure out what we need to keep
        Set<String> values = new TreeSet(exemplarComparator);

        for (Iterator it = equivMap.iterator(); it.hasNext();) {
            Set<String> values1 = (Set) it.next();
            // if there is only one result, drop it
            if (values1.size() == 1) {
                if (false && SHOW_DEBUG) {
                    String item = values1.iterator().next();
                    System.out.println("Skipping: " + item + "\t"
                        + equivalenceClassCollator.getRawCollationKey(item, null));
                }
                continue;
            }
            values.clear();
            values.addAll(values1);
            // if (showDetails) Log.getLog().println(bf.showSetNames(values));
            Iterator chars = values.iterator();
            // the lowest value is the exemplar value, so use it as the base
            String target = (String) chars.next();
            if (SHOW_DEBUG) {
                System.out.println("Target: <" + target + ">\t " + Utility.hex(target) + "\t"
                    + equivalenceClassCollator.getRawCollationKey(target, null));
            }
            while (chars.hasNext()) {
                String source = (String) chars.next();
                mapping.put(source, target);
                if (SHOW_DEBUG) {
                    System.out.println("\tSource: <" + source + ">\t " + Utility.hex(source) + "\t"
                        + equivalenceClassCollator.getRawCollationKey(source, null));
                }
            }
            // for (Iterator it2 = values.iterator(); it.hasNext();) {
            // bf.
            // }
            count++;
            countMapped += values.size() - 1;
        }
        return mapping;
        // // convert mapping to UnicodeMap
        // Set problems = new TreeSet();
        // Folder folder = new Folder();
        // //folder.put('\u2215', "/");
        //
        // for (Iterator it = mapping.keySet().iterator(); it.hasNext();) {
        // String source = (String) it.next();
        // folder.put(UTF16.charAt(source, 0), (String) mapping.get(source));
        // }
        // // redo folder until it stabilizes
        // // folder.complete();
        //
        // for (Iterator it = problems.iterator(); it.hasNext();) {
        // String source = (String) it.next();
        // String target = folder.fold((String) mapping.get(source));
        // String other = folder.fold(source);
        // if (target.equals(other)) {
        // it.remove();
        // } else {
        // if (showDetails) Log.getLog().println("Couldn't map source " + Utility.escape(source)
        // + "\t" + Utility.escape(target) + "\t" + Utility.escape(other));
        // }
        // }
        // if (showDetails && problems.size() != 0) {
        // Log.getLog().println("Problems");
        // for (Iterator it = problems.iterator(); it.hasNext();) {
        // String item = (String) it.next();
        // //Log.getLog().println(bf.showSetNames(item));
        // //Log.getLog().println("\t-" + bf.showSetNames(reasonMap.get(item)));
        // }
        // }
        //
        // if (showDetails) Log.getLog().println( "\tEquivalence Classes:\t" + count + "\tMapped characters:\t" +
        // countMapped + "\tProblems:\t" + problems.size());
        // return folder;
    }

    VariantFolder caseFolder = new VariantFolder(new CaseVariantFolder());

    VariantFolder.AlternateFetcher COLLATION_FETCHER = new VariantFolder.AlternateFetcher() {
        @Override
        public Set<String> getAlternates(String item, Set<String> output) {
            output.add(item);
            Set set = equivMap.getEquivalences(item);
            if (set != null) {
                output.addAll(set);
            }
            return output;
        }
    };

    private void closeUnderFolding() {
        if (false) return;
        // TODO Generalize
        Set<String> others = new HashSet<>();
        List<Collection<String>> input = new ArrayList<>();
        VariantFolder recursiveFolder = new VariantFolder(COLLATION_FETCHER);
        TreeSet<CharSequence> hack = new TreeSet();
        hack.add("aa");

        while (true) {
            others.clear();
            for (CharSequence item : hack) { // seenSoFar
                if (item.length() == 1) {
                    continue;
                }
                String str = item.toString();
                if (UTF16.countCodePoint(str) <= 1) {
                    continue;
                }
                Set<String> results = recursiveFolder.getClosure(item.toString());
                results.removeAll(seenSoFar);
                Log.logln(item + "\t" + results);
                others.addAll(results);
            }
            if (others.size() == 0) {
                break;
            }
            for (String item : others) {
                addToEquiv(item, item);
            }
        }
    }

    private static UnicodeSet fullExpansions = null;

    static UnicodeSet getFullExpansions() {
        if (fullExpansions == null) addExpansionResults(fullExpansions = new UnicodeSet());
        return fullExpansions;
    }

    private static UnicodeSet addExpansionResults(UnicodeSet fullExpansions) {
        StringBuffer trialString = new StringBuffer();
        Map stringToKey = new TreeMap();
        Map keyToString = new TreeMap();
        Set nfkc = new HashSet();
        for (int i = 0; i < 0x10FFFF; ++i) {
            int cat = UCharacter.getType(i);
            if (cat == UCharacter.UNASSIGNED || cat == UCharacter.PRIVATE_USE || cat == UCharacter.SURROGATE) continue;
            String source = UTF16.valueOf(i);
            nfkc.add(Normalizer.compose(source, true));

            CollationElementIterator x = uca.getCollationElementIterator(source);
            trialString.setLength(0);
            while (true) {
                int element = x.next();
                if (element == CollationElementIterator.NULLORDER) break;
                char primaryOrder = (char) CollationElementIterator.primaryOrder(element);
                if (primaryOrder == 0) continue;
                trialString.append(primaryOrder);
            }
            if (trialString.length() == 0) continue;
            String key = trialString.toString();
            stringToKey.put(source, key);
            String newSource = (String) keyToString.get(key);
            if (newSource == null) {
                keyToString.put(key, source);
            }
        }
        UnicodeSet expansions = new UnicodeSet();
        UnicodeSet contractions = new UnicodeSet();
        try {
            uca.getContractionsAndExpansions(contractions, expansions, true);
        } catch (Exception e1) {
            throw new IllegalArgumentException(e1);
        }

        fullExpansions = new UnicodeSet();
        global: for (UnicodeSetIterator usi = new UnicodeSetIterator(expansions); usi.next();) {
            trialString.setLength(0);
            String source = usi.getString();
            String key = (String) stringToKey.get(source);
            if (key == null || key.length() == 1) continue;
            main: while (key.length() > 0) {
                for (Iterator it = keyToString.entrySet().iterator(); it.hasNext();) {
                    Entry e = (Entry) it.next();
                    String otherKey = (String) e.getKey();
                    if (key.startsWith(otherKey)) {
                        trialString.append((String) e.getValue());
                        key = key.substring(otherKey.length());
                        continue main;
                    }
                }
                System.out.println("Failed with: " + source);
                continue global;
            }
            String result = trialString.toString();
            if (contractions.contains(result) || nfkc.contains(result)) {
                continue global;
            }
            if (SHOW_DEBUG & false) {
                System.out.println("Adding: " + usi.getString() + "\t=>\t" + trialString);
            }
            fullExpansions.add(result);
        }
        fullExpansions.freeze();
        return fullExpansions;
    }

    CanonicalIterator canonicalIterator = new CanonicalIterator("");

    /**
     * Adds items, looking for all canonically equivalent strings as well.
     *
     * @param item
     */
    private void addItems(String item) {
        addItems2(item, item);
        String minNFKD = getMinimalNKFD(item, equivalenceClassCollator);
        if (!minNFKD.equals(item)) {
            addItems2(minNFKD, item);
        }
        canonicalIterator.setSource(item);
        for (String nextItem = canonicalIterator.next(); nextItem != null; nextItem = canonicalIterator.next()) {
            addItems2(nextItem, item);
        }
    }

    /**
     * Adds items, looking for all case-equivalent strings as well.
     *
     * @param item
     * @param original
     */
    private void addItems2(String item, String original) {
        addItems3(item, original);
        for (String nextItem : caseFolder.getClosure(item)) {
            addItems3(nextItem, original);
        }
    }

    private void addItems3(String item, String original) {
        addToEquiv(item, original);
        canonicalIterator.setSource(item);
        for (String newItem = canonicalIterator.next(); newItem != null; newItem = canonicalIterator.next()) {
            addToEquiv(newItem, original);
        }
    }

    Set<CharSequence> seenSoFar = new TreeSet<>();

    private void addToEquiv(String item, String original) {
        if (item.equals("aA")) {
            System.out.println("ouch");
        }
        if (seenSoFar.contains(item)) {
            return;
        }
        seenSoFar.add(item);
        // String norm = Normalizer.compose(item, true);
        // if (UTF16.countCodePoint(norm) < UTF16.countCodePoint(item)) {
        // item = norm;
        // }
        RawCollationKey k = equivalenceClassCollator.getRawCollationKey(item, null);
        equivMap.add(item, k);
        reasonMap.put(item, original);
    }

    static UnicodeSet spaceTatweelAndNSM = new UnicodeSet("[\\u0020\\u0640[:Mn:][:Me:]]");
    static UnicodeSet NSM = new UnicodeSet("[[:Mn:][:Me:]]");

    /**
     * Return the minimal NFKD string that has the same uca key
     *
     * @param item
     * @param k
     * @param ucaWeak
     * @return
     */
    private String getMinimalNKFD(String item, Collator ucaWeak) {
        String nfkd = com.ibm.icu.text.Normalizer.decompose(item, true);
        if (nfkd.startsWith(" ")) {
            if (spaceTatweelAndNSM.containsAll(nfkd)) {
                return item; // fails
            }
        }
        String start = "";
        String end = nfkd;
        while (end.length() != 0) {
            int cp = UTF16.charAt(end, 0);
            String tryEnd = end.substring(UTF16.getCharCount(cp));
            String trial = start + tryEnd;
            if (!ucaWeak.equals(trial, item)) { // retain character
                start += UTF16.valueOf(cp);
            }
            end = tryEnd;
        }
        return start;
    }

}