Loading...
Searching...
No Matches
PriorityQueue_Heap.h
Go to the documentation of this file.
// -*- c++ -*-
//------------------------------------------------------------------------------
// PriorityQueue_Heap.h
//------------------------------------------------------------------------------
// Copyright (c) 1999 by Vladislav Grinchenko
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Library General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//------------------------------------------------------------------------------
#ifndef PRIORITY_QUEUE_HEAP_H
#define PRIORITY_QUEUE_HEAP_H
#include <sys/types.h>
#include <string.h>
#include "assa/PriorityQueue_Impl.h"
namespace ASSA {
template< class T, class Compare >
class PriorityQueue_Heap : public PriorityQueue_Impl< T, Compare >
{
public:
PriorityQueue_Heap (size_t max_ = 0);
PriorityQueue_Heap (size_t, const Compare&);
PriorityQueue_Heap (const PriorityQueue_Heap&);
~PriorityQueue_Heap ();
PriorityQueue_Heap& operator= (const PriorityQueue_Heap&);
void insert (const T&);
T pop ();
const T& top () const;
bool remove (T);
size_t size ();
T& operator[] (int idx);
protected:
void upheap (size_t);
void downheap (size_t);
bool resize (size_t);
Compare m_comp;
private:
void allocate (size_t);
T* m_queue;
size_t m_size;
size_t m_curr;
size_t m_lwm;
};
template< class T, class Compare>
inline
PriorityQueue_Heap<T, Compare>::
PriorityQueue_Heap (size_t maxsz_)
: m_curr (1), m_lwm (20)
{
trace("PriorityQueue_Heap::PriorityQueue_Heap");
allocate (maxsz_);
}
template< class T, class Compare>
inline
PriorityQueue_Heap<T, Compare>::
PriorityQueue_Heap (size_t maxsz_, const Compare& x_)
: m_comp (x_), m_curr (1), m_lwm (20)
{
allocate (maxsz_);
}
template< class T, class Compare>
inline void
PriorityQueue_Heap<T, Compare>::
allocate (size_t s_)
{
m_size = s_ > m_lwm ? s_ : m_lwm;
m_queue = new T [m_size];
}
template< class T, class Compare>
inline
PriorityQueue_Heap<T, Compare>::
PriorityQueue_Heap (const PriorityQueue_Heap& h_)
: m_comp (h_.m_comp), m_size (h_.m_size), m_curr (h_.m_curr),
m_lwm (h_.m_lwm)
{
allocate (m_size);
::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
}
template< class T, class Compare>
PriorityQueue_Heap<T, Compare>&
PriorityQueue_Heap<T, Compare>::
operator= (const PriorityQueue_Heap& h_)
{
delete [] m_queue;
m_comp = h_.m_comp;
m_size = h_.m_size;
m_curr = h_.m_curr;
m_lwm = h_.m_lwm;
allocate (m_size);
::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
return *this;
}
template< class T, class Compare>
inline
PriorityQueue_Heap<T, Compare>::
~PriorityQueue_Heap ()
{
delete [] m_queue;
}
template< class T, class Compare>
void
PriorityQueue_Heap<T, Compare>::
insert (const T& t_)
{
if (m_curr+1 == m_size) // if array filled up
resize (m_size*2); // then resize array
m_queue [m_curr] = t_;
upheap (m_curr);
m_curr++;
}
template< class T, class Compare>
void
PriorityQueue_Heap<T, Compare>::
upheap (size_t k_)
{
T v = m_queue[k_];
m_queue[0] = 0;
while ( k_/2 != 0 && m_comp (v, m_queue[k_/2]) ) {
m_queue[k_] = m_queue[k_/2];
k_ = k_/2;
}
m_queue[k_] = v;
}
template< class T, class Compare>
T
PriorityQueue_Heap<T, Compare>::
pop ()
{
T v = m_queue[1];
m_queue[1] = m_queue[--m_curr];
downheap (1);
if (m_curr*3 <= m_size && m_curr*2 > m_lwm) {
resize (m_curr*2);
}
return v;
}
template< class T, class Compare>
inline const T&
PriorityQueue_Heap<T, Compare>::
top () const
{
return (const T&) m_queue[1];
}
template< class T, class Compare>
void
PriorityQueue_Heap<T, Compare>::
downheap (size_t k_)
{
register size_t j;
T v = m_queue[k_];
while (k_ <= m_curr/2) {
j = 2*k_;
if (j < m_curr && m_comp (m_queue[j+1], m_queue[j]))
j++;
if (m_comp (v, m_queue[j]))
break;
m_queue[k_] = m_queue[j];
k_ = j;
}
m_queue[k_] = v;
}
template< class T, class Compare>
bool
PriorityQueue_Heap<T, Compare>::
remove (T t_)
{
register size_t i;
for (i=1; i < m_curr; i++)
if (m_queue[i] == t_)
break;
if (i == m_curr) // not found
return false;
m_curr--;
if (i == m_curr) // last element in queue
return true;
m_queue[i] = m_queue[m_curr];
downheap (i);
return true;
}
template< class T, class Compare>
inline size_t
PriorityQueue_Heap<T, Compare>::
size ()
{
return m_curr-1;
}
template< class T, class Compare>
bool
PriorityQueue_Heap<T, Compare>::
resize (size_t newsz_)
{
if (m_size == newsz_)
return true;
T* new_chunk = new T[newsz_];
::memcpy (new_chunk, m_queue, m_curr * sizeof(T));
delete [] m_queue;
m_queue = new_chunk;
m_size = newsz_;
return true;
}
template< class T, class Compare>
T&
PriorityQueue_Heap<T, Compare>::
operator[] (int idx)
{
return m_queue[idx+1];
}
} // end namespace ASSA
#endif /* PRIORITY_QUEUE_HEAP_H */
trace
#define trace(s)
trace() is used to trace function call chain in C++ program.
Definition Logger.h:429
PriorityQueue_Impl.h
Interface class that defines Implementor of the Bridge pattern.
ASSA::AutoPtrRef
A wrapper class to provide AutoPtr with reference semantics.
Definition AutoPtr.h:32
ASSA::PriorityQueue_Heap
Definition PriorityQueue_Heap.h:30
ASSA::PriorityQueue_Heap::resize
bool resize(size_t)
Definition PriorityQueue_Heap.h:230
ASSA::PriorityQueue_Heap::operator=
PriorityQueue_Heap & operator=(const PriorityQueue_Heap &)
Definition PriorityQueue_Heap.h:104
ASSA::PriorityQueue_Heap::m_queue
T * m_queue
Definition PriorityQueue_Heap.h:56
ASSA::PriorityQueue_Heap::m_curr
size_t m_curr
Array's size.
Definition PriorityQueue_Heap.h:58
ASSA::PriorityQueue_Heap::downheap
void downheap(size_t)
Definition PriorityQueue_Heap.h:178
ASSA::PriorityQueue_Heap::m_size
size_t m_size
Array of queued pointers.
Definition PriorityQueue_Heap.h:57
ASSA::PriorityQueue_Heap::insert
void insert(const T &)
Definition PriorityQueue_Heap.h:127
ASSA::PriorityQueue_Heap::top
const T & top() const
Definition PriorityQueue_Heap.h:170
ASSA::PriorityQueue_Heap::upheap
void upheap(size_t)
Definition PriorityQueue_Heap.h:140
ASSA::PriorityQueue_Heap::remove
bool remove(T)
Definition PriorityQueue_Heap.h:198
ASSA::PriorityQueue_Heap::pop
T pop()
Definition PriorityQueue_Heap.h:155
ASSA::PriorityQueue_Heap::~PriorityQueue_Heap
~PriorityQueue_Heap()
Definition PriorityQueue_Heap.h:119
ASSA::PriorityQueue_Heap::allocate
void allocate(size_t)
Definition PriorityQueue_Heap.h:84
ASSA::PriorityQueue_Heap::size
size_t size()
Definition PriorityQueue_Heap.h:222
ASSA::PriorityQueue_Heap::m_lwm
size_t m_lwm
Next free slot in array.
Definition PriorityQueue_Heap.h:59
ASSA::PriorityQueue_Heap::PriorityQueue_Heap
PriorityQueue_Heap(size_t max_=0)
Definition PriorityQueue_Heap.h:65
ASSA::PriorityQueue_Heap::operator[]
T & operator[](int idx)
Definition PriorityQueue_Heap.h:246
ASSA::PriorityQueue_Heap::m_comp
Compare m_comp
Definition PriorityQueue_Heap.h:51
ASSA::PriorityQueue_Impl
Class PriorityQueue_Impl.
Definition PriorityQueue_Impl.h:54
ASSA
Definition Acceptor.h:40