source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/2D/EP/ExtremePointsFunctions2D.cs @ 9495

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 ExtremPointsFunctions2D {




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

      #region Preperations
          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>>();
      Dictionary<int, HashSet<TwoDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<TwoDimensionalPacking>>();
      var occupiedPoints = new List<int[,]>();

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

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

      ObservableDictionary<int, TwoDimensionalPacking> itemPositions = new ObservableDictionary<int, TwoDimensionalPacking>();
      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].ItemID;
          var item = itemMeasures[itemIndex];

          extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], 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]);
            solution.PackingInformations[binNr].Remove(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].ItemID;
          var item = itemMeasures[itemIndex];

          extremePointsForBin[binNr] = OrderExtremePoints(extremePointsForBin[binNr], 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]);
            solution.PackingInformations[binNr].Add(unpackedItems[i]);
          }
        }
        if (remainingItems.Count > 0 && binNr + 1 >= nrOfBins) {
          extremePointsForBin[nrOfBins] = new HashSet<TwoDimensionalPacking>();
          extremePointsForBin[nrOfBins].Add(new TwoDimensionalPacking(nrOfBins, 0, 0, false));
          occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
          solution.PackingInformations[nrOfBins] = new ItemList<PackingInformation>();
          nrOfBins++;
        }
      }

      return itemPositions;
    }


    public static ObservableDictionary<int, TwoDimensionalPacking> ExtremePointBasedPacking(GroupingVectorEncoding solution,
        ItemList<RectangularPackingItem> itemMeasures, RectangularPackingBin 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<TwoDimensionalPacking>> extremePointsForBin = new Dictionary<int, HashSet<TwoDimensionalPacking>>(); 
      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<TwoDimensionalPacking>();
        extremePointsForBin[i].Add(new TwoDimensionalPacking(i, 0, 0, false));    
        occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
      }

      ObservableDictionary<int, TwoDimensionalPacking> itemPositions = new ObservableDictionary<int, TwoDimensionalPacking>();
      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] = OrderExtremePoints(extremePointsForBin[binNr], 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] = OrderExtremePoints(extremePointsForBin[binNr], 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<TwoDimensionalPacking>();
          extremePointsForBin[nrOfBins].Add(new TwoDimensionalPacking(nrOfBins, 0, 0, false));
          occupiedPoints = IncreaseBinCountForOccupiedPoints(occupiedPoints, binMeasures);
          nrOfBins++;
        }
      }

      return itemPositions;
    }


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

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

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

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

      foreach (int itemIndex in solution.PackingSequence) {
        var item = itemMeasures[itemIndex];
        extremePoints = OrderExtremePoints(extremePoints, occupiedPoints, binMeasures);
        var positionFound = FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions);
        if (positionFound != null) {
          extremePoints.Remove(positionFound); 
        }
        else {
          positionFound = new TwoDimensionalPacking(nrOfBins, 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 TwoDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<RectangularPackingItem> itemMeasures, RectangularPackingBin binMeasures,
        HashSet<TwoDimensionalPacking> extremePoints, List<int[,]> occupiedPoints, ObservableDictionary<int, TwoDimensionalPacking> itemPositions) {
          return FindExtremePointForItem(itemIndex, itemMeasures, binMeasures, extremePoints, occupiedPoints, itemPositions, false);
    }
    private static TwoDimensionalPacking FindExtremePointForItem(int itemIndex, ItemList<RectangularPackingItem> itemMeasures, RectangularPackingBin binMeasures, 
        HashSet<TwoDimensionalPacking> extremePoints, List<int[,]> occupiedPoints, ObservableDictionary<int, TwoDimensionalPacking> itemPositions, bool rotated) {

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

      int epIndex = 0;
      while (epIndex < extremePoints.Count &&
        (!BottomLeftFunctions.IsPositionFeasible(binMeasures, extremePoints.ElementAt(epIndex).AssignedBin, item, extremePoints.ElementAt(epIndex), itemPositions, itemMeasures))) 
      { 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, RectangularPackingBin binMeasures) {
      occupiedPoints.Add(new int[binMeasures.Width, binMeasures.Height]);
      int lastIndex = occupiedPoints.Count - 1;
      for (int w = 0; w < binMeasures.Width; w++) {
        for (int h = 0; h < binMeasures.Height; h++) {
            occupiedPoints[lastIndex][w, h] = -1;
        }
      }
      return occupiedPoints;
    }
    private static List<int[,]>  OccupyPointsForNewItem(List<int[,]> occupiedPoints, RectangularPackingItem newItem, TwoDimensionalPacking position, int itemIndex) {
      int width = position.Rotated ? newItem.Height : newItem.Width; 
      int height = position.Rotated ? newItem.Width : newItem.Height;
      for (int w = position.X; w < position.X + width; w++) {
        for (int h = position.Y; h < position.Y + height; h++) {
            occupiedPoints[position.AssignedBin][w,h] = itemIndex;
        }
      }
      return occupiedPoints;
    }
    private static HashSet<TwoDimensionalPacking> GenerateNewExtremePointsForNewItem(HashSet<TwoDimensionalPacking> extremePoints, List<int[,]> occupiedPoints, 
        RectangularPackingItem newItem, TwoDimensionalPacking position, RectangularPackingBin binMeasures) {
      int currentBin = position.AssignedBin;

      int newWidth = position.Rotated ? newItem.Height : newItem.Width;
      int newHeight = position.Rotated ? newItem.Width : newItem.Height;

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




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


      return extremePoints;
    }

    public static HashSet<TwoDimensionalPacking> OrderExtremePoints(HashSet<TwoDimensionalPacking> hashSet, List<int[,]> occupiedPoints, RectangularPackingBin binMeasures) {
      return new HashSet<TwoDimensionalPacking>(hashSet.OrderBy(ep => ep.AssignedBin).ThenBy(ep => ep.X).ThenBy(ep => ep.Y).ThenBy(ep => ShortestPossibleSideFromEP(ep, occupiedPoints, binMeasures)));
    }
    private static int ShortestPossibleSideFromEP(TwoDimensionalPacking ep, List<int[,]> occupiedPoints, RectangularPackingBin binMeasures) {
      int shortestSide = int.MaxValue;

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

      int currentX = ep.X;
      while (currentX < binMeasures.Width && occupiedPoints[ep.AssignedBin][currentX, ep.Y] == -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] == -1) { currentY++;  }
      if (currentY - ep.Y < shortestSide)
        shortestSide = currentY - ep.Y;

      return shortestSide;
    }
  }
}