filter duplicate from NSArray using object property

Question

I have an NSArray which contains list of Order objects, an Order object has three properties ( id, typeID and description), I want to filter my array based on typeID to exclude duplicates. Duplicates are determined by typeID e.g if there are 2 items with typeID=7 then I want to pick the Order which has the max id so in this case it would be => id=2.

My src Array with Order objects:

Item 1: id=1, typeID=7, description="some text 1"
Item 2: id=2, typeID=7, description="some text 2"
Item 3: id=3, typeID=5, description="some text 3"
Item 4: id=4, typeID=5, description="some text 4"
Item 5: id=5, typeID=8, description="some text 5"

After applying filter my returned array should look likefollowing:

Item 2: id=2, typeID=7, description="some text 2"
Item 4: id=4, typeID=5, description="some text 4"
Item 5: id=5, typeID=8, description="some text 5"

Can someone suggest what would be the best way to do this, thanks.

Answer 1

I used a method using NSSet's non duplicate power.

Here is the code

I used + method here because you can use this method in any shared class and access it in any class you want.

+ (NSArray *)removeDuplicateEntriesFromArray:(NSArray *)array basedOnKey:(NSString *)key{
NSMutableArray *newArray = [NSMutableArray new];
//get array containing all the keys.
NSArray *keysArray = [array valueForKey:key];
//putting these keys into a set which will remove duplicate keys
NSSet *noDuplicateKeys = [[NSSet alloc]initWithArray:keysArray];

for (NSString *currentKey in noDuplicateKeys) {
    //Now searching objects with all the keys available in the set and putting those objects into newArray.
    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"%K == %@",key ,currentKey];
    NSArray *allObjectsWithKey = [array filteredArrayUsingPredicate:predicate];
    [newArray addObject:[allObjectsWithKey firstObject]];
}
return [newArray copy];
}

Answer 2

I think the most effective way is to use NSDictionary to store the object as value and the property value as key, and before adding any object to the dictionary you check if it exist or not which is O(1) operation, i.e. the whole process will take O(n)

Here is the code

- (NSArray *)removeDuplicatesFromArray:(NSArray *)array onProperty:(NSString *)propertyName {
    NSMutableDictionary *dictionary = [[NSMutableDictionary alloc] init];

    for (int i=0; i<array.count; i++) {

        NSManagedObject *currentItem = array[i];
        NSString *propertyValue = [currentItem valueForKey:propertyName];

        if ([dictionary valueForKey:propertyValue] == nil) {
            [dictionary setValue:currentItem forKey:propertyValue];
        }
    }

    NSArray *uniqueItems = [dictionary allValues];

    return uniqueItems;
}

Answer 3

First of all thank you all for all your tips, this is how I was able to solve my problem:

-( NSArray *) filterOutDuplicateOrder: (NSArray *)unFilteredArray
{

    // First sort array by descending so I could capture the max id
    NSSortDescriptor *descriptor = [[NSSortDescriptor alloc] initWithKey:@"itemID" ascending:NO];
    NSArray *sortedDescArray = [unFilteredArray sortedArrayUsingDescriptors:[NSArray arrayWithObjects:descriptor,nil]];
    
    // Filter out duplicates using typeID
    NSMutableArray *filteredArrayOfObjects = [[NSMutableArray alloc] init];
    for (Order *order in sortedDescArray)
    {
        if(!([[filteredArrayOfObjects valueForKeyPath:@"typeID"] containsObject:order.typeID]))
        {
            [filteredArrayOfObjects addObject:progressNote];
        }
    }    
    return resultArray;
}

Answer 4

Method One:

- (NSIndexSet *)indexesOfObjectsPassingTest:(BOOL (^)(id obj, NSUInteger idx, BOOL *stop))predicate

I'm thinking something like:

__block NSMutableSet *uniqueTypeIDs = [NSMutableSet set];
NSIndexSet *set = [myArrayOfObjects indexesOfObjectsPassingTest:^BOOL(id object, NSUInteger idx, BOOL *stop) {
    if([uniqueTypeIDs containsObject:[NSNumber numberWithInt:object.typeID]]) {
        return NO;
    } else {
        [uniqueTypeIDs addObject:[NSNumber numberWithInt:object.typeID]];
        return YES;
    }
}];

Do your typeIDs require conversion to NSNumber? You decide. The returned NSIndexSet will contain the indexes of all objects that pass the test. Then you can act on those objects, or remove them from your array.

Method Two:

Alternatively use a NSSet. If your objects are really unique then turn the array into a set and then back into an array - that's the easiest way to lose duplicate objects.

NSSet *set = [NSSet setWithArray:array];

makes the set, comprised of unique objects

[set allObjects];

gives you an array of all objects in the set

Method Three:

Another way is to use a NSMutableDictionary using type ID as key; iterate over the array, and use the typeID (turned into NSNumber) as key to store indexes. If you find the key already exists in the dictionary don't add it again. The result is a dictionary that contains indexes of unique objects in the original array.

Answer 5

Naturally if we read "filter duplicates" we think of sets ans filter operation. But this would be hairy in this case, as the duplicates aren't really duplicates and NSSet won't give us the opportunity to decide which item to prefer.

I choose to first segment the items for its typeID, pick the first object in every segment and than order them for its ids.

pre work

I use this Item class:

@interface Item : NSObject
@property NSInteger itemID;
@property NSInteger typeID;
@property(copy) NSString *itemDescription;
@end

@implementation Item

