macOS Radix Class : Need Public Input

[Jordan72]

I'm learning Objective-C and Cocoa from books. I need some input from people(books don't do that). I'm not in school, so front-row classmates are out of the picture. Here is my first serious class. I need to be groomed to finish. Any input would be greatly appreciated.

Memory leak? Problem with a convention? Another method would be nice? Bad variable/method name? Could use a better algorithm? Anything, if just a small comment will help.

This class gives a uniqe sequence of objects or all unique sequences of objects the programmer sends to a Radix instance. The purpose? Logic analysis, encryption, decryption, real time encryption, debugging, creativity development, etc.

//
//  Radix.h
//  RadixProject
//
//  Created by Jordan Evans on 12/1/05.
//  Copyright 2005 XRADIX All rights reserved.
//

#import <Foundation/Foundation.h>

@interface Radix : NSObject
{
	int numOfSets;//Number of NSArrays in NSArray sent.
	int possibilities;  //This is the total number of possible sequences that can be produced.
	struct radixSet *sets;  //This structure pointer is used to point to an array of structs.  Each struct represents facts about each set(NSArray).
}


-(id)initWithSets:(NSArray *)arrayOfSets;
-(void)zeroElements;
-(void)initRadixVariables:(NSArray *)arrayOfSets;
-(int)possibilities;
-(void)freeSets;
-(void)reInitWithArray:(NSArray *)arrayOfSets;

-(NSArray *)allSequences;
-(NSArray *)sequence: (int)requestedSequence;
-(NSArray *)sequencesInRange:(NSRange)range;

@end


@implementation Radix

struct radixSet
{
	id setPtr;//A pointer to an NSArray.  This NSArray is a set belonging to arrayOfSets.
	int element;//Used to point to an element in a set.  Each element number is the postion it resides in the array.  This number is assinged to element, if that particular element is under query.
	int omegaElement;//Is the number of the postion of the last element(object) in an array set.  Is assigned once.  Is used for carry operations.  I.e., in base ten, when nine is hit, zero is replaced.  Nine is omega element for base ten.
	int radix;//Each set has a base.  This is based on the number of elements(objects) in the set(NSArray).
};

-(int)possibilities
{
	return possibilities;
}

-(id)initWithSets:(NSArray *)arrayOfSets
{
	self = [super init];
	if (self != nil)
	{
		[self initRadixVariables:arrayOfSets];
	}
	return self;
}

-(void)zeroElements
{
	//Reinitialize all elements to alpha position.
	int i;
	
	for(i=0;i<numOfSets;i++)
	{
		sets->element = 0;
		sets++;
	}
	sets -= numOfSets;
}

-(void)freeSets
{
	free(sets);
}

-(void)initRadixVariables:(NSArray *)arrayOfSets
{
	int i;
		
	numOfSets = [arrayOfSets count];
	possibilities = 1;
	sets = (struct radixSet *)malloc (sizeof(struct radixSet)*numOfSets);
	
	for(i=0;i<numOfSets;i++)
	{
		//Each element is set to the alpha element, which is the first object of a NSArray.
		sets->element = 0;
		//Each setPtr is set to it's respective NSArray.
		sets->setPtr = [arrayOfSets objectAtIndex:i];
		//Each base is set, based upon the NSArray count.
		sets->radix = [[arrayOfSets objectAtIndex:i] count];
		//Each omega element is also set based on the NSArray count.
		sets->omegaElement = [sets->setPtr count]-1;
		//possibilities is the product of all bases of the sets(NSArrays).
		possibilities *= (sets->omegaElement + 1);
		sets++;
	}
	sets -= numOfSets;
}

-(void)reInitWithArray:(NSArray *)arrayOfSets
{
	[self freeSets];
	[self initRadixVariables:arrayOfSets];
}

- (void)dealloc;
{
	free(sets);
	[super dealloc];
}

-(NSArray *)allSequences
{
	NSRange seqRange;
	seqRange.location = 0;
	seqRange.length = possibilities;
	
	return [self sequencesInRange:seqRange];
}

-(NSArray *)sequence: (int)requestedSequence
{
	NSMutableArray *sequenceArray = [[NSMutableArray alloc] init];
	
	int i = 0;

	while(requestedSequence)
	{
			//Converts the requestedSequence integer into a multi-base number. At the same time, advances the element of each set.  This advance of element is determined by the varing radix.
			sets[i].element = requestedSequence % sets[i].radix;
			requestedSequence /= sets[i].radix;
			i++;
	}
	
	//Adds appropriate object to array, depending upon where element was set by previous section.
	for( i=0; i<numOfSets; i++ )
		[sequenceArray addObject:[sets[i].setPtr objectAtIndex:sets[i].element] ];
		
	[self zeroElements];
	
	return sequenceArray;
}

