/*

 * Copyright (c) 2002, 2010, 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 com.sun.java.util.jar.pack;

import java.io.ByteArrayOutputStream;

import java.io.IOException;

import java.io.OutputStream;

import java.util.ArrayList;

import java.util.Collections;

import java.util.HashSet;

import java.util.Iterator;

import java.util.List;

import java.util.Random;

import java.util.Set;

import java.util.zip.Deflater;

import java.util.zip.DeflaterOutputStream;

import static com.sun.java.util.jar.pack.Constants.*;

/**

 * Heuristic chooser of basic encodings.

 * Runs "zip" to measure the apparent information content after coding.

 * @author John Rose

 */

class CodingChooser {

    int verbose;

    int effort;

    boolean optUseHistogram = true;

    boolean optUsePopulationCoding = true;

    boolean optUseAdaptiveCoding = true;

    boolean disablePopCoding;

    boolean disableRunCoding;

    boolean topLevel = true;

    // Derived from effort; >1 (<1) means try more (less) experiments

    // when looking to beat a best score.

    double fuzz;

    Coding[] allCodingChoices;

    Choice[] choices;

    ByteArrayOutputStream context;

    CodingChooser popHelper;

    CodingChooser runHelper;

    Random stress;  // If not null, stress mode oracle.

    // Element in sorted set of coding choices:

    static

    class Choice {

        final Coding coding;

        final int index;       // index in choices

        final int[] distance;  // cache of distance

        Choice(Coding coding, int index, int[] distance) {

            this.coding   = coding;

            this.index    = index;

            this.distance = distance;

        }

        // These variables are reset and reused:

        int searchOrder; // order in which it is checked

        int minDistance; // min distance from already-checked choices

        int zipSize;     // size of encoding in sample, zipped output

        int byteSize;    // size of encoding in sample (debug only)

        int histSize;    // size of encoding, according to histogram

        void reset() {

            searchOrder = Integer.MAX_VALUE;

            minDistance = Integer.MAX_VALUE;

            zipSize = byteSize = histSize = -1;

        }

        boolean isExtra() {

            return index < 0;

        }

        public String toString() {

            return stringForDebug();

        }

        private String stringForDebug() {

            String s = "";

            if (searchOrder < Integer.MAX_VALUE)

                s += " so: "+searchOrder;

            if (minDistance < Integer.MAX_VALUE)

                s += " md: "+minDistance;

            if (zipSize > 0)

                s += " zs: "+zipSize;

            if (byteSize > 0)

                s += " bs: "+byteSize;

            if (histSize > 0)

                s += " hs: "+histSize;

            return "Choice["+index+"] "+s+" "+coding;

        }

    }

    CodingChooser(int effort, Coding[] allCodingChoices) {

        PropMap p200 = Utils.currentPropMap();

        if (p200 != null) {

            this.verbose

                = Math.max(p200.getInteger(Utils.DEBUG_VERBOSE),

                           p200.getInteger(Utils.COM_PREFIX+"verbose.coding"));

            this.optUseHistogram

                = !p200.getBoolean(Utils.COM_PREFIX+"no.histogram");

            this.optUsePopulationCoding

                = !p200.getBoolean(Utils.COM_PREFIX+"no.population.coding");

            this.optUseAdaptiveCoding

                = !p200.getBoolean(Utils.COM_PREFIX+"no.adaptive.coding");

            int lstress

                = p200.getInteger(Utils.COM_PREFIX+"stress.coding");

            if (lstress != 0)

                this.stress = new Random(lstress);

        }

        this.effort = effort;

        // The following line "makes sense" but is too much

        // work for a simple heuristic.

        //if (effort > 5)  zipDef.setLevel(effort);

        this.allCodingChoices = allCodingChoices;

        // If effort = 9, look carefully at any solution

        // whose initial metrics are within 1% of the best

        // so far.  If effort = 1, look carefully only at

        // solutions whose initial metrics promise a 1% win.

        this.fuzz = 1 + (0.0025 * (effort-MID_EFFORT));

        int nc = 0;

        for (int i = 0; i < allCodingChoices.length; i++) {

            if (allCodingChoices[i] == null)  continue;

            nc++;

        }

        choices = new Choice[nc];

        nc = 0;

        for (int i = 0; i < allCodingChoices.length; i++) {

            if (allCodingChoices[i] == null)  continue;

            int[] distance = new int[choices.length];

            choices[nc++] = new Choice(allCodingChoices[i], i, distance);

        }

        for (int i = 0; i < choices.length; i++) {

            Coding ci = choices[i].coding;

            assert(ci.distanceFrom(ci) == 0);

            for (int j = 0; j < i; j++) {

                Coding cj = choices[j].coding;

                int dij = ci.distanceFrom(cj);

                assert(dij > 0);

                assert(dij == cj.distanceFrom(ci));

                choices[i].distance[j] = dij;

                choices[j].distance[i] = dij;

            }

        }

    }

