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 428 of file OOPriorityQueue.m.

                       :(NSUInteger)i
{
    NSUInteger              end = _count - 1;
    NSUInteger              li, ri, next;
    id                      obj = nil;
    
    obj = _heap[i];
    while (PQLeftChild(i) <= end)
    {
        li = PQLeftChild(i);
        ri = PQRightChild(i);
        
        // If left child has lower priority than right child, or there is only one child...
        if (li == end || PQCompare(_heap[li], _heap[ri], _comparator) < 0)
        {
            next = li;
        }
        else
        {
            next = ri;
        }
        
        if (PQCompare(_heap[next], obj, _comparator) < 0)
        {
            // Exchange parent with lowest-priority child
            _heap[i] = _heap[next];
            _heap[next] = obj;
            i = next;
        }
        else  break;
    }
}

References nil, PQCompare(), PQLeftChild(), and PQRightChild().

Here is the call graph for this function:

bubbleUpFrom:

- (void) bubbleUpFrom:

(NSUInteger)

i

Extends class OOPriorityQueue.

Definition at line 406 of file OOPriorityQueue.m.

                     :(NSUInteger)i
{
    NSUInteger              pi;
    id                      obj = nil, par = nil;
    
    while (0 < i)
    {
        pi = PQParent(i);
        obj = _heap[i];
        par = _heap[pi];
        
        if (PQCompare(obj, par, _comparator) < 0)
        {
            _heap[i] = par;
            _heap[pi] = obj;
            i = pi;
        }
        else  break;
    }
}

References nil, PQCompare(), and PQParent().

Here is the call graph for this function:

growBuffer

- (void) growBuffer

Extends class OOPriorityQueue.

Definition at line 462 of file OOPriorityQueue.m.

{
    id                  *newBuffer = NULL;
    NSUInteger          newCapacity;
    
    newCapacity = _capacity * 3 / 2;
    if (newCapacity < kMinCapacity)  newCapacity = kMinCapacity;
    
    // Note: realloc(NULL, size) with non-zero size is equivalent to malloc(size), so this is OK starting from a NULL buffer.
    newBuffer = realloc(_heap, newCapacity * sizeof(id));
    if (newBuffer == NULL)
    {
        // Attempt to grow by just one waffer-thin slot.
        newCapacity = _capacity + 1;
        newBuffer = realloc(_heap, newCapacity * sizeof(id));
        
        if (newBuffer == NULL)
        {
            // Failed to grow.
            [NSException raise:NSMallocException
                        format:@"Could not expand capacity of OOPriorityQueue."];
        }
    }
    
    _heap = newBuffer;
    _capacity = newCapacity;
    
    assert(_count < _capacity);
}

References growBuffer, and kMinCapacity.

Referenced by growBuffer.

Here is the call graph for this function:

Here is the caller graph for this function:

makeObjectsPerformSelector:

- (void) makeObjectsPerformSelector:

(SEL)

selector

Extends class OOPriorityQueue.

Definition at line 393 of file OOPriorityQueue.m.

                                   :(SEL)selector
{
    NSUInteger              i;
    
    if (selector == NULL)  return;
    
    for (i = 0; i != _count; ++i)
    {
        [_heap[i] performSelector:selector];
    }
}

removeObjectAtIndex:

- (void) removeObjectAtIndex:

(NSUInteger)

i

Extends class OOPriorityQueue.

Definition at line 517 of file OOPriorityQueue.m.

                           :(NSUInteger)i
{
    id                  object = nil;
    
    if (_count <= i)  return;
    
    object = _heap[i];
    if (i < --_count)
    {
        // Overwrite object with last object in array
        _heap[i] = _heap[_count];
        
        // Push previously-last object down until tree is partially ordered.
        [self bubbleDownFrom:i];
    }
    else
    {
        // Special case: removing last (or only) object. No bubbling needed.
    }
    
    [object autorelease];
    if (_count * 2 <= _capacity)  [self shrinkBuffer];
}

References OOPriorityQueue::bubbleDownFrom:, nil, and OOPriorityQueue::shrinkBuffer.

Here is the call graph for this function:

shrinkBuffer

- (void) shrinkBuffer

Extends class OOPriorityQueue.

Definition at line 493 of file OOPriorityQueue.m.

{
    NSUInteger          amountToRemove;
    id                  *newBuffer = NULL;
    NSUInteger          newCapacity;
    
    if (kMinCapacity < _capacity)
    {
        // Remove two thirds of free space, if at least three slots are free.
        amountToRemove = (_capacity - _count) * 2 / 3;
        if (2 < amountToRemove)
        {
            newCapacity = _capacity - amountToRemove;
            newBuffer = realloc(_heap, newCapacity * sizeof(id));
            if (newBuffer != NULL)
            {
                _heap = newBuffer;
                _capacity = newCapacity;
            }
        }
    }
}

References kMinCapacity, and shrinkBuffer.

Referenced by shrinkBuffer.

Here is the call graph for this function:

Here is the caller graph for this function:

---

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

• src/Core/OOPriorityQueue.m