[9596] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[13032] | 3 | * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[9596] | 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 |
|
---|
| 22 | using System.Collections.Generic;
|
---|
| 23 | using System.Linq;
|
---|
| 24 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 25 | using HeuristicLab.Core;
|
---|
| 26 | using HeuristicLab.Common;
|
---|
| 27 | using HeuristicLab.Collections;
|
---|
| 28 |
|
---|
[14151] | 29 | namespace HeuristicLab.Problems.BinPacking {
|
---|
[9596] | 30 | [Item("BinPacking", "Represents a single-bin packing for a bin-packing problem.")]
|
---|
| 31 | [StorableClass]
|
---|
[14146] | 32 | public abstract class BinPacking<D, B, I> : Item
|
---|
[14048] | 33 | where D : class, IPackingPosition
|
---|
[14045] | 34 | where B : PackingShape<D>
|
---|
[14146] | 35 | where I : PackingShape<D> {
|
---|
[9596] | 36 | #region Properties
|
---|
| 37 | [Storable]
|
---|
[14146] | 38 | public ObservableDictionary<int, D> ItemPositions { get; private set; }
|
---|
[9596] | 39 |
|
---|
| 40 | [Storable]
|
---|
[14128] | 41 | public ObservableDictionary<int, I> ItemMeasures { get; private set; } // TODO: rename to items
|
---|
[9596] | 42 |
|
---|
| 43 | [Storable]
|
---|
[14146] | 44 | public B BinMeasures { get; private set; }
|
---|
[9596] | 45 |
|
---|
| 46 | [Storable]
|
---|
[9599] | 47 | public SortedSet<D> ExtremePoints { get; protected set; }
|
---|
[9596] | 48 |
|
---|
[9599] | 49 | [Storable]
|
---|
| 50 | protected Dictionary<int, List<int>> OccupationLayers { get; set; }
|
---|
| 51 |
|
---|
[9596] | 52 | #endregion Properties
|
---|
| 53 |
|
---|
[14146] | 54 | protected BinPacking(B binMeasures)
|
---|
| 55 | : base() {
|
---|
[9596] | 56 | ItemPositions = new ObservableDictionary<int, D>();
|
---|
| 57 | ItemMeasures = new ObservableDictionary<int, I>();
|
---|
| 58 | BinMeasures = (B)binMeasures.Clone();
|
---|
[9599] | 59 | OccupationLayers = new Dictionary<int, List<int>>();
|
---|
[13578] | 60 | InitializeOccupationLayers(); // TODO
|
---|
[9596] | 61 | }
|
---|
| 62 |
|
---|
[9599] | 63 |
|
---|
[9596] | 64 | [StorableConstructor]
|
---|
| 65 | protected BinPacking(bool deserializing) : base(deserializing) { }
|
---|
[14146] | 66 | protected BinPacking(BinPacking<D, B, I> original, Cloner cloner)
|
---|
[9596] | 67 | : base(original, cloner) {
|
---|
| 68 | this.ItemPositions = new ObservableDictionary<int, D>(original.ItemPositions);
|
---|
| 69 | this.ItemMeasures = new ObservableDictionary<int, I>(original.ItemMeasures);
|
---|
[14146] | 70 | this.BinMeasures = (B)original.BinMeasures.Clone(cloner);
|
---|
| 71 | this.OccupationLayers = new Dictionary<int, List<int>>(original.OccupationLayers);
|
---|
[9596] | 72 | }
|
---|
[14146] | 73 |
|
---|
[9596] | 74 | protected abstract void GenerateNewExtremePointsForNewItem(I measures, D position);
|
---|
| 75 |
|
---|
| 76 | public abstract D FindExtremePointForItem(I measures, bool rotated, bool stackingConstraints);
|
---|
| 77 | public abstract D FindPositionBySliding(I measures, bool rotated);
|
---|
| 78 |
|
---|
[14146] | 79 | public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<I> itemMeasures);
|
---|
| 80 | public abstract void SlidingBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, Dictionary<int, bool> rotationArray);
|
---|
| 81 | public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, bool stackingConstraints);
|
---|
| 82 | public abstract void ExtremePointBasedPacking(ref IList<int> sequence, IList<I> itemMeasures, bool stackingConstraints, Dictionary<int, bool> rotationArray);
|
---|
[9596] | 83 |
|
---|
| 84 | public void PackItem(int itemID, I measures, D position) {
|
---|
| 85 | ItemMeasures[itemID] = measures;
|
---|
| 86 | ItemPositions[itemID] = position;
|
---|
| 87 | ExtremePoints.Remove(position);
|
---|
[9599] | 88 | foreach (int id in ItemMeasures.Select(x => x.Key))
|
---|
| 89 | GenerateNewExtremePointsForNewItem(ItemMeasures[id], ItemPositions[id]);
|
---|
| 90 |
|
---|
| 91 | AddNewItemToOccupationLayers(itemID, measures, position);
|
---|
[9596] | 92 | }
|
---|
| 93 |
|
---|
[14146] | 94 | public double PackingDensity {
|
---|
[9596] | 95 | get {
|
---|
| 96 | double result = 0;
|
---|
| 97 | foreach (var entry in ItemMeasures)
|
---|
[13605] | 98 | result += entry.Value.Volume;
|
---|
| 99 | result /= BinMeasures.Volume;
|
---|
[9596] | 100 | return result;
|
---|
| 101 | }
|
---|
| 102 | }
|
---|
| 103 |
|
---|
[9598] | 104 |
|
---|
| 105 | public int PointOccupation(D position) {
|
---|
[9599] | 106 | foreach (var id in GetLayerItemIDs(position)) {
|
---|
| 107 | if (ItemMeasures[id].EnclosesPoint(ItemPositions[id], position))
|
---|
| 108 | return id;
|
---|
[9598] | 109 | }
|
---|
| 110 | return -1;
|
---|
| 111 | }
|
---|
[9599] | 112 |
|
---|
[9596] | 113 | public bool IsPointOccupied(D position) {
|
---|
[9599] | 114 | foreach (var id in GetLayerItemIDs(position)) {
|
---|
| 115 | if (ItemMeasures[id].EnclosesPoint(ItemPositions[id], position))
|
---|
[9596] | 116 | return true;
|
---|
| 117 | }
|
---|
| 118 | return false;
|
---|
| 119 | }
|
---|
[9599] | 120 | public bool IsPositionFeasible(I measures, D position) {
|
---|
[9598] | 121 | //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
|
---|
[9599] | 122 | if (!BinMeasures.Encloses(position, measures))
|
---|
[9596] | 123 | return false;
|
---|
| 124 |
|
---|
[9599] | 125 | foreach (var id in GetLayerItemIDs(measures, position)) {
|
---|
| 126 | if (ItemMeasures[id].Overlaps(ItemPositions[id], position, measures))
|
---|
[9596] | 127 | return false;
|
---|
| 128 | }
|
---|
| 129 |
|
---|
| 130 | return true;
|
---|
| 131 | }
|
---|
[14146] | 132 | public abstract int ShortestPossibleSideFromPoint(D position);
|
---|
| 133 | public abstract bool IsStaticStable(I measures, D position);
|
---|
[9599] | 134 |
|
---|
| 135 |
|
---|
| 136 | protected abstract void InitializeOccupationLayers();
|
---|
| 137 | protected abstract void AddNewItemToOccupationLayers(int itemID, I measures, D position);
|
---|
| 138 | protected abstract List<int> GetLayerItemIDs(D position);
|
---|
| 139 | protected abstract List<int> GetLayerItemIDs(I measures, D position);
|
---|
[14146] | 140 | }
|
---|
[9596] | 141 | }
|
---|