---

buckets.h

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

#ifndef BUCKETS_H
#define BUCKETS_H

#include <vector>

#include "../stxxl/containers/stack.h"
#include "../data_structures/sparingStack.h"

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


template <NodeCount nodesPerBucket = 1>
class Buckets
{
public:
    typedef int BucketID;
    
private:
    typedef stxxl::STACK_GENERATOR<RelabeledEdge,
                                   stxxl::external,
                                   stxxl::grow_shrink2,
                                   DS_EXT_PAGE_SIZE,
                                   DS_EXT_BLOCK_SIZE>::result EdgesOfSeveralNodes;

    typedef REWS_SparingStack<DS_INT_EDGES_PER_BLOCK, DS_INT_NO_OF_BLOCKS> EdgesOfOneNode;
    
    typedef CommonPoolOfBlocks<RelabeledEdgeWithoutSource,
                               DS_INT_EDGES_PER_BLOCK,
                               DS_INT_NO_OF_BLOCKS> PoolEdgesOfOneNode;
    
public:
    static BucketID noOfExtBuckets(NodeCount noOfNodes, NodeCount noOfNodesInIntMem);
    
        
    Buckets(EdgeVector<Edge> &graph, MST &result,
            BucketID noOfBuckets, NodeCount noOfNodesInIntMem)
        : _graph( graph ), _result( result ), _extBuckets( noOfBuckets-1 ),
          _noOfNodesInIntMem( noOfNodesInIntMem ),
          _prefetchPool( DS_EXT_PREFETCH_POOL ), _writePool( DS_EXT_WRITE_POOL )
        {
            initBuckets();
            reduceNodes();
        }
    
    InternalMemoryBucket* getIntMemBucket() {return _firstExtBucket;}

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

    MST &_result;

    NodeCount _noOfNodesInIntMem;

    InternalMemoryBucket *_firstExtBucket;
    
    std::vector<EdgesOfSeveralNodes*> _extBuckets;

    stxxl::prefetch_pool<EdgesOfSeveralNodes::block_type> _prefetchPool;

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

    EdgesOfOneNode _intBuckets[nodesPerBucket];

    NodeID _firstNodeIDofCurrentBucket;

    void initBuckets();

    void reduceNodes();

    BucketID bucketID(NodeID nodeID) const;

    void addToExternalBucket(const RelabeledEdge &edge);

    void addToExternalBucket(const RelabeledEdge &edge, BucketID newBucketID);
};


template <NodeCount nodesPerBucket>
inline Buckets<nodesPerBucket>::BucketID Buckets<nodesPerBucket>::bucketID(NodeID nodeID)
const
{
    if (nodeID < _noOfNodesInIntMem) return -1;
    return (nodeID - _noOfNodesInIntMem) / nodesPerBucket;
}

template <NodeCount nodesPerBucket>
inline void Buckets<nodesPerBucket>::addToExternalBucket(const RelabeledEdge &edge)
{
    if ( edge.isSelfLoop() ) return; // Self loops can be ignored.
    addToExternalBucket( edge, bucketID(edge.source()) );
}

template <NodeCount nodesPerBucket>
inline void Buckets<nodesPerBucket>::addToExternalBucket(const RelabeledEdge &edge,
                                                         BucketID newBucketID)
{
    if (newBucketID == -1) {
        // special case
        _firstExtBucket->push_back( edge );
    }
    else {
        _extBuckets[newBucketID]->push( edge );
    }
}

template <NodeCount nodesPerBucket>
inline void Buckets<nodesPerBucket>::add(const RelabeledEdge &edge)
{
    if (edge.source() >= _firstNodeIDofCurrentBucket) {
        // The relabeled edge still belongs to the current external bucket.
        // Therefore it is added to the appropriate internal bucket of one
        // single node.
        _intBuckets[edge.source() - _firstNodeIDofCurrentBucket]
            .push(edge);
    }
    else {
        // The relabeled edge now belongs to another external bucket.
        // Therefore it is added to the appropriate external bucket.
        addToExternalBucket( edge, bucketID(edge.source()) );
    }
}

#endif // BUCKETS_H

---