-(NSString *)description
{
    return [NSString stringWithFormat:@"Item: %li, typeID: %li, description: %@", (long)self.itemID, (long)self.typeID, self.itemDescription];
}
@end

Note, that id and description are rather bad property names.

I use this code to create a list of items:

NSArray *data =@[ @{@"itemID": @1, @"typeID": @7, @"description": @"some text 1"},
                  @{@"itemID": @2, @"typeID": @7, @"description": @"some text 2"},
                  @{@"itemID": @3, @"typeID": @5, @"description": @"some text 3"},
                  @{@"itemID": @4, @"typeID": @5, @"description": @"some text 4"},
                  @{@"itemID": @5, @"typeID": @8, @"description": @"some text 5"}];

NSMutableArray *items = [@[ ] mutableCopy];


[data enumerateObjectsUsingBlock:^(NSDictionary *obj, NSUInteger idx, BOOL *stop) {
    [items addObject:({
        Item *item = [[Item alloc] init];
        item.itemID = [obj[@"itemID"] integerValue];
        item.typeID = [obj[@"typeID"] integerValue];
        item.itemDescription = obj[@"description"];
        item;
    })];
}];

This should be all code that you have in a similar way. or you don't need it.

the answer

I create a dictionary with the typeIDs as keys. as values I add and fill mutable arrays:

NSMutableDictionary *itemsByType = [@{} mutableCopy];

[items enumerateObjectsUsingBlock:^(Item *item, NSUInteger idx, BOOL *stop) {
    id key = @(item.typeID);
    if (![[itemsByType allKeys] containsObject:key]) {
        itemsByType[key] = [@[] mutableCopy];
    }
    [itemsByType[key] addObject:item];
}];
    

Now I sort each of this mutable arrays:

[itemsByType enumerateKeysAndObjectsUsingBlock:^(id key, NSMutableArray *items, BOOL *stop) {
    [items sortUsingComparator:^NSComparisonResult(Item *item1, Item *item2) {
        return item1.itemID < item2.itemID;
    }];
}];

and put every first object for each array to the results:

NSMutableArray *resultArray = [@[] mutableCopy];
[[itemsByType allKeys]  enumerateObjectsUsingBlock:^(id key, NSUInteger idx, BOOL *stop) {
    [resultArray addObject:itemsByType[key][0]];
}];

Now I sort the results by the itemID

[resultArray sortUsingComparator:^NSComparisonResult(Item *item1, Item *item2){
    return item1.itemID > item2.itemID;
}];

The result:

NSLog(@"%@", resultArray);

prints

(
    "Item: 2, typeID: 7, description: some text 2",
    "Item: 4, typeID: 5, description: some text 4",
    "Item: 5, typeID: 8, description: some text 5"
)

---

The source code of my test program: gist

---

an alternative could be sorting for typeID ascending and for itemID descending. Than loop the items and take each first item for an unseen type id. Sort the result for typeID.

[items sortUsingDescriptors:@[[[NSSortDescriptor alloc] initWithKey:@"typeID" ascending:YES],
                              [[NSSortDescriptor alloc] initWithKey:@"itemID" ascending:NO]
                              ]];

NSInteger lastestTypeID = -1;

NSMutableArray *result = [@[] mutableCopy];

for (Item *item in items) {
    if (item.typeID > lastestTypeID) {
        lastestTypeID = item.typeID;
        [result addObject:item];
    }
}

[result sortUsingComparator:^NSComparisonResult(Item *obj1, Item *obj2) {
    return obj1.itemID > obj2.itemID;
}];

Answer 6

There was no reason to downvote Adam's answer. Also the first method given by him can probably be made more concise this way.

__block NSMutableSet *uniqueTypeIDs = [NSMutableSet set];    
NSMutableArray *myFilteredArrayOfObjects = [NSMutableArray new];

[myArrayOfObjects indexesOfObjectsPassingTest:^BOOL(id object, NSUInteger idx, BOOL *stop) {
if([uniqueTypeIDs containsObject:[NSNumber numberWithInt:object.typeID]]) {
    return NO;
} else {
    [uniqueTypeIDs addObject:[NSNumber numberWithInt:object.typeID]];
    [myFilteredArrayOfObjects addObject:object];
    return YES;
}
}];

Edit - Or even this can be a way. (Haven't tried it though.)

NSMutableArray *myFilteredArrayOfObjects = [NSMutableArray new];

[myArrayOfObjects indexesOfObjectsPassingTest:^BOOL(id object, NSUInteger idx, BOOL *stop) {
if([[myFilteredArrayOfObjects valueForKeyPath:@"typeID"] containsObject:object.typeID]) {
    return NO;
} else {
    [myFilteredArrayOfObjects addObject:object];
    return YES;
}
}];

Answer 7

Use a sorting method first (perhaps generating a separate copy) to make sure that you are sorted first by typeID, then by id in reverse like this:

id=4, typeID=5, description="some text 4"
id=3, typeID=5, description="some text 3"
id=2, typeID=7, description="some text 2"
id=1, typeID=7, description="some text 1"
id=5, typeID=8, description="some text 5"

Now walk the resulting array in order, keeping track of the typeID as you go. You are guaranteed that if the typeID is different from that of the previous item (or this is the first item), this one goes into your result array (the starred items are the ones):

id=4, typeID=5, description="some text 4" *
id=3, typeID=5, description="some text 3"
id=2, typeID=7, description="some text 2" *
id=1, typeID=7, description="some text 1"
id=5, typeID=8, description="some text 5" *