Changeset 9593 for branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs

Timestamp:

06/06/13 03:12:42 (11 years ago)

Author:

jhelm

Message:

#1966: Applied some heavy refactoring on the decoder-classes and cleaned up the code a bit;

File:

• branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs (modified) (6 diffs)

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs

@@ -33 +33 @@
 using HeuristicLab.Data;
 using HeuristicLab.Collections;
+using HeuristicLab.Problems.BinPacking.Dimensions;
+using HeuristicLab.Problems.BinPacking.PackingBin;
 
 namespace HeuristicLab.Encodings.PackingEncoding.PackingPlan {
@@ -45 +47 @@
     public int NrOfBins {
       get {
-        if (PackingItemPositions != null)
-          return PackingItemPositions.Select(p => p.Value.AssignedBin).Max() + 1;
+        if (BinPackings != null)
+          return BinPackings.Count;
         else return 0;
       }
@@ -52 +54 @@
 
     [Storable]
-    public ObservableDictionary<int, D> PackingItemPositions { get; set; }
-    [Storable]
-    public ObservableDictionary<int, B> PackingBinMeasures { get; set; }
-
-    [Storable]
-    public ItemList<I> PackingItemMeasures {
-      get;
-      set;
-    }
+    public ObservableList<BinPacking<D, B, I>> BinPackings { get; set; }
+
     [Storable]
     private DoubleValue quality;
@@ -76 +71 @@
     #endregion
 
-    public PackingPlan(B binMeasures, ItemList<I> itemMeasures)
+    public PackingPlan(B binMeasures)
+      : this(){
+      //this.BinPackings.Add(new BinPacking<D,B,I> ());
+    }
+    public PackingPlan()
       : base() {
-      this.PackingItemMeasures = new ItemList<I> (itemMeasures);
-      this.PackingBinMeasures = new ObservableDictionary<int, B>();
-      this.PackingBinMeasures[0] = binMeasures;
-    }
-    public PackingPlan(ObservableDictionary<int, B> binMeasures, ItemList<I> itemMeasures)
-      : base() {
-      this.PackingItemMeasures = itemMeasures;
-      this.PackingBinMeasures = binMeasures;
+      this.BinPackings = new ObservableList<BinPacking<D, B,I>>();
     }
 
@@ -92 +84 @@
     protected PackingPlan(PackingPlan<D,B,I> original, Cloner cloner)
       : base(original, cloner) {
-      PackingItemPositions = new ObservableDictionary<int, D>(original.PackingItemPositions);
-      PackingBinMeasures = new ObservableDictionary<int, B>(original.PackingBinMeasures);
-      PackingItemMeasures = original.PackingItemMeasures;
+        this.BinPackings = new ObservableList<BinPacking<D, B, I>>(original.BinPackings);
     }
     public override IDeepCloneable Clone(Cloner cloner) {
       return new PackingPlan<D,B,I>(this, cloner);
     }
-
-    public B GetPackingBinMeasuresForBinNr(int binNr) {
-      if (PackingBinMeasures.ContainsKey(binNr))
-        return PackingBinMeasures[binNr];
-      else
-        return PackingBinMeasures[0];
-    }
-
+         
 
     #region Events
@@ -125 +108 @@
     }
 
-    public event EventHandler PackingItemPositionChanged;
-    private void OnPackingItemPositionChanged() {
-      var changed = PackingItemPositionChanged;
+    public event EventHandler BinPackingsChanged;
+    private void OnBinPackingsChanged() {
+      var changed = BinPackingsChanged;
       if (changed != null)
         changed(this, EventArgs.Empty);
     }
-    private void RegisterPackingItemPositionEvents() {
-      PackingItemPositions.PropertyChanged += new System.ComponentModel.PropertyChangedEventHandler(PackingItemPosition_PropertyChanged);
-    }
-    private void DeregisterPackingItemPositionEvents() {
-      PackingItemPositions.PropertyChanged -= new System.ComponentModel.PropertyChangedEventHandler(PackingItemPosition_PropertyChanged);
-    }
-    private void PackingItemPosition_PropertyChanged(object sender, EventArgs e) {
-      OnPackingItemPositionChanged();
+    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("BinPacking", "Represents a single-bin packing for a bin-packing problem.")]
+  [StorableClass]
+  public abstract class BinPacking<D,B,I>  : Item
+    where D : class, IPackingDimensions
+    where B : PackingShape<D>, IPackingBin
+    where I : PackingShape<D>, IPackingItem {
+  
+    [Storable]
+    public ObservableDictionary<int, D> ItemPositions { get; private set; }
+
+    [Storable]
+    public B BinMeasures { get; private set; }
+
+    [Storable]
+    public ObservableDictionary<int, I> ItemMeasures { get; private set; }
+
+    [Storable]
+    public HashSet<D> ExtremePoints { get; protected set; }
+
+    [Storable]
+    public OccupiedPoints<D, I> OccupiedPoints { get; protected set; }
+
+    public BinPacking(B binMeasures) : base() {   
+      ItemPositions = new ObservableDictionary<int, D>();
+      ItemMeasures = new ObservableDictionary<int, I>();
+      BinMeasures = (B)binMeasures.Clone();
+      ExtremePoints = new HashSet<D>();
+      ExtremePoints.Add(binMeasures.Origin);
+    }
+
+    [StorableConstructor]
+    protected BinPacking(bool deserializing) : base(deserializing) { }
+    protected BinPacking(BinPacking<D,B,I> original, Cloner cloner)
+      : base(original, cloner) {
+      this.ItemPositions = new ObservableDictionary<int, D>(original.ItemPositions);
+      this.ItemMeasures = new ObservableDictionary<int, I>(original.ItemMeasures);
+        this.BinMeasures = (B)original.BinMeasures.Clone(cloner);
+    }
+   
+
+    protected abstract void GenerateNewExtremePointsForNewItem(I measures, D position);
+    public abstract D FindExtremePointForItem(I measures, bool rotated, bool stackingConstraint);
+    public abstract D FindPositionBySliding(I measures, bool rotated);
+    public void PackItem(int itemID, I measures, D position) {
+      ItemMeasures[itemID] = measures;
+      ItemPositions[itemID] = position;
+      ExtremePoints.Remove(position);
+      GenerateNewExtremePointsForNewItem(measures, position);
+      OccupiedPoints.OccupyPoints(measures, position, itemID);
+    }
+
+
+    public double PackingDensity { 
+      get {
+        double result = 0;
+        foreach (var entry in ItemMeasures)
+          result += entry.Value.MultipliedMeasures;
+        result /= BinMeasures.MultipliedMeasures;
+        return result;
+      }
+    }
+
+    public bool IsPositionFeasible1(I currentItem, D currentPosition) {
+      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the item does not collide with another already packed item
+      if (!BinMeasures.Encloses(currentPosition, currentItem))
+        return false;
+
+      foreach (var ipEntry in ItemPositions) {
+        if (ItemMeasures[ipEntry.Key].Overlaps(ipEntry.Value, currentPosition, currentItem))
+          return false;
+      }
+
+      return true;
+    }
+    public bool IsPositionFeasible(I currentItem, D position) {
+      if (!BinMeasures.Encloses(position, currentItem))
+        return false;
+
+      return OccupiedPoints.IsPositionFeasible (currentItem, position);
+    }
+  }
+
+
+
+
+
+  [Item("BinPacking2D", "Represents a single-bin packing for a 2D bin-packing problem.")]
+  [StorableClass]
+  public class BinPacking2D : BinPacking<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> {
+
+    public BinPacking2D(RectangularPackingBin binMeasures) : base(binMeasures) {
+      OccupiedPoints = new OccupiedPoints2D(binMeasures);
+    }
+    [StorableConstructor]
+    protected BinPacking2D(bool deserializing) : base(deserializing) { }
+    protected BinPacking2D(BinPacking2D original, Cloner cloner)
+      : base(original, cloner) {
+    }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new BinPacking2D(this, cloner);
+    }
+                      
+    protected override void GenerateNewExtremePointsForNewItem(RectangularPackingItem newItem, TwoDimensionalPacking position) {
+
+      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(0, position.X + newWidth, position.Y);
+      if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height) {
+        //Traversing down the y-axis        
+        while (sourcePointX.Y > 0 && !OccupiedPoints.IsPointOccupied(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y - 1))) {
+          sourcePointX.Y--;
+        }
+        ExtremePoints.Add(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y));
+      }
+
+
+
+
+      //Find ExtremePoints beginning from sourcepointY
+      var sourcePointY = new TwoDimensionalPacking(0, position.X, position.Y + newItem.Height);
+      if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height) {
+        //Traversing down the x-axis  
+        while (sourcePointY.X > 0 && !OccupiedPoints.IsPointOccupied(new TwoDimensionalPacking (0,sourcePointY.X - 1, sourcePointY.Y))) {
+          sourcePointY.X--;
+        }
+        ExtremePoints.Add(new TwoDimensionalPacking(0, sourcePointY.X, sourcePointY.Y));
+      }
+
+      ExtremePoints = new HashSet<TwoDimensionalPacking>(ExtremePoints.
+        OrderBy(ep => ep.AssignedBin).
+        ThenBy(ep => ep.X).
+        ThenBy(ep => ep.Y).
+        ThenBy(ep => OccupiedPoints.ShortestPossibleSideFromEP(ep)));
+    }
+
+    public override TwoDimensionalPacking FindExtremePointForItem(RectangularPackingItem measures, bool rotated, bool stackingConstraint) {
+      RectangularPackingItem item = new RectangularPackingItem(
+        rotated ? measures.Height : measures.Width,
+        rotated ? measures.Width : measures.Height,
+        measures.TargetBin);
+
+      int epIndex = 0;
+      while (epIndex < ExtremePoints.Count && (!IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex)))) { epIndex++; }
+
+      if (epIndex < ExtremePoints.Count) {
+        var result = ExtremePoints.ElementAt(epIndex);
+        result.Rotated = rotated;
+        return result;
+      }
+      return null;
+    }
+    public override TwoDimensionalPacking FindPositionBySliding(RectangularPackingItem measures, bool rotated) {
+      TwoDimensionalPacking currentPosition = new TwoDimensionalPacking(0,
+        BinMeasures.Width - (rotated ? measures.Height : measures.Width),
+        BinMeasures.Height - (rotated ? measures.Width : measures.Height), rotated);
+      //Slide the item as far as possible to the left
+      while (IsPositionFeasible(measures, MoveLeft(currentPosition))
+        || IsPositionFeasible(measures, MoveDown(currentPosition))) {
+        //Slide the item as far as possible to the bottom
+        while (IsPositionFeasible(measures, MoveDown(currentPosition))) {
+          currentPosition = MoveDown(currentPosition);
+        }
+        if (IsPositionFeasible(measures, MoveLeft(currentPosition)))
+          currentPosition = MoveLeft(currentPosition);
+      }
+
+      return IsPositionFeasible(measures, currentPosition) ? currentPosition : null;
+    }
+    private static TwoDimensionalPacking MoveLeft(TwoDimensionalPacking original) {
+      return new TwoDimensionalPacking(original.AssignedBin, original.X - 1, original.Y, original.Rotated);
+    }
+    private static TwoDimensionalPacking MoveDown(TwoDimensionalPacking original) {
+      return new TwoDimensionalPacking(original.AssignedBin, original.X, original.Y - 1, original.Rotated);
+    }
+  }
+
+
+
+  [Item("BinPacking3D", "Represents a single-bin packing for a 3D bin-packing problem.")]
+  [StorableClass]
+  public class BinPacking3D : BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> {
+
+    
+    public BinPacking3D(CuboidPackingBin binMeasures) : base(binMeasures) {
+      OccupiedPoints = new OccupiedPoints3D(binMeasures);
+    }
+    [StorableConstructor]
+    protected BinPacking3D(bool deserializing) : base(deserializing) { }
+    protected BinPacking3D(BinPacking3D original, Cloner cloner)
+      : base(original, cloner) {
+    }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new BinPacking3D(this, cloner);
+    }
+                                       
+    protected override void GenerateNewExtremePointsForNewItem(CuboidPackingItem newItem, ThreeDimensionalPacking position) {
+      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(0, 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.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, currentYValue, sourcePointX.Z))) {
+          currentYValue--;
+        }
+        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, currentYValue, sourcePointX.Z));
+
+        //Traversing down the z-axis
+        int currentZValue = sourcePointX.Z;
+        while (currentZValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, sourcePointX.Y, currentZValue - 1))) {
+          currentZValue--;
+        }
+        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, currentZValue));
+      }
+
+
+
+
+      //Find ExtremePoints beginning from sourcepointY
+      var sourcePointY = new ThreeDimensionalPacking(0, 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.IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointY.Y, sourcePointY.Z))) {
+          currentXValue--;
+        }
+        ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointY.Y, sourcePointY.Z));
+
+        //Traversing down the z-axis
+        int currentZValue = sourcePointY.Z;
+        while (currentZValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointY.X, sourcePointY.Y, currentZValue - 1))) {
+          currentZValue--;
+        }
+        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, currentZValue));
+      }
+
+
+
+
+
+      //Find ExtremePoints beginning from sourcepointZ
+      var sourcePointZ = new ThreeDimensionalPacking(0, 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.IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointZ.Y, sourcePointZ.Z))) {
+          currentXValue--;
+        }
+        ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointZ.Y, sourcePointZ.Z));
+
+        //Traversing down the y-axis                                                                            
+        int currentYValue = sourcePointZ.Y;
+        while (currentYValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointZ.X, currentYValue, sourcePointZ.Z))) {
+          currentYValue--;
+        }
+        ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointZ.X, currentYValue, sourcePointZ.Z));
+      }
+
+      ExtremePoints = new HashSet<ThreeDimensionalPacking>(ExtremePoints.
+        OrderBy(ep => ep.AssignedBin).
+        ThenBy(ep => ep.Z).
+        ThenBy(ep => ep.X).
+        ThenBy(ep => ep.Y).
+        ThenBy(ep => OccupiedPoints.ShortestPossibleSideFromEP(ep)));
+    }
+
+    public override ThreeDimensionalPacking FindExtremePointForItem(CuboidPackingItem measures, bool rotated, bool stackingConstraint) {
+
+      CuboidPackingItem item = new CuboidPackingItem(
+        rotated ? measures.Depth : measures.Width,
+        measures.Height,
+        rotated ? measures.Width : measures.Depth,
+        measures.TargetBin);
+
+      int epIndex = 0;
+      while (epIndex < ExtremePoints.Count && (
+        !IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex)) || (stackingConstraint && !OccupiedPoints.IsStaticStable(item, ExtremePoints.ElementAt(epIndex)))
+      )) { epIndex++; }
+
+      if (epIndex < ExtremePoints.Count) {
+        var result = ExtremePoints.ElementAt(epIndex);
+        result.Rotated = rotated;
+        return result;
+      }
+      return null;
+    }
+    public override ThreeDimensionalPacking FindPositionBySliding(CuboidPackingItem measures, bool rotated) {
+      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
+      ThreeDimensionalPacking currentPosition = new ThreeDimensionalPacking(0,
+        BinMeasures.Width - (rotated ? measures.Depth : measures.Width),
+        BinMeasures.Height - measures.Height,
+        BinMeasures.Depth - (rotated ? measures.Width : measures.Depth), rotated);
+      //Slide the item as far as possible to the bottom
+      while (IsPositionFeasible(measures, MoveDown(currentPosition))
+        || IsPositionFeasible(measures, MoveLeft(currentPosition))
+        || IsPositionFeasible(measures, MoveBack(currentPosition))) {
+        //Slide the item as far as possible to the left
+        while (IsPositionFeasible(measures, MoveLeft(currentPosition))
+        || IsPositionFeasible(measures, MoveBack(currentPosition))) {
+          //Slide the item as far as possible to the back
+          while (IsPositionFeasible(measures, MoveBack(currentPosition))) {
+            currentPosition = MoveBack(currentPosition);
+          }
+          if (IsPositionFeasible(measures, MoveLeft(currentPosition)))
+            currentPosition = MoveLeft(currentPosition);
+        }
+        if (IsPositionFeasible(measures, MoveDown(currentPosition)))
+          currentPosition = MoveDown(currentPosition);
+      }
+
+      return IsPositionFeasible(measures, currentPosition) ? currentPosition : null;
+    }
+    private static ThreeDimensionalPacking MoveLeft(ThreeDimensionalPacking original) {
+      return new ThreeDimensionalPacking(original.AssignedBin, original.X - 1, original.Y, original.Z, original.Rotated);
+    }
+    private static ThreeDimensionalPacking MoveDown(ThreeDimensionalPacking original) {
+      return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y - 1, original.Z, original.Rotated);
+    }
+    private static ThreeDimensionalPacking MoveBack(ThreeDimensionalPacking original) {
+      return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y, original.Z - 1, original.Rotated);
+    }
+  }
+
+
+
 }