1

Is there an efficient way to reorder NSMutableArray by changing its starting index? Example: if my array is [A,B,C,D,E], I would like to set 3rd element as starting element, and thus create the array [C,D,E,A,B]. I am doing it by slicing the array into two separate array, and then concatenating them. Is there a more efficient or clean way to do this?

Edit: the following is my current code

NSArray myArray = [self getMyArray]; // [A,B,C,D]
int startingIndex = 2; 
NSArray *subArray1 = [myArray subarrayWithRange:NSMakeRange(_startingIndex, [myArray count] - _startingIndex + 1)]; // [C,D]
NSArray *subArray2 = [myArray subarrayWithRange:NSMakeRange(0, _startingIndex - 1)]; //[A,B]
NSMutableArray *reorderedArray = [NSMutableArray arrayWithArray:subArray1]; 
[reorderedArray addObjectsFromArray: subArray2]; //[C,D,A,B]
Shai Givati
  • 1,106
  • 1
  • 10
  • 24

3 Answers3

1

The most economical way of rotating NSMutableArray in terms of additional memory is the double-reversion algorithm described in this Q&A, because it does not require any additional storage. The idea is to reverse the entire array, and then reverse the two ranges separately.

In your example the array would be reversed, like this

E D C B A

then the first three elements would be reversed

C D E B A

and finally the tail of the array would be reversed:

C D E A B

Make a helper function for reversing a range, and call it three times:

reverseInPlace(myArray, 0, myArray.count-1);
reverseInPlace(myArray, 0, _startingIndex);
reverseInPlace(myArray, _startingIndex+1, myArray.count-1);

One way to implement reverseInPlace is as follows:

static void reverseInPlace(NSMutableArray *a, int f, int b) {
    while (f < b) {
        [a exchangeObjectAtIndex:f++ withObjectAtIndex:b--];
    }
}
Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • Thanks alot, just what I looked for – Shai Givati Oct 23 '16 at 10:14
  • That's O(N) though, to do better you'll need a ring buffer of some sort (which NSMutableArray is not). – mz2 Oct 23 '16 at 10:16
  • @mz2 Of course it's O(n) - you can't do better than that if you start with any array. OP's problem, however, is not the asymptotic time complexity, because he's got an O(n) solution in time, but the space complexity, which this solution reduces from O(n) in his case to O(1). – Sergey Kalinichenko Oct 23 '16 at 10:19
  • Without taking a position on how clearly the question suggests the only optimisation asked in the question is about space I wanted to point this out, because if that's the only operation needed, a purpose-built circular buffer may be a better option. – mz2 Oct 23 '16 at 10:22
0

No, NSMutableArray is not documented to behave as a circular buffer (ring buffer), nor does it have operations you'd expect to have in one. Some potentially useful resources for solving this with a data structure where rotations have an O(1) cost:

  1. Answer to a related Objective-C question about ring buffers, linking to CHDataStructures available also as a pod if you are so inclined.
  2. Boost.Circular: a C++ circular buffer which you could wrap into some Objective-C++ for your purposes.

If all you need is to rotate a fixed, predictable length buffer, a circular buffer is a simple data structure to implement yourself. Apple's CoreAudio utility classes also include a general purpose ring buffer (CARingBuffer) you may find useful as a reference for your implementation.

If an in-place O(N) solution is sufficient for your needs, the other answer is a better choice than the varyingly complicated things I'm proposing above.

Community
  • 1
  • 1
mz2
  • 4,672
  • 1
  • 27
  • 47
0

More efficient and cleaner:

NSRange range = NSMakeRange(0, startingIndex - 1);
NSArray *subArray = [array subarrayWithRange:range];
[array removeObjectsInRange:range];
[array addObjectsFromArray:subArray];
Willeke
  • 14,578
  • 4
  • 19
  • 47