Changeset 9599 for branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/BinPacking3D.cs

Timestamp:

06/09/13 12:58:39 (11 years ago)

Author:

jhelm

Message:

#1966: Bugfixing; Refactoring; Performancetuning;

File:

• branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/BinPacking3D.cs (modified) (12 diffs)

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

@@ -41 +41 @@
   public class BinPacking3D : BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> {
 
-    public BinPacking3D(CuboidPackingBin binMeasures) : base(binMeasures) {
-      //OccupiedPoints = new OccupiedPoints3D(binMeasures);
+    public BinPacking3D(CuboidPackingBin binMeasures)
+      : base(binMeasures) {
+      //ExtremePoints = new HashSet<ThreeDimensionalPacking>();
+      ExtremePoints = new SortedSet<ThreeDimensionalPacking>(new EPComparer3D());
+      ExtremePoints.Add(binMeasures.Origin);
     }
     [StorableConstructor]
@@ -48 +51 @@
     protected BinPacking3D(BinPacking3D original, Cloner cloner)
       : base(original, cloner) {
-        this.depthWasDoubled = original.depthWasDoubled;
+      this.depthWasDoubled = original.depthWasDoubled;
+      this.ExtremePoints = new SortedSet<ThreeDimensionalPacking>(original.ExtremePoints, new EPComparer3D());
     }
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -63 +67 @@
         //Traversing down the y-axis            
         ThreeDimensionalPacking current = new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
-        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown (current))) {
-          current = ThreeDimensionalPacking.MoveDown(current);
-        }
-        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
-        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
+        while (current.Y > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveDown (current))) {
+          current = ThreeDimensionalPacking.MoveDown(current);
+        }
+        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
+        while (current.X > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
           current = ThreeDimensionalPacking.MoveLeft(current);
         }
@@ -74 +78 @@
         //Traversing down the z-axis                 
         current = new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
-        while (current.Z > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveBack (current))) {
+        while (current.Z > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveBack (current))) {
           current = ThreeDimensionalPacking.MoveBack(current);
         }
         ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
-        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
+        while (current.Y > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
           current = ThreeDimensionalPacking.MoveDown(current);
         }
@@ -92 +96 @@
         //Traversing down the x-axis          
         ThreeDimensionalPacking current = new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
-        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
+        while (current.X > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
           current = ThreeDimensionalPacking.MoveLeft(current);
         }
         ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
-        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
+        while (current.Y > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
           current = ThreeDimensionalPacking.MoveDown(current);
         }
@@ -103 +107 @@
         //Traversing down the z-axis                                                                   
         current = new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
-        while (current.Z > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveBack(current))) {
+        while (current.Z > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveBack(current))) {
           current = ThreeDimensionalPacking.MoveBack(current);
         }
         ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
-        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
+        while (current.Y > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
           current = ThreeDimensionalPacking.MoveDown(current);
         }
@@ -122 +126 @@
         //Traversing down the x-axis                                                                             
         ThreeDimensionalPacking current = new ThreeDimensionalPacking(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
-        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
+        while (current.X > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
           current = ThreeDimensionalPacking.MoveLeft(current);
         }
         ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
-        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
+        while (current.Y > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
           current = ThreeDimensionalPacking.MoveDown(current);
         }
@@ -133 +137 @@
         //Traversing down the y-axis                                                                     
         current = new ThreeDimensionalPacking(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
-        while (current.Y > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
-          current = ThreeDimensionalPacking.MoveDown(current);
-        }
-        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
-        while (current.X > 0 && IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
+        while (current.Y > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveDown(current))) {
+          current = ThreeDimensionalPacking.MoveDown(current);
+        }
+        ExtremePoints.Add((ThreeDimensionalPacking)current.Clone());
+        while (current.X > 0 && !IsPointOccupied(ThreeDimensionalPacking.MoveLeft(current))) {
           current = ThreeDimensionalPacking.MoveLeft(current);
         }
@@ -143 +147 @@
       }
 
-      ExtremePoints = new HashSet<ThreeDimensionalPacking>(ExtremePoints.
-        OrderBy(ep => ep.Z).
-        ThenBy(ep => ep.X).
-        ThenBy(ep => ep.Y)//.ThenBy(ep => ShortestPossibleSideFromPoint(ep)) 
-        );
+      //ExtremePoints.RemoveWhere(ep => IsPointOccupied (ep));
+
+      //ExtremePoints = new HashSet<ThreeDimensionalPacking>(ExtremePoints.
+      //  OrderBy(ep => ep.Z).
+      //  ThenBy(ep => ep.X).
+      //  ThenBy(ep => ep.Y)//.ThenBy(ep => ShortestPossibleSideFromPoint(ep)) 
+      //  );
     }
 
