- Timestamp:
- 07/12/17 15:17:41 (7 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/PriorityQueue.cs
r14785 r15207 25 25 26 26 namespace HeuristicLab.Algorithms.DataAnalysis { 27 // TODO: move to HeuristicLab.Collections28 27 29 28 // Code Taken from branch: RoutePlanning, Heap4 … … 63 62 64 63 public KeyValuePair<TK, TV> PeekMin() { 65 if(size == 0) { 66 throw new InvalidOperationException("Heap is empty"); 67 } 64 if (size == 0) throw new InvalidOperationException("Heap is empty"); 68 65 return new KeyValuePair<TK, TV>(data[1].Key, data[1].Value); 69 66 } … … 86 83 size = sz - 1; 87 84 finalLayerDist++; 88 if (finalLayerDist == finalLayerSize) {85 if (finalLayerDist == finalLayerSize) { 89 86 finalLayerSize >>= 2; 90 87 finalLayerDist = 0; 91 88 } 92 89 93 while (succ < sz) {90 while (succ < sz) { 94 91 var minKey = data[succ].Key; 95 92 var delta = 0; 96 93 97 var otherKey = data[succ + 1].Key; 98 if(otherKey.CompareTo(minKey) < 0) { 94 for (var i = 1; i <= 3; i++) { 95 var otherKey = data[succ + i].Key; 96 if (otherKey.CompareTo(minKey) >= 0) continue; 99 97 minKey = otherKey; 100 delta = 1;98 delta = i; 101 99 } 102 otherKey = data[succ + 2].Key; 103 if(otherKey.CompareTo(minKey) < 0) { 104 minKey = otherKey; 105 delta = 2; 106 } 107 otherKey = data[succ + 3].Key; 108 if(otherKey.CompareTo(minKey) < 0) { 109 minKey = otherKey; 110 delta = 3; 111 } 100 112 101 succ += delta; 113 102 layerPos += delta; … … 136 125 pred = pred - layerDist; // finally preds index 137 126 138 while (data[pred].Key.CompareTo(bubble) > 0) { // must terminate since inf at root127 while (data[pred].Key.CompareTo(bubble) > 0) { // must terminate since inf at root 139 128 data[hole].Key = data[pred].Key; 140 129 data[hole].Value = data[pred].Value; … … 149 138 data[hole].Key = bubble; 150 139 data[hole].Value = data[sz].Value; 151 152 140 data[sz].Key = Supremum; // mark as deleted 153 141 } … … 158 146 finalLayerDist--; 159 147 160 if (finalLayerDist == -1) { // layer full161 // start next layer148 if (finalLayerDist == -1) { // layer full 149 // start next layer 162 150 finalLayerSize <<= 2; 163 151 finalLayerDist = finalLayerSize - 1; … … 172 160 pred = pred - layerDist; // finally preds index 173 161 var predKey = data[pred].Key; 174 while (predKey.CompareTo(key) > 0) {162 while (predKey.CompareTo(key) > 0) { 175 163 data[hole].Key = predKey; 176 164 data[hole].Value = data[pred].Value; … … 195 183 var sup = Supremum; 196 184 var cap = capacity; 197 for (var i = 1; i <= cap; i++) {185 for (var i = 1; i <= cap; i++) { 198 186 data[i].Key = sup; 199 187 }
Note: See TracChangeset
for help on using the changeset viewer.