I have a NSMutableArray oldArray. Now, at one point, this NSMutableArray object gets updated with another NSMutableArray, which may have more, less or same number of elements as the previous NSMutableArray.
I want to compare the old and the new array for changes. What I want are two NSArrays addedArray and removedArray which will contain the indices of the elements which have been added and/or removed from the old array.
This whole problem will be more clear with an example :
oldArray = {@"a",@"b",@"d",@"e",@"g"};
newArray = {@"a",@"c",@"d",@"e",@"f",@"h"};
So, here the removed objects are @"b" and @"g" at indices 1 and 4 respectively. And the objects added are @"c", @"f" and @"h" at indices 1, 4 and 5 (first objects are removed, then added).
Therefore,
removedArray = {1,4}; and addedArray = {1,4,5};
I want an efficient way to get these two arrays - removedArray and addedArray from the old and new NSMutableArray. Thanks! If the problem is not very understandable, I'm willing to provide more information.
Edit 1
Perhaps it will be more clear if I explain what I want to use this for.
Actually what I am using this for is updating a UITableView with methods insertRowsAtIndexPaths and removeRowsAtIndexPaths with animation after the tableview gets loaded, so that the user can see the removed rows go out and the new rows come in. The tableview stores the Favourites elements which the user can add or remove. So after adding some favorites and removing some; when the user comes back to the favourites tableview, the animations will be shown.
Edit 2
Should have mentioned this earlier, but the elements in both the old and the new array will be in an ascending order. Only the indices of the removal or addition matters. The order cannot be changed. ex. {@"b",@"a",@"c",@"d"} cannot be an array.
I have tried iterating through the old and the new arrays using loops and if conditions, but is it getting really messy and buggy.
This is not a simple problem. First, note that it may have multiple solutions:
a b c d
b c d e
both (a={0, 1, 2, 3}, r={0, 1, 2, 3}) and (a={3}, r={0}) are valid solutions. What you are probably looking for is a minimal solution.
One way to get a minimal solution is by finding the Longest Common Subsequence (LCS) of the two sequences. The algorithm for finding LCS will tell you which elements of the two sequences belong to the LCS, and which do not. Indexes of each element of the original array that is not in LCS go into the removed array; indexes of elements of the new array that are not in LCS go into the added array.
Here are a few examples (I parenthesized the elements of LCS):
0 1 2 3 4 5
(a) b (d) (e) g
(a) c (d) (e) f h
The items of old not in LCS are 1 and 4; the items of new 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.