dev6546 dev6546 - 4 months ago 30
Objective-C Question

Priority Queue Objective-C++?

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

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;
- (void)pushObject:(MyClass *)myObject;
- (void)popObject;
@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->top();   }
- (void)pushObject:(MyClass *)myObject { self.queue->push(myObject); }
- (void)popObject                      { self.queue->pop();          }

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

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