    Choice makeExtraChoice(Coding coding) {

        int[] distance = new int[choices.length];

        for (int i = 0; i < distance.length; i++) {

            Coding ci = choices[i].coding;

            int dij = coding.distanceFrom(ci);

            assert(dij > 0);

            assert(dij == ci.distanceFrom(coding));

            distance[i] = dij;

        }

        Choice c = new Choice(coding, -1, distance);

        c.reset();

        return c;

    }

    ByteArrayOutputStream getContext() {

        if (context == null)

            context = new ByteArrayOutputStream(1 << 16);

        return context;

    }

    // These variables are reset and reused:

    private int[] values;

    private int start, end;  // slice of values

    private int[] deltas;

    private int min, max;

    private Histogram vHist;

    private Histogram dHist;

    private int searchOrder;

    private Choice regularChoice;

    private Choice bestChoice;

    private CodingMethod bestMethod;

    private int bestByteSize;

    private int bestZipSize;

    private int targetSize;   // fuzzed target byte size

    private void reset(int[] values, int start, int end) {

        this.values = values;

        this.start = start;

        this.end = end;

        this.deltas = null;

        this.min = Integer.MAX_VALUE;

        this.max = Integer.MIN_VALUE;

        this.vHist = null;

        this.dHist = null;

        this.searchOrder = 0;

        this.regularChoice = null;

        this.bestChoice = null;

        this.bestMethod = null;

        this.bestZipSize = Integer.MAX_VALUE;

        this.bestByteSize = Integer.MAX_VALUE;

        this.targetSize = Integer.MAX_VALUE;

    }

    public static final int MIN_EFFORT = 1;

    public static final int MID_EFFORT = 5;

    public static final int MAX_EFFORT = 9;

    public static final int POP_EFFORT = MID_EFFORT-1;

    public static final int RUN_EFFORT = MID_EFFORT-2;

    public static final int BYTE_SIZE = 0;

    public static final int ZIP_SIZE = 1;

