////////////////////////////////////////////////////////////////////////////////
/** 
  \file     
  \brief \ru parray c возможность сортировки по любому признаку 
         \en Array of pointers (of parray type) with ability of sorting by any criteria. \~
*/
////////////////////////////////////////////////////////////////////////////////

#ifndef __TEMPL_PSRT_ARRAY_H
#define __TEMPL_PSRT_ARRAY_H


#include <templ_p_array.h>


#ifdef __FreeBSD__
#include <stdlib.h>
#endif


//------------------------------------------------------------------------------
// \ru константы для поиска \en constants for search 
// ---
enum PArraySortFind {
  // \ru граница выравнивания трудоемкости простого перебора с делением пополам \en balancing boundary of complexity of simple search with bisection 
  // \ru (а) для int ключа \en (a) for integer (int) key  
  // \ru ((4(*) + 4(/)) + 2(== >1) + 2(смещ2)) / (1(== >1) + 1(смещ2)) = 5 трудоемкость одной итерации поиска, \en ((4(*) + 4(/)) + 2(== >1) + 2(смещ2)) / (1(== >1) + 1(смещ2)) = 5 complexity of one iteration of search, 
  // \ru выравнивание при ~ 25 (5 делений(32) - 25 сравнений) \en balancing for ~ 25 (5 bisections (32) - 25 comparisons) 
  // \ru (b) для double ключа \en (b) for double key  
  // \ru ((4(*) + 4(/)) + 2(== >2) + 2(смещ2)) / (1(== >2) + 1(смещ2)) = 4 трудоемкость одной итерации поиска, \en ((4(*) + 4(/)) + 2(== >2) + 2(смещ2)) / (1(== >2) + 1(смещ2)) = 4 complexity of one iteration of search, 
  // \ru выравнивание при ~ 20 (5 делений(32) - 20 сравнений) \en balancing for ~ 20 (5 bisections (32) - 20 comparisons)   
  paf_Flat   = 20,   // \ru для double если меньше 20 элементов простой перебор выгодней \en simple search is more advantageous for double values if the number of elements is less than 20 
  paf_Bytwo  = 4096,
  paf_Byline = 2048,
};


//------------------------------------------------------------------------------
//
// ---
enum PArraySortDivide {
  pad_Two  = 2,
  pad_Line = 10,
};


//------------------------------------------------------------------------------
//
// ---
enum PArraySortMemory {
  pam_1      = 100,
  pam_1Delta = 10,
  pam_2      = 1000,
  pam_2Delta = 200,
  pam_3      = 10000,
  pam_3Delta = 2300,
  pam_4      = 100000,
  pam_4Delta = 27182,
};


//------------------------------------------------------------------------------
//
// ---
enum PResSO {
  pso_More,
  pso_Less,
  pso_Equal,
};


//------------------------------------------------------------------------------
//
// ---
class PArrayReg {
public:
  size_t armin;
  size_t armax;
public:
  PArrayReg( size_t oMin, size_t oMax = SYS_MAX_T )
    : armin( oMin )
    , armax( oMax )
  {}
};


//------------------------------------------------------------------------------
// \ru массив указателей с быстрой сортировкой и поиском \en array of pointers with quick sorting and searching 
// ---
template <class Type>
class PArraySort : public PArray<Type> {
private:
  typedef size_t (*PArSortAddress      )( const Type * );
  typedef size_t (*PArSortObj          )( const void *, const Type * );
  typedef bool   (*PArSortRangeCompFunc)( const void *, const Type *, const Type * );

public:
  PArraySort( size_t i_upper = 5, uint16 i_delta = 5, bool shouldDelete = true ); // \ru конструктор \en constructor 

