Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
06/07/13 01:20:12 (11 years ago)
Author:
jhelm
Message:

#1966: More refactoring; Added more sophisticated structures for packing-plan and bin-packing representation; Transferred parts of the decoding-algorithms to these structures; Did some more refactoring and cleanup;

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r9593 r9596  
    3535using HeuristicLab.Problems.BinPacking.Dimensions;
    3636using HeuristicLab.Problems.BinPacking.PackingBin;
     37using HeuristicLab.Encodings.PackingEncoding.MultiComponentVector;
     38using HeuristicLab.Encodings.PackingEncoding.GroupingVector;
     39using HeuristicLab.Encodings.PackingEncoding.PackingSequence;
    3740
    3841namespace HeuristicLab.Encodings.PackingEncoding.PackingPlan {
    3942  [Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")]
    4043  [StorableClass]
    41   public class PackingPlan<D, B, I> : ParameterizedNamedItem, IPackingPlan
     44  public abstract class PackingPlan<D, B, I> : ParameterizedNamedItem, IPackingPlan
    4245    where D : class, IPackingDimensions
    4346    where B : PackingShape<D>, IPackingBin
    … …  
    5255      }
    5356    }
     57    [Storable]
     58    protected bool StackingConstraints { get; set; }
     59    [Storable]
     60    protected bool UseExtremePoints { get; set; }
     61
     62    [Storable]
     63    public B BinMeasures { get; private set; }
    5464
    5565    [Storable]
    … …  
    7181    #endregion
    7282
    73     public PackingPlan(B binMeasures)
    74       : this(){
    75       //this.BinPackings.Add(new BinPacking<D,B,I> ());
    76     }
    77     public PackingPlan()
    78       : base() {
    79       this.BinPackings = new ObservableList<BinPacking<D, B,I>>();
     83    public PackingPlan(B binMeasures, bool useExtremePoints, bool stackingConstraints)
     84      : base(){
     85        BinMeasures = (B)binMeasures.Clone();
     86        StackingConstraints = stackingConstraints;
     87        UseExtremePoints = useExtremePoints;
     88        BinPackings = new ObservableList<BinPacking<D, B, I>>();
    8089    }
    8190
    … …  
    8695        this.BinPackings = new ObservableList<BinPacking<D, B, I>>(original.BinPackings);
    8796    }
    88     public override IDeepCloneable Clone(Cloner cloner) {
    89       return new PackingPlan<D,B,I>(this, cloner);
    90     }
    91          
     97   
     98
     99    public abstract BinPacking<D, B, I> NewBinPacking();
     100    public void UpdateBinPackings() {
     101      BinPackings.RemoveAll(x => x.ItemPositions.Count == 0);
     102      BinPackings = new ObservableList<BinPacking<D, B, I>>(BinPackings.OrderByDescending (bp => bp.PackingDensity));
     103    }
     104
     105    public void Pack(MultiComponentVectorEncoding solution, ItemList<I> itemMeasures) {
     106      var sequenceMatrix = solution.GenerateSequenceMatrix();
     107      Dictionary<int, bool> rotated = solution.GenerateRotationArray();
     108
     109      //Fill bins according to grouping vector
     110      List<int> remainingIDs = new List<int>();
     111      foreach (var sequence in sequenceMatrix) {
     112        remainingIDs = remainingIDs.Concat(sequence).ToList();
     113        var bp = NewBinPacking();
     114        if (!UseExtremePoints)
     115          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
     116        else
     117          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
     118        BinPackings.Add(bp);
     119      }
     120      UpdateBinPackings();
     121
     122      //Try to put remaining items in existing bins
     123      var temp = new List<int>(remainingIDs);
     124      foreach (int id in temp) {
     125        foreach (var bp in BinPackings) {
     126          var position = UseExtremePoints ? bp.FindExtremePointForItem(itemMeasures[id], rotated[id], StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], rotated[id]);
     127          if (position != null) {
     128            bp.PackItem(id, itemMeasures[id], position);
     129            remainingIDs.Remove(id);
     130          }
     131        }
     132      }
     133
     134      //Put still remaining items in new bins
     135      while (remainingIDs.Count > 0) {
     136        var bp = NewBinPacking();
     137        if (!UseExtremePoints)
     138          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
     139        else
     140          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
     141        BinPackings.Add(bp);
     142      }
     143      UpdateBinPackings();
     144    }
     145    public void Pack(GroupingVectorEncoding solution, ItemList<I> itemMeasures) {
     146      var sequenceMatrix = solution.GenerateSequenceMatrix();
     147
     148      //Fill bins according to grouping vector
     149      List<int> remainingIDs = new List<int>();
     150      foreach (var sequence in sequenceMatrix) {
     151        remainingIDs = remainingIDs.Concat(sequence).ToList();
     152        var bp = NewBinPacking();
     153        if (!UseExtremePoints)
     154          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
     155        else
     156          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
     157        BinPackings.Add(bp);
     158      }
     159      UpdateBinPackings();
     160
     161      //Try to put remaining items in existing bins
     162      var temp = new List<int>(remainingIDs);
     163      foreach (int id in temp) {
     164        foreach (var bp in BinPackings) { 
     165          var position = UseExtremePoints ? bp.FindExtremePointForItem (itemMeasures[id], false, StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], false);
     166          if (position != null) {
     167            bp.PackItem(id, itemMeasures[id], position);
     168            remainingIDs.Remove(id);
     169          }
     170        }
     171      }
     172
     173      //Put still remaining items in new bins
     174      while (remainingIDs.Count > 0) {
     175        var bp = NewBinPacking();
     176        if (!UseExtremePoints)
     177          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
     178        else
     179          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
     180        BinPackings.Add(bp);
     181      }
     182      UpdateBinPackings();
     183    }
     184    public void Pack(PackingSequenceEncoding solution, ItemList<I> itemMeasures) {
     185      List<int> remainingIDs = new List<int>(solution.PackingSequence);
     186      while (remainingIDs.Count > 0) {
     187        var bp = NewBinPacking();
     188        if (!UseExtremePoints)
     189          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
     190        else
     191          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
     192        BinPackings.Add(bp);
     193      }
     194      UpdateBinPackings();
     195    }
     196
    92197
    93198    #region Events
    … …  
    126231  }
    127232
    128   [Item("BinPacking", "Represents a single-bin packing for a bin-packing problem.")]
     233
     234
     235
     236  [Item("PackingPlan2D", "Represents a concrete solution for a 2D bin-packing problem.")]
    129237  [StorableClass]
    130   public abstract class BinPacking<D,B,I>  : Item
    131     where D : class, IPackingDimensions
    132     where B : PackingShape<D>, IPackingBin
    133     where I : PackingShape<D>, IPackingItem {
    134  
    135     [Storable]
    136     public ObservableDictionary<int, D> ItemPositions { get; private set; }
    137 
    138     [Storable]
    139     public B BinMeasures { get; private set; }
    140 
    141     [Storable]
    142     public ObservableDictionary<int, I> ItemMeasures { get; private set; }
    143 
    144     [Storable]
    145     public HashSet<D> ExtremePoints { get; protected set; }
    146 
    147     [Storable]
    148     public OccupiedPoints<D, I> OccupiedPoints { get; protected set; }
    149 
    150     public BinPacking(B binMeasures) : base() {   
    151       ItemPositions = new ObservableDictionary<int, D>();
    152       ItemMeasures = new ObservableDictionary<int, I>();
    153       BinMeasures = (B)binMeasures.Clone();
    154       ExtremePoints = new HashSet<D>();
    155       ExtremePoints.Add(binMeasures.Origin);
    156     }
    157 
     238  public class PackingPlan2D : PackingPlan<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> {
     239    public PackingPlan2D(RectangularPackingBin binMeasures) : this(binMeasures, false, false) { }
     240    public PackingPlan2D(RectangularPackingBin binMeasures, bool useExtremePoints, bool stackingConstraints) : base(binMeasures, useExtremePoints, stackingConstraints) { }
    158241    [StorableConstructor]
    159     protected BinPacking(bool deserializing) : base(deserializing) { }
    160     protected BinPacking(BinPacking<D,B,I> original, Cloner cloner)
     242    protected PackingPlan2D(bool deserializing) : base(deserializing) { }
     243    protected PackingPlan2D(PackingPlan2D original, Cloner cloner)
    161244      : base(original, cloner) {
    162       this.ItemPositions = new ObservableDictionary<int, D>(original.ItemPositions);
    163       this.ItemMeasures = new ObservableDictionary<int, I>(original.ItemMeasures);
    164         this.BinMeasures = (B)original.BinMeasures.Clone(cloner);
    165     }
    166    
    167 
    168     protected abstract void GenerateNewExtremePointsForNewItem(I measures, D position);
    169     public abstract D FindExtremePointForItem(I measures, bool rotated, bool stackingConstraint);
    170     public abstract D FindPositionBySliding(I measures, bool rotated);
    171     public void PackItem(int itemID, I measures, D position) {
    172       ItemMeasures[itemID] = measures;
    173       ItemPositions[itemID] = position;
    174       ExtremePoints.Remove(position);
    175       GenerateNewExtremePointsForNewItem(measures, position);
    176       OccupiedPoints.OccupyPoints(measures, position, itemID);
    177     }
    178 
    179 
    180     public double PackingDensity {
    181       get {
    182         double result = 0;
    183         foreach (var entry in ItemMeasures)
    184           result += entry.Value.MultipliedMeasures;
    185         result /= BinMeasures.MultipliedMeasures;
    186         return result;
    187       }
    188     }
    189 
    190     public bool IsPositionFeasible1(I currentItem, D currentPosition) {
    191       //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
    192       if (!BinMeasures.Encloses(currentPosition, currentItem))
    193         return false;
    194 
    195       foreach (var ipEntry in ItemPositions) {
    196         if (ItemMeasures[ipEntry.Key].Overlaps(ipEntry.Value, currentPosition, currentItem))
    197           return false;
    198       }
    199 
    200       return true;
    201     }
    202     public bool IsPositionFeasible(I currentItem, D position) {
    203       if (!BinMeasures.Encloses(position, currentItem))
    204         return false;
    205 
    206       return OccupiedPoints.IsPositionFeasible (currentItem, position);
     245    }
     246    public override IDeepCloneable Clone(Cloner cloner) {
     247      return new PackingPlan2D(this, cloner);
     248    }
     249    public override BinPacking<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> NewBinPacking() {
     250      return new BinPacking2D(BinMeasures);
    207251    }
    208252  }
    … …  
    212256
    213257
    214   [Item("BinPacking2D", "Represents a single-bin packing for a 2D bin-packing problem.")]
     258  [Item("PackingPlan3D", "Represents a concrete solution for a 3D bin-packing problem.")]
    215259  [StorableClass]
    216   public class BinPacking2D : BinPacking<TwoDimensionalPacking, RectangularPackingBin, RectangularPackingItem> {
    217 
    218     public BinPacking2D(RectangularPackingBin binMeasures) : base(binMeasures) {
    219       OccupiedPoints = new OccupiedPoints2D(binMeasures);
    220     }
     260  public class PackingPlan3D : PackingPlan<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> {
     261    public PackingPlan3D(CuboidPackingBin binMeasures) : this(binMeasures, false, false) { }
     262    public PackingPlan3D(CuboidPackingBin binMeasures, bool useExtremePoints, bool stackingConstraints) : base(binMeasures, useExtremePoints, stackingConstraints) { }
    221263    [StorableConstructor]
    222     protected BinPacking2D(bool deserializing) : base(deserializing) { }
    223     protected BinPacking2D(BinPacking2D original, Cloner cloner)
     264    protected PackingPlan3D(bool deserializing) : base(deserializing) { }
     265    protected PackingPlan3D(PackingPlan3D original, Cloner cloner)
    224266      : base(original, cloner) {
    225267    }
    226268    public override IDeepCloneable Clone(Cloner cloner) {
    227       return new BinPacking2D(this, cloner);
    228     }
    229                      
    230     protected override void GenerateNewExtremePointsForNewItem(RectangularPackingItem newItem, TwoDimensionalPacking position) {
    231 
    232       int newWidth = position.Rotated ? newItem.Height : newItem.Width;
    233       int newHeight = position.Rotated ? newItem.Width : newItem.Height;
    234 
    235       //Find ExtremePoints beginning from sourcepointX
    236       var sourcePointX = new TwoDimensionalPacking(0, position.X + newWidth, position.Y);
    237       if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height) {
    238         //Traversing down the y-axis       
    239         while (sourcePointX.Y > 0 && !OccupiedPoints.IsPointOccupied(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y - 1))) {
    240           sourcePointX.Y--;
    241         }
    242         ExtremePoints.Add(new TwoDimensionalPacking(0, sourcePointX.X, sourcePointX.Y));
    243       }
    244 
    245 
    246 
    247 
    248       //Find ExtremePoints beginning from sourcepointY
    249       var sourcePointY = new TwoDimensionalPacking(0, position.X, position.Y + newItem.Height);
    250       if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height) {
    251         //Traversing down the x-axis 
    252         while (sourcePointY.X > 0 && !OccupiedPoints.IsPointOccupied(new TwoDimensionalPacking (0,sourcePointY.X - 1, sourcePointY.Y))) {
    253           sourcePointY.X--;
    254         }
    255         ExtremePoints.Add(new TwoDimensionalPacking(0, sourcePointY.X, sourcePointY.Y));
    256       }
    257 
    258       ExtremePoints = new HashSet<TwoDimensionalPacking>(ExtremePoints.
    259         OrderBy(ep => ep.AssignedBin).
    260         ThenBy(ep => ep.X).
    261         ThenBy(ep => ep.Y).
    262         ThenBy(ep => OccupiedPoints.ShortestPossibleSideFromEP(ep)));
    263     }
    264 
    265     public override TwoDimensionalPacking FindExtremePointForItem(RectangularPackingItem measures, bool rotated, bool stackingConstraint) {
    266       RectangularPackingItem item = new RectangularPackingItem(
    267         rotated ? measures.Height : measures.Width,
    268         rotated ? measures.Width : measures.Height,
    269         measures.TargetBin);
    270 
    271       int epIndex = 0;
    272       while (epIndex < ExtremePoints.Count && (!IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex)))) { epIndex++; }
    273 
    274       if (epIndex < ExtremePoints.Count) {
    275         var result = ExtremePoints.ElementAt(epIndex);
    276         result.Rotated = rotated;
    277         return result;
    278       }
    279       return null;
    280     }
    281     public override TwoDimensionalPacking FindPositionBySliding(RectangularPackingItem measures, bool rotated) {
    282       TwoDimensionalPacking currentPosition = new TwoDimensionalPacking(0,
    283         BinMeasures.Width - (rotated ? measures.Height : measures.Width),
    284         BinMeasures.Height - (rotated ? measures.Width : measures.Height), rotated);
    285       //Slide the item as far as possible to the left
    286       while (IsPositionFeasible(measures, MoveLeft(currentPosition))
    287         || IsPositionFeasible(measures, MoveDown(currentPosition))) {
    288         //Slide the item as far as possible to the bottom
    289         while (IsPositionFeasible(measures, MoveDown(currentPosition))) {
    290           currentPosition = MoveDown(currentPosition);
    291         }
    292         if (IsPositionFeasible(measures, MoveLeft(currentPosition)))
    293           currentPosition = MoveLeft(currentPosition);
    294       }
    295 
    296       return IsPositionFeasible(measures, currentPosition) ? currentPosition : null;
    297     }
    298     private static TwoDimensionalPacking MoveLeft(TwoDimensionalPacking original) {
    299       return new TwoDimensionalPacking(original.AssignedBin, original.X - 1, original.Y, original.Rotated);
    300     }
    301     private static TwoDimensionalPacking MoveDown(TwoDimensionalPacking original) {
    302       return new TwoDimensionalPacking(original.AssignedBin, original.X, original.Y - 1, original.Rotated);
     269      return new PackingPlan3D(this, cloner);
     270    }
     271    public override BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> NewBinPacking() {
     272      return new BinPacking3D(BinMeasures);
    303273    }
    304274  }
    305275
    306 
    307 
    308   [Item("BinPacking3D", "Represents a single-bin packing for a 3D bin-packing problem.")]
    309   [StorableClass]
    310   public class BinPacking3D : BinPacking<ThreeDimensionalPacking, CuboidPackingBin, CuboidPackingItem> {
    311 
    312    
    313     public BinPacking3D(CuboidPackingBin binMeasures) : base(binMeasures) {
    314       OccupiedPoints = new OccupiedPoints3D(binMeasures);
    315     }
    316     [StorableConstructor]
    317     protected BinPacking3D(bool deserializing) : base(deserializing) { }
    318     protected BinPacking3D(BinPacking3D original, Cloner cloner)
    319       : base(original, cloner) {
    320     }
    321     public override IDeepCloneable Clone(Cloner cloner) {
    322       return new BinPacking3D(this, cloner);
    323     }
    324                                        
    325     protected override void GenerateNewExtremePointsForNewItem(CuboidPackingItem newItem, ThreeDimensionalPacking position) {
    326       int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
    327       int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
    328 
    329       //Find ExtremePoints beginning from sourcepointX
    330       var sourcePointX = new ThreeDimensionalPacking(0, position.X + newWidth, position.Y, position.Z);
    331       if (sourcePointX.X < BinMeasures.Width && sourcePointX.Y < BinMeasures.Height && sourcePointX.Z < BinMeasures.Depth) {
    332         //Traversing down the y-axis                                                                           
    333         int currentYValue = sourcePointX.Y;
    334         while (currentYValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, currentYValue, sourcePointX.Z))) {
    335           currentYValue--;
    336         }
    337         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, currentYValue, sourcePointX.Z));
    338 
    339         //Traversing down the z-axis
    340         int currentZValue = sourcePointX.Z;
    341         while (currentZValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointX.X, sourcePointX.Y, currentZValue - 1))) {
    342           currentZValue--;
    343         }
    344         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointX.X, sourcePointX.Y, currentZValue));
    345       }
    346 
    347 
    348 
    349 
    350       //Find ExtremePoints beginning from sourcepointY
    351       var sourcePointY = new ThreeDimensionalPacking(0, position.X, position.Y + newItem.Height, position.Z);
    352       if (sourcePointY.X < BinMeasures.Width && sourcePointY.Y < BinMeasures.Height && sourcePointY.Z < BinMeasures.Depth) {
    353         //Traversing down the x-axis 
    354         int currentXValue = sourcePointY.X;
    355         while (currentXValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointY.Y, sourcePointY.Z))) {
    356           currentXValue--;
    357         }
    358         ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointY.Y, sourcePointY.Z));
    359 
    360         //Traversing down the z-axis
    361         int currentZValue = sourcePointY.Z;
    362         while (currentZValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointY.X, sourcePointY.Y, currentZValue - 1))) {
    363           currentZValue--;
    364         }
    365         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointY.X, sourcePointY.Y, currentZValue));
    366       }
    367 
    368 
    369 
    370 
    371 
    372       //Find ExtremePoints beginning from sourcepointZ
    373       var sourcePointZ = new ThreeDimensionalPacking(0, position.X, position.Y, position.Z + newDepth);
    374       if (sourcePointZ.X < BinMeasures.Width && sourcePointZ.Y < BinMeasures.Height && sourcePointZ.Z < BinMeasures.Depth) {
    375         //Traversing down the x-axis 
    376         int currentXValue = sourcePointZ.X;
    377         while (currentXValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, currentXValue - 1, sourcePointZ.Y, sourcePointZ.Z))) {
    378           currentXValue--;
    379         }
    380         ExtremePoints.Add(new ThreeDimensionalPacking(0, currentXValue, sourcePointZ.Y, sourcePointZ.Z));
    381 
    382         //Traversing down the y-axis                                                                           
    383         int currentYValue = sourcePointZ.Y;
    384         while (currentYValue > 0 && !OccupiedPoints.IsPointOccupied(new ThreeDimensionalPacking (0, sourcePointZ.X, currentYValue, sourcePointZ.Z))) {
    385           currentYValue--;
    386         }
    387         ExtremePoints.Add(new ThreeDimensionalPacking(0, sourcePointZ.X, currentYValue, sourcePointZ.Z));
    388       }
    389 
    390       ExtremePoints = new HashSet<ThreeDimensionalPacking>(ExtremePoints.
    391         OrderBy(ep => ep.AssignedBin).
    392         ThenBy(ep => ep.Z).
    393         ThenBy(ep => ep.X).
    394         ThenBy(ep => ep.Y).
    395         ThenBy(ep => OccupiedPoints.ShortestPossibleSideFromEP(ep)));
    396     }
    397 
    398     public override ThreeDimensionalPacking FindExtremePointForItem(CuboidPackingItem measures, bool rotated, bool stackingConstraint) {
    399 
    400       CuboidPackingItem item = new CuboidPackingItem(
    401         rotated ? measures.Depth : measures.Width,
    402         measures.Height,
    403         rotated ? measures.Width : measures.Depth,
    404         measures.TargetBin);
    405 
    406       int epIndex = 0;
    407       while (epIndex < ExtremePoints.Count && (
    408         !IsPositionFeasible(item, ExtremePoints.ElementAt(epIndex)) || (stackingConstraint && !OccupiedPoints.IsStaticStable(item, ExtremePoints.ElementAt(epIndex)))
    409       )) { epIndex++; }
    410 
    411       if (epIndex < ExtremePoints.Count) {
    412         var result = ExtremePoints.ElementAt(epIndex);
    413         result.Rotated = rotated;
    414         return result;
    415       }
    416       return null;
    417     }
    418     public override ThreeDimensionalPacking FindPositionBySliding(CuboidPackingItem measures, bool rotated) {
    419       //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
    420       ThreeDimensionalPacking currentPosition = new ThreeDimensionalPacking(0,
    421         BinMeasures.Width - (rotated ? measures.Depth : measures.Width),
    422         BinMeasures.Height - measures.Height,
    423         BinMeasures.Depth - (rotated ? measures.Width : measures.Depth), rotated);
    424       //Slide the item as far as possible to the bottom
    425       while (IsPositionFeasible(measures, MoveDown(currentPosition))
    426         || IsPositionFeasible(measures, MoveLeft(currentPosition))
    427         || IsPositionFeasible(measures, MoveBack(currentPosition))) {
    428         //Slide the item as far as possible to the left
    429         while (IsPositionFeasible(measures, MoveLeft(currentPosition))
    430         || IsPositionFeasible(measures, MoveBack(currentPosition))) {
    431           //Slide the item as far as possible to the back
    432           while (IsPositionFeasible(measures, MoveBack(currentPosition))) {
    433             currentPosition = MoveBack(currentPosition);
    434           }
    435           if (IsPositionFeasible(measures, MoveLeft(currentPosition)))
    436             currentPosition = MoveLeft(currentPosition);
    437         }
    438         if (IsPositionFeasible(measures, MoveDown(currentPosition)))
    439           currentPosition = MoveDown(currentPosition);
    440       }
    441 
    442       return IsPositionFeasible(measures, currentPosition) ? currentPosition : null;
    443     }
    444     private static ThreeDimensionalPacking MoveLeft(ThreeDimensionalPacking original) {
    445       return new ThreeDimensionalPacking(original.AssignedBin, original.X - 1, original.Y, original.Z, original.Rotated);
    446     }
    447     private static ThreeDimensionalPacking MoveDown(ThreeDimensionalPacking original) {
    448       return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y - 1, original.Z, original.Rotated);
    449     }
    450     private static ThreeDimensionalPacking MoveBack(ThreeDimensionalPacking original) {
    451       return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y, original.Z - 1, original.Rotated);
    452     }
    453   }
    454 
    455 
    456 
    457276}
Note: See TracChangeset for help on using the changeset viewer.