    CodingMethod choose(int[] values, int start, int end, Coding regular, int[] sizes) {

        // Save the value array

        reset(values, start, end);

        if (effort <= MIN_EFFORT || start >= end) {

            if (sizes != null) {

                int[] computed = computeSizePrivate(regular);

                sizes[BYTE_SIZE] = computed[BYTE_SIZE];

                sizes[ZIP_SIZE]  = computed[ZIP_SIZE];

            }

            return regular;

        }

        if (optUseHistogram) {

            getValueHistogram();

            getDeltaHistogram();

        }

        for (int i = start; i < end; i++) {

            int val = values[i];

            if (min > val)  min = val;

            if (max < val)  max = val;

        }

        // Find all the preset choices that might be worth looking at:

        int numChoices = markUsableChoices(regular);

        if (stress != null) {

            // Make a random choice.

            int rand = stress.nextInt(numChoices*2 + 4);

            CodingMethod coding = null;

            for (int i = 0; i < choices.length; i++) {

                Choice c = choices[i];

                if (c.searchOrder >= 0 && rand-- == 0) {

                    coding = c.coding;

                    break;

                }

            }

            if (coding == null) {

                if ((rand & 7) != 0) {

                    coding = regular;

                } else {

                    // Pick a totally random coding 6% of the time.

                    coding = stressCoding(min, max);

                }

            }

            if (!disablePopCoding

                && optUsePopulationCoding

                && effort >= POP_EFFORT) {

                coding = stressPopCoding(coding);

            }

            if (!disableRunCoding

                && optUseAdaptiveCoding

                && effort >= RUN_EFFORT) {

                coding = stressAdaptiveCoding(coding);

            }

            return coding;

        }

        double searchScale = 1.0;

        for (int x = effort; x < MAX_EFFORT; x++) {

            searchScale /= 1.414;  // every 2 effort points doubles work

        }

        int searchOrderLimit = (int)Math.ceil( numChoices * searchScale );

        // Start by evaluating the "regular" choice.

        bestChoice = regularChoice;

        evaluate(regularChoice);

        int maxd = updateDistances(regularChoice);

        // save these first-cut numbers for later

        int zipSize1 = bestZipSize;

        int byteSize1 = bestByteSize;

        if (regularChoice.coding == regular && topLevel) {

            // Give credit for being the default; no band header is needed.

            // Rather than increasing every other size value by the band

            // header amount, we decrement this one metric, to give it an edge.

            // Decreasing zipSize by a byte length is conservatively correct,

            // especially considering that the escape byte is not likely to

            // zip well with other bytes in the band.

            int X = BandStructure.encodeEscapeValue(_meta_canon_max, regular);

            if (regular.canRepresentSigned(X)) {

                int Xlen = regular.getLength(X);  // band coding header

                //regularChoice.histSize -= Xlen; // keep exact byteSize

                //regularChoice.byteSize -= Xlen; // keep exact byteSize

                regularChoice.zipSize -= Xlen;

                bestByteSize = regularChoice.byteSize;

                bestZipSize = regularChoice.zipSize;

            }

        }

        int dscale = 1;

        // Continually select a new choice to evaluate.

        while (searchOrder < searchOrderLimit) {

            Choice nextChoice;

            if (dscale > maxd)  dscale = 1;  // cycle dscale values!

            int dhi = maxd / dscale;

            int dlo = maxd / (dscale *= 2) + 1;

            nextChoice = findChoiceNear(bestChoice, dhi, dlo);

            if (nextChoice == null)  continue;

            assert(nextChoice.coding.canRepresent(min, max));

            evaluate(nextChoice);

            int nextMaxd = updateDistances(nextChoice);

            if (nextChoice == bestChoice) {

                maxd = nextMaxd;

                if (verbose > 5)  Utils.log.info("maxd = "+maxd);

            }

        }

        // Record best "plain coding" choice.

        Coding plainBest = bestChoice.coding;

        assert(plainBest == bestMethod);

        if (verbose > 2) {

            Utils.log.info("chooser: plain result="+bestChoice+" after "+bestChoice.searchOrder+" rounds, "+(regularChoice.zipSize-bestZipSize)+" fewer bytes than regular "+regular);

        }

        bestChoice = null;

        if (!disablePopCoding

            && optUsePopulationCoding

            && effort >= POP_EFFORT

            && bestMethod instanceof Coding) {

            tryPopulationCoding(plainBest);

        }

        if (!disableRunCoding

            && optUseAdaptiveCoding

            && effort >= RUN_EFFORT

            && bestMethod instanceof Coding) {

            tryAdaptiveCoding(plainBest);

        }

        // Pass back the requested information:

        if (sizes != null) {

            sizes[BYTE_SIZE] = bestByteSize;

            sizes[ZIP_SIZE]  = bestZipSize;

        }

        if (verbose > 1) {

            Utils.log.info("chooser: result="+bestMethod+" "+

                             (zipSize1-bestZipSize)+

                             " fewer bytes than regular "+regular+

                             "; win="+pct(zipSize1-bestZipSize, zipSize1));

        }

        CodingMethod lbestMethod = this.bestMethod;

        reset(null, 0, 0);  // for GC

        return lbestMethod;

    }

    CodingMethod choose(int[] values, int start, int end, Coding regular) {

        return choose(values, start, end, regular, null);

    }

    CodingMethod choose(int[] values, Coding regular, int[] sizes) {

        return choose(values, 0, values.length, regular, sizes);

    }

    CodingMethod choose(int[] values, Coding regular) {

        return choose(values, 0, values.length, regular, null);

    }

