Пишемо вектор на Dlang

Доброго часу доби, хабр!

У цьому пості я хочу розглянути деякі особливості мови D, на прикладі створення структури алгебраїчного вектора. У пості не розглядаються питання лінійної алгебри або інший математики.

Варто нагадати, що на відміну від C++ до D класи і структури мають різне логічне призначення і вони влаштовані по-різному. Структури не можуть успадковуватися, у структурах немає ніякої іншої інформації, крім полів (в класах є таблиця віртуальних функцій, наприклад), структури зберігаються за значенням (класи завжди посиланнями). Структури прекрасно підходять для простих типів даних.

Отже, уявімо, що нам хочеться створити вектор, який ми могли б спокійно використовувати в обчисленнях, передавати в opengl, при цьому він був зручний в обігу.

Почнемо з простого:

struct Vector(size_t N,T)
{
T[N] data;
this( in T[N] vals... ) { data = vals; } 
}

Тут все зрозуміло: розмір та тип вектора визначаються параметрами шаблонізації.
Розберемо конструктор. Три крапки в кінці vals дозволяють викликати конструктор без дужок для масиву:

auto a = Vector!(3,float)(1,2,3);

Не дуже зручно прописувати повний тип кожен раз, коли створюєш змінну, зробимо псевдонім:

alias Vector3f = Vector!(3,float);

auto a = Vector3f(1,2,3);

Якщо вам подібний підхід видається не гнучким, D дозволяє робити псевдоніми з шаблонними параметрами:

alias Vector3(T) = Vector!(3,T);

auto a = Vector3!float(1,2,3);
auto b = Vector3!int(1,2,3);

Але якщо в шаблонизацию передати 0, то ми отримаємо статичний вектор з нульовою довжиною, не думаю що це корисно. Додамо обмеження:

struct Vector(size_t N,T) if( N > 0 ) { ... }

Тепер при спробі инстанцировать шаблон вектора з нульовою довжиною:

Vector!(0,float) a;

Отримаємо помилку:

vector.d(10): Error: template instance vector.Vector!(0, float) does not match template declaration Vector(ulong N, T) if (N > 0)

Додамо трохи математики:

struct Vector(size_t N,T) if( N > 0 )
{
...
auto opBinary(string op)( in Vector!(N,T) b ) const
{
Vector!(N,T) ret;
foreach( i; 0 .. N )
mixin( "ret.data[i] = data[i] " ~ op ~ " b.data[i];" );
return ret;
}
}

Тепер ми можемо використовувати наш вектор так:

auto a = Vector3!float(1,2,3);
auto b = Vector3!float(2,3,4);
auto c = Vector3!float(5,6,7);
c = a + b / c * a;

При цьому D зберігає пріоритет операцій (спочатку множення, потім додавання).
Але якщо ми спробуємо використовувати вектора різних типів, зіткнемося з проблемою, що ці типи векторів не сумісні. Обійдемо цю проблему:

...
auto opBinary(string op,E)( in Vector!(N,E) b ) const
if( is( typeof( mixin( "T. init" ~ op ~ "E. init" ) ) : T ) )
{ ...}
...

Не змінюючи код функції ми додали підтримку всіх можливих типів даних, навіть власних, головне, щоб бінарна операція «op» повертала результат. При цьому результат повинен мати можливість неявно приводиться до типу T. Варто зауважити, що вектор int з вектором float скласти не вийде, так як результат додавання int і float це float, а він приводиться до int тільки явно, за допомогою конструкції cast.

Так само реалізуються поелементні операції з числами:

auto opBinary(string op,E)( in E b ) const
if( is( typeof( mixin( "T. init" ~ op ~ "E. init" ) ) : T ) )
{ ...}

При бажанні можна обмежити набір операцій усередині конструкції обмеження сигнатури («if» до тіла функції), перевіривши «op» на відповідність бажаним операціями.

Якщо ми хочемо, щоб наш вектор міг бути прийнятий функціями, які беруть статичні масиви:

