Finding first available integer in an array, translated from ASOC…

[fiz]

Hello,

Simple problem but I’m really tired: I have to find the first unattributed integer number into a NSArray. In ASOC I did this:

	set testID to 1
	set alreadyDefined to myController's arrangedObjects's valueForKey_("ID") as list
	repeat while testID is in alreadyDefined
			set testID to testID + 1
	end repeat

When it comes to Objective-C, I suddenly feel stupid. I know that this ASOC code will be transformed into C, but how? The first two lines are obvious:

	int testID =1;

or maybe better:

	NSNumber *testID = [NSNumber numberWithInt: 1];

then
NSArray *alreadyDefined = [NSArray arrayWithArray: [myController arrangedObjects]valueForKey:@“ID”]];

The values for the key “ID” are “legal” integer NSNumbers. Then what? There is no:

	while (testID in alreadyDefined)

in ObjC. More, it seems this is the sort of things I would prefer to code in rough C
but here I’m really lost.

Maybe a link to solve this without using Predicates?

Thank you!

EDIT : I found this:
int lowest = 1; // or zero

NSArray *tempArray = [array sortedArrayUsingSelector:@selector(compare:)];

for (NSNumber *number in tempArray)
{
if ([number intValue] == lowest)
{
lowest = [number intValue] + 1;
}
}

I’ll give it a try.

[StefanK]

@fiz

There is no:

	while (testID in alreadyDefined)

in ObjC.

There is “yes”:

 int testID = 1;
    while ([alreadyDefined containsObject:[NSNumber numberWithInt:testID]]) {
        testID++;
    }
    NSLog(@"%d", testID);

[fiz]

Thank you Stefan, the other solution is working too, but as I don’t like “for” loops very much (except for fast enumeration), I’ll use yours. And I like this combination of cocoa’s methods and basic C incrementation

EDIT : Single question : if you wanted to manage memory yourself, would you have to dealloc “by hand” all the NSNumbers created into the while loop? Imagine if this array counted 120’000 items.

[StefanK]

Objective-C is a superset of C, so C is always present

[StefanK]

@fiz

EDIT : Single question : if you wanted to manage memory yourself, would you have to dealloc “by hand” all the NSNumbers created into the while loop? Imagine if this array counted 120’000 items.

No, the principal rule of memory management is:
You are responsible for releasing the object after creating it with alloc/init, copy or new.
You are not responsible for convenience methods like [NS With. ]

However with an array of 120’000 items I’d use memory optimized code

[DJ_Bazzie_Wazzie]

@fiz

EDIT : Single question : if you wanted to manage memory yourself, would you have to dealloc “by hand” all the NSNumbers created into the while loop? Imagine if this array counted 120’000 items.

If you think that there is a possibility of 120,000 items in the list then looping inside a looping (120,000 X 120,000 times max) is much to heavy code. Contains object has also a for loop until it find the first occurrence of the object you’re looking for. So get rid of all the overhead and use something as below.

int highestValue = 0;
for (NSNumber *identifier in alreadyDefined) {
if ([identifier intValue] > highestValue)
highestValue = [identifier intValue];
}

[StefanK]

@DJ Bazzie Wazzie

int highestValue = 0;
for (NSNumber *identifier in alreadyDefined) {
if ([identifier intValue] > highestValue)
highestValue = [identifier intValue];
}

hm, I don’t see the advantage. Your “overheadless” solution iterates always [alreadyDefined count] times.
The “containsObject” iterates until it reaches the first unused value.
That could be a tremendous time saving

[DJ_Bazzie_Wazzie]

@StefanK

hm, I don’t see the advantage. Your “overheadless” solution iterates always [alreadyDefined count] times.
The “containsObject” iterates until it reaches the first unused value.

Well simple example… you have a list of 250 random number but only the first free number is 100. With the double iterations, like in your example, it would take an avarage of 12,500 iterations while mine still takes only 250. Then when you have an ordered list you could bring back the iterations only to 5050. Stefan’s example would only be be faster when the first available number is lower than 22 and the list is sorted (and contains 250 items). imagine that with a list of 120,000 items; it can go up to billions of iterations and the first available number needs to be lower than 500.

Another pro is that I don’t need memory management because I don’t create and destroy objects (which I don’t need)

[Shane_Stanley]

Bernard,

