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

◆ addObjects:

- (void) addObjects: (id) collection

Definition at line 128 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];
}

◆ bubbleDownFrom:

- (void) bubbleDownFrom: (NSUInteger) i

implementation

Provided by category OOPriorityQueue(Private).

Definition at line 128 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;
    }
}

◆ bubbleUpFrom:

- (void) bubbleUpFrom: (NSUInteger) i

implementation

Provided by category OOPriorityQueue(Private).

Definition at line 128 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;
    }
}

◆ copyWithZone:

- (id) copyWithZone: (NSZone *) zone

implementation

Definition at line 128 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;
}

◆ count

- (NSUInteger) count

Definition at line 128 of file OOPriorityQueue.m.

{
    return _count;
}

◆ dealloc

- (void) dealloc

implementation

Definition at line 128 of file OOPriorityQueue.m.

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

◆ description

- (NSString *) description

implementation

Definition at line 128 of file OOPriorityQueue.m.

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

◆ growBuffer

- (void) growBuffer

implementation

Provided by category OOPriorityQueue(Private).

Definition at line 128 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);
}

◆ hash

- (NSUInteger) hash

implementation

Definition at line 128 of file OOPriorityQueue.m.

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

◆ init

- (id) init

implementation

Definition at line 128 of file OOPriorityQueue.m.

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

◆ initWithComparator:

- (id) initWithComparator: (SEL) comparator

Definition at line 128 of file OOPriorityQueue.m.

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

◆ isEqual:

- (BOOL) isEqual: (id) object

implementation

Definition at line 128 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;
}

◆ makeObjectsPerformSelector:

- (void) makeObjectsPerformSelector: (SEL) selector

implementation

Provided by category OOPriorityQueue(Private).

Definition at line 128 of file OOPriorityQueue.m.

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

◆ nextObject

- (id) nextObject

Definition at line 128 of file OOPriorityQueue.m.

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

◆ objectEnumerator

- (NSEnumerator *) objectEnumerator

Definition at line 128 of file OOPriorityQueue.m.

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

◆ peekAtNextObject

- (id) peekAtNextObject

Definition at line 128 of file OOPriorityQueue.m.

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

◆ queueWithComparator:

+ (instancetype) queueWithComparator: (SEL) comparator

Definition at line 128 of file OOPriorityQueue.m.

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

◆ removeExactObject:

- (void) removeExactObject: (id) object

Definition at line 128 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];
        }
    }
}

◆ removeNextObject

- (void) removeNextObject

Definition at line 128 of file OOPriorityQueue.m.

{
    [self removeObjectAtIndex:0];
}

◆ removeObject:

- (void) removeObject: (id) object

Definition at line 128 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];
        }
    }
}

◆ removeObjectAtIndex:

- (void) removeObjectAtIndex: (NSUInteger) i

implementation

Provided by category OOPriorityQueue(Private).

Definition at line 128 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];
}

◆ shrinkBuffer

- (void) shrinkBuffer

implementation

Provided by category OOPriorityQueue(Private).

Definition at line 128 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;
            }
        }
    }
}

◆ sortedObjects

- (NSArray *) sortedObjects

Definition at line 128 of file OOPriorityQueue.m.

{
    return [[self objectEnumerator] allObjects];
}

Member Data Documentation

◆ _capacity

- (NSUInteger) _capacity

private

Definition at line 59 of file OOPriorityQueue.h.

◆ _comparator

- (SEL) _comparator

private

Definition at line 56 of file OOPriorityQueue.h.

◆ _count

- (NSUInteger) _count

private

Definition at line 58 of file OOPriorityQueue.h.

◆ _heap

- (OO_PQ_STRONG id*) _heap

private

Definition at line 57 of file OOPriorityQueue.h.

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

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

Instance Methods

Class Methods

Private Attributes

Detailed Description

Method Documentation

◆ addObject:

◆ addObjects:

◆ bubbleDownFrom:

◆ bubbleUpFrom:

◆ copyWithZone:

◆ count

◆ dealloc

◆ description

◆ growBuffer

◆ hash

◆ init

◆ initWithComparator:

◆ isEqual:

◆ makeObjectsPerformSelector:

◆ nextObject

◆ objectEnumerator

◆ peekAtNextObject

◆ queueWithComparator:

◆ removeExactObject:

◆ removeNextObject

◆ removeObject:

◆ removeObjectAtIndex:

◆ shrinkBuffer

◆ sortedObjects

Member Data Documentation

◆ _capacity

◆ _comparator

◆ _count

◆ _heap