source: trunk/sources/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs @ 15241

Last change on this file since 15241 was 15241, checked in by abeham, 5 years ago

#2762:

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