#region License Information
/* HeuristicLab
* Copyright (C) 2002-2016 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 .
*/
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Core;
using HeuristicLab.Common;
using HeuristicLab.Collections;
namespace HeuristicLab.Problems.BinPacking {
[Item("BinPacking", "Represents a single-bin packing for a bin-packing problem.")]
[StorableClass]
public abstract class BinPacking : Item
where TPos : class, IPackingPosition
where TBin : PackingShape
where TItem : PackingShape {
#region Properties
[Storable]
public ObservableDictionary Positions { get; private set; }
[Storable]
public ObservableDictionary Items { get; private set; }
[Storable]
public TBin BinShape { get; private set; }
[Storable]
public SortedSet ExtremePoints { get; protected set; }
[Storable]
protected Dictionary> OccupationLayers { get; set; }
#endregion Properties
public int FreeVolume {
get { return BinShape.Volume - Items.Sum(x => x.Value.Volume); }
}
protected BinPacking(TBin binShape)
: base() {
Positions = new ObservableDictionary();
Items = new ObservableDictionary();
BinShape = (TBin)binShape.Clone();
ExtremePoints = new SortedSet();
OccupationLayers = new Dictionary>();
}
[StorableConstructor]
protected BinPacking(bool deserializing) : base(deserializing) { }
protected BinPacking(BinPacking original, Cloner cloner)
: base(original, cloner) {
this.Positions = new ObservableDictionary();
foreach (var kvp in original.Positions) {
Positions.Add(kvp.Key, cloner.Clone(kvp.Value));
}
this.Items = new ObservableDictionary();
foreach (var kvp in original.Items) {
Items.Add(kvp.Key, cloner.Clone(kvp.Value));
}
this.BinShape = (TBin)original.BinShape.Clone(cloner);
this.ExtremePoints = new SortedSet(original.ExtremePoints.Select(p => cloner.Clone(p)));
this.OccupationLayers = new Dictionary>();
foreach (var kvp in original.OccupationLayers) {
OccupationLayers.Add(kvp.Key, new List(kvp.Value));
}
}
protected abstract void GenerateNewExtremePointsForNewItem(TItem item, TPos position);
public abstract TPos FindExtremePointForItem(TItem item, bool rotated, bool stackingConstraints);
public abstract TPos FindPositionBySliding(TItem item, bool rotated, bool stackingConstraints);
public abstract void SlidingBasedPacking(ref IList sequence, IList items, bool stackingConstraints);
public abstract void SlidingBasedPacking(ref IList sequence, IList items, Dictionary rotationArray, bool stackingConstraints);
public abstract void ExtremePointBasedPacking(ref IList sequence, IList items, bool stackingConstraints);
public abstract void ExtremePointBasedPacking(ref IList sequence, IList items, bool stackingConstraints, Dictionary rotationArray);
public virtual void PackItem(int itemID, TItem item, TPos position) {
Items[itemID] = item;
Positions[itemID] = position;
ExtremePoints.Remove(position);
GenerateNewExtremePointsForNewItem(item, position);
AddNewItemToOccupationLayers(itemID, item, position);
}
public virtual bool PackItemIfFeasible(int itemID, TItem item, TPos position, bool stackingConstraints) {
if (IsPositionFeasible(item, position, stackingConstraints)) {
PackItem(itemID, item, position);
return true;
}
return false;
}
public double PackingDensity {
get {
double result = 0;
foreach (var entry in Items)
result += entry.Value.Volume;
result /= BinShape.Volume;
return result;
}
}
public int PointOccupation(TPos position) {
foreach (var id in GetLayerItemIDs(position)) {
if (Items[id].EnclosesPoint(Positions[id], position))
return id;
}
return -1;
}
public bool IsPointOccupied(TPos position) {
foreach (var id in GetLayerItemIDs(position)) {
if (Items[id].EnclosesPoint(Positions[id], position))
return true;
}
return false;
}
public virtual bool IsPositionFeasible(TItem item, TPos position, bool stackingConstraints) {
//In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the point is supported by something; 3. the item does not collide with another already packed item
if (!BinShape.Encloses(position, item))
return false;
foreach (var id in GetLayerItemIDs(item, position)) {
if (Items[id].Overlaps(Positions[id], position, item))
return false;
}
return true;
}
public abstract int ShortestPossibleSideFromPoint(TPos position);
public abstract bool IsStaticStable(TItem measures, TPos position);
protected abstract void InitializeOccupationLayers();
protected abstract void AddNewItemToOccupationLayers(int itemID, TItem item, TPos position);
protected abstract List GetLayerItemIDs(TPos position);
protected abstract List GetLayerItemIDs(TItem item, TPos position);
}
}