SaraP
432 lines
21 KiB
C++
432 lines
21 KiB
C++
////////////////////////////////////////////////////////////////////////////////
|
|
/**
|
|
\file
|
|
\brief \ru Упорядоченный массив указателей.
|
|
\en Ordered array of pointers. \~
|
|
|
|
*/
|
|
////////////////////////////////////////////////////////////////////////////////
|
|
|
|
#ifndef __TEMPL_SP_ARRAY_H
|
|
#define __TEMPL_SP_ARRAY_H
|
|
|
|
|
|
#include <templ_p_array.h>
|
|
|
|
|
|
////////////////////////////////////////////////////////////////////////////////
|
|
//
|
|
// \ru упорядоченный массив указателей \en ordered array of pointers
|
|
// \ru у объектов массива должны быть операторы "==" и "<" \en objects of the array should have operators "==" and "<"
|
|
// \ru одинаковые объекты не добавляются \en the similar objects are not added
|
|
//
|
|
////////////////////////////////////////////////////////////////////////////////
|
|
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( class SPArray );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( Type * add_to_array ( SPArray<Type> &, Type * ent, size_t & indexEnt ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( size_t find_from_array ( const SPArray<Type> &, const Type * ent ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( size_t find_from_array_spec( const SPArray<Type> &, const Type * ent, bool & isPresent ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( reader & CALL_DECLARATION operator >> ( reader & in, SPArray<Type> & ref ) );
|
|
FORVARD_DECL_TEMPLATE_TYPENAME( writer & CALL_DECLARATION operator << ( writer & out, const SPArray<Type> & ref ) );
|
|
|
|
template <class Type>
|
|
class SPArray : protected PArray<Type> {
|
|
public :
|
|
SPArray( size_t maxCnt = 0, uint16 delt = 1, bool shouldDelete = true )
|
|
: PArray<Type>( maxCnt, delt, shouldDelete ) {}
|
|
|
|
using PArray<Type>::OwnsElem;
|
|
using PArray<Type>::Delta;
|
|
using PArray<Type>::Upper;
|
|
using PArray<Type>::Flush;
|
|
using PArray<Type>::HardFlush;
|
|
using PArray<Type>::Adjust;
|
|
using PArray<Type>::RemoveInd;
|
|
using PArray<Type>::Count;
|
|
using PArray<Type>::MaxIndex;
|
|
using PArray<Type>::operator[];
|
|
using PArray<Type>::Reserve;
|
|
using PArray<Type>::SetSize;
|
|
using PArray<Type>::GetLast;
|
|
using PArray<Type>::FindIt;
|
|
|
|
using PArray<Type>::empty;
|
|
using PArray<Type>::size;
|
|
using PArray<Type>::reserve;
|
|
using PArray<Type>::capacity;
|
|
using PArray<Type>::begin;
|
|
using PArray<Type>::end;
|
|
using PArray<Type>::front;
|
|
using PArray<Type>::back;
|
|
using PArray<Type>::clear;
|
|
|
|
Type * Add( Type * ); // \ru добавить элемент с упорядочиванием по массиву \en add element with sorting
|
|
Type * Add( Type *, size_t & indexEnt );// \ru добавить элемент с упорядочиванием по массиву, возвращает индекс \en add element with sorting, returns index of the element
|
|
|
|
// \ru После "простого" добавления нет возможности восстановить сортированность массива \en After a "simple" adding there is no possibility to recover the sorting of the array
|
|
void AddSimple ( Type * ent ) { PArray<Type>::Add( ent ); } // \ru Доступ к функции базового класса - добавить элемент в конец массива \en An access to the function of the base class - add an element to the end of the array
|
|
// \ru Доступ к функции базового класса - добавить массив в конец массива \en An access to the function of the base class - add an array to the end of the array
|
|
bool AddArraySimple( const RPArray<Type> & arr ) { return PArray<Type>::AddArray( arr ); }
|
|
Type * RemoveObj( Type * delObject, DelType = defDelete ); // \ru удалить элемент из массива \en delete an element from array
|
|
// \ru Доступ к функции базового класса - удалить элемент из массива \en An access to the function of the base class - delete an element from the array
|
|
Type * RemoveObjSimple( Type * delObject, DelType delType = defDelete ) { return PArray<Type>::RemoveObj( delObject, delType ); } ; // \ru удалить элемент из массива \en delete an element from array
|
|
|
|
size_t Find( const Type * ) const; // \ru найти элемент в упорядоченном массиве \en find an element in ordered array
|
|
size_t PossibleIndex( const Type *, bool & isPresent ) const; // \ru найти место в массиве, куда будет добавлен элемент ( без добавления ) \en find a place in the array for adding an element (adding is not performed)
|
|
// \ru на выходе : isPresent == true - элемент уже в массиве \en in output : isPresent == true - the element is already in the array
|
|
bool IsExist( const Type * ) const; // \ru true если элемент найден \en true if the element was found
|
|
|
|
TEMPLATE_FRIEND Type * add_to_array TEMPLATE_SUFFIX ( SPArray<Type> &, Type * ent, size_t & indexEnt );
|
|
TEMPLATE_FRIEND size_t find_from_array TEMPLATE_SUFFIX ( const SPArray<Type> &, const Type * ent );
|
|
TEMPLATE_FRIEND size_t find_from_array_spec TEMPLATE_SUFFIX ( const SPArray<Type> &, const Type * ent, bool & isPresent );
|
|
|
|
private:
|
|
SPArray( const SPArray<Type> & ); // \ru запрещено !!! \en forbidden !!!
|
|
void operator = ( const SPArray<Type> & ); // \ru запрещено !!! \en forbidden !!!
|
|
|
|
// \ru Т.к. наследование private, то сделаем здесь операторы чтения-записи \en Since there is a private inheritance, then make here operators of reading/writing
|
|
//ID K8 KNOWN_OBJECTS_RW_REF_OPERATORS( SPArray<Type> )
|
|
TEMPLATE_FRIEND reader & CALL_DECLARATION operator >> TEMPLATE_SUFFIX ( reader & in, SPArray<Type> & ref );
|
|
TEMPLATE_FRIEND writer & CALL_DECLARATION operator << TEMPLATE_SUFFIX ( writer & out, const SPArray<Type> & ref );
|
|
|
|
#ifdef __DEBUG_MEMORY_ALLOCATE_FREE_
|
|
public:
|
|
void * operator new ( size_t );
|
|
void operator delete ( void *, size_t );
|
|
#endif // __DEBUG_MEMORY_ALLOCATE_FREE_
|
|
};
|
|
|
|
|
|
#ifdef __DEBUG_MEMORY_ALLOCATE_FREE_
|
|
//------------------------------------------------------------------------------
|
|
// \ru Перегрузка оператора new. \en Overloading of the "new" operator.
|
|
// ---
|
|
template <class Type>
|
|
inline void * SPArray<Type>::operator new( size_t size ) {
|
|
return ::Allocate( size, typeid(SPArray<Type>).name() );
|
|
}
|
|
|
|
//------------------------------------------------------------------------------
|
|
// \ru Перегрузка оператора delete. \en Overloading of the "delete" operator.
|
|
// ---
|
|
template <class Type>
|
|
inline void SPArray<Type>::operator delete( void * ptr, size_t size ) {
|
|
::Free( ptr, size, typeid(SPArray<Type>).name() );
|
|
}
|
|
#endif // __DEBUG_MEMORY_ALLOCATE_FREE_
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
// \ru добавить элемент с упорядочиванием по массиву \en add element with sorting
|
|
// ---
|
|
template <class Type>
|
|
inline Type * SPArray<Type>::Add( Type * el )
|
|
{
|
|
size_t index;
|
|
return add_to_array( *this, el, index );
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
// \ru добавить элемент с упорядочиванием по массиву, возвращает индекс \en add element with sorting, returns index of the element
|
|
// ---
|
|
template <class Type>
|
|
inline Type* SPArray<Type>::Add( Type * el, size_t & indexEl ) {
|
|
return add_to_array( *this, el, indexEl );
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
// \ru поиск объекта в массиве \en search of an element in array
|
|
// ---
|
|
template <class Type>
|
|
inline size_t SPArray<Type>::Find( const Type * el ) const {
|
|
return find_from_array( *this, el );
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
// \ru Есть ли в массиве такой указатель \en Whether such pointer exists in the array
|
|
// ---
|
|
template <class Type>
|
|
inline bool SPArray<Type>::IsExist( const Type * el ) const {
|
|
return find_from_array( *this, el ) != SYS_MAX_T;
|
|
}
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
// \ru удалить элемент из массива (по указателю) \en delete an element from array (by the pointer)
|
|
// ---
|
|
template <class Type>
|
|
inline Type * SPArray<Type>::RemoveObj( Type * delObject, DelType del )
|
|
{
|
|
PRECONDITION( PArray<Type>::nowDeletedElem == nullptr ); // \ru Временно, для отладки \en Temporarily, for debugging
|
|
size_t i = find_from_array( *this, delObject );
|
|
return ( i != SYS_MAX_T ) ? RemoveInd( i, del ) : nullptr;
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
// \ru найти место в массиве, куда будет добавлен элемент ( без добавления ) \en find a place in the array for adding ann element (adding is not performed)
|
|
// \ru на выходе : isPresent == true - элемент уже в массиве \en in output : isPresent == true - the element is already in the array
|
|
// ---
|
|
template <class Type>
|
|
inline size_t SPArray<Type>::PossibleIndex( const Type * el, bool & isPresent ) const {
|
|
return find_from_array_spec( *this, el, isPresent );
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
// \ru добавление объекта в массив с упорядочиванием \en adding an object to the array with ordering
|
|
// ---
|
|
template <class Type>
|
|
Type * add_to_array( SPArray<Type> & arr, Type * el, size_t & indexEl )
|
|
{
|
|
if ( el == nullptr ) // \ru LF_Linux: добавил проверку на nullptr \en LF_Linux: added a check for nullptr
|
|
return nullptr;
|
|
size_t mx = arr.count - 1;
|
|
size_t mxc = mx;
|
|
size_t mn = 0;
|
|
|
|
// \ru общий случай - элементов больше двух \en the common case - the number of elements is more than two
|
|
if ( arr.count > 2 ) {
|
|
while ( mn + 1 < mx ) { // \ru пока не нашли - ищем \en seek until do not find
|
|
size_t md = ( mn + mx ) / 2;
|
|
if ( *arr[md] < *el ) {
|
|
if ( *el == *arr[mx] ) {
|
|
indexEl = mx;
|
|
return 0;
|
|
}
|
|
mn = md;
|
|
}
|
|
// \ru по логике правильнее было бы проверять сначала меньше, потом тождественно, а затем, уже \en it would be better to check at first whether it is less, then whether it is equal and only after this
|
|
// \ru без сравнения - делать вывод что больше. \en conclude which is greater without comparison.
|
|
// \ru НО! оператор сравнения, как правило более быстрый, чем оператор тождественности, \en BUT! the comparison operator is generally faster than identity operator,
|
|
// \ru и заведомо более часто используется( тождественно - финишная операция в поиске ) \en and it is used more often (identity check is the last operation in search)
|
|
// \ru и если поставить проверку тождественности впереди "больше" - можно получить торможение \en and if the identity check will be placed before the "greater" check then there may occur an inhibition
|
|
// \ru на тяжелых операторах \en on heavy operators
|
|
// \ru Кроме того, все три проверки делаются, дабы не отказывать программистам в их праве делать \en -
|
|
// \ru ошибки при написании операторов сравнения и тождественности и потом их с комфортом исправлять. \en -
|
|
else if ( *el < *arr[md] ) {
|
|
if ( *el == *arr[mn] ) {
|
|
indexEl = mn;
|
|
return 0;
|
|
}
|
|
mx = md;
|
|
}
|
|
else if ( *arr[md] == (Type&)*el ) {
|
|
indexEl = md;
|
|
return 0;
|
|
}
|
|
// \ru если попадаем сюда - значит некорректно написаны операторы "тождественно" и сравнения \en if we are here then operators of identity check and comparison are not correct
|
|
else {
|
|
PRECONDITION( 0 );
|
|
indexEl = SYS_MAX_T;
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
if ( *el < *arr[0] ) {
|
|
arr.Insert( 0, el );
|
|
indexEl = 0;
|
|
return arr[0]; //arr.parr;
|
|
}
|
|
if ( *arr[mxc] < *el ) {
|
|
arr.PArray<Type>::Add( el );
|
|
indexEl = mxc + 1;
|
|
return arr[indexEl]; //arr.parr + indexEl;
|
|
}
|
|
|
|
arr.Insert( mx, el );
|
|
indexEl = mx;
|
|
return arr[mx];//arr.parr + mx;
|
|
}
|
|
|
|
// \ru специальные случаи \en special cases
|
|
// \ru массив пустой - просто добавляем \en the array is empty - simply add
|
|
// \ru проверку на пустоту массива нельзя переносить за проверку границ - \en a check for array emptiness should not be moved outside a boundary check -
|
|
// \ru можно вылететь (из-за mxc = -1) \en the error may occur (because of mxc = -1)
|
|
if ( !arr.count ) {
|
|
arr.PArray<Type>::Add( el );
|
|
indexEl = 0;
|
|
return arr[0]; //arr.parr;
|
|
}
|
|
|
|
// \ru SA K6 элемент за границами массива - добавляем \en SA K6 an element is out of bounds - add it
|
|
if ( *el < *arr[0] ) {
|
|
arr.Insert( 0, el );
|
|
indexEl = 0;
|
|
return arr[0]; //arr.parr;
|
|
}
|
|
if ( *arr[mxc] < *el ) {
|
|
arr.PArray<Type>::Add( el );
|
|
indexEl = mxc + 1;
|
|
return arr[indexEl]; //arr.parr + indexEl;
|
|
}
|
|
|
|
// \ru SA K6 элемент не за границами массива и массив содержит 2 элемента \en SA K6 an element is not outside the array's bounds and the array consists of 2 elements
|
|
if ( arr.count == 2 ) {
|
|
if ( *el == *arr[0]/*arr.parr*/ ) {
|
|
indexEl = 0;
|
|
return 0;
|
|
}
|
|
else
|
|
if ( *el == *arr[1]/*arr.parr[1]*/ ) {
|
|
indexEl = 1;
|
|
return 0;
|
|
}
|
|
else {
|
|
arr.Insert( 1, el );
|
|
indexEl = 1;
|
|
return arr[1]; // arr.parr + 1;
|
|
}
|
|
}
|
|
|
|
indexEl = 0;
|
|
return 0;
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
// \ru поиск объекта в массиве \en search of an element in array
|
|
// \ru поиск ведется методом половинных делений \en a search is performed by the bisection method
|
|
// ---
|
|
template <class Type>
|
|
size_t find_from_array_spec( const SPArray<Type> & arr, const Type * el, bool & isPresent )
|
|
{
|
|
isPresent = false;
|
|
|
|
if ( el == nullptr ) // \ru LF_Linux: добавил проверку на nullptr \en LF_Linux: added a check for nullptr
|
|
return SYS_MAX_T;
|
|
|
|
if ( !arr.count || *el < *arr/*.parr*/[0] )
|
|
return 0;
|
|
|
|
size_t mx = arr.count - 1;
|
|
|
|
if ( *arr/*.parr*/[mx] < *el )
|
|
return mx + 1;
|
|
|
|
if ( arr.count == 1 ) { // \ru значит *el == *parr[0] \en it means *el == *parr[0]
|
|
isPresent = true;
|
|
return 0;
|
|
}
|
|
|
|
if ( arr.count == 2 ) { // \ru значит между 0 и 1 \en between 0 and 1
|
|
if (*el == *arr/*.parr*/[0]) {
|
|
isPresent = true;
|
|
return 0;
|
|
}
|
|
else {
|
|
if (*el == *arr/*.parr*/[1]) isPresent = true;
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
size_t mn = 0;
|
|
|
|
while ( mn + 1 < mx ) { // \ru пока не нашли - ищем \en seek until do not find
|
|
if (*el == *arr/*.parr*/[mn]) {
|
|
isPresent = true;
|
|
return mn;
|
|
}
|
|
else {
|
|
if ( *el == *arr/*.parr*/[mx] ) {
|
|
isPresent = true;
|
|
return mx;
|
|
}
|
|
else {
|
|
size_t md = (mn + mx) / 2;
|
|
if ( *arr/*.parr*/[md] < *el )
|
|
mn = md;
|
|
else if ( *el < *arr/*.parr*/[md] )
|
|
mx = md;
|
|
else if ( *arr/*.parr*/[md] == (Type&)*el ) {
|
|
isPresent = true;
|
|
return md;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return mx;
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------------
|
|
// \ru поиск объекта в массиве \en search of an element in array
|
|
// \ru поиск ведется методом половинных делений \en a search is performed by the bisection method
|
|
// \ru Входные параметры: \en Input parameters:
|
|
// \ru arr - массив элементов \en arr - the array of elements
|
|
// \ru el - объект для поиска \en el - the object for the search
|
|
// \ru Возвращаемое значение: \en The returned value:
|
|
// \ru Индекс объекта в массиве. Если объект не был найден, то возращается SYS_MAX_T. \en index of an object in array If the object was not found then SYS_MAX_T is returned.
|
|
// ---
|
|
template <class Type>
|
|
size_t find_from_array( const SPArray<Type> & arr, const Type * el )
|
|
{
|
|
if ( el == nullptr ) // \ru LF_Linux: добавил проверку на nullptr \en LF_Linux: added a check for nullptr
|
|
return SYS_MAX_T;
|
|
// \ru общий случай - элементов больше 11 //LF_Linux: откуда 11??? \en the common case - the number of elements is more than 11 //LF_Linux: why 11??
|
|
if ( arr.count > 11 ) {
|
|
size_t mx = arr.count - 1;
|
|
size_t mxc = mx;
|
|
size_t mn = 0;
|
|
|
|
while ( mn + 1 < mx ) { // \ru пока не нашли - ищем \en seek until do not find
|
|
size_t md = ( mn + mx ) / 2;
|
|
if ( *arr[md] < *el ) {
|
|
if ( *el == *arr[mx] )
|
|
return mx;
|
|
mn = md;
|
|
}
|
|
// \ru по логике правильнее было бы проверять сначала меньше, потом тождественно, а затем, уже \en it would be better to check at first whether it is less, then whether it is equal and only after this
|
|
// \ru без сравнения - делать вывод что больше. \en conclude which is greater without comparison.
|
|
// \ru НО! оператор сравнения, как правило более быстрый, чем оператор тождественности, \en BUT! the comparison operator is generally faster than identity operator,
|
|
// \ru и заведомо более часто используется( тождественно - финишная операция в поиске ) \en and it is used more often (identity check is the last operation in search)
|
|
// \ru и если поставить проверку тождественности впереди "больше" - можно получить торможение \en and if the identity check will be placed before the "greater" check then there may occur an inhibition
|
|
// \ru на тяжелых операторах \en on heavy operators
|
|
// \ru Кроме того, все три проверки делаются, дабы не отказывать программистам в их праве делать \en -
|
|
// \ru ошибки при написании операторов сравнения и тождественности и потом их с комфортом исправлять. \en -
|
|
else if ( *el < *arr[md] ) {
|
|
if ( *el == *arr[mn] )
|
|
return mn;
|
|
mx = md;
|
|
}
|
|
else if ( *arr[md] == *el )
|
|
return md;
|
|
// \ru если попадаем сюда - значит некорректно написаны операторы "тождественно" и сравнения \en if we are here then operators of identity check and comparison are not correct
|
|
else {
|
|
PRECONDITION( 0 );
|
|
return SYS_MAX_T;
|
|
}
|
|
}
|
|
|
|
// \ru проверка по границам \en check by bounds
|
|
if ( *el < *arr[0] )
|
|
return SYS_MAX_T;
|
|
if ( *arr[mxc] < *el )
|
|
return SYS_MAX_T/*-1*/;
|
|
}
|
|
else {
|
|
// \ru специальные случаи \en special cases
|
|
if ( arr.count == 1 )
|
|
return *el == *arr[0] ? 0 : SYS_MAX_T;
|
|
else {
|
|
if ( arr.count == 2 )
|
|
return *el == *arr[0] ? 0 : ((*el == *arr[1]) ? 1 : SYS_MAX_T);
|
|
else {
|
|
// 2 < count <= 11
|
|
for( size_t i = 0, count = arr.count; i < count; i++ )
|
|
if ( *el == *arr[i] )
|
|
return i;
|
|
}
|
|
}
|
|
}
|
|
|
|
return SYS_MAX_T;
|
|
}
|
|
|
|
|
|
#endif // __TEMPL_SP_ARRAY_H
|