package com.bsc36.project11cs.models;

import java.util.List;

/**
 * BackTrack class
 */
public class BackTrack {
    private final Knapsack knapsack;

    public BackTrack(Knapsack knapsack) {
        this.knapsack = knapsack;
    }

    public void startParcelSolver() {
        knapsack.emptyGrid();
        boolean solutionFound = backTrackSearchParcels(knapsack);
        System.out.println(solutionFound ? "Solution found!" : "No solution found.");
    }

    /**
     * Backtrack search for parcels
     * @param knapsack Knapsack
     * @return boolean
     */
    private boolean backTrackSearchParcels(Knapsack knapsack) {
        if (knapsack.isCargoSpaceFull()) {
            //cargoSpace is full of no gaps, a solution is found
            //show GUI solution...
            return true;
        }

        // Retrieve the current parcel character from the input array
        Parcel parcel = knapsack.getRandomParcel(knapsack);
        List<int[][][]> rotations = parcel.getRotations();
        for (int[][][] rotatedShape : rotations){
            parcel.setShape(rotatedShape);
            // Iterate through all possible positions
            for (int x = 0; x < (knapsack.getCargoSpace()).getLength(); x++) {
                for (int y = 0; y < (knapsack.getCargoSpace()).getHeight(); y++) {
                    for (int z = 0; z < (knapsack.getCargoSpace()).getWidth(); z++) {

                            // Check if the parcel can be placed at the current position
                            if (knapsack.canPlaceParcel(rotatedShape, x, y, z)) {
                                System.out.println("Can Place Parcel at: " + x + ", " + y + ", " + z);
                                // If it's valid to place the parcel, add it to the cargo space
                                knapsack.addParcel(parcel, x, y, z);

                                // Check if the piece introduces a single hole
                                if (knapsack.introducesHoles(rotatedShape, x, y, z)) {
                                    knapsack.removeParcel(parcel, x, y, z);
                                    continue;
                                }

                                // Check if the piece introduces larger, but not refillable spaces
                                /*
                                    if (knapsack.introducesNotRefillableSpaces(rotatedShape, x, y, z)) {
                                    knapsack.removeParcel(parcel, x, y, z);
                                    continue;
                                }
                               */

                                // Recurse to the next parcel
                                if (backTrackSearchParcels(knapsack)) {
                                    return true;
                                }

                                // Remove the parcel from the cargo space (backtrack)
                                knapsack.removeParcel(parcel, x, y, z);
                                Runtime.getRuntime().gc();


                            }
                        
                    }
                }
            }
        }
        return false;
    }

    private boolean isValidSolution(Knapsack knapsack) {
        return knapsack.hasNoGaps();
    }
}
