Skip to content

Instantly share code, notes, and snippets.

@darcyliu darcyliu/PriorityQueue.h
Last active Nov 6, 2018

Embed
What would you like to do?
Objective-C Priority Queue
//
// 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
//
// 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
//
// 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.