views:

405

answers:

3

Instead of implementing my own I was wondering if anyone knows of a histogram or bag datastructure implementation in Objective-C that I can use.

Essentially a histogram is a hashmap of lists where the lists contain values that relate to their hash entry. A good example is a histogram of supermarket items where you place each group of items dairy, meat, canned goods in their own bag. You can then very easily access each group of items according to their type.

A: 

There's one in the GNU Objective-C Class library, but the docs appear to be pretty incomplete and the project's homepage must be currently having a problem -- still, if GPL software is acceptable for your project, you might want to download and check the sources.

Alex Martelli
From what I can tell, that library project seems pretty dead. It says it has become part of GNUstep, but I couldn't find anything promising in the GNUstep SVN repository.
Quinn Taylor
+2  A: 

NSCountedSet is a multiset (aka "bag") that counts distinct objects, but doesn't allow duplicates. However, based on your explanation, I don't think that's what you need, and neither is a histogram, which automatically buckets values based on a set of (usually numerical) ranges.

I believe what you really want is a multimap, which is a "key to one-or-more values" relation. The data structures framework I maintain includes CHMultiDictionary, a multimap implementation. I won't claim by any means that it's perfect or complete, but I hope it may be helpful for your problem.

Quinn Taylor
Note: My CHMultiDictionary stores the values for each key in a set, so no duplicates are permitted. If you want to allow duplicate values, you'll probably want something more like what Peter suggests. Perhaps modifying my code so the user can decide whether to allow duplicates would be a nice touch...
Quinn Taylor
Another possibility is the OHHashMultiMap class in ObjectiveLib. (http://objectivelib.sourceforge.net/NoOpenStep/interfaceOLHashMultiMap.html) The downside is that this library is much closer to STL than to the Cocoa collections — the APIs don't quite match up and the concepts are quite different from NS(Mutable)Dictionary.
Quinn Taylor
+2  A: 

It sounds to me like you simply want a dictionary of arrays. You can put NSArrays as elements of NSDictionarys, something like:

NSMutableDictionary* dict = [NSMutableDictionary dictionary];
[dict setObject:[NSMutableArray arrayWithObjects:@"milk", @"eggs", @"cheese", nil] forKey:@"dairy"];
[dict setObject:[NSMutableArray arrayWithObjects:@"steak", @"sausages", @"mince", nil] forKey:@"meat"];

[[dict objectForKey:@"meat"] addObject:@"lamb"];

NSLog( @"Dictionary is %@", dict );
Peter N Lewis