How to shift the start of an array in C#?

Question

I'm trying to reorganize an array based on the first occurrence of a value (thus simulating similar functionality to a circular array.)

For example, in the following array I wish the first occurrence of the value 6 to become the new first element, and prior elements to become the latter:

So:

int[] myArray = {2, 3, 6, 1, 7, 6};

Becomes:

myArray = {6, 1, 7, 6, 2, 3};

What is the "best" way to achieve this?

Answer 1

You could do the following:

1. Create new array of same size as original
2. Determine your "Start index"
3. Use Array.Copy() to copy everything from start index to end of source array to destination array
4. Use Array.Copy() to copy everything from 0 to start index of source array to the end of the destination array

That way you get a copy of your source array that looks as you expected.

You'll have to play with various overloads of Array.Copy(), however, because I don't know the exact parameter values right now.

Answer 2

var ar = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
ar = ar.SkipWhile(a => a != 6).ToArray<int>();

Answer 3

To begin with, do a linear search to find the first occurrence of the value that you want to make the first element:

// value contains the value to find.

int skip;
for (int i = 0; i < array.Length; i++)
{
    if (array[i] == value)
    {
        skip = i;
        break;
    }
}

// skip contains the index of the element to put at the front.
// Equivalently, it is the number of items to skip.
// (I chose this name for it because it makes the subtractions
// in the Array.Copy implementation more intuitive.)

Do you want to change the actual array? Then do what Thorsten Dittmar suggests:

int[] array = new int[] { 2, 3, 6, 1, 7, 6 };
int[] result = new int[array.Length];

int skip = 2; // So that array[skip] will be result[0] at the end

Array.Copy(array, skip, result, 0, array.Length - skip);
Array.Copy(array, 0, result, array.Length - skip, skip);

Do you want to just view the array in the new order, without doing anything else? Then index it like so:

array[(i + skip) % array.Length]  // Instead of array[i]

Edit: Just for laughs, an implementation of Jon Skeet's suggestion to implement the copy while using only a single buffer value (sourceValue):

// GCD gives the greatest common divisor
int gcd = GCD(array.Length, skip);

// period is the length of the permutation cycles in our rotation.
int period = array.Length / gcd;

int max = array.Length / period;
for (int i = 0; i < max; i++)
{
    int sourceIndex = i;
    int sourceValue = array[sourceIndex];

    for (int n = 1; n <= period; n++)
    {
        int destinationIndex = (sourceIndex + array.Length - skip) % array.Length;

        int temp = array[destinationIndex];
        array[destinationIndex] = sourceValue;
        sourceValue = temp;

        sourceIndex = destinationIndex;
    }
}

Answer 4

Thorsten's solution creates a new array; here's an in place version which only creates a temporary array as large as the amount your rotation size:

public static void RotateLeft<T>(T[] array, int places)
{
    T[] temp = new T[places];
    Array.Copy(array, 0, temp, 0, places);
    Array.Copy(array, places, array, 0, array.Length - places);
    Array.Copy(temp, 0, array, array.Length - places, places);
}

I'm sure it could be done with just a single temporary buffer item, but it would be more complicated :)

As an efficiency measure, here's a "rotate left one place" shortcut:

public static void RotateLeft<T>(T[] array)
{
    T temp = array[0];
    Array.Copy(array, 0, array, 1, array.Length - 1);
    array[array.Length-1] = temp;
}

Answer 5

int[] myArray = { 2, 3, 6, 1, 7, 6 };
myArray = myArray
            .SkipWhile(i => i != 6)
            .Concat(myArray.TakeWhile(i => i != 6))
            .ToArray();

Should do the trick!

You will need a using System.Linq;

Kindness,

Dan

Answer 6

As an alternative to creating a new array, you can wrap it with a class:

class CircularList<T> : IList<T>
{
    static IEnumerable<T> ToEnumerator(CircularList<T> list)
    {
        for (int i = 0; i < list.Count; i++)
        {
            yield return list[i];
        }
    }

    IList<T> arr;
    public int Shift { get; private set; }
    public CircularList(IList<T> arr, int shift)
    {
        this.arr = arr;
        this.Shift = shift;
    }

    int shiftIndex(int baseIndex)
    {
        return (baseIndex + Shift) % arr.Count;
    }

    #region IList<T> Members

    public int IndexOf(T item) { throw new NotImplementedException(); }
    public void Insert(int index, T item) { throw new NotImplementedException(); }
    public void RemoveAt(int index) { throw new NotImplementedException(); }
    public T this[int index]
    {
        get { return arr[shiftIndex(index)]; }
        set { arr[shiftIndex(index)] = value; }
    }

    #endregion

    #region ICollection<T> Members

    public void Add(T item) { throw new NotImplementedException(); }
    public void Clear() { throw new NotImplementedException(); }
    public bool Contains(T item) { throw new NotImplementedException(); }
    public void CopyTo(T[] array, int arrayIndex) { throw new NotImplementedException(); }
    public int Count { get { return arr.Count; } }
    public bool IsReadOnly { get { throw new NotImplementedException(); } }
    public bool Remove(T item) { throw new NotImplementedException(); }

    #endregion

    #region IEnumerable<T> Members

    public IEnumerator<T> GetEnumerator()
    {
        return ToEnumerator(this).GetEnumerator();
    }

    #endregion

    #region IEnumerable Members

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return ToEnumerator(this).GetEnumerator();
    }

    #endregion
}

This program:

class Program
{
    static void Main(string[] args)
    {
        int[] myArray = { 2, 3, 6, 1, 7, 6 };
        CircularList<int> circularList =
            new CircularList<int>(myArray, Array.IndexOf<int>(myArray, 6));

        foreach (int i in circularList)
        {
            Console.WriteLine(i);
        }
    }
}

Prints the following:

6
1
7
6
2
3