File DialQueue.h

↰ Parent directory (ADS/priority)

A monotone bucket queue with overflow, beyond the book: the queue of Dial on a circular window of W buckets, W a power of 2, the keys out of the window in a radix heap [see File RadixHeap.h].

Definition (ADS/priority/DialQueue.h)

Detailed Description

It serves the algorithms whose extracted keys never decrease and whose pushed keys stay close to the last one extracted, :math:` ell : Dijkstra’s algorithm with integer weights at most C < W, where every key pushed is in :math: [ ell , ell + C ] `, and the event simulations with bounded delays.

A key k in :math:` [ ell , ell + W ) ` goes to the bucket :math:` k bmod W , a vector used as a stack, which holds a single key since the window is W wide; a key beyond it goes to the overflow. A bit per bucket tells whether it has items, so that the next key in use is found by scanning W / 64 words at most, from the bucket of :math: ell ` around the circle. When the overflow holds a key smaller than the first bucket in use (or the buckets are empty), its items in the window :math:` [ ell’ , ell’ + W ) ` of its least key :math:` ell’ ` move to the buckets, each once, a bucket of the radix heap at a time [see RadixHeap::extractBelow()]. Hence, with all the keys pushed in :math:` [ ell , ell + C ] , C < W, the overflow is never used, push() takes O( 1 ) time and pop() :math: O( 1 + W / w ) , w = 64, against the :math: O( 1 + C ) ` of the scan of the buckets one by one; a key pushed farther costs its moves in the radix heap and one move into the window. The buckets keep their memory, so that a queue in a steady state calls no allocator, and their items are contiguous.

The contracts [see File Contract.h]: a key pushed is not smaller than the last one extracted (any key before the first and after clear()), top(), topKey() and pop() need a queue that is not empty; the invariant, checked on queues of at most 1024 items, is that the bits tell the buckets in use and that the buckets and the overflow count size() items. The operations are defined in DialQueue.tpp.

    1. Dial, Algorithm 360: shortest-path forest with topological ordering, Communications of the ACM 12(11), 632-633, 1969, doi:10.1145/363269.363610

    1. Cherkassky, A. V. Goldberg, T. Radzik, Shortest paths algorithms: theory and experimental evaluation, Mathematical Programming 73(2), 129-174, 1996, doi:10.1007/BF02592101

    1. Ahuja, K. Mehlhorn, J. Orlin, R. E. Tarjan, Faster algorithms for the shortest path problem, Journal of the ACM 37(2), 213-223, 1990, doi:10.1145/77600.77615

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/priority/RadixHeap.h (File RadixHeap.h)

  • ADS/priority/impl/DialQueue.tpp

  • bit

  • concepts

  • cstddef

  • cstdint

  • limits

  • type_traits

  • utility

  • vector

Namespaces

Classes