Objective-c優先級隊列

Question

我已經開始使用Objective-c進行iOS編程。我從Java切換過來，我想知道是否有任何現有的庫，例如Java Collections Framework for Obj-c，更具體地說是一個優先級隊列實現。我做了一些搜索，但一直無法提出任何事情。

更新：我發現了這一點，但根本不知道如何使用它自己：http://www.ohloh.net/p/pqlib

Answer 1

我無法找到一個優先級隊列的實現，所以我繼續做我自己。我不確定它有多強大，但我希望這可能會將其他人指向正確的方向。

PriorityQueue.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 

PriorityQueue.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 

Comparable.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其中麥克實現了用於C++ STD優先隊列Objective-C的包裝。

Answer 3

CFBinaryHeap可以用作一個優先級隊列和在文檔中被描述爲這樣：https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFBinaryHeapRef/

的缺點似乎是：

1）沒有刪除或更新元素的能力。據我可以告訴你只能刪除min元素。 2）在Objc或Swift中使用它非常類似C並且不太舒服。

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