////////////////////////////////////////////////////////////////////////////////
/** 
  \file
  \brief \ru Упорядоченный массив объектов.
         \en Ordered array of objects. \~

*/
////////////////////////////////////////////////////////////////////////////////

#ifndef __TEMPL_SSARRAY_H
#define __TEMPL_SSARRAY_H


#include <templ_s_array.h>


FORVARD_DECL_TEMPLATE_TYPENAME( class SSArray );
FORVARD_DECL_TEMPLATE_TYPENAME( Type * add_to_array        (       SSArray<Type> &, const Type & el, size_t & indexEl ) );
FORVARD_DECL_TEMPLATE_TYPENAME( size_t find_in_array       ( const SSArray<Type> &, const Type & el ) );
FORVARD_DECL_TEMPLATE_TYPENAME( size_t find_from_array_spec( const SSArray<Type> &, const Type & el, bool & isPresent ) );
FORVARD_DECL_TEMPLATE_TYPENAME( reader & CALL_DECLARATION operator >> ( reader & in,        SSArray<Type> & ref ) );
FORVARD_DECL_TEMPLATE_TYPENAME( writer & CALL_DECLARATION operator << ( writer & out, const SSArray<Type> & ref ) );

//------------------------------------------------------------------------------
/** \brief \ru Упорядоченный массив.
           \en Ordered array. \~
  \details \ru Упорядоченный массив объектов. \n
    У объектов массива должны быть операторы "==" и "<".
    Одинаковые объекты не добавляются. \n
           \en Ordered array of objects. \n
    Elements of the array should have operators "==" and "<".
    The similar objects are not added. \n \~
  \ingroup Base_Tools_Containers
*/
// ---
template <class Type>
class SSArray : protected SArray<Type> {
public :
  SSArray( size_t maxCnt = 0, uint16 delt = 1 ) : SArray<Type>( maxCnt, delt ) {}
  SSArray( const SSArray<Type> & other )        : SArray<Type>( other ) {}
protected:
  SSArray( const SArray<Type> & other )         : SArray<Type>( other ) {}
public:
  using SArray<Type>::operator[];

  using SArray<Type>::Flush;
  using SArray<Type>::HardFlush;
  using SArray<Type>::Adjust;
  using SArray<Type>::Remove;
  using SArray<Type>::RemoveInd;  
  using SArray<Type>::Count;
  using SArray<Type>::MaxIndex;
  using SArray<Type>::GetAddr;
  using SArray<Type>::GetEndAddr;
  using SArray<Type>::Reserve;
  using SArray<Type>::SetSize;
  using SArray<Type>::SetMaxDelta;

  using SArray<Type>::empty;
  using SArray<Type>::size;
  using SArray<Type>::reserve;
  using SArray<Type>::capacity;
  using SArray<Type>::begin;
  using SArray<Type>::end;
  using SArray<Type>::cbegin;
  using SArray<Type>::cend;
  using SArray<Type>::front;
  using SArray<Type>::back;
  using SArray<Type>::clear;
  using SArray<Type>::erase;
  using SArray<Type>::shrink_to_fit;

  Type  * Add ( const Type & );                  // \ru добавить элемент с упорядочиванием по массиву \en add element with sorting 
  Type  * Add ( const Type &, size_t & indexEnt ); // \ru добавить элемент с упорядочиванием по массиву, возвращает индекс \en add element with sorting, returns index of the element 
  // \ru используя эту функцию, пользователь несет всю ответственность за дальнейшую работу сортировки \en When using this function the user is fully responsible for the further work of the sorting process 
  // \ru - сортировка может работать неправильно. \en - sorting may work incorrectly. 
  void    AddSimple( const Type & ent ) { SArray<Type>::Add( ent ); } // \ru Доступ к функции базового класса - добавить элемент в конец массива \en An access to the function of the base class - add an element to the end of the array 

  size_t  Find( const Type & ) const;      // \ru найти элемент в упорядоченном массиве \en find an element in ordered array 
  size_t  RemoveObj( const Type & delObject );

  bool    operator == ( const SSArray<Type> & ) const; // \ru сравнить два массива \en compare two arrays 
  bool    operator != ( const SSArray<Type> & ) const; // \ru сравнить два массива \en compare two arrays 
  bool    operator <  ( const SSArray<Type> & ) const; // \ru сравнить два массива \en compare two arrays 
  void    operator =  ( const SSArray<Type> & arr ) { SArray<Type>::operator = ( arr ); }
  
  // \ru преобразование к базовому классу \en Convert to the base class 
  const SArray<Type>  & BaseClass() const { return *this; }

  size_t  PossibleIndex( const Type & ent, bool & isPresent ) const; // \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_FRIEND Type * add_to_array         TEMPLATE_SUFFIX (       SSArray<Type> &, const Type & el, size_t & indexEl );
  TEMPLATE_FRIEND size_t find_in_array        TEMPLATE_SUFFIX ( const SSArray<Type> &, const Type & el );
  TEMPLATE_FRIEND size_t find_from_array_spec TEMPLATE_SUFFIX ( const SSArray<Type> &, const Type & el, bool & isPresent );

  TEMPLATE_FRIEND reader & CALL_DECLARATION operator >> TEMPLATE_SUFFIX ( reader & in,        SSArray<Type> & ref );
  TEMPLATE_FRIEND writer & CALL_DECLARATION operator << TEMPLATE_SUFFIX ( writer & out, const SSArray<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 * SSArray<Type>::operator new( size_t size ) {
  return ::Allocate( size, typeid(SSArray<Type>).name() );
}

//------------------------------------------------------------------------------
// \ru Перегрузка оператора delete. \en Overloading of the "delete" operator. 
// ---
template <class Type>
inline void SSArray<Type>::operator delete ( void * ptr, size_t size) {
  ::Free( ptr, size, typeid(SSArray<Type>).name() );
}
#endif // __DEBUG_MEMORY_ALLOCATE_FREE_


//-------------------------------------------------------------------------------
// \ru оператор сравнения двух массивов \en an operator of two arrays comparison 
// ---
template <class Type>
inline bool SSArray<Type>::operator == ( const SSArray<Type> & w ) const {
  if ( SArray<Type>::count != w.count )
    return false;

  // \ru OV K6 При размещении в памяти с выравниванием не равным 1, между элементами массива \en OV K6 While the memory allocation with alignment which is not equal 1 between elements of the array  
  // \ru возможно появление "дырок" заполненного случайным мусором, т.к. сравнивать этот мусор \en may appear "holes" filled by random trash, since there is not reason to compare this trash 
  // \ru нам никчему, будем сравнивать содержимое массивов поэлементно (через оператор == объекта) \en we will compare the content of arrays element by element (using the operator == of an object) 
  for ( size_t i = 0; i < SArray<Type>::count; ++i ) {
    if ( !((*this)[i] == w[i]) )
      return false;
  }
  return true;
}


//-------------------------------------------------------------------------------
// \ru оператор сравнения двух массивов \en an operator of two arrays comparison 
// ---
template <class Type>
inline bool SSArray<Type>::operator < ( const SSArray<Type> & w ) const {
  // \ru OV K6 При размещении в памяти с выравниванием не равным 1, между элементами массива \en OV K6 While the memory allocation with alignment which is not equal 1 between elements of the array  
  // \ru возможно появление "дырок" заполненного случайным мусором, т.к. сравнивать этот мусор \en may appear "holes" filled by random trash, since there is not reason to compare this trash 
  // \ru нам никчему, будем сравнивать содержимое массивов поэлементно (через оператор < объекта) \en we will compare the content of arrays element by element (using the operator < of an object) 
  for ( size_t i = 0, c = std_min(SArray<Type>::count, w.count); i < c; i++ ) {
    if ( !((*this)[i] == w[i]) )
      return (bool)((*this)[i] < w[i]);
  }

  if ( SArray<Type>::count != w.count )
    return SArray<Type>::count < w.count;

  return true;
}


//-------------------------------------------------------------------------------
// \ru оператор сравнения двух массивов \en an operator of two arrays comparison 
// ---
template <class Type>
inline bool SSArray<Type>::operator != ( const SSArray<Type> & w ) const {
  return ! ( *this == w );
}


//-------------------------------------------------------------------------------
// \ru добавление объекта в массив \en adding an object to array 
// ---
template <class Type>
inline Type * SSArray<Type>::Add( const Type & el ) {
  size_t indexEl = SYS_MAX_T;
  return add_to_array( *this, el, indexEl );
}


//-------------------------------------------------------------------------------
// \ru добавление объекта в массив \en adding an object to array 
// ---
template <class Type>
inline Type * SSArray<Type>::Add( const Type & el, size_t & indexEl ) {
  return add_to_array( *this, el, indexEl );
}


//------------------------------------------------------------------------------
// \ru удалить элемент из массива \en delete an element from array 
// ---
template <class Type>
inline size_t SSArray<Type>::RemoveObj( const Type & delObject )
{
  size_t ind = Find( delObject );
  if ( ind != SYS_MAX_T )
    RemoveInd( ind );
  return ind;
}


//-------------------------------------------------------------------------------
// \ru поиск объека в массиве \en search of an element in array 
// ---
template <class Type>
inline size_t SSArray<Type>::Find( const Type & el ) const {
  return find_in_array( *this, el );
}


//-------------------------------------------------------------------------------
// \ru найти место в массиве, куда будет добавлен элемент ( без добавления ) \en find a place in the array for adding ann element (adding is not performed) 
// ---
template <class Type>
inline size_t SSArray<Type>::PossibleIndex( const Type & el, bool & isPresent ) const {
  return find_from_array_spec( *this, el, isPresent );
}


//-------------------------------------------------------------------------------
// \ru добавить объект в массив с упорядочиванием \en add an object to the array with ordering 
// ---
template <class Type>
Type * add_to_array( SSArray<Type> & arr, const Type & el, size_t & indexEl )
{
  size_t mx = arr.count - 1;
  size_t mxc = mx;
  size_t mn = 0;

  if ( arr.count > 2 ) {
    while ( mn + 1 < mx ) {  // \ru пока не нашли - ищем \en seek until do not find 
      size_t md = ( mn + mx ) / 2;
      Type & mdE = arr[md];
      if ( mdE < 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 < mdE ) {
        if ( el == arr[mn] ) {
          indexEl = mn;
          return 0;
        }
        mx = md;
      }
      else if ( mdE == (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 );
        return 0; // \ru но это не повод устраивать зависание. \en we have to exit to avoid hang.
      }
    }

    // \ru здесь дублирование кода проверки границ \en here the code of boundaries check is duplicated 
    // \ru объем кода принесен в жертву скорости \en the code is huge but optimized 
    if ( el < arr[0] ) {
      Type * res = arr.InsertInd( 0, el );
      indexEl = 0;
      return res; //arr.parr;
    }
    if ( arr[mxc] < el ) {
      Type * res = arr.SArray<Type>::Add( el );
      indexEl = mxc + 1;
      return res; 
    }

    Type * res = arr.InsertInd( mx, el );
    indexEl = mx;
    return res;
  }

  // \ru проверку на пустоту массива нельзя переносить за проверку границ - \en a check for array emptyness should not be moved outside a boundary check -  
  // \ru можно вылететь (из-за mxc = -1) \en the error may occur (because of mxc = -1) 
  if ( !arr.count ) {
    Type * res = arr.SArray<Type>::Add( el );
    indexEl = 0;
    return res; //arr.parr;
  }

  // \ru здесь дублирование кода проверки границ \en here the code of boundaries check is duplicated 
  // \ru объем кода принесен в жертву скорости \en the code is huge but optimized 
  if ( el < arr[0] ) {
    Type * res = arr.InsertInd( 0, el );
    indexEl = 0;
    return res; 
  }
  if ( arr[mxc] < el ) {
    Type * res = arr.SArray<Type>::Add( el );
    indexEl = mxc + 1;
    return res; 
  }

  if ( arr.count == 2 ) {
    if ( el == arr[0] ) {
      indexEl = 0;
      return 0;
    }
    else
      if ( el == arr[1] ) {
        indexEl = 1;
        return 0;
      }
      else {
        Type * res = arr.InsertInd( 1, el );
        indexEl = 1;
        return res; 
      }
  }

  indexEl = 0;
  return 0;
}


//-------------------------------------------------------------------------------
// \ru найти объект в массиве \en find an object in the array 
// \ru поиск ведется методом половинных делений \en a search is performed by the bisection method 
// ---
template <class Type>
size_t find_in_array( const SSArray<Type> & arr, const Type & el )
{
  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;
      Type & mdE = arr[md];
      if ( mdE < 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 < mdE ) {
        if ( el == arr[mn] )
          return mn;
        mx = md;
      }
      else if ( mdE == 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;
      }
    }

    if ( el < arr[0] )
      return SYS_MAX_T;
    if ( arr[mxc] < el )
      return SYS_MAX_T;
  }
  else {
    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; i < arr.count; i++ )
          if ( el == arr[i] )
            return i;
      }
    }
  }

  return SYS_MAX_T;
}


//-------------------------------------------------------------------------------
// \ru найти объект в массиве \en find an object in the array 
// \ru поиск ведется методом половинных делений \en a search is performed by the bisection method 
// ---
template <class Type>
size_t find_from_array_spec( const SSArray<Type> & arr, const Type & el, bool & isPresent )
{
  isPresent = false;

  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;
}


#endif // __TEMPL_SSARRAY_H