objective-c - Objective-c 优先级队列

Question

我已经开始使用 Objective-c 进行 iOS 编程。我从 Java 切换过来，我想知道是否有任何现有的库，例如用于 Obj-c 的 Java 集合框架，更具体地说是优先级队列实现。我已经进行了一些搜索，但无法提出任何建议。

更新：我发现了这个，但不知道如何自己使用它：http: //www.ohloh.net/p/pqlib

Answer 1

我无法找到优先级队列的实现，所以我继续制作自己的。我不确定它有多强大，但我希望它可以为其他人指明正确的方向。

优先队列.h

//
//  PriorityQueue.h
//

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

//Implements a priority queue. All objects in queue must implement the comparable protocol and must be all of the same type. The queue can be explicity typed at initialization, otherwise the type of the first object entered will be the type of the queue
@interface PriorityQueue : NSObject{
    NSMutableArray *queue;
    Class type;
}

- (id)init;
- (id)initWithObjects:(NSSet *)objects;
- (id)initWithCapacity:(int)capacity;
- (id)initWithCapacity:(int)capacity andType:(Class)oType; //Queue will reject objects not of that type

#pragma mark - Useful information
- (BOOL)isEmpty;
- (BOOL)contains:(id<comparable, NSObject>)object;
- (Class)typeOfAllowedObjects; //Returns the type of objects allowed to be stored in the queue
- (int) size;

#pragma mark - Mutation
- (void)clear;
- (BOOL)add:(id<comparable, NSObject>)object;
- (void)remove:(id<comparable, NSObject>)object;

#pragma mark - Getting things out
- (id)peek;
- (id)poll;
- (id)objectMatchingObject:(id<comparable, NSObject>)object;
- (NSArray *)toArray;

#pragma mark -
- (void)print;

@end

优先队列.m

//
//  PriorityQueue.m
//

#import "PriorityQueue.h"

#define INITIAL_CAPACITY 50
@implementation PriorityQueue

#pragma mark - Initialization
- (id)init{
    return [self initWithCapacity:INITIAL_CAPACITY andType:nil];
}

- (id)initWithObjects:(NSSet *)objects{
    self = [self initWithCapacity:INITIAL_CAPACITY andType:nil];
    for (id<comparable, NSObject>object in objects){
        [self add:object];
    }
    return self;
}

- (id)initWithCapacity:(int)capacity{
    return [self initWithCapacity:capacity andType:nil];
}

- (id)initWithCapacity:(int)capacity andType:(Class)oType{
    self = [super init];
    if(self){
        queue = [[NSMutableArray alloc] init];
        type = oType;
    }
    return self;
}

#pragma mark - Useful information
- (BOOL)isEmpty{
    if(queue.count == 0){
        return YES;
    }
    else{ return NO;}
}

- (BOOL)contains:(id<comparable, NSObject>)object{
    //Search the array to see if the object is already there
    for(id<comparable> o in queue){
        if([o isEqual:object]){
            return YES;
        }
    }
    return NO;
}

- (Class)typeOfAllowedObjects{
    NSLog(@"Allowed Types: %@", type);
    return type;
}

- (int) size{
    return [queue count];
}

#pragma mark - Mutation
//Mutation
- (void)clear{
    [queue removeAllObjects];
}

//A "greater" object (compareTo returns 1) is at the end of the queue.
- (BOOL)add:(id<comparable, NSObject>)object{
    //Make sure the object's type is the same as the type of the queue
    if(type == nil){
//        NSLog(@"Type is nil");
        type = [object class];
    }
    if([object class] != type){
        NSLog(@"ERROR: Trying to add incorrect object");
        return NO;
    }

    if([queue count] == 0){
        [queue addObject:object];
        return YES;
    }
    for(int i = 0; i < [queue count]; i++){
        if([object compareTo:queue[i]] < 0){
            [queue insertObject:object atIndex:i];
            return YES;
        }
    }
    [queue addObject:object];
    return YES;
}

- (void)remove:(id<comparable, NSObject>)object{
    [queue removeObject:object];
}

#pragma mark - Getting things out
- (id)peek{
    return queue[0];
}

- (id)poll{
    //Get the object at the front
    id head = queue[0];

    //Remove and return that object
    [queue removeObject:head];
    return head;
}

- (id)objectMatchingObject:(id<comparable, NSObject>)object{
    //Search the array to see if the object is already there
    for(id<comparable> o in queue){
        if([o isEqual:object]){
            return o;
        }
    }
    return nil;
}

- (NSArray *)toArray{
    return [[NSArray alloc] initWithArray:queue];
}

#pragma mark -
- (NSString *)description{
    return [NSString stringWithFormat:@"PriorityQueue: %@ allows objects of type %@", queue, type];
}

- (void)print{
    NSLog(@"%@", [self description]);
}

@end

可比.h

//
//  comparable.h
//

#import <Foundation/Foundation.h>


//NOTE: Class must check to make sure it is the same class as whatever is passed in
@protocol comparable

- (int)compareTo:(id<comparable, NSObject>)object;
- (BOOL)isEqual:(id<comparable, NSObject>)object;

@end

Answer 2

请参阅https://mikeash.com/pyblog/using-evil-for-good.html，其中 Mike 为 C++ STD 优先级队列实现了 Objective-C 包装器。

Answer 3

CFBinaryHeap 可用作优先级队列，并在文档中这样描述：https ://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFBinaryHeapRef/

缺点似乎是：

1) 没有删除或更新元素的能力。据我所知，您只能删除 min 元素。

2) 它非常类似于 C，在 Objc 或 Swift 中使用起来不是很愉快。

