util_stl_dtk.hpp

Go to the documentation of this file.

#ifndef UTIL_STL_DTK_HPP_
#define UTIL_STL_DTK_HPP_
 
#include "def/define.h"
#include "dtk/config.hpp"
#include <iostream>
#include <type_traits>
#include <utility>
 
template <typename T1,typename T2>
class Dtk_pair;
 
void Dtk_ThrowOverflowException();
 
// #ifdef _DEBUG
// #define _DEBUG_DTK
// #endif
 
template<typename T>
struct Dtk_greater
{
     int operator()(const T& t1,const T& t2) const {return t1>t2;}
};
 
template<typename T>
struct Dtk_less
{
     int operator()(const T& t1,const T& t2) const {return t1<t2;}
};
 
 
 
template<typename T>
void Dtk_swap( T& a, T& b )
{
     T tmp = std::move( a );
     a = std::move( b );
     b = std::move( tmp );
}
 
template <typename T>
class Dtk_tab
{
     struct allocator_from_t
     {
          T * operator()( std::pair<T *, Dtk_Size_t> src, Dtk_Size_t n )
          {
               T * out = new T[ n ];
#if !defined( _MSC_VER ) || _MSC_VER >= 1700 // at least vs12
               do_move_if( src.first, src.first + src.second, out, std::integral_constant<bool, std::is_move_assignable<T>::value>() );
#else
               do_move_if( src.first, src.first + src.second, out, std::integral_constant<bool, false>() );
#endif
               return out;
          }
     private:
          void do_move_if( T * begin, T * end, T * dst, std::true_type )
          {
               for( ; begin != end; ( void )( ++begin ), ( void )( ++dst ) )
                    *dst = std::move( *begin );
          }
          void do_move_if( T * begin, T * end, T * dst, std::false_type )
          {
               for( ; begin != end; ( void )( ++begin ), ( void )( ++dst ) )
                    *dst = *begin;
          }
     };
private:
     T* v;
     Dtk_Size_t nb;
     Dtk_Size_t rsv;
     T* _dtk_doublerealloc(Dtk_Size_t s)
     {
#if 0
          T* ex = v;
          v=new T[s];
          Pdtk_Assert(s>=nb);
          Pdtk_Assert(v!=NULL);
          if (s >= nb)
          {
               for (Dtk_Size_t i = 0; i < nb; i++)
                    v[i] = ex[i];
          }
          return ex;
#else
          Pdtk_Assert( s >= nb );
          auto old = v;
          if( s >= nb )
               v = allocator_from_t()( std::make_pair( old, nb ), s );
          else
               v = new T[ s ];
          return old;
#endif
     }
private:
     /*template <typename comp>
     int _partition(int top, int bottom,const comp& C)
     {//http://mathbits.com/mathbits/compsci/Arrays/Quick.htm
          //T x = v[top];       //crash pour des tableaux de 30000+ elts
          assert((top + bottom) / 2 < (int) nb);
          T x = v[ (top + bottom) / 2]; 
          int i = top - 1;
          int j = bottom + 1;
          T temp;
          do
          {
               do      
               {
                    j --;
                    assert(j<(int)nb);
               }while (C(x,v[j]));//while (C(v[j],x));// //chngt car le tri etait inverse CT le 09-01-07
 
               do  
               {
                    i++;
                    assert(i<(int)nb);
               } while (C(v[i],x));//while (C(x,v[i]));// //chngt car le tri etait inverse CT le 09-01-07
 
               if (i < j)
               { 
                    assert(i<(int)nb);
                    assert(j<(int)nb);
                    temp = v[i];    // switch elements at positions i and j
                    v[i] = v[j];
                    v[j] = temp;
               }
          }while (i < j);   
          return j;           // returns middle index 
     }
     template <typename comp>
     void _quicksort(int top, int bottom,const comp& C)
     {
          if (top < bottom)
          {
               int middle = _partition(top, bottom,C);
               assert(middle<bottom);
               _quicksort(top, middle,C);   // sort top partition
               assert(middle+1>top);
               _quicksort(middle+1, bottom,C);    // sort bottom partition
          }
          return;
     }*/
     