-(NSArray *)sequencesInRange:(NSRange)range
{
	int i, v, sequence;
	NSMutableArray *sequenceArray, *returnArray;
	
    sequenceArray = [[NSMutableArray alloc] init];
    returnArray = [[NSMutableArray alloc] init];
	i = 0;v = 0;sequence = 0;
	
	//Does what -sequence does above, for the purpose of getting sequence up to the starting line.  
	while(range.location)
	{
		sets[i].element = range.location % sets[i].radix;
		range.location /= sets[i].radix;
		i++;
	}
	
	for( i=0; i<numOfSets; i++ )
		[sequenceArray addObject:[sets[i].setPtr objectAtIndex:sets[i].element] ];
	
	//Releases object so objects who request sequences have responsibility for memory of object.
	[returnArray addObject:sequenceArray];
	[[returnArray lastObject] release];
	
	do
	{
		do
		{
			//This is the carry implemention, as in math, carry a one.
			if( sets[v].element == sets[v].omegaElement )
			{
				//When a carry occurs, element must be set to alpha element, which is zero.
				sets[v].element = 0;
				//The sets must be advanced, so the next set may increment.  This occurs in the next section.  
				v++;
			}
			
			//If a set is at it's omega element, go back and carry.
		}while( sets[v].element == sets[v].omegaElement );
		
		//Increment the present set.  Element will now refer to next element(object).
		sets[v].element += 1;
		//Zero out the set.  It will remain the zero set around the outer-most do loop, unless a carry operation needs to occur.  If not, the zero set is always incremented.  If there is a carry, the last set that is not at it's omega element will be incremented and at that point the set needs to be zeroed, so incrementation begins in the one's column again. (One's column, as in math).
		v = 0;
		//Increase the number of sequences.
		sequence++;
		
		//All sequences have been added, break.  This is here because the next section would inappropriately allocate an extra sequence.
		if(sequence == (range.location + range.length) )
			break;

		//Allocate an array so a new sequence can be added.
		sequenceArray = [[NSMutableArray alloc] init];
		//Add appropriate objects based upon element position in each set.
		for( i=0; i<numOfSets; i++ )
			[sequenceArray addObject: [sets[i].setPtr objectAtIndex:sets[i].element] ];
			
		[returnArray addObject:sequenceArray];
		[[returnArray lastObject] release];
	}
	while( sequence != (range.location + range.length) );
	
	[self zeroElements];

	return returnArray;
}
@end

int main (int argc, const char * argv[])
{
	NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
	
	NSString *string1 = [NSString stringWithString:@"0"];
	NSString *string2 = [NSString stringWithString:@"1"];
	NSString *string3 = [NSString stringWithString:@"2"];
	NSArray *set1 = [NSArray arrayWithObjects: string1, string2, string3, nil];
	
	NSString *string4 = [NSString stringWithString:@"0"];
	NSString *string5 = [NSString stringWithString:@"1"];
	NSArray *set2 = [NSArray arrayWithObjects: string4, string5, nil];
	
	NSString *string6 = [NSString stringWithString:@"0"];
	NSString *string7 = [NSString stringWithString:@"1"];
	NSArray *set3 = [NSArray arrayWithObjects: string6, string7, nil];
	
	NSString *string8 = [NSString stringWithString:@"0"];
	NSString *string9 = [NSString stringWithString:@"1"];
	NSArray *set4 = [NSArray arrayWithObjects: string8, string9, nil];

	Radix *myRadix = [[Radix alloc] initWithSets:[NSArray arrayWithObjects: set1, set2, set3, set4, nil]];
	
	NSString *string10 = [NSString stringWithString:@"0"];
	NSString *string11 = [NSString stringWithString:@"1"];
	NSArray *set5 = [NSArray arrayWithObjects: string10, string11, nil];
	[set5 retain];
	
	NSString *string12 = [NSString stringWithString:@"0"];
	NSString *string13 = [NSString stringWithString:@"1"];
	NSArray *set6 = [NSArray arrayWithObjects: string12, string13, nil];
	[set6 retain];
	
	NSMutableArray *newDataSource = [[NSMutableArray alloc] initWithObjects: set5, set6, nil];
	
	NSArray *recSeqArray;
	
	NSRange seqRange;
	seqRange.location = 9;//Location here is based on array notation.  Zero indicates first sequence.
	seqRange.length = 6;//Length here is not in array notation.  Is number of sequences wanted.
	
//	THIS IS FOR -sequence:
	recSeqArray = [myRadix sequence:3];
	printf("One Sequence:  \n%s\n", [[recSeqArray description] cString] );
	[recSeqArray release];
	
//	THIS IS FOR -allSequences
	recSeqArray = [myRadix allSequences];
	printf("All Sequences:  \n%s\n", [[recSeqArray description] cString] );
	[recSeqArray release];

//  THIS IS FOR -sequencesInRange:
	recSeqArray = [myRadix sequencesInRange:seqRange];
	printf("A Range of Sequences:  \n%s\n", [[recSeqArray description] cString] );
	[recSeqArray release];
	
//  THIS IS FOR -reInitWithArray:, This gives capacity for real-time encryption to occur.
	[myRadix reInitWithArray:newDataSource];
	recSeqArray = [myRadix allSequences];
	printf("New Source -allSequences:  \n%s\n", [[recSeqArray description] cString] );
	[recSeqArray release];
	
	recSeqArray = [myRadix sequence:1];
	printf("One Sequence:  \n%s\n", [[recSeqArray description] cString] );
	[recSeqArray release];
	
	recSeqArray = [myRadix sequence:0];
	printf("One Sequence:  \n%s\n", [[recSeqArray description] cString] );
	[recSeqArray release];
	
	[newDataSource release];
	[myRadix release];
    [pool release];
    return 0;
}

 

