1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
// Copyright (c) Microsoft Open Technologies, Inc. All rights reserved. See License.txt in the project root for license information.
using System.Threading;
using System.Collections.Generic;
namespace System.Reactive
{
internal class PriorityQueue<T> where T : IComparable<T>
{
#if !NO_INTERLOCKED_64
private static long _count = long.MinValue;
#else
private static int _count = int.MinValue;
#endif
private IndexedItem[] _items;
private int _size;
public PriorityQueue()
: this(16)
{
}
public PriorityQueue(int capacity)
{
_items = new IndexedItem[capacity];
_size = 0;
}
private bool IsHigherPriority(int left, int right)
{
return _items[left].CompareTo(_items[right]) < 0;
}
private void Percolate(int index)
{
if (index >= _size || index < 0)
return;
var parent = (index - 1) / 2;
if (parent < 0 || parent == index)
return;
if (IsHigherPriority(index, parent))
{
var temp = _items[index];
_items[index] = _items[parent];
_items[parent] = temp;
Percolate(parent);
}
}
private void Heapify()
{
Heapify(0);
}
private void Heapify(int index)
{
if (index >= _size || index < 0)
return;
var left = 2 * index + 1;
var right = 2 * index + 2;
var first = index;
if (left < _size && IsHigherPriority(left, first))
first = left;
if (right < _size && IsHigherPriority(right, first))
first = right;
if (first != index)
{
var temp = _items[index];
_items[index] = _items[first];
_items[first] = temp;
Heapify(first);
}
}
public int Count { get { return _size; } }
public T Peek()
{
if (_size == 0)
throw new InvalidOperationException(Strings_Core.HEAP_EMPTY);
return _items[0].Value;
}
private void RemoveAt(int index)
{
_items[index] = _items[--_size];
_items[_size] = default(IndexedItem);
Heapify();
if (_size < _items.Length / 4)
{
var temp = _items;
_items = new IndexedItem[_items.Length / 2];
Array.Copy(temp, 0, _items, 0, _size);
}
}
public T Dequeue()
{
var result = Peek();
RemoveAt(0);
return result;
}
public void Enqueue(T item)
{
if (_size >= _items.Length)
{
var temp = _items;
_items = new IndexedItem[_items.Length * 2];
Array.Copy(temp, _items, temp.Length);
}
var index = _size++;
_items[index] = new IndexedItem { Value = item, Id = Interlocked.Increment(ref _count) };
Percolate(index);
}
public bool Remove(T item)
{
for (var i = 0; i < _size; ++i)
{
if (EqualityComparer<T>.Default.Equals(_items[i].Value, item))
{
RemoveAt(i);
return true;
}
}
return false;
}
struct IndexedItem : IComparable<IndexedItem>
{
public T Value;
#if !NO_INTERLOCKED_64
public long Id;
#else
public int Id;
#endif
public int CompareTo(IndexedItem other)
{
var c = Value.CompareTo(other.Value);
if (c == 0)
c = Id.CompareTo(other.Id);
return c;
}
}
}
}
|
