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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2015 Joseph Helm and 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 HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Core;
using HeuristicLab.Common;
using HeuristicLab.Data;
using HeuristicLab.Collections;
using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Problems.BinPacking;

namespace HeuristicLab.Encodings.PackingEncoding {
  [Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")]
  [StorableClass]
  public abstract class PackingPlan<D, B, I> : Item, IPackingPlan
    where D : class, IPackingPosition
    where B : PackingShape<D>
    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

    protected 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
  }
}