     template <typename comp>
     void _mergesort(T* temp, int left, int right,const comp& C)
     {
          int i, j, k, mid = (left+right)/2;
          if (left == right) return;
          _mergesort(temp, left, mid,C); // la premiere moitie
          _mergesort(temp, mid+1, right,C);// Sort 2nd half
          // operation de fusion. Premierement, copier les deux moities dans temp.
          for (i=left; i<=mid; i++)
               temp[i] = v[i];
          for (j=1; j<=right-mid; j++)
               temp[right-j+1] = v[j+mid];
          // fusionner les deux moities dans array
          for (i=left,j=right,k=left; k<=right; k++)
               if (C(temp[i],temp[j]))
                    v[k] = temp[i++];
               else 
                    v[k] = temp[j--];
     }
 
public:
    typedef T value_type;
     typedef T * pointer;
     typedef T const * const_pointer;
     typedef pointer iterator;
     typedef const_pointer const_iterator;
 
     Dtk_tab()
     {
          nb=0;
          rsv=0;
          v=NULL;
     }
     Dtk_tab(Dtk_Size_t initreservesize,int resize=0)
     {
          Pdtk_Assert(initreservesize>0);  // forbidden : at least one element on reserve.
          rsv=initreservesize;
          nb=0;
          if (resize)
               nb = rsv;
          if (rsv>0)
               v=new T[rsv];
          else
               v=NULL;
     }
     ~Dtk_tab() 
     {
          if (v!=NULL)
          {
               delete [] v;
               v=NULL;
          }
     }
     const T* GetArray () const
     {
          return this->v;
     }
     T * data() { return v; }
     T const * data() const { return v; }
     Dtk_tab(const Dtk_tab<T>& t)
     {
//#ifdef DTK_DEBUG_STL_TRACE
//        FILE* F = fopen("/stltrace.txt","a");
//        fprintf(F,"Dtk_tab copy constructor size : %d ; elemsize : %d\n",t.size(),sizeof(T));
//        fclose(F);
//#endif
          nb=t.nb;
          rsv=t.nb; // shrink_to_fit while copy
          if (rsv>0)
          {
               Pdtk_Assert(nb > 0);
               v=new T[nb];
               for(Dtk_Size_t i=0;i<nb;i++)
                    v[i] = t.v[i];
          }
          else
               v=NULL;
     }
     Dtk_tab& operator=(const Dtk_tab<T>& t)
     {
          if (&t!=this)
          {
               if (v!=NULL)
               {
                    Pdtk_Assert(rsv>0);
                    delete [] v;
               }
               v=NULL;
               nb=t.nb;
               rsv=t.nb;
               if (t.v!=NULL && nb > 0)
               {
                    v=new T[nb];
                    for(Dtk_Size_t i=0;i<nb;i++)
                         v[i] = t.v[i];
               }
          } 
          return *this;
     }
     int operator==(const Dtk_tab<T>& t) const
     {
          if (t<*this || *this<t)
               return 0;
          return 1;
     }
 
#ifndef DTK_NO_CXX11_RVALUE_REFERENCES
     Dtk_tab(Dtk_tab<T> && t) DTK_NOEXCEPT : v(t.v), nb(t.nb), rsv(t.rsv)
     {
          t.v = 0;
          t.nb = 0;
          t.rsv = 0;
     }
 
     Dtk_tab<T>& operator=(Dtk_tab<T> && t) DTK_NOEXCEPT
     {
          if(this != &t)
          {
               delete [] v;
               v = t.v;
               nb = t.nb;
               rsv = t.rsv;
               t.v = 0;
               t.nb = 0;
               t.rsv = 0;
          }
 
          return *this;
     }
#endif
 