void foo(size_t N)( in float[N] arr ) { ... }

Ми можемо скористатися цікавою конструкцією мови D: створення псевдоніма на this.

struct Vector(size_t N,T) if (N > 0)
{
T[N] data;
alias this data;
...
}

Тепер скрізь де компілятор захоче отримати статичний масив, а буде переданий вектор, буде передано поле data. Побічним результатом є, що writeln тепер теж приймає data і не виписує повний тип друку. Так само тепер немає необхідності ігнорувати opIndex:

auto a = Vector3!float(1,2,3);
a[2] = 10;

Додамо трохи різноманітності. У даний момент инстанцировать вектор ми можемо хоч з рядками

auto a = Vector2!string("hell", "habr");
auto b = Vector2!string("o", "ahabr");
writeln( a ~ b ); // ["привіт", "habrahabr"]

і деякі операції над вектором не мають сенсу, наприклад знаходження довжини або знаходження одиничного вектора. Це не проблема для D. Додамо методи знаходження довжини і одиничного вектора таким чином:

import std.algorithm;
import std.math;
struct Vector(size_t N,T) if (N > 0)
{
...
static if( is( typeof( T. init * T. init ) == T ) )
{
const @property
{
auto len2() { return reduce!((r,v)=>r+=v*v)( data.dup ); }

static if( is( typeof( sqrt(T. init) ) ) )
{
auto len() { return sqrt( len2 ); }
auto e() { return this / len; }
}
}
}
}

Тепер метод len2 (квадрат довжини) буде оголошено практично для всіх числових типів даних, а ось len і e тільки для float, double і real. Але якщо дуже хочеться, можна і для всіх зробити:

...
import std.traits;
struct Vector(size_t N,T) if (N > 0)
{
this(E)( in Vector!(N,E) b ) // дозволяє конструювати вектор інших сумісних векторів
if( is( typeof( cast(T)(E. init) ) ) )
{
foreach( i; 0 .. N )
data[i] = cast(T)(b[i]);
}
...
static if( isNumeric!T )
{
auto len(E=CommonType!(T,float))() { return sqrt( cast(E)len2 ); }
auto e(E=CommonType!(T,float))() { return Vector!(N,E)(this) / len!E; }
}
...
}

Тепер методи len і e приймають шаблонний параметр за промовчанням, який обчислюється як найбільший тип з двох

CommonType!(int,float) a; // float a;
CommonType!(double,float) b; // double b;

При бажанні ми можемо явно вказати його, наприклад, у випадку, якщо нам потрібна подвійна точність довжини вектора int.

Трохи про конструктора. Можна створити конструктор з можливість створювати вектор більш варіативно, наприклад так:

auto a = Vector3f(1,2,3);
auto b = Vector2f(1,2);
auto c = Vector!(8,float)( 0, a, 4, b, 3 );

Виглядає він просто:

struct Vector(size_t N,T) if (N > 0)
{
...
this(E...)( in E vals )
{
size_t i = 0;
foreach( v; vals ) i += fillData( data, i, v );
}
...
}

Такий конструктор може приймати параметри різних типів, в будь-якій кількості.

Визначимо функцію fillData:

size_t fillData(size_t N,T,E)( ref T[N] data, size_t no, E val )
{
static if( isNumeric!E )
{
data[no] = cast(T)val;
return 1;
}
else static if( isStaticArray!E &&
isNumeric!(typeof(E. init[0])) )
{
foreach( i, v; val )
data[no+i] = v;
return val.length;
}
else static if( isVector!E )
{
foreach( i, v; val.data )
data[no+i] = cast(T)v;
return val.data.length;
}
else static assert(0,"unkompatible type");
}

Вона відпрацьовує тільки три базових типи: число, статичний масив і вектор. Більш гнучкий варіант займають набагато більше місця і в ньому мало відмінних моментів. Розглянемо шаблон isVector. Він дозволяє визначити, чи є тип E яким вектором. Це знову ж таки робиться через перевірку існування типу, але вже для функції.

template isVector(E)
{
enum isVector = is( typeof( impl(E. init) ) );
void impl(size_t N,T)( Vector!(N,T) x );
}


Вектор не буде повноцінним, якщо ми не зможемо звертатися до його полів так: a.x + b.y.
Можна просто створити кілька властивостей з подібними іменами:

...
auto x() const @property { return data[0]; }
...

але, це не для нас. Спробуємо реалізувати більш гнучкий спосіб доступу:
  • з можливістю створювати вектора з різним набором полів ( xyz, rgb, uv )
  • щоб можна було отримувати доступ до полів не тільки в однині ( a.xy = vec2(1,2) )
  • одного типу вектора має бути кілька варіантів доступу

Використовувати ми для цього будемо чарівний метод opDispatch. Суть його полягає в тому, що якщо метод класу (або структури в нашому випадку) не знайдено, то рядок після точки відправляється в цей метод як параметр шаблону:

class A
{
void opDispatch(string str)( int x ) { writeln( str, ": ", x ); }
}
auto a = new A;
a.hello( 4 ); // hello: 4


Додамо в тип нашого вектора параметризацію рядком і трохи обмежимо варіанти цього рядка

enum string SEP1=" ";
enum string SEP2="|";
struct Vector(size_t N,T,alias string AS) 
if ( N > 0 && ( AS.length == 0 || isCompatibleAccessStrings(N,AS,SEP1,SEP2) ) )
{
...
}

Функція isCompatibleAccessStrings перевіряє валідність рядка доступу до полів. Визначимо правила:
  • імена полів повинні бути валідними ідентифікаторами мови D;
  • кількість імен у кожному варіанті має відповідати розмірності вектора N;
  • імена розділяються пропуском (SEP1);
  • варіанти повинні бути розділені вертикальною рискою (SEP2).
Хоч у цій функції немає нічого особливого, для повноти картини варто навести її текст.
текст функції isCompatibleAccessStrings та інших допоміжних
/// compatible for creating access dispatches
pure bool isCompatibleArrayAccessStrings( size_t N, string str, string sep1="", string sep2="|" )
in { assert( sep1 != sep2 ); } body
{
auto strs = str.split(sep2);
foreach( s; strs )
if( !isCompatibleArrayAccessString(N,s,sep1) )
return false;

string[] fa;
foreach( s; strs )
fa ~= s.split(sep1);

foreach( ref v; fa ) v = strip(v);

foreach( i, a; fa )
foreach( j, b; fa )
if( i != j && a == b ) return false;

return true;
}


/// compatible for creating access dispatches
pure bool isCompatibleArrayAccessString( size_t N, string str, string sep="" )
{ return N == getAccessFieldsCount(str,sep) && isArrayAccessString(str,sep); }

///
pure bool isArrayAccessString( in string as, in string sep="", bool allowDot=false )
{
if( as.length == 0 ) return false;
auto splt = as.split(sep);
foreach( i, val; splt )
if( !isValueAccessString(val,allowDot) || canFind(splt[0..i],val) )
return false;
return true;
}

///
pure size_t getAccessFieldsCount( string str, string sep )
{ return str.split(sep).length; }

///
pure ptrdiff_t getIndex( as string, string arg, string sep1="", string sep2="|" )
in { assert( sep1 != sep2 ); } body
{
foreach( str; as.split(sep2) )
foreach( i, v; str.split(sep1) )
if( arg == v ) return i;
return -1;
}

///
pure bool oneOfAccess( string str, string arg, string sep="" )
{
auto splt = str.split(sep);
return canFind(splt,arg);
}

///
pure bool oneOfAccessAll( string str, string arg, string sep="" )
{
auto splt = arg.split("");
return all!(a=>oneOfAccess(str,a,sep))(splt);
}

