C# Collection - Order by an element (Rotate)

I have an IEnumerable<Point> collection. Lets say 开发者_如何学Cit contains 5 points (in reality it is more like 2000)

I want to order this collection so that a specifc point in the collection becomes the first element, so it's basically chopping a collection at a specific point and rejoining them together.

So my list of 5 points:

{0,0}, {10,0}, {10,10}, {5,5}, {0,10}

Reordered with respect to element at index 3 would become:

{5,5}, {0,10}, {0,0}, {10,0}, {10,10}

What is the most computationally efficient way of resolving this problem, or is there an inbuilt method that already exists... If so I can't seem to find one!

var list = new[] { 1, 2, 3, 4, 5 };

var rotated = list.Skip(3).Concat(list.Take(3));

// rotated is now {4, 5, 1, 2, 3}

A simple array copy is O(n) in this case, which should be good enough for almost all real-world purposes. However, I will grant you that in certain cases - if this is a part deep inside a multi-level algorithm - this may be relevant. Also, do you simply need to iterate through this collection in an ordered fashion or create a copy?

Linked lists are very easy to reorganize like this, although accessing random elements will be more costly. Overall, the computational efficiency will also depend on how exactly you access this collection of items (and also, what sort of items they are - value types or reference types?).

The standard .NET linked list does not seem to support such manual manipulation but in general, if you have a linked list, you can easily move around sections of the list in the way you describe, just by assigning new "next" and "previous" pointers to the endpoints.

The collection library available here supports this functionality: http://www.itu.dk/research/c5/. Specifically, you are looking for LinkedList<T>.Slide() the method which you can use on the object returned by LinkedList<T>.View().

Version without enumerating list two times, but higher memory consumption because of the T[]:

public static IEnumerable<T> Rotate<T>(IEnumerable<T> source, int count)
{
    int i = 0;

    T[] temp = new T[count];

    foreach (var item in source)
    {
        if (i < count)
        {
            temp[i] = item;
        }
        else
        {
            yield return item;
        }

        i++;
    }

    foreach (var item in temp)
    {
        yield return item;
    }
}

[Test]
public void TestRotate()
{
    var list = new[] { 1, 2, 3, 4, 5 };

    var rotated = Rotate(list, 3);

    Assert.That(rotated, Is.EqualTo(new[] { 4, 5, 1, 2, 3 }));
}

Note: Add argument checks.

Another alternative to the Linq method shown by ulrichb would be to use the Queue Class (a fifo collection) dequeue to your index, and enqueue the ones you have taken out.

The naive implementation using linq would be:

IEnumerable x = new[] { 1, 2, 3, 4 };
var tail = x.TakeWhile(i => i != 3);
var head = x.SkipWhile(i => i != 3);
var combined = head.Concat(tail); // is now 3, 4, 1, 2

What happens here is that you perform twice the comparisons needed to get to your first element in the combined sequence. The solution is readable and compact but not very efficient. The solutions described by the other contributors may be more efficient since they use special data structures as arrays or lists.

You can write a user defined extension of List that does the rotation by using List.Reverse(). I took the basic idea from the C++ Standard Template Library which basically uses Reverse in three steps: Reverse(first, mid) Reverse(mid, last) Reverse(first, last)

As far as I know, this is the most efficient and fastest way. I tested with 1 billion elements and the rotation Rotate(0, 50000, 800000) takes 0.00097 seconds. (By the way: adding 1 billion ints to the List already takes 7.3 seconds)

Here's the extension you can use:

public static class Extensions
{
  public static void Rotate(this List<int> me, int first, int mid, int last)
  {
    //indexes are zero based!
    if (first >= mid || mid >= lastIndex)
      return;
    me.Reverse(first, mid - first + 1);
    me.Reverse(mid + 1, last - mid);
    me.Reverse(first, last - first + 1);
  }
}

The usage is like:

static void Main(string[] args)
{
    List<int> iList = new List<int>{0,1,2,3,4,5};    
    Console.WriteLine("Before rotate:");
    foreach (var item in iList)
    {
      Console.Write(item + " ");
    }
    Console.WriteLine();
    
    int firstIndex = 0, midIndex = 2, lastIndex = 4;
    iList.Rotate(firstIndex, midIndex, lastIndex);
    
    Console.WriteLine($"After rotate {firstIndex}, {midIndex}, {lastIndex}:");
    foreach (var item in iList)
    {
      Console.Write(item + " ");
    }
    Console.ReadKey();
}