Amaç-c Öncelik Sırası

Question

iOS programlama için Objective-c'yi kullanmaya başladım. Java'dan geçiş yaptım ve Obj-c için Java Koleksiyonlar Çerçevesi, daha özel olarak bir öncelik sırası uygulaması gibi mevcut kütüphanelerin olup olmadığını öğrenmek istedim. Bazı aramalar yaptım, ancak hiçbir şey yapamadım.

GÜNCELLEME: bunu buldum, ama kendim nasıl kullanılacağını hiçbir fikrim yok olacaktır: http://www.ohloh.net/p/pqlib

Answer 1

Ben bir öncelik sırasının bir uygulama bulamadı, bu yüzden devam ettim ve kendi yaptı. Ne kadar sağlam olduğundan emin değilim, ama umarım başkalarına doğru yönde işaret edebilir.

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 Mike C++ STD öncelik sırası hedefi-Cı sarıcı uygular

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

bakınız https://mikeash.com/pyblog/using-evil-for-good.html. CFBinaryHeap Öncelik Sırasına olarak kullanılabilir ve docs gibi tarif edilir

Answer 3

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

olumsuzlukları görünmektedir:

1) hiçbir kaldırmasını veya güncelleme eleman yeteneği yoktur. Anlayabildiğim kadarıyla sadece min elementini kaldırabilirsiniz.

2) Objc veya Swift'de kullanımı çok hoş değildir ve çok hoş değildir.

Answer 4

Yaklaşımı destekleyen değer güncelleştirmelerim. CFBinaryHeap güncelleme değerlerini desteklemediğinden, bunları bir geçersiz kılma listesine koydum ve çıkartıldıktan sonra nesne tekrar yerleştirilir ve yeni bir ekstraksiyon yapılır. Sana Grand Central Distpatch olacağını aradığınızı en yakın düşünüyorum

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