  void    Add         ( Type * ent           );                 // \ru добавить элемент в конец массива \en add element to the end of array 
  void    AddAt       ( Type * ent, size_t k )  { Insert( k, ent ); }
  void    AddAfter    ( Type * ent, size_t k ); // \ru добавить элемент после указанного \en add element after specified one 
  void    Add         ( PArray<Type> &           ); // \ru добавить массив \en add array 
  void    Add         ( PArray<Type> &, size_t k ); // \ru добавить массив в позицию \en add array to the position 
  void    Insert      ( size_t k, Type * ent ); // \ru вставить элемент перед указанным \en insert element before the specified one 

  void    RemoveRng   ( size_t, size_t, DelType del = defDelete );  // \ru удалить диапазон указателей из массива \en delete a range of pointers from array 
  void    DetachRng   ( size_t, size_t );                           // \ru отцепить из массива диапазон указателей \en detach a range of pointers from array 

  typedef int (*PArSortCompFunc)( const Type **, const Type ** );
  void    Sort        ( PArSortCompFunc, PArrayReg * = nullptr ); // \ru быстрая сортировка в любом диапазоне \en quick sorting in any range
  void    Sort        ( const void *, PArSortRangeCompFunc,  size_t armin = 0, size_t armax = SYS_MAX_T ); // \ru быстрая сортировка в заданном диапазоне \en quick sorting in a given range 
  bool    Find        ( const Type *, PArSortAddress, size_t &, size_t armin = 0, size_t armax = SYS_MAX_T ); // \ru найти адрес в любом поле объекта \en find address in any field of object 
  bool    Find        ( const size_t, PArSortAddress, size_t &, size_t armin = 0, size_t armax = SYS_MAX_T ); // \ru найти адрес в любом поле объекта \en find address in any field of object 
  bool    Find        ( const void *, PArSortObj,     size_t &, size_t armin = 0, size_t armax = SYS_MAX_T ); // \ru найти данный объект в сортированном массиве \en find a given object in sorted array 

  int     FindObj     ( const Type *, PArSortCompFunc, size_t &, PArrayReg * = nullptr ) const; // \ru найти данный объект в сортированном массиве \en find a given object in sorted array
  Type *  AddSort     (       Type *, PArSortCompFunc, size_t & ); // \ru добавить элемент в сортированном порядке \en add element in sorted order 

  void    Inverse     (); // \ru инверсия массива \en inversion of array 

  void    Reserve     ( size_t n ); // \ru зарезервировать место под n элементов \en reserve memory for n elements 

private:
  bool    FindObject  ( const void *, PArSortObj,     size_t &, size_t, size_t ); // \ru найти данный объект в сортированном массиве \en find a given object in sorted array 
  bool    FindAddress ( const size_t, PArSortAddress, size_t &, size_t, size_t ); // \ru найти адрес в любом поле объекта \en find address in any field of object 
  void    SortRange   ( const void *, PArSortRangeCompFunc,  size_t, size_t ); // \ru быстрая сортировка в заданном диапазоне \en quick sorting in a given range 
  void    CatchMemory (); // \ru захват памяти \en capture of memory 
  size_t  CalculateDelta();

private:
  PArraySort( const PArraySort & ); // \ru не реализовано \en not implemented 
  void operator = ( const PArraySort & ); // \ru не реализовано \en not implemented 
};


//-----------------------------------------------------------------------------
// \ru конструктор \en constructor 
// ---
template<class Type>
inline PArraySort<Type>::PArraySort( size_t i_upper, uint16 i_delta, bool shouldDelete )
  : PArray<Type>( i_upper, i_delta, shouldDelete ) {
}


//------------------------------------------------------------------------------
// \ru добавить элемент \en add element 
// ---
template <class Type>
inline void PArraySort<Type>::Add( PArray<Type> & o )
{
  PArray<Type>::AddArray( o );
  if ( PArray<Type>::owns )
    o.OwnsElem( false );
}


