Objective-C Priority Queue

main.m

//
//  main.m
//  PriorityQueue
//
//  Created by Darcy Liu on 2018/11/6.
//  Copyright © 2018 Darcy Liu. All rights reserved.
//

#import <Foundation/Foundation.h>
#import "PriorityQueue.h"

@interface Task : NSObject {
    NSString *_name;
}
@property (nonatomic, assign, readonly) int priority;

- (instancetype)initWithPriority:(int)priority andName:(NSString *)name;
- (NSComparisonResult)compare:(Task *)other;
@end

@implementation Task
- (instancetype)initWithPriority:(int)priority andName:(NSString *)name {
    if ((self = [super init])) {
        _priority = priority;
        _name = [name copy];
    }
    return self;
}
- (NSString *)description {
    return [NSString stringWithFormat:@"%d, %@", _priority, _name];
}

- (NSComparisonResult)compare:(Task *)other {
    if (_priority == other.priority)
        return NSOrderedSame;
    else if (_priority < other.priority)
        return NSOrderedAscending;
    else
        return NSOrderedDescending;
}
@end

int main (int argc, const char *argv[]) {
    @autoreleasepool {
        
        PriorityQueue<NSObject *> *pq = [[PriorityQueue alloc] init];
        
        [pq push:[[Task alloc] initWithPriority:3 andName:@"Clear drains"]];
        [pq push:[[Task alloc] initWithPriority:4 andName:@"Feed cat"]];
        [pq push:[[Task alloc] initWithPriority:5 andName:@"Make tea"]];
        [pq push:[[Task alloc] initWithPriority:1 andName:@"Solve RC tasks"]];
        [pq push:[[Task alloc] initWithPriority:2 andName:@"Tax return"]];
        
        NSLog(@"%@", [pq allObjects]);
        
        while([pq size] > 0) {
            NSLog(@"%@", [pq top]);
            [pq pop];
        }
        
        NSLog(@"isEmpty: %d", [pq isEmpty]);
    }
    return 0;
}

PriorityQueue.h

//
//  PriorityQueue.h
//  PriorityQueue
//
//  Created by Darcy Liu on 2018/11/6.
//  Copyright © 2018 Darcy Liu. All rights reserved.
//

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface PriorityQueue<__covariant T> : NSObject
- (instancetype)initWithCapacity:(NSUInteger)numItems NS_DESIGNATED_INITIALIZER;

- (BOOL)isEmpty;
- (NSUInteger)size;
- (__kindof T)top;
- (void)push:(__kindof T)item;
- (void)pop;
- (NSArray<__kindof T> *)allObjects;
@end

NS_ASSUME_NONNULL_END

PriorityQueue.m

//
//  PriorityQueue.m
//  PriorityQueue
//
//  Created by Darcy Liu on 2018/11/6.
//  Copyright © 2018 Darcy Liu. All rights reserved.
//

#import "PriorityQueue.h"

const void *PQRetain(CFAllocatorRef allocator, const void *ptr) {
    return (__bridge_retained const void *)(__bridge id)ptr;
}
void PQRelease(CFAllocatorRef allocator, const void *ptr) {
    (void)(__bridge_transfer id)ptr;
}
CFComparisonResult PQCompare(const void *ptr1, const void *ptr2, void *unused) {
    if (![(__bridge id)ptr1 respondsToSelector:@selector(compare:)] ||
        ![(__bridge id)ptr2 respondsToSelector:@selector(compare:)] ) {
        return kCFCompareEqualTo;
    }
    return (CFComparisonResult)[(__bridge id)ptr1 compare:(__bridge id)ptr2];
}

@interface PriorityQueue()
{
    CFBinaryHeapRef _pq;
}
@end

@implementation PriorityQueue
- (instancetype)init
{
    return [self initWithCapacity:0];
}

- (instancetype)initWithCapacity:(NSUInteger)numItems
{
    self = [super init];
    if (self) {
        CFBinaryHeapCallBacks callBacks = {0, PQRetain, PQRelease, NULL, PQCompare};
        _pq = CFBinaryHeapCreate(NULL, numItems, &callBacks, NULL);
    }
    return self;
}

- (void)dealloc
{
    CFBinaryHeapRemoveAllValues(_pq);
    CFRelease(_pq);
}

- (BOOL)isEmpty
{
    return 0 == [self size];
}

- (NSUInteger)size
{
    return CFBinaryHeapGetCount(_pq);
}

- (__kindof id)top
{
    return (id)CFBinaryHeapGetMinimum(_pq);
}

- (void)push:(__kindof id)item
{
    CFBinaryHeapAddValue(_pq, (__bridge const void *)item);
}

- (void)pop
{
    CFBinaryHeapRemoveMinimumValue(_pq);
}

- (NSArray *)allObjects
{
    NSUInteger n = [self size];
    const void ** values = malloc(n * sizeof(const void *));
    CFBinaryHeapGetValues(_pq, values);
    CFArrayRef objects = CFArrayCreate(kCFAllocatorDefault, values, n, &kCFTypeArrayCallBacks);
    free(values);
    NSArray *items = (__bridge_transfer NSArray *)objects;
    return items;
}

@end