Defining NSArray / NSMutableArray Change Indices

Question

I have an NSMutableArray oldArray . Now, at some point, this NSMutableArray updated with another NSMutableArray , which may have more, less, or the same number of elements than the previous NSMutableArray .

I want to compare old and new arrays with changes. I want two NSArray addedArray and removedArray that will contain the indices of the elements that were added and / or removed from the old array.

All this problem will be more clear on an example:

 oldArray = {@"a",@"b",@"d",@"e",@"g"}; newArray = {@"a",@"c",@"d",@"e",@"f",@"h"}; 

So, here the deleted objects are @ "b" and @ "g" at indices 1 and 4, respectively. Added objects @ "c", @ "f" and @ "h" at indices 1, 4 and 5 (the first objects are deleted and then added).

Thus,

 removedArray = {1,4}; and addedArray = {1,4,5}; 

I need an efficient way to get these two arrays - removedArray and addedArray from the old and new NSMutableArray . Thank you If the problem is not very clear, I am ready to provide additional information.

Change 1

It might be more clear if I explain what I want to use for this.

In fact, for this, I update the UITableView using the insertRowsAtIndexPaths and removeRowsAtIndexPaths with animation after the table loads, so that the user can see that the deleted rows are coming out and new rows appear. tableview stores Favorites that a user can add or remove. Therefore, after adding some favorites and deleting some; when the user returns to the favorites tableview, animations will be shown.

Edit 2

It should be mentioned earlier, but the elements of both the old and the new arrays will be in ascending order. Only deletion or addition rates are considered. Order cannot be changed. ex. {@ "b", @ "a", @ "c", @ "d"} cannot be an array.

Answer 1

I tried iterating over old and new arrays using loops and conditions, but it gets really messy and buggy.

This is not an easy problem. First, note that it can have several solutions:

 abcd bcde 

both (a={0, 1, 2, 3}, r={0, 1, 2, 3}) and (a={3}, r={0}) are feasible solutions. What you are probably looking for is a minimal solution.

One way to get a minimal solution is to find the Longest Common Subsequence (LCS) of two sequences. The LCS search algorithm will tell you which elements of the two sequences belong to LCS and which do not. The indices of each element of the original array that is not in LCS are included in the removed array; the indices of the elements of the new array that are not in LCS fall into the added array.

Here are some examples (I copied the LCS elements):

  0 1 2 3 4 5 (a) b (d) (e) g (a) c (d) (e) fh 

Non-LCS old elements are 1 and 4; new elements not in LCS are 1, 4, and 5.

Here is another example:

  0 1 2 3 a (b) (c) (d) (b) (c) (d) e 

Now added is 3 , and removed is 0 .

Answer 2

• addedArray = newArray ∖ (newArray ∩ oldArray)

    = newArray ∖ ({@"a",@"c",@"d",@"e",@"f",@"h"} ∩ {@"a",@"b",@"d",@"e",@"g"}) = newArray ∖ {@"a",@"d",@"e"} = {@"a",@"c",@"d",@"e",@"f",@"h"} ∖ {@"a",@"d",@"e"} = {@"c",@"f",@"h"} 

• deletedArray = oldArray ∖ (oldArray ∩ newArray)

    = oldArray ∖ ({@"a",@"b",@"d",@"e",@"g"} ∩ {@"a",@"c",@"d",@"e",@"f",@"h"}) = oldArray ∖ {@"a",@"d",@"e"} = {@"a",@"b",@"d",@"e",@"g"} ∖ {@"a",@"d",@"e"} = {@"b",@"g"} 

To find the intersections of the array, you can look at the following SO entry: Search for the intersection NSMutableArrays

Answer 3

If both arrays are already sorted in ascending order, you can find the added and deleted elements with one cycle over both arrays (using two independent pointers in the array):

 NSArray *oldArray = @[@"a",@"b",@"d",@"e",@"g"]; NSArray *newArray = @[@"a",@"c",@"d",@"e",@"f",@"h"]; NSMutableArray *removedArray = [NSMutableArray array]; NSMutableArray *addedArray = [NSMutableArray array]; NSUInteger iold = 0; // index into oldArray NSUInteger inew = 0; // index into newArray while (iold < [oldArray count] && inew < [newArray count]) { // Compare "current" element of old and new array: NSComparisonResult c = [oldArray[iold] compare:newArray[inew]]; if (c == NSOrderedAscending) { // oldArray[iold] has been removed [removedArray addObject:@(iold)]; iold++; } else if (c == NSOrderedDescending) { // newArray[inew] has been added [addedArray addObject:@(inew)]; inew++; } else { // oldArray[iold] == newArray[inew] iold++, inew++; } } // Process remaining elements of old array: while (iold < [oldArray count]) { [removedArray addObject:@(iold)]; iold++; } // Process remaining elements of new array: while (inew < [newArray count]) { [addedArray addObject:@(inew)]; inew++; } NSLog(@"removed: %@", removedArray); NSLog(@"added: %@", addedArray); 

Output:

  removed: (
     one,
     4
 )
 added: (
     one,
     4,
     5
 )