---

pQueue.h

/****************************************************
 *  Bachelor Project:                               *
 *  External Memory Minimum Spanning Trees          *
 *  by Dominik Schultes <mail@dominik-schultes.de>  *
 *                                                  *
 *                pQueue.h                          *
 *                                                  *
 *  July 22, 2003                                   *
 ****************************************************/

#ifndef PQUEUE_H
#define PQUEUE_H


#include "../stxxl/containers/priority_queue.h"

#include "../data_structures/edgeVector.h"
#include "../data_structures/mst.h"


class PQueue
{
 private:
    typedef stxxl::PRIORITY_QUEUE_GENERATOR<RelabeledEdge,
                                            SourceWeightOrdering<RelabeledEdge>,
                                            DS_PQUEUE_INTERNAL_MEMORY,
                                            DS_PQUEUE_MAX_SIZE>::result PriorityQueue;
    
 public:
    PQueue(EdgeVector<Edge> &graph, MST &result, NodeCount noOfNodesInIntMem)
        : _graph( graph ), _result( result ), 
          _noOfNodesInIntMem( noOfNodesInIntMem ),
          _prefetchPool( DS_PQUEUE_PREFETCH_POOL ), _writePool( DS_PQUEUE_WRITE_POOL ),
          _pqueue(_prefetchPool, _writePool)
        {
            initPQueue();
            reduceNodes();
        }
    
    InternalMemoryBucket* getIntMemBucket() {return _firstExtBucket;}

    void add(const RelabeledEdge &edge);
    
 private:
    EdgeVector<Edge> &_graph;

    MST &_result;

    NodeCount _noOfNodesInIntMem;

    InternalMemoryBucket *_firstExtBucket;
    
    stxxl::prefetch_pool<PriorityQueue::block_type> _prefetchPool;

    stxxl::write_pool<PriorityQueue::block_type> _writePool;

    PriorityQueue _pqueue;
    
    void initPQueue();

    void reduceNodes();
};


inline void PQueue::add(const RelabeledEdge &edge)
{
    if ( edge.isSelfLoop() ) return; // Self loops can be ignored.
    
    if (edge.source() < _noOfNodesInIntMem) {
        // add to the first external bucket
        _firstExtBucket->push_back( edge );
    }
    else {
        // add to the priority queue
        _pqueue.push( edge );
    }
}


#endif // PQUEUE_H

---