---

sparingStack.h

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


#ifndef SPARINGSTACK_H
#define SPARINGSTACK_H

template <typename value_type, int elementsPerBlock, int noOfBlocks>
class CommonPoolOfBlocks
{
 public:
    class Block
    {
     public:
        Block()
            : _size( 0 ), _prev( 0 )
            {}

        void push(const value_type &element) {
            _elements[_size++] = element;
        }

        const value_type & top() const {return _elements[_size-1];}

        void pop() {_size--;}

        void clear() {_size = 0;}

        bool empty() const {return (_size==0);}

        bool full() const {return (_size==elementsPerBlock);}

        int size() const {return _size;}

        const value_type & operator[](int index) const {return _elements[index];}

        void setPrevBlock(Block *const prev) {_prev = prev;}

        Block * prevBlock() const {return _prev;}
        
     private:
        int _size;

        Block *_prev;

        value_type _elements[elementsPerBlock];
    };
    

    CommonPoolOfBlocks()
        : _free( &_blocks[noOfBlocks-1] ), _reserveMemory( 0 ),
          _totalNoOfBlocks( noOfBlocks ), _noOfFreeBlocks( noOfBlocks )
        {
            // initialize the linked list of free blocks
            for (int i=noOfBlocks-1; i>0; i--)
                _blocks[i].setPrevBlock(&_blocks[i-1]);
        }

    ~CommonPoolOfBlocks() {
        for (int i=0; i<_additionalBlocks.size(); i++) {
            delete[] _additionalBlocks[i];
            DS_VERBOSE1( std::cout << std::endl
                         << "CommonPoolOfBlocks::~CommonPoolOfBlocks(): "
                         << "additionally created blocks deleted." << std::endl );
        }
    }

    Block * request() {
        
        if ( ! _free ) { // If there are no more free blocks...
            // check if reserve memory is available
            int noOfNewBlocks = _reserveMemory / sizeof( Block );
            if (noOfNewBlocks == 0) {
                // If there is not enough reserve memory, the program is aborted !
                std::cerr << "CommonPoolOfBlocks: request(): No free blocks available !"
                          << std::endl;
                abort();
            }

            DS_VERBOSE1( std::cout << std::endl << "CommonPoolOfBlocks::request(): "
                         << noOfNewBlocks << " new blocks created." << std::endl );

            // allocate new blocks according to the available reserve memory
            _reserveMemory -= noOfNewBlocks * sizeof( Block );
            
            DS_LOGGING2( _totalNoOfBlocks += noOfNewBlocks;
                         _noOfFreeBlocks += noOfNewBlocks );

            Block *newBlocks = new Block[noOfNewBlocks];
            _additionalBlocks.push_back( newBlocks );
            for (int i=0; i<noOfNewBlocks; i++) {
                newBlocks[i].setPrevBlock( _free );
                _free = &newBlocks[i];
            }
        }
        
        DS_LOGGING2( _noOfFreeBlocks-- );

        // return a free block
        Block *block = _free;
        _free = _free->prevBlock();
        return block;
    }

    void release(Block *block) {
        block->setPrevBlock(_free);
        _free = block;

        DS_LOGGING2( _noOfFreeBlocks++ );
    }

    void increaseReserveMemory(int newMemory) {
        _reserveMemory += newMemory;
    }

    
    DS_LOGGING2(
        int noOfBlocksUsed() const {return _totalNoOfBlocks - _noOfFreeBlocks;}
        
        int noOfBlocksFree() const {return _noOfFreeBlocks;}
    )
        
 private:
    Block _blocks[noOfBlocks];

    Block *_free;

    int _reserveMemory;

    std::vector<Block*> _additionalBlocks;
    
    int _totalNoOfBlocks;
    
    int _noOfFreeBlocks;
    
};


template <typename value_type, int elementsPerBlock, int noOfBlocks>
class SparingStack
{
 protected:
    typedef CommonPoolOfBlocks<value_type, elementsPerBlock, noOfBlocks> Pool;
    typedef Pool::Block Block;
    
 public:
    SparingStack() : _top( &_bottom ) {}

    ~SparingStack() {
        while (_top != &_bottom) {
            Block *oldBlock = _top;
            _top = _top->prevBlock();
            oldBlock->clear();
            _pool->release(oldBlock);
        }
    }

    void setPool(Pool *pool) {_pool = pool;}

    bool empty() const {return _top->empty();}

    void push(const value_type &element) {
        if ( _top->full() ) {
            // If the current block is full, request a new one.
            Block *newBlock = _pool->request();
            newBlock->setPrevBlock(_top);
            _top = newBlock;
        }
        _top->push(element);
    }

    const value_type & top() const {return _top->top();}

    void pop() {
        _top->pop();
        if ( (_top->empty()) && (_top != &_bottom) ) {
            // If the current block is now empty, release it.
            // (The 'bottom' block belongs to the stack and is never released.)
            Block *oldBlock = _top;
            _top = _top->prevBlock();
            _pool->release(oldBlock);
        }
    }

    int size() const {
        Block *current = _top;
        int blockCounter = 0;
        while (current != &_bottom) {
            blockCounter++;
            current = current->prevBlock();
        }
        return _top->size() + (blockCounter * DS_INT_EDGES_PER_BLOCK);
    }
    
 protected:
    Pool *_pool;

    Block *_top;

    Block _bottom;  
};


template <int elementsPerBlock, int noOfBlocks>
class REWS_SparingStack : public SparingStack<RelabeledEdgeWithoutSource,
                                              elementsPerBlock,
                                              noOfBlocks>
{
 public:
    NodeID determineMinEdge(MST &result) const {
        // determine the edge with minimum weight
        RelabeledEdgeWithoutSource minEdge = top();
        Block *current = _top;
        while (true) {
            for (int index=current->size()-1; index >= 0; index--) {
                if ( (*current)[index] < minEdge ) minEdge = (*current)[index]; 
            }
            if (current == &_bottom) break;
            current = current->prevBlock();
        }

        // Add the edge with minimum weight incident to the
        // current node to the resulting minimum spanning tree.
        result.add( minEdge );
                
        DS_VERBOSE2( std::cout << "( !!! MST::add = "
                     << minEdge << " )" );

        return minEdge.target();
    }
};


#endif // SPARINGSTACK_H

---