Mass++ Common Libraries v2.7.5
 All Classes Namespaces Files Functions Variables Enumerations Macros
Public Member Functions | Protected Attributes | List of all members
kome::core::Heap< T > Class Template Reference

heap data management class More...

#include <Heap.h>

Public Member Functions

 Heap ()
 constructor
 
 Heap (boost::function< bool(T &, T &) > lessFun)
 constructor More...
 
virtual ~Heap ()
 destructor
 
void clear ()
 clears heap
 
unsigned size ()
 gets heap size More...
 
T at (const unsigned int index)
 gets heap element More...
 
void add (T elm)
 adds element More...
 
void remove (const unsigned int index)
 removes element More...
 

Protected Attributes

T * m_arr
 
unsigned int m_size
 
unsigned int m_arrSize
 
boost::function< bool(T &, T &) > m_less
 

Detailed Description

template<typename T>
class kome::core::Heap< T >

heap data management class

Definition at line 27 of file Heap.h.

Constructor & Destructor Documentation

template<typename T >
kome::core::Heap< T >::Heap ( boost::function< bool(T &, T &) >  lessFun)
inline

constructor

Parameters
[in]lessFuncompare function

Definition at line 45 of file Heap.h.

45  {
46  m_arr = NULL;
47  m_size = 0;
48  m_arrSize = 0;
49  m_less = lessFun;
50  }
kome::core::Heap::m_size
unsigned int m_size
Definition: Heap.h:65
NULL
#define NULL
Definition: CoreMacros.h:18
kome::core::Heap::m_less
boost::function< bool(T &, T &) > m_less
Definition: Heap.h:71
kome::core::Heap::m_arrSize
unsigned int m_arrSize
Definition: Heap.h:68

Member Function Documentation

template<typename T >
void kome::core::Heap< T >::add ( T  elm)
inline

adds element

Parameters
[in]elmelement to be added

Definition at line 115 of file Heap.h.

115  {
116  // check array
117  if( m_size + 1 >= m_arrSize ) {
118  // new array
119  m_arrSize *= 2;
120  if( m_arrSize < 10 ) {
121  m_arrSize = 10;
122  }
123  T* arr = new T[ m_arrSize ];
124 
125  // copy
126  memcpy( arr, m_arr, sizeof( T ) * m_size );
127 
128  // swap
129  if( m_arr != NULL ) {
130  delete[] m_arr;
131  }
132  m_arr = arr;
133  }
134 
135  // add
136  m_arr[ m_size ] = elm;
137  int idx = (int)m_size;
138  m_size++;
139 
140  // swap
141  while( idx > 0 ) {
142  int hlfIdx = ( idx - 1 ) / 2;
143  if( m_less( m_arr[ idx ], m_arr[ hlfIdx ] ) ) {
144  T tmp = m_arr[ idx ];
145  m_arr[ idx ] = m_arr[ hlfIdx ];
146  m_arr[ hlfIdx ] = tmp;
147  idx = hlfIdx;
148  }
149  else {
150  idx = -1;
151  }
152  }
153  }
kome::core::Heap::m_size
unsigned int m_size
Definition: Heap.h:65
NULL
#define NULL
Definition: CoreMacros.h:18
kome::core::Heap::m_less
boost::function< bool(T &, T &) > m_less
Definition: Heap.h:71
kome::core::Heap::m_arrSize
unsigned int m_arrSize
Definition: Heap.h:68
template<typename T >
T kome::core::Heap< T >::at ( const unsigned int  index)
inline

gets heap element

Parameters
[in]indexindex
Returns
heap element

Definition at line 106 of file Heap.h.

106  {
107  return m_arr[ index ];
108  }
template<typename T >
void kome::core::Heap< T >::remove ( const unsigned int  index)
inline

removes element

Parameters
[in]indexelement index

Definition at line 160 of file Heap.h.

160  {
161  // check the index
162  if( index >= m_size ) {
163  return;
164  }
165 
166  // array[ N ] -> array[ index ]
167  m_arr[ index ] = m_arr[ m_size - 1 ];
168  m_size--;
169 
170  // swap
171  int idx = index;
172  if( idx > 0 && m_less( m_arr[ idx ], m_arr[ idx / 2 ] ) ) { // parent
173  while( idx > 0 ) {
174  int hlfIdx = ( idx - 1 ) / 2;
175  if( m_less( m_arr[ idx ], m_arr[ hlfIdx ] ) ) {
176  T tmp = m_arr[ idx ];
177  m_arr[ idx ] = m_arr[ hlfIdx ];
178  m_arr[ hlfIdx ] = tmp;
179  idx = hlfIdx;
180  }
181  else {
182  idx = -1;
183  }
184  }
185  }
186  else { // children
187  while( idx < (int)m_size ) {
188  // index
189  int lIdx = idx * 2 + 1;
190  int rIdx = idx * 2 + 2;
191 
192  // check left
193  bool lswap = false;
194  if( lIdx < (int)m_size ) {
195  if( m_less( m_arr[ lIdx ], m_arr[ idx ] ) ) {
196  lswap = true;
197  }
198  }
199 
200  // check right
201  bool rswap = false;
202  if( rIdx < (int)m_size ) {
203  if( m_less( m_arr[ rIdx ], m_arr[ idx ] ) ) {
204  rswap = true;
205  }
206  }
207 
208  // compare
209  if( lswap && rswap ) {
210  if( m_less( m_arr[ rIdx ], m_arr[ lIdx ] ) ) {
211  lswap = false;
212  }
213  else {
214  rswap = false;
215  }
216  }
217 
218  // swap
219  int swapIdx = (int)m_size;
220  if( lswap ) {
221  swapIdx = lIdx;
222  }
223  else if( rswap ) {
224  swapIdx = rIdx;
225  }
226 
227  if( swapIdx < (int)m_size ) {
228  T tmp = m_arr[ idx ];
229  m_arr[ idx ] = m_arr[ swapIdx ];
230  m_arr[ swapIdx ] = tmp;
231  }
232  idx = swapIdx;
233  }
234  }
235  }
kome::core::Heap::m_size
unsigned int m_size
Definition: Heap.h:65
kome::core::Heap::m_less
boost::function< bool(T &, T &) > m_less
Definition: Heap.h:71
template<typename T >
unsigned kome::core::Heap< T >::size ( )
inline

gets heap size

Returns
heap size

Definition at line 96 of file Heap.h.

96  {
97  return m_size;
98  }
kome::core::Heap::m_size
unsigned int m_size
Definition: Heap.h:65

Member Data Documentation

template<typename T >
T* kome::core::Heap< T >::m_arr
protected

array

Definition at line 62 of file Heap.h.

template<typename T >
unsigned int kome::core::Heap< T >::m_arrSize
protected

array size

Definition at line 68 of file Heap.h.

template<typename T >
boost::function< bool( T&, T& ) > kome::core::Heap< T >::m_less
protected

compare function

Definition at line 71 of file Heap.h.

template<typename T >
unsigned int kome::core::Heap< T >::m_size
protected

heap size

Definition at line 65 of file Heap.h.

The documentation for this class was generated from the following file:
Generated on Sun Mar 18 2018 12:32:09 for Mass++ Common Libraries v2.7.5 by   doxygen 1.8.6