From 8362bf63dea22bbf6736609b0f49c152f975eb63 Mon Sep 17 00:00:00 2001 From: tpearson Date: Wed, 20 Jan 2010 01:29:50 +0000 Subject: Added old abandoned KDE3 version of koffice git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/applications/koffice@1077364 283d02a7-25f6-0310-bc7c-ecb5cbfe19da --- lib/kofficecore/priorityqueue.h | 216 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 216 insertions(+) create mode 100644 lib/kofficecore/priorityqueue.h (limited to 'lib/kofficecore/priorityqueue.h') diff --git a/lib/kofficecore/priorityqueue.h b/lib/kofficecore/priorityqueue.h new file mode 100644 index 00000000..68019143 --- /dev/null +++ b/lib/kofficecore/priorityqueue.h @@ -0,0 +1,216 @@ +/* This file is part of the KOffice libraries + Copyright (C) 2001 Werner Trobin + + 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 +#include +#include +#include + +// Better put all those internal classes in some namespace to avoid clashes +// as the names are quite generic +namespace KOffice { + + /** + * This PriorityQueue class is implemented as "upside down" heap, i.e. the item + * with the \b smallest key is at the root of the heap. + * If you feel like using that class your template parameter has to have a public + * method "unsigned int key() const" which returns - surprise - the key. The + * supplied key must not be "negative." We use UINT_MAX as value to represent + * "infinity" for the shortest path algorithm. + * As this is a very specialized class we also demand a "void setIndex(int i)" + * method in order to tell nodes where they are located inside the heap. This is + * a very ugly approach, but it's the only way I see if you want to avoid a O(n) + * search for the item where you decreased the key :} + * Just to make it even worse we also use a "int index() const" method + * to fetch the index... well, you most likely would need one anyway ;) + * Note: This class is pointer based (like QPtr*) - if you create PriorityQueue + * we actually operate on X* ! We don't care about deleting your pointers at all. + * We don't copy them, we don't create new ones,... - you own them, you have + * to delete them :) + * + * In case you change a key value make sure to call keyDecreased and pass the + * item you touched. This is running in O(log n) according to Cormen... + * + * All the ideas are stol^H^H^H^Hborrowed from "Introduction to Algorithms", + * Cormen et al + * + * @author Werner Trobin + */ + template class PriorityQueue { + + public: + PriorityQueue() {} + PriorityQueue( const PriorityQueue& rhs ) : m_vector( rhs.m_vector ) {} + PriorityQueue( const QAsciiDict& items ); + ~PriorityQueue() {} + + PriorityQueue &operator=( const PriorityQueue& rhs ) { m_vector = rhs.m_vector; return *this; } + bool operator==( const PriorityQueue& 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 ); + + /** + * Call this method after decreasing the key of the ith item. The heap + * properties will no longer be valid if you either forget to call that + * method, or if you \b increase the key. + */ + void keyDecreased( T* item ); + + T* extractMinimum(); + + /** + * For debugging + */ + 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 m_vector; + }; + + template + PriorityQueue::PriorityQueue( const QAsciiDict& items ) : m_vector( items.count() ) + { + // First put all items into the vector + QAsciiDictIterator 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 + void PriorityQueue::insert( T* item ) + { + if ( !item ) + return; + int i = static_cast( m_vector.size() ); + m_vector.push_back( 0 ); // extend the vector by one item. i == index to the last item + bubbleUp( item, i ); + } + + template + void PriorityQueue::keyDecreased( T* item ) + { + if ( !item ) + return; + bubbleUp( item, item->index() ); + } + + template + T* PriorityQueue::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 + void PriorityQueue::dump() const + { + kdDebug( 30500 ) << "++++++++++ PriorityQueue::dump ++++++++++" << endl; + QString out; + int size = static_cast( m_vector.size() ); + for ( int i = 0; i < size; ++i ) { + if ( m_vector[ i ]->index() != i ) + out += " ERROR: index out of sync. Should be " + QString::number( i ) + ", is " + + QString::number( m_vector[ i ]->index() ) + ". "; + out += QString::number( m_vector[ i ]->key() ); + out += ", "; + } + if ( out.isEmpty() ) + out = "(empty)"; + kdDebug( 30500 ) << out << endl; + kdDebug( 30500 ) << "++++++++++ PriorityQueue::dump (done) ++++++++++" << endl; + } + + template + void PriorityQueue::heapify( int i ) + { + int l = left( i ), r = right( i ), size = static_cast( 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 + void PriorityQueue::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 + void PriorityQueue::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 -- cgit v1.2.1