CODEWITHSUNDEEP
javajavafxbin-packing
user3063257
user3063257

Reputation: 129

First-Fit Bin Packing Algorithm Skipping Numbers

I'm trying to do First-Fit bin packing. This is the code I've written with explanations for each line as comments:

private void runFirstFit(ActionEvent event) {
    // The counters
    int i;
    int j = 0;

    // The boolean
    packingComplete = false;

    // Declare an arrayList from the numbers the user has entered
    ArrayList<Integer> numbers = new ArrayList(6);

    // Add numbers into the array from input (using a loop)
    for (i = 0; i < 6; i++) {
        numbers.add(parseInt(getNumber(i)));
    }

    // - Main packing algorithm starts here -
    // Iterate through arraylist and get next number
    Iterator<Integer> iterator = numbers.iterator();

    // While there are still numbers left, try and add to bins
    while (iterator.hasNext()) {
        // Number(s) still exist in the list
        // Check if number can fit inside bin
        System.out.println("Number currently in queue: " + iterator.next());

        if (canNumberFitInsideBin(j, iterator.next())) {
            // Put number inside bin
            bin[j] += String.valueOf(iterator.next()) + ", ";

            System.out.println("Number added to bin " + j);
        } else {
            // Bin is full, move to the next bin (increment counter)
            j++;

            // Put number inside that bin
            bin[j] += String.valueOf(iterator.next()) + ", ";

            System.out.println("Counter incremented");
        }
    }

    // Update all labels
    updateAllBinLabels();
}

Basically, the getNumber(i) part is a function that returns a number. I am using the loop to add the actual numbers (6 of them, to be more specific) into the ArrayList called "numbers".

I've tried printing out the number at each stage and seeing which number it's dealing with - but it seems that it just randomly skips some of the numbers for no reason. For example with an ArrayList input of 1,2,3,4,5,6 the first number it adds to bin[0] is 3 (which should be 1) and then it also adds 6 to bin[0] and kind of ignores all the other numbers and going to the next bin array.

Can anyone spot what I'm doing wrong?

Thanks

Upvotes: 0

Views: 2405

Answers (1)

Dylan
Dylan

Reputation: 540

The most obvious problem is that iterator.next() should only be called once per entry into the loop. Each time you call it, you are moving forward in your list. You need to call it once and keep it in a temporary variable at the top of the loop.

Also you should probably check that the number can fit in the next bin in the else, unless you know none of the values are ever bigger than your bin size.

Upvotes: 2

Related Questions