     int operator<(const Dtk_tab<T>& t) const
     {
          Dtk_Size_t i;
          if (size()<t.size())
               return 1;
          if (t.size()<size())
               return 0;
          for(i=0;i<size();i++)
          {
               if ((v[i]<t.v[i]))
                    return 1;
               if ((t.v[i]<v[i]))
                    return 0;
          }
          return 0;
     }
     void clear(int no_delete=0) 
     {
          if (v==NULL)
               return;
          if (no_delete)
          {
               nb=0;
               return;
          }
          delete [] v;
          nb=0;
          rsv=0;
          v=NULL;
     }
     inline T& operator[](Dtk_Size_t k)
     {
#ifdef _DEBUG_DTK
          if (k>=nb)
               Dtk_ThrowOverflowException();
#endif
          return v[k];
     }
     inline const T& operator[](Dtk_Size_t k) const
     {
#ifdef _DEBUG_DTK
          if (k>=nb)
               Dtk_ThrowOverflowException();
#endif
          return v[k];
     }
     inline T& at(Dtk_Size_t k) 
     {
          return operator[](k);
     }
     inline const T& at(Dtk_Size_t k) const 
     {
          return operator[](k);
     } 
     void push_back(const T& x) 
     {
          if (nb==rsv)
          {
               if (nb==0)
               {
                    rsv=1;
                    v = new T[1];
                    v[nb++]=x;
               }
               else
               {
                    rsv*=2;
                    T to_add;
                    to_add = x;
                    T* ex = _dtk_doublerealloc(rsv);
                    //v[nb++]=x;
                    v[ nb++ ] = to_add;
                    delete [] ex;
               }
          }
          else
               v[nb++]=x;
     }
 
#ifndef DTK_NO_CXX11_RVALUE_REFERENCES
     void push_back(T&& x) 
     {
          if (nb==rsv)
          {
               if (nb==0)
               {
                    rsv=1;
                    v = new T[1];
                    v[nb++]=std::move(x);
               }
               else
               {
                    rsv*=2;
                    T* ex = _dtk_doublerealloc(rsv);
                    v[nb++]= std::move(x);
                    delete [] ex;
               }
          }
          else
               v[nb++]=std::move(x);
     }
#endif
 
     void pop_back()
     {
          Pdtk_Assert(nb!=0);
          if( nb == 0 ) {     Dtk_ThrowOverflowException(); }
          nb--;
     }  // extent : liberation a 1/3.
 
     Dtk_Size_t size() const 
     {
          return nb;
     }
 
     Dtk_Size_t capacity() const 
     {
          return rsv;
     }
 
     T& back()
     {
          Pdtk_Assert(nb!=0);
          return v[nb - 1];
     }
     const T& back() const
     {
          Pdtk_Assert(nb!=0);
          return v[nb - 1];
     }
     T& front()
     {
          Pdtk_Assert(nb!=0);
          return v[0];
     }
     const T& front() const
     {
          Pdtk_Assert(nb!=0);
          return v[0];
     }
 
     void resize(Dtk_Size_t n, const T& t) 
     {
          if (n<=nb) 
          {
               nb=n;
               return;
          } 
          if (n<=0) 
          {
               clear();
               return;
          }
          if (v==NULL)
          {
               Pdtk_Assert(rsv==0 && n>0);
               v = new T[n];
          }
          else
               delete [] _dtk_doublerealloc(n);
          for(Dtk_Size_t i=nb;i<n;i++) 
               v[i]=t;
          nb=rsv=n;
     }
     void resize(Dtk_Size_t n) 
     {
          if (n<=nb) 
          {
               nb=n;
               return;
          } 
          if (n<=0) 
          {
               clear();
               return;
          }
          if (n<rsv)  // cas ou n>nb && n<rsv
          {
               nb = n;
               return;
          }
          if (v==NULL)
          {
               Pdtk_Assert(rsv==0);
               v = new T[n];
          }
          else
               delete [] _dtk_doublerealloc(n);
 
          nb=rsv=n;
     }
 
     void swap(const Dtk_Size_t inA, const Dtk_Size_t inB) 
     {
#ifdef _DEBUG_DTK
          if ( inA >= nb || inB >= nb )
               Dtk_ThrowOverflowException();
#endif
          const T Tmp = v[ inA ];
          v[ inA ] = v[ inB ];
          v[ inB ] = Tmp;
     }
 
     void remove( const T& a)
     {
          int pos = find( a );
          if( pos >= 0)
          {
            swap( pos, nb - 1 );
               pop_back();
          }
     }
 
