---

duplicatesRemover.h

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

#ifndef DUPLICATESREMOVER_H
#define DUPLICATESREMOVER_H

template <typename SuperContainer>
class DuplicatesRemover
{
 public:
    DuplicatesRemover(SuperContainer *superContainer)
        : _superContainer( superContainer ), _size( 0 )
        {}

    void insert(const RelabeledEdgeWithoutSource &edge, NodeID source) {
        int index = find( edge.target() );
        if ( empty(index) ) {
            // There is NO edge with the same target node.
            if (_size == _maxSize) {
                // The container is full, so the current edge has to be
                // output directly.
                _superContainer->add( RelabeledEdge(edge, source) );
            }
            else {
                // Add the edge to the container
                _hashMap[index] = HashMapElement( edge, _size );
                _edges[_size++] = edge;
            }
        }
        else {
            // There is another edge with the same target node.
            // So this a duplicate !
            DS_LOGGING2( logging.duplicates().increase() );
            if (edge < _hashMap[index].first) {
                // The current edge has a lower weight than the existing edge.
                // Therefore the existing edge is replaced.
                _edges[ _hashMap[index].second ] = edge;
                _hashMap[index].first = edge;
            }
        }
    }

    void clear(NodeID source) {
        while ( _size > 0 ) {
            clearLocal( _edges[--_size].target() );
            _superContainer->add( RelabeledEdge(_edges[_size], source) );
        }
    }
    
 private:
    static const EdgeCount _maxSize = 1024;

    static const EdgeCount _hashMapSize = 2 * _maxSize;
    
    typedef std::pair<RelabeledEdgeWithoutSource, int> HashMapElement;

    RelabeledEdgeWithoutSource _edges[_maxSize];

    HashMapElement _hashMap[_hashMapSize];

    EdgeCount _size;

    SuperContainer *_superContainer;

    int hashFunction(NodeID x) const {
        return x % _hashMapSize;        
    }

    int find(NodeID x) const {
        int i = hashFunction(x);
        while ((_hashMap[i].first.target() != x) && ( ! empty(i) ))
            i = (i+1) % _hashMapSize;
        return i;
    }

    void clearLocal(NodeID x) {
        int i = hashFunction(x);
        while ( ! empty(i) ) {
            _hashMap[i].first = RelabeledEdgeWithoutSource();
            i = (i+1) % _hashMapSize;
        }
    }

    bool empty(int index) const {
        if ( (_hashMap[index].first.originalSource() == 0) &&
             (_hashMap[index].first.originalTarget() == 0) ) return true;
        return false;
    }

};

#endif // DUPLICATESREMOVER_H

---