Changeset 15473


Ignore:
Timestamp:
11/15/17 12:30:13 (2 years ago)
Author:
rhanghof
Message:

#2817

  • Added unit tests
  • Refactoring of bp 3D
Location:
branches/2817-BinPackingSpeedup
Files:
338 added
8 deleted
17 edited

Legend:

Unmodified
Added
Removed
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/2D/BinPacking2D.cs

    r15241 r15473  
    3434    public BinPacking2D(PackingShape binShape)
    3535      : base(binShape) {
     36      OccupationLayers = new Dictionary<int, List<int>>();
    3637      ExtremePoints.Add(binShape.Origin);
    3738      InitializeOccupationLayers();
     
    4041    [StorableConstructor]
    4142    protected BinPacking2D(bool deserializing) : base(deserializing) { }
    42     protected BinPacking2D(BinPacking2D original, Cloner cloner) : base(original, cloner) { }
     43    protected BinPacking2D(BinPacking2D original, Cloner cloner) : base(original, cloner) {
     44      this.OccupationLayers = new Dictionary<int, List<int>>();
     45      foreach (var kvp in original.OccupationLayers) {
     46        OccupationLayers.Add(kvp.Key, new List<int>(kvp.Value));
     47      }
     48    }
    4349    public override IDeepCloneable Clone(Cloner cloner) {
    4450      return new BinPacking2D(this, cloner);
    4551    }
     52
     53    [Storable]
     54    protected Dictionary<int, List<int>> OccupationLayers { get; set; }
    4655
    4756    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
     
    7584    }
    7685
    77     public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
     86    public PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
    7887      PackingItem rotatedItem = new PackingItem(
    7988        rotated ? item.Height : item.Width,
     
    91100      return null;
    92101    }
    93     public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
     102
     103    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
     104      Items[itemID] = item;
     105      Positions[itemID] = position;
     106      ExtremePoints.Remove(position);
     107      GenerateNewExtremePointsForNewItem(item, position);
     108
     109      AddNewItemToOccupationLayers(itemID, item, position);
     110    }
     111
     112    public bool PackItemIfFeasible(int itemID, PackingItem item, PackingPosition position, bool stackingConstraints) {
     113      if (IsPositionFeasible(item, position, stackingConstraints)) {
     114        PackItem(itemID, item, position);
     115        return true;
     116      }
     117      return false;
     118    }
     119
     120    /// <summary>
     121    ///
     122    /// </summary>
     123    /// <param name="item"></param>
     124    /// <param name="position"></param>
     125    /// <param name="stackingConstraints"></param>
     126    /// <returns></returns>
     127    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
     128      //In this case feasability is defined as following:
     129      //1. the item fits into the bin-borders;
     130      //2. the point is supported by something;
     131      //3. the item does not collide with another already packed item
     132      if (!BinShape.Encloses(position, item))
     133        return false;
     134
     135      foreach (var id in GetLayerItemIDs(item, position)) {
     136        if (Items[id].Overlaps(Positions[id], position, item))
     137          return false;
     138      }
     139
     140      return true;
     141    }
     142
     143
     144    public PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
    94145      PackingPosition currentPosition = new PackingPosition(0,
    95146        BinShape.Width - (rotated ? item.Height : item.Width),
     
    109160    }
    110161
    111     public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
     162    public void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    112163      var temp = new List<int>(sequence);
    113164      for (int i = 0; i < temp.Count; i++) {
     
    120171      }
    121172    }
    122     public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
     173    public void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
    123174      var temp = new List<int>(sequence);
    124175      for (int i = 0; i < temp.Count; i++) {
     
    131182      }
    132183    }
    133     public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
     184    public void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    134185      var temp = new List<int>(sequence);
    135186      foreach (int itemID in temp) {
     
    143194    }
    144195   
    145     public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
     196    public void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
    146197      var temp = new List<int>(sequence);
    147198      foreach (int itemID in temp) {
     
    155206    }
    156207
    157     public override int ShortestPossibleSideFromPoint(PackingPosition position) {
     208    public int ShortestPossibleSideFromPoint(PackingPosition position) {
    158209      int shortestSide = int.MaxValue;
    159210      int width = BinShape.Width;
     
    179230      throw new NotSupportedException();
    180231    }
    181     protected override void InitializeOccupationLayers() {
     232    protected void InitializeOccupationLayers() {
    182233      for (int i = 0; i * 10 <= BinShape.Width; i += 1) {
    183234        OccupationLayers[i] = new List<int>();
     
    185236    }
    186237
    187     protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
     238    protected void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
    188239      int x1 = position.X / 10;
    189240      int x2 = (position.X + (position.Rotated ? item.Height : item.Width)) / 10;
     
    192243        OccupationLayers[i].Add(itemID);
    193244    }
    194     protected override List<int> GetLayerItemIDs(PackingPosition position) {
     245    protected List<int> GetLayerItemIDs(PackingPosition position) {
    195246      return OccupationLayers[position.X / 10];
    196247    }
    197     protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
     248    protected List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
    198249      List<int> result = new List<int>();
    199250      int x1 = position.X / 10;
     
    205256      return result;
    206257    }
     258   
     259
     260    public int PointOccupation(PackingPosition position) {
     261      foreach (var id in GetLayerItemIDs(position)) {
     262        if (Items[id].EnclosesPoint(Positions[id], position))
     263          return id;
     264      }
     265      return -1;
     266    }
     267
     268    public bool IsPointOccupied(PackingPosition position) {
     269      foreach (var id in GetLayerItemIDs(position)) {
     270        if (Items[id].EnclosesPoint(Positions[id], position))
     271          return true;
     272      }
     273      return false;
     274    }
    207275  }
    208276}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r15471 r15473  
    4141      ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
    4242      AddExtremePoint(binShape.Origin);
    43       InitializeOccupationLayers();
    4443    }
    4544    [StorableConstructor]
     
    6463      #endregion
    6564    }
    66 
    67     #region New methods for bin packer class
    6865
    6966    /// <summary>
     
    114111      AddExtremePoint(ep3);
    115112    }
    116        
     113
    117114    private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
    118115      var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
     
    132129        }
    133130      }
    134      
    135       if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0  || limit.Z - pos.Z <= 0) {
     131
     132      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
    136133        return Tuple.Create(0, 0, 0);
    137       }     
     134      }
    138135      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
    139136    }
     
    363360        itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
    364361    }
    365 
    366 
    367 
    368     #endregion
     362   
    369363
    370364    /// <summary>
     
    501495      return false;
    502496    }
    503        
     497
    504498    #region Projections
    505499
     
    629623    #endregion
    630624
    631 
    632     #region Sliding based packing  and obsolet methods
    633     public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
    634       throw new NotSupportedException();
    635       PackingItem newItem = new PackingItem(
    636         rotated ? item.Depth : item.Width,
    637         item.Height,
    638         rotated ? item.Width : item.Depth,
    639         item.TargetBin, item.Weight, item.Material);
    640 
    641       var ep = ExtremePoints.Where(x => IsPositionFeasible(newItem, x, stackingConstraints))
    642                             .FirstOrDefault();
    643       if (ep != null) {
    644         var result = new PackingPosition(ep.AssignedBin, ep.X, ep.Y, ep.Z, rotated);
    645         return result;
    646       }
    647       return null;
    648     }
    649 
    650 
    651 
    652 
    653     public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
    654       throw new NotSupportedException();
    655     }
    656 
    657     public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    658       throw new NotSupportedException();
    659     }
    660     public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
    661       throw new NotSupportedException();
    662     }
    663 
    664 
    665     public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    666       throw new NotSupportedException();
    667     }
    668 
    669     public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
    670       throw new NotSupportedException();
    671     }
    672 
    673     public override int ShortestPossibleSideFromPoint(PackingPosition position) {
    674       throw new NotSupportedException();
    675     }
    676 
    677 
    678     protected override void InitializeOccupationLayers() {
    679     }
    680     protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
    681     }
    682 
    683 
    684     protected override List<int> GetLayerItemIDs(PackingPosition position) {
    685       return null;
    686     }
    687     protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
    688       return null;
    689     }
    690     #endregion
    691625
    692626
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/BinUtilizationEvaluator.cs

    r14167 r15473  
    2626using HeuristicLab.Common;
    2727
    28 namespace HeuristicLab.Problems.BinPacking3D {
     28namespace HeuristicLab.Problems.BinPacking3D.Evaluators {
    2929  // NOTE: same implementation as for 2d problem
    3030  [Item("Bin-Utilization Evaluator (3d)", "Calculates the overall utilization of bin space.")]
     
    4343
    4444    #region IEvaluator Members
     45
     46    /// <summary>
     47    /// Calculates the bin utilization in percent.
     48    /// </summary>
     49    /// <param name="solution"></param>
     50    /// <returns>Returns the calculated bin utilization of all bins in percent.</returns>
    4551    public double Evaluate(Solution solution) {
    4652      return CalculateBinUtilization(solution);
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Evaluators/PackingRatioEvaluator.cs

    r15462 r15473  
    2626using HeuristicLab.Common;
    2727
    28 namespace HeuristicLab.Problems.BinPacking3D {
     28namespace HeuristicLab.Problems.BinPacking3D.Evaluators {
    2929  // NOTE: same implementation as for 2d problem
    3030  [Item("Packing-Ratio Evaluator (3d)", "Calculates the ratio between packed and unpacked space.")]
     
    4343
    4444    #region IEvaluator Members
     45
     46    /// <summary>
     47    /// Calculates the packing ratio for the solution.
     48    /// The packing ration is calculated as followed:
     49    /// Falkenauer:1996 - A Hybrid Grouping Genetic Algorithm for Bin Packing
     50    /// fBPP = (SUM[i=1..N](Fi / C)^k)/N
     51    /// N.......the number of bins used in the solution,
     52    /// Fi......the sum of sizes of the items in the bin i (the fill of the bin),
     53    /// C.......the bin capacity and
     54    /// k.......a constant, k>1.
     55    /// </summary>
     56    /// <param name="solution"></param>
     57    /// <returns>Returns the calculated packing ratio of the bins in the given solution.</returns>
    4558    public double Evaluate(Solution solution) {
    4659      return CalculatePackingRatio(solution);
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/BPPData.cs

    r14162 r15473  
    2222
    2323
    24 namespace HeuristicLab.Problems.BinPacking3D {
     24namespace HeuristicLab.Problems.BinPacking3D.Instances {
    2525
     26  /// <summary>
     27  /// Represents an instance which contains bin packing problem data.
     28  /// </summary>
    2629  public class BPPData {
    2730    /// <summary>
     
    2932    /// </summary>
    3033    public string Name { get; set; }
     34
    3135    /// <summary>
    3236    /// Optional! The description of the instance
     
    3842    /// </summary>
    3943    public int NumItems { get { return Items == null ? 0 : Items.Length; } }
     44
     45    /// <summary>
     46    /// Assigned packing shape
     47    /// </summary>
    4048    public PackingShape BinShape { get; set; }
     49
     50    /// <summary>
     51    /// Array with assigned packing items
     52    /// </summary>
    4153    public PackingItem[] Items { get; set; }
     54   
    4255    /// <summary>
    4356    /// Optional! The quality of the best-known solution.
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProvider.cs

    r15454 r15473  
    164164    }
    165165
    166 
     166    /// <summary>
     167    /// Loads the data from the given data descriptor.
     168    /// It retuns a bin packing problem data instance with the data of the random instance provider.
     169    /// </summary>
     170    /// <param name="dd"></param>
     171    /// <returns></returns>
    167172    public override BPPData LoadData(IDataDescriptor dd) {
    168173      var randDd = dd as RandomDataDescriptor;
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RealWorldContainerPackingInstanceProvider.cs

    r15471 r15473  
    2828using System.Text.RegularExpressions;
    2929using HeuristicLab.Problems.Instances;
     30using HeuristicLab.Problems.BinPacking3D.Instances;
    3031
    3132namespace HeuristicLab.Problems.BinPacking3D {
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs

    r15471 r15473  
    5454    /// <param name="packingItem"></param>
    5555    /// <param name="position"></param>
    56     protected void PackItem(ref BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) {
     56    protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) {
    5757
    5858      packingBin.PackItem(itemId, packingItem, position);
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs

    r15471 r15473  
    6767        // if a valid packing position could be found, the current item can be added to the given bin
    6868        if (position != null) {
    69           PackItem(ref packingBin, itemId, items[itemId], position, useStackingConstraints);
     69          PackItem(packingBin, itemId, items[itemId], position, useStackingConstraints);
    7070          remainingIds.Remove(itemId);
    7171        }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs

    r15471 r15473  
    6464          var bin = packingBin;
    6565          if (positionFound) {
    66             PackItem(ref bin, remainingId, item, position, useStackingConstraints);
     66            PackItem(bin, remainingId, item, position, useStackingConstraints);
    6767            break;
    6868          }
     
    7777          }
    7878
    79           PackItem(ref packingBin, remainingId, item, position, useStackingConstraints);
     79          PackItem(packingBin, remainingId, item, position, useStackingConstraints);
    8080          packingList.Add(packingBin);
    8181        }
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs

    r15471 r15473  
    5656          if (point.Item1.IsPositionFeasible(item, point.Item2, useStackingConstraints)) {
    5757            var binPacking = point.Item1;
    58             PackItem(ref binPacking, remainingId, item, point.Item2, useStackingConstraints);
     58            PackItem(binPacking, remainingId, item, point.Item2, useStackingConstraints);
    5959            packed = true;
    6060            break;
     
    6666          var position = FindPackingPositionForItem(binPacking, item, useStackingConstraints, rotated);
    6767          if (position != null) {
    68             PackItem(ref binPacking, remainingId, item, position, useStackingConstraints);
     68            PackItem(binPacking, remainingId, item, position, useStackingConstraints);
    6969          } else {
    7070            throw new InvalidOperationException("Item " + remainingId + " cannot be packed in an empty bin.");
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ProblemBase.cs

    r15471 r15473  
    3030using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3131using HeuristicLab.Problems.Instances;
     32using HeuristicLab.Problems.BinPacking3D.Encoding;
     33using HeuristicLab.Problems.BinPacking3D.Evaluators;
     34using HeuristicLab.Problems.BinPacking3D.Instances;
    3235
    3336namespace HeuristicLab.Problems.BinPacking3D {
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs

    r15454 r15473  
    5151    public SortedSet<TPos> ExtremePoints { get; protected set; }
    5252
    53     [Storable]
    54     protected Dictionary<int, List<int>> OccupationLayers { get; set; }
    55    
    56     #endregion Properties
     53    public double PackingDensity {
     54      get {
     55        double result = 0;
     56        foreach (var entry in Items)
     57          result += entry.Value.Volume;
     58        result /= BinShape.Volume;
     59        return result;
     60      }
     61    }
    5762
    5863    public int FreeVolume {
    5964      get { return BinShape.Volume - Items.Sum(x => x.Value.Volume); }
    6065    }
    61 
     66    #endregion Properties
     67   
    6268    protected BinPacking(TBin binShape)
    6369      : base() {
     
    6672      BinShape = (TBin)binShape.Clone();
    6773      ExtremePoints = new SortedSet<TPos>();
    68       OccupationLayers = new Dictionary<int, List<int>>();
    6974    }
    7075
    7176    [StorableConstructor]
    7277    protected BinPacking(bool deserializing) : base(deserializing) { }
     78
    7379    protected BinPacking(BinPacking<TPos, TBin, TItem> original, Cloner cloner)
    7480      : base(original, cloner) {
     
    8389      this.BinShape = (TBin)original.BinShape.Clone(cloner);
    8490      this.ExtremePoints = new SortedSet<TPos>(original.ExtremePoints.Select(p => cloner.Clone(p)));
    85       this.OccupationLayers = new Dictionary<int, List<int>>();
    86       foreach (var kvp in original.OccupationLayers) {
    87         OccupationLayers.Add(kvp.Key, new List<int>(kvp.Value));
    88       }
    8991    }
    90 
     92   
     93    /// <summary>
     94    /// Generate new extreme points for a given item
     95    /// </summary>
     96    /// <param name="item"></param>
     97    /// <param name="position"></param>
    9198    protected abstract void GenerateNewExtremePointsForNewItem(TItem item, TPos position);
    92 
    93     public abstract TPos FindExtremePointForItem(TItem item, bool rotated, bool stackingConstraints);
    94     public abstract TPos FindPositionBySliding(TItem item, bool rotated, bool stackingConstraints);
    95 
    96     public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints);
    97     public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints);
    98     public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints);
    99     public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray);
    100 
    101     public virtual void PackItem(int itemID, TItem item, TPos position) {
    102       Items[itemID] = item;
    103       Positions[itemID] = position;
    104       ExtremePoints.Remove(position);
    105       GenerateNewExtremePointsForNewItem(item, position);
    106      
    107       AddNewItemToOccupationLayers(itemID, item, position);
    108     }
    109     public virtual bool PackItemIfFeasible(int itemID, TItem item, TPos position, bool stackingConstraints) {
    110       if (IsPositionFeasible(item, position, stackingConstraints)) {
    111         PackItem(itemID, item, position);
    112         return true;
    113       }
    114       return false;
    115     }
    116 
    117     public double PackingDensity {
    118       get {
    119         double result = 0;
    120         foreach (var entry in Items)
    121           result += entry.Value.Volume;
    122         result /= BinShape.Volume;
    123         return result;
    124       }
    125     }
    126 
    127 
    128     public int PointOccupation(TPos position) {
    129       foreach (var id in GetLayerItemIDs(position)) {
    130         if (Items[id].EnclosesPoint(Positions[id], position))
    131           return id;
    132       }
    133       return -1;
    134     }
    135 
    136     public bool IsPointOccupied(TPos position) {
    137       foreach (var id in GetLayerItemIDs(position)) {
    138         if (Items[id].EnclosesPoint(Positions[id], position))
    139           return true;
    140       }
    141       return false;
    142     }
    143 
     99   
    144100    /// <summary>
    145     ///
     101    /// Packs an item into the bin packing
     102    /// </summary>
     103    /// <param name="itemID"></param>
     104    /// <param name="item"></param>
     105    /// <param name="position"></param>
     106    public abstract void PackItem(int itemID, TItem item, TPos position);
     107   
     108    /// <summary>
     109    /// Checks if the given position is feasible for the given item
    146110    /// </summary>
    147111    /// <param name="item"></param>
    148112    /// <param name="position"></param>
    149113    /// <param name="stackingConstraints"></param>
    150     /// <returns></returns>
    151     public virtual bool IsPositionFeasible(TItem item, TPos position, bool stackingConstraints) {
    152       //In this case feasability is defined as following:
    153       //1. the item fits into the bin-borders;
    154       //2. the point is supported by something;
    155       //3. the item does not collide with another already packed item
    156       if (!BinShape.Encloses(position, item))
    157         return false;
     114    /// <returns>Returns true if the given position is feasible for the given item</returns>
     115    public abstract bool IsPositionFeasible(TItem item, TPos position, bool stackingConstraints);
    158116
    159       foreach (var id in GetLayerItemIDs(item, position)) {
    160         if (Items[id].Overlaps(Positions[id], position, item))
    161           return false;
    162       }
    163 
    164       return true;
    165     }
     117    /// <summary>
     118    /// Checks if the given item is static stable on the given position
     119    /// </summary>
     120    /// <param name="measures">Item</param>
     121    /// <param name="position">Position of the item</param>
     122    /// <returns>Returns true if the given item is static stable on the given position</returns>
     123    public abstract bool IsStaticStable(TItem measures, TPos position);
    166124   
    167     public abstract int ShortestPossibleSideFromPoint(TPos position);
    168     public abstract bool IsStaticStable(TItem measures, TPos position);
    169 
    170     protected abstract void InitializeOccupationLayers();
    171     protected abstract void AddNewItemToOccupationLayers(int itemID, TItem item, TPos position);
    172     protected abstract List<int> GetLayerItemIDs(TPos position);
    173     protected abstract List<int> GetLayerItemIDs(TItem item, TPos position);
     125   
    174126  }
    175127}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

    r15462 r15473  
    107107    <Compile Include="3D\Packer\BinPackerFirstFit.cs" />
    108108    <Compile Include="3D\BinPacking3D.cs" />
    109     <Compile Include="3D\Decoder\ExtremePointPermutationDecoder.cs" />
     109    <Compile Include="3D\Encoding\ExtremePointPermutationDecoder.cs" />
    110110    <Compile Include="3D\Evaluators\BinUtilizationEvaluator.cs" />
    111111    <Compile Include="3D\Evaluators\PackingRatioEvaluator.cs" />
     
    120120    <Compile Include="3D\Instances\RandomDataDescriptor.cs" />
    121121    <Compile Include="3D\Instances\RealWorldContainerPackingInstanceProvider.cs" />
    122     <Compile Include="3D\IntegerVectorEncoding\ThreeDInstanceParser.cs" />
    123     <Compile Include="3D\IntegerVectorEncoding\BottomLeftIntegerVectorDecoder.cs" />
    124     <Compile Include="3D\IntegerVectorEncoding\ExtremePointIntegerVectorDecoder.cs" />
    125     <Compile Include="3D\IntegerVectorEncoding\IntegerVectorDecoderBase.cs" />
    126     <Compile Include="3D\IntegerVectorEncoding\IntegerVectorProblem.cs" />
    127     <Compile Include="3D\Interfaces\IDecoder.cs" />
    128     <Compile Include="3D\Interfaces\IEvaluator.cs" />
    129     <Compile Include="3D\Interfaces\IOperator.cs" />
    130     <Compile Include="3D\MoveEvaluatorBase.cs" />
     122    <Compile Include="3D\Instances\ThreeDInstanceParser.cs" />
     123    <Compile Include="3D\Encoding\IDecoder.cs" />
     124    <Compile Include="3D\Evaluators\IEvaluator.cs" />
     125    <Compile Include="3D\IOperator.cs" />
     126    <Compile Include="3D\Evaluators\MoveEvaluatorBase.cs" />
    131127    <Compile Include="3D\PackingItem.cs" />
    132128    <Compile Include="3D\PackingPosition.cs" />
    133129    <Compile Include="3D\PackingShape.cs" />
    134     <Compile Include="3D\PermutationEncoding\PermutationProblem.cs" />
    135     <Compile Include="3D\PermutationEncoding\Swap2MoveEvaluator.cs" />
    136     <Compile Include="3D\PermutationEncoding\TranslocationMoveEvaluator.cs" />
     130    <Compile Include="3D\Encoding\PermutationProblem.cs" />
     131    <Compile Include="3D\Evaluators\Swap2MoveEvaluator.cs" />
     132    <Compile Include="3D\Evaluators\TranslocationMoveEvaluator.cs" />
    137133    <Compile Include="3D\ProblemBase.cs" />
    138134    <Compile Include="3D\Solution.cs" />
    139     <Compile Include="3D\Sorting\PackingItemSorter.cs" />
    140     <Compile Include="Algorithms\3D\ExtremePointAlgorithm.cs" />
     135    <Compile Include="3D\Sorting\PermutationPackingItemSorter.cs" />
     136    <Compile Include="3D\Algorithms\ExtremePointAlgorithm.cs" />
    141137    <Compile Include="BinPacking.cs" />
    142138    <Compile Include="Interfaces\IPackingItem.cs">
     
    162158    <None Include="Plugin.cs.frame" />
    163159  </ItemGroup>
    164   <ItemGroup>
    165     <Folder Include="3D\Algorithms\" />
    166   </ItemGroup>
     160  <ItemGroup />
    167161  <ItemGroup>
    168162    <ProjectReference Include="..\..\HeuristicLab.Analysis\3.3\HeuristicLab.Analysis-3.3.csproj">
  • branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/PermutationSortingTest.cs

    r15463 r15473  
    145145    public void TestSortByMaterialClusteredAreaHeightExtension() {
    146146      Permutation actual = _items.SortByMaterialClusteredAreaHeight(_packingShape, 1.0);
    147       Permutation expected = new Permutation(PermutationTypes.Absolute, new int[] { 0, 2, 5, 7, 8, 10, 13, 9, 11, 12, 14, 1, 3, 4, 6 });
     147      Permutation expected = new Permutation(PermutationTypes.Absolute, new int[] { 8, 13, 3, 2, 7, 12, 11, 1, 6, 0, 5, 10, 9, 14, 4 });
    148148      for (int i = 0; i < expected.Length; i++) {
    149149        Assert.AreEqual(expected[i], actual[i]);
  • branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/RandomInstanceProviderTest.cs

    r15471 r15473  
    4444    private IDictionary<string, List<Dimension>> ReadReferenceItemLists() {
    4545      var itemList = new Dictionary<string, List<Dimension>>();
    46       string path = @".\..\HeuristicLab.Tests\HeuristicLab.Problems.Bin-Packing-3.3\ReferenceInstances";
     46      string path = @".\..\HeuristicLab.Tests\HeuristicLab.Problems.Bin-Packing-3.3\TestInstances\ReferenceInstances";
    4747
    4848      string[] files = Directory.GetFiles(path);
  • branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r15471 r15473  
    586586    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\PermutationSortingTest.cs" />
    587587    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\ExtremePointAlgorithmTest.cs" />
     588    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\3D\ThreeDInstanceParserTest.cs" />
    588589    <Compile Include="HeuristicLab.Problems.Bin-Packing-3.3\Utils\TestUtils.cs" />
    589590    <Compile Include="HeuristicLab.Problems.DataAnalysis-3.4\ThresholdCalculatorsTest.cs" />
Note: See TracChangeset for help on using the changeset viewer.