Ticket #15 (reopened defect)

Opened 5 years ago

Last modified 5 years ago

Add Priority Queue

Reported by: thomasm Owned by: mgreve
Priority: blocker Milestone: 1.0
Version: Keywords:
Cc:

Description

TPIE should have it's own priority queue. Lars Hvam Petersen has developed a couple of priority queues for his masters thesis and has made the source available for TPIE. I have put it here:  http://www.daimi.au.dk/~thomasm/tpie/larsthesis/

He suggests using the 'sanders' priority queue. Note that the code needs a lot of cleaning up and uses stxxl in places, which needs to go away.

Change History

Changed 5 years ago by thomasm

  • owner set to mgreve

Changed 5 years ago by mgreve

  • status changed from new to closed
  • resolution set to fixed

Kasper and I have added PQSequence3 from Lars Hvam Petersen's masters thesis. This is an implementation of Peter Sander's external priority queue from his article Fast Priority Queues for Cached Memory.

The priority consists of the following files in tpie/: priority_queue.h, priority_queue.inl pq_overflow_heap.h, pq_overflow_heap.inl pq_merge_heap.h, pq_merge_heap.inl pq_internal_heap.h, pq_internal_heap.inl

We fixed a couple of memory-allocation related bugs in the original source code, rewrote the internal heap, and all output going to stdout now goes to the logging system in TPIE.

A couple of tests are placed in test/test_priority_queue.cpp.

Changed 5 years ago by thomasm

  • status changed from closed to reopened
  • resolution fixed deleted

The priority queue does not have doxygen comments. I don't think we should close this bug (or any other bug concerning new functionality) before everything is documented.

Note: See TracTickets for help on using tickets.