1 | #region License Information
|
---|
2 | /* HeuristicLab
|
---|
3 | * Copyright (C) 2002-2016 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 |
|
---|
22 | using System;
|
---|
23 | using System.Collections.Generic;
|
---|
24 | using System.Linq;
|
---|
25 |
|
---|
26 | namespace HeuristicLab.Algorithms.DataAnalysis {
|
---|
27 |
|
---|
28 | // Code Taken from branch: RoutePlanning, Heap4
|
---|
29 | // implementation based on C++ version from Peter Sanders
|
---|
30 | // http://www.mpi-inf.mpg.de/~sanders/programs/spq/
|
---|
31 | public sealed class PriorityQueue<TK, TV> where TK : IComparable {
|
---|
32 | private class KNElement {
|
---|
33 | public TK Key { get; set; }
|
---|
34 | public TV Value { get; set; }
|
---|
35 | }
|
---|
36 |
|
---|
37 | private readonly int capacity;
|
---|
38 | private int size; // index of last used element
|
---|
39 | private int finalLayerSize; // size of first layer with free space
|
---|
40 | private int finalLayerDist; // distance to end of layer
|
---|
41 | //private KNElement[] rawData;
|
---|
42 | private readonly KNElement[] data; // aligned version of rawData
|
---|
43 |
|
---|
44 | public PriorityQueue(TK supremum, TK infimum, int cap) {
|
---|
45 | capacity = cap;
|
---|
46 | data = Enumerable.Range(0, capacity + 4).Select(x => new KNElement()).ToArray();
|
---|
47 |
|
---|
48 | data[0].Key = infimum; // sentinel
|
---|
49 | data[capacity + 1].Key = supremum;
|
---|
50 | data[capacity + 2].Key = supremum;
|
---|
51 | data[capacity + 3].Key = supremum;
|
---|
52 | Reset();
|
---|
53 | }
|
---|
54 |
|
---|
55 | public int Size {
|
---|
56 | get { return size; }
|
---|
57 | }
|
---|
58 |
|
---|
59 | public TK Supremum {
|
---|
60 | get { return data[capacity + 1].Key; }
|
---|
61 | }
|
---|
62 |
|
---|
63 | public KeyValuePair<TK, TV> PeekMin() {
|
---|
64 | if (size == 0) throw new InvalidOperationException("Heap is empty");
|
---|
65 | return new KeyValuePair<TK, TV>(data[1].Key, data[1].Value);
|
---|
66 | }
|
---|
67 |
|
---|
68 | public TK PeekMinKey() {
|
---|
69 | return data[1].Key;
|
---|
70 | }
|
---|
71 |
|
---|
72 | public TV PeekMinValue() {
|
---|
73 | return data[1].Value;
|
---|
74 | }
|
---|
75 |
|
---|
76 | public void RemoveMin() {
|
---|
77 | // first move up elements on a min-path
|
---|
78 | var hole = 1;
|
---|
79 | var succ = 2;
|
---|
80 | var layerSize = 4;
|
---|
81 | var layerPos = 0;
|
---|
82 | var sz = size;
|
---|
83 | size = sz - 1;
|
---|
84 | finalLayerDist++;
|
---|
85 | if (finalLayerDist == finalLayerSize) {
|
---|
86 | finalLayerSize >>= 2;
|
---|
87 | finalLayerDist = 0;
|
---|
88 | }
|
---|
89 |
|
---|
90 | while (succ < sz) {
|
---|
91 | var minKey = data[succ].Key;
|
---|
92 | var delta = 0;
|
---|
93 |
|
---|
94 | for (var i = 1; i <= 3; i++) {
|
---|
95 | var otherKey = data[succ + i].Key;
|
---|
96 | if (otherKey.CompareTo(minKey) >= 0) continue;
|
---|
97 | minKey = otherKey;
|
---|
98 | delta = i;
|
---|
99 | }
|
---|
100 |
|
---|
101 | succ += delta;
|
---|
102 | layerPos += delta;
|
---|
103 |
|
---|
104 | // move min successor up
|
---|
105 | data[hole].Key = minKey;
|
---|
106 | data[hole].Value = data[succ].Value;
|
---|
107 |
|
---|
108 | // step to next layer
|
---|
109 | hole = succ;
|
---|
110 | succ = succ - layerPos + layerSize; // beginning of next layer
|
---|
111 | layerPos <<= 2;
|
---|
112 | succ += layerPos; // now correct value
|
---|
113 | layerSize <<= 2;
|
---|
114 | }
|
---|
115 |
|
---|
116 | // bubble up rightmost element
|
---|
117 | var bubble = data[sz].Key;
|
---|
118 | layerSize >>= 2; // now size of hole's layer
|
---|
119 | layerPos >>= 2; // now pos of hole within its layer
|
---|
120 |
|
---|
121 | var layerDist = layerSize - layerPos - 1; // hole's dist to end of layer
|
---|
122 | var pred = hole + layerDist - layerSize; // end of pred's layer for now
|
---|
123 | layerSize >>= 2; // now size of pred's layer
|
---|
124 | layerDist >>= 2; // now pred's pos in layer
|
---|
125 | pred = pred - layerDist; // finally preds index
|
---|
126 |
|
---|
127 | while (data[pred].Key.CompareTo(bubble) > 0) { // must terminate since inf at root
|
---|
128 | data[hole].Key = data[pred].Key;
|
---|
129 | data[hole].Value = data[pred].Value;
|
---|
130 | hole = pred;
|
---|
131 | pred = hole + layerDist - layerSize; // end of hole's layer for now
|
---|
132 | layerSize >>= 2;
|
---|
133 | layerDist >>= 2;
|
---|
134 | pred = pred - layerDist; // finally preds index
|
---|
135 | }
|
---|
136 |
|
---|
137 | // finally move data to hole
|
---|
138 | data[hole].Key = bubble;
|
---|
139 | data[hole].Value = data[sz].Value;
|
---|
140 | data[sz].Key = Supremum; // mark as deleted
|
---|
141 | }
|
---|
142 |
|
---|
143 | public void Insert(TK key, TV value) {
|
---|
144 | var layerSize = finalLayerSize;
|
---|
145 | var layerDist = finalLayerDist;
|
---|
146 | finalLayerDist--;
|
---|
147 |
|
---|
148 | if (finalLayerDist == -1) { // layer full
|
---|
149 | // start next layer
|
---|
150 | finalLayerSize <<= 2;
|
---|
151 | finalLayerDist = finalLayerSize - 1;
|
---|
152 | }
|
---|
153 |
|
---|
154 | size++;
|
---|
155 |
|
---|
156 | var hole = size;
|
---|
157 | var pred = hole + layerDist - layerSize; // end of pred's layer for now
|
---|
158 | layerSize >>= 2; // now size of pred's layer
|
---|
159 | layerDist >>= 2;
|
---|
160 | pred = pred - layerDist; // finally preds index
|
---|
161 | var predKey = data[pred].Key;
|
---|
162 | while (predKey.CompareTo(key) > 0) {
|
---|
163 | data[hole].Key = predKey;
|
---|
164 | data[hole].Value = data[pred].Value;
|
---|
165 | hole = pred;
|
---|
166 | pred = hole + layerDist - layerSize; // end of pred's layer for now
|
---|
167 | layerSize >>= 2; // now isze of pred's layer
|
---|
168 | layerDist >>= 2;
|
---|
169 | pred = pred - layerDist; // finally preds index
|
---|
170 | predKey = data[pred].Key;
|
---|
171 | }
|
---|
172 |
|
---|
173 | // finally move data to hole
|
---|
174 | data[hole].Key = key;
|
---|
175 | data[hole].Value = value;
|
---|
176 | }
|
---|
177 |
|
---|
178 | // reset size to 0 and fill data array with sentinels
|
---|
179 | private void Reset() {
|
---|
180 | size = 0;
|
---|
181 | finalLayerSize = 1;
|
---|
182 | finalLayerDist = 0;
|
---|
183 | var sup = Supremum;
|
---|
184 | var cap = capacity;
|
---|
185 | for (var i = 1; i <= cap; i++) {
|
---|
186 | data[i].Key = sup;
|
---|
187 | }
|
---|
188 | }
|
---|
189 | }
|
---|
190 | }
|
---|