OOPriorityQueue Class Reference

#include <OOPriorityQueue.h>

Inheritance diagram for OOPriorityQueue:

Collaboration diagram for OOPriorityQueue:

Instance Methods
(id)	- initWithComparator:
(void)	- addObject:
(void)	- removeObject:
(void)	- removeExactObject:
(NSUInteger)	- count
(id)	- nextObject
(id)	- peekAtNextObject
(void)	- removeNextObject
(void)	- addObjects:
(NSArray *)	- sortedObjects
(NSEnumerator *)	- objectEnumerator
(id)	- init [implementation]
(void)	- dealloc [implementation]
(NSString *)	- description [implementation]
(BOOL)	- isEqual: [implementation]
(NSUInteger)	- hash [implementation]
(id)	- copyWithZone: [implementation]
(void)	- makeObjectsPerformSelector: [implementation]
(void)	- bubbleUpFrom: [implementation]
(void)	- bubbleDownFrom: [implementation]
(void)	- growBuffer [implementation]
(void)	- shrinkBuffer [implementation]
(void)	- removeObjectAtIndex: [implementation]

Class Methods
(instancetype)	+ queueWithComparator:

Private Attributes
SEL	_comparator
OO_PQ_STRONG id *	_heap
NSUInteger	_count
NSUInteger	_capacity

Detailed Description

Definition at line 52 of file OOPriorityQueue.h.

Method Documentation

addObject:

- (void) addObject:

(id)

object

Definition at line 271 of file OOPriorityQueue.m.

                  :(id)object
{
    NSUInteger          i;
    
    // Validate object
    if (object == nil)
    {
        [NSException raise:NSInvalidArgumentException
                    format:@"Attempt to insert nil into OOPriorityQueue."];
    }
    
    if (![object respondsToSelector:_comparator])
    {
        [NSException raise:NSInvalidArgumentException
                    format:@"Attempt to insert object (%@) which does not support comparator %@ into OOPriorityQueue.",
                           object, NSStringFromSelector(_comparator)];
    }
    
    // Ensure there is sufficent space.
    if (_count == _capacity)  [self growBuffer];
    
    // insert object at end of buffer.
    i = _count++;
    _heap[i] = object;
    
    [self bubbleUpFrom:i];
    [object retain];
}

References _capacity, _comparator, _count, _heap, bubbleUpFrom:, growBuffer, and nil.

Referenced by addObjects:, and OOScriptTimer::scheduleTimer.

Here is the call graph for this function:

Here is the caller graph for this function:

addObjects:

- (void) addObjects:

(id)

collection

Definition at line 366 of file OOPriorityQueue.m.

                   :(id)collection
{
    id                  value = nil;
    
    if ([collection respondsToSelector:@selector(objectEnumerator)])  collection = [collection objectEnumerator];
    if (![collection respondsToSelector:@selector(nextObject)])  return;
    
    while ((value = [collection nextObject]))  [self addObject:value];
}

References addObject:, nextObject, nil, and objectEnumerator.

Referenced by OOScriptTimer::updateTimers.

Here is the call graph for this function:

Here is the caller graph for this function:

bubbleDownFrom:

- (void) bubbleDownFrom: (NSUInteger) i

implementation

Provided by category OOPriorityQueue(Private).

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;
    }
}

Referenced by OOPriorityQueue(Private)::removeObjectAtIndex:.

Here is the caller graph for this function:

bubbleUpFrom:

- (void) bubbleUpFrom: (NSUInteger) i

implementation

Provided by category OOPriorityQueue(Private).

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;
    }
}

Referenced by addObject:.

Here is the caller graph for this function:

copyWithZone:

- (id) copyWithZone: (NSZone *) zone

implementation

Definition at line 243 of file OOPriorityQueue.m.

                   :(NSZone *)zone
{
    OOPriorityQueue             *copy = nil;
    
    copy = [[self class] allocWithZone:zone];
    if (copy != nil)
    {
        copy->_comparator = _comparator;
        copy->_count = _count;
        copy->_capacity = _count;
        
        copy->_heap = malloc(_count * sizeof(id));
        if (copy->_heap != NULL)
        {
            memcpy(copy->_heap, _heap, _count * sizeof(id));
            [copy makeObjectsPerformSelector:@selector(retain)];
        }
        else  if (_count != 0)
        {
            [copy release];
            copy = nil;
        }
    }
    
    return copy;
}