Here’s another approach:

    array = [array sortedArrayUsingSelector:@selector(compare:)];
    __block NSUInteger theValue = [[array objectAtIndex:0] intValue];
    [array enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        NSUInteger temp = [obj intValue];
        if (temp > (theValue + 1)) {
            *stop = YES;
        } else {
            theValue = temp;
        }
    }];
    NSLog(@"first missing int: %lu", ++theValue);

For ARC, you may have to insert an “array = nil;” in the block.

[fiz]

Well. That’s much more than I expected! First of all, I’d like to thank everyone of you for these detailed explanations. This single problem may be solved in four different ways. I shouldn’t have talk about these 120000 items, it was not a question about efficiency, but more a memory management question.

Shane, I don’t understand this enumerateObjectsUsingBlock method. The “block” is (as I guess) a compound statement, using only three variables (the object, the index and the “stop” boolean). Is it useful to make better tests on each object as a predicate? Is it faster than a fast enumeration with an IF test inside? And makeObjectsPerformSelector makes every object of an array to receive a message, with no parameters?

That makes a lot of customizable actions to perform on an array – but of course arrays are probably one of the most used structures in a program.

Once again, thank you. I’m really impressed.

Regards,

[DJ_Bazzie_Wazzie]

@fiz

Shane, I don’t understand this enumerateObjectsUsingBlock method.

A block is like a function pointer in C but is stored in the stack of it’s runtime. Blocks have also access to late binding material which is a big plus because they are stored at runtime unlike pieces of executable memory like lambdas.

@fiz

Is it useful to make better tests on each object as a predicate?

if statements on integer values aren’t really CPU intensive unlike object comparisons.

@fiz

Is it faster than a fast enumeration with an IF test inside?

Blocks can be faster with dictionaries than fast enumerations, with arrays the difference isn’t noticeable. Blocks is a developer’s preference. Blocks are more used to save development time when this actions needs to be done on many different arrays. Then you define the block else were and can simply imply them on every array you like.

@fiz

And makeObjectsPerformSelector makes every object of an array to receive a message, with no parameters?

There is an makeObjectsPerformSelector:withObject: as well so you can pass an object to every iteration.

[Shane_Stanley]

Blocks are more used to save development time

I don’t know where they are more used, but they are certainly also useful for other things. And they’re required for the non-deprecated methods for showing save/open panels as sheets, so they’re worth knowing about.

Bernard, you might find this interesting: macresearch.org/cocoa-scientists-xxxii-10-uses-blocks-cobjective-c

[fiz]

Interesting indeed, Shane:

Another example of where Cocoa developers have traditionally had to operate with callbacks is the very common task of displaying a save or open panel. With blocks, there are no complex delegate methods, and the code you want executed on completion is right in front of you.

So I’m not alone to find these 3-methods (show window, remove it and execute) for showing a simple dialog a bit complicated. it’s a real relief. There is just to understand how these useful blocks really work.

[DJ_Bazzie_Wazzie]

@Shane Stanley

Blocks are more used to save development time

I don’t know where they are more used, but they are certainly also useful for other things.

You’re right: I meant in the context that blocks are more used over fast enumeration because of saving development time (and programmer’s preference) than other reasons.

[DJ_Bazzie_Wazzie]

@fiz

So I’m not alone to find these 3-methods (show window, remove it and execute) for showing a simple dialog a bit complicated. it’s a real relief.

You still can use the 3-methods way, blocks allows you to make a simplified callback, but doesn’t remove any method.

@fiz

There is just to understand how these useful blocks really work.

Like I said, they work like C function pointers (i remember you said something having a C history) but are stored differently. Normally a function pointer is stored at compile time. That means the ‘block’'s executable code is loaded and stored into the memory. function pointers can’t make use of late bindings this way; you need at least a runtime to achieve that. Blocks are similar but are stored in the heap or stack which makes it possible to store blocks of executable code which can access late binded material too.

[fiz]

@DJ Bazzie Wazzie

function pointers can’t make use of late bindings this way; you need at least a runtime to achieve that. Blocks are similar but are stored in the heap or stack which makes it

So I could use binding loaded in IB but I couldn’t use any

[myObject bind:@“attributedString” toObject: cardArrayController withKeyPath: @“selection.theText” options: nil];

for example, because my block wouldn’t be aware of the change. Do I understand correctly?

blocks allows you to make a simplified callback

The given example shows just how to avoid related code to be broken into separate handlers – this seems to be clearer, not particularly more efficient.

[Shane_Stanley]

@DJ Bazzie Wazzie

saving development time (and programmer’s preference)

Right. I’m a big fan of blocks with operation queues, where addOperationWithBlock: seems so convenient.