Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.BinPacking/3.3/BinPacking.cs @ 14800

Last change on this file since 14800 was 14162, checked in by gkronber, 8 years ago

#2641: first import of bin packing problem (TODO: persistence and sample)

File size: 5.7 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    protected BinPacking(TBin binShape)
56      : base() {
57      Positions = new ObservableDictionary<int, TPos>();
58      Items = new ObservableDictionary<int, TItem>();
59      BinShape = (TBin)binShape.Clone();
60      OccupationLayers = new Dictionary<int, List<int>>();
61    }
62
63
64    [StorableConstructor]
65    protected BinPacking(bool deserializing) : base(deserializing) { }
66    protected BinPacking(BinPacking<TPos, TBin, TItem> original, Cloner cloner)
67      : base(original, cloner) {
68      this.Positions = new ObservableDictionary<int, TPos>();
69      foreach (var kvp in original.Positions) {
70        Positions.Add(kvp.Key, cloner.Clone(kvp.Value));
71      }
72      this.Items = new ObservableDictionary<int, TItem>();
73      foreach (var kvp in original.Items) {
74        Items.Add(kvp.Key, cloner.Clone(kvp.Value));
75      }
76      this.BinShape = (TBin)original.BinShape.Clone(cloner);
77      this.OccupationLayers = new Dictionary<int, List<int>>();
78      foreach (var kvp in original.OccupationLayers) {
79        OccupationLayers.Add(kvp.Key, new List<int>(kvp.Value));
80      }
81    }
82
83    protected abstract void GenerateNewExtremePointsForNewItem(TItem item, TPos position);
84
85    public abstract TPos FindExtremePointForItem(TItem item, bool rotated, bool stackingConstraints);
86    public abstract TPos FindPositionBySliding(TItem item, bool rotated);
87
88    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items);
89    public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<TItem> items, Dictionary<int, bool> rotationArray);
90    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints);
91    public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<TItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray);
92
93    public void PackItem(int itemID, TItem item, TPos position) {
94      Items[itemID] = item;
95      Positions[itemID] = position;
96      ExtremePoints.Remove(position);
97      foreach (int id in Items.Select(x => x.Key))
98        GenerateNewExtremePointsForNewItem(Items[id], Positions[id]);
99
100      AddNewItemToOccupationLayers(itemID, item, position);
101    }
102
103    public double PackingDensity {
104      get {
105        double result = 0;
106        foreach (var entry in Items)
107          result += entry.Value.Volume;
108        result /= BinShape.Volume;
109        return result;
110      }
111    }
112
113
114    public int PointOccupation(TPos position) {
115      foreach (var id in GetLayerItemIDs(position)) {
116        if (Items[id].EnclosesPoint(Positions[id], position))
117          return id;
118      }
119      return -1;
120    }
121
122    public bool IsPointOccupied(TPos position) {
123      foreach (var id in GetLayerItemIDs(position)) {
124        if (Items[id].EnclosesPoint(Positions[id], position))
125          return true;
126      }
127      return false;
128    }
129    public bool IsPositionFeasible(TItem item, TPos position) {
130      //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
131      if (!BinShape.Encloses(position, item))
132        return false;
133
134      foreach (var id in GetLayerItemIDs(item, position)) {
135        if (Items[id].Overlaps(Positions[id], position, item))
136          return false;
137      }
138
139      return true;
140    }
141    public abstract int ShortestPossibleSideFromPoint(TPos position);
142    public abstract bool IsStaticStable(TItem measures, TPos position);
143
144
145    protected abstract void InitializeOccupationLayers();
146    protected abstract void AddNewItemToOccupationLayers(int itemID, TItem item, TPos position);
147    protected abstract List<int> GetLayerItemIDs(TPos position);
148    protected abstract List<int> GetLayerItemIDs(TItem item, TPos position);
149  }
150}
Note: See TracBrowser for help on using the repository browser.