Очередь приоритетов Objective-c

Question

Я начал использовать Objective-c для программирования iOS. Я переключился с Java, и мне хотелось знать, существуют ли какие-либо существующие библиотеки, такие как Java Collections Framework для Obj-c, а точнее - реализация очереди приоритетов. Я сделал некоторые поиски, но не смог ничего придумать.

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

// 
// 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 где Майк реализует Objective-C обертку для приоритетной очереди C++ STD.

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