source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs @ 15554

Last change on this file since 15554 was 15554, checked in by rhanghof, 21 months ago

#2817:

  • Unittests
  • Bugfixes on the line projection based extreme point creation method
File size: 4.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Encodings.PermutationEncoding;
25using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation;
27using System;
28using System.Collections.Generic;
29using System.Linq;
30using System.Text;
31using System.Threading.Tasks;
32
33namespace HeuristicLab.Problems.BinPacking3D.Packer {
34  internal class BinPackerFirstFit : BinPacker {
35    #region Constructors for HEAL
36    [StorableConstructor]
37    protected BinPackerFirstFit(bool deserializing) : base(deserializing) { }
38
39    protected BinPackerFirstFit(BinPackerFirstFit original, Cloner cloner) 
40      : base(original, cloner) {
41    }
42
43    public override IDeepCloneable Clone(Cloner cloner) {
44      return new BinPackerFirstFit(this, cloner);
45    }
46    #endregion
47
48    public BinPackerFirstFit() : base() { }   
49
50    /// <summary>
51    /// Packs the items of the object by using a first fit algorithm into an amount of bins and returns them.
52    /// </summary>
53    /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns>
54    public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) {
55      IList<BinPacking3D> packingList = new List<BinPacking3D>();
56      IList<int> remainingIds = new List<int>(sortedItems);
57
58      while (remainingIds.Count > 0) {
59        BinPacking3D packingBin = new BinPacking3D(binShape);
60        PackRemainingItems(ref remainingIds, ref packingBin, items, epGenerationMethod, useStackingConstraints, null);
61        packingList.Add(packingBin);
62      }
63
64      return packingList;
65    }
66
67    /// <summary>
68    /// Tries to pack the remainig items into a given BinPacking3D object. Each item could be packed into the BinPacking3D object will be removed from the list of remaining ids
69    /// </summary>
70    /// <param name="remainingIds">List of remaining ids. After the method has been executed the list has to have less items</param>
71    /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param>
72    /// <param name="packingBin">This object will be filled with some of the given items</param>
73    protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {
74      IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints);
75      foreach (var itemId in new List<int>(remainingIds)) {
76        bool rotated = rotationArray == null ? false : rotationArray[itemId];
77        PackingPosition position = FindPackingPositionForItem(packingBin, items[itemId], useStackingConstraints, rotated);
78        // if a valid packing position could be found, the current item can be added to the given bin
79        if (position != null) {
80          PackItem(packingBin, itemId, items[itemId], position, extremePointCreator, useStackingConstraints);
81          remainingIds.Remove(itemId);
82        }
83      }
84    }
85  }
86}
Note: See TracBrowser for help on using the repository browser.