@Test public void testMaxSizeZero() throws Exception { List<WorkUnit> workUnitList = Lists.newArrayList( getWorkUnitWithWeight(1), getWorkUnitWithWeight(1)); List<WorkUnit> multiWorkUnits = new WorstFitDecreasingBinPacking(0).pack(workUnitList, weighter); Assert.assertEquals(multiWorkUnits.size(), 2); Assert.assertEquals(workUnitList, multiWorkUnits); }
@Override @OverridingMethodsMustInvokeSuper public List<WorkUnit> pack(List<WorkUnit> workUnitsIn, WorkUnitWeighter weighter) { if (this.maxWeightPerUnit <= 0) { return workUnitsIn; } List<WorkUnit> workUnits = Lists.newArrayList(workUnitsIn); long smallUnitSize = 0; int largeUnits = 0; for (WorkUnit workUnit : workUnits) { long weight = weighter.weight(workUnit); if (weight <= this.maxWeightPerUnit) { smallUnitSize += weight; } else { largeUnits++; } } int estimateByWeight = largeUnits + (int) ((smallUnitSize - 1) / this.maxWeightPerUnit) + 1; int estimatedMultiWorkUnits = Math.min(estimateByWeight, workUnits.size()); MinMaxPriorityQueue<MultiWorkUnit> pQueue = MinMaxPriorityQueue.orderedBy(new MultiWorkUnitComparator()).create(); for (int i = 0; i < estimatedMultiWorkUnits; i++) { pQueue.add(MultiWorkUnit.createEmpty()); } Collections.sort(workUnits, Collections.reverseOrder(new WeightComparator(weighter))); for (WorkUnit workUnit : workUnits) { MultiWorkUnit lightestMultiWorkUnit = pQueue.peek(); long weight = Math.max(1, weighter.weight(workUnit)); long multiWorkUnitWeight = getMultiWorkUnitWeight(lightestMultiWorkUnit); if (multiWorkUnitWeight == 0 || (weight + multiWorkUnitWeight <= this.maxWeightPerUnit && weight + multiWorkUnitWeight > multiWorkUnitWeight)) { addToMultiWorkUnit(lightestMultiWorkUnit, workUnit, weight); pQueue.poll(); pQueue.add(lightestMultiWorkUnit); } else { MultiWorkUnit newMultiWorkUnit = MultiWorkUnit.createEmpty(); addToMultiWorkUnit(newMultiWorkUnit, workUnit, weight); pQueue.add(newMultiWorkUnit); } } return Lists.<WorkUnit> newArrayList(Iterables.filter(pQueue, new Predicate<MultiWorkUnit>() { @Override @edu.umd.cs.findbugs.annotations.SuppressWarnings( value="NP_PARAMETER_MUST_BE_NONNULL_BUT_MARKED_AS_NULLABLE", justification="Allowing nullable values") public boolean apply(@Nullable MultiWorkUnit input) { return getMultiWorkUnitWeight(input) > 0; } })); }
WorstFitDecreasingBinPacking implements WorkUnitBinPacker { @Override @OverridingMethodsMustInvokeSuper public List<WorkUnit> pack(List<WorkUnit> workUnitsIn, WorkUnitWeighter weighter) { if (this.maxWeightPerUnit <= 0) { return workUnitsIn; } List<WorkUnit> workUnits = Lists.newArrayList(workUnitsIn); long smallUnitSize = 0; int largeUnits = 0; for (WorkUnit workUnit : workUnits) { long weight = weighter.weight(workUnit); if (weight <= this.maxWeightPerUnit) { smallUnitSize += weight; } else { largeUnits++; } } int estimateByWeight = largeUnits + (int) ((smallUnitSize - 1) / this.maxWeightPerUnit) + 1; int estimatedMultiWorkUnits = Math.min(estimateByWeight, workUnits.size()); MinMaxPriorityQueue<MultiWorkUnit> pQueue = MinMaxPriorityQueue.orderedBy(new MultiWorkUnitComparator()).create(); for (int i = 0; i < estimatedMultiWorkUnits; i++) { pQueue.add(MultiWorkUnit.createEmpty()); } Collections.sort(workUnits, Collections.reverseOrder(new WeightComparator(weighter))); for (WorkUnit workUnit : workUnits) { MultiWorkUnit lightestMultiWorkUnit = pQueue.peek(); long weight = Math.max(1, weighter.weight(workUnit)); long multiWorkUnitWeight = getMultiWorkUnitWeight(lightestMultiWorkUnit); if (multiWorkUnitWeight == 0 || (weight + multiWorkUnitWeight <= this.maxWeightPerUnit && weight + multiWorkUnitWeight > multiWorkUnitWeight)) { addToMultiWorkUnit(lightestMultiWorkUnit, workUnit, weight); pQueue.poll(); pQueue.add(lightestMultiWorkUnit); } else { MultiWorkUnit newMultiWorkUnit = MultiWorkUnit.createEmpty(); addToMultiWorkUnit(newMultiWorkUnit, workUnit, weight); pQueue.add(newMultiWorkUnit); } } return Lists.<WorkUnit> newArrayList(Iterables.filter(pQueue, new Predicate<MultiWorkUnit>() { @Override @edu.umd.cs.findbugs.annotations.SuppressWarnings( value="NP_PARAMETER_MUST_BE_NONNULL_BUT_MARKED_AS_NULLABLE", justification="Allowing nullable values") public boolean apply(@Nullable MultiWorkUnit input) { return getMultiWorkUnitWeight(input) > 0; } })); } }
WorstFitDecreasingBinPacking implements WorkUnitBinPacker { @Override @OverridingMethodsMustInvokeSuper public List<WorkUnit> pack(List<WorkUnit> workUnitsIn, WorkUnitWeighter weighter) { if (this.maxWeightPerUnit <= 0) { return workUnitsIn; } List<WorkUnit> workUnits = Lists.newArrayList(workUnitsIn); long smallUnitSize = 0; int largeUnits = 0; for (WorkUnit workUnit : workUnits) { long weight = weighter.weight(workUnit); if (weight <= this.maxWeightPerUnit) { smallUnitSize += weight; } else { largeUnits++; } } int estimateByWeight = largeUnits + (int) ((smallUnitSize - 1) / this.maxWeightPerUnit) + 1; int estimatedMultiWorkUnits = Math.min(estimateByWeight, workUnits.size()); MinMaxPriorityQueue<MultiWorkUnit> pQueue = MinMaxPriorityQueue.orderedBy(new MultiWorkUnitComparator()).create(); for (int i = 0; i < estimatedMultiWorkUnits; i++) { pQueue.add(MultiWorkUnit.createEmpty()); } Collections.sort(workUnits, Collections.reverseOrder(new WeightComparator(weighter))); for (WorkUnit workUnit : workUnits) { MultiWorkUnit lightestMultiWorkUnit = pQueue.peek(); long weight = Math.max(1, weighter.weight(workUnit)); long multiWorkUnitWeight = getMultiWorkUnitWeight(lightestMultiWorkUnit); if (multiWorkUnitWeight == 0 || (weight + multiWorkUnitWeight <= this.maxWeightPerUnit && weight + multiWorkUnitWeight > multiWorkUnitWeight)) { addToMultiWorkUnit(lightestMultiWorkUnit, workUnit, weight); pQueue.poll(); pQueue.add(lightestMultiWorkUnit); } else { MultiWorkUnit newMultiWorkUnit = MultiWorkUnit.createEmpty(); addToMultiWorkUnit(newMultiWorkUnit, workUnit, weight); pQueue.add(newMultiWorkUnit); } } return Lists.<WorkUnit> newArrayList(Iterables.filter(pQueue, new Predicate<MultiWorkUnit>() { @Override @edu.umd.cs.findbugs.annotations.SuppressWarnings( value="NP_PARAMETER_MUST_BE_NONNULL_BUT_MARKED_AS_NULLABLE", justification="Allowing nullable values") public boolean apply(@Nullable MultiWorkUnit input) { return getMultiWorkUnitWeight(input) > 0; } })); }  }
WorstFitDecreasingBinPacking implements WorkUnitBinPacker { @Override @OverridingMethodsMustInvokeSuper public List<WorkUnit> pack(List<WorkUnit> workUnitsIn, WorkUnitWeighter weighter) { if (this.maxWeightPerUnit <= 0) { return workUnitsIn; } List<WorkUnit> workUnits = Lists.newArrayList(workUnitsIn); long smallUnitSize = 0; int largeUnits = 0; for (WorkUnit workUnit : workUnits) { long weight = weighter.weight(workUnit); if (weight <= this.maxWeightPerUnit) { smallUnitSize += weight; } else { largeUnits++; } } int estimateByWeight = largeUnits + (int) ((smallUnitSize - 1) / this.maxWeightPerUnit) + 1; int estimatedMultiWorkUnits = Math.min(estimateByWeight, workUnits.size()); MinMaxPriorityQueue<MultiWorkUnit> pQueue = MinMaxPriorityQueue.orderedBy(new MultiWorkUnitComparator()).create(); for (int i = 0; i < estimatedMultiWorkUnits; i++) { pQueue.add(MultiWorkUnit.createEmpty()); } Collections.sort(workUnits, Collections.reverseOrder(new WeightComparator(weighter))); for (WorkUnit workUnit : workUnits) { MultiWorkUnit lightestMultiWorkUnit = pQueue.peek(); long weight = Math.max(1, weighter.weight(workUnit)); long multiWorkUnitWeight = getMultiWorkUnitWeight(lightestMultiWorkUnit); if (multiWorkUnitWeight == 0 || (weight + multiWorkUnitWeight <= this.maxWeightPerUnit && weight + multiWorkUnitWeight > multiWorkUnitWeight)) { addToMultiWorkUnit(lightestMultiWorkUnit, workUnit, weight); pQueue.poll(); pQueue.add(lightestMultiWorkUnit); } else { MultiWorkUnit newMultiWorkUnit = MultiWorkUnit.createEmpty(); addToMultiWorkUnit(newMultiWorkUnit, workUnit, weight); pQueue.add(newMultiWorkUnit); } } return Lists.<WorkUnit> newArrayList(Iterables.filter(pQueue, new Predicate<MultiWorkUnit>() { @Override @edu.umd.cs.findbugs.annotations.SuppressWarnings( value="NP_PARAMETER_MUST_BE_NONNULL_BUT_MARKED_AS_NULLABLE", justification="Allowing nullable values") public boolean apply(@Nullable MultiWorkUnit input) { return getMultiWorkUnitWeight(input) > 0; } })); }  @Override @OverridingMethodsMustInvokeSuper List<WorkUnit> pack(List<WorkUnit> workUnitsIn, WorkUnitWeighter weighter); }
WorstFitDecreasingBinPacking implements WorkUnitBinPacker { @Override @OverridingMethodsMustInvokeSuper public List<WorkUnit> pack(List<WorkUnit> workUnitsIn, WorkUnitWeighter weighter) { if (this.maxWeightPerUnit <= 0) { return workUnitsIn; } List<WorkUnit> workUnits = Lists.newArrayList(workUnitsIn); long smallUnitSize = 0; int largeUnits = 0; for (WorkUnit workUnit : workUnits) { long weight = weighter.weight(workUnit); if (weight <= this.maxWeightPerUnit) { smallUnitSize += weight; } else { largeUnits++; } } int estimateByWeight = largeUnits + (int) ((smallUnitSize - 1) / this.maxWeightPerUnit) + 1; int estimatedMultiWorkUnits = Math.min(estimateByWeight, workUnits.size()); MinMaxPriorityQueue<MultiWorkUnit> pQueue = MinMaxPriorityQueue.orderedBy(new MultiWorkUnitComparator()).create(); for (int i = 0; i < estimatedMultiWorkUnits; i++) { pQueue.add(MultiWorkUnit.createEmpty()); } Collections.sort(workUnits, Collections.reverseOrder(new WeightComparator(weighter))); for (WorkUnit workUnit : workUnits) { MultiWorkUnit lightestMultiWorkUnit = pQueue.peek(); long weight = Math.max(1, weighter.weight(workUnit)); long multiWorkUnitWeight = getMultiWorkUnitWeight(lightestMultiWorkUnit); if (multiWorkUnitWeight == 0 || (weight + multiWorkUnitWeight <= this.maxWeightPerUnit && weight + multiWorkUnitWeight > multiWorkUnitWeight)) { addToMultiWorkUnit(lightestMultiWorkUnit, workUnit, weight); pQueue.poll(); pQueue.add(lightestMultiWorkUnit); } else { MultiWorkUnit newMultiWorkUnit = MultiWorkUnit.createEmpty(); addToMultiWorkUnit(newMultiWorkUnit, workUnit, weight); pQueue.add(newMultiWorkUnit); } } return Lists.<WorkUnit> newArrayList(Iterables.filter(pQueue, new Predicate<MultiWorkUnit>() { @Override @edu.umd.cs.findbugs.annotations.SuppressWarnings( value="NP_PARAMETER_MUST_BE_NONNULL_BUT_MARKED_AS_NULLABLE", justification="Allowing nullable values") public boolean apply(@Nullable MultiWorkUnit input) { return getMultiWorkUnitWeight(input) > 0; } })); }  @Override @OverridingMethodsMustInvokeSuper List<WorkUnit> pack(List<WorkUnit> workUnitsIn, WorkUnitWeighter weighter); static final String TOTAL_MULTI_WORK_UNIT_WEIGHT; }