     void sort()
     {
          sort(Dtk_less<T>());
     }
     template <typename comp>
     void sort(const comp& C)
     {
          if(nb > 0 )
          {
               //_quicksort((int)0,(int)(nb-1),C);
               T* tmp = new T[nb];
               _mergesort(tmp,(int)0,(int)(nb-1),C);
               delete [] tmp;
          }
     }
 
     int find(const T& e) const
     {
          for(Dtk_Size_t i=0;i<nb;i++) 
               if (v[i]==e) 
                    return (int)i;
          return -1;
     }
     template <typename comp>
     int find(const T& e,const comp& C) const
     {
          for(Dtk_Size_t i=0;i<nb;i++) 
               if (!C(v[i],e) && !C(e,v[i])) 
                    return (int)i;
          return -1;
     }
     //Dtk_tab& operator+=(const Dtk_tab& T) {V.resize(V.size()+T.V.size());V.insert(V.end(),T.V.begin(),T.V.end());return *this;}
     Dtk_tab& operator+=(const Dtk_tab& t) 
     {
          if (t.nb==0) // empty 2nd
               return *this;
          rsv=nb+t.nb;
          if (v==NULL)
               v = new T[rsv];
          else
               delete [] _dtk_doublerealloc(rsv);
          for(Dtk_Size_t i=0;i<t.nb;i++) 
               v[i+nb] = t.v[i];
          nb=nb+t.nb;
          return *this;
     }
 
     Dtk_tab& operator+=( Dtk_tab&& t )
     {
          if( t.nb == 0 )
               return *this;
          rsv = nb + t.nb;
          if( v == nullptr )
               v = new T[ rsv ];
          else
               delete[] _dtk_doublerealloc( rsv );
          for( Dtk_Size_t i = 0; i < t.nb; i++ )
               v[ i + nb ] = std::move( t.v[ i ] );
          nb = nb + t.nb;
          return *this;
     }
 
     Dtk_tab subtab(Dtk_Size_t a,Dtk_Size_t b) 
     {
          Pdtk_Assert(a<nb && b<nb && b>=a);
          Dtk_tab<T> res;
          res.resize(b-a+1);
          for(Dtk_Size_t i=0;i<res.rsv;i++) 
               res.v[i] = v[a+i];
          return res;
     }
     void reserve(Dtk_Size_t n) 
     {
          if (n<=rsv) 
               return; 
          if (v==NULL)
          {
               Pdtk_Assert(rsv==0);
               v = new T[n];
               rsv = n;
               return;
          }
          rsv = n;
          delete [] _dtk_doublerealloc(rsv);
     }
     T min_element() const
     {
          if (nb==0) 
               return T();
          T min = v[0];
          for(Dtk_Size_t i=0;i<nb;i++) 
               if (v[i]<min) 
                    min=v[i];
          return min;
     }
     T max_element() const
     {
          if (nb==0) 
               return T();
          T max = v[0];
          for(Dtk_Size_t i=0;i<nb;i++) 
               if (v[i]>max) 
                    max=v[i];
          return max;
     }
     Dtk_Size_t min_ithelement()
     {
          if (nb==0) 
               return 0;
          Dtk_Size_t imin = 0;
          T min = v[0];
          for(Dtk_Size_t i=0;i<nb;i++) 
               if (v[i]<min) 
               {
                    min=v[i];
                    imin = i;
               }
               return imin;
     }
     Dtk_Size_t max_ithelement()
     {
          if (nb==0) 
               return 0;
          Dtk_Size_t imax = 0;
          T max = v[0];
          for(Dtk_Size_t i=0;i<nb;i++) 
               if (v[i]>max) 
               {
                    max=v[i];
                    imax = i;
               }
               return imax;
     }
 
