PriorityQueue.h

00001 //
00002 // Copyright(C) 2005--2006 Institute of Computing Tech, Chinese Academy of Sciences. 
00003 // All rights reserved.
00004 // This file is part of FirteX (www.firtex.org)
00005 //
00006 // Use of the FirteX is subject to the terms of the software license set forth in 
00007 // the LICENSE file included with this software, and also available at
00008 // http://www.firtex.org/license.html
00009 //
00010 // Author       : 郭瑞杰(GuoRuijie)
00011 // Email        : ruijieguo@software.ict.ac.cn,ruijieguo@gmail.com
00012 // Created      : 2006/5/20
00013 //
00014 #ifndef _PRIORITYQUEUE_H
00015 #define _PRIORITYQUEUE_H
00016 
00017 #if _MSC_VER > 1000
00018 #pragma once
00019 #endif // _MSC_VER > 1000
00020 
00021 
00022 #include "StdHeader.h"
00023 
00024 namespace firtex
00025 {
00026         namespace utility
00027         {
00033                 template <class _type> 
00034                 class CPriorityQueue
00035                 {
00036 
00037                 private:
00038                         _type*  m_heap; 
00039                         size_t  m_size;
00040                         bool    m_bDelete;
00041                         size_t  m_maxSize;
00042 
00043                         void upHeap()
00044                         {
00045                                 size_t i = m_size;
00046                                 _type node = m_heap[i];                   // save bottom node (WAS object)
00047                                 int32_t j = ((uint32_t)i) >> 1;
00048                                 while (j > 0 && lessThan(node,m_heap[j]))
00049                                 {
00050                                         m_heap[i] = m_heap[j];                    // shift parents down
00051                                         i = j;
00052                                         j = ((uint32_t)j) >> 1;
00053                                 }
00054                                 m_heap[i] = node;                                 // install saved node
00055                         }
00056                         void downHeap()
00057                         {
00058                                 size_t i = 1;
00059                                 _type node = m_heap[i];                   // save top node
00060                                 size_t j = i << 1;                                // find smaller child
00061                                 size_t k = j + 1;
00062                                 if (k <= m_size && lessThan(m_heap[k], m_heap[j])) 
00063                                 {
00064                                         j = k;
00065                                 }
00066                                 while (j <= m_size && lessThan(m_heap[j],node)) 
00067                                 {
00068                                         m_heap[i] = m_heap[j];                    // shift up child
00069                                         i = j;
00070                                         j = i << 1;
00071                                         k = j + 1;
00072                                         if (k <= m_size && lessThan(m_heap[k], m_heap[j]))
00073                                         {
00074                                                 j = k;
00075                                         }
00076                                 }
00077                                 m_heap[i] = node;                                 // install saved node
00078                         }
00079 
00080                 protected:
00081                         CPriorityQueue()
00082                         {
00083                                 m_size = 0;
00084                                 m_bDelete = false;
00085                                 m_heap = NULL;
00086                                 m_maxSize = 0;
00087                         }
00088 
00093                         virtual bool lessThan(_type a, _type b)=0;
00094 
00098                         void initialize(const size_t maxSize, bool deleteOnClear)
00099                         {
00100                                 m_size = 0;
00101                                 m_bDelete = deleteOnClear;
00102                                 m_maxSize = maxSize;
00103                                 size_t heapSize = m_maxSize + 1;
00104                                 m_heap = new _type[heapSize];                           
00105                         }
00106 
00107                 public:
00108                         virtual ~CPriorityQueue()
00109                         {
00110                                 clear();
00111                                 delete[] m_heap;
00112                         }
00113 
00119                         void put(_type element)
00120                         {
00121                                 if(m_size >= m_maxSize)
00122                                         FIRTEX_THROW2(GENERIC_ERROR,"add is out of bounds");                    
00123 
00124                                 m_size++;       
00125                                 m_heap[m_size] = element;               
00126                                 upHeap();
00127                         }
00128 
00135                         bool insert(_type element)
00136                         {
00137                                 if(m_size < m_maxSize)
00138                                 {
00139                                         put(element);
00140                                         return true;
00141                                 }
00142                                 else if(m_size > 0 && !lessThan(element, top()))
00143                                 {
00144                                         if ( m_bDelete )
00145                                         {
00146                                                 delete m_heap[1];
00147                                         }
00148                                         m_heap[1] = element;
00149                                         adjustTop();
00150                                         return true;
00151                                 }
00152                                 else
00153                                         return false;
00154                         }
00155 
00159                         _type top()
00160                         {
00161                                 if (m_size > 0)
00162                                         return m_heap[1];
00163                                 else
00164                                         return NULL;
00165                         }
00166 
00170                         _type pop()
00171                         {
00172                                 if (m_size > 0) 
00173                                 {
00174                                         _type result = m_heap[1];                         // save first value
00175                                         m_heap[1] = m_heap[m_size];                       // move last to first
00176 
00177                                         m_heap[m_size] = (_type)0;                        // permit GC of objects
00178                                         m_size--;
00179                                         downHeap();                               // adjust m_heap
00180                                         return result;
00181                                 }
00182                                 else
00183                                         return (_type)NULL;
00184                         }
00185 
00194                         void adjustTop()
00195                         {
00196                                 downHeap();
00197                         }
00198 
00199 
00203                         size_t size()
00204                         {
00205                                 return m_size;
00206                         }
00207 
00211                         void clear()
00212                         {
00213                                 for (size_t i = 1; i <= m_size; i++)
00214                                 {
00215                                         if ( m_bDelete ){
00216                                                 delete m_heap[i];
00217                                         }
00218                                 }
00219                                 m_size = 0;
00220                         }
00221                 };
00222         }
00223 }
00224 
00225 #endif