    private int markUsableChoices(Coding regular) {

        int numChoices = 0;

        for (int i = 0; i < choices.length; i++) {

            Choice c = choices[i];

            c.reset();

            if (!c.coding.canRepresent(min, max)) {

                // Mark as already visited:

                c.searchOrder = -1;

                if (verbose > 1 && c.coding == regular) {

                    Utils.log.info("regular coding cannot represent ["+min+".."+max+"]: "+regular);

                }

                continue;

            }

            if (c.coding == regular)

                regularChoice = c;

            numChoices++;

        }

        if (regularChoice == null && regular.canRepresent(min, max)) {

            regularChoice = makeExtraChoice(regular);

            if (verbose > 1) {

                Utils.log.info("*** regular choice is extra: "+regularChoice.coding);

            }

        }

        if (regularChoice == null) {

            for (int i = 0; i < choices.length; i++) {

                Choice c = choices[i];

                if (c.searchOrder != -1) {

                    regularChoice = c;  // arbitrary pick

                    break;

                }

            }

            if (verbose > 1) {

                Utils.log.info("*** regular choice does not apply "+regular);

                Utils.log.info("    using instead "+regularChoice.coding);

            }

        }

        if (verbose > 2) {

            Utils.log.info("chooser: #choices="+numChoices+" ["+min+".."+max+"]");

            if (verbose > 4) {

                for (int i = 0; i < choices.length; i++) {

                    Choice c = choices[i];

                    if (c.searchOrder >= 0)

                        Utils.log.info("  "+c);

                }

            }

        }

        return numChoices;

    }

    // Find an arbitrary choice at least dlo away from a previously

    // evaluated choices, and at most dhi.  Try also to regulate its

    // min distance to all previously evaluated choices, in this range.

    private Choice findChoiceNear(Choice near, int dhi, int dlo) {

        if (verbose > 5)

            Utils.log.info("findChoice "+dhi+".."+dlo+" near: "+near);

        int[] distance = near.distance;

        Choice found = null;

        for (int i = 0; i < choices.length; i++) {

            Choice c = choices[i];

            if (c.searchOrder < searchOrder)

                continue;  // already searched

            // Distance from "near" guy must be in bounds:

            if (distance[i] >= dlo && distance[i] <= dhi) {

                // Try also to keep min-distance from other guys in bounds:

                if (c.minDistance >= dlo && c.minDistance <= dhi) {

                    if (verbose > 5)

                        Utils.log.info("findChoice => good "+c);

                    return c;

                }

                found = c;

            }

        }

        if (verbose > 5)

            Utils.log.info("findChoice => found "+found);

        return found;

    }

    private void evaluate(Choice c) {

        assert(c.searchOrder == Integer.MAX_VALUE);

        c.searchOrder = searchOrder++;

        boolean mustComputeSize;

        if (c == bestChoice || c.isExtra()) {

            mustComputeSize = true;

        } else if (optUseHistogram) {

            Histogram hist = getHistogram(c.coding.isDelta());

            c.histSize = (int)Math.ceil(hist.getBitLength(c.coding) / 8);

            c.byteSize = c.histSize;

            mustComputeSize = (c.byteSize <= targetSize);

        } else {

            mustComputeSize = true;

        }

        if (mustComputeSize) {

            int[] sizes = computeSizePrivate(c.coding);

            c.byteSize = sizes[BYTE_SIZE];

            c.zipSize  = sizes[ZIP_SIZE];

            if (noteSizes(c.coding, c.byteSize, c.zipSize))

                bestChoice = c;

        }

        if (c.histSize >= 0) {

            assert(c.byteSize == c.histSize);  // models should agree

        }

        if (verbose > 4) {

            Utils.log.info("evaluated "+c);

        }

    }

    private boolean noteSizes(CodingMethod c, int byteSize, int zipSize) {

        assert(zipSize > 0 && byteSize > 0);

        boolean better = (zipSize < bestZipSize);

        if (verbose > 3)

            Utils.log.info("computed size "+c+" "+byteSize+"/zs="+zipSize+

                             ((better && bestMethod != null)?

                              (" better by "+

                               pct(bestZipSize - zipSize, zipSize)): ""));

        if (better) {

            bestMethod = c;

            bestZipSize = zipSize;

            bestByteSize = byteSize;

            targetSize = (int)(byteSize * fuzz);

            return true;

        } else {

            return false;

        }

    }

    private int updateDistances(Choice c) {

        // update all minDistance values in still unevaluated choices

        int[] distance = c.distance;

        int maxd = 0;  // how far is c from everybody else?

        for (int i = 0; i < choices.length; i++) {

            Choice c2 = choices[i];