|
Вначале рассмотрим операции, которые не меняют массивы. Массивы можно сравнивать: template <class T> inline
bool operator == ( CCArrRef<T> & a, CCArrRef<T> & b )
{
if ( a.size() != b.size() ) return false;
for ( nat i = 0; i < a.size(); ++i )
if ( a[i] != b[i] ) return false;
return true;
}
template <class T> inline
bool operator != ( CCArrRef<T> & a, CCArrRef<T> & b )
{
if ( a.size() != b.size() ) return true;
for ( nat i = 0; i < a.size(); ++i )
if ( a[i] != b[i] ) return true;
return false;
}
Применять некоторую операцию поочерёдно к заданному значению:
template <class T1, class T2> inline
T1 & operator += ( T1 & t, CCArrRef<T2> & a )
{
for ( nat i = 0; i < a.size(); ++i ) t += a[i];
return t;
}
template <class T1, class T2> inline
T1 & operator << ( T1 & t, CCArrRef<T2> & a )
{
for ( nat i = 0; i < a.size(); ++i ) t << a[i];
return t;
}
Можно подсчитать к-во элементов равных данному:
template <class A, class B> inline
nat count ( const A & a, const B & b, nat from = 0 )
{
nat n = 0;
for ( nat i = from; i < a.size(); ++i ) if ( a[i] == b ) ++n;
return n;
}
Можно найти индекс первого или последнего элемента равного данному ( в случае, если такой не будет найден возвращается
к-во элементов массива ):
template <class A, class B> inline
nat firEqu ( const A & a, const B & b, nat from = 0 )
{
for ( nat i = from; i < a.size(); ++i ) if ( a[i] == b ) return i;
return a.size();
}
template <class A, class B> inline
nat lasEqu ( const A & a, const B & b )
{
for ( nat i = a.size(); i > 0; --i ) if ( a[i-1] == b ) return i-1;
return a.size();
}
Можно определить - есть ли в массиве элемент равный данному:
template <class A, class B> inline
bool hasEqu ( const A & a, const B & b )
{
for ( nat i = 0; i < a.size(); ++i ) if ( a[i] == b ) return true;
return false;
}
Шаблон функций firMin находит индекс первого с начала минимального элемента:
template <class T> inline
nat firMin ( const T & a )
{
nat m = 0;
for ( nat i = 1; i < a.size(); ++i ) if ( a[i] < a[m] ) m = i;
return m;
}
Шаблон функций firMax находит индекс первого с начала максимального элемента:
template <class T> inline
nat firMax ( const T & a )
{
nat m = 0;
for ( nat i = 1; i < a.size(); ++i ) if ( a[i] > a[m] ) m = i;
return m;
}
Шаблон функций findMinMax находит минимальное и максимальное значения элементов:
template <class T1, class T2> inline
bool findMinMax ( const T1 & a, T2 & min, T2 & max )
{
if ( ! a.size() ) return false;
max = min = a[0];
for ( nat i = 1; i < a.size(); ++i )
{
const T2 & t = a[i];
if ( min > t ) min = t; else
if ( max < t ) max = t;
}
return true;
}
Шаблон функций amean находит арифметическое среднее по всему массиву:
template <class T> inline
Def<T> amean ( CCArrRef<T> & a )
{
if ( ! a.size() ) return Def<T>();
T res ( a[0] );
for ( nat i = 1; i < a.size(); ++i ) res += a[i];
return res / a.size();
}
Если элементы массива упорядочены по возрастанию,
то при помощи функций firEqu123 и lasEqu123 можно найти индекс первого или последнего элемента равного данному,
а при помощи функции hasEqu123 узнать - есть ли в массиве элемент равный данному:
template <class A, class B> inline
nat firEqu123 ( const A & a, const B & b )
{
if ( ! a.size() ) return 0;
int prior = -1, last = a.size() - 1;
while ( prior + 1 < last )
{
const int i = ( prior + last ) / 2;
if ( a[i] < b ) prior = i; else last = i;
}
return a[last] == b ? last : a.size();
}
template <class A, class B> inline
nat lasEqu123 ( const A & a, const B & b )
{
if ( a.size() == 0 ) return 0;
nat from = 0, before = a.size();
while ( from + 1 < before )
{
const nat i = ( from + before ) / 2;
if ( a[i] > b ) before = i; else from = i;
}
return a[from] == b ? from : a.size();
}
template <class A, class B> inline
bool hasEqu123 ( const A & a, const B & b )
{
if ( ! a.size() ) return 0;
nat from = 0, before = a.size();
while ( from + 1 < before )
{
const nat i = ( from + before ) / 2;
if ( a[i] > b ) before = i; else from = i;
}
return a[from] == b;
}
Теперь рассмотрим операции, которые меняют массивы.
Операторы <<= и >>= осуществляют циклический сдвиг элементов на заданное количество шагов в начало и в конец массива соответственно:
template <class T> inline
ArrRef<T> & operator <<= ( ArrRef<T> & a, nat k )
{
const nat n = a.size();
if ( n < 2 || ! ( k %= n ) ) return a;
const nat m = n - k;
if ( m < k ) return a >>= m;
nat i;
CmbArray<T, 64> b ( k );
for ( i = 0; i < k; ++i ) b[i] = a[i];
for ( i = 0; i < m; ++i ) a[i] = a[i+k];
for ( i = 0; i < k; ++i ) a[i+m] = b[i];
return a;
}
template <class T> inline
ArrRef<T> & operator >>= ( ArrRef<T> & a, nat k )
{
const nat n = a.size();
if ( n < 2 || ! ( k %= n ) ) return a;
const nat m = n - k;
if ( m < k ) return a <<= m;
nat i;
CmbArray<T, 64> b ( k );
for ( i = 0; i < k; ++i ) b[i] = a[i+m];
for ( i = m; --i > 0; ) a[i+k] = a[i]; a[k] = a[0];
for ( i = 0; i < k; ++i ) a[i] = b[i];
return a;
}
Следующие функции-операторы делают арифметичекие операции с элементами массива
поочерёдно начиная с первого:
template <class T1, class T2> inline
ArrRef<T1> & operator += ( ArrRef<T1> & a, const T2 & b )
{
for ( nat i = 0; i < a.size(); ++i ) a[i] += b;
return a;
}
template <class T1, class T2> inline
ArrRef<T1> & operator -= ( ArrRef<T1> & a, const T2 & b )
{
for ( nat i = 0; i < a.size(); ++i ) a[i] -= b;
return a;
}
template <class T1, class T2> inline
ArrRef<T1> & operator *= ( ArrRef<T1> & a, const T2 & b )
{
for ( nat i = 0; i < a.size(); ++i ) a[i] *= b;
return a;
}
template <class T1, class T2> inline
ArrRef<T1> & operator /= ( ArrRef<T1> & a, const T2 & b )
{
for ( nat i = 0; i < a.size(); ++i ) a[i] /= b;
return a;
}
Функция sum складывает почленно элементы массивов b и c, и записывает их в массив a:
template <class A, class B, class C> inline
A & sum ( A & a, const B & b, const C & c )
{
const nat n = _min ( a.size(), b.size(), c.size() );
for ( nat i = 0; i < n; ++i ) a[i] = b[i] + c[i];
return a;
}
Описание шаблона классов Def находится здесь.
Исходники находятся в файле ShevArray.h. Наверх |