Oolite 1.91.0.7644-241112-7f5034b
Loading...
Searching...
No Matches
OOPriorityQueue(Private) Category Reference

Instance Methods

(void) - makeObjectsPerformSelector:
 
(void) - bubbleUpFrom:
 
(void) - bubbleDownFrom:
 
(void) - growBuffer
 
(void) - shrinkBuffer
 
(void) - removeObjectAtIndex:
 

Detailed Description

Definition at line 105 of file OOPriorityQueue.m.

Method Documentation

◆ bubbleDownFrom:

- (void) bubbleDownFrom: (NSUInteger) i

Extends class OOPriorityQueue.

Definition at line 128 of file OOPriorityQueue.m.

428 :(NSUInteger)i
429{
430 NSUInteger end = _count - 1;
431 NSUInteger li, ri, next;
432 id obj = nil;
433
434 obj = _heap[i];
435 while (PQLeftChild(i) <= end)
436 {
437 li = PQLeftChild(i);
438 ri = PQRightChild(i);
439
440 // If left child has lower priority than right child, or there is only one child...
441 if (li == end || PQCompare(_heap[li], _heap[ri], _comparator) < 0)
442 {
443 next = li;
444 }
445 else
446 {
447 next = ri;
448 }
449
450 if (PQCompare(_heap[next], obj, _comparator) < 0)
451 {
452 // Exchange parent with lowest-priority child
453 _heap[i] = _heap[next];
454 _heap[next] = obj;
455 i = next;
456 }
457 else break;
458 }
459}
OOINLINE NSComparisonResult PQCompare(id a, id b, SEL comparator)
OOINLINE NSUInteger PQLeftChild(NSUInteger n) INLINE_CONST_FUNC
OOINLINE NSUInteger PQRightChild(NSUInteger n) INLINE_CONST_FUNC
return nil

◆ bubbleUpFrom:

- (void) bubbleUpFrom: (NSUInteger) i

Extends class OOPriorityQueue.

Definition at line 128 of file OOPriorityQueue.m.

406 :(NSUInteger)i
407{
408 NSUInteger pi;
409 id obj = nil, par = nil;
410
411 while (0 < i)
412 {
413 pi = PQParent(i);
414 obj = _heap[i];
415 par = _heap[pi];
416
417 if (PQCompare(obj, par, _comparator) < 0)
418 {
419 _heap[i] = par;
420 _heap[pi] = obj;
421 i = pi;
422 }
423 else break;
424 }
425}
OOINLINE NSUInteger PQParent(NSUInteger n) INLINE_CONST_FUNC

◆ growBuffer

- (void) growBuffer

Extends class OOPriorityQueue.

Definition at line 128 of file OOPriorityQueue.m.

463{
464 id *newBuffer = NULL;
465 NSUInteger newCapacity;
466
467 newCapacity = _capacity * 3 / 2;
468 if (newCapacity < kMinCapacity) newCapacity = kMinCapacity;
469
470 // Note: realloc(NULL, size) with non-zero size is equivalent to malloc(size), so this is OK starting from a NULL buffer.
471 newBuffer = realloc(_heap, newCapacity * sizeof(id));
472 if (newBuffer == NULL)
473 {
474 // Attempt to grow by just one waffer-thin slot.
475 newCapacity = _capacity + 1;
476 newBuffer = realloc(_heap, newCapacity * sizeof(id));
477
478 if (newBuffer == NULL)
479 {
480 // Failed to grow.
481 [NSException raise:NSMallocException
482 format:@"Could not expand capacity of OOPriorityQueue."];
483 }
484 }
485
486 _heap = newBuffer;
487 _capacity = newCapacity;
488
489 assert(_count < _capacity);
490}
@ kMinCapacity

◆ makeObjectsPerformSelector:

- (void) makeObjectsPerformSelector: (SEL) selector

Extends class OOPriorityQueue.

Definition at line 128 of file OOPriorityQueue.m.

393 :(SEL)selector
394{
395 NSUInteger i;
396
397 if (selector == NULL) return;
398
399 for (i = 0; i != _count; ++i)
400 {
401 [_heap[i] performSelector:selector];
402 }
403}

◆ removeObjectAtIndex:

- (void) removeObjectAtIndex: (NSUInteger) i

Extends class OOPriorityQueue.

Definition at line 128 of file OOPriorityQueue.m.

517 :(NSUInteger)i
518{
519 id object = nil;
520
521 if (_count <= i) return;
522
523 object = _heap[i];
524 if (i < --_count)
525 {
526 // Overwrite object with last object in array
527 _heap[i] = _heap[_count];
528
529 // Push previously-last object down until tree is partially ordered.
530 [self bubbleDownFrom:i];
531 }
532 else
533 {
534 // Special case: removing last (or only) object. No bubbling needed.
535 }
536
537 [object autorelease];
538 if (_count * 2 <= _capacity) [self shrinkBuffer];
539}

◆ shrinkBuffer

- (void) shrinkBuffer

Extends class OOPriorityQueue.

Definition at line 128 of file OOPriorityQueue.m.

494{
495 NSUInteger amountToRemove;
496 id *newBuffer = NULL;
497 NSUInteger newCapacity;
498
499 if (kMinCapacity < _capacity)
500 {
501 // Remove two thirds of free space, if at least three slots are free.
502 amountToRemove = (_capacity - _count) * 2 / 3;
503 if (2 < amountToRemove)
504 {
505 newCapacity = _capacity - amountToRemove;
506 newBuffer = realloc(_heap, newCapacity * sizeof(id));
507 if (newBuffer != NULL)
508 {
509 _heap = newBuffer;
510 _capacity = newCapacity;
511 }
512 }
513 }
514}

The documentation for this category was generated from the following file: