Программирование на Athanor – 17 (кольца)

Кольца: их создание и основные операции над ними

Хотя списки чаще всего представляют создания простых последовательностей данных, но у них есть некоторые недостатки. Один из них – принципиальная асимметрия списков, вызванная их природой. Например, для элементов списка очень легко найти следующий элемент, но существенно труднее – предыдущий (т.к. искать его часто приходится с самого начала списка). Очень легко добавлять элементы в начало списка, и заметно труднее – в его конец (т.к. сложность задачи растёт линейно с длиной списка), и то же справедливо и для удаления элементов. Более того: динамическое формирование списка, элементами которого также являются списки, может потребовать дополнительных ухищрений, т.к. список этот обычно должен быть открытым. Поэтому в языке присутствует ещё одна структура данных – кольца – у которой нет перечисленных недостатков.

Как, наверное, ясно из названия, кольцо – это кольцевой буфер, содержащий в себе элементы произвольного типа. В отличие от списков – кольца строго симметричны: очень легко вставлять/удалять элементы в кольцо / из кольца в произвольном его месте, а также их изменять.

В отличие от списков, кольца создаются явно, с помощью конструктора:

Для ring есть синоним: r_create. Все прочие функторы для работы с кольцами также начинаются с префикса "r_". Только что созданное кольцо не содержит ни одного элемента. Добавить их в кольцо – можно следующими операциями:

Вставка "в начало" – означает перед первым элементом кольца, "в конец" – после последнего. Правда, если кольцо – пустое, то результат обеих операций одинаков: в кольце просто появляется элемент Element. Вставляемый элемент может иметь любой тип (в том числе, может быть списком, и даже ()). Разумеется, есть и обратные операции, удаляющие элементы из кольца:

Обе операции возвращают удалённое значение. (Из пустого кольца, разумеется, удалить уже ничего нельзя.) Также легко выяснить, сколько элементов уже имеется в кольце:

Уже имеющиеся в кольце элементы можно изменять. Для этого есть операция доступа (т.е. аксессор):

Поскольку кольцо циклически замкнуто, то когда Index соответствует какому-то элементу – ему же соответствуют и Index + Count*N (где Count – число элементов в кольце, а N – произвольное целое число). Индекс 0 всегда соответствует первому элементу (также доступному и как Count, 2*Count и т.д.); индекс -1 всегда соответствует последнему элементу (равно как и Count - 1, 2*Count - 1 и т.д.). Для непустого кольца – любое целое значение Index является законным, т.к. ему всегда соответствует какой-либо элемент! Только для пустого кольца – вызов r_elem незаконен, т.к. в нём просто нет элементов. Результат этой операции мутабелен, каждый элемент кольца доступен не только для чтения, но и для изменения.

Для наглядной демонстрации, определим простой конструктор ring_range – возвращающий кольцо, последовательно содержащее элементы из числового диапазона Range:

! ring_range (Range) : [R i] = {
	R = ring ();
	for_inc (i, Range, r_ins_last (R, '[' +$ i +$ ']'));
	R };

Заметьте, что здесь в кольцо мы вставляем не числа, а строки (т.к. каждое число окружается квадратными скобками) – но это также для наглядности. Поскольку при выводе кольца в стандартный вывод (или в какой-либо ещё поток) его элементы (также, как и для списков) просто выводятся подряд – добавим эти скобки в качестве явных разделителей. Работает это так:

Ring_0 = ring_range (10..20);

<: ( r_count (Ring_0), "\n" );

<: ( Ring_0, "\n" );

Результатом будет:

10
[10][11][12][13][14][15][16][17][18][19]

Теперь, для разнообразия, выведем не все элементы кольца подряд – а только с чётными индексами:

for_inc (i, r_count (Ring_0) % 2, <: r_elem (Ring_0, i * 2));
<: "\n";

и получим в результате:

[10][12][14][16][18]

Поскольку кольца замкнуты, для них определена ещё одна полезная операция: поворот на заданное число.

