Priority Queue Objective-C++?

Question

I'm working on a path finding algorithm and want to implement a priority queue to speed it up.

I'm adding my Node Object to the queue based on the property fScore. With the smallest fScore always added to the top of the queue.

What are my options for this? Would it best to implement a c++ priority queue using stl? If so how would I set this up to take in my objective-c object Node and how would I specify what the list is being ordered on (Node.fScore).

Thanks

Answer 1

For std:: priority_queue, if you are using ARC you should be 90% of the way there. STL container will automatically store strong references. WIN!

You will need to create a custom compare class.

typedef std::priority_queue<MyClass *, std::vector<MyClass *>, MyClassCompare> MyPriorityQueue;

I'm not exactly sure how you will want to implement your compare class. It will look something like:

class MyClassCompare {
    bool operator()(MyClass *lhs, MyClass *rhs) const {
        // magic!!! Be sure to return a bool.
    }
};

---

Example Wrapper Class

MyClassQueue.h

@interface MyClassQueue : NSObject
@property (nonatomic, readonly) MyClass *topObject;
@property (nonatomic, readonly) NSUInteger count;
- (void)pushObject:(MyClass *)myObject;
- (void)popObject;
- (void)popAllObjects;
@end

MyClassQueue.mm

#import "MyClassQueue.h"
#include <queue>
#import "MyClass.h"

class MyClassCompare {
    bool operator()(MyClass *lhs, MyClass *rhs) const {
        // magic!!! Be sure to return a bool.
    }
};

typedef std::priority_queue<MyClass *, std::vector<MyClass *>, MyClassCompare> MyPriorityQueue;

@interface MyClassQueue ()
@property (nonatomic) MyPriorityQueue *queue;
@end
@implementation MyClassQueue

- (MyClass *)topObject {
    return !self.queue->empty() ? self.queue->top() : nil;
}

- (NSUInteger)count {
    return (NSUInteger)self.queue->size();
}

- (void)pushObject:(MyClass *)myObject {
    self.queue->push(myObject);
}

- (void)popObject {
    if (!self.queue->empty()) {
        self.queue->pop();
    }
}

- (void)popAllObjects {
    if (!self.queue->empty()) {
        delete _queue;
        _queue = new MyPriorityQueue();
    }
}

- (instancetype)init {
    self = [super init];
    if (self != nil) {
        _queue = new MyPriorityQueue();
    }
    return self;
}

- (void)dealloc {
    delete _queue;
    _queue = NULL;
}    
@end