source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/2D/BL/BottomLeftFunctions.cs @ 9563

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using HeuristicLab.Collections;
using HeuristicLab.Core;
using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Problems.BinPacking.Dimensions;
using HeuristicLab.Problems.BinPacking.Interfaces;
using HeuristicLab.Problems.BinPacking.PackingBin;
using HeuristicLab.Problems.BinPacking.PackingItem;
using HeuristicLab.Problems.BinPacking.Shapes;

namespace HeuristicLab.Problems.BinPacking.Decoders {
  public static class BottomLeftFunctions {


    public static ObservableDictionary<int, TwoDimensionalPacking> BottomLeftPacking(
      MultiComponentVectorEncoding solution, RectangularPackingBin binMeasures, ItemList<RectangularPackingItem> itemMeasures) {
      int nrOfBins = solution.NrOfBins;

      //Get all indexes of items for every bin according to grouping-vector
      Dictionary<int, List<PackingInformation>> unpackedItemIndexesPerBin = new Dictionary<int, List<PackingInformation>>();

      for (int i = 0; i < nrOfBins; i++) {
        unpackedItemIndexesPerBin[i] = new List<PackingInformation>(solution.PackingInformations[i]);
      }

      ObservableDictionary<int, TwoDimensionalPacking> packingPositions = new ObservableDictionary<int, TwoDimensionalPacking>();
      var remainingItems = new List<PackingInformation>();

      //Iterate over all bin-lists
      for (int binNr = 0; binNr < nrOfBins; binNr++) {
        //Iterate over the current bin-item-list and find feasible positions in the current bin for each item
        var unpackedItems = unpackedItemIndexesPerBin[binNr];
        for (int i = 0; i < unpackedItems.Count; i++) {
          var itemIndex = unpackedItems[i].ItemID;
          var item = itemMeasures[itemIndex];
          TwoDimensionalPacking position = null;

          position = BottomLeftFunctions.BottomLeftPosition(binMeasures, binNr, item, packingPositions, itemMeasures, unpackedItems[i].Rotated);

          if (position == null) {
            position = BottomLeftFunctions.BottomLeftPosition(binMeasures, binNr, item, packingPositions, itemMeasures, !unpackedItems[i].Rotated);
          }
          if (position == null) {
            remainingItems.Add(unpackedItems[i]);
          } else {
            packingPositions[itemIndex] = position;
            solution.PackingInformations[binNr].Remove(unpackedItems[i]);
            solution.PackingInformations[binNr].Find(pi => pi.ItemID == itemIndex).Rotated = position.Rotated;
          }
        }
      }

      //Packing of remaining items
      //Iterate over all bin-lists
      for (int binNr = 0; binNr < nrOfBins && remainingItems.Count > 0; binNr++) {
        var unpackedItems = new List<PackingInformation>(remainingItems);
        for (int i = 0; i < unpackedItems.Count; i++) {
          var itemIndex = unpackedItems[i].ItemID;
          var item = itemMeasures[itemIndex];
          TwoDimensionalPacking position = null;

          //Look for space in current bin
          position = BottomLeftFunctions.BottomLeftPosition(binMeasures, binNr, item, packingPositions, itemMeasures, unpackedItems[i].Rotated);

          if (position == null) {
            position = BottomLeftFunctions.BottomLeftPosition(binMeasures, binNr, item, packingPositions, itemMeasures, !unpackedItems[i].Rotated);
          }
          if (position != null) {
            packingPositions[itemIndex] = position;
            remainingItems.Remove(unpackedItems[i]);
            solution.PackingInformations[binNr].Add(unpackedItems[i]);
            solution.PackingInformations[binNr].Find(pi => pi.ItemID == itemIndex).Rotated = position.Rotated;
          }
        }
        if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
          solution.PackingInformations[nrOfBins] = new ItemList<PackingInformation>();
          nrOfBins++;
        }
      }

      return packingPositions;
    }

    public static ObservableDictionary<int, TwoDimensionalPacking> BottomLeftPacking(
      GroupingVectorEncoding solution, RectangularPackingBin binMeasures, ItemList<RectangularPackingItem> itemMeasures) {

      int nrOfBins = solution.GroupingVector.Max() + 1;

      //Get all indexes of items for every bin according to grouping-vector
      //It is assumed, that at this point the item-indexes are sorted according to their item-size!
      Dictionary<int, List<int>> unpackedItemIndexesPerBin = new Dictionary<int, List<int>>();

      for (int i = 0; i < nrOfBins; i++) {
        unpackedItemIndexesPerBin[i] = solution.GroupingVector
          .Select((Value, Index) => new { Value, Index })
          .Where(temp => temp.Value == i)
          .Select(temp => temp.Index).ToList();
      }

      ObservableDictionary<int, TwoDimensionalPacking> packingPositions = new ObservableDictionary<int, TwoDimensionalPacking>();
      var remainingItems = new List<int>();

      //Iterate over all bin-lists
      for (int binNr = 0; binNr < nrOfBins; binNr++) {
        //Iterate over the current bin-item-list and find feasible positions in the current bin for each item
        var unpackedItems = unpackedItemIndexesPerBin[binNr];
        for (int i = 0; i < unpackedItems.Count; i++) {
          var itemIndex = unpackedItems[i];
          var item = itemMeasures[itemIndex];
          TwoDimensionalPacking position = null;

          //Look for space in current bin
          position = BottomLeftFunctions.BottomLeftPosition(binMeasures, binNr, item, packingPositions, itemMeasures);

          //Did not find enough space in current bin
          if (position == null) {
            remainingItems.Add(itemIndex);
          } else
            packingPositions[itemIndex] = position;
        }
      }

      //Packing of remaining items
      //Iterate over all bin-lists
      for (int binNr = 0; binNr < nrOfBins && remainingItems.Count > 0; binNr++) {
        var unpackedItems = new List<int>(remainingItems);
        for (int i = 0; i < unpackedItems.Count; i++) {
          var itemIndex = unpackedItems[i];
          var item = itemMeasures[itemIndex];
          TwoDimensionalPacking position = null;

          //Look for space in current bin
          position = BottomLeftFunctions.BottomLeftPosition(binMeasures, binNr, item, packingPositions, itemMeasures);

          if (position != null) {
            packingPositions[itemIndex] = position;
            remainingItems.Remove(itemIndex);
            solution.GroupingVector[itemIndex] = binNr;
          }
        }
        if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
          nrOfBins++;
        }
      }

