source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs @ 9599

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using HeuristicLab.Problems.BinPacking.Interfaces;
using HeuristicLab.Problems.BinPacking.PackingItem;
using HeuristicLab.Problems.BinPacking.Shapes;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Core;
using HeuristicLab.Common;
using HeuristicLab.Parameters;
using HeuristicLab.Data;
using HeuristicLab.Collections;
using HeuristicLab.Problems.BinPacking.Dimensions;
using HeuristicLab.Problems.BinPacking.PackingBin;
using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
using HeuristicLab.Encodings.IntegerVectorEncoding;

namespace HeuristicLab.Encodings.PackingEncoding.PackingPlan {
  [Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")]
  [StorableClass]
  public abstract class PackingPlan<D, B, I> : ParameterizedNamedItem, IPackingPlan
    where D : class, IPackingDimensions
    where B : PackingShape<D>, IPackingBin
    where I : PackingShape<D>, IPackingItem {

    #region Properties
    public int NrOfBins {
      get {
        if (BinPackings != null)
          return BinPackings.Count;
        else return 0;
      }
    }
    [Storable]
    protected bool StackingConstraints { get; set; }
    [Storable]
    protected bool UseExtremePoints { get; set; }

    [Storable]
    public B BinMeasures { get; private set; }

    [Storable]
    public ObservableList<BinPacking<D, B, I>> BinPackings { get; set; }

    [Storable]
    private DoubleValue quality;
    public DoubleValue Quality {
      get { return quality; }
      set {
        if (quality != value) {
          if (quality != null) DeregisterQualityEvents();
          quality = value;
          if (quality != null) RegisterQualityEvents();
          OnQualityChanged();
        }
      }
    }
    #endregion

    public PackingPlan(B binMeasures, bool useExtremePoints, bool stackingConstraints)
      : base(){
        BinMeasures = (B)binMeasures.Clone();
        StackingConstraints = stackingConstraints;
        UseExtremePoints = useExtremePoints;
        BinPackings = new ObservableList<BinPacking<D, B, I>>();
    }

    [StorableConstructor]
    protected PackingPlan(bool deserializing) : base(deserializing) { }
    protected PackingPlan(PackingPlan<D,B,I> original, Cloner cloner)
      : base(original, cloner) {
        this.BinPackings = new ObservableList<BinPacking<D, B, I>>(original.BinPackings);
    }
    

    public abstract BinPacking<D, B, I> NewBinPacking();
    public void UpdateBinPackings() {
      BinPackings.RemoveAll(x => x.ItemPositions.Count == 0);
      BinPackings = new ObservableList<BinPacking<D, B, I>>(BinPackings.OrderByDescending (bp => bp.PackingDensity));
    }

    public void Pack(MultiComponentVectorEncoding solution, ItemList<I> itemMeasures) {
      var sequenceMatrix = solution.GenerateSequenceMatrix();
      Dictionary<int, bool> rotated = solution.GenerateRotationArray();

      //Fill bins according to grouping vector
      List<int> remainingIDs = new List<int>();
      foreach (var sequence in sequenceMatrix) {
        remainingIDs = remainingIDs.Concat(sequence).ToList();
        var bp = NewBinPacking();
        if (!UseExtremePoints)
          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
        else
          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
        BinPackings.Add(bp);
      }
      UpdateBinPackings();

      //Try to put remaining items in existing bins
      var temp = new List<int>(remainingIDs);
      foreach (int id in temp) {
        foreach (var bp in BinPackings) {
          var position = UseExtremePoints ? bp.FindExtremePointForItem(itemMeasures[id], rotated[id], StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], rotated[id]);
          if (position != null) {
            bp.PackItem(id, itemMeasures[id], position);
            remainingIDs.Remove(id);
            break;
          }
        }
      }

      //Put still remaining items in new bins
      while (remainingIDs.Count > 0) {
        var bp = NewBinPacking();
        if (!UseExtremePoints)
          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
        else
          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
        BinPackings.Add(bp);
      }
      UpdateBinPackings();

      var newSolution = new ObservableDictionary<int,ItemList<PackingInformation>> ();
      foreach (var bp in BinPackings) {
        int binIndex = newSolution.Count;
        newSolution[binIndex] = new ItemList<PackingInformation>();
        foreach (var entry in bp.ItemPositions)
          newSolution[binIndex].Add(new PackingInformation (entry.Key, entry.Value.Rotated));
      }
      solution.PackingInformations = newSolution;
    }
    public void Pack(GroupingVectorEncoding solution, ItemList<I> itemMeasures) {
      var sequenceMatrix = solution.GenerateSequenceMatrix();

      //Fill bins according to grouping vector
      List<int> remainingIDs = new List<int>();
      foreach (var sequence in sequenceMatrix) {
        remainingIDs = remainingIDs.Concat(sequence).ToList();
        var bp = NewBinPacking();
        if (!UseExtremePoints)
          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
        else
          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
        BinPackings.Add(bp);
      }
      UpdateBinPackings();

      //Try to put remaining items in existing bins
      var temp = new List<int>(remainingIDs);
      foreach (int id in temp) {
        foreach (var bp in BinPackings) {  
          var position = UseExtremePoints ? bp.FindExtremePointForItem (itemMeasures[id], false, StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], false);
          if (position != null) {
            bp.PackItem(id, itemMeasures[id], position);
            remainingIDs.Remove(id);
            break;
          }
        }
      }

      //Put still remaining items in new bins
      while (remainingIDs.Count > 0) {
        var bp = NewBinPacking();
        if (!UseExtremePoints)
          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
        else
          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
        BinPackings.Add(bp);
      }
      UpdateBinPackings();

      var newSolution = new int[solution.GroupingVector.Length];
      int binIndex = 0;
      foreach (var bp in BinPackings) {
        foreach (var entry in bp.ItemPositions)
          newSolution[entry.Key] = binIndex;
        binIndex++;
      }
      solution.GroupingVector = new IntegerVector (newSolution);
    }
    public void Pack(PackingSequenceEncoding solution, ItemList<I> itemMeasures) {
      List<int> remainingIDs = new List<int>(solution.PackingSequence);
      while (remainingIDs.Count > 0) {
        var bp = NewBinPacking();
        if (!UseExtremePoints)
          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
        else
          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
        BinPackings.Add(bp);
      }
      UpdateBinPackings();
    }