Answer 4

我支持价值更新的方法。由于 CFBinaryHeap 不支持更新值，我将它们放在失效列表中，一旦被提取，对象就会再次插入并进行新的提取。

/**
 Objective-C wrapper around CFBinaryHeap implementing a priority queue and extended by updating a previous value
 */

NS_ASSUME_NONNULL_BEGIN

@interface BEPriorityQueue<ObjectType, ValueType> : NSObject

- (void)dispose;

@property (nonatomic, readonly) NSUInteger count;

- (void)insert:(ObjectType)object value:(ValueType)value;
- (void)update:(ObjectType)object value:(ValueType)value;

/** returns and removes object with lowest value (highest priority */
- (ObjectType)extractMinimum;

- (BOOL)containsObject:(ObjectType)object;
- (id)valueForObject:(id)object;

- (void)removeAllObjects;

@end

NS_ASSUME_NONNULL_END

有了这个实现：

NS_ASSUME_NONNULL_BEGIN

@interface BEPriorityQueue()

- (CFComparisonResult)compareObject:(id)object1 with:(id)object2;

@end

static CFComparisonResult BEPriorityQueueCompareItems(const void *ptr1, const void *ptr2, void *info)
{
    id object1 = (__bridge id)ptr1;
    id object2 = (__bridge id)ptr2;

    BEPriorityQueue* queue = (__bridge id)info;
    return [queue compareObject:object1 with:object2];
}

static const void *BEPriorityQueueItemRetain(CFAllocatorRef allocator, const void *ptr) {
    return CFRetain(ptr);
}

static void BEPriorityQueueItemRelease(CFAllocatorRef allocator, const void *ptr) {
    CFRelease(ptr);
}

@implementation BEPriorityQueue
{
    BOOL                _disposed;
    CFBinaryHeapRef     _binaryHeapRef;
    NSMapTable*         _objectToValue;
    NSMutableSet*       _invalidated;
}

- (instancetype)init
{
    self = [super init];
    if (self)
    {

        CFBinaryHeapCallBacks callbacks = (CFBinaryHeapCallBacks) {
            .version = 0,
            .retain = &BEPriorityQueueItemRetain,
            .release = &BEPriorityQueueItemRelease,
            .copyDescription = &CFCopyDescription,
            .compare = &BEPriorityQueueCompareItems
        };

        CFBinaryHeapCompareContext compareContext = (CFBinaryHeapCompareContext) {
            .version = 0,
            .info = (__bridge void *)(self),
            .retain = NULL,
            .release = NULL,
            .copyDescription = NULL,
        };

        _binaryHeapRef = CFBinaryHeapCreate(NULL, 0, &callbacks, &compareContext);
        _objectToValue = [NSMapTable strongToStrongObjectsMapTable];
        _invalidated = [NSMutableSet set];
    }
    return self;
}

- (void)dealloc
{
    [self dispose];

    if (_binaryHeapRef != NULL)
    {
        CFRelease(_binaryHeapRef);
        _binaryHeapRef = NULL;
    }
}

- (void)dispose
{
    [self removeAllObjects];
    _disposed = YES;
}

#pragma mark internal

- (CFComparisonResult)compareObject:(id)object1 with:(id)object2
{
    id value1 = [_objectToValue objectForKey:object1];
    id value2 = [_objectToValue objectForKey:object2];
    return (CFComparisonResult)[value1 compare:value2];
}

#pragma mark interface

- (NSUInteger)count
{
    BEEnsureFalse(_disposed);
    return (NSUInteger)CFBinaryHeapGetCount(_binaryHeapRef);
}

- (id)extractMinimum
{
    BEEnsureFalse(_disposed);

    const void *ptr = NULL;
    if (!CFBinaryHeapGetMinimumIfPresent(_binaryHeapRef, &ptr))
        return nil;

    id object = (__bridge id)ptr;
    id value = [_objectToValue objectForKey:object];

    CFBinaryHeapRemoveMinimumValue(_binaryHeapRef);
    [_objectToValue removeObjectForKey:object];

    // if the objects was invalidated, it may no longer be the minimum
    // therefore reinsert the object and extract again
    if ([_invalidated containsObject:object])
    {
        [_invalidated removeObject:object];
        [self insert:object value:value];
        return [self extractMinimum];
    }

    return object;
}

- (void)insert:(id)object value:(id)value
{
    BEEnsureFalse(_disposed);
    BEEnsureIsNotNil(object);
    BEEnsureIsNotNil(value);
    BEEnsureTrue([value respondsToSelector:@selector(compare:)]); // <NSComparable>

    [_objectToValue setObject:value forKey:object]; // first to be available furing insertion compare
    CFBinaryHeapAddValue(_binaryHeapRef, (__bridge void *)object);
}

- (void)update:(id)object value:(id)value
{
    BEEnsureFalse(_disposed);
    BEEnsureIsNotNil(object);
    BEEnsureTrue([value respondsToSelector:@selector(compare:)]); // <NSComparable>

    [_objectToValue setObject:value forKey:object]; // first to be available during insertion compare
    [_invalidated addObject:object];
}

- (BOOL)containsObject:(id)object
{
    BEEnsureFalse(_disposed);
    return CFBinaryHeapContainsValue(_binaryHeapRef, (__bridge void *)object);
}

- (id)valueForObject:(id)object
{
    return [_objectToValue objectForKey:object];
}

- (void)removeAllObjects
{
    CFBinaryHeapRemoveAllValues(_binaryHeapRef);
    [_objectToValue removeAllObjects];
    [_invalidated removeAllObjects];
}

@end


NS_ASSUME_NONNULL_END