forked from newrelic/node-newrelic
-
Notifications
You must be signed in to change notification settings - Fork 0
/
priority-queue.js
123 lines (101 loc) · 2.66 KB
/
priority-queue.js
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
/*
* Copyright 2020 New Relic Corporation. All rights reserved.
* SPDX-License-Identifier: Apache-2.0
*/
'use strict'
const Heap = require('@tyriar/fibonacci-heap').FibonacciHeap
function PriorityQueue(limit) {
this.limit = limit == null ? 10 : limit
this.seen = 0
this._data = new Heap()
Object.defineProperty(this, 'length', {
get: function getLength() {
return this._data._nodeCount
}
})
}
PriorityQueue.prototype.overflow = function overflow() {
const diff = this.seen - this.limit
return diff >= 0 ? diff : 0
}
PriorityQueue.prototype.getMinimumPriority = function getMinimumPriority() {
return this.length < this.limit ? 0 : this._data.findMinimum().key
}
PriorityQueue.prototype.add = function add(value, priority) {
this.seen++
if (this.limit <= 0) {
return false
}
priority = priority || Math.random()
if (this.length === this.limit) {
return this._replace(value, priority)
}
this._data.insert(priority, value)
return true
}
PriorityQueue.prototype._replace = function _replace(value, priority) {
if (priority > this._data.findMinimum().key) {
this._data.insert(priority, value)
this._data.extractMinimum()
return true
}
return false
}
PriorityQueue.prototype.getRawEvents = function getRawEvents() {
const events = []
const min = this._data.findMinimum()
if (min) {
_getRawEvents(min, events)
}
return events
function _getRawEvents(head, evts) {
let current = head
do {
evts.push({ value: current.value, priority: current.key })
if (current.child) {
_getRawEvents(current.child, evts)
}
current = current.next
} while (current !== head)
}
}
PriorityQueue.prototype.toArray = function toArray() {
const nodes = []
const min = this._data.findMinimum()
if (min) {
serializeHeap(min, nodes)
}
return nodes
function serializeHeap(head, arr) {
let current = head
do {
arr.push(current.value)
if (current.child) {
serializeHeap(current.child, arr)
}
current = current.next
} while (current !== head)
}
}
PriorityQueue.prototype.setLimit = function setLimit(newLimit) {
this.limit = newLimit
while (this.length > newLimit) {
this._data.extractMinimum()
}
}
PriorityQueue.prototype.merge = function merge(events) {
if (!events || !events.length) {
return
}
if (events instanceof PriorityQueue) {
while (events.length) {
const current = events._data.extractMinimum()
this.add(current.value, current.key)
}
} else {
for (let i = 0; i < events.length; ++i) {
this.add(events[i].value, events[i].priority)
}
}
}
module.exports = PriorityQueue