SaraP
1245 lines
43 KiB
C++
1245 lines
43 KiB
C++
//////////////////////////////////////////////////////////////////////////////////////////
|
|
/**
|
|
\file
|
|
\brief \ru Шаблонные утилиты.
|
|
\en Template utilities. \~
|
|
*/
|
|
/////////////////////////////////////////////////////////////////////////////// C3D API///
|
|
|
|
#ifndef __GENERIC_UTILITY_H
|
|
#define __GENERIC_UTILITY_H
|
|
|
|
#include <memory.h>
|
|
//
|
|
#include <templ_sptr.h>
|
|
//
|
|
#include <assert.h>
|
|
#include <mb_variables.h>
|
|
|
|
#include <new>
|
|
#include <utility>
|
|
#include <functional>
|
|
#include <vector>
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Пустой тип данных. \en Empty data type.
|
|
//---
|
|
struct null_type
|
|
{
|
|
static const null_type value() { return null_type(); }
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/** \brief \ru Шаблон для получения индексного типа (для статического сопоставления типов на этапе компиляции)
|
|
\en Template to generate an indexed type (for static type-matching in compile-time)
|
|
*/
|
|
//---
|
|
template<size_t>
|
|
struct index_tag
|
|
{
|
|
index_tag() {} // Constructor under GCC compiler
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Цветовая маркировка (применяется для графов) \en Color marking (used for graphs)
|
|
//---
|
|
enum color_code: char
|
|
{
|
|
white_color = 0
|
|
, gray_color = 1
|
|
, green_color = 2
|
|
, black_color = 3
|
|
, red_color
|
|
, orange_color
|
|
, visited_color
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
// Constant valued function
|
|
//---
|
|
template<bool boolVal>
|
|
bool boolFunc() { return boolVal; }
|
|
|
|
/*
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Цветовая маркировка, например, для графовых объектов \en Color marking, for example: for graph objects
|
|
//---
|
|
template<typename ColorValue = color_code >
|
|
struct color_traits
|
|
{
|
|
static color_code white() { return white_color; }
|
|
static color_code gray() { return gray_color; }
|
|
static color_code green() { return green_color; }
|
|
static color_code red() { return red_color; }
|
|
static color_code black() { return black_color; }
|
|
};
|
|
|
|
template<>
|
|
struct color_traits<char>
|
|
{
|
|
static char white() { return 0; }
|
|
static char gray() { return 1; }
|
|
static char green() { return 2; }
|
|
static char red() { return 3; }
|
|
static char black() { return 4; }
|
|
};
|
|
*/
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Графовые характеристики типов. \en Graph datatype traits.
|
|
//---
|
|
template< class Graph >
|
|
struct graph_traits
|
|
{
|
|
/*
|
|
Ассоциативные типы данных концепции графа.
|
|
Associative datatypes of the graph concept.
|
|
*/
|
|
typedef typename Graph::vertex vertex; // Тип, интерпретируемый, как вершина графа.
|
|
typedef typename Graph::edge edge; // Тип, интерпретируемый, как ребро графа
|
|
typedef typename Graph::vertex_iterator vertex_iterator; // Обход всех вершин графа
|
|
typedef typename Graph::adjacency_iterator adjacency_iterator; // Обход смежных вершин некоторой вершины
|
|
typedef typename Graph::vertices_size_t vertices_size_t; // Целочисленный тип размера графа
|
|
typedef typename Graph::degree_size_t degree_size_t; // Целочисленный тип вершинной степени
|
|
typedef typename Graph::edge_iterator edge_iterator; // Итератор обхода исходящих ребер [или неориентированных ребер]
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Наибольшее из двух. \en Maximum of two.
|
|
// ---
|
|
template<class T>
|
|
inline const T & max_of( const T & elem1, const T & elem2 )
|
|
{
|
|
if ( elem2 < elem1 )
|
|
return elem1;
|
|
return elem2;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Наибольшее из двух. \en Maximum of two.
|
|
// ---
|
|
template<class T>
|
|
inline const T & min_of( const T & elem1, const T & elem2 )
|
|
{
|
|
if ( elem1 < elem2 )
|
|
return elem1;
|
|
return elem2;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Поменять местами значения. \en Swap the values.
|
|
// ---
|
|
template<class T>
|
|
inline void swap_vals( T & elem1, T & elem2 )
|
|
{
|
|
T tmp = elem1;
|
|
elem1 = elem2;
|
|
elem2 = tmp;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Поменять местами значения указателей. \en Swap the values of pointers.
|
|
// ---
|
|
template<class T>
|
|
inline void swap_ptrs( T* & elem1, T* & elem2 )
|
|
{
|
|
T * tmp = elem1;
|
|
elem1 = elem2;
|
|
elem2 = tmp;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Поменять местами значения указателей. \en Swap the values of pointers.
|
|
//---
|
|
template<class Type>
|
|
inline void swap_ptrs( SPtr<Type> & p1, SPtr<Type> & p2 )
|
|
{
|
|
SPtr<Type> t = p1;
|
|
p1 = p2;
|
|
p2 = t;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
// \ru Равенство пары указателей \en Equality of pointer pair
|
|
//---
|
|
template< class Type1, class Type2 >
|
|
bool equal_ptrs( const Type1 * ptr1, const Type2 * ptr2 )
|
|
{
|
|
return static_cast<const Type2*>(ptr1) == ptr2;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
// \ru Равенство пары указателей \en Equality of pointer pair
|
|
//---
|
|
template< class Type1, class Type2 >
|
|
bool equal_ptrs( SPtr<Type1> ptr1, const Type2 * ptr2 )
|
|
{
|
|
return static_cast<const Type2*>(ptr1.get()) == ptr2;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
// \ru Равенство пары двухмерных векторов или точек \en Equality of 2D points or vectors
|
|
//---
|
|
template< class XY1, class XY2 >
|
|
bool equal_xy( const XY1 & v1, const XY2 & v2, double eps )
|
|
{
|
|
if ( fabs(v1.x-v2.x) > eps )
|
|
return false;
|
|
if ( fabs(v1.y-v2.y) > eps )
|
|
return false;
|
|
return true;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
// \ru Наименьший общий делитель \en The lowest common denominator
|
|
// ---
|
|
template < typename Integer >
|
|
Integer euclid_algo ( Integer a, Integer b )
|
|
{
|
|
Integer const zero = static_cast<Integer>( 0 );
|
|
|
|
bool goOn = true;
|
|
while ( goOn )
|
|
{
|
|
if ( a == zero ) {
|
|
goOn = false;
|
|
return b;
|
|
}
|
|
|
|
b %= a;
|
|
|
|
if ( b == zero ) {
|
|
goOn = false;
|
|
return a;
|
|
}
|
|
|
|
a %= b;
|
|
}
|
|
return zero;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Получить НОД для пары целых чисел \en Get GCD for a pair of integers
|
|
// ---
|
|
template < typename IntegerType >
|
|
inline IntegerType gcd( IntegerType a, IntegerType b )
|
|
{
|
|
IntegerType const zero = static_cast<IntegerType>( 0 );
|
|
IntegerType const result = ::euclid_algo( a, b );
|
|
return ( result < zero ) ? -result : result;
|
|
}
|
|
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
// \ru Функциональный объект - коллектор \en The functional object - collector
|
|
/*\ru Играет роль посетителя foreach-алгоритмов, осуществляющий накачку STL-совместимых контейнеров
|
|
\en Serves as a visitor of foreach-algorithms exercising pumping of STL-compatible containers \~
|
|
*/
|
|
//---
|
|
template<class _Cont>
|
|
struct collector
|
|
{
|
|
typedef typename _Cont::value_type value_type;
|
|
_Cont & container; // \ru STL-совместимый контейнер \en STL-compatible container
|
|
|
|
collector( _Cont & arr )
|
|
: container( arr ) {}
|
|
collector( const collector & c ) : container( c.container ) {}
|
|
void operator () ( const value_type & elem ) const
|
|
{
|
|
container.push_back( elem );
|
|
}
|
|
|
|
private: // \ru не реализовано \en not implemented
|
|
collector & operator = ( const collector & );
|
|
};
|
|
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/** \brief \ru Статический вектор.
|
|
\en Static vector.
|
|
\note \ru Требуется, что бы элементы вектора имели конструктор по умолчанию,
|
|
конструктор копирования и оператор присвоения.
|
|
\en Required that the vector elements have a default constructor,
|
|
copy constructor and assignment operator. \~
|
|
*/
|
|
//---
|
|
template<class Elem, size_t arrSize>
|
|
class static_array
|
|
{
|
|
public:
|
|
typedef Elem value_type; // \ru ассоциативный тип элемента массива \en associative type of array element
|
|
|
|
private:
|
|
value_type arr[arrSize]; // \ru статическое выделение памяти под массив \en static allocation for the array
|
|
|
|
public:
|
|
/// \ru Инициализация одним элементом. \en Initialization of one element.
|
|
explicit static_array( const Elem & val )
|
|
{
|
|
fill( val );
|
|
}
|
|
/// \ru Инициализация парой элементов. \en Initialization of a pair of elements.
|
|
static_array( const Elem & e1, const Elem & e2 )
|
|
{
|
|
PRECONDITION( arrSize == 2 );
|
|
arr[0] = e1;
|
|
arr[1] = e2;
|
|
}
|
|
/// \ru Конструктор по тройке. \en Constructs as a triplet.
|
|
static_array( const Elem & e1, const Elem & e2, const Elem & e3 )
|
|
{
|
|
PRECONDITION( arrSize == 3 );
|
|
arr[0] = e1;
|
|
arr[1] = e2;
|
|
arr[2] = e3;
|
|
}
|
|
explicit static_array( const static_array & vec )
|
|
{
|
|
_Assign( vec );
|
|
}
|
|
|
|
template<class _Vector>
|
|
static_array( const _Vector & vec )
|
|
{
|
|
_Assign( vec );
|
|
}
|
|
|
|
/// \ru Инициализация одним элементом. \en Initialization of one element.
|
|
static_array & fill( const Elem & val )
|
|
{
|
|
for( size_t idx = 0; idx<arrSize; ++idx )
|
|
{
|
|
arr[idx] = val;
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
template<class _Iter>
|
|
static_array & assign( _Iter iter, _Iter last )
|
|
{
|
|
for ( value_type * myIter = arr ; iter!=last; ++iter, ++myIter )
|
|
{
|
|
PRECONDITION( myIter < arr+arrSize );
|
|
*myIter = *iter;
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
inline value_type & operator[] ( size_t idx )
|
|
{
|
|
PRECONDITION( idx < arrSize );
|
|
return arr[idx];
|
|
}
|
|
inline const value_type & operator[] ( size_t idx ) const
|
|
{
|
|
PRECONDITION( idx < arrSize );
|
|
return arr[idx];
|
|
}
|
|
template<class _Vector>
|
|
static_array & operator = ( const _Vector & vec )
|
|
{
|
|
_Assign( vec );
|
|
return *this;
|
|
}
|
|
|
|
/// \ru Равенство. \en Equality.
|
|
template<class _Vector>
|
|
bool operator == ( const _Vector & vec ) const
|
|
{
|
|
if ( arrSize != vec.size() )
|
|
{
|
|
return false;
|
|
}
|
|
for( size_t idx = 0; idx<arrSize; ++idx )
|
|
{
|
|
if ( arr[idx] != vec[idx] )
|
|
{
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
inline const Elem * c_arr() const { return arr; }
|
|
inline Elem * c_arr() { return arr; }
|
|
inline size_t size() const { return arrSize; }
|
|
inline value_type & front() { return *arr; }
|
|
inline value_type & back() { PRECONDITION(arrSize>0); return arr[arrSize-1]; }
|
|
inline const value_type & front() const { return *arr; }
|
|
inline const value_type & back() const { PRECONDITION(arrSize>0); return arr[arrSize-1]; }
|
|
|
|
private:
|
|
template< class _Vector >
|
|
void _Assign( const _Vector & vec )
|
|
{
|
|
PRECONDITION( vec.size() == size() );
|
|
for ( size_t idx = ::min_of( arrSize, vec.size() ); idx > 0; )
|
|
{
|
|
idx--;
|
|
arr[idx] = vec[idx];
|
|
}
|
|
}
|
|
};
|
|
|
|
// \ru (!) Запретить пустые статические массивы \en (!) Prevent empty static arrays
|
|
template<class Elem> class static_array<Elem,0> {};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Статический вектор двух элементов (пара). \en Static vector of two elements (pair).
|
|
//---
|
|
template<class Elem>
|
|
struct static_pair: public static_array<Elem,2>
|
|
{
|
|
typedef static_array<Elem,2> parent_type;
|
|
// static_pair(): parent_type() {}
|
|
explicit static_pair( const Elem & el ): parent_type( el ) {}
|
|
static_pair( const Elem & el1, const Elem & el2 ): parent_type( el1, el2 ) {}
|
|
explicit static_pair( const static_pair & pair ) : parent_type( pair ) {}
|
|
|
|
static_pair & operator = ( const static_pair & vec )
|
|
{
|
|
parent_type::operator=( vec );
|
|
return *this;
|
|
}
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/**
|
|
\brief \ru Динамический контейнер для хранения элементов упорядоченного множества.
|
|
\en Dynamic container for storing elements of an ordered set.
|
|
|
|
\details
|
|
\ru Тип элемента контейнера должен иметь операторы порядка. Не стоит путать этот
|
|
тип контейнера с set или map. Он вовсе не обязан всегда поддерживаться в отсортированном
|
|
состоянии, а только тогда, когда это закажут (с кэшированием алгоритма сортировки).
|
|
Гарантируется, что вектор отсортирован сразу после вызова функций get_sorted или sort.
|
|
Константные методы, а также метод erase не нарушают сортировки.\n
|
|
\en Type of container element must have order operators. Do not confuse this
|
|
type of container with a set or map. It is not obliged always be supported in a sorted
|
|
state, and only when it is needed (with caching of sorting algorithm). It is guaranteed
|
|
that the vector is sorted immediately after the function call get_sorted or sort.
|
|
Const methods and the erase method does not break sorting. \n \~
|
|
|
|
\par \ru Про эффективность
|
|
|
|
Часто сортированный вектор оказывается более эффективным, чем std::map или std::set,
|
|
особенно если добавление/удаление элементов массива осуществляется серийно и достаточно
|
|
редко перемежаются, с запросами быстрого (бинарного) поиска элемента или его места по
|
|
порядку. В отличие от map или set минимально дефрагментируется память и не требуется
|
|
избыточной информации для хранения указателей (может занимать в 4 раза меньше памяти).
|
|
Для быстрых запросов можно применять стандартные алгоритмы, такие
|
|
как std::binary_search, std::lower_bound и т.п.
|
|
|
|
\en About efficiency
|
|
|
|
Often sorted vector is more effective than
|
|
std::map or std::set especially when adding/removing elements
|
|
of the array is standard and is rarely interspersed
|
|
with queries quickly (binary) search of element or its place by
|
|
the order. In contrast to the map or set minimal defragmented
|
|
memory and does not require excess information for storage of pointers
|
|
(can occupy memory in less than 4 times).
|
|
For fast queries, can use standard algorithms such
|
|
as std::binary_search, std::lower_bound etc. \~
|
|
*/
|
|
//---
|
|
template<class KeyType, class _Pr = std::less<KeyType> > // \ru KeyType - тип элемента с операторами порядка "<" \en KeyType - the element type with the operators of order "<"
|
|
class sorting_array
|
|
{
|
|
public:
|
|
typedef std::vector<KeyType> container_type;
|
|
typedef typename container_type::value_type value_type;
|
|
typedef typename container_type::size_type size_type;
|
|
typedef typename container_type::const_iterator iterator;
|
|
typedef typename container_type::iterator _iterator;
|
|
typedef std::pair<iterator,iterator> iter_range;
|
|
typedef _Pr key_compare; // \ru отношение порядка (предикат) \en order relation (predicate)
|
|
|
|
public:
|
|
sorting_array() : m_vector(), m_sorted( true ) {}
|
|
|
|
public:
|
|
iter_range get_sorted() { sort(); return iter_range(m_vector.begin(), m_vector.end()); }
|
|
iter_range range() const { return iter_range(m_vector.begin(), m_vector.end()); }
|
|
const KeyType & sorted_back() { sort(); return m_vector.back(); }
|
|
bool empty() const { return m_vector.empty(); }
|
|
iterator begin() const { return m_vector.begin(); }
|
|
iterator end() const { return m_vector.end(); }
|
|
_iterator _begin() { return m_vector.begin(); }
|
|
_iterator _end() { return m_vector.end(); }
|
|
const KeyType & front() const { return m_vector.front(); }
|
|
const KeyType & back() const { return m_vector.back(); }
|
|
void erase( iterator );
|
|
void erase( iterator f, iterator l );
|
|
bool is_sorted() const { return m_sorted; }
|
|
iterator insert( iterator _whereItr, const KeyType & val ); // \ru вставить элемент перед позицией whereItr \en insert element before position whereItr
|
|
template <class InputIterator>
|
|
void insert( iterator position, InputIterator first, InputIterator last )
|
|
{
|
|
m_vector.insert( position, first, last );
|
|
m_sorted = false;
|
|
}
|
|
template <class InputIterator>
|
|
void assign ( InputIterator first, InputIterator last )
|
|
{
|
|
m_vector.assign( first, last );
|
|
m_sorted = false;
|
|
}
|
|
void resize( size_t n, const KeyType & val );
|
|
void reserve ( size_t n ) { m_vector.reserve( n ); }
|
|
void push_back( const KeyType & val );
|
|
void sort()
|
|
{
|
|
if ( !m_sorted )
|
|
{
|
|
std::sort( m_vector.begin(), m_vector.end(), _Pr() );
|
|
m_sorted = true;
|
|
}
|
|
}
|
|
void clear() { m_vector.clear(); }
|
|
size_t size() const { return m_vector.size(); }
|
|
KeyType & operator[] ( size_t n ) { PRECONDITION( n < m_vector.size() ); return m_vector[n]; }
|
|
const KeyType & operator[] ( size_t n ) const { PRECONDITION( n < m_vector.size() ); return m_vector[n]; }
|
|
|
|
private:
|
|
container_type m_vector;
|
|
bool m_sorted;
|
|
|
|
private:
|
|
sorting_array( const sorting_array & ); // \ru реализовать по необходимости \en implement if necessary
|
|
sorting_array & operator = ( const sorting_array & ); // \ru реализовать по необходимости \en implement if necessary
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
//
|
|
// ---
|
|
template<class KeyType, class _Pr >
|
|
void sorting_array<KeyType,_Pr>::push_back( const KeyType & val )
|
|
{
|
|
m_sorted = m_vector.empty() ? true : m_sorted && _Pr()( m_vector.back(), val );
|
|
m_vector.push_back( val );
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
//
|
|
//---
|
|
template<class KeyType, class _Pr >
|
|
void sorting_array<KeyType,_Pr>::erase( iterator ersItr )
|
|
{
|
|
m_vector.erase( m_vector.begin() + (ersItr - begin()) );
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
//
|
|
//---
|
|
template<class KeyType, class _Pr >
|
|
void sorting_array<KeyType,_Pr>::erase( iterator f, iterator l )
|
|
{
|
|
typename container_type::iterator first, last;
|
|
first = last = m_vector.begin();
|
|
std::advance( first, std::distance(begin(),f) ); // convert from const-iterator to non-const
|
|
std::advance( last, std::distance(begin(),l) );
|
|
m_vector.erase( first, last );
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
// \ru Вставить элемент перед позицией whereItr \en Insert element before position whereItr
|
|
//---
|
|
template<class KeyType, class _Pr >
|
|
typename sorting_array<KeyType,_Pr>::iterator
|
|
sorting_array<KeyType,_Pr>::insert( iterator _whereItr, const KeyType & val )
|
|
{
|
|
typename container_type::iterator whereItr = m_vector.begin();
|
|
std::advance( whereItr, std::distance(begin(),_whereItr) ); // \ru перевод из конст-итератора в неконст \en convert from const-iterator to non-const
|
|
// \ru Далее проверяем не нарушает ли новая вставка упорядоченности массива \en Next, whether new insert does not break ordering of the array
|
|
if ( m_sorted && (_whereItr != m_vector.end()) )
|
|
{
|
|
m_sorted = ! key_compare()( *_whereItr, val );
|
|
if ( m_sorted ) // val <= _where
|
|
{
|
|
m_sorted = ( _whereItr == m_vector.begin() ) || !key_compare()( val, *(--_whereItr) );
|
|
}
|
|
}
|
|
|
|
// \ru Вставка \en Insert
|
|
return m_vector.insert( whereItr, val );
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
//
|
|
//---
|
|
template<class KeyType, class _Pr >
|
|
void sorting_array<KeyType,_Pr>::resize( size_t n, const KeyType & val )
|
|
{
|
|
if ( m_sorted && (m_vector.size() < n) && !m_vector.empty() )
|
|
{
|
|
m_sorted = !key_compare()( val, m_vector.back() ); // m_vector.back() <= val
|
|
}
|
|
|
|
m_vector.resize( n, val );
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Проверка упорядоченности массива \en Check for ordering array
|
|
//---
|
|
template<class SortedArray>
|
|
bool check_ordering( const SortedArray & arr )
|
|
{
|
|
if ( arr.is_sorted() && !arr.empty() )
|
|
{
|
|
typename SortedArray::value_type prev( *arr.begin() );
|
|
typename SortedArray::iterator first = arr.begin()+1;
|
|
typename SortedArray::iterator last = arr.end();
|
|
for( ; first!=last; ++first )
|
|
{
|
|
if ( (*first) < prev )
|
|
{
|
|
return false; // \ru нарушен порядок следования \en order has been broken
|
|
}
|
|
prev = *first;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Обнулить структуру данных (использовать осторожно!). \en Reset the data structure (use with caution!).
|
|
//---
|
|
template< class DataSt >
|
|
inline DataSt null_struct()
|
|
{
|
|
DataSt data;
|
|
::memset( &data, 0, sizeof(DataSt) );
|
|
return data;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Отладочный инспектор union-контейнера (НЕдоделан!). \en Debug Inspector of union-container (NOT completed yet!).
|
|
//---
|
|
template<class _PairUnion>
|
|
struct dbg_inspector
|
|
{
|
|
union data_t
|
|
{
|
|
typename _PairUnion::value_type * first;
|
|
};
|
|
data_t data;
|
|
dbg_inspector() { data.first = 0; }
|
|
void init( const _PairUnion & ) {}
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Хвостовой элемент для рекурсивного определения типа recursive_union<T1,T2>. \en Tail element for recursive determination of type recursive_union<T1,T2>.
|
|
//---
|
|
struct empty_variant
|
|
{
|
|
static const size_t dataSize = 0;
|
|
static const size_t power = 0;
|
|
struct value_type {};
|
|
bool empty() { return true; }
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Получить номер типа из списка union-контейнера. \en Get type index from the list of union-container.
|
|
//---
|
|
template<class _PairUnion, class _Type>
|
|
struct which_type
|
|
{
|
|
static const int value = 1 + which_type<typename _PairUnion::tail_type,_Type>::value;
|
|
};
|
|
|
|
// \ru Специализация 1 \en Specialization 1
|
|
template<class _PairUnion>
|
|
struct which_type<_PairUnion,typename _PairUnion::value_type>
|
|
{
|
|
static const int value = 0;
|
|
};
|
|
|
|
// \ru Специализация 2 \en Specialization 2
|
|
template<class _Type>
|
|
struct which_type<empty_variant,_Type>
|
|
{
|
|
static const int value = -1;
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Получить тип варианта с заданным номером. \en Get variant type with a given index.
|
|
//---
|
|
template<class T, int idx >
|
|
struct type_which
|
|
{
|
|
typedef typename T::tail_type tail_t;
|
|
typedef typename type_which<tail_t,idx-1>::value_t value_t;
|
|
};
|
|
|
|
template<class T>
|
|
struct type_which<T,0>
|
|
{
|
|
typedef typename T::value_type value_t;
|
|
};
|
|
|
|
template<class T>
|
|
struct type_which<T,-1>
|
|
{
|
|
private:
|
|
typedef null_type value_t;
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Проводник посетителя для рекурсивно-заданного контейнера. \en Conductor of visitor for recursively given container.
|
|
//---
|
|
template<class _PairUnion, int typeNb, int power >
|
|
struct union_conductor
|
|
{
|
|
typedef typename type_which<_PairUnion,typeNb>::value_t _Type;
|
|
|
|
/// \ru Статическое приведение типа. \en Static cast of type.
|
|
template<class U, class T>
|
|
static T * unsafe_cast( U & u ) { return u.template unsafe_cast<T>(); }
|
|
|
|
/// \ru Статическое приведение типа. \en Static cast of type.
|
|
template<class U, class T>
|
|
static const T * unsafe_cast( const U & u ) { return u.template unsafe_cast<T>(); }
|
|
|
|
/// \ru Применить функтор. \en Apply the functor.
|
|
template<class _Visitor>
|
|
static inline void apply( const _Visitor & vis, _PairUnion & oper )
|
|
{
|
|
if ( oper.which() == typeNb )
|
|
{
|
|
vis( *unsafe_cast<_PairUnion,_Type>(oper) );
|
|
}
|
|
else
|
|
{
|
|
union_conductor<_PairUnion,typeNb+1,power>::apply( vis, oper );
|
|
}
|
|
}
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
// \ru Вызвать деструктор для указателя, если его тип попадает в диапазон от t до power. \en Call the destructor for the pointer if its type is within the range from t to power.
|
|
//---
|
|
template<class _PairUnion, int power >
|
|
struct union_conductor<_PairUnion,power,power>
|
|
{
|
|
template<class _Visitor>
|
|
static inline void apply( const _Visitor & , _PairUnion & ) {}
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/**
|
|
\brief \ru Рекурсивное определение класса "union-контейнер".
|
|
\en Recursive definition of class "union-container".
|
|
\details \ru Контейнер, который может хранить элемент типа "value_type" или один из типов
|
|
хвостового контейнера.
|
|
\en Container which can store the element of type "value_type" or one of types
|
|
of tail container. \~
|
|
*/
|
|
//---
|
|
template<class Type, class Tail = empty_variant >
|
|
class recursive_union
|
|
{
|
|
typedef recursive_union<Type,Tail> _Myt;
|
|
|
|
public: // \ru доступные ассоциативные типы и константы \en available associative types and constants
|
|
static const size_t dataSize = sizeof(Type) > Tail::dataSize ? sizeof(Type) : Tail::dataSize;
|
|
static const size_t power = 1 + Tail::power; // \ru Количество типов, которое может обеспечить вариант \en The count of types which can provide a variant
|
|
|
|
typedef Type value_type;
|
|
typedef Tail tail_type;
|
|
|
|
public:
|
|
recursive_union() : m_typeNb(-1) { ::memset(m_data, 0, dataSize); }
|
|
recursive_union( const Type & );
|
|
|
|
#ifndef __DEBUG_MEMORY_ALLOCATE_FREE_
|
|
template<class _Type>
|
|
recursive_union( const _Type & elem )
|
|
: m_typeNb( which_type<_Myt,_Type>::value )
|
|
, dbg_data()
|
|
{
|
|
if ( m_typeNb >= 0 )
|
|
{
|
|
new ( (void*)m_data ) _Type( elem );
|
|
}
|
|
}
|
|
#else // __DEBUG_MEMORY_ALLOCATE_FREE_
|
|
template<class _Type>
|
|
recursive_union( const _Type & )
|
|
: m_typeNb( which_type<_Myt,_Type>::value )
|
|
, dbg_data()
|
|
{
|
|
// (!) The placement form of operator new is required.
|
|
C3D_ASSERT_UNCONDITIONAL( false );
|
|
}
|
|
#endif //__DEBUG_MEMORY_ALLOCATE_FREE_
|
|
|
|
~recursive_union();
|
|
|
|
private: // \ru вспомогательные объекты \en assisting objects
|
|
// \ru Посетитель для вызова конструктора типа, которым занят union-контейнер \en The visitor to call the type constructor which is occupied by union-container
|
|
struct assigner
|
|
{
|
|
assigner( _Myt & d ) : lOper(&d) {}
|
|
|
|
template<class _Type>
|
|
void operator() ( const _Type & elem ) const
|
|
{
|
|
C3D_ASSERT( lOper );
|
|
*lOper = elem;
|
|
}
|
|
private:
|
|
mutable _Myt * lOper; // \ru Левый операнд присвоения \en The left operand of assignment
|
|
|
|
private:
|
|
assigner & operator = ( const assigner & );
|
|
};
|
|
|
|
// \ru Посетитель для вызова деcтруктора типа, которым занят union-контейнер \en The visitor to call the type destructor which is occupied by union-container
|
|
struct destroyer
|
|
{
|
|
template<class _Type>
|
|
static void ignore(const _Type & ) {} // \ru для подавления сообщений \en for suppression of messages
|
|
|
|
template<class _Type>
|
|
void operator() (const _Type & elem ) const
|
|
{
|
|
ignore( elem );
|
|
elem.~_Type();
|
|
}
|
|
};
|
|
|
|
// \ru Проверка на равенство \en The check for equality
|
|
struct comparer
|
|
{
|
|
const _Myt & data;
|
|
mutable bool result;
|
|
comparer( const _Myt & d ) : data( d ), result(false) {}
|
|
template<class _Type>
|
|
void operator() ( const _Type & elem ) const
|
|
{
|
|
result = (data == elem);
|
|
}
|
|
private:
|
|
comparer & operator = ( const comparer & );
|
|
};
|
|
|
|
struct conductor: public union_conductor<_Myt,0,power> {};
|
|
struct const_conductor: public union_conductor<const _Myt,0,power> {};
|
|
|
|
public:
|
|
int which() const { return m_typeNb; }
|
|
// \ru Проверить пустой ли контейнер \en Check whether the container is empty
|
|
bool empty() const { return m_typeNb < 0; }
|
|
|
|
// \ru Безопасное динамическое приведение типа \en Secure dynamic cast of type
|
|
template<class _Type>
|
|
_Type * safe_cast()
|
|
{
|
|
if ( which_type<_Myt,_Type>::value == m_typeNb )
|
|
{
|
|
return (_Type*)m_data;
|
|
}
|
|
return 0;
|
|
}
|
|
// \ru Безопасное динамическое приведение типа \en Secure dynamic cast of type
|
|
template<class _Type>
|
|
const _Type * safe_cast() const
|
|
{
|
|
if ( which_type<_Myt,_Type>::value == m_typeNb )
|
|
{
|
|
return (const _Type*)m_data;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
// \ru Статическое приведение типа \en Static cast of type
|
|
template<class _Type>
|
|
_Type * unsafe_cast()
|
|
{
|
|
assert( (which_type<_Myt,_Type>::value == m_typeNb) );
|
|
return (_Type*)m_data;
|
|
}
|
|
|
|
// \ru Статическое приведение типа \en Static cast of type
|
|
/*
|
|
template<int _typeNb> typename type_which<_Myt,_typeNb>::value_t &
|
|
unsafe_get();
|
|
*/
|
|
/*
|
|
{
|
|
assert( (which_type<_Myt,_Type>::value == m_typeNb) );
|
|
return (type_which<_Myt,_typeNb>::value_t*)m_data;
|
|
}
|
|
*/
|
|
|
|
// \ru Статическое приведение типа \en Static cast of type
|
|
template<class _Type>
|
|
const _Type * unsafe_cast() const
|
|
{
|
|
assert( (which_type<_Myt,_Type>::value == m_typeNb) );
|
|
return reinterpret_cast<const _Type*>( m_data );
|
|
}
|
|
|
|
void release()
|
|
{
|
|
accept( destroyer() );
|
|
m_typeNb = -1;
|
|
}
|
|
/*
|
|
template<class _Type>
|
|
void release()
|
|
{
|
|
if ( which_type<_Myt,_Type>::value == m_typeNb )
|
|
{
|
|
((_Type*)m_data)->~_Type();
|
|
m_typeNb = -1;
|
|
}
|
|
}
|
|
*/
|
|
|
|
// \ru Присвоение другого union-контейнера \en Assignment of another union-container
|
|
_Myt & operator = ( const _Myt & v )
|
|
{
|
|
release();
|
|
v.accept( assigner(*this) );
|
|
C3D_ASSERT( m_typeNb == v.m_typeNb );
|
|
return *this;
|
|
}
|
|
|
|
// \ru Присвоение произвольного типа \en Assignment of arbitrary type
|
|
/*
|
|
template<class _Type>
|
|
_Myt & operator = ( const _Type & elem )
|
|
{
|
|
m_typeNb = which_type<_Myt,_Type>::value;
|
|
if ( m_typeNb >= 0 )
|
|
{
|
|
new ( (void*)m_data ) _Type( elem );
|
|
}
|
|
return *this;
|
|
}
|
|
*/
|
|
|
|
// \ru Равенство \en Equality
|
|
bool operator == ( const _Myt & v ) const
|
|
{
|
|
if ( m_typeNb == v.m_typeNb )
|
|
{
|
|
comparer cmp( *this );
|
|
v.accept( cmp );
|
|
return cmp.result;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
// \ru Равенство \en Equality
|
|
template<class _Type>
|
|
bool operator == ( const _Type & elem ) const
|
|
{
|
|
if ( m_typeNb == which_type<_Myt,_Type>::value )
|
|
{
|
|
return elem == *unsafe_cast<_Type>();
|
|
}
|
|
return false;
|
|
}
|
|
|
|
// \ru Доступ посетителя \en Visitor access
|
|
template<class _Visitor>
|
|
void accept( const _Visitor & vis ) const
|
|
{
|
|
const_conductor::apply( vis, *this );
|
|
}
|
|
// \ru Доступ посетителя \en Visitor access
|
|
template<class _Visitor>
|
|
void accept( const _Visitor & vis )
|
|
{
|
|
conductor::apply( vis, *this );
|
|
}
|
|
|
|
private: // \ru данные \en data
|
|
char m_data[dataSize];
|
|
int m_typeNb;
|
|
dbg_inspector<_Myt> dbg_data;
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
//
|
|
//---
|
|
template<class Type, class Tail>
|
|
recursive_union<Type,Tail>::recursive_union( const Type & elem )
|
|
: m_typeNb( 0 )
|
|
, dbg_data()
|
|
{
|
|
dbg_data.init( *this );
|
|
new ( (void*)m_data ) Type( elem );
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
//
|
|
//---
|
|
template<class Type, class Tail>
|
|
recursive_union<Type,Tail>::~recursive_union()
|
|
{
|
|
release();
|
|
}
|
|
|
|
template<class T, class Tail >
|
|
struct def_pair_union // \ru определитель рекурсивного контейнера для пары типов \en determinant of a recursive container for a pair of types
|
|
{
|
|
typedef recursive_union<T,Tail> value_t;
|
|
};
|
|
template<class T>
|
|
struct def_pair_union<T,empty_variant>
|
|
{
|
|
typedef recursive_union<T,empty_variant> value_t;
|
|
};
|
|
template<>
|
|
struct def_pair_union<null_type,empty_variant>
|
|
{
|
|
typedef empty_variant value_t;
|
|
};
|
|
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/** \brief \ru union-контейнер для экземпляра типа из определенного набора типов.
|
|
\en union-container for instance of type from a specific set of types.
|
|
\details \ru Позволяет создать тип, принимающий значения из некоторого набора разнородных
|
|
типов.
|
|
\en Allows to create a type which takes values ??from a set of heterogeneous
|
|
types. \~
|
|
*/
|
|
//---
|
|
template<
|
|
class T0
|
|
, class T1
|
|
, class T2 = null_type
|
|
, class T3 = null_type
|
|
, class T4 = null_type
|
|
, class T5 = null_type>
|
|
class aligned_union
|
|
{
|
|
typedef empty_variant _Tail6;
|
|
typedef typename def_pair_union<T5,_Tail6>::value_t _Tail5;
|
|
typedef typename def_pair_union<T4,_Tail5>::value_t _Tail4;
|
|
typedef typename def_pair_union<T3,_Tail4>::value_t _Tail3;
|
|
typedef typename def_pair_union<T2,_Tail3>::value_t _Tail2;
|
|
typedef typename def_pair_union<T1,_Tail2>::value_t _Tail1;
|
|
typedef typename def_pair_union<T0,_Tail1>::value_t _Variant;
|
|
|
|
typedef aligned_union<T0,T1,T2,T3,T4,T5> _Myt;
|
|
|
|
public:
|
|
aligned_union(): m_data() {}
|
|
template<class T>
|
|
aligned_union( const T & elem ) : m_data( elem ) {}
|
|
|
|
public:
|
|
/// \ru Выдать номер текущего типа, которым занят контейнер \en Get a index of the current type which is occupied container
|
|
int which() const { return m_data.which(); }
|
|
/// \ru Проверить пустой ли контейнер \en Check whether the container is empty
|
|
bool empty() const { return m_data.empty(); }
|
|
/// \ru Применить функтор (посетитель) \en Apply the functor (visitor)
|
|
template<class _Vis>
|
|
void accept( const _Vis & vis ) const { m_data.accept( vis ); }
|
|
/// \ru Применить функтор (посетитель) \en Apply the functor (visitor)
|
|
template<class _Vis>
|
|
void accept( const _Vis & vis ) { m_data.accept( vis ); }
|
|
/// \ru Сделать контейнер пустым \en Make an empty container
|
|
void clear() { m_data.release(); }
|
|
/// \ru Операция присвоения \en Assignment operation
|
|
_Myt & operator = ( const _Myt & elem ) { m_data = elem.m_data; return *this; }
|
|
template<class T >
|
|
_Myt & operator = ( const T & elem ) { m_data = elem; return *this; }
|
|
// \ru Операция сравнения \en Compare operation
|
|
bool operator == ( const _Myt & elem ) const { return m_data == elem.m_data; }
|
|
template<class T >
|
|
bool operator == ( const T & elem ) const { return m_data == elem; }
|
|
/// \ru Безопасно преобразовать тип контейнера к указателю \en Safely convert type of container to a pointer
|
|
template<class T >
|
|
T * safe_cast() { return m_data.template safe_cast<T>(); }
|
|
template<class T >
|
|
const T * safe_cast() const { return m_data.template safe_cast<T>(); }
|
|
template<class T >
|
|
bool get( T & val ) const
|
|
{
|
|
if ( const T * ptr = m_data.template safe_cast<T>() )
|
|
{
|
|
val = *ptr;
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
private:
|
|
_Variant m_data;
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
//
|
|
// ---
|
|
template<class _Iterator, class _Element>
|
|
constexpr bool is_exist( _Iterator begIt, _Iterator endIt, const _Element & elem )
|
|
{
|
|
return std::find( begIt, endIt, elem ) != endIt;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
//
|
|
// ---
|
|
template<class _Iterator, class UnaryPredicate>
|
|
constexpr bool is_exist_if( _Iterator begIt, _Iterator endIt, UnaryPredicate _Pred )
|
|
{
|
|
return std::find_if( begIt, endIt, _Pred ) != endIt;
|
|
}
|
|
|
|
namespace c3d
|
|
{
|
|
|
|
struct color_label
|
|
{
|
|
color_code val;
|
|
color_label() : val( white_color ) {}
|
|
bool operator == ( color_code col ) const { return col == val; }
|
|
color_label & operator = ( color_code col ) { val = col; return *this; }
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
//
|
|
//---
|
|
template <typename Iterator>
|
|
struct _IterTraits
|
|
{
|
|
typedef typename Iterator::value_type value_type;
|
|
typedef typename Iterator::reference reference;
|
|
};
|
|
|
|
template <typename T>
|
|
struct _IterTraits<T*>
|
|
{
|
|
typedef T value_type;
|
|
typedef T& reference;
|
|
};
|
|
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
// Диапазон итераторов.
|
|
//---
|
|
template<class Iterator>
|
|
struct range : public std::pair<Iterator, Iterator>
|
|
{
|
|
typedef std::pair<Iterator, Iterator> _Pair;
|
|
|
|
//typedef std::iterator_traits<Iterator> _IterTraits; // Стандартный пока не действует на итераторы графа.
|
|
typedef typename _IterTraits<Iterator>::value_type value_type;
|
|
typedef typename _IterTraits<Iterator>::reference reference;
|
|
|
|
range( const Iterator & iter, const Iterator & last ) : _Pair( iter, last ) {}
|
|
range( Iterator && iter, Iterator && last ) : _Pair( iter, last ) {}
|
|
range( const _Pair & other ) : _Pair( other ) {}
|
|
range() : _Pair() {}
|
|
Iterator begin() const { return _Pair::first; }
|
|
Iterator end() const { return _Pair::second; }
|
|
bool empty() const { return _Pair::first == _Pair::second; }
|
|
size_t size() const { return (size_t)std::distance( _Pair::first, _Pair::second ); }
|
|
void clear() { _Pair::first = _Pair::second; }
|
|
range & move_front() { ++_Pair::first; return *this; }
|
|
range & drop_front() { ++_Pair::first; return *this; }
|
|
range & drop_back() { --_Pair::second; return *this; }
|
|
|
|
const reference front() const { return *_Pair::first; }
|
|
const reference back() const { return *(_Pair::second - 1); }
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
// Get a range of the STL-container
|
|
//---
|
|
template<class _Cont>
|
|
inline range<typename _Cont::const_iterator> range_of( const _Cont & list )
|
|
{
|
|
return {list.begin(), list.end()};
|
|
}
|
|
|
|
template<class _Cont>
|
|
inline range<typename _Cont::iterator> range_of( _Cont & list )
|
|
{
|
|
return {list.begin(), list.end()};
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
// Get a range of iterators
|
|
//---
|
|
template<class _Iterator>
|
|
inline range<_Iterator> make_range( _Iterator first, _Iterator last )
|
|
{
|
|
return {first, last};
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Пара ссылок. \en A pair of references.
|
|
//---
|
|
template<class _Ty1, class _Ty2>
|
|
struct ref_pair
|
|
{
|
|
_Ty1 & first;
|
|
_Ty2 & second;
|
|
|
|
ref_pair( _Ty1 & val1, _Ty2 & val2 )
|
|
: first(val1), second(val2)
|
|
{}
|
|
ref_pair( const ref_pair & other )
|
|
: first(other.first), second(other.second)
|
|
{}
|
|
|
|
template<class _Other1, class _Other2>
|
|
ref_pair( const std::pair<_Other1, _Other2> & right )
|
|
: first(right.first), second(right.second)
|
|
{}
|
|
|
|
template<class _Other1, class _Other2>
|
|
ref_pair & operator = ( const std::pair<_Other1, _Other2> & right )
|
|
{
|
|
first = right.first;
|
|
second = right.second;
|
|
return *this;
|
|
}
|
|
|
|
private:
|
|
ref_pair & operator = ( const ref_pair & ); // \ru не реализуемо \en not implemented
|
|
};
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
/// \ru Выдать ссылки одной связкой. \en Get references as one bunch.
|
|
//---
|
|
template<typename Type1, typename Type2 >
|
|
inline ref_pair<Type1,Type2>
|
|
tie( Type1 & iter1, Type2 & iter2 )
|
|
{
|
|
return ref_pair<Type1,Type2> ( iter1, iter2 );
|
|
}
|
|
|
|
//----------------------------------------------------------------------------------------
|
|
//
|
|
// ---
|
|
template< class InputIt, class UnaryPredicate >
|
|
inline bool all_of( InputIt iter, InputIt last, UnaryPredicate Pred )
|
|
{
|
|
for ( ; iter != last; ++iter )
|
|
{
|
|
if ( !Pred(*iter) )
|
|
{
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
|
|
}; // namespace c3d
|
|
|
|
#endif // __GENERIC_UTILITY_H
|
|
|
|
// eof
|