[caveman_uk]

1) In your sequence: method you should autorelease the array before returning it. You wouldn't need the releases in main if you did. Also it's the convention - see below.

2) And in sequencesInRange. Sort out sequenceArray and the other (the one you return) by convention should be autoreleased (I know you release it in main but that's not the way it's done. All methods should return autoreleased objects unless they are copy or alloc). You actually keep allocing sequenceArray in a do...while. You are not releasing ANY of them (Actually you are...using the 'lastObject] release' rubbish. Could you make it less obvious what your code does? Why not do [sequenceArray release]?) You actually don't need to alloc anyway. You could use the [NSMutableArray array] method. It gives an autoreleased array. Don't do alloc unless you really have to.

3) In main you're leaking set5 and set6

More personal style stuff...

3) I'd probably make radixSet a class not a struct. It is slower and perhaps overkill but avoids all that -> and free rubbish. I just think a class would be more Cocoa-ey.

4) Don't call the method reInitWithArray.... it's confusing. If it's not a class initialiser don't use the word init in it's name.

5) What happens if someone calls -init on your Radix class. Your internal variables are undefined and you don't do any checking for this in your other methods. You should have a designated initialiser so if it's going to be your initWithSets: method then you should override init so that it calls initWithSets appropriately.

6) When you're creating the sets in main you could do rather

NSArray *set2 = [NSArray arrayWithObjects: @"0", @"1", nil];

rather than creating separate strings

7) You don't need to do the cString conversion for your printf's. You could use NSLog() and that accepts %@ formatters for Objective-C strings.


From the look of the code it looks a bit like when a C programmer learns Objective-C. There's a lot of ->, malloc and free going on. I have hardly ever used malloc or free in an objective-C program. You really should take a look at how you're using objects and how well you're sticking to the conventions of the language. Currently you're using alloc way too often and you're returning objects that aren't autoreleased. Doing both is making it more likely you will have memory leaks as you have to remember what's retained. If you use autoreleased objects you only have to retain the things you actually must retain. It's easier to remember to release a couple of objects than it is a dozen.

 

[robbieduncan]

1) In your sequence: method you should autorelease the array before returning it. You wouldn't need the releases in main if you did. Also it's the convention - see below.

Or use [NSMutableArray array] which returns an auto-released array instead of alloc/init.

 

[caveman_uk]

Or use [NSMutableArray array] which returns an auto-released array instead of alloc/init.

I think I mentioned that in 2)

BTW Jordan, I hope you don't think I'm being harsh with my comments. You did ask. There are other things but then I'd really be nitpicking.

 

[robbieduncan]

I think I mentioned that in 2)

Oops

 

[Jordan72]

1) In your sequence: method you should autorelease the array before returning it. You wouldn't need the releases in main if you did.

Isn't autoreleasing returned objects a class method convention? Along with it, there is always a version to have a class object return an object without autoreleasing it, which is -alloc, which leaves the init'ing up to an instance method. So, wouldn't this apply for instance methods that return objects? I mean the instance method may have one method that returns an autoreleased object and one that doesn't?

If I were to follow convention wouldn't these be my two init-type methods, when creating the object:

a class method,

-radixWithSets:

and the counterpart instance method (when -alloc is used),

