NSSet -member to verify NSValue equality

Question

I have an NSSet containing many thousands of NSValue objects (wrapping CGPoints ). I would very quickly find out if a CGPoint value CGPoint in an NSSet . It seems to me that the member: NSSet method can do the job here, except that it checks for equality using isEqual: NSValue objects use isEqualToValue: so when executing the code:

 [mySet member:valueToCheck]; 

this actually causes Xcode to crash.

1) Is there a way to use custom equality checking to make this work for NSValue objects?

2) Is this even the best approach (i.e. member: fast enough)? The scenario is that I have an NSSet containing a large number of dots displaying pixels on the screen (iPad). Later, I need to bombard this set with many thousands of dots per second to see if they exist in the set. My approach seems rude to achieve this. I was thinking of creating something like a huge two-dimensional bitmap, with each index representing a pixel on the screen. As soon as I know what I'm testing for, I can just go straight to that point of the array and check 1 or 0 ... does this sound better or worse?

thanks

Answer 1

Can you get this in a simple reproducible case? For example, I just tried:

 NSValue *v = [NSValue valueWithCGPoint:CGPointMake(1, 1)]; NSSet *s = [NSSet setWithObject:v]; NSLog(@"%@", [s member:[NSValue valueWithCGPoint:CGPointMake(1, 1)]]); 

But everything works fine.

change

-isEqual: no problem:

 NSValue *v1 = [NSValue valueWithPoint:NSMakePoint(1, 1)]; NSValue *v2 = [NSValue valueWithPoint:NSMakePoint(1, 1)]; NSLog(@"%d", [v1 isEqual:v2]); //logs "1" 

-hash not a problem:

 NSLog(@"%d", ([v1 hash] == [v2 hash])); //logs "1" 

These are different objects:

 NSLog(@"%d", (v1 != v2)); //logs "1" 

The problem is in the code. Try to clean and restore.

Answer 2

Answer no. 2:

I don’t know how NSSet is implemented internally, but considering that you know that you store points (with X and Y), I think you will be better off implementing your own partitioning algorithm. Personally, I would choose my own implementation over NSSet if you say that you have thousands of points.

Storing huge two-dimensional arrays for each pixel is likely to be the fastest way, but it will kill you in terms of memory consumption. You need something quick, but also easy.

There are many algorithms, and you can find them by searching for “spatial separation algorithms” on Wikipedia or Google. It also depends on your programming skills and how much time you are willing to invest in it.

For example, it would be quite simple to implement a quad-tree in which you begin to immerse your screen (or area) in 4 equal parts. Then, if and where necessary, you divide this particular cell into 4 parts as well. And you do this until each cell contains a sufficiently small number of points so that you can check all these errors. You can find a very good description on the wiki: http://en.wikipedia.org/wiki/Quadtree

Hope this helps,

Answer 3

[mySet member:valueToCheck] should not crash. NSValue isEqual: works fine when I try it here, and actually, probably calls isEqualToValue: when it is assigned a different NSValue for comparison. Is valueToCheck really NSValue, or is it CGPoint?

Cannot override default hash settings and comparison methods for NSSet. But NSSet seamlessly connects to CFSetRef , and you can easily specify your own hashing and comparison methods:

 CFSetCallBacks callbacks = kCFTypeSetCallBacks; callbacks.equal = customEqualFunction; callbacks.hash = customHashFunction; NSMutableSet *set = (NSMutableSet *)CFSetCreateMutable(NULL, 0, &callbacks); 

The restrictions on these functions are apparently the same as in the NSObject hash and isEqual: methods, all that is equal should have the same hash. C-style prototypes for customEqualFunction and customHashFunction described here and.

Answer 4

One solution would be to subclass NSSet and override member: to make its own comparison. Then your own comparison may be a simple call to isEqualToValue: See subclass notes in the NSSet documentation .

Another approach would be to add a category to NSValue that implements isEqual: . In this case, I would prefer a subclass, because it is a more limited solution.

Answer 5

This is not just a problem with -isEqual: you may also have a problem with the - hash method. If you want to use NSSet, you probably should create your own class that wraps CGPoint. -isEqual: then trivial, and -hash can be implemented using some method of combining bits of both coordinates, and then treating them as NSUInteger.

You will also want to implement the NSCopying protocol, which is also trivial if your points are immutable (just save and return self to -copyWithZone: .