Cyclic cuts, shifts and rotation of collections
One of the typical tasks when working with collections and arrays is the selection of n elements, starting with the i -th index, or, alternatively, the selection of elements from the i -th through the jth index. In C # using the Linq library extension methods, it is solved very simply:
For strings, there is a special Substing method:
Often, novice developers invent their bikes for such purposes due to lack of knowledge, so at interviews technical interviewers sometimes ask questions about this topic. In some programming languages, there is also a related and very interesting concept of slices , a detailed explanation of which with examples follows.
')
Let given an array of letters sorted alphabetically. Each letter corresponds not only to the usual positive index, counted from left to right (from the head), but also negative, counted from right to left (from the tail):
UPDATE
Initially, the method of indexing the Python language was used as the basis (the second parameter of the method is the tail index), but during the discussions it turned out that this is not the optimal solution (using the length [including negative] as the second parameter gives more advantages), so the material was updated
Final Update
Implementation
So yield us. And quite a bit of code came out. I like, and you?
PS And that's not all, this article was written intentionally. The Slice method is a small part of the syntax sugar of the powerful and functional library Aero Framework , which provides abstractions and higher level concepts so delicately coordinated with each other, that with proper patience in studying this harmony will amaze you ... True, the Aero Framework code is the most perfect that I was lucky to write in life at the moment. And this article is about cyclical cuts and shifts only zamanuha! Learn the Aero Framework and you will definitely appreciate it.
var selectedItems = items.Skip(i).Take(n).ToArray(); var selectedItems = items.Skip(i).Take(j - i).ToArray(); For strings, there is a special Substing method:
var target = source.Substing(i, n); var target = source.Substing(i, j - i); var target = source.Substing(i); // from i to end Often, novice developers invent their bikes for such purposes due to lack of knowledge, so at interviews technical interviewers sometimes ask questions about this topic. In some programming languages, there is also a related and very interesting concept of slices , a detailed explanation of which with examples follows.
')
Let given an array of letters sorted alphabetically. Each letter corresponds not only to the usual positive index, counted from left to right (from the head), but also negative, counted from right to left (from the tail):
var bodyLetters = new[] {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'I'}; var headIndexes = new[] { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 }; var tailIndexes = new[] {-8 , -7 , -6 , -5 , -4 , -3 , -2 , -1 }; UPDATE
Initially, the method of indexing the Python language was used as the basis (the second parameter of the method is the tail index), but during the discussions it turned out that this is not the optimal solution (using the length [including negative] as the second parameter gives more advantages), so the material was updated
A variant of the Slice method with Python language indexing (the second parameter is the tail index)
The choice of elements from the fourth to the seventh inclusive can be done in several ways:
It is convenient not to turn on the tail, since the sample length is then easily calculated from indices without an extra increment of one and does not cause confusion (5-2 = 3 instead of 5-2 + 1 = 4)
But the question arises how, in this case, to include the last element of the original collection in the resulting sample, because there is no element with index 8 , and there is not even a negative match for it (unless the integer -0 , which cannot be distinguished from +0 )? Here there is some mismatch. Of course, you can make the inclusion of the tail, complicating the calculation of the length, or artificially use indices outside the array, as was done, for example, in the Python language .
To make the best decision, let's consider other points, how should the method behave when the tail index is before the head index?
The most elementary solutions are to give an empty sample, throw an exception, or tolerantly change the indexes of the tail and head in some places, and then continue processing, perhaps, output the resulting sample in the reverse order?
And what to do when the indices of the tail and head are the same? According to our rules, we turn on the head, but we exclude the tail, but in this case the tail and the head are the same! There is a logical contradiction. Returning to the case with the inclusion of the tail?
Let's think ... What if we close, loop the array on ourselves ? That is, suppose that immediately after the last index 7 goes 0 again, and if you pass, say, parameters 6 and 2 to the method, then output the following result 'G', 'I', 'A', 'B' . Then to include the last element of the original collection in the sample, it suffices to write Slice (6, 0) // 'G' 'I' , and the record Slice (5, 5) will result in the original collection being cyclically shifted five indexes to the left - 'F', 'G', 'I', 'A', 'B', 'C', 'D', 'E' - this is a miracle!
In order to get one element, you need to write Slice (5, 6) , plus no difficulties with negative indices, and if you suddenly go beyond the bounds of the array, you will get the expected exception. How beautiful everything turned out! If you suddenly need to display the cut-off sample in the reverse order, then the Reverse method will help. We found a common solution for two classes of problems at once, devoid of contradictions and very natural ...
Well, it remains to implement it!
// bodyLetters.Slice(3, 7); // 'D', 'E', 'F', 'G' bodyLetters.Slice(-5, 7); // 'D', 'E', 'F', 'G' bodyLetters.Slice(3, -1); // 'D', 'E', 'F', 'G' bodyLetters.Slice(-5, -1); // 'D', 'E', 'F', 'G' It is convenient not to turn on the tail, since the sample length is then easily calculated from indices without an extra increment of one and does not cause confusion (5-2 = 3 instead of 5-2 + 1 = 4)
But the question arises how, in this case, to include the last element of the original collection in the resulting sample, because there is no element with index 8 , and there is not even a negative match for it (unless the integer -0 , which cannot be distinguished from +0 )? Here there is some mismatch. Of course, you can make the inclusion of the tail, complicating the calculation of the length, or artificially use indices outside the array, as was done, for example, in the Python language .
To make the best decision, let's consider other points, how should the method behave when the tail index is before the head index?
bodyLetters.Slice(7, 3); // ??? bodyLetters.Slice(-1, -5); // ??? The most elementary solutions are to give an empty sample, throw an exception, or tolerantly change the indexes of the tail and head in some places, and then continue processing, perhaps, output the resulting sample in the reverse order?
And what to do when the indices of the tail and head are the same? According to our rules, we turn on the head, but we exclude the tail, but in this case the tail and the head are the same! There is a logical contradiction. Returning to the case with the inclusion of the tail?
Let's think ... What if we close, loop the array on ourselves ? That is, suppose that immediately after the last index 7 goes 0 again, and if you pass, say, parameters 6 and 2 to the method, then output the following result 'G', 'I', 'A', 'B' . Then to include the last element of the original collection in the sample, it suffices to write Slice (6, 0) // 'G' 'I' , and the record Slice (5, 5) will result in the original collection being cyclically shifted five indexes to the left - 'F', 'G', 'I', 'A', 'B', 'C', 'D', 'E' - this is a miracle!
In order to get one element, you need to write Slice (5, 6) , plus no difficulties with negative indices, and if you suddenly go beyond the bounds of the array, you will get the expected exception. How beautiful everything turned out! If you suddenly need to display the cut-off sample in the reverse order, then the Reverse method will help. We found a common solution for two classes of problems at once, devoid of contradictions and very natural ...
// bodyLetters.Slice(6, 2); // 'G', 'I', 'A', 'B' bodyLetters.Slice(5, 5); // 'F', 'G', 'I', 'A', 'B', 'C', 'D', 'E' bodyLetters.Slice(5, 5, SliceOptions.Lazy); // {empty} bodyLetters.Slice(5, 6); // 'F' bodyLetters.Slice(5, 0); // 'F', 'G', 'I' bodyLetters.Slice(5); // 'F', 'G', 'I' Well, it remains to implement it!
[Flags] public enum SliceOptions { None = 0, Lazy = 1, } public static IEnumerable<T> Slice<T>( this IEnumerable<T> collection, int head, int tail = 0, SliceOptions options = SliceOptions.None) { var items = collection as T[] ?? collection.ToArray(); var count = items.Count(); head = head < 0 ? count + head : head; tail = tail < 0 ? count + tail : tail; if (head < 0 || count - 1 < head) throw new ArgumentOutOfRangeException("head"); if (tail < 0 || count - 1 < tail) throw new ArgumentOutOfRangeException("tail"); if (head == tail && (options & SliceOptions.Lazy) == SliceOptions.Lazy) { yield break; } if (head < tail) { foreach (var item in items.Skip(head).Take(tail - head)) { yield return item; } } else { foreach (var item in items.Skip(head)) { yield return item; } foreach (var item in items.Skip(0).Take(tail)) { yield return item; } } } Update 2
public static IEnumerable<T> Turn<T>(this IList<T> items, int skip, int turnsCount = 0) { var reverse = skip < 0; var count = items.Count; skip = reverse ? count + skip : skip; var take = turnsCount == 0 ? reverse ? -skip - 1 : count - skip : count*turnsCount; return items.Ring(skip, take); } public static IEnumerable<T> Ring<T>(this IList<T> items, int skip, int take) { var reverse = take < 0; var count = items.Count; skip = skip < 0 ? count + skip : skip; skip = skip < count ? skip : skip%count; take = reverse ? -take : take; for (var i = 0; i < take; i++) { var j = i < count ? i : i%count; var index = reverse ? skip - j : skip + j; index = index < 0 ? count + index : index; index = index < count ? index : index%count; yield return items[index]; } } private static void Main(string[] args) { var bodyLetters = new[] {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'I'}; var headIndexes = new[] { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 }; var tailIndexes = new[] {-8 , -7 , -6 , -5 , -4 , -3 , -2 , -1 }; // 'C', 'D', 'E', 'F', 'G', 'I', 'A', 'B', bodyLetters.Ring(2, 8).ToList().ForEach(Console.Write); Console.WriteLine(); // 'C', 'B', 'A', 'I', 'G', 'F', 'E', 'D', bodyLetters.Ring(2, -8).ToList().ForEach(Console.Write); Console.WriteLine(); // 'D', 'E', 'F', 'G' bodyLetters.Ring(3, 4).ToList().ForEach(Console.Write); Console.WriteLine(); // 'D', 'E', 'F', 'G' bodyLetters.Ring(-5, 4).ToList().ForEach(Console.Write); Console.WriteLine(); // 'D', 'C', 'B', 'A' bodyLetters.Ring(-5, -4).ToList().ForEach(Console.Write); Console.WriteLine(); // 'D', 'E', 'F', 'G', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'I', 'A', 'B', 'C' bodyLetters.Ring(3, 16).ToList().ForEach(Console.Write); Console.WriteLine(); // 'D', 'C', 'B', 'A', 'I', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'I', 'G', 'F', 'E' bodyLetters.Ring(-5, -16).ToList().ForEach(Console.Write); Console.WriteLine(); // 'D', 'E', 'F', 'G', 'I' bodyLetters.Turn(3).ToList().ForEach(Console.Write); Console.WriteLine(); // 'D', 'C', 'B', 'A' bodyLetters.Turn(-5).ToList().ForEach(Console.Write); Console.WriteLine(); Console.ReadKey(); } Final Update
private static void Main(string[] args) { var bodyLetters = new[] {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'I'}; var headIndexes = new[] { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 }; var tailIndexes = new[] {-8 , -7 , -6 , -5 , -4 , -3 , -2 , -1 }; // CDEFGICDEF bodyLetters.SkipByRing(18).TakeByRing(10).ToList().ForEach(Console.Write); Console.WriteLine(); // FEDCBAFEDC bodyLetters.SkipByRing(-18).TakeByRing(10).ToList().ForEach(Console.Write); Console.WriteLine(); // IGFEDCIGFE bodyLetters.SkipByRing(18).TakeByRing(-10).ToList().ForEach(Console.Write); Console.WriteLine(); // ABCDEFABCD bodyLetters.SkipByRing(-18).TakeByRing(-10).ToList().ForEach(Console.Write); Console.WriteLine(); Console.WriteLine(); // CDEFGIABCD bodyLetters.SliceByRing(18, 10).ToList().ForEach(Console.Write); Console.WriteLine(); // GIABCDEFGI bodyLetters.SliceByRing(-18, 10).ToList().ForEach(Console.Write); Console.WriteLine(); // BAIGFEDCBA bodyLetters.SliceByRing(18, -10).ToList().ForEach(Console.Write); Console.WriteLine(); // FEDCBAIGFE bodyLetters.SliceByRing(-18, -10).ToList().ForEach(Console.Write); Console.WriteLine(); Console.ReadKey(); } Implementation
// ReSharper disable PossibleMultipleEnumeration // ReSharper disable LoopCanBePartlyConvertedToQuery public static IEnumerable<T> SkipByRing<T>(this IEnumerable<T> source, int count) { var originalCount = 0; var reverse = count < 0; count = reverse ? -count : count; source = reverse ? source.Reverse() : source; while (true) { if (originalCount > 0) count %= originalCount; foreach (var item in source) { originalCount++; if (count > 0) { count--; continue; } yield return item; } if (count == 0) yield break; } } public static IEnumerable<T> TakeByRing<T>(this IEnumerable<T> source, int count) { var reverse = count < 0; count = reverse ? -count : count; source = reverse ? source.Reverse() : source; while (true) { foreach (var item in source) { if (count > 0) { count--; yield return item; } } if (count == 0) yield break; } } public static IEnumerable<T> SliceByRing<T>(this IEnumerable<T> source, int skipCount, int takeCount) { var originalCount = 0; var skipReverse = skipCount < 0; var takeReverse = takeCount < 0; skipCount = skipReverse ? -skipCount : skipCount; takeCount = takeReverse ? -takeCount : takeCount; source = takeReverse ? source.Reverse() : source; if (skipReverse ^ takeReverse) { var count = source.Count(); skipCount = count - skipCount % count; } while (true) { if (originalCount > 0) skipCount %= originalCount; foreach (var item in source) { originalCount++; if (skipCount > 0) { skipCount--; continue; } if (takeCount > 0) { takeCount--; yield return item; } } if (takeCount == 0) yield break; } } So yield us. And quite a bit of code came out. I like, and you?
PS And that's not all, this article was written intentionally. The Slice method is a small part of the syntax sugar of the powerful and functional library Aero Framework , which provides abstractions and higher level concepts so delicately coordinated with each other, that with proper patience in studying this harmony will amaze you ... True, the Aero Framework code is the most perfect that I was lucky to write in life at the moment. And this article is about cyclical cuts and shifts only zamanuha! Learn the Aero Framework and you will definitely appreciate it.
Source: https://habr.com/ru/post/272743/
All Articles