blob: 4f70334a438661aa46023036a2a29ab115dde186 [file] [log] [blame]
 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file // for details. All rights reserved. Use of this source code is governed by a // BSD-style license that can be found in the LICENSE file. library priority_queue; import 'dart:collection'; import 'dart:math'; /** * A priority used for the priority queue. Subclasses only need to implement * the compareTo function. */ abstract class Priority implements Comparable { /** * Return < 0 if other is bigger, >0 if other is smaller, 0 if they are equal. */ int compareTo(dynamic other); bool operator <(dynamic other) => compareTo(other) < 0; bool operator >(dynamic other) => compareTo(other) > 0; bool operator ==(dynamic other) => compareTo(other) == 0; } /** * Priority based on integers. */ class IntPriority extends Priority { int priority; IntPriority(int this.priority); int compareTo(dynamic other) { return (priority - other.priority) as int; } String toString() => "\$priority"; } /** * An element of a priority queue. The type is used restriction based * querying of the queues. */ abstract class TypedElement { bool typeEquals(var other); } class StringTypedElement extends TypedElement { String type; V value; StringTypedElement(String this.type, V this.value); bool typeEquals(dynamic otherType) => otherType == type; String toString() => ""; } /** * A priority node in a priority queue. A priority node contains all of the * values for a given priority in a given queue. It is part of a linked * list of nodes, with prev and next pointers. */ class PriorityNode { T priority; Queue values; PriorityNode? prev; PriorityNode? next; PriorityNode(N initialNode, T this.priority) : values = new Queue() { add(initialNode); } void add(N n) => values.add(n); bool remove(N n) => values.remove(n); N removeFirst() => values.removeFirst(); bool get isEmpty => values.isEmpty; N get first => values.first; String toString() => "Priority: \$priority \$values"; } /** * A priority queue with a FIFO property for nodes with same priority. * The queue guarantees that nodes are returned in the same order they * are added for a given priority. * For type safety this queue is guarded by the elements being subclasses of * TypedElement - this is not strictly neccesary since we never actually * use the value or type of the nodes. */ class PriorityQueue { PriorityNode? head; int length = 0; void add(N value, P priority) { length++; if (head == null) { head = new PriorityNode(value, priority); return; } assert(head!.next == null); var node = head!; while (node.prev != null && node.priority > priority) { node = node.prev as PriorityNode; } if (node.priority == priority) { node.add(value); } else if (node.priority < priority) { var newNode = new PriorityNode(value, priority); newNode.next = node.next; if (node.next != null) node.next!.prev = newNode; newNode.prev = node; node.next = newNode; if (node == head) head = newNode; } else { var newNode = new PriorityNode(value, priority); node.prev = newNode; newNode.next = node; } } N get first => head!.first; Priority get firstPriority => head!.priority; bool get isEmpty => head == null; N removeFirst() { if (isEmpty) throw "Can't get element from empty queue"; var value = head!.removeFirst(); if (head!.isEmpty) { if (head!.prev != null) { head!.prev!.next = null; } head = head!.prev as PriorityNode?; } length--; assert(head == null || head!.next == null); return value; } String toString() { if (head == null) return "Empty priority queue"; var node = head!; var buffer = new StringBuffer(); while (node.prev != null) { buffer.writeln(node); node = node.prev as PriorityNode; } buffer.writeln(node); return buffer.toString(); } } /** * Implements a specialized priority queue that efficiently allows getting * the highest priorized node that adheres to a set of restrictions. * Most notably it allows to get the highest priority node where the node's * type is not in an exclude list. * In addition, the queue has a number of properties: * The queue has fifo semantics for nodes with the same priority and type, * i.e., if nodes a and b are added to the queue with priority x and type z * then a is returned first iff a was added before b * For different types with the same priority no guarantees are given, but * the returned values try to be fair by returning from the biggest list of * tasks in case of priority clash. (This could be fixed by adding timestamps * to every node, that is _only_ used when collisions occur, not for * insertions) */ class RestrictViewPriorityQueue { // We can't use the basic dart priority queue since it does not guarantee // FIFO for items with the same order. This is currently not uptimized for // different N, if many different N is expected here we should have a // priority queue instead of a list. List> restrictedQueues = >[]; PriorityQueue mainQueue = new PriorityQueue(); void add(N value, P priority) { for (var queue in restrictedQueues) { if ((queue.first as StringTypedElement).value == value) { queue.add(value, priority); } } mainQueue.add(value, priority); } bool get isEmpty => restrictedQueues.length + mainQueue.length == 0; int get length => restrictedQueues.fold(0, (v, e) => v + e.length) + mainQueue.length; PriorityQueue? getRestricted(List restrictions) { var current = null; // Find highest restricted priority. for (var queue in restrictedQueues) { if (!restrictions.any((e) => queue.head!.first.typeEquals(e))) { if (current == null || queue.firstPriority > current.firstPriority) { current = queue; } else if (current.firstPriority == queue.firstPriority) { current = queue.length > current.length ? queue : current; } } } return current; } N? get first { if (isEmpty) throw "Trying to remove node from empty queue"; var candidate = getRestricted([]); if (candidate != null && (mainQueue.isEmpty || mainQueue.firstPriority < candidate.firstPriority)) { return candidate.first as N; } return mainQueue.isEmpty ? null : mainQueue.first; } /** * Returns the node that under the given set of restrictions. * If the queue is empty this function throws. * If the queue is not empty, but no node exists that adheres to the * restrictions we return null. */ N? removeFirst({List restrictions: const []}) { if (isEmpty) throw "Trying to remove node from empty queue"; var candidate = getRestricted(restrictions); if (candidate != null && (mainQueue.isEmpty || mainQueue.firstPriority < candidate.firstPriority)) { var value = candidate.removeFirst(); if (candidate.isEmpty) restrictedQueues.remove(candidate); return value as N; } while (!mainQueue.isEmpty) { var currentPriority = mainQueue.firstPriority; var current = mainQueue.removeFirst(); if (!restrictions.any((e) => current.typeEquals(e))) { return current; } else { PriorityQueue? restrictedQueue; for (var e in restrictedQueues) { if (current.typeEquals((e.first as StringTypedElement).type)) { restrictedQueue = e; break; } } if (restrictedQueue == null) { restrictedQueue = new PriorityQueue(); restrictedQueues.add(restrictedQueue); } restrictedQueue.add(current, currentPriority as P); } } return null; } String toString() { if (isEmpty) return "Empty queue"; var buffer = new StringBuffer(); if (!restrictedQueues.isEmpty) { buffer.writeln("Restricted queues"); for (var queue in restrictedQueues) { buffer.writeln("\$queue"); } } buffer.writeln("Main queue:"); buffer.writeln("\$mainQueue"); return buffer.toString(); } } /// TEMPORARY TESTING AND PERFORMANCE void main([args]) { stress(new RestrictViewPriorityQueue()); } void stress(queue) { final int SIZE = 50000; Random random = new Random(29); var priorities = [1, 2, 3, 16, 32, 42, 56, 57, 59, 90]; var values = [ new StringTypedElement('safari', 'foo'), new StringTypedElement('ie', 'bar'), new StringTypedElement('ff', 'foobar'), new StringTypedElement('dartium', 'barfoo'), new StringTypedElement('chrome', 'hest'), new StringTypedElement('drt', 'fisk') ]; var restricted = [values[0], values[4]]; void addRandom() { queue.add(values[random.nextInt(values.length)], new IntPriority(priorities[random.nextInt(priorities.length)])); } var stopwatch = new Stopwatch()..start(); while (queue.length < SIZE) { addRandom(); } stopwatch.stop(); print("Adding took: \${stopwatch.elapsedMilliseconds}"); print("Queue length: \${queue.length}"); stopwatch = new Stopwatch()..start(); while (queue.length > 0) { queue.removeFirst(); } stopwatch.stop(); print("Remowing took: \${stopwatch.elapsedMilliseconds}"); print("Queue length: \${queue.length}"); print("Restricted add/remove"); while (queue.length < SIZE) { addRandom(); } for (int i = 0; i < SIZE; i++) { if (random.nextDouble() < 0.5) { queue.removeFirst(restrictions: restricted); } else { queue.removeFirst(); } addRandom(); } }