priorityqueue.h

/* This file is part of the KOffice libraries
   Copyright (C) 2001 Werner Trobin <trobin@kde.org>
 
   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License version 2 as published by the Free Software Foundation.
 
   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.
 
   You should have received a copy of the GNU Library General Public License
   along with this library; see the file COPYING.LIB.  If not, write to
   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
*/
 
#ifndef priority_queue_h
#define priority_queue_h
 
#include <vector>
#include <tqstring.h>
#include <tqasciidict.h>
#include <kdebug.h>
 
// Better put all those internal classes in some namespace to avoid clashes
// as the names are quite generic
namespace KOffice {

    template<class T> class PriorityQueue {
 
    public:
        PriorityQueue() {}
        PriorityQueue( const PriorityQueue<T>& rhs ) : m_vector( rhs.m_vector ) {}
        PriorityQueue( const TQAsciiDict<T>& items );
        ~PriorityQueue() {}
 
        PriorityQueue<T> &operator=( const PriorityQueue<T>& rhs ) { m_vector = rhs.m_vector; return *this; }
        bool operator==( const PriorityQueue<T>& rhs ) { return m_vector == rhs.m_vector; }
 
        unsigned int count() const { return m_vector.size(); }
        bool isEmpty() const { return m_vector.empty(); }
 
        void insert( T* item );

        void keyDecreased( T* item );
 
        T* extractMinimum();

        void dump() const;
 
    private:
        // Note: We have to use a 1-based index here, and we get/return 0-based ones
        int parent( int i ) { return ( ( i + 1 ) >> 1 ) - 1; }
        int left( int i ) { return ( ( i + 1 ) << 1 ) - 1; }
        int right( int i ) { return ( i + 1 ) << 1; }
 
        void heapify( int i );
        // item is !=0 for sure
        void bubbleUp( T* item, int i );
        // Builds the heap in the vector in O(n)
        void buildHeap();
 
        std::vector<T*> m_vector;
    };
 
    template<class T>
    PriorityQueue<T>::PriorityQueue( const TQAsciiDict<T>& items ) : m_vector( items.count() )
    {
        // First put all items into the vector
        TQAsciiDictIterator<T> it( items );
        for ( int i = 0; it.current(); ++it, ++i ) {
            it.current()->setIndex( i );
            m_vector[ i ] = it.current();
        }
        // Then build a heap in that vector
        buildHeap();
    }
 
    template<class T>
    void PriorityQueue<T>::insert( T* item )
    {
        if ( !item )
            return;
        int i = static_cast<int>( m_vector.size() );
        m_vector.push_back( 0 ); // extend the vector by one item. i == index to the last item
        bubbleUp( item, i );
    }
 
    template<class T>
    void PriorityQueue<T>::keyDecreased( T* item )
    {
        if ( !item )
            return;
        bubbleUp( item, item->index() );
    }
 
    template<class T>
    T* PriorityQueue<T>::extractMinimum()
    {
        if ( m_vector.size() < 1 )
            return 0;
        T *min = m_vector[ 0 ];
        m_vector[ 0 ] = m_vector[ m_vector.size() - 1 ];
        // update the index
        m_vector[ 0 ]->setIndex( 0 );
        m_vector.pop_back();
        heapify( 0 );
        return min;
    }
 
    template<class T>
    void PriorityQueue<T>::dump() const
    {
        kdDebug( 30500 ) << "++++++++++ PriorityQueue::dump ++++++++++" << endl;
        TQString out;
        int size = static_cast<int>( m_vector.size() );
        for ( int i = 0; i < size; ++i ) {
            if ( m_vector[ i ]->index() != i )
                out += " ERROR: index out of sync. Should be " + TQString::number( i ) + ", is " +
                       TQString::number( m_vector[ i ]->index() ) + ". ";
            out += TQString::number( m_vector[ i ]->key() );
            out += ", ";
        }
        if ( out.isEmpty() )
            out = "(empty)";
        kdDebug( 30500 ) << out << endl;
        kdDebug( 30500 ) << "++++++++++ PriorityQueue::dump (done) ++++++++++" << endl;
    }
 
    template<class T>
    void PriorityQueue<T>::heapify( int i )
    {
        int l = left( i ), r = right( i ), size = static_cast<int>( m_vector.size() );
        int smallest;
 
        if ( l < size && m_vector[ l ]->key() < m_vector[ i ]->key() )
            smallest = l;
        else
            smallest = i;
        if ( r < size && m_vector[ r ]->key() < m_vector[ smallest ]->key() )
            smallest = r;
 
        if ( smallest != i ) {
            T* tmp = m_vector[ i ];
            m_vector[ i ] = m_vector[ smallest ];
            // update indices
            m_vector[ i ]->setIndex( i );
            tmp->setIndex( smallest );
            m_vector[ smallest ] = tmp;
            heapify( smallest );
        }
    }
 
    template<class T>
    void PriorityQueue<T>::bubbleUp( T* item, int i )
    {
        int p = parent( i );
        while ( i > 0 && m_vector[ p ]->key() > item->key() ) {
            // update the index first
            m_vector[ p ]->setIndex( i );
            // then move it there
            m_vector[ i ] = m_vector[ p ];
            i = p;
            p = parent( i );
        }
        item->setIndex( i );
        m_vector[ i ] = item;
    }
 
    template<class T>
    void PriorityQueue<T>::buildHeap()
    {
        // from size() / 2 down to 1
        for ( int i = ( m_vector.size() >> 1 ) - 1; i >= 0; --i )
            heapify( i );
    }
 
} // namespace KOffice
 
#endif // priority_queue_h