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 우선 순위 큐에 대한 목표 - 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. CFBinaryHeap는 우선 순위 대기열로 사용할 수 있으며 문서에 같은 설명

Answer 3

는 : https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFBinaryHeapRef/

단점은 것 같다 :

1) 더 제거 또는 업데이트 요소의 기능은 없습니다. 내가 알 수있는 한, min 요소 만 제거 할 수 있습니다.

2) Objc 또는 Swift에서 사용하는 것은 매우 C와 비슷하지만별로 즐겁지 않습니다.

Answer 4

나의 접근 방식은 가치 업데이트를 지원합니다. CFBinaryHeap은 값을 업데이트하는 것을 지원하지 않으므로 무효화 목록에 넣고 일단 추출되면 객체가 다시 삽입되고 새로운 추출이 수행됩니다. 난 당신이 그랜드 센트럴 Distpatch 것 찾고있는 가장 가까운 생각

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