/*
 * Copyright (c) 2004, 2013, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package build.tools.charsetmapping;

import java.io.*;
import java.util.*;


/**
 * Reads a map in the form of a sequence of key/value-expression pairs from the
 * standard input, attempts to construct a hash map that fits within the given
 * table-size and chain-depth constraints, and, if successful, writes source
 * code to the standard output for a subclass of sun.util.PreHashedMap that
 * implements the map.
 *
 * @see sun.util.PreHashedMap
 *
 * @author Mark Reinhold
 */

public class Hasher {

    private PrintStream err = System.err;

    boolean verbose = false;
    List<String> keys = new ArrayList<>();      // Key strings
    List<String> values = new ArrayList<>();    // Value expressions
    String pkg = null;                          // Package prefix for generated class
    String cln = null;                          // Name of generated class
    String vtype = null;                        // Value type
    int maxBits = 11;                           // lg table size
    int maxDepth = 3;                           // Max chain depth
    boolean inner = false;                      // Generating an inner class?
    boolean empty = false;                      // Generating an empty table?

    Object[] ht;                                // Hash table itself
    int nb;                                     // Number of bits (lg table size)
    int md;                                     // Maximum chain depth
    int mask;                                   // Hash-code mask
    int shift;                                  // Hash-code shift size

    int hash(String w) {
        return (w.hashCode() >> shift) & mask;
    }

    // Build a hash table of size 2^nb, shifting the hash code by s bits
    //
    void build(int nb, int s) {

        this.nb = nb;
        this.shift = s;
        int n = 1 << nb;
        this.mask = n - 1;
        ht = new Object[n];
        int nw = keys.size();

        for (int i = 0; i < nw; i++) {
            String w = keys.get(i);
            String v = values.get(i);
            int h = hash(w);
            if (ht[h] == null)
                ht[h] = new Object[] { w, v };
            else
                ht[h] = new Object[] { w, v, ht[h] };
        }

        this.md = 0;
        for (int i = 0; i < n; i++) {
            int d = 1;
            for (Object[] a = (Object[])ht[i];
                 a != null && a.length > 2;
                 a = (Object[])a[2], d++);
            this.md = Math.max(md, d);
        }

    }

    Hasher build() {
        // Iterate through acceptable table sizes
        for (int nb = 2; nb < maxBits; nb++) {
            // Iterate through possible shift sizes
            for (int s = 0; s < (32 - nb); s++) {
                build(nb, s);
                if (verbose)
                    err.println("nb=" + nb + " s=" + s + " md=" + md);
                if (md <= maxDepth) {
                    // Success
                     if (verbose) {
                        if (cln != null)
                            err.print(cln + ": ");
                        err.println("Table size " + (1 << nb) + " (" + nb + " bits)"
                                    + ", shift " + shift
                                    + ", max chain depth " + md);
                    }
                    return this;
                }
            }
        }
        throw new RuntimeException("Cannot find a suitable size"
                                   + " within given constraints");
    }

    // Look for the given key in the hash table
    //
    String get(String k) {
        int h = hash(k);
        Object[] a = (Object[])ht[h];
        for (;;) {
            if (a[0].equals(k))
                return (String)a[1];
            if (a.length < 3)
                return null;
            a = (Object[])a[2];
        }
    }

    // Test that all input keys can be found in the table
    //
    Hasher test() {
        if (verbose)
            err.println();
        for (int i = 0, n = keys.size(); i < n; i++) {
            String w = keys.get(i);
            String v = get(w);
            if (verbose)
                err.println(hash(w) + "\t" + w);
            if (!v.equals(values.get(i)))
                throw new Error("Incorrect value: " + w + " --> "
                                + v + ", should be " + values.get(i));
        }
        return this;
    }

    String ind = "";                    // Indent prefix

    // Generate code for a single table entry
    //
    void genEntry(Object[] a, int depth, PrintStream out) {
        Object v = empty ? null : a[1];
        out.print("new Object[] { \"" + a[0] + "\", " + v);
        if (a.length < 3) {
            out.print(" }");
            return;
        }
        out.println(",");
        out.print(ind + "                     ");
        for (int i = 0; i < depth; i++)
            out.print("    ");
        genEntry((Object[])a[2], depth + 1, out);
        out.print(" }");
    }

    // Generate a PreHashedMap subclass from the computed hash table
    //
    Hasher generate(PrintStream out) throws IOException {
        if (cln == null)
            return this;

        if (inner)
            ind = "    ";

        if (!inner && pkg != null) {
            out.println();
            out.println("package " + pkg + ";");
            out.println();
        }

        if (inner) {
            out.println(ind + "private static final class " + cln);
        } else {
            out.println();
            out.println("public final class " + cln);
        }
        out.println(ind + "    extends sun.util.PreHashedMap<" + vtype +">");
        out.println(ind + "{");

        out.println();
        out.println(ind + "    private static final int ROWS = "
                    + ht.length + ";");
        out.println(ind + "    private static final int SIZE = "
                    + keys.size() + ";");
        out.println(ind + "    private static final int SHIFT = "
                    + shift + ";");
        out.println(ind + "    private static final int MASK = 0x"
                    + Integer.toHexString(mask) + ";");
        out.println();

        out.println(ind + "    " + (inner ? "private " : "public ")
                    + cln + "() {");
        out.println(ind + "        super(ROWS, SIZE, SHIFT, MASK);");
        out.println(ind + "    }");
        out.println();

        out.println(ind + "    protected void init(Object[] ht) {");
        for (int i = 0; i < ht.length; i++) {
            if (ht[i] == null)
                continue;
            Object[] a = (Object[])ht[i];
            out.print(ind + "        ht[" + i + "] = ");
            genEntry(a, 0, out);
            out.println(";");
        }
        out.println(ind + "    }");
        out.println();

        out.println(ind + "}");
        if (inner)
            out.println();

        return this;
    }

    private Hasher(List<String> keys, List<String> values,
                   String pkg, String cln, String vtype,
                   int maxBits, int maxDepth,
                   boolean inner, boolean empty,
                   boolean verbose) {
        this.keys = keys;
        this.values = values;
        this.pkg = pkg;
        this.cln = cln;
        this.vtype = vtype;
        this.maxBits = maxBits;
        this.maxDepth = maxDepth;
        this.inner = inner;
        this.empty = empty;
        this.verbose = verbose;
    }

    public static void genClass(PrintStream out,
                                List<String> keys, List<String> values,
                                String pkg, String cln, String vtype,
                                int maxBits, int maxDepth,
                                boolean inner, boolean empty, boolean verbose)
        throws IOException {
        new Hasher(keys, values, pkg, cln, vtype,
                   maxBits, maxDepth, inner, empty, verbose)
            .build()
            .test()
            .generate(out);
    }
}