Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2994-AutoDiffForIntervals/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs @ 17285

Last change on this file since 17285 was 17209, checked in by gkronber, 5 years ago

#2994: merged r17132:17198 from trunk to branch

File size: 6.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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 System.Collections.Generic;
23using System.Linq;
24using HEAL.Attic;
25using HeuristicLab.Core;
26using HeuristicLab.Common;
27using HeuristicLab.Collections;
28
29namespace HeuristicLab.Problems.BinPacking {
30  [Item("BinPacking", "Represents a single-bin packing for a bin-packing problem.")]
31  [StorableType("7B0C7B64-CB50-405F-9F73-15B7C86F9B86")]
32  public abstract class BinPacking<TPos, TBin, TItem> : Item
33    where TPos : class, IPackingPosition
34    where TBin : PackingShape<TPos>
35    where TItem : PackingShape<TPos> {
36    #region Properties
37    [Storable]
38    public ObservableDictionary<int, TPos> Positions { get; private set; }
39
40    [Storable]
41    public ObservableDictionary<int, TItem> Items { get; private set; }
42
43    [Storable]
44    public TBin BinShape { get; private set; }
45
46    [Storable]
47    public SortedSet<TPos> ExtremePoints { get; protected set; }
48
49    [Storable]
50    protected Dictionary<int, List<int>> OccupationLayers { get; set; }
51   
52    #endregion Properties
53
54    public int FreeVolume {
55      get { return BinShape.Volume - Items.Sum(x => x.Value.Volume); }
56    }
57
58    protected BinPacking(TBin binShape)
59      : base() {
60      Positions = new ObservableDictionary<int, TPos>();
61      Items = new ObservableDictionary<int, TItem>();
62      BinShape = (TBin)binShape.Clone();
63      ExtremePoints = new SortedSet<TPos>();
64      OccupationLayers = new Dictionary<int, List<int>>();
65    }
66
67    [StorableConstructor]
68    protected BinPacking(StorableConstructorFlag _) : base(_) { }
69    protected BinPacking(BinPacking<TPos, TBin, TItem> original, Cloner cloner)
70      : base(original, cloner) {
71      this.Positions = new ObservableDictionary<int, TPos>();
72      foreach (var kvp in original.Positions) {
73        Positions.Add(kvp.Key, cloner.Clone(kvp.Value));
74      }
75      this.Items = new ObservableDictionary<int, TItem>();
76      foreach (var kvp in original.Items) {
77        Items.Add(kvp.Key, cloner.Clone(kvp.Value));
78      }
79      this.BinShape = (TBin)original.BinShape.Clone(cloner);
80      this.ExtremePoints = new SortedSet<TPos>(original.ExtremePoints.Select(p => cloner.Clone(p)));
81      this.OccupationLayers = new Dictionary<int, List<int>>();
82      foreach (var kvp in original.OccupationLayers) {
83        OccupationLayers.Add(kvp.Key, new List<int>(kvp.Value));
84      }
85    }
86
87    protected abstract void GenerateNewExtremePointsForNewItem(TItem item, TPos position);
88
89    public abstract TPos FindExtremePointForItem(TItem item, bool rotated, bool stackingConstraints);
90    public abstract TPos FindPositionBySliding(TItem item, bool rotated, bool stackingConstraints);
91
92    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints);
93    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints);
94    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints);
95    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray);
96
97    public virtual void PackItem(int itemID, TItem item, TPos position) {
98      Items[itemID] = item;
99      Positions[itemID] = position;
100      ExtremePoints.Remove(position);
101      foreach (int id in Items.Select(x => x.Key))
102        GenerateNewExtremePointsForNewItem(Items[id], Positions[id]);
103     
104      AddNewItemToOccupationLayers(itemID, item, position);
105    }
106    public virtual bool PackItemIfFeasible(int itemID, TItem item, TPos position, bool stackingConstraints) {
107      if (IsPositionFeasible(item, position, stackingConstraints)) {
108        PackItem(itemID, item, position);
109        return true;
110      }
111      return false;
112    }
113
114    public double PackingDensity {
115      get {
116        double result = 0;
117        foreach (var entry in Items)
118          result += entry.Value.Volume;
119        result /= BinShape.Volume;
120        return result;
121      }
122    }
123
124
125    public int PointOccupation(TPos position) {
126      foreach (var id in GetLayerItemIDs(position)) {
127        if (Items[id].EnclosesPoint(Positions[id], position))
128          return id;
129      }
130      return -1;
131    }
132
133    public bool IsPointOccupied(TPos position) {
134      foreach (var id in GetLayerItemIDs(position)) {
135        if (Items[id].EnclosesPoint(Positions[id], position))
136          return true;
137      }
138      return false;
139    }
140    public virtual bool IsPositionFeasible(TItem item, TPos position, bool stackingConstraints) {
141      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the point is supported by something; 3. the item does not collide with another already packed item
142      if (!BinShape.Encloses(position, item))
143        return false;
144
145      foreach (var id in GetLayerItemIDs(item, position)) {
146        if (Items[id].Overlaps(Positions[id], position, item))
147          return false;
148      }
149
150      return true;
151    }
152   
153    public abstract int ShortestPossibleSideFromPoint(TPos position);
154    public abstract bool IsStaticStable(TItem measures, TPos position);
155
156    protected abstract void InitializeOccupationLayers();
157    protected abstract void AddNewItemToOccupationLayers(int itemID, TItem item, TPos position);
158    protected abstract List<int> GetLayerItemIDs(TPos position);
159    protected abstract List<int> GetLayerItemIDs(TItem item, TPos position);
160  }
161}
Note: See TracBrowser for help on using the repository browser.