References _capacity, _comparator, _count, _heap, makeObjectsPerformSelector:, and nil.

Here is the call graph for this function:

count

- (NSUInteger) count

Definition at line 338 of file OOPriorityQueue.m.

{
    return _count;
}

References _count, and count.

Referenced by count, and isEqual:.

Here is the call graph for this function:

Here is the caller graph for this function:

dealloc

- (void) dealloc

implementation

Definition at line 168 of file OOPriorityQueue.m.

{
    [self makeObjectsPerformSelector:@selector(release)];
    free(_heap);
    
    [super dealloc];
}

References _heap, dealloc, and makeObjectsPerformSelector:.

Referenced by dealloc.

Here is the call graph for this function:

Here is the caller graph for this function:

description

- (NSString *) description

implementation

Definition at line 177 of file OOPriorityQueue.m.

{
    return [NSString stringWithFormat:@"<%@ %p>{count=%lu, capacity=%lu}", [self class], self, _count, _capacity];
}

References description.

Referenced by description.

Here is the call graph for this function:

Here is the caller graph for this function:

growBuffer

- (void) growBuffer

implementation

Provided by category OOPriorityQueue(Private).

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);
}

Referenced by addObject:.

Here is the caller graph for this function:

hash

- (NSUInteger) hash

implementation

Definition at line 236 of file OOPriorityQueue.m.

{
    if (_count == 0)  return NSNotFound;
    return _count ^ [_heap[0] hash];
}

References _count, and hash.

Referenced by hash.

Here is the call graph for this function:

Here is the caller graph for this function:

init

- (id) init

implementation

Definition at line 162 of file OOPriorityQueue.m.

{
    return [self initWithComparator:@selector(compare:)];
}

References init, and initWithComparator:.

Referenced by init.

Here is the call graph for this function:

Here is the caller graph for this function:

initWithComparator:

- (id) initWithComparator:

(SEL)

comparator

Definition at line 144 of file OOPriorityQueue.m.

                         :(SEL)comparator
{
    if (comparator == NULL)
    {
        [self release];
        return nil;
    }
    
    self = [super init];
    if (self != nil)
    {
        _comparator = comparator;
    }
    
    return self;
}

References _comparator, and nil.

Referenced by init.

Here is the caller graph for this function:

isEqual:

- (BOOL) isEqual: (id) object

implementation

Definition at line 206 of file OOPriorityQueue.m.

                :(id)object
{
    NSUInteger                  i;
    OOPriorityQueue             *selfCopy = nil, *otherCopy = nil;
    BOOL                        identical = YES;
    
    if (object == self)  return YES;
    if (![object isKindOfClass:[self class]])  return NO;
    
    if (_count != [object count])  return NO;
    if (_count == 0)  return YES;
    
    selfCopy = [self copy];
    otherCopy = [object copy];
    i = _count;
    while (i--)
    {
        if (![[selfCopy nextObject] isEqual:[otherCopy nextObject]])
        {
            identical = NO;
            break;
        }
    }
    [selfCopy release];
    [otherCopy release];
    
    return identical;
}

References _count, count, nextObject, and nil.

Here is the call graph for this function:

makeObjectsPerformSelector:

- (void) makeObjectsPerformSelector: (SEL) selector

implementation

Provided by category OOPriorityQueue(Private).

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];
    }
}

Referenced by copyWithZone:, and dealloc.

Here is the caller graph for this function:

nextObject

- (id) nextObject

Definition at line 344 of file OOPriorityQueue.m.

{
    id result = [self peekAtNextObject];
    [self removeNextObject];
    return result;
}

References nextObject, peekAtNextObject, and removeNextObject.

Referenced by addObjects:, isEqual:, nextObject, and OOPriorityQueueEnumerator::nextObject.

Here is the call graph for this function:

Here is the caller graph for this function:

objectEnumerator

- (NSEnumerator *) objectEnumerator

Definition at line 383 of file OOPriorityQueue.m.

{
    return [[[OOPriorityQueueEnumerator alloc] initWithPriorityQueue:self] autorelease];
}

