import it.uniupo.algoTools.MaxHeap;

import java.util.Arrays;

public class FracKnapsack {

    private final double capacity;
    private final double[] volume;
    private final double[] value;

    public FracKnapsack(double capacity, double[] volume, double[] value) {
        this.capacity = capacity;
        this.volume = volume;
        this.value = value;
    }

    private double fracKnapsackImpl(double[] dose, double[] quant) {
        double valTot = 0;
        double remaningSpace = capacity;

        MaxHeap<Integer, Double> maxHeap = new MaxHeap<>();

        for (int i = 0; i < dose.length; ++i) {
            maxHeap.add(i, value[i] / volume[i]);
        }

        while (!maxHeap.isEmpty() && remaningSpace > 0) {
            // Estraggo il materiale con valore unitario massimo
            int extractedMaterial = maxHeap.extractMax();

            //Se posso prendererlo tutto senza riempite lo zaiono lo prendo tutto
            if (remaningSpace >= volume[extractedMaterial]) {
                dose[extractedMaterial] = 1;
                quant[extractedMaterial] = volume[extractedMaterial];
                valTot += value[extractedMaterial];
            }
            //Altrimenti ne prendo una frazione
            else {
                dose[extractedMaterial] = remaningSpace / volume[extractedMaterial];
                quant[extractedMaterial] = remaningSpace;
                valTot += (value[extractedMaterial] * dose[extractedMaterial]);
            }
            remaningSpace -= quant[extractedMaterial];
        }
        return valTot;
    }

    public double maxVal() {
        double[] dose = new double[volume.length];
        double[] quant = new double[volume.length];

        return fracKnapsackImpl(dose, quant);
    }

    public double dose(int i) {
        if (i < 0 || i > volume.length) {
            throw new IllegalArgumentException("Valore di dose inserito errato");
        }
        double[] dose = new double[volume.length];
        double[] quant = new double[volume.length];

        fracKnapsackImpl(dose, quant);
        return dose[i];
    }

    public boolean more(int i, int j) {
        if ((i < 0 || i > volume.length) || (j < 0 || j > volume.length)) {
            throw new IllegalArgumentException("Valore di dose inserito errato");
        }
        double[] dose = new double[volume.length];
        double[] quant = new double[volume.length];

        fracKnapsackImpl(dose, quant);
        return quant[i] > quant[j];
    }
}