//------------------------------------------------------------------------------
// \ru добавить элемент \en add element 
// ---
template <class Type>
inline void PArraySort<Type>::Add( PArray<Type> & o, size_t index )
{
  PArray<Type>::InsertArray( o, index );
  if ( PArray<Type>::owns )
    o.OwnsElem( false );
}


//-----------------------------------------------------------------------------
// \ru добавить элемент \en add element 
// ---
template <class Type>
inline void PArraySort<Type>::Add( Type * ent )
{
  CatchMemory();
  this->operator[](  PArray<Type>::count++ ) = ent;
}


//------------------------------------------------------------------------------
// \ru добавить элемент \en add element 
// ---
template <class Type>
inline void PArraySort<Type>::AddAfter( Type * ent, size_t index )
{
  if ( ! PArray<Type>::count )
    Add( ent );
  else {
    CatchMemory(); // \ru добавить памяти, если все использовано \en add memory if whole allocated memory is used 
    PArray<Type>::AddAfter( ent, index );
  }
}


//------------------------------------------------------------------------------
// \ru вставить элемент \en insert element 
// ---
template <class Type>
inline void PArraySort<Type>::Insert( size_t index, Type * ent )
{
  CatchMemory(); // \ru добавить памяти, если все использовано \en add memory if whole allocated memory is used 
  PArray<Type>::Insert( index, ent );
}