     friend std::ostream& operator<<(std::ostream& o,const Dtk_tab& d)
     {
          o<<"<Tab><Size>"<<d.size()<<"</Size>"<<std::endl;
          Dtk_Size_t i;
          for(i=0;i<d.size();i++)
          {
               o<<"<Elem_"<<i<<">"<< d[i] <<"</Elem_"<<i<<">"<<std::endl;
          }
          o << "</Tab>"<<std::endl;
          return o;
     }
     Dtk_Size_t GetSize() const
     {
          return 2*sizeof(Dtk_Size_t) + sizeof(T*) + rsv * sizeof(T);
     }
     void reduce()
     {
          if (rsv>nb)
          {
               rsv = nb;
               if (rsv==0)
                    rsv = 1;
               delete [] _dtk_doublerealloc(rsv);
          }
     }
     void reverse(){Dtk_Size_t i;for(i=0;i<nb/2;i++) Dtk_swap(v[i],v[nb-i-1]);}
 
     iterator begin()
     {
          return v;
     }
     const_iterator begin() const
     {
          return v;
     }
     const_iterator cbegin() const
     {
          return v;
     }
     iterator end()
     {
          return v + nb;
     }
     const_iterator end() const
     {
          return v + nb;
     }
     const_iterator cend() const
     {
          return v + nb;
     }
};
 
 
 
template <typename T1,typename T2>
class Dtk_pair
{
public:
   T1 first;
   T2 second;
   Dtk_pair() {}
   Dtk_pair(const T1& a,const T2& b) {first = a; second = b;}
 
   template <typename Arg, typename Arg2> Dtk_pair( Arg&& a, Arg2&& b ) : first( std::forward<Arg>( a ) ), second( std::forward<Arg2>( b ) )
   {
   }
 
   template <typename Pair> Dtk_pair( Pair&& p )
     : first(std::forward<Pair>(p).first), second(std::forward<Pair>(p).second)
   {
   }
 
   friend std::ostream& operator<<(std::ostream& o,const Dtk_pair& d)
   {
      o<<"<Pair><First>" << d.first <<"</First><Second>" << d.second << "</Second></Pair>" <<std::endl;
      return o;
   }
   int operator<(const Dtk_pair<T1,T2>& t) const
   {
          if (first<t.first)  
               return 1;
          if (first>t.first)  
               return 0;
          return second<t.second;
     }
   int operator==(const Dtk_pair<T1,T2>& t) const
   {
        return (first == t.first) && (second == t.second);
   }
};
 
 
template <typename T1, typename T2>
Dtk_pair<T1, T2> make_Dtkpair( T1&& x, T2&& y )
{
     return Dtk_pair<T1, T2>( std::forward<T1>( x ), std::forward<T2>( y ) );
}
 
 
 
 
namespace dtk
{
     template<class InputIterator, class Predicate>
     bool all_of(InputIterator first, InputIterator last, Predicate Pred)
     {    // test if all elements satisfy _Pred
          for (; first != last; ++first)
               if (!Pred(*first))
                    return false;
          return true;
     }
 
     template<typename T, class Predicate>
     bool all_of(const Dtk_tab<T> & tab, Predicate Pred)
     {
          for(Dtk_Size_t i = 0; i < tab.size(); ++i)
               if(!Pred(tab[i]))
                    return false;
          return true;
     }
 
     template<class InputIterator, class Predicate>
     bool any_of(InputIterator first, InputIterator last, Predicate Pred)
     {
          for(; first != last; ++first)
               if(Pred(*first))
                    return true;
          return false;
     }
 
     template<typename T, class Predicate>
     bool any_of(const Dtk_tab<T> & tab, Predicate Pred)
     {
          for(Dtk_Size_t i = 0; i < tab.size(); ++i)
               if(Pred(tab[i]))
                    return true;
          return false;
     }
 
     template<class InputIterator, class Predicate>
     bool none_of(InputIterator first, InputIterator last, Predicate Pred)
     {
          for (; first != last; ++first)
               if (Pred(*first))
                    return false;
          return true;
     }
 
     template<typename T, class Predicate>
     bool none_of(const Dtk_tab<T> & tab, Predicate Pred)
     {
          for(Dtk_Size_t i = 0; i < tab.size(); ++i)
               if(Pred(tab[i]))
                    return false;
          return true;
     }
}  // end of namespace dtk
 
 
 
#endif  // of ifndef UTIL_STL_DTK_HPP_