      return packingPositions;
    }

    public static ObservableDictionary<int, TwoDimensionalPacking> BottomLeftPacking(
      PackingSequenceEncoding solution, RectangularPackingBin binMeasures, ItemList<RectangularPackingItem> itemMeasures) {

      ObservableDictionary<int, TwoDimensionalPacking> packingPositions = new ObservableDictionary<int, TwoDimensionalPacking>();
      int nrOfBins = 1;
      for (int i = 0; i < solution.PackingSequence.Length; i++) {
        var item = itemMeasures[solution.PackingSequence[i]];
        TwoDimensionalPacking position = null;
        //Look for space in existing bins
        for (int binNr = 0; binNr < nrOfBins; binNr++) {
          position = BottomLeftFunctions.BottomLeftPosition(binMeasures, binNr, item, packingPositions, itemMeasures);
          if (position != null)
            break;
        }
        //Did not find enough space in any of the existing bins => create new bin
        if (position == null) {
          nrOfBins++;
          position = BottomLeftFunctions.BottomLeftPosition(binMeasures, nrOfBins - 1, item, packingPositions, itemMeasures);
        }

        if (position == null)
          position = new TwoDimensionalPacking(-1, 0, 0);

        packingPositions[solution.PackingSequence[i]] = position;
      }

      return packingPositions;
    }

    private static TwoDimensionalPacking BottomLeftPosition(RectangularPackingBin binMeasures, int binNr, RectangularPackingItem currentItem, ObservableDictionary<int, TwoDimensionalPacking> itemPositions, ItemList<RectangularPackingItem> itemMeasures) {
      return BottomLeftPosition(binMeasures, binNr, currentItem, itemPositions, itemMeasures, false);
    }
    private static TwoDimensionalPacking BottomLeftPosition(RectangularPackingBin binMeasures, int binNr, RectangularPackingItem currentItem, ObservableDictionary<int, TwoDimensionalPacking> itemPositions, ItemList<RectangularPackingItem> itemMeasures, bool rotated) {      
      TwoDimensionalPacking currentPosition = new TwoDimensionalPacking(binNr, 
        binMeasures.Width - (rotated ? currentItem.Height : currentItem.Width), 
        binMeasures.Height - (rotated ? currentItem.Width : currentItem.Height), rotated);
      //Slide the item as far as possible to the left
      while (IsPositionFeasible(binMeasures, binNr, currentItem, MoveLeft(currentPosition), itemPositions, itemMeasures)
        || IsPositionFeasible(binMeasures, binNr, currentItem, MoveDown(currentPosition), itemPositions, itemMeasures)) {
        //Slide the item as far as possible to the bottom
          while (IsPositionFeasible(binMeasures, binNr, currentItem, MoveDown(currentPosition), itemPositions, itemMeasures)) {
          currentPosition = MoveDown(currentPosition);
        }
          if (IsPositionFeasible(binMeasures, binNr, currentItem, MoveLeft(currentPosition), itemPositions, itemMeasures))
          currentPosition = MoveLeft(currentPosition);
      }

      return IsPositionFeasible(binMeasures, binNr, currentItem, currentPosition, itemPositions, itemMeasures) ? currentPosition : null;
    }

    public static bool IsPositionFeasible(RectangularPackingBin binMeasures, int binNr, RectangularPackingItem currentItem,
      TwoDimensionalPacking currentPosition, ObservableDictionary<int, TwoDimensionalPacking> itemPositions, ItemList<RectangularPackingItem> itemMeasures) {
      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the item does not collide with another already packed item
      if (!binMeasures.Encloses(currentPosition, currentItem))
        return false;
      var itemsWithPositions = itemMeasures.
        Select((Value, Index) => new { Value, Index }).
        Where(s => itemPositions.ContainsKey(s.Index)).
        Select((s) => new { Measures = itemMeasures[s.Index], Position = itemPositions[s.Index] });

      foreach (var itemWithPosition in itemsWithPositions) {
        if (itemWithPosition.Position.AssignedBin == binNr && itemWithPosition.Measures.Overlaps(itemWithPosition.Position, currentPosition, currentItem))
          return false;
      }

      return true;
    }

    private static TwoDimensionalPacking MoveLeft(TwoDimensionalPacking original) {
      return new TwoDimensionalPacking(original.AssignedBin, original.X - 1, original.Y, original.Rotated);
    }
    private static TwoDimensionalPacking MoveDown(TwoDimensionalPacking original) {
      return new TwoDimensionalPacking(original.AssignedBin, original.X, original.Y - 1, original.Rotated);
    }

  }
}