//------------------------------------------------------------------------------
// \ru удалить диапазон из массива \en delete a range from array 
// ---
template <class Type>
void PArraySort<Type>::RemoveRng( size_t startIndex, size_t countRng, DelType del )
{
  C3D_ASSERT(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily

  // \ru если диапазон не пуст и индекс принадлежит массиву \en if range is not empty and index belongs to array 
  if ( countRng && startIndex <  PArray<Type>::count ) {

    // \ru корректируем размер удаляемого региона \en correct the deleted region size 
    if ( startIndex + countRng > PArray<Type>::count )
      countRng = PArray<Type>::count - startIndex;

    // \ru вычислить флаг необходимости удаления объектов \en calculate a flag of necessity to delete objects 
    if ( del == Delete || ( del == defDelete &&  PArray<Type>::owns ) ) {

      // \ru будем удалять \en to delete 
      size_t i = 0;
      for( const Type ** parr =  PArray<Type>::GetAddr() + startIndex; i < countRng; i++, parr++ ) {
        Type * d = (Type*)*parr;
        *parr = nullptr; // \ru сначала обнулим указатель ... \en set pointer to null ...

        C3D_ASSERT( !d || PArray<Type>::nowDeletedElem != d );  // \ru ЯТ - временно \en ЯТ - temporarily 
        PArray<Type>::nowDeletedElem = d;

        delete d;

        PArray<Type>::nowDeletedElem = nullptr;
      }
    }

    // \ru вычислить новую позицию \en calculate a new position 
    size_t newPos = startIndex + countRng;

    // \ru передвинуть элементы в конце на стартовую позицию \en move elements at the end to the start position 
    const Type **parr =  PArray<Type>::GetAddr();

    memcpy( (void*)(parr + startIndex), (void*)(parr + newPos), (PArray<Type>::count - newPos) * SIZE_OF_POINTER );

    PArray<Type>::count -= countRng; // \ru установить новое количество элементов в массиве \en set a new number of elements in array 
  }
}


//------------------------------------------------------------------------------
// \ru Отсоединить от массива диапазон указателей без удаления \en Detach from array a range of pointers without deletion 
// ---
template <class Type>
inline void PArraySort<Type>::DetachRng( size_t startIndex, size_t countRng ) {
  RemoveRng( startIndex, countRng, noDelete );
}


//------------------------------------------------------------------------------
// \ru Определить величину приращения \en Determine a value of increment 
// ---
template <class Type>
inline size_t PArraySort<Type>::CalculateDelta()
{
  if (  PArray<Type>::count > pam_1/*100*/ ) {
    if (  PArray<Type>::count < pam_2/*1000*/ ) {
      if (  PArray<Type>::delta < (uint16)pam_1Delta/*10*/ )
         PArray<Type>::delta = (uint16)pam_1Delta;
    }
    else if (  PArray<Type>::count < pam_3/*10000*/ ) {
      if (  PArray<Type>::delta < (uint16)pam_2Delta/*200*/ )
         PArray<Type>::delta = (uint16)pam_2Delta;
    }
    else if (  PArray<Type>::count < pam_4/*100000*/ ) {
      if (  PArray<Type>::delta < (uint16)pam_3Delta/*2300*/ )
         PArray<Type>::delta = (uint16)pam_3Delta;
    }
    else { // >= 100000
      if (  PArray<Type>::delta < (uint16)pam_4Delta/*27182*/ )
         PArray<Type>::delta = (uint16)pam_4Delta;
    }
  }
  return  PArray<Type>::delta;
}


//-----------------------------------------------------------------------------
// \ru захват большего куска памяти ( если нужно ) \en allocate the larger piece of memory (if it is necessary) 
// ---
template <class Type>
inline void PArraySort<Type>::CatchMemory()
{
  PRECONDITION(  PArray<Type>::nowDeletedElem == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily
  if (  PArray<Type>::upper ==  PArray<Type>::count )
    set_Parray_size( *this, PArray<Type>::upper + CalculateDelta(), false/*clear*/ );
}


//------------------------------------------------------------------------------
// \ru зарезервировать место под n элементов \en reserve memory for n elements 
// ---
template <class Type>
inline void PArraySort<Type>::Reserve( size_t n )
{
  C3D_ASSERT(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily
  // \ru если требуется памяти больше, чем есть сейчас, и больше, чем оказалось бы \en if there is required more memory that exists at the moment and more than it would become 
  // \ru при следующем захвате, то захватить ее \en on the next allocation then allocate it 
  size_t space =  PArray<Type>::upper -  PArray<Type>::count;
  if ( space < n && (space + CalculateDelta() < n) )
    set_Parray_size( *this, PArray<Type>::count + n, false/*clear*/ );
}


//-----------------------------------------------------------------------------
// \ru быстрая сортировка всего массива по признаку заданному функцией fcmp \en quick sort of the whole array with the specified by the function 'fcmp' criteria 
// ---
template<class Type>
inline void PArraySort<Type>::Sort( PArSortCompFunc fcmp, PArrayReg * arReg )
{
  PRECONDITION(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily
  if (  PArray<Type>::count > 1 ) { // \ru если хотя бы два элемента в массиве \en if there are at least two elements in array 
    typedef int (*QCompFunc)( const void*, const void* );
    if ( !arReg ) {
      ::qsort( (void *) PArray<Type>::GetAddr(),  PArray<Type>::count, sizeof(size_t), (QCompFunc)fcmp );
    }
    else if ( arReg->armin < arReg->armax ) { // \ru если сортируемый диапазон правильный \en if the sorted range is correct 
      size_t maxInd = PArray<Type>::count - 1;
      // \ru если минимальная граница меньше максимального элемента в массиве \en if the minimum bound is less than the maximum element in array 
      if ( arReg->armin < maxInd ) {
        if ( arReg->armax > maxInd )
          arReg->armax = maxInd;
        ::qsort( (void *)( PArray<Type>::GetAddr() + arReg->armin), (arReg->armax - arReg->armin + 1), sizeof(size_t), (QCompFunc)fcmp );
      }
    }
  }
}


//-----------------------------------------------------------------------------
// \ru быстрая сортировка в заданном диапазоне по признаку заданному функцией fcmp \en quick sort of the given range with the specified by the function 'fcmp' criteria 
// ---
template<class Type>
inline void PArraySort<Type>::Sort( const void * obj, PArSortRangeCompFunc fcmp, size_t armin, size_t armax )
{
  C3D_ASSERT(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily
  if (  PArray<Type>::count > 1 ) { // \ru если хотя бы два элемента в массиве \en if there are at least two elements in array 
    if ( armax > armin ) { // \ru если диапазон сортировки правильный \en if the sorting range is correct 
      if ( armin < PArray<Type>::count - 1 ) { // \ru если минимальная граница меньше максимального элемента в массиве \en if the minimum bound is less than the maximum element in array 
        if ( armax >= PArray<Type>::count ) // \ru если максимальная граница больше или равна максимальному индексу плюс один \en if the maximum boundis not less than maximum index plus one 
          armax = PArray<Type>::count - 1; // \ru установить armax равным максимальному индексу в массиве \en set 'armax' to be equal to the maximum index in array 
        SortRange( obj, fcmp, armin, armax ); // \ru функция быстрой сортировки \en the quick sort function 
      }
    }
  }
}


//-----------------------------------------------------------------------------
// \ru быстрая сортировка в заданном диапазоне по признаку заданному функцией fcmp \en quick sort of the given range with the specified by the function 'fcmp' criteria 
// ---
template<class Type>
void PArraySort<Type>::SortRange( const void * obj, PArSortRangeCompFunc fcmp, size_t ilo, size_t ihi )
{
  C3D_ASSERT(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily
  size_t lo  = ilo; // \ru нижняя граница \en lower bound 
  size_t hi  = ihi; // \ru верхняя граница \en upper bound 

  const Type * mid = (const Type*)(*this)/*parr*/[(lo + hi) / 2]; // \ru найти значение в середине диапазона \en find the value in the middle of the range 

  do { // \ru до тех пор пока верхняя граница больше или равна нижней \en until the upper bound is not less than the lower bound 
    while ( !fcmp(obj, (const Type*)(*this)/*parr*/[lo], mid ) )
      lo++; // \ru если нет необходимости переставлять нижний индекс \en if there is no reason to change position of the lower index 

    while ( !fcmp(obj, mid, (const Type*)(*this)/*parr*/[hi]) )
      hi--; // \ru если нет необходимости переставлять верхний индекс \en if there is no reason to change position of the upper index 

    if ( lo <= hi ) { // \ru если нижняя граница меньше или равна верхней то \en if the lower bound is not greater than the upper bound then 
      Type *t  = (*this)/*parr*/[lo]; // \ru переставить объекты в массиве \en exchange positions of objects in array 
      (*this)/*parr*/[lo] = (*this)/*parr*/[hi];
      (*this)/*parr*/[hi] = t;
      lo++; // \ru сдвинуть границу \en move the bound 
      hi--;
    }
    else
      break;

  } while ( true );

  if ( hi > ilo ) // \ru рекурсия для верхней и нижней границы \en recursion for upper and lower bounds 
    SortRange( obj, fcmp, ilo, hi );

  if ( lo < ihi )
    SortRange( obj, fcmp, lo, ihi );
}


//-----------------------------------------------------------------------------
// \ru найти адрес в любом поле объекта \en find address in any field of object 
// ---
template<class Type>
inline bool PArraySort<Type>::Find( const size_t address, PArSortAddress fadr, size_t & findedAddress,
                                    size_t armin, size_t armax )
{
  C3D_ASSERT(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily
  bool res = false;

  findedAddress = SYS_MAX_T/*OV_x64 -1*/;

  if (  PArray<Type>::count && armin <  PArray<Type>::count && armax >= armin ) {

    if ( armax >=  PArray<Type>::count ) {
      armax =  PArray<Type>::count;
      armax--;
    }

    findedAddress = armax;
    findedAddress++;

    res = FindAddress( address, fadr, findedAddress, armin, armax );
  }

  return res;
}


//-----------------------------------------------------------------------------
// \ru найти адрес в любом поле объекта \en find address in any field of object 
// ---
template<class Type>
inline bool PArraySort<Type>::Find( const Type * member, PArSortAddress fadr, size_t & findedAddress, size_t armin, size_t armax )
{
  C3D_ASSERT(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily
  return Find( fadr(member), fadr, findedAddress, armin, armax );
}


//------------------------------------------------------------------------------
// \ru найти данный объект в сортированном массиве \en find a given object in sorted array 
// ---
template<class Type>
inline bool PArraySort<Type>::Find( const void * obj, PArSortObj fobj, size_t & findedId, size_t armin, size_t armax )
{
  C3D_ASSERT(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily

  bool res = false;

  findedId = SYS_MAX_T;

  if ( PArray<Type>::count && armin <  PArray<Type>::count && armax >= armin ) {

    if ( armax >=  PArray<Type>::count ) {
      armax = PArray<Type>::count;
      armax--;
    }

    findedId = armax;
    findedId++;

    res = FindObject( obj, fobj, findedId, armin, armax );
  }

  return res;
}


//------------------------------------------------------------------------------
// \ru найти данный объект в сортированном массиве \en find a given object in sorted array 
// ---
template<class Type>
bool PArraySort<Type>::FindObject( const void * obj, PArSortObj fobj, size_t & findedId, size_t armin, size_t armax )
{
  C3D_ASSERT(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily

  bool res = false; // \ru флаг, который указывает существует ли искомый объект в массиве \en flag which specifies whether the required object is in array 

  size_t id  = armax - armin; // \ru количество элементов в диапазоне \en the number of elements in range 

  if ( id < paf_Flat ) { // \ru если количество элементов в диапазоне небольшое, то просматриваем сначала \en if the number of elements in range is not too large then start search from the beginning 

    for ( size_t i = armin; i <= armax; i++ ) { // \ru (т.к. одно умножение в 4 раза дольше сравнения) \en (because one multiplying takes in 4 times more time than a comparison) 
      size_t pso = fobj( obj, (*this)/*parr*/[i] );

      if ( !(pso == pso_More) ) { // \ru возвращаем номер вершины \en return a number of vertex 
        res = pso == pso_Equal;
        findedId = i;
        break;
      }
    }
  }
  else {
    // \ru находим вершину находящуюся в середине диапазона (целочисленное деление) \en find a vertex in the middle of range (integer division) 
    size_t half = id / pad_Two + armin;
    size_t pso  = fobj( obj, (*this)/*parr*/[half] );

    if ( pso == pso_More )
      armin = half;
    else
      armax = half;

    res = FindObject( obj, fobj, findedId, armin, armax ); // \ru рекурсивно вызываем функцию с новым диапазоном \en recursively call the function with new range 
  }

  return res;
}


//-----------------------------------------------------------------------------
// \ru найти адрес в любом поле объекта \en find address in any field of object 
// ---
template<class Type>
bool PArraySort<Type>::FindAddress( const size_t address, PArSortAddress fadr, size_t & findedAddress, size_t armin, size_t armax )
{
  C3D_ASSERT(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily

  bool res = false; // \ru флаг, который указывает существует ли искомый адресс в массиве \en flag which specifies whether the required address is in array 
  size_t id  = armax - armin; // \ru количество элементов в диапазоне \en the number of elements in range 

  if ( id < paf_Flat ) { // \ru если количество элементов в диапазоне не большое, то просматривем сначала \en if the number of elements in range is not too large then start search from the beginning 

    for ( size_t i = armin; i <= armax; i++ ) { // \ru (т.к. одно умножение в 4 раза дольше сравнения) \en (because one multiplying takes in 4 times more time than a comparison) 
      size_t currentAddress = fadr( (*this)/*parr*/[i] );

      if ( !(currentAddress < address) ) { // \ru возвращаем номер вершины, \en return a number of vertex, 
        res = currentAddress == address;
        findedAddress = i;
        break;
      }
    }
  }
  else {
    // \ru если количество элементов в массиве достаточное, то деление пополам \en if the number of elements in array is enough then perform a bisection 
    if ( id < paf_Bytwo ) {
      // \ru находим вершину находящуюся в середине диапазона (целочисленное деление) \en find a vertex in the middle of range (integer division) 
      size_t half        = id / pad_Two + armin;
      size_t addressHalf = fadr( (*this)/*parr*/[half] );

      if ( addressHalf < address )
        armin = half;
      else
        armax = half;

      res = FindAddress( address, fadr, findedAddress, armin, armax ); // \ru рекурсивно вызываем функцию с новым диапазоном \en recursively call the function with new range 
    }
    else { // \ru если вершин очень много в массиве, то используем линейную аппроксимацию \en if there are too many vertices in array then use a linear approximation 
      size_t minAddress = fadr( (*this)/*parr*/[armin] ); // \ru минимальный адрес \en minimal address 

      if ( minAddress != address ) { // \ru если не равен искомому адресу \en if it is not equal to the required address 
        size_t maxAddress = fadr( (*this)/*parr*/[armax] ); // \ru максимальный адрес в массиве \en maximal address in array 

        size_t d = maxAddress - minAddress; // \ru диапазон адресов в массиве \en range of addresses in array 
        size_t i = ( address - minAddress ) * id / d + armin; // \ru предполагаемый индекс искомого адреса \en the expected index of the required address 

        if ( i < armin ) // \ru выровнять диапазон \en justify the range 
          i = armin;
        else if ( i > armax )
          i = armax;

        size_t middleAddress = fadr( (*this)/*parr*/[i] ); // \ru найти адрес вершины по данному индексу \en find the address of vertex by the given index 

        if ( middleAddress < address ) { // \ru если искомый адрес больше \en if the required address is greater 

          armin = i; // \ru установить нижнюю границу \en set the lower bound 
          id    = armax - armin; // \ru вычислить новый диапазон индексов \en calculate the new range of indices 

          if ( id > paf_Byline ) { // \ru если он достаточно большой оценить верхнюю границу \en if it is rather large then estimate the upper bound 
            size_t h        = id / pad_Line + armin;
            size_t haddress = fadr( (*this)/*parr*/[h] );

            if ( haddress < address )
              armin = h;
            else
              armax = h;
          }

          res = FindAddress( address, fadr, findedAddress, armin, armax );
        }
        else { // \ru если искомый адрес меньше \en if the required address is less 

          armax = i; // \ru установить верхнюю границу \en set the upper bound 
          id    = armax - armin; // \ru вычислить новый диапазон индексов \en calculate the new range of indices 

          if ( id > paf_Byline ) { // \ru если он достаточно большой оценить нижнюю границу \en if it is rather large then estimate the lower bound 
            size_t h        = armax - id / pad_Line;
            size_t haddress = fadr( (*this)/*parr*/[h] );

            if ( haddress < address )
              armin = h;
            else
              armax = h;
          }

          res = FindAddress( address, fadr, findedAddress, armin, armax );
        }
      }
      else { // \ru иначе искомая вершина находится в начале массива \en otherwise the required value is situated in the begin of array 
        res           = true;
        findedAddress = armin;
      }
    }
  }

  return res;
}


//------------------------------------------------------------------------------
// \ru найти данный объект в сортированном массиве (!!!obj - обязан быть первым в fcmp!!!) \en find the given object in sorted array (!!! 'obj'  sould be the first in 'fcmp' !!!) 
// ---
template<class Type>
int PArraySort<Type>::FindObj( const Type * obj, PArSortCompFunc fcmp, size_t & iFnd, PArrayReg * arReg ) const
{
  PRECONDITION(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily
  if ( (PArray<Type>::count) > 0 ) {
    size_t id = PArray<Type>::count; // \ru количество элементов в диапазоне \en the number of elements in range 
    id--;
    size_t armin, armax, half;
    if ( !arReg ) {
      if ( fcmp((const Type **)&obj, (const Type **)&((*this)[id])) > 0 ) {
        iFnd = id;
        return 2;
      }
      armin = 0;
      armax = id;
    }                                         
    else {
      if ( arReg->armax < id ) {
        if ( fcmp((const Type **)&obj, (const Type **)&((*this)[arReg->armax])) > 0 ) {
          iFnd = arReg->armax;
          return 1;
        }
        armax = arReg->armax;
      }
      else {
        if ( fcmp((const Type **)&obj, (const Type **)&((*this)[id])) > 0 ) {
          iFnd = id;
          return 2;
        }
        armax = id;
      }
      armin = ( (arReg->armin < armax) ? arReg->armin : armax );
      id = ( armax - armin );
    }
    int ires = fcmp( (const Type **)&obj, (const Type **)&((*this)[armin]) );
    if ( ires <= 0 ) { // \ru возвращаем номер вершины, \en return a number of vertex, 
      iFnd = armin;
      return ires;
    }
    while ( id > paf_Flat ) {
      id /= 2;
      half = id + armin;
      ires = fcmp( (const Type **)&obj, (const Type **)&((*this)[half]) );
      if ( ires > 0 ) {
        armin = half;
      }
      else if ( ires < 0 ) {
        armax = half;
      }
      else {
        iFnd = half;
        while ( (half > 0) && !fcmp((const Type **)&obj, (const Type **)&((*this)[--half])) )
          iFnd = half;
        return 0;
      }
    }
    // \ru если количество элементов в диапазоне не большое, то просматриваем сначала \en if the number of elements in range is not too large then start search from the beginning 
    for ( size_t i = armin; i <= armax; i++ ) { // \ru (т.к. одно умножение в 4 раза дольше сравнения) \en (because one multiplying takes in 4 times more time than a comparison) 
      ires = fcmp( (const Type **)&obj, (const Type **)&((*this)[i]) );
      if ( ires <= 0 ) { // \ru возвращаем номер вершины, \en return a number of vertex, 
        iFnd = i;
        return ires;
      }
    }
    iFnd = armax;
    return 1;
  }
  return -2;
}


//------------------------------------------------------------------------------
// \ru добавить элемент в сортированном порядке \en add element in sorted order 
// ---
template<class Type>
inline Type * PArraySort<Type>::AddSort( Type * obj, PArSortCompFunc fcmp, size_t & iFnd )
{
  PRECONDITION(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily
  int ires = FindObj( obj, fcmp, iFnd );
  if ( (ires == -2) || (ires == 2) ) {
    iFnd = ( (ires == -2) ? 0 : PArray<Type>::count );
    Add( obj );
  }
  else
    if ( ires == -1 )
      AddAt( obj, iFnd );

  return ires ? (*this)/*parr*/[iFnd] : nullptr;
}


//------------------------------------------------------------------------------
// \ru инверсия массива \en inversion of array 
// ---
template<class Type>
void PArraySort<Type>::Inverse()
{
  C3D_ASSERT(  PArray<Type>::nowDeletedElem  == nullptr ); // \ru ЯТ - временно \en ЯТ - temporarily

  if (  PArray<Type>::count ) {
    size_t endI = PArray<Type>::count - 1; // \ru проверено count > 0 \en count > 0 validated 
    size_t fstI = 0;

    while ( (ptrdiff_t)fstI < (ptrdiff_t)endI ) {

      Type * fstObj = (*this)/*parr*/[fstI]; // \ru запомнить указатель на объект (это копия указателя!!!) \en remember the pointer to the object (this is the copy of the pointer!!!) 

      (*this)/*parr*/[fstI] = (*this)/*parr*/[endI];
      (*this)/*parr*/[endI] = fstObj;

      fstI++;
      endI--;
    }
  }
}


#endif // __TEMPL_PSRT_ARRAY_H