All geek questions in one place

Objective-c Priority Queue

I started using Objective-c for iOS programming. I switched from Java, and I wanted to know if there are any existing libraries, such as the Java Collections Framework for Obj-c, or rather, the implementation of the priority queue. I performed some searches, but could not think of anything.

UPDATE: I found this, but had no idea how to use it: http://www.ohloh.net/p/pqlib

+6
source share
4 answers

I could not find the implementation of the priority queue, so I went ahead and made my own. I'm not sure how great this is, but I hope this can point others in the right direction.

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 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
+2
source

See https://mikeash.com/pyblog/using-evil-for-good.html , where Mike implements the Objective-C wrapper for the C ++ STD priority queue.

+2
source

CFBinaryHeap can be used as a priority queue and is described as such in the documents: https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFBinaryHeapRef/

The disadvantages are as follows:

1) There is no way to delete or update an item. As far as I can tell, you can only remove the min element.

2) It is very C-like and not very pleasant to use in Objc or Swift.

+1
source

My approach supports updating values. Since CFBinaryHeap does not support updating values, I put them on the invalid list, and as soon as it is checked out, the object is inserted again and a new checkout will be performed.

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

With this implementation:

 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
+1
source

Source: https://habr.com/ru/post/949579/

More articles:


All Articles