-initWithSets:

But when Radix instances are assigned a new set, how do I write both versions, like this? I'm not sure how to go about that.

-replaceWithAutoreleasedSets:

and an instance method,

-replaceWithSets:

3) I'd probably make radixSet a class not a struct. It is slower and perhaps overkill but avoids all that -> and free rubbish. I just think a class would be more Cocoa-ey.

I did that at first, and it looked pretty, but pretty was slower.

 

[Jordan72]

BTW Jordan, I hope you don't think I'm being harsh with my comments. You did ask. There are other things but then I'd really be nitpicking.

It hard enough find people willing to talk about this beginner stuff, how could I complain about pickey?

 

[caveman_uk]

Isn't autoreleasing returned objects a class method convention?

No. There's loads of instance methods that return autoreleased objects. For example

- (NSString *)stringByAppendingString:(NSString *)aString

In fact the methods that do not return autoreleased objects are the exception (basically alloc and the various copy methods).

Along with it, there is always a version to have a class object return an object without autoreleasing it, which is -alloc, which leaves the init'ing up to an instance method. So, wouldn't this apply for instance methods that return objects? I mean the instance method may have one method that returns an autoreleased object and one that doesn't?

If you check the class documentation all the methods return autoreleased objects. There are not non-autoreleased versions. I'll repeat - The only methods that return non-autoreleased objects are alloc, copy, mutableCopy (and anything else copy related).

You don't need to make a class method that creates an autoreleased object. (Like [NSMutableArray array]) to match the alloc 'version'. You can if you want but it's optional. All you should do is override init if your class needs special initialisation.

I did that at first, and it looked pretty, but pretty was slower.

How do you know? I said it'd be slower but I seriously doubt you'd have noticed. Looking at what your struct actually does I reckon an NSMutableDictionary would be a good replacement. You could then store that in an NSMutableArray. There seem to be values in your struct you don't need to store - Radix and omegaElement seem to be invariant. They are just determined from the [count] of the array of the object stored in setPtr. You could determine these as you need them using

[[[sets objectAtIndex:i]objectForKey"setPtr"] count].

Actually do you need 'element' either? In which case don't even bother with a dictionary or copying stuff into another variable. Just retain the array that's passed when initing.

In general I think your design is making this an awful lot harder than it needs to be.

 

[Jordan72]

...The only methods that return non-autoreleased objects are alloc, copy, mutableCopy (and anything else copy related).

Okay. So I'm adding these two distictions to my memory list rules.

1. All instance methods that return objects return autoreleased objects.

2. Class methods return both autoreleased and non-autoreleased objects. The only class methods that do not return non-autoreleased objects are the ones with alloc, copy, mutablecopy or copy related.

I didn't know this about instance methods in general. Thanks.

How do you know? I said it'd be slower ... Radix and omegaElement seem to be invariant. They are just determined from the [count] of the array of the object stored in setPtr. You could determine these as you need them using

[[[sets objectAtIndex:i]objectForKey"setPtr"] count].

I wrote it with objects instead of structs before and no I haven't set up a timer to check for speed, but I'm basing the decision to go with a struct on this situation I had run into earlier:

for ( i=0; i<[someObj count]; i++ )
{
     [[someObj lastObject] release];
}

This proved to me that my program did things during a loop that were unneccesary. Why should I message, when I could cache an int for a condition in a loop? Especially if this loop is either a) iterated through many times or b) iterated through a few times, but called many times.

Actually do you need 'element' either? In which case don't even bother with a dictionary or copying stuff into another variable. Just retain the array that's passed when initing.

Element is absolutely neccessary. The element indicates the object of a set that forms a unique sequence. I.e., if each set was base ten, and I had three sets, there could be 1000 unique combinations of these objects (10 x 10 x 10 or 10 ^3). Element would be used to indicate each object of the set that forms that unique sequence.

To get to that sequence, I literally have to count. The only way to count in this situation I've found is to use comparison. If I compared objects, that would involved messaging everytime during the counting. But, if I use cached ints, then I avoid messaging in these cumbersome but neccessary parts of the implementation.

It has been really hard class to explain what I'm trying to accomplish with this class. This makes it harder to talk about the smaller issues.

 

[caveman_uk]

for ( i=0; i<[someObj count]; i++ )
{
     [[someObj lastObject] release];
}

What's wrong with [someObj removeAllObjects]? it would do exactly that. It's one line - one call.

 

[caveman_uk]

Element is absolutely neccessary. The element indicates the object of a set that forms a unique sequence. I.e., if each set was base ten, and I had three sets, there could be 1000 unique combinations of these objects (10 x 10 x 10 or 10 ^3). Element would be used to indicate each object of the set that forms that unique sequence.

