NSArray: Remove objects with duplicate properties

Question

I have an NSMutableArray that contains a few custom objects. Two of the objects have the same properties such as title and author. I want to remove the duplicate object and leave the other.

Asset *asset;
NSMutableArray *items = [[[NSMutableArray alloc] init] autorelease];

// First
asset = [[Asset alloc] init];
asset.title = @"Developer";
asset.author = @"John Smith";
[items addObject:asset];
[asset release];

// Second
asset = [[Asset alloc] init];
asset.title = @"Writer";
asset.author = @"Steve Johnson";
[items addObject:asset];
[asset release];

// Third
asset = [[Asset alloc] init];
asset.title = @"Developer";
asset.author = @"John Smith";
[items addObject:asset];
[asset release];

Since they are NOT the same object, but only having duplicate properties, how can I remove the duplicate?

Answer 1

First, I'd override the isEqual: method for Asset like this:

-(BOOL)isEqual:(Asset *)otherAsset {
    return [self.title isEqual:otherAsset.title] && [self.author isEqual:otherAsset.author];
}

Then, if you want to avoid placing duplicates in the array in the first place:

NSUInteger idx = [items indexOfObject:asset];  // tests objects for equality using isEqual:
if (idx == NSNotFound) [items addObject:asset];

If the array already contains duplicates, then any algorithm that finds them has a run time already worse than linear, but I think creating a new array and only adding unique elements like above is the best algorithm. Something like this:

NSMutableArray *itemsWithUniqueElements = [NSMutableArray arrayWithCapacity:[items count]];

for (Asset *anAsset in items) {
    if ([items indexOfObject:anAsset] == NSNotFound)
        [itemsWithUniqueElements addObject:anAsset];
}

[items release];
items = [itemsWithUniqueElements retain];

In the worst case scenario (all elements are already unique) the number of iterations is:

1 + 2 + 3 + ... + n =  n * (n+1) / 2

Which is still O(n^2) but is slightly better than @Justin Meiners' algorithm. No offense! :)

Answer 2

If you'd like your custom NSObject subclasses to be considered equal when their names are equal you may implement isEqual: and hash. This will allow you to add of the objects to an NSSet/NSMutableSet (a set of distinct objects).

You may then easily create a sorted NSArray by using NSSet's sortedArrayUsingDescriptors:method.

MikeAsh wrote a pretty solid piece about implementing custom equality: Friday Q&A 2010-06-18: Implementing Equality and Hashing

Answer 3

You could create a HashSet and as you loop, you could add "title+author" concatenated set to the HashSet (NSMutableSet). As you arrive at each item, if the HashSet contains your key, either remove it or don't copy (either deleting or creating a copy without duplicates).

That makes it order n (1 loop)

Here's the NSMutableSet class:

http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Classes/NSMutableSet_Class/Reference/NSMutableSet.html#//apple_ref/occ/cl/NSMutableSet

EDIT with code:

The meat of the code is the one loop.

void print(NSMutableArray *assets)
{
    for (Asset *asset in assets)
    {
        NSLog(@"%@/%@", [asset title], [asset author]);
    }
}

int main (int argc, const char * argv[])
{

    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

    //
    // Create the initial data set
    //
    Asset *asset;
    NSMutableArray *items = [[[NSMutableArray alloc] init] autorelease];

    // First
    asset = [[Asset alloc] init];
    asset.title = @"Developer";
    asset.author = @"John Smith";
    [items addObject:asset];
    [asset release];

    // Second
    asset = [[Asset alloc] init];
    asset.title = @"Writer";
    asset.author = @"Steve Johnson";
    [items addObject:asset];
    [asset release];

    // Third
    asset = [[Asset alloc] init];
    asset.title = @"Developer";
    asset.author = @"John Smith";
    [items addObject:asset];
    [asset release];

    NSLog(@"****Original****");
    print(items);

    //
    // filter the data set in one pass
    //
    NSMutableSet *lookup = [[NSMutableSet alloc] init];
    for (int index = 0; index < [items count]; index++)
    {
        Asset *curr = [items objectAtIndex:index];
        NSString *identifier = [NSString stringWithFormat:@"%@/%@", [curr title], [curr author]];

        // this is very fast constant time lookup in a hash table
        if ([lookup containsObject:identifier])
        {
            NSLog(@"item already exists.  removing: %@ at index %d", identifier, index);
            [items removeObjectAtIndex:index];
        }
        else
        {
            NSLog(@"distinct item.  keeping %@ at index %d", identifier, index);
            [lookup addObject:identifier];
        }
    }

    NSLog(@"****Filtered****");
    print(items);

    [pool drain];
    return 0;
}

Here's the output:

Craplet[11991:707] ****Original****
Craplet[11991:707] Developer/John Smith
Craplet[11991:707] Writer/Steve Johnson
Craplet[11991:707] Developer/John Smith
Craplet[11991:707] distinct item.  keeping Developer/John Smith at index 0
Craplet[11991:707] distinct item.  keeping Writer/Steve Johnson at index 1
Craplet[11991:707] item already exists.  removing: Developer/John Smith at index 2
Craplet[11991:707] ****Filtered****
Craplet[11991:707] Developer/John Smith
Craplet[11991:707] Writer/Steve Johnson

Answer 4

You can use the uniqueness of an NSSet to get distinct items from your original array. If you have the source code for Assest you will need to override the hash and isEqual: method on the Asset class.

@interface Asset : NSObject
@property(copy) NSString *title, *author;
@end

@implementation Asset
@synthesize title, author;

-(NSUInteger)hash
{
    NSUInteger prime = 31;
    NSUInteger result = 1;

    result = prime * result + [self.title hash];
    result = prime * result + [self.author hash];

    return result;
}

-(BOOL)isEqual:(id)object
{
    return [self.title isEqualToString:[object title]] && 
    [self.author isEqualToString:[object author]];
}

- (void)dealloc {
    [title release];
    [author release];
    [super dealloc];
}

@end

Then to implement:

Asset *asset;
NSMutableArray *items = [[[NSMutableArray alloc] init] autorelease];

// First
asset = [[Asset alloc] init];
asset.title = @"Developer";
asset.author = @"John Smith";
[items addObject:asset];
[asset release];

// Second
asset = [[Asset alloc] init];
asset.title = @"Writer";
asset.author = @"Steve Johnson";
[items addObject:asset];
[asset release];

// Third
asset = [[Asset alloc] init];
asset.title = @"Developer";
asset.author = @"John Smith";
[items addObject:asset];
[asset release];

NSLog(@"Items: %@", items);

NSSet *distinctItems = [NSSet setWithArray:items];

NSLog(@"Distinct: %@", distinctItems);

And if you need an array at the end you can just call [distinctItems allObjects]

Answer 5

This is one way you could do it :

NSMutableArray* toRemove = [NSMutableArray array];

    for (Asset* asset1 in items)
    {
        for (Asset* asset2 in items)
        {
            if (asset1 != asset2)
            {
                if ([asset1.title isEqualToString:asset2.title] && [asset1.author isEqualToString:asset2.author])
                {
                    [toRemove addObject:asset2];
                }
            }
        }
    }

    for (Asset* deleted in toRemove)
    {
        [items removeObject:toRemove];
    }