aboutsummaryrefslogtreecommitdiff
path: root/src/stable/heap.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/stable/heap.h1180
1 files changed, 590 insertions, 590 deletions
diff --git a/src/stable/heap.h b/src/stable/heap.h
index a813f92..5033618 100644
--- a/src/stable/heap.h
+++ b/src/stable/heap.h
@@ -17,596 +17,596 @@
17 17
18namespace Bu 18namespace Bu
19{ 19{
20 subExceptionDecl( HeapException ); 20 subExceptionDecl( HeapException );
21 21
22 template<typename item, typename cmpfunc, typename itemalloc> 22 template<typename item, typename cmpfunc, typename itemalloc>
23 class Heap; 23 class Heap;
24 24
25 /** @cond DEVEL */ 25 /** @cond DEVEL */
26 template<typename item, typename cmpfunc, typename itemalloc> 26 template<typename item, typename cmpfunc, typename itemalloc>
27 class HeapCore 27 class HeapCore
28 { 28 {
29 friend class Heap<item, cmpfunc, itemalloc>; 29 friend class Heap<item, cmpfunc, itemalloc>;
30 friend class SharedCore< 30 friend class SharedCore<
31 Heap<item, cmpfunc, itemalloc>, HeapCore<item, cmpfunc, itemalloc> 31 Heap<item, cmpfunc, itemalloc>, HeapCore<item, cmpfunc, itemalloc>
32 >; 32 >;
33 private: 33 private:
34 HeapCore() : 34 HeapCore() :
35 iSize( 0 ), 35 iSize( 0 ),
36 iFill( 0 ), 36 iFill( 0 ),
37 aItem( NULL ) 37 aItem( NULL )
38 { 38 {
39 } 39 }
40 40
41 virtual ~HeapCore() 41 virtual ~HeapCore()
42 { 42 {
43 clear(); 43 clear();
44 } 44 }
45 45
46 void init() 46 void init()
47 { 47 {
48 if( iSize > 0 ) 48 if( iSize > 0 )
49 return; 49 return;
50 50
51 iSize = 7; 51 iSize = 7;
52 iFill = 0; 52 iFill = 0;
53 aItem = ia.allocate( iSize ); 53 aItem = ia.allocate( iSize );
54 } 54 }
55 55
56 void init( int iCap ) 56 void init( int iCap )
57 { 57 {
58 if( iSize > 0 ) 58 if( iSize > 0 )
59 return; 59 return;
60 60
61 for( iSize = 1; iSize < iCap; iSize=iSize*2+1 ) { } 61 for( iSize = 1; iSize < iCap; iSize=iSize*2+1 ) { }
62 iFill = 0; 62 iFill = 0;
63 aItem = ia.allocate( iSize ); 63 aItem = ia.allocate( iSize );
64 } 64 }
65 65
66 void clear() 66 void clear()
67 { 67 {
68 if( iSize == 0 ) 68 if( iSize == 0 )
69 return; 69 return;
70 70
71 for( int j = 0; j < iFill; j++ ) 71 for( int j = 0; j < iFill; j++ )
72 ia.destroy( &aItem[j] ); 72 ia.destroy( &aItem[j] );
73 ia.deallocate( aItem, iSize ); 73 ia.deallocate( aItem, iSize );
74 aItem = NULL; 74 aItem = NULL;
75 iSize = 0; 75 iSize = 0;
76 iFill = 0; 76 iFill = 0;
77 } 77 }
78 78
79 void upSize() 79 void upSize()
80 { 80 {
81 if( iSize == 0 ) 81 if( iSize == 0 )
82 { 82 {
83 init(); 83 init();
84 return; 84 return;
85 } 85 }
86 86
87 item *aNewItems = ia.allocate( iSize*2+1 ); 87 item *aNewItems = ia.allocate( iSize*2+1 );
88 // 88 //
89 // We cannot use a memcopy here because we don't know what kind 89 // We cannot use a memcopy here because we don't know what kind
90 // of datastructures are being used, we have to copy them one at 90 // of datastructures are being used, we have to copy them one at
91 // a time. 91 // a time.
92 // 92 //
93 for( int j = 0; j < iFill; j++ ) 93 for( int j = 0; j < iFill; j++ )
94 { 94 {
95 ia.construct( &aNewItems[j], aItem[j] ); 95 ia.construct( &aNewItems[j], aItem[j] );
96 ia.destroy( &aItem[j] ); 96 ia.destroy( &aItem[j] );
97 } 97 }
98 ia.deallocate( aItem, iSize ); 98 ia.deallocate( aItem, iSize );
99 aItem = aNewItems; 99 aItem = aNewItems;
100 iSize = iSize*2+1; 100 iSize = iSize*2+1;
101 } 101 }
102 102
103 virtual void enqueue( const item &it ) 103 virtual void enqueue( const item &it )
104 { 104 {
105 item i = it; // TODO: This is a silly workaround, put the i item 105 item i = it; // TODO: This is a silly workaround, put the i item
106 // at the end. 106 // at the end.
107 if( iFill+1 >= iSize ) 107 if( iFill+1 >= iSize )
108 upSize(); 108 upSize();
109 109
110 for( int j = 0; j < iFill; ) 110 for( int j = 0; j < iFill; )
111 { 111 {
112 if( cmp( i, aItem[j] ) ) 112 if( cmp( i, aItem[j] ) )
113 { 113 {
114 Bu::swap( i, aItem[j] ); 114 Bu::swap( i, aItem[j] );
115 } 115 }
116 116
117 if( j*2+1 >= iFill ) 117 if( j*2+1 >= iFill )
118 break; 118 break;
119 if( cmp( i, aItem[j*2+1] ) ) 119 if( cmp( i, aItem[j*2+1] ) )
120 { 120 {
121 j = j*2+1; 121 j = j*2+1;
122 } 122 }
123 else 123 else
124 { 124 {
125 j = j*2+2; 125 j = j*2+2;
126 } 126 }
127 } 127 }
128 ia.construct( &aItem[iFill], i ); 128 ia.construct( &aItem[iFill], i );
129 if( iFill > 0 ) 129 if( iFill > 0 )
130 { 130 {
131 for( int j = iFill; j >= 0; ) 131 for( int j = iFill; j >= 0; )
132 { 132 {
133 int k = (j-1)/2; 133 int k = (j-1)/2;
134 if( j == k ) 134 if( j == k )
135 break; 135 break;
136 if( cmp( aItem[k], aItem[j] ) ) 136 if( cmp( aItem[k], aItem[j] ) )
137 break; 137 break;
138 138
139 Bu::swap( aItem[k], aItem[j] ); 139 Bu::swap( aItem[k], aItem[j] );
140 j = k; 140 j = k;
141 } 141 }
142 } 142 }
143 iFill++; 143 iFill++;
144 } 144 }
145 145
146 virtual item dequeue() 146 virtual item dequeue()
147 { 147 {
148 if( iFill == 0 ) 148 if( iFill == 0 )
149 throw HeapException("Heap empty."); 149 throw HeapException("Heap empty.");
150 item iRet = aItem[0]; 150 item iRet = aItem[0];
151 int j; 151 int j;
152 for( j = 0; j < iFill; ) 152 for( j = 0; j < iFill; )
153 { 153 {
154 int k = j*2+1; 154 int k = j*2+1;
155 if( k+1 < iFill && cmp( aItem[k+1], aItem[k] ) ) 155 if( k+1 < iFill && cmp( aItem[k+1], aItem[k] ) )
156 { 156 {
157 if( k+1 < iFill-1 && cmp( aItem[iFill-1], aItem[k+1] ) ) 157 if( k+1 < iFill-1 && cmp( aItem[iFill-1], aItem[k+1] ) )
158 break; 158 break;
159 aItem[j] = aItem[k+1]; 159 aItem[j] = aItem[k+1];
160 j = k+1; 160 j = k+1;
161 } 161 }
162 else if( k < iFill ) 162 else if( k < iFill )
163 { 163 {
164 if( k < iFill-1 && cmp( aItem[iFill-1], aItem[k] ) ) 164 if( k < iFill-1 && cmp( aItem[iFill-1], aItem[k] ) )
165 break; 165 break;
166 aItem[j] = aItem[k]; 166 aItem[j] = aItem[k];
167 j = k; 167 j = k;
168 } 168 }
169 else 169 else
170 break; 170 break;
171 } 171 }
172 if( j < iFill-1 ) 172 if( j < iFill-1 )
173 aItem[j] = aItem[iFill-1]; 173 aItem[j] = aItem[iFill-1];
174 ia.destroy( &aItem[iFill-1] ); 174 ia.destroy( &aItem[iFill-1] );
175 iFill--; 175 iFill--;
176 176
177 return iRet; 177 return iRet;
178 } 178 }
179 179
180 private: 180 private:
181 int iSize; 181 int iSize;
182 int iFill; 182 int iFill;
183 item *aItem; 183 item *aItem;
184 cmpfunc cmp; 184 cmpfunc cmp;
185 itemalloc ia; 185 itemalloc ia;
186 }; 186 };
187 /** @endcond */ 187 /** @endcond */
188 188
189 /** 189 /**
190 * A priority queue that allows for an unlimited number of priorities. All 190 * A priority queue that allows for an unlimited number of priorities. All
191 * objects enqueued must support less-than-comparison. Then every time an 191 * objects enqueued must support less-than-comparison. Then every time an
192 * item is dequeued it is always the least item in the heap. The heap 192 * item is dequeued it is always the least item in the heap. The heap
193 * operates using a binary tree for storage, which allows most operations 193 * operates using a binary tree for storage, which allows most operations
194 * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins 194 * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins
195 * whereas peeking is constant time. 195 * whereas peeking is constant time.
196 * 196 *
197 * This heap implementation allows iterating, however please note that any 197 * This heap implementation allows iterating, however please note that any
198 * enqueue or dequeue operation will invalidate the iterator and make it 198 * enqueue or dequeue operation will invalidate the iterator and make it
199 * unusable (if it still works, you shouldn't trust the results). Also, 199 * unusable (if it still works, you shouldn't trust the results). Also,
200 * the items are not stored in memory in order, they are optomized into a 200 * the items are not stored in memory in order, they are optomized into a
201 * tree. This means that the items will be in effectively random order 201 * tree. This means that the items will be in effectively random order
202 * while iterating through them, and the order cannot be trusted. Also, 202 * while iterating through them, and the order cannot be trusted. Also,
203 * modifying an item in the heap will not cause that item to be re-sorted. 203 * modifying an item in the heap will not cause that item to be re-sorted.
204 * If you want to change the position of an item in the heap you will have 204 * If you want to change the position of an item in the heap you will have
205 * to dequeue every item before it, dequeue that item, change it, and 205 * to dequeue every item before it, dequeue that item, change it, and
206 * re-enqueue all of the items removed. 206 * re-enqueue all of the items removed.
207 */ 207 */
208 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> > 208 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
209 class Heap : public Queue<item>, public SharedCore< 209 class Heap : public Queue<item>, public SharedCore<
210 Heap<item, cmpfunc, itemalloc>, 210 Heap<item, cmpfunc, itemalloc>,
211 HeapCore<item, cmpfunc, itemalloc> 211 HeapCore<item, cmpfunc, itemalloc>
212 > 212 >
213 { 213 {
214 private: 214 private:
215 typedef class Heap<item,cmpfunc,itemalloc> MyType; 215 typedef class Heap<item,cmpfunc,itemalloc> MyType;
216 typedef class HeapCore<item,cmpfunc,itemalloc> Core; 216 typedef class HeapCore<item,cmpfunc,itemalloc> Core;
217 217
218 protected: 218 protected:
219 using SharedCore<MyType, Core>::core; 219 using SharedCore<MyType, Core>::core;
220 using SharedCore<MyType, Core>::_hardCopy; 220 using SharedCore<MyType, Core>::_hardCopy;
221 using SharedCore<MyType, Core>::_resetCore; 221 using SharedCore<MyType, Core>::_resetCore;
222 using SharedCore<MyType, Core>::_allocateCore; 222 using SharedCore<MyType, Core>::_allocateCore;
223 223
224 public: 224 public:
225 Heap() 225 Heap()
226 { 226 {
227 } 227 }
228 228
229 Heap( cmpfunc cmpin ) 229 Heap( cmpfunc cmpin )
230 { 230 {
231 core->cmp = cmpin; 231 core->cmp = cmpin;
232 } 232 }
233 233
234 Heap( int iInitialCapacity ) 234 Heap( int iInitialCapacity )
235 { 235 {
236 core->init( iInitialCapacity ); 236 core->init( iInitialCapacity );
237 } 237 }
238 238
239 Heap( cmpfunc cmpin, int iInitialCapacity ) 239 Heap( cmpfunc cmpin, int iInitialCapacity )
240 { 240 {
241 core->cmp = cmpin; 241 core->cmp = cmpin;
242 core->init( iInitialCapacity ); 242 core->init( iInitialCapacity );
243 } 243 }
244 244
245 Heap( const MyType &rSrc ) : 245 Heap( const MyType &rSrc ) :
246 SharedCore<MyType, Core>( rSrc ) 246 SharedCore<MyType, Core>( rSrc )
247 { 247 {
248 } 248 }
249 249
250 virtual ~Heap() 250 virtual ~Heap()
251 { 251 {
252 } 252 }
253 253
254 virtual void enqueue( const item &it ) 254 virtual void enqueue( const item &it )
255 { 255 {
256 _hardCopy(); 256 _hardCopy();
257 257
258 core->enqueue( it ); 258 core->enqueue( it );
259 } 259 }
260 260
261 virtual item &peek() 261 virtual item &peek()
262 { 262 {
263 _hardCopy(); 263 _hardCopy();
264 264
265 if( core->iFill == 0 ) 265 if( core->iFill == 0 )
266 throw HeapException("Heap empty."); 266 throw HeapException("Heap empty.");
267 return core->aItem[0]; 267 return core->aItem[0];
268 } 268 }
269 269
270 virtual const item &peek() const 270 virtual const item &peek() const
271 { 271 {
272 if( core->iFill == 0 ) 272 if( core->iFill == 0 )
273 throw HeapException("Heap empty."); 273 throw HeapException("Heap empty.");
274 return core->aItem[0]; 274 return core->aItem[0];
275 } 275 }
276 276
277 virtual item dequeue() 277 virtual item dequeue()
278 { 278 {
279 _hardCopy(); 279 _hardCopy();
280 280
281 return core->dequeue(); 281 return core->dequeue();
282 } 282 }
283 283
284 virtual bool isEmpty() const 284 virtual bool isEmpty() const
285 { 285 {
286 return (core->iFill==0); 286 return (core->iFill==0);
287 } 287 }
288 288
289 virtual int getSize() const 289 virtual int getSize() const
290 { 290 {
291 return core->iFill; 291 return core->iFill;
292 } 292 }
293 293
294 class iterator 294 class iterator
295 { 295 {
296 friend class const_iterator; 296 friend class const_iterator;
297 friend class Heap<item, cmpfunc, itemalloc>; 297 friend class Heap<item, cmpfunc, itemalloc>;
298 private: 298 private:
299 Heap<item, cmpfunc, itemalloc> *pHeap; 299 Heap<item, cmpfunc, itemalloc> *pHeap;
300 int iIndex; 300 int iIndex;
301 301
302 iterator( Heap<item, cmpfunc, itemalloc> *pHeap, int iIndex ) : 302 iterator( Heap<item, cmpfunc, itemalloc> *pHeap, int iIndex ) :
303 pHeap( pHeap ), iIndex( iIndex ) 303 pHeap( pHeap ), iIndex( iIndex )
304 { 304 {
305 } 305 }
306 306
307 void checkValid() 307 void checkValid()
308 { 308 {
309 if( pHeap == NULL ) 309 if( pHeap == NULL )
310 throw Bu::ExceptionBase("Iterator not initialized."); 310 throw Bu::ExceptionBase("Iterator not initialized.");
311 if( iIndex < 0 || iIndex >= pHeap->core->iFill ) 311 if( iIndex < 0 || iIndex >= pHeap->core->iFill )
312 throw Bu::ExceptionBase("Iterator out of bounds."); 312 throw Bu::ExceptionBase("Iterator out of bounds.");
313 } 313 }
314 314
315 public: 315 public:
316 iterator() : 316 iterator() :
317 pHeap( NULL ), 317 pHeap( NULL ),
318 iIndex( -1 ) 318 iIndex( -1 )
319 { 319 {
320 } 320 }
321 321
322 iterator( const iterator &i ) : 322 iterator( const iterator &i ) :
323 pHeap( i.pHeap ), 323 pHeap( i.pHeap ),
324 iIndex( i.iIndex ) 324 iIndex( i.iIndex )
325 { 325 {
326 } 326 }
327 327
328 bool operator==( const iterator &oth ) const 328 bool operator==( const iterator &oth ) const
329 { 329 {
330 return (oth.pHeap == pHeap) && (oth.iIndex == iIndex); 330 return (oth.pHeap == pHeap) && (oth.iIndex == iIndex);
331 } 331 }
332 332
333 bool operator!=( const iterator &oth ) const 333 bool operator!=( const iterator &oth ) const
334 { 334 {
335 return (oth.pHeap != pHeap) || (oth.iIndex != iIndex); 335 return (oth.pHeap != pHeap) || (oth.iIndex != iIndex);
336 } 336 }
337 337
338 item &operator*() 338 item &operator*()
339 { 339 {
340 pHeap->_hardCopy(); 340 pHeap->_hardCopy();
341 341
342 return pHeap->core->aItem[iIndex]; 342 return pHeap->core->aItem[iIndex];
343 } 343 }
344 344
345 item *operator->() 345 item *operator->()
346 { 346 {
347 pHeap->_hardCopy(); 347 pHeap->_hardCopy();
348 348
349 return &(pHeap->core->aItem[iIndex]); 349 return &(pHeap->core->aItem[iIndex]);
350 } 350 }
351 351
352 iterator &operator++() 352 iterator &operator++()
353 { 353 {
354 checkValid(); 354 checkValid();
355 iIndex++; 355 iIndex++;
356 if( iIndex >= pHeap->iFill ) 356 if( iIndex >= pHeap->iFill )
357 iIndex = -1; 357 iIndex = -1;
358 358
359 return *this; 359 return *this;
360 } 360 }
361 361
362 iterator &operator--() 362 iterator &operator--()
363 { 363 {
364 checkValid(); 364 checkValid();
365 iIndex--; 365 iIndex--;
366 366
367 return *this; 367 return *this;
368 } 368 }
369 369
370 iterator &operator++( int ) 370 iterator &operator++( int )
371 { 371 {
372 checkValid(); 372 checkValid();
373 iIndex++; 373 iIndex++;
374 if( iIndex >= pHeap->core->iFill ) 374 if( iIndex >= pHeap->core->iFill )
375 iIndex = -1; 375 iIndex = -1;
376 376
377 return *this; 377 return *this;
378 } 378 }
379 379
380 iterator &operator--( int ) 380 iterator &operator--( int )
381 { 381 {
382 checkValid(); 382 checkValid();
383 iIndex--; 383 iIndex--;
384 384
385 return *this; 385 return *this;
386 } 386 }
387 387
388 iterator operator+( int iDelta ) 388 iterator operator+( int iDelta )
389 { 389 {
390 checkValid(); 390 checkValid();
391 iterator ret( *this ); 391 iterator ret( *this );
392 ret.iIndex += iDelta; 392 ret.iIndex += iDelta;
393 if( ret.iIndex >= pHeap->core->iFill ) 393 if( ret.iIndex >= pHeap->core->iFill )
394 ret.iIndex = -1; 394 ret.iIndex = -1;
395 return ret; 395 return ret;
396 } 396 }
397 397
398 iterator operator-( int iDelta ) 398 iterator operator-( int iDelta )
399 { 399 {
400 checkValid(); 400 checkValid();
401 iterator ret( *this ); 401 iterator ret( *this );
402 ret.iIndex -= iDelta; 402 ret.iIndex -= iDelta;
403 if( ret.iIndex < 0 ) 403 if( ret.iIndex < 0 )
404 ret.iIndex = -1; 404 ret.iIndex = -1;
405 return ret; 405 return ret;
406 } 406 }
407 407
408 operator bool() const 408 operator bool() const
409 { 409 {
410 return iIndex != -1; 410 return iIndex != -1;
411 } 411 }
412 412
413 bool isValid() const 413 bool isValid() const
414 { 414 {
415 return iIndex != -1; 415 return iIndex != -1;
416 } 416 }
417 417
418 iterator &operator=( const iterator &oth ) 418 iterator &operator=( const iterator &oth )
419 { 419 {
420 pHeap = oth.pHeap; 420 pHeap = oth.pHeap;
421 iIndex = oth.iIndex; 421 iIndex = oth.iIndex;
422 } 422 }
423 }; 423 };
424 424
425 class const_iterator 425 class const_iterator
426 { 426 {
427 friend class Heap<item, cmpfunc, itemalloc>; 427 friend class Heap<item, cmpfunc, itemalloc>;
428 private: 428 private:
429 Heap<item, cmpfunc, itemalloc> *pHeap; 429 Heap<item, cmpfunc, itemalloc> *pHeap;
430 int iIndex; 430 int iIndex;
431 431
432 const_iterator( Heap<item, cmpfunc, itemalloc> *pHeap, 432 const_iterator( Heap<item, cmpfunc, itemalloc> *pHeap,
433 int iIndex ) : 433 int iIndex ) :
434 pHeap( pHeap ), iIndex( iIndex ) 434 pHeap( pHeap ), iIndex( iIndex )
435 { 435 {
436 } 436 }
437 437
438 void checkValid() 438 void checkValid()
439 { 439 {
440 if( pHeap == NULL ) 440 if( pHeap == NULL )
441 throw Bu::ExceptionBase("Iterator not initialized."); 441 throw Bu::ExceptionBase("Iterator not initialized.");
442 if( iIndex < 0 || iIndex >= pHeap->core->iFill ) 442 if( iIndex < 0 || iIndex >= pHeap->core->iFill )
443 throw Bu::ExceptionBase("Iterator out of bounds."); 443 throw Bu::ExceptionBase("Iterator out of bounds.");
444 } 444 }
445 445
446 public: 446 public:
447 const_iterator() : 447 const_iterator() :
448 pHeap( NULL ), 448 pHeap( NULL ),
449 iIndex( -1 ) 449 iIndex( -1 )
450 { 450 {
451 } 451 }
452 452
453 const_iterator( const const_iterator &i ) : 453 const_iterator( const const_iterator &i ) :
454 pHeap( i.pHeap ), 454 pHeap( i.pHeap ),
455 iIndex( i.iIndex ) 455 iIndex( i.iIndex )
456 { 456 {
457 } 457 }
458 458
459 const_iterator( const iterator &i ) : 459 const_iterator( const iterator &i ) :
460 pHeap( i.pHeap ), 460 pHeap( i.pHeap ),
461 iIndex( i.iIndex ) 461 iIndex( i.iIndex )
462 { 462 {
463 } 463 }
464 464
465 bool operator==( const const_iterator &oth ) const 465 bool operator==( const const_iterator &oth ) const
466 { 466 {
467 return (oth.pHeap == pHeap) && (oth.iIndex == iIndex); 467 return (oth.pHeap == pHeap) && (oth.iIndex == iIndex);
468 } 468 }
469 469
470 bool operator!=( const const_iterator &oth ) const 470 bool operator!=( const const_iterator &oth ) const
471 { 471 {
472 return (oth.pHeap != pHeap) || (oth.iIndex != iIndex); 472 return (oth.pHeap != pHeap) || (oth.iIndex != iIndex);
473 } 473 }
474 474
475 const item &operator*() 475 const item &operator*()
476 { 476 {
477 pHeap->_hardCopy(); 477 pHeap->_hardCopy();
478 478
479 return pHeap->core->aItem[iIndex]; 479 return pHeap->core->aItem[iIndex];
480 } 480 }
481 481
482 const item *operator->() 482 const item *operator->()
483 { 483 {
484 pHeap->_hardCopy(); 484 pHeap->_hardCopy();
485 485
486 return &(pHeap->core->aItem[iIndex]); 486 return &(pHeap->core->aItem[iIndex]);
487 } 487 }
488 488
489 const_iterator &operator++() 489 const_iterator &operator++()
490 { 490 {
491 checkValid(); 491 checkValid();
492 iIndex++; 492 iIndex++;
493 if( iIndex >= pHeap->core->iFill ) 493 if( iIndex >= pHeap->core->iFill )
494 iIndex = -1; 494 iIndex = -1;
495 495
496 return *this; 496 return *this;
497 } 497 }
498 498
499 const_iterator &operator--() 499 const_iterator &operator--()
500 { 500 {
501 checkValid(); 501 checkValid();
502 iIndex--; 502 iIndex--;
503 503
504 return *this; 504 return *this;
505 } 505 }
506 506
507 const_iterator &operator++( int ) 507 const_iterator &operator++( int )
508 { 508 {
509 checkValid(); 509 checkValid();
510 iIndex++; 510 iIndex++;
511 if( iIndex >= pHeap->core->iFill ) 511 if( iIndex >= pHeap->core->iFill )
512 iIndex = -1; 512 iIndex = -1;
513 513
514 return *this; 514 return *this;
515 } 515 }
516 516
517 const_iterator &operator--( int ) 517 const_iterator &operator--( int )
518 { 518 {
519 checkValid(); 519 checkValid();
520 iIndex--; 520 iIndex--;
521 521
522 return *this; 522 return *this;
523 } 523 }
524 524
525 const_iterator operator+( int iDelta ) 525 const_iterator operator+( int iDelta )
526 { 526 {
527 checkValid(); 527 checkValid();
528 const_iterator ret( *this ); 528 const_iterator ret( *this );
529 ret.iIndex += iDelta; 529 ret.iIndex += iDelta;
530 if( ret.iIndex >= pHeap->iFill ) 530 if( ret.iIndex >= pHeap->iFill )
531 ret.iIndex = -1; 531 ret.iIndex = -1;
532 return ret; 532 return ret;
533 } 533 }
534 534
535 const_iterator operator-( int iDelta ) 535 const_iterator operator-( int iDelta )
536 { 536 {
537 checkValid(); 537 checkValid();
538 const_iterator ret( *this ); 538 const_iterator ret( *this );
539 ret.iIndex -= iDelta; 539 ret.iIndex -= iDelta;
540 if( ret.iIndex < 0 ) 540 if( ret.iIndex < 0 )
541 ret.iIndex = -1; 541 ret.iIndex = -1;
542 return ret; 542 return ret;
543 } 543 }
544 544
545 operator bool() const 545 operator bool() const
546 { 546 {
547 return iIndex != -1; 547 return iIndex != -1;
548 } 548 }
549 549
550 bool isValid() const 550 bool isValid() const
551 { 551 {
552 return iIndex != -1; 552 return iIndex != -1;
553 } 553 }
554 554
555 const_iterator &operator=( const const_iterator &oth ) 555 const_iterator &operator=( const const_iterator &oth )
556 { 556 {
557 pHeap = oth.pHeap; 557 pHeap = oth.pHeap;
558 iIndex = oth.iIndex; 558 iIndex = oth.iIndex;
559 } 559 }
560 560
561 const_iterator &operator=( const iterator &oth ) 561 const_iterator &operator=( const iterator &oth )
562 { 562 {
563 pHeap = oth.pHeap; 563 pHeap = oth.pHeap;
564 iIndex = oth.iIndex; 564 iIndex = oth.iIndex;
565 } 565 }
566 }; 566 };
567 567
568 iterator begin() 568 iterator begin()
569 { 569 {
570 if( core->iFill == 0 ) 570 if( core->iFill == 0 )
571 return end(); 571 return end();
572 return iterator( this, 0 ); 572 return iterator( this, 0 );
573 } 573 }
574 574
575 const_iterator begin() const 575 const_iterator begin() const
576 { 576 {
577 if( core->iFill == 0 ) 577 if( core->iFill == 0 )
578 return end(); 578 return end();
579 return const_iterator( this, 0 ); 579 return const_iterator( this, 0 );
580 } 580 }
581 581
582 iterator end() 582 iterator end()
583 { 583 {
584 return iterator( this, -1 ); 584 return iterator( this, -1 );
585 } 585 }
586 586
587 const_iterator end() const 587 const_iterator end() const
588 { 588 {
589 return const_iterator( this, -1 ); 589 return const_iterator( this, -1 );
590 } 590 }
591 591
592 592
593 protected: 593 protected:
594 virtual Core *_copyCore( Core *src ) 594 virtual Core *_copyCore( Core *src )
595 { 595 {
596 Core *pRet = _allocateCore(); 596 Core *pRet = _allocateCore();
597 597
598 pRet->iSize = src->iSize; 598 pRet->iSize = src->iSize;
599 pRet->iFill = src->iFill; 599 pRet->iFill = src->iFill;
600 pRet->cmp = src->cmp; 600 pRet->cmp = src->cmp;
601 pRet->aItem = pRet->ia.allocate( pRet->iSize ); 601 pRet->aItem = pRet->ia.allocate( pRet->iSize );
602 for( int j = 0; j < pRet->iFill; j++ ) 602 for( int j = 0; j < pRet->iFill; j++ )
603 { 603 {
604 pRet->ia.construct( &pRet->aItem[j], src->aItem[j] ); 604 pRet->ia.construct( &pRet->aItem[j], src->aItem[j] );
605 } 605 }
606 606
607 return pRet; 607 return pRet;
608 } 608 }
609 }; 609 };
610}; 610};
611 611
612#endif 612#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 07:55:02 +0000