A difference between Java and Objective-C/Cocoa? Java has ConcurrentLinkedQueue, PriorityBlockingQueue, ArrayBlockingQueue, blah blah blah.
Objective-C/Cocoa(or Foundation) has NSMutableArray. NSMutableArray has some nice instance methods that make it _extremely_ easy to build a queue, stack, priority queue (synchronized or otherwise) without loading up the API with a billion separate classes.
Need a stack?
-(void) push:(id) item {
[list addObject:item] // where list is the actual array in your stack
count++;
}
-(id) pop {
id r = [list lastObject];
[list removeLastObject];
count--;
return r;
}
How about a queue?
-(void) enqueue:(id) item {
[list insertObject:item atIndex:0];
count++;
}
-(id) dequeue {
id r = [list lastObject];
[list removeLastObject];
count--;
return r;
}
Priority queueing and/or synchronization for thread-safety will be left as an exercise for the reader. Man, I've always wanted to say that... :)
Thursday, May 22, 2008
NSMutableArray makes awesome Cocoa stacks and queues
Subscribe to:
Post Comments (Atom)
8 comments:
Very Cool! Thanks for this.
Note that for those playing along at home, it should be -(id) pop
Also, why do you have count as a variable? Can't you just use [list count];
In fact, without the instance variable... you could add these methods to a category on NSMutableArray.
Thanks for the fix on the type-o on pop.
As for using count as a variable, I mainly do that for the case that if you're going to be checking the size of the list often, there is no need for the stack overhead of another method call. Incrementing/decrementing a local variable when you add/remove is cheaper than the overhead of another method call every time you want to know how many items you have.
Alex, it's totally random that I'd happen on your blog and this entry literally the day after I was thinking about this and wrote my own set of classes to implement a few data structures.
I posted the code on the BYU CocoaHeads site.
The local count idea is certainly interesting. The benefit would depend a lot on how much it's used, as you say, and I think any class can spare 4 bytes for another integer. Wait ... you're using NSUInteger on Leopard, right? ;-)
By the way, I took an opposite approach with adding and removing. I treat the 0 index as the front, since iterating through the objects then gives a (more?) intelligent ordering. Another great thing about using NSMutableArray is that adopting NSFastEnumeration is a breeze. Same with NSCopying and NSCoding, so the resulting data structures are first-class citizens.
in dequeue you need to retain r before calling removeLastObject or else it can be deallocated (at least in non-garbage collected environments).
Something like:
-(id) dequeue {
id r = [[list lastObject] retain];
[list removeLastObject];
count--;
return [r autorelease];
}
Nice. Thanks for the tips. Not sure why Apple doesn't include NSStack and NSQueue as part of its core framework.
Does anybody out there know whether NSMutableArrays use linked lists, and if so whether they're optimized for front-end or back-end retrieval?
I figured this would be relevant to the topic. Certainly, it's not hard to create one of these structures on the fly, but it's nice when they're already available, so I took the liberty of making them available. All of the structures are Cocoa-friendly and ready to be used.
http://cocoaheads.byu.edu/code/CHDataStructures
Also, Alex, I accepted your exercise for the reader; behold, CHMutableArrayHeap, a binary heap implementation which works quite nicely as a priority queue.
I also deleted the URL from comment 3, since that code has been integrated into this much better framework. :-)
#tasteofindia - Check out this page for analysis of how NSMutableArray behaves and its likely implementation. Also, the benchmarks in the project above can provide some answers to your question.
Post a Comment