Когда значение Shift больше нуля, элементы кольца циклически сдвигаются вперёд на Shift позиций (т.е. его последние Shift элементов – становятся первыми); когда значение Shift меньше нуля, элементы кольца циклически сдвигаются назад на -Shift позиций (т.е. его первые -Shift элементов – становятся последними). Разумеется, если Shift равно нулю – то вообще ничего не меняется. Фактически, значение Shift также берётся по модулю, равному текущему числу элементов в кольце. Например:

r_rotate (Ring_0, 3);

<: [ Ring_0 "\n" ];

r_rotate (Ring_0, -3);

<: [ Ring_0 "\n" ];

Первый вызов r_rotate сдвигает кольцо на три элемента вперёд, второй – на три элемента назад (восстанавливая всё, как было раньше):

[13][14][15][16][17][18][19][10][11][12]
[10][11][12][13][14][15][16][17][18][19]

Есть и альтернативный метод поворота кольца:

Операция работает как r_rotate, но с той важной разницей, что начальный (нулевой) элемент кольца она фиксирует: он так и остаётся начальным, а вот остальные элементы "проворачиваются" вокруг него. Это лучше демонстрируют примеры:

r_pivot (Ring_0, 4);

<: [ Ring_0 "\n" ];

r_pivot (Ring_0, -4);

<: [ Ring_0 "\n" ];

Здесь первым вызовом мы "проворачиваем" кольцо Ring_0 на четыре элемента вперёд, а вторым – на четыре элемента назад (полностью устраняя последствия первого). Меняют своё положение все элементы, кроме начального "[10]", который является "неподвижной точкой":

[10][16][17][18][19][11][12][13][14][15]
[10][11][12][13][14][15][16][17][18][19]

Наконец, есть ещё r_reverse, эффект которого понятен из названия:

После вызова r_reverse – порядок элементов кольца меняется на противоположный:

r_reverse (Ring_0);

<: [ Ring_0 "\n" ];

r_reverse (Ring_0);

<: [ Ring_0 "\n" ];

Само собой, второй вызов r_reverse – отменяет эффект первого:

[19][18][17][16][15][14][13][12][11][10]
[10][11][12][13][14][15][16][17][18][19]

Для колец – равно, как и для списков, массивов, словарей – определены итераторы:

Оба итератора перебирают все элементы кольца (выполняя для каждого элемента тело Loop). Для r_loop порядок перебора прямой (от начального элемента кольца к конечному), для r_loop_rev порядок обратный (от конечного элемента к начальному). Как и для всех итераторов, возвращаемым значением является результат последнего вызова Loop (если Loop не вызывалось ни разу – это возможно, только когда кольцо пустое – то возвращается ()).

Наконец, кольцо может быть легко преобразовано в список из своих элементов:

В завершение отметим, что кольцо можно быстро очистить:

После выполнения r_clear – в кольце-операнде не остаётся элементов вообще. (Есть ли необходимость что-то специально пояснять про деструктивность этой операции??) После r_clear кольцо становится пустым, в чём нетрудно убедиться:

Операция r_is_empty – это предикат, возвращающий 1 (если кольцо пустое) или 0 (если в нём есть хотя бы один элемент). (Она предпочтительнее, чем r_count (Ring) == 0 – т.к. не подсчитывает число элементов в кольце, а просто проверяет, есть ли там хотя бы один.) Ну и (как и для всех прочих типов данных) – присутствует предикат is_ring (возвращающий 1, если результатом вычисления его операнда является кольцо, и 0, если это что-то другое).

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

! read_input (stream) : [line I E content result] = {
	content = ring ();

	while (stream :> line)::
		r_ins_last (content, line);

	result = array (r_count (content));
	I = 0;
	r_loop (E, content, result {I ++} = E);

	result
	};	` -- read_input `

Вызов read_input (Input) – возвращает массив из строк, считанных из входного потока Input (если операнд пустой – то из стандартного ввода). Сперва мы считываем их в кольцо content, потом создаём массив result, и (в итераторе r_loop) перегружаем все строки из кольца в массив.

В принципе, на кольцах – основные агрегаторы данных языка и завершаются. Правда, это если не включать в это число объекты. (Но объекты, классы и все связанные с ними механизмы ООП – это уже тема для совершенно отдельного разговора...)