source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/DBL/DeepestBottomLeftFunctions.cs @ 9593

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.PackingPlan;
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 DeepestBottomLeftFunctions {

    public static ObservableList<BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> DeepestLeftBottomPacking(MultiComponentVectorEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> 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, ThreeDimensionalPacking> itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
      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];
          ThreeDimensionalPacking position = null;

          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, itemPositions, itemMeasures, unpackedItems[i].Rotated);

          if (position == null) {
            position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, itemPositions, itemMeasures, !unpackedItems[i].Rotated);
          }
          if (position == null) {
            remainingItems.Add(unpackedItems[i]);
            solution.PackingInformations[binNr].Remove(unpackedItems[i]);
          } else {
            itemPositions[itemIndex] = position;
            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];
          ThreeDimensionalPacking position = null;

          //Look for space in current bin
          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, itemPositions, itemMeasures, unpackedItems[i].Rotated);

          if (position == null) {
            position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, itemPositions, itemMeasures, !unpackedItems[i].Rotated);
          }
          if (position != null) {
            itemPositions[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 BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>.GetBinPackings(itemPositions, binMeasures, itemMeasures, nrOfBins);
    }

    public static ObservableList<BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> DeepestLeftBottomPacking(GroupingVectorEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> 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, ThreeDimensionalPacking> itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
      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];
          ThreeDimensionalPacking position = null;

          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, itemPositions, itemMeasures);

          if (position == null) {
            remainingItems.Add(itemIndex);
          } else
            itemPositions[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];
          ThreeDimensionalPacking position = null;

          //Look for space in current bin
          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, itemPositions, itemMeasures);

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

      return BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>.GetBinPackings(itemPositions, binMeasures, itemMeasures, nrOfBins);
    }

    public static ObservableList<BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>> DeepestLeftBottomPacking(PackingSequenceEncoding solution, CuboidPackingBin binMeasures, ItemList<CuboidPackingItem> itemMeasures) {
      ObservableDictionary<int, ThreeDimensionalPacking> itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
      int nrOfBins = 1;
      for (int i = 0; i < solution.PackingSequence.Length; i++) {
        var item = itemMeasures[solution.PackingSequence[i]];
        ThreeDimensionalPacking position = null;
        //Look for space in existing bins
        for (int binNr = 0; binNr < nrOfBins; binNr++) {
          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, binNr, item, itemPositions, itemMeasures);
          if (position != null)
            break;
        }
        //Did not find enough space in any of the existing bins => create new bin
        if (position == null) {
          nrOfBins++;
          position = DeepestBottomLeftFunctions.DeepestLeftBottomPosition(binMeasures, nrOfBins - 1, item, itemPositions, itemMeasures);
        }

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

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

      return BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem>.GetBinPackings(itemPositions, binMeasures, itemMeasures, nrOfBins);
    }

    public static ThreeDimensionalPacking DeepestLeftBottomPosition(CuboidPackingBin binMeasures, int binNr, CuboidPackingItem currentItem, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, ItemList<CuboidPackingItem> itemMeasures) {
      return DeepestLeftBottomPosition(binMeasures, binNr, currentItem, itemPositions, itemMeasures, false);
    }
    public static ThreeDimensionalPacking DeepestLeftBottomPosition(CuboidPackingBin binMeasures, int binNr, CuboidPackingItem currentItem, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, ItemList<CuboidPackingItem> itemMeasures, bool rotated) {
      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
      ThreeDimensionalPacking currentPosition = new ThreeDimensionalPacking(binNr, 
        binMeasures.Width - (rotated ? currentItem.Depth : currentItem.Width), 
        binMeasures.Height - currentItem.Height, 
        binMeasures.Depth - (rotated ? currentItem.Width : currentItem.Depth), rotated);
      //Slide the item as far as possible to the bottom
      while (IsPositionFeasible(binMeasures, binNr, currentItem, MoveDown(currentPosition), itemPositions, itemMeasures)
        || IsPositionFeasible(binMeasures, binNr, currentItem, MoveLeft(currentPosition), itemPositions, itemMeasures)
        || IsPositionFeasible(binMeasures, binNr, currentItem, MoveBack(currentPosition), itemPositions, itemMeasures)) {
        //Slide the item as far as possible to the left
          while (IsPositionFeasible(binMeasures, binNr, currentItem, MoveLeft(currentPosition), itemPositions, itemMeasures)
          || IsPositionFeasible(binMeasures, binNr, currentItem, MoveBack(currentPosition), itemPositions, itemMeasures)) {
          //Slide the item as far as possible to the back
            while (IsPositionFeasible(binMeasures, binNr, currentItem, MoveBack(currentPosition), itemPositions, itemMeasures)) {
            currentPosition = MoveBack(currentPosition);
          }
            if (IsPositionFeasible(binMeasures, binNr, currentItem, MoveLeft(currentPosition), itemPositions, itemMeasures))
            currentPosition = MoveLeft(currentPosition);
        }
          if (IsPositionFeasible(binMeasures, binNr, currentItem, MoveDown(currentPosition), itemPositions, itemMeasures))
          currentPosition = MoveDown(currentPosition);
      }

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

    

    public static bool IsPositionFeasible(CuboidPackingBin binMeasures, int binNr, CuboidPackingItem currentItem,
      ThreeDimensionalPacking currentPosition, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, ItemList<CuboidPackingItem> 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 ThreeDimensionalPacking MoveLeft(ThreeDimensionalPacking original) {
      return new ThreeDimensionalPacking(original.AssignedBin, original.X - 1, original.Y, original.Z, original.Rotated);
    }
    private static ThreeDimensionalPacking MoveDown(ThreeDimensionalPacking original) {
      return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y - 1, original.Z, original.Rotated);
    }
    private static ThreeDimensionalPacking MoveBack(ThreeDimensionalPacking original) {
      return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y, original.Z - 1, original.Rotated);
    }

  }
}