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

в 9:39, , рубрики: 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 data this;
...
}

Теперь везде где компилятор захочет получить статический массив, а будет передан вектор, будет передано поле 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 ); // ["hello", "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( string as, 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(c) ) return false;
    return true;
}

bool allowedChar( in char c )
{
    switch(c)
    {
        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) ) ); }

            // в случае, если существует вариант доступа, где каждое полe определяется одной буквой
            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 (на данный момент там не последняя версия, без вариантов доступа к полям, но скоро всё изменится).

Автор: deviator

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js