@@ -281 +287 @@
 
       if (IsPointOccupied (new ThreeDimensionalPacking (0, position.X, position.Y - 1, position.Z))
-        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width, position.Y - 1, position.Z))
-        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X, position.Y - 1, position.Z + item.Depth))
-        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width, position.Y - 1, position.Z + item.Depth)))
+        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width-1, position.Y - 1, position.Z))
+        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X, position.Y - 1, position.Z + item.Depth-1))
+        && IsPointOccupied (new ThreeDimensionalPacking (0, position.X + item.Width-1, position.Y - 1, position.Z + item.Depth-1)))
         return true;
 
@@ -307 +313 @@
     }
 
-
     [Storable]
     private bool depthWasDoubled = false;
@@ -336 +341 @@
 
       if (ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X, ep.Y - 1, ep.Z))].SupportsStacking(item)
-        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X + item.Width, ep.Y - 1, ep.Z))].SupportsStacking(item)
-        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X, ep.Y - 1, ep.Z + item.Depth))].SupportsStacking(item)
-        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X + item.Width, ep.Y - 1, ep.Z + item.Depth))].SupportsStacking(item))
+        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X + item.Width-1, ep.Y - 1, ep.Z))].SupportsStacking(item)
+        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X, ep.Y - 1, ep.Z + item.Depth-1))].SupportsStacking(item)
+        && ItemMeasures[PointOccupation(new ThreeDimensionalPacking(0, ep.X + item.Width-1, ep.Y - 1, ep.Z + item.Depth-1))].SupportsStacking(item))
         return true;
 
       return false;
+    }    
+    
+
+    protected override void InitializeOccupationLayers() {
+      for (int i = 0; i*10 <= BinMeasures.Depth; i += 1) {
+        OccupationLayers[i] = new List<int>();
+      }
+    }
+    protected override void AddNewItemToOccupationLayers(int itemID, CuboidPackingItem measures, ThreeDimensionalPacking position) {
+      int z1 = position.Z / 10;
+      int z2 = (position.Z + (position.Rotated ? measures.Width : measures.Depth)) / 10;
+
+      for (int i = z1; i <= z2; i++)
+        OccupationLayers[i].Add(itemID);
+    }
+    protected override List<int> GetLayerItemIDs(ThreeDimensionalPacking position) {
+      return OccupationLayers[position.Z / 10];
+    }
+    protected override List<int> GetLayerItemIDs(CuboidPackingItem measures, ThreeDimensionalPacking position) {
+      List<int> result = new List<int>();
+      int z1 = position.Z / 10;
+      int z2 = (position.Z + (position.Rotated ? measures.Width : measures.Depth)) / 10;
+
+      for (int i = z1; i <= z2; i++)
+        result.AddRange(OccupationLayers[i]);
+
+      return result;
+    }
+  }
+  public class EPComparer3D : IComparer<ThreeDimensionalPacking> {
+    public int Compare(ThreeDimensionalPacking a, ThreeDimensionalPacking b) { 
+        int result = a.Z.CompareTo (b.Z);
+      if (result == 0)
+        result = a.X.CompareTo (b.X);
+      if (result == 0)
+        result = a.Y.CompareTo(b.Y);
+
+      return result;
     }
   }