source: branches/2994-AutoDiffForIntervals/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/PriorityQueue.cs @ 17209

Last change on this file since 17209 was 17209, checked in by gkronber, 3 months ago

#2994: merged r17132:17198 from trunk to branch

File size: 6.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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;
25
26namespace 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}
Note: See TracBrowser for help on using the repository browser.