source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/3D/EP/ExtremePointsFunctions3D.cs @ 9440

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.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 ExtremePointsFunctions3D {




    public static ObservableDictionary<int, ThreeDimensionalPacking> ExtremePointBasedPacking(ref MultiComponentVectorEncoding solution, 
        ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures) {

      #region Preperations
      int lowerBound = solution.PackingInformations.Max(x => x.AssignedBin);
      int nrOfBins = lowerBound + 1;

      //Get all indexes of items for every bin according to grouping-vector                      
      Dictionary<int, List<PackingInformation>> unpackedItemIndexesPerBin = new Dictionary<int, List<PackingInformation>>();
      Dictionary<int, HashSet<ThreeDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<ThreeDimensionalPacking>>();
      var occupiedPoints = new List<int[, ,]>();

      for (int i = 0; i < nrOfBins; i++) {        
        unpackedItemIndexesPerBin[i] = solution.PackingInformations
          .Where(pi => pi.AssignedBin == i)
          .ToList();

        extremePointsForBin[i] = new HashSet<ThreeDimensionalPacking>();
        extremePointsForBin[i].Add(new ThreeDimensionalPacking(i, 0, 0, 0, false));
        occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
      }

      ObservableDictionary<int, ThreeDimensionalPacking> itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
      var remainingItems = new List<PackingInformation>();

      #endregion Preperations


      //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].ItemIndex;
          var item = itemMeasures[itemIndex];

          extremePointsForBin[binNr] = new HashSet<ThreeDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
          var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
          if (positionFound != null) {
            extremePointsForBin[binNr].Remove(positionFound);
            itemPositions[itemIndex] = positionFound;
            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
          } else
            remainingItems.Add(unpackedItems[i]);
        }
      }


      //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);
        //Iterate over all the remaining items
        for (int i = 0; i < unpackedItems.Count; i++) {
          var itemIndex = unpackedItems[i].ItemIndex;
          var item = itemMeasures[itemIndex];

          extremePointsForBin[binNr] = new HashSet<ThreeDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
          var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions, unpackedItems[i].Rotated);
          if (positionFound != null) {
            extremePointsForBin[binNr].Remove(positionFound);
            itemPositions[itemIndex] = positionFound;
            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
            remainingItems.Remove(unpackedItems[i]);
            if (binNr <= lowerBound) {
              InsertItemgeneAfterLastItemgeneOfUsedBin(ref solution, itemIndex, binNr);
            }
          }
        }
        if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
          extremePointsForBin[nrOfBins] = new HashSet<ThreeDimensionalPacking>();
          extremePointsForBin[nrOfBins].Add(new ThreeDimensionalPacking(nrOfBins, 0, 0, 0, false));
          occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
          nrOfBins++;
        }
      }

      return itemPositions;
    }
    private static void InsertItemgeneAfterLastItemgeneOfUsedBin(ref MultiComponentVectorEncoding solution, int itemIndex, int binNr) {
      var itemgene = solution.PackingInformations.Find(pi => pi.ItemIndex == itemIndex);
      solution.PackingInformations.Remove (itemgene);
      itemgene.AssignedBin = binNr;
      int targetIndex = solution.PackingInformations.FindLastIndex(pi => pi.AssignedBin == binNr);
      solution.PackingInformations.Insert(targetIndex + 1, itemgene);
    }


    public static ObservableDictionary<int, ThreeDimensionalPacking> ExtremePointBasedPacking(GroupingVectorEncoding solution,
        ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures) {

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

      //Get all indexes of items for every bin according to grouping-vector
      Dictionary<int, List<int>> unpackedItemIndexesPerBin = new Dictionary<int, List<int>>();   
      Dictionary<int, HashSet<ThreeDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<ThreeDimensionalPacking>>(); 
      var occupiedPoints = new 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();

        extremePointsForBin[i] = new HashSet<ThreeDimensionalPacking>();
        extremePointsForBin[i].Add(new ThreeDimensionalPacking(i, 0, 0, 0, false));    
        occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
      }

      ObservableDictionary<int, ThreeDimensionalPacking> itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();
      var remainingItems = new List<int>();

      #endregion Preperations

              

      //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];

          extremePointsForBin[binNr] = new HashSet<ThreeDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
          var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
          if (positionFound != null) {
            extremePointsForBin[binNr].Remove(positionFound);
            itemPositions[itemIndex] = positionFound;
            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);
          } else 
            remainingItems.Add(itemIndex);
        }
      }



      //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);
        //Iterate over all the remaining items
        for (int i = 0; i < unpackedItems.Count; i++) {
          var itemIndex = unpackedItems[i];
          var item = itemMeasures[itemIndex];

          extremePointsForBin[binNr] = new HashSet<ThreeDimensionalPacking>(extremePointsForBin[binNr].OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
          var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePointsForBin[binNr], occupiedPoints, itemPositions);
          if (positionFound != null) {
            extremePointsForBin[binNr].Remove(positionFound);
            itemPositions[itemIndex] = positionFound;
            occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
            extremePointsForBin[binNr] = GenerateNewExtremePointsForNewItem(extremePointsForBin[binNr], occupiedPoints, item, positionFound, binMeasures);        
            remainingItems.Remove(itemIndex);
          } 
        }
        if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
          extremePointsForBin[nrOfBins] = new HashSet<ThreeDimensionalPacking>();
          extremePointsForBin[nrOfBins].Add(new ThreeDimensionalPacking(nrOfBins, 0, 0, 0, false));
          occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
          nrOfBins++;
        }
      }

      return itemPositions;
    }


    public static ObservableDictionary<int, ThreeDimensionalPacking> ExtremePointBasedPacking(PackingSequenceEncoding solution, 
        ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures) {

      #region Preperations 
      var itemPositions = new ObservableDictionary<int, ThreeDimensionalPacking>();  
      int nrOfBins = 1;

      var occupiedPoints = new List<int[, ,]>();
      occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);

      HashSet<ThreeDimensionalPacking> extremePoints = new HashSet<ThreeDimensionalPacking>();
      extremePoints.Add(new ThreeDimensionalPacking(0, 0, 0, 0, false));
      #endregion

      foreach (int itemIndex in solution.PackingSequence) {
        var item = itemMeasures[itemIndex];
        extremePoints = new HashSet<ThreeDimensionalPacking>(extremePoints.OrderBy(ep => ep.AssignedBin).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
        var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions);
        if (positionFound != null) {
          extremePoints.Remove(positionFound); 
        }
        else {
          positionFound = new ThreeDimensionalPacking(nrOfBins, 0, 0, 0);
          occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
          nrOfBins++;
        }
        itemPositions[itemIndex] = positionFound;
        occupiedPoints = OccupyPointsForNewItem(occupiedPoints, item, positionFound, itemIndex);
        extremePoints = GenerateNewExtremePointsForNewItem(extremePoints, occupiedPoints, item, positionFound, binMeasures);
      }

      return itemPositions;
    }


    private static ThreeDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures,
        HashSet<ThreeDimensionalPacking> extremePoints, List<int[, ,]> occupiedPoints, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions) {
          return FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions, false);
    }
    private static ThreeDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<CuboidPackingItem> itemMeasures, CuboidPackingBin binMeasures, 
        HashSet<ThreeDimensionalPacking> extremePoints, List<int[,,]> occupiedPoints, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, bool rotated) {

      var itemFromList = itemMeasures[itemIndex];
      CuboidPackingItem item = new CuboidPackingItem(
        rotated ? itemFromList.Depth : itemFromList.Width, 
        itemFromList.Height, 
        rotated ? itemFromList.Width : itemFromList.Depth, 
        itemFromList.TargetBin);

      int epIndex = 0;
      while (epIndex < extremePoints.Count &&
        (!DeepestBottomLeftFunctions.IsPositionFeasible(binMeasures, extremePoints.ElementAt(epIndex).AssignedBin, item, extremePoints.ElementAt(epIndex), itemPositions, itemMeasures) ||
        !IsStaticStable(occupiedPoints[extremePoints.ElementAt(epIndex).AssignedBin], item, extremePoints.ElementAt(epIndex)))) 
      { epIndex++; }

      if (epIndex < extremePoints.Count) {
        var result = extremePoints.ElementAt(epIndex);
        result.Rotated = rotated;
        return result;
      } 
      return null;
    }
    private static List<int[, ,]> IncreaseBinCountForOccupiedPoints(List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
      occupiedPoints.Add(new int[binMeasures.Width, binMeasures.Height, binMeasures.Depth]);
      int lastIndex = occupiedPoints.Count - 1;
      for (int w = 0; w < binMeasures.Width; w++) {
        for (int h = 0; h < binMeasures.Height; h++) {
          for (int d = 0; d < binMeasures.Depth; d++) {
            occupiedPoints[lastIndex][w, h, d] = -1;
          }
        }
      }
      return occupiedPoints;
    }
    private static bool IsStaticStable(int[, ,] occupiedPoints, CuboidPackingItem item, ThreeDimensionalPacking ep) {
      //Static stability is given, if item is placed on the ground
      if (ep.Y == 0)
        return true;

      if (occupiedPoints[ep.X, ep.Y - 1, ep.Z] != -1 
        && occupiedPoints[ep.X + item.Width - 1, ep.Y - 1, ep.Z] != -1 
        && occupiedPoints[ep.X, ep.Y - 1, ep.Z + item.Depth - 1] != -1 
        && occupiedPoints[ep.X + item.Width - 1, ep.Y - 1, ep.Z + item.Depth - 1] != -1)
        return true;

      //int groundCount = 0;
      //for (int x = ep.X; x < ep.X + item.Width - 1; x++) {
      //  for (int z = ep.Z; z < ep.Z + item.Depth - 1; z++) {
      //    if (occupiedPoints[x,ep.Y-1, z] != -1)                                                     
      //      groundCount++;
      //  }
      //}
      //double stableGround = (double)(groundCount) / (double)(item.Width * item.Depth);
      //if (stableGround > 0.75)
      //  return true;

      return false;
    }
    private static List<int[, ,]>  OccupyPointsForNewItem(List<int[, ,]> occupiedPoints, CuboidPackingItem newItem, ThreeDimensionalPacking position, int itemIndex) {
      int width = position.Rotated ? newItem.Depth : newItem.Width; 
      int depth = position.Rotated ? newItem.Width : newItem.Depth;
      for (int w = position.X; w < position.X + width; w++) {
        for (int h = position.Y; h < position.Y + newItem.Height; h++) {
          for (int d = position.Z; d < position.Z + depth; d++) {
            occupiedPoints[position.AssignedBin][w,h,d] = itemIndex;
          }
        }
      }
      return occupiedPoints;
    }
    private static HashSet<ThreeDimensionalPacking> GenerateNewExtremePointsForNewItem(HashSet<ThreeDimensionalPacking> extremePoints, List<int[, ,]> occupiedPoints, 
        CuboidPackingItem newItem, ThreeDimensionalPacking position, CuboidPackingBin binMeasures) {
      int currentBin = position.AssignedBin;

      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;

      //Find ExtremePoints beginning from sourcepointX
      var sourcePointX = new ThreeDimensionalPacking(currentBin, position.X + newWidth, position.Y, position.Z);
      if (sourcePointX.X < binMeasures.Width && sourcePointX.Y < binMeasures.Height && sourcePointX.Z < binMeasures.Depth) {
        //Traversing down the y-axis                                                                            
        int currentYValue = sourcePointX.Y;
        while (currentYValue > 0 && occupiedPoints[currentBin][sourcePointX.X, currentYValue, sourcePointX.Z] == -1) {
          currentYValue--;
        }
        extremePoints.Add(new ThreeDimensionalPacking(currentBin, sourcePointX.X, currentYValue, sourcePointX.Z));

        //Traversing down the z-axis
        int currentZValue = sourcePointX.Z;
        while (currentZValue > 0 && occupiedPoints[currentBin][sourcePointX.X, sourcePointX.Y, currentZValue - 1] == -1) {
          currentZValue--;
        }
        extremePoints.Add(new ThreeDimensionalPacking(currentBin, sourcePointX.X, sourcePointX.Y, currentZValue));
      }




      //Find ExtremePoints beginning from sourcepointY
      var sourcePointY = new ThreeDimensionalPacking(currentBin, position.X, position.Y + newItem.Height, position.Z);
      if (sourcePointY.X < binMeasures.Width && sourcePointY.Y < binMeasures.Height && sourcePointY.Z < binMeasures.Depth) {
        //Traversing down the x-axis  
        int currentXValue = sourcePointY.X;
        while (currentXValue > 0 && occupiedPoints[currentBin][currentXValue - 1, sourcePointY.Y, sourcePointY.Z] == -1) {
          currentXValue--;
        }
        extremePoints.Add(new ThreeDimensionalPacking(currentBin, currentXValue, sourcePointY.Y, sourcePointY.Z));

        //Traversing down the z-axis
        int currentZValue = sourcePointY.Z;
        while (currentZValue > 0 && occupiedPoints[currentBin][sourcePointY.X, sourcePointY.Y, currentZValue - 1] == -1) {
          currentZValue--;
        }
        extremePoints.Add(new ThreeDimensionalPacking(currentBin, sourcePointY.X, sourcePointY.Y, currentZValue));
      }





      //Find ExtremePoints beginning from sourcepointZ
      var sourcePointZ = new ThreeDimensionalPacking(currentBin, position.X, position.Y, position.Z + newDepth);
      if (sourcePointZ.X < binMeasures.Width && sourcePointZ.Y < binMeasures.Height && sourcePointZ.Z < binMeasures.Depth) {
        //Traversing down the x-axis  
        int currentXValue = sourcePointZ.X;
        while (currentXValue > 0 && occupiedPoints[currentBin][currentXValue - 1, sourcePointZ.Y, sourcePointZ.Z] == -1) {
          currentXValue--;
        }
        extremePoints.Add(new ThreeDimensionalPacking(currentBin, currentXValue, sourcePointZ.Y, sourcePointZ.Z));

        //Traversing down the y-axis                                                                            
        int currentYValue = sourcePointZ.Y;
        while (currentYValue > 0 && occupiedPoints[currentBin][sourcePointZ.X, currentYValue, sourcePointZ.Z] == -1) {
          currentYValue--;
        }
        extremePoints.Add(new ThreeDimensionalPacking(currentBin, sourcePointZ.X, currentYValue, sourcePointZ.Z));
      }


      return extremePoints;
    }
    private static int ShortestPossibleSideFromEP(ThreeDimensionalPacking ep, List<int[, ,]> occupiedPoints, CuboidPackingBin binMeasures) {
      int shortestSide = int.MaxValue;

      if (ep.X >= binMeasures.Width || ep.Y >= binMeasures.Height || ep.Z >= binMeasures.Depth)
        return shortestSide;

      int currentX = ep.X;
      while (currentX < binMeasures.Width && occupiedPoints[ep.AssignedBin][currentX, ep.Y, ep.Z] == -1) { currentX++; }   
      if (currentX - ep.X < shortestSide)
        shortestSide = currentX - ep.X;

      int currentY = ep.Y;
      while (currentY < binMeasures.Height && occupiedPoints[ep.AssignedBin][ep.X, currentY, ep.Z] == -1) { currentY++;  }
      if (currentY - ep.Y < shortestSide)
        shortestSide = currentY - ep.Y;

      int currentZ = ep.Z;
      while (currentZ < binMeasures.Depth && occupiedPoints[ep.AssignedBin][ep.X, ep.Y, currentZ] == -1) { currentZ++; }
      if (currentZ - ep.Z < shortestSide)
        shortestSide = currentZ - ep.Z;

      return shortestSide;
    }
  }
}