//
you're reading...

Programming

Behold the Holy Array!

Sometimes you need a hashtable that is indexed by an integer. Maybe it’s for a game grid or you need it for storing supplementary data for another array, possibly classic C-style array that is part of a cross-platform library which holds opaque objects used by that library.

Swiss cheese boostedYou could use NSMutableDictionary to store this data – but it’ll be overkill. That class needs to have a copy of its keys to work, and creating NSNumber wrappers for each key is largely a waste of memory when you know that the keys will be nonnegative small integers (as in no larger than a few thousand).

What you need is a “holy” array – an array with holes in it, just like Swiss cheese. That is, an array that can take in arbitrary nonnegative integer as an index and will store the object with the index that you want, expanding the array as needed. You’ll also want an array that won’t complain and halt your program when you give it an incorrect index. 

I’ve encountered this need many times in my iOS and OS X projects, and I solve it by adding a pair of category methods to NSArray / NSMutableArray. One is -[NSArray objectAtCheckedIndex:] that will retrieve an object out of a possibly “sparse” array, returning nil if there isn’t any object to return. The other side of the pair is -[NSMutableArray setObject:atCheckedIndex:] that will dutifully place an object into the desired index.


@implementation NSArray (FoundationAdditions)

-(id) objectAtCheckedIndex:(NSUInteger) index {
	if(index >= self.count) {
		return nil;
	} else {
		id result =  [self objectAtIndex:index];
		return result == [NSNull null] ? nil : result;
	}
}

@end


@implementation NSMutableArray (FoundationAdditions)


-(void) setObject:(id) object atCheckedIndex:(NSUInteger) index {
	NSNull* null = [NSNull null];
	if (!object) {
		object = null;
	}
	
	NSUInteger count = self.count;
	if (index < count) {
		[self replaceObjectAtIndex:index withObject:object];
	} else {
		if (index > count) {
			NSUInteger delta = index - count;
			for (NSUInteger i=0; i<delta;i++) {
				[self addObject:null];
			}
		}
		[self addObject:object];
	}
}

@end

Since Cocoa arrays can’t have nil elements, I made use of the NSNull singleton to represent an empty position. Thus if you don’t want NSNull objects returned, you’ll need to exclusively use the accessor method above. This is most important when you’re enumerating through the array using the fast enumeration for…in loop, since you can’t always assume that the objects returned by the enumerator will always have the same types (some of them may be NSNull).

Some people may call this a sparse array, because most of its elements are expected to be empty. However my implementation isn’t a real sparse array in its strictest sense, since it still allocates real memory for its “holes”. A true sparse array implementation will not take up memory for each of its empty elements, but I suppose its implementation would be at least as complex as a hashtable and probably not much more efficient. When you’re really concerned for the extra null pointers that are allocated for the array, probably you want to re-look at using NSMutableDictionary for solving your problem instead.

That’s all for now. You take care.



Do you enjoy this post? Enter your e-mail address below to receive articles like this one in your mailbox.

Free Updates!

Learn how to grow your indie business while keeping your day job.

Categories

Archives

Keep updated!

Don't miss out on new articles!