Objective-c優先度キュー

Question

iOSプログラミングでObjective-cを使用し始めました。私はJavaから切り換えました。Obj-cのJava Collections Frameworkのような既存のライブラリ、特に優先度キューの実装があるかどうかを知りたいと思っていました。私はいくつかの検索をしましたが、何かを考え出すことができませんでした。

UPDATE：私はこれを見つけたが、それを自分自身を使用する方法が分からないでしょう：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マイクはC++ STDプライオリティキューのためのObjective-Cラッパーを実装し

// 
// 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。

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