    #region Events
    public event EventHandler QualityChanged;
    private void OnQualityChanged() {
      var changed = QualityChanged;
      if (changed != null)
        changed(this, EventArgs.Empty);
    }
    private void RegisterQualityEvents() {
      Quality.ValueChanged += new EventHandler(Quality_ValueChanged);
    }
    private void DeregisterQualityEvents() {
      Quality.ValueChanged -= new EventHandler(Quality_ValueChanged);
    }
    private void Quality_ValueChanged(object sender, EventArgs e) {
      OnQualityChanged();
    }

    public event EventHandler BinPackingsChanged;
    private void OnBinPackingsChanged() {
      var changed = BinPackingsChanged;
      if (changed != null)
        changed(this, EventArgs.Empty);
    }
    private void RegisterBinPackingsEvents() {
      BinPackings.PropertyChanged += new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged);
    }
    private void DeregisterBinPackingsEvents() {
      BinPackings.PropertyChanged -= new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged);
    }
    private void BinPackings_PropertyChanged(object sender, EventArgs e) {
      OnBinPackingsChanged();
    }
    #endregion
  }




  [Item("PackingPlan2D", "Represents a concrete solution for a 2D bin-packing problem.")]
  [StorableClass]
  public class PackingPlan2D : PackingPlan<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> {
    public PackingPlan2D(RectangularPackingBin binMeasures) : this(binMeasures, false, false) { }
    public PackingPlan2D(RectangularPackingBin binMeasures, bool useExtremePoints, bool stackingConstraints) : base(binMeasures, useExtremePoints, stackingConstraints) { } 
    [StorableConstructor]
    protected PackingPlan2D(bool deserializing) : base(deserializing) { }
    protected PackingPlan2D(PackingPlan2D original, Cloner cloner)
      : base(original, cloner) {
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new PackingPlan2D(this, cloner);
    }
    public override BinPacking<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> NewBinPacking() {
      return new BinPacking2D(BinMeasures);
    }
  }





  [Item("PackingPlan3D", "Represents a concrete solution for a 3D bin-packing problem.")]
  [StorableClass]
  public class PackingPlan3D : PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> {
    public PackingPlan3D(CuboidPackingBin binMeasures) : this(binMeasures, false, false) { }
    public PackingPlan3D(CuboidPackingBin binMeasures, bool useExtremePoints, bool stackingConstraints) : base(binMeasures, useExtremePoints, stackingConstraints) { } 
    [StorableConstructor]
    protected PackingPlan3D(bool deserializing) : base(deserializing) { }
    protected PackingPlan3D(PackingPlan3D original, Cloner cloner)
      : base(original, cloner) {
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new PackingPlan3D(this, cloner);
    }
    public override BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> NewBinPacking() {
      return new BinPacking3D(BinMeasures);
    }
  }

}