Objective-C implementation of a histogram or bag datastructure

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

CFIOMultimap apparently is an implementation of a multimap. However, as of the time of writing I couldn't get it to work. It returns nils all the time when I subscript.

Perhaps it can be fixed and adapted for your use.