Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import MinHeap from '../heap/MinHeap';
- import Comparator from '../../utils/comparator/Comparator';
- // It is the same as min heap except that when comparing two elements
- // we take into account its priority instead of the element's value.
- export default class PriorityQueue extends MinHeap {
- constructor() {
- // Call MinHip constructor first.
- super();
- // Setup priorities map.
- this.priorities = new Map();
- // Use custom comparator for heap elements that will take element priority
- // instead of element value into account.
- this.compare = new Comparator(this.comparePriority.bind(this));
- }
- /**
- * Add item to the priority queue.
- * @param {*} item - item we're going to add to the queue.
- * @param {number} [priority] - items priority.
- * @return {PriorityQueue}
- */
- add(item, priority = 0) {
- this.priorities.set(item, priority);
- super.add(item);
- return this;
- }
- /**
- * Remove item from priority queue.
- * @param {*} item - item we're going to remove.
- * @param {Comparator} [customFindingComparator] - custom function for finding the item to remove
- * @return {PriorityQueue}
- */
- remove(item, customFindingComparator) {
- super.remove(item, customFindingComparator);
- this.priorities.delete(item);
- return this;
- }
- /**
- * Change priority of the item in a queue.
- * @param {*} item - item we're going to re-prioritize.
- * @param {number} priority - new item's priority.
- * @return {PriorityQueue}
- */
- changePriority(item, priority) {
- this.remove(item, new Comparator(this.compareValue));
- this.add(item, priority);
- return this;
- }
- /**
- * Find item by ite value.
- * @param {*} item
- * @return {Number[]}
- */
- findByValue(item) {
- return this.find(item, new Comparator(this.compareValue));
- }
- /**
- * Check if item already exists in a queue.
- * @param {*} item
- * @return {boolean}
- */
- hasValue(item) {
- return this.findByValue(item).length > 0;
- }
- /**
- * Compares priorities of two items.
- * @param {*} a
- * @param {*} b
- * @return {number}
- */
- comparePriority(a, b) {
- if (this.priorities.get(a) === this.priorities.get(b)) {
- return 0;
- }
- return this.priorities.get(a) < this.priorities.get(b) ? -1 : 1;
- }
- /**
- * Compares values of two items.
- * @param {*} a
- * @param {*} b
- * @return {number}
- */
- compareValue(a, b) {
- if (a === b) {
- return 0;
- }
- return a < b ? -1 : 1;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement