Казалось бы в одной из статей мы уже расставили все точки над «ё», однако, не тут было, так как к нам пришла внезапная идея…
Дело в том, что довольно часто приходиться работать с массивами, причем, массивами статическими (т.е. массивами уже заданной размерности), и очень хочется хоть немного комфорта. Иногда, впрочем, встречаются и такие задачи, от которых, так и хочется, реализовать по своему часть функционала (или выпилить лишний) — вот тогда и приходиться решаться на крайности, например, решить проблему с динамическим созданием статического массива нужного размера.
Но, когда мне пришла эта идея в голову и уже была готова примерная реализация, задача с динамическим созданием была решена, но код эксперимента в области «условно новых технологий» отправлять в корзину было жалко, а былой опыт знакомства со скриптовыми языками (Python, Lua и прочие) возбудил любопытство и некоторое желание по портированию тамошних особенностей некоторых структур данных, вследствие чего, решено было продолжить опыты.
Начнем с того, что создадим параметризованную структуру (шаблонный тип, если по-русски) и согласно принципу открытости/закрытости из ООП сделаем закрытое поле, в которое и будет инкапсулирован статический массив некоторой размерности:
struct ExtendedArray(T, size_t M)
{
private:
T[M] internalArray;
public:
this(T value = T.init)
{
internalArray = value;
}
}
(кстати, ООП бывает не только в классах)
Параметры T и M определяют тип и размерность массива (которую, кстати, уже изменить нельзя!), а конструктор this заботиться о корректной инициализации (строго говоря, это не является необходимым — D инициализирует все переменные, но можно сделать так, чтобы переменные не были проинициализированы, для чего необходимо им присвоить void) используя или значение по умолчанию принятое для типа, или же то, значение которое вам кажется удобным.
Теперь, в свежесозданной структуре, мы осуществим интересную идею: оказывается, в некоторых языках программирования допускается использование отрицательных индексов для обращения к элементам массивам, при этом знак минуса в индексе обозначает тот факт, что индексация ведется не слева-направо, а справа-налево, и начинается с 1 (0 уже выбран для обозначения «левого края» массива и не забудьте знак минус в том случае, если захотите воспользоваться этим новшеством).
Реализация этой идеи проста: нужно в структуре определить три метода — opIndex, который отвечает за возврат значения по его индексу; opIndexAssign, который определяет операцию присваивания значения элементу массива с некоторым индексом и метод opIndexOpAssign, который определяет сокращенное присваивание значения некоторому элементу массива:
inout(T) opIndex(long index) inout
{
return internalArray[calculateIndex(index)];
}
T opIndexAssign(T value, long index)
{
return internalArray[calculateIndex(index)] = value;
}
T opIndexOpAssign(string op)(T value, int index)
{
return mixin("internalArray[calculateIndex(index)] " ~ op ~ "= value");
}
Но, чтобы все это заработало, необходимо пересчитывать индексы массива (актуально для отрицательных значений индексов), для чего используется весьма простая процедура подсчета «голого», т.е. реального индекса, исходящая из переданного в методы параметра:
size_t calculateIndex(long index) inout
{
if (index >= 0)
{
return cast(size_t) index;
}
else
{
return cast(size_t) ((index % cast(long) M) + M) % M;
}
}
(работает весьма просто: однако, формулу перевода в реальный индекс я пытался вывести около получаса, поскольку передо мной стояла «слегка» усложненная задача — реализация закольцованного массива, т.е массива в котором невозможен выход за границы, и поддерживающего отрицательную индексацию).
Как видите, определить для своих структур данных поведение, аналогичное встроенным массивам, не так уж и сложно, особенно, если уметь применять микшины (напоминаю, инструкция mixin превращает заданную строк в исполнимый код и подобная трансформация исходного кода работает только на стадии компиляции), однако, мы таким образом определили не весь спектр поведения, принадлежащий массивам…
Одним из часто используемых свойств массива является длина этого массива, а также возможность задания индекса элемента исходя из известной длины самого массива. Как вы помните, D позволяет использовать внутри квадратных скобок особый оператор — знак $, который обозначает длину массива и кроме того, D позволяет перегружать этот оператор:
size_t opDollar()
{
return M;
}
Как насчет инкремента/декремента элемента массива?
Вообще, если посмотреть на существующий код, то выяснится, что мы забыли перегрузить операторы, действующие только на один операнд (т.е. унарные операторы), к которым принадлежат инкремент и декремент. Чтобы исправить ошибку, стоит воспользоваться возможностью переопределения метода opUnary и стоит воспользоваться таким прекрасным инструментом, как mixin:
T opIndexUnary(string op)(long index)
{
mixin("return " ~ op ~ "internalArray[calculateIndex(index)];");
}
Никогда не задумывались над тем, что не устраивает в типах встроенных массивов, несмотря на то, что операции над ними очень тщательно продуманы и обладают огромной выразительностью?
Я как-то думал над этим вопросом и мне не нравилось то, что не предусмотрено некое стандартное средство, которое позволяет быстро определять наличие/отсутствие некоторого элемента в заданном массиве, при том, что для ассоциативных массивов подобная функциональность уже есть «из коробки» (кто не понял о чем я, то посмотрите в документации, что делает оператор in для ассоциативных массивов). С помощью перегрузки операторов возможно исправить столь досадную недоработку, для чего достаточно перегрузить бинарный оператор in следующим образом:
bool opBinaryRight(string op)(T value) if (op == "in")
{
bool isContain = false;
foreach (index; 0..M)
{
if (value == internalArray[calculateIndex(index)])
{
isContain = true;
break;
}
}
return isContain;
}
В нашем скромном расширенном массиве еще кое-чего недостает, а именно возможности сравнения расширенных массивов друг с другом, хоть это востребовано и не так часто. В реализации подобного чуда глупо, на мой взгляд, кустарничать и мы воспользуемся стандартным алгоритмом сравнения (cmp из std.algorithm) для выполнения перегрузки метода opCmp (возвращает int: -1 для случая когда левое выражение меньше правого; 0 когда оба выражения равны; 1 когда левое выражение больше правого выражения — об этом можно прочесть в книге «Язык программирования D»):
int opCmp(in ExtendedArray!(T,M) rhs) const
{
import std.algorithm : cmp;
return cmp(cast(T[]) internalArray, cast(T[]) rhs.content);
}
(обращаем внимание на следующий факт: нужно привести внутренние массивы к динамическим массивам, иначе алгоритм cmp не сработает и вы получите ошибку компиляции. Кроме того, про свойство content я упомяну немного погодя…).
Теперь, для полноты картины нам не хватает только операций для получения среза (т.е. использования двух индексов в операции индексирования) и операций над самими срезами (прибавления значения выражения ко всем элементам среза, вычитания значения из всех элементов среза и тому подобных операций) для чего необходимо перегрузить opSlice, причем в двух вариантах.
Прежде чем делать перегрузку, необходимо определить такую вещь, как диапазон, причем это надо сделать прямо внутри нашей структуры ExtendedArray (все это нужно для того, чтобы операции над срезами были достаточно быстрым и не требовали выделения памяти под хранение срезов. Кроме того, действия над диапазонами необыкновенно удобны и экономичны). Диапазон (Range) — это одна из основных концепций в языке программирования D, однако, я не буду в нее вдаваться подробно (я думаю, об этом еще успеем рассказать и, скорее всего, не в одной статье) и только покажу как ее определить в данном случае (методы для данного диапазона не являются стандартными для диапазона методами, но конкретно в случае перегрузки — это стандартный прием):
struct Range
{
T[] rangeArray;
Range opUnary(string op)()
{
mixin(op ~ "rangeArray[];");
return this;
}
Range opAssign(T value)
{
rangeArray[] = value;
return this;
}
Range opOpAssign(string op)(T value)
{
mixin("rangeArray[] " ~ op ~ "= value;");
return this;
}
}
Все методы диапазона уже знакомы нам по вышеописанным методам для целевой структуры расширенного массива и выполняют те же самые действия, но уже над встроенным в структуру диапазона динамичесим массивом. Используя написанный диапазон, а также подстановочный параметр inout (этот параметр позволит функции не реагировать на квалификаторы immutable/const, которые будучи соединенными с основными типами данных порождают новые типы) можно определить два метода opSlice — для случая применения пустых квадратных скобок (соответствует выделению всего массива) и для случая, собственно, индексации (в квадратных скобках два числа):
inout(Range) opSlice() inout
{
return inout(Range)(internalArray);
}
inout(Range) opSlice(long begin, long end) inout
{
T[] sliceAccumulator;
if (begin == end)
{
sliceAccumulator ~= internalArray[calculateIndex(begin)];
return inout(Range)(cast(inout(T[])) sliceAccumulator);
}
else
{
for (long index = begin; index < end; index++)
{
sliceAccumulator ~= internalArray[calculateIndex(index)];
}
return inout(Range)(cast(inout(T[])) sliceAccumulator);
}
}
Я понимаю, что это выглядит, как адская жесть, однако, это воспринимать довольно легко: в случае выделения всего массива метод выдает диапазон, который принимает весь массив на вход; иначе метод выдает диапазон, который был сгенерирован путем прохода цикла foreach по нужным индексам внутреннего массива структуры ExtendedArray (с учетом необходимого перерасчета индексов). Если это трудно понять, то я рекомендую вам заглянуть в «Programming in D» в раздел «Operators overloading», а также провести ряд экспериментов для выяснения того, как работает этот суровый код (уверяю, ничего страшного в этом нет, хотя я сам просидел два часа просто пытаясь понять, что это за лютая жесть) и почитать ряд номеров журнала FPS (самое хорошее объяснение концепции диапазонов на русском языке), а мы продолжим модернизировать встроенные массивы…
Для более полной картины, добавим еще два метода, которые облегчат жизнь при работе с нашим массивом: метод content(), который выдает содержимое внутреннего массива не нарушая инкапсуляцию; и метод opCast, который позволит преобразовать тип нашей структуры в тип динамического массива:
T[] opCast(T : T[])()
{
return cast(T[]) internalArray;
}
Теперь, у нас почти все реализовано и можно приступить к испытаниям:
import std.stdio;
void main()
{
// определяем массив, состоящий из 10 целых чисел
ExtendedArray!(int, 10) a;
// определяем массив, содержащий 10 целых числе каждое из которых - 15
ExtendedArray!(int, 10) b = ExtendedArray!(int, 10)(15);
writeln(a.content); // содержимое массива a
writeln(b.content); // содержимое массива b
writeln(a[-1]); // последний элемент массива
b[-5] = 7; // присваиваем 5-ому с конца элементу значение
writeln(b.content); // вывод изменений
++b[3]; // увеличим значение 3-его элемента на 1
writeln(b.content);
writeln(b[$-4..$-2]); // вывод диапазона
writeln(7 in a); // проверка на наличие 7 в а
writeln(7 in b); // проверка на наличие 7 в b
writeln(a == b); // сравнение массивов
writeln(a[4..7] += 10); // операция над целым срезом (внутренний массив при таких операциях не меняется !)
}
Маленький трюк — можно создать шаблон, который облегчит создание массивов определенного типа и использовать его почти также, как используется наша целевая структура:
template intArray(size_t M)
{
alias intArray = ExtendedArray!(int, M);
}
Весь код расширенного массива:
import std.stdio;
void main()
{
// определяем массив, состоящий из 10 целых чисел
ExtendedArray!(int, 10) a;
// определяем массив, содержащий 10 целых числе каждое из которых - 15
ExtendedArray!(int, 10) b = ExtendedArray!(int, 10)(15);
writeln(a.content); // содержимое массива a
writeln(b.content); // содержимое массива b
writeln(a[-1]); // последний элемент массива
b[-5] = 7; // присваиваем 5-ому с конца элементу значение
writeln(b.content); // вывод изменений
++b[3]; // увеличим значение 3-его элемента на 1
writeln(b.content);
writeln(b[$-4..$-2]); // вывод диапазона
writeln(7 in a); // проверка на наличие 7 в а
writeln(7 in b); // проверка на наличие 7 в b
writeln(a == b); // сравнение массивов
writeln(a[4..7] += 10); // операция над целым срезом (внутренний массив при таких операциях не меняется !)
intArray!5 c;
c[3] = 9;
writeln(c.content);
}
template intArray(size_t M)
{
alias intArray = ExtendedArray!(int, M);
}
struct ExtendedArray(T, size_t M)
{
private:
T[M] internalArray;
size_t calculateIndex(long index) inout
{
if (index >= 0)
{
return cast(size_t) index;
}
else
{
return cast(size_t) ((index % cast(long) M) + M) % M;
}
}
public:
this(T value = T.init)
{
internalArray = value;
}
inout(T[M]) content() inout
{
return internalArray;
}
inout(T) opIndex(long index) inout
{
return internalArray[calculateIndex(index)];
}
T opIndexAssign(T value, long index)
{
return internalArray[calculateIndex(index)] = value;
}
T opIndexOpAssign(string op)(T value, int index)
{
return mixin("internalArray[calculateIndex(index)] " ~ op ~ "= value");
}
size_t opDollar()
{
return M;
}
T opIndexUnary(string op)(long index)
{
mixin("return " ~ op ~ "internalArray[calculateIndex(index)];");
}
bool opBinaryRight(string op)(T value) if (op == "in")
{
bool isContain = false;
foreach (index; 0..M)
{
if (value == internalArray[calculateIndex(index)])
{
isContain = true;
break;
}
}
return isContain;
}
int opCmp(in ExtendedArray!(T,M) rhs) const
{
import std.algorithm : cmp;
return cmp(cast(T[]) internalArray, cast(T[]) rhs.content);
}
struct Range
{
T[] rangeArray;
Range opUnary(string op)()
{
mixin(op ~ "rangeArray[];");
return this;
}
Range opAssign(T value)
{
rangeArray[] = value;
return this;
}
Range opOpAssign(string op)(T value)
{
mixin("rangeArray[] " ~ op ~ "= value;");
return this;
}
}
inout(Range) opSlice() inout
{
return inout(Range)(internalArray);
}
inout(Range) opSlice(long begin, long end) inout
{
T[] sliceAccumulator;
if (begin == end)
{
sliceAccumulator ~= internalArray[calculateIndex(begin)];
return inout(Range)(cast(inout(T[])) sliceAccumulator);
}
else
{
for (long index = begin; index < end; index++)
{
sliceAccumulator ~= internalArray[calculateIndex(index)];
}
return inout(Range)(cast(inout(T[])) sliceAccumulator);
}
}
T[] opCast(T : T[])()
{
return cast(T[]) internalArray;
}
}
Напоследок стоит сказать, что не все в данном примере реализовано достаточно гладко, да, и есть чего добавить (например, стоит задуматься на добавлением методов length, dup, idup и им подобных), но я уверен, что это небольшое введение показало вам возможности языка, а также придало сил к возможной «настройке» языка под себя.
