Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

I have an NSMutableArray holding NSStrings e.g. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

I would like to be able to shift elements with wrapping.

So e.g. move 1 to the centre, shifting all elements, wrapping the remaining ones (that cross the bounds) to the start again, and vice versa e.g. 10 to the centre.

{7, 8, 9, 10, 1, 2, 3, 4, 5, 6} and {6, 7, 8, 9, 10, 1, 2, 3, 4, 5}

Is there an optimised sort method like this already existing?

share|improve this question
1  
I think we can do that in linear time with one for loop, one for the first k elements say 1-6 and next for remaining m elements i.e 7-10. and k+m = n which is size of the array. But i am not aware of any standard algorithm as such. – Praveen S yesterday
@PraveenS - trueIndex = (offset + index) % array.count. I think that's better than linear time. – Hot Licks yesterday

5 Answers

up vote 1 down vote accepted

The most efficient approach would be to create a wrapper object which maintains the current "origin" of the array and re-interprets indexes by adding that origin, modulo the length. In fact, if the array is only accessed in a handful of places this is easily done with 1-2 lines of code in-line.

-(id)objectForIndex:(NSInteger) index {
    NSInteger realIndex = (origin + index) % array.count;
    return [array objectAtIndex:realIndex];
}

(If this extends NS(Mutable)Array then "array" is "super". If only a wrapper then "array" is an instance var. "origin" is an instance var/property in either case.)

share|improve this answer
Smart, no need to mutate. – Helium3 19 hours ago
up vote 1 down vote

I'm unaware of any methods on NSArray for this, but:

static NSArray *shiftArray(NSArray *array, NSInteger pos)
{
    NSInteger length = [array count];
    NSArray *post = [array subarrayWithRange:(NSRange){ .location = length - pos, .length = pos }];
    NSArray *pre = [array subarrayWithRange:(NSRange){ .location = 0, .length = length - pos}];
    return [post arrayByAddingObjectsFromArray:pre];
}

e.g.:

NSArray *array = @[@"A", @"B", @"C", @"D", @"E", @"F", @"G", @"H", @"I"];
NSLog(@"array = %@",shiftArray(array, 4));

Should do what you describe.

Logs to the console:

array = (
    F,
    G,
    H,
    I,
    A,
    B,
    C,
    D,
    E
)

Likely not performant.

share|improve this answer
up vote 0 down vote 
-(NSArray*)shiftForward:(BOOL)forward withbits:(int)bit
{
    NSInteger length = [array count];
    NSArray *right;
    NSArray *left;

    if (forward) {
        //code for right shift
        right = [array subarrayWithRange:(NSRange){ .location = length - bit, .length = bit }];
        left = [array subarrayWithRange:(NSRange){ .location = 0, .length = length - bit}];
        return [right arrayByAddingObjectsFromArray:left];
    }else{
        //code for left shift
        left = [array subarrayWithRange:(NSRange){ .location =0, .length = bit }];
        right= [array subarrayWithRange:(NSRange){ .location = bit, .length = length - bit}];
        return [right arrayByAddingObjectsFromArray:left];
    }
}

- (void)viewDidLoad
{
    array = @[@"1", @"2", @"3", @"4", @"5", @"6", @"7", @"8", @"9"];
    NSLog(@"array is %@",[self shiftForward:YES withbits:3]);
}
share|improve this answer
up vote 0 down vote

Rotating is essentially done by taking N elements from one end of the array and putting them on the other end instead. You could do this with immutable arrays if you wanted, but mutable arrays offer a slightly cleaner implementation.

For rotate left, the simplest way is probably just:

// Make sure we don't overrun the array if the rotation is larger.
numberOfObjectsToRotateLeft %= array.count;

NSRange range = NSMakeRange(0, numberOfObjectsToRotateLeft);
NSMutableArray * rotatedArray = [array mutableCopy];

[rotatedArray addObjectsFromArray:[rotatedArray subarrayWithRange:range]];
[rotatedArray removeObjectsInRange:range];

// now return or use rotatedArray

Rotate right would be similar, but the range would be at the end of the array, and you'd insert the objects starting at index 0 with -insertObjects:atIndexes::

// Make sure we don't overrun the array if the rotation is larger.
numberOfObjectsToRotateRight %= array.count;

NSRange range = NSMakeRange(array.count - numberOfObjectsToRotateRight, numberOfObjectsToRotateRight);
NSMutableArray * rotatedArray = [array mutableCopy];

NSArray * movedObjects = [rotatedArray subarrayWithRange:range];
[rotatedArray removeObjectsInRange:range];
[rotatedArray insertObjects:movedObjects atIndexes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(0, numberOfObjectsToRotateRight)]];

// now return or use rotatedArray
share|improve this answer
up vote 0 down vote

surely if you are shifting by N elements that must wrap around all you would do is take the last N array elements and stick them at the front?

and if you are shifting the other way, take the front and put at the back.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.