Ok you need an array of ints to hold element(s). You don't need an array of structs. You need two arrays - the array of sets that's passed in (which you can retain or copy if need be...do you change the values of the sets? Does it matter?) and an array of the same dimensions that holds elements. See? Still no struct. No laborious free, malloc or -> stuff. Two simple arrays. The other two values in your struct are invariate. You could get those values by a simple -count when you need them. They don't need to be stored.

 

[caveman_uk]

Why should I message, when I could cache an int for a condition in a loop? Especially if this loop is either a) iterated through many times or b) iterated through a few times, but called many times.

Do you know how long objective-C messaging takes? It's about 50 CPU cycles per call. On a 1.5GHz Machine that's 30nanoseconds a call or 30 billionths of a second per message. Are you seriously saying you can notice? Unless you do a few million I doubt it.

I refer you to a post in another forum by Michael Ash of Rogue Amoeba link

The First Rule of Program Optimization: Don't do it.

The Second Rule of Program Optimization (for experts only!): Don't do it
yet.

In other words, implement your methods as you have done, and then forget
about things. Objective-C message sending overhead is not that high,
particularly considering what it does, but even when the extra capability
is less than necessary it's fast. It typically takes 50 CPU cycles, which
on my machine (1.5GHZ) is around 30 nanoseconds. If you should ever get to
the point where an extra 30 nanoseconds of call overhead is making your
stuff slow, then you could consider drastic action to improve the
situation, but I doubt you'll ever get to that point.

The bottom line is write your code to a good algorithm and make your code as readable and understandable as possible. Don't try to fix what you don't know is broke....unless you know what you're doing and Shark tells you it's a good idea.

 

[robbieduncan]

Do you know how long objective-C messaging takes? It's about 50 CPU cycles per call. On a 1.5GHz Machine that's 30nanoseconds a call or 30 billionths of a second per message. Are you seriously saying you can notice? Unless you do a few million I doubt it.

I refer you to a post in another forum by Michael Ash of Rogue Amoeba link

The bottom line is write your code to a good algorithm and make your code as readable and understandable as possible. Don't try to fix what you don't know is broke....unless you know what you're doing and Shark tells you it's a good idea.

Well said. I seem to remember a very similar discussion around here not that long ago. If Shark tells you that your Obj-C messaging is actually a problem you can always use IMPs to speed it up.

 

[Jordan72]

I get the impression you really are interested. That's okay. I can find others.

BTW, just to let you in on something, over optimization fallacy is a popular urban myth to justify laziness and make the herd think lazily, so the few experts who do actually do spend time with it are up above those who don't pay attention at all to it. Look at the next performance tests for software and you'll see who ignored optimization prematurely.

 

[caveman_uk]

BTW, just to let you in on something, over optimization fallacy is a popular urban myth to justify laziness and make the herd think lazily, so the few experts who do actually do spend time with it are up above those who don't pay attention at all to it. Look at the next performance tests for software and you'll see who ignored optimization prematurely.

I don't think newbies who are asking for help are really in a position to tell people who are trying to help them that they are wrong. You don't know enough about objective-C or the way it works to even begin to understand how to optimise a program. Even if you think you do, how do you know what needs optimising? Have you profiled your app?

Whilst you're busy optimising the crap out of stuff that doesn't need fixing, someone else will have their app out, running, in users hands and they will be giving their users new features. I'm not saying just put any old crap out and fix it later. Make sure your app is debugged, doesn't crash, doesn't leak memory and doesn't beachball. But sitting there trying to optimise stuff THAT DOESN'T NEED FIXING doesn't help you or anyone else (other than making you feel clever when in truth no-one really cares).

 

[Catfish_Man]

I get the impression you really are interested. That's okay. I can find others.

BTW, just to let you in on something, over optimization fallacy is a popular urban myth to justify laziness and make the herd think lazily, so the few experts who do actually do spend time with it are up above those who don't pay attention at all to it. Look at the next performance tests for software and you'll see who ignored optimization prematurely.

/me wonders when Donald Knuth started spreading urban myths about programming.

Reference.

 

[Jordan72]

If you actually took the time to think about what I was attempting there, you'd realize that its sole purpose was to create every, I repeat every possible combination within dynamic parameters.

I think that's a root toot'n candidate for optimization if there ever was one. So there!

La la la la la la, I can't hear you.

 

[caveman_uk]

Whatever.

If it keeps you happy then great, carry on. It's your time you're wasting. I'm not going to waste any more of mine trying to help you.