Циклические срезы, сдвиги и вращения коллекций

Одна из типовых задач при работе с коллекциями и массивами — выборка n элементов, начиная с i-того индекса, или же, как ��ариант, выборка элементов с i-того по j-й индекс. На языке C# с использованием методов-расширений библиотеки Linq решается она очень просто:

var selectedItems = items.Skip(i).Take(n).ToArray();
var selectedItems = items.Skip(i).Take(j - i).ToArray();

Для строк предусмотрен специальный метод Substing:

var target = source.Substing(i, n);
var target = source.Substing(i, j - i);
var target = source.Substing(i); // from i to end

Часто начинающие разработчики изобретают свои велосипеды для подобных целей из-за недостающих знаний, поэтому на собеседованиях технические интервьюверы иногда задают вопросы по этой теме. В некоторых языках программирования также существует родственная и весьма интересная концепция срезов (slices), детальное пояснение которой с примерами следует далее.



Пускай дан массив букв, упорядоченных по алфавиту. Каждой букве соответствует не только привычный положительный индекс исчисляемый слева-направо (от головы), но и отрицательный, исчисляемый справа-налево (от хвоста):

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
Изначально был взят за основу способ индексации языка Python (второй параметр метода — индекс хвоста), однако в ходе обсуждений выяснилось, что это не оптимальное решение (использование длины [в том числе отрицательной] в качестве второго параметра даёт больше преимуществ), поэтому материал был обновлён.

Вариант метода Slice с индексацией языка Python (второй параметр - индекс хвоста)

Выбор элементов с четвёртого по седьмой включительно можно осуществить несколькими способами:

// хвост не включается в результат
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'

Хвост удобно не включать, поскольку длина выборки тогда легко вычисляется по индексам без лишнего инкремента на единицу и не вызывает путаницы (5-2 = 3 вместо 5-2+1 = 4)

Но возникает вопрос, как в таком случае включить последний элемент исходной коллекции в результирующую выборку, ведь элемента с индексом 8 нет, а отрицательного соответствия ему даже не найти (разве что целочисленный -0, который не отличить от +0)? Тут возникает некоторая рассогласованность. Конечно, можно сделать включение хвоста, усложнив вычисление длины, либо искусственно использовать индексы за пределами массива, как поступили, например, в языке Python.

Чтобы принять оптимальное решение, давайте рассмотрим и другие моменты, как должен вести себя метод, когда индекс хвоста находится раньше индекса головы?

bodyLetters.Slice(7, 3); // ???
bodyLetters.Slice(-1, -5); // ???

Самые элементарные решения — выдать пустую выборку, бросить исключение или же толерантно поменять индексы хвоста и головы местами, а затем продолжить обработку, быть может, вывести результирующую выборку в обратном порядке?

А как поступить, когда индексы хвоста и головы совпадают? По нашим правилам мы включаем голову, но исключаем хвост, однако в таком случае хвост и голова — это одно и то же! Возникает логическое противоречие. Возвращаться к случаю с включением хвоста?

Давайте подумаем… Что если замкнуть, зациклить массив сам на себя? То есть предположить, что сразу за последним индексом 7 идёт снова 0, и если передать в метод, скажем, параметры 6 и 2, то вывести следующий результат 'G', 'I', 'A', 'B'. Тогда чтобы включить последний элемент исходной коллекции в выборку достаточно написать Slice(6, 0) // 'G' 'I', а запись Slice(5, 5) приведёт к тому, что мы получим исходную коллекцию циклически сдвинутую на пять индексов влево — 'F', 'G', 'I', 'A', 'B', 'C', 'D', 'E' — вот чудо!

Для того чтобы получить один элемент нужно написать Slice(5, 6), плюс никаких трудностей с отрицательными индексами, а если вдруг выйдем за границы массива, то получим ожидаемое исключение. Как красиво всё получилось! Если же вдруг потребуется вывести срезанную выборку в обратном порядке, то метод Reverse в помощь. Мы нашли общее решение сразу для двух классов задач лишённое противоречий и очень естественное…

// хвост не включается в результат
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'

Что ж, осталось его реализовать!

       [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;
            }
        }

Вот и пригодился нам yield. И совсем немного кода получилось. Мне нравится, а вам?

P.S. И это не всё, данная статья написана намеренно. Метод Slice — это маленькая часть из синтаксического сахара мощной и функциональной библиотеки Aero Framework, которая предоставляет абстракции и концепции более высокого уровня настолько филигранно согласованные между собой, что при должном терпении в изучении эта стройность вас поразит… Правда, код Aero Framework — это самое совершенное, что мне посчастливилось написать в жизни на текущий момент. А эта статья про циклические срезы и сдвиги только лишь замануха! Изучайте Aero Framework и вы его обязательно оцените.