The Rules
  • Feel free to leave constructive criticism, or point out a better way to do something.
  • Personal attacks or flames, on me or anyone else, will be deleted.
  • Past history has shown that 99% of comments I can't read (i.e. those in other languages) to be spam. Therefore, any comment I can't read will be removed.
  • I'm pretty mellow concerning profanity, but excessive (as determined subjectively by me), bad language will be removed.

Thursday, May 22, 2008

NSMutableArray makes awesome Cocoa stacks and queues

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... :)

8 comments:

Anonymous said...

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.

Alex said...

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.

Quinn said...

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? ;-)

Quinn said...

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.

Bleyddyn said...

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];
}

tasteofindia said...

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?

Quinn said...
This comment has been removed by the author.
Quinn said...

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.