References objectEnumerator.

Referenced by addObjects:, objectEnumerator, and sortedObjects.

Here is the call graph for this function:

Here is the caller graph for this function:

peekAtNextObject

- (id) peekAtNextObject

Definition at line 352 of file OOPriorityQueue.m.

{
    if (_count == 0)  return nil;
//  return [[_heap[0] retain] autorelease];
    return _heap[0];
}

References _count, _heap, nil, and peekAtNextObject.

Referenced by nextObject, peekAtNextObject, and OOScriptTimer::updateTimers.

Here is the call graph for this function:

Here is the caller graph for this function:

queueWithComparator:

+ (instancetype) queueWithComparator:

(SEL)

comparator

Definition at line 138 of file OOPriorityQueue.m.

                                    :(SEL)comparator
{
    return [[[self alloc] initWithComparator:comparator] autorelease];
}

removeExactObject:

- (void) removeExactObject:

(id)

object

Definition at line 322 of file OOPriorityQueue.m.

                          :(id)object
{
    NSUInteger              i;
    
    if (object == nil)  return;
    
    for (i = 0; i < _count; ++i)
    {
        if (object == _heap[i])
        {
            [self removeObjectAtIndex:i];
        }
    }
}

References _count, _heap, nil, and removeObjectAtIndex:.

Referenced by OOScriptTimer::unscheduleTimer.

Here is the call graph for this function:

Here is the caller graph for this function:

removeNextObject

- (void) removeNextObject

Definition at line 360 of file OOPriorityQueue.m.

{
    [self removeObjectAtIndex:0];
}

References removeNextObject, and removeObjectAtIndex:.

Referenced by nextObject, removeNextObject, and OOScriptTimer::updateTimers.

Here is the call graph for this function:

Here is the caller graph for this function:

removeObject:

- (void) removeObject:

(id)

object

Definition at line 301 of file OOPriorityQueue.m.

                     :(id)object
{
    NSUInteger              i;
    
    /*  Perform linear search for object (using comparator). A depth-first
        search could skip leaves of lower priority, but I don't expect this to
        be called very often.
    */
    
    if (object == nil)  return;
    
    for (i = 0; i < _count; ++i)
    {
        if (PQCompare(object, _heap[i], _comparator) == 0)
        {
            [self removeObjectAtIndex:i];
        }
    }
}

References _comparator, _count, _heap, nil, PQCompare(), and removeObjectAtIndex:.

Here is the call graph for this function:

removeObjectAtIndex:

- (void) removeObjectAtIndex: (NSUInteger) i

implementation

Provided by category OOPriorityQueue(Private).

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];
}

Referenced by removeExactObject:, removeNextObject, and removeObject:.

Here is the caller graph for this function:

shrinkBuffer

- (void) shrinkBuffer

implementation

Provided by category OOPriorityQueue(Private).

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;
            }
        }
    }
}

Referenced by OOPriorityQueue(Private)::removeObjectAtIndex:.

Here is the caller graph for this function:

sortedObjects

- (NSArray *) sortedObjects

Definition at line 377 of file OOPriorityQueue.m.

{
    return [[self objectEnumerator] allObjects];
}

References objectEnumerator, and sortedObjects.

Referenced by OOScriptTimer::noteGameReset, and sortedObjects.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

_capacity

- (NSUInteger) _capacity

private

Definition at line 59 of file OOPriorityQueue.h.

Referenced by addObject:, and copyWithZone:.

_comparator

- (SEL) _comparator

private

Definition at line 56 of file OOPriorityQueue.h.

Referenced by addObject:, copyWithZone:, initWithComparator:, and removeObject:.

_count

- (NSUInteger) _count

private

Definition at line 58 of file OOPriorityQueue.h.

Referenced by addObject:, copyWithZone:, count, hash, isEqual:, peekAtNextObject, removeExactObject:, and removeObject:.

_heap

- (OO_PQ_STRONG id*) _heap

private

Definition at line 57 of file OOPriorityQueue.h.

Referenced by addObject:, copyWithZone:, dealloc, peekAtNextObject, removeExactObject:, and removeObject:.

---

The documentation for this class was generated from the following files:

• src/Core/OOPriorityQueue.h
• src/Core/OOPriorityQueue.m