///
pure bool oneOfAnyAccessAll( string str, string arg, string sep1="", string sep2="|" )
in { assert( sep1 != sep2 ); } body
{
foreach( s; str.split(sep2) )
if( oneOfAccessAll(s,arg,sep1) ) return true;
return false;
}

/// check symbol count for access to field
pure bool isOneSymbolPerFieldForAnyAccessString( string str, string sep1="", string sep2="|" )
in { assert( sep1 != sep2 ); } body
{
foreach( s; str.split(sep2) )
if( isOneSymbolPerFieldAccessString(s,sep1) ) return true;
return false;
}

/// check symbol count for access to field
pure bool isOneSymbolPerFieldAccessString( string str, string sep="" )
{
foreach( s; str.split(sep) )
if( s.length > 1 ) return false;
return true;
}

pure
{

bool isValueAccessString( in string as, bool allowDot=false )
{
return as.length > 0 &&
startsWithAllowedChars(as) &&
(allowDot?(all!(a=>isValueAccessString(a))(as.split("."))):allowedCharsOnly(as));
}

bool startsWithAllowedChars( in string as )
{
switch(as[0])
{
case 'a': .. case 'z': goto case;
case 'A': .. case 'Z': goto case;
case '_': return true;
default: return false;
}
}

bool allowedCharsOnly( in string as )
{
foreach( c; as ) if( !allowedChar© ) return false;
return true;
}

bool allowedChar( in char c )
{
switch©
{
case 'a': .. case 'z': goto case;
case 'A': .. case 'Z': goto case;
case '0': .. case '9': goto case;
case '_': return true;
default: return false;
}
}

}


Тепер оголосимо методи:

struct Vector( size_t N, T, alias string AS="" )
if( N > 0 && ( isCompatibleArrayAccessStrings(N,AS,SEP1,SEP2) || AS.length == 0 ) )
{
...
static if( AS.length > 0 ) // якщо рядок доступу є
{
@property
{
// можна і отримувати і змінювати значення: a.x = b.y;
ref T opDispatch(string v)()
if( getIndex(AS,v,SEP1,SEP2) != -1 )
{ mixin( format( "return data[%d];", getIndex(AS,v,SEP1,SEP2) ) ); }

// константный метод
T opDispatch(string v)() const
if( getIndex(AS,v,SEP1,SEP2) != -1 )
{ mixin( format( "return data[%d];", getIndex(AS,v,SEP1,SEP2) ) ); }

// у разі, якщо існує варіант доступу, де кожне поле визначається однією буквою
static if( isOneSymbolPerFieldForAnyAccessString(AS,SEP1,SEP2) )
{
// auto a = b.xy; // typeof(a) == Vector!(2,int,"x y");
// auto a = b.xx; // typeof(a) == Vector!(2,int,"");
auto opDispatch(string v)() const
if( v.length > 1 && oneOfAnyAccessAll(AS,v,SEP1,SEP2) )
{
mixin( format( `return Vector!(v.length,T,"%s")(%s);`,
isCompatibleArrayAccessString(v.length,v)?v.split("").join(SEP1):"",
array( map!(a=>format( `data[%d]`,getIndex(AS,a,SEP1,SEP2)))(v.split("")) ).join(",")
));
}

// a.xy = b.zw;
auto opDispatch( string v, U )( in U b )
if( v.length > 1 && oneOfAnyAccessAll(AS,v,SEP1,SEP2) && isCompatibleArrayAccessString(v.length,v) &&
( isCompatibleVector!(v.length,T,U) || ( isDynamicVector!U && is(typeof(T(U. datatype.init))) ) ) )
{
foreach( i; 0 .. v.length )
data[getIndex(AS,""~v[i],SEP1,SEP2)] = T( b[i] );
return opDispatch!v;
}
}
}
}


Текст повноцінного вектора можна знайти на github або в пакеті descore на dub (на даний момент там не остання версія, без варіантів доступу до полів, але скоро все зміниться).

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.