Line data    Source code

       1             : #ifndef VSET_VTREE_SORTED_ARRAY_HPP
       2             : #define VSET_VTREE_SORTED_ARRAY_HPP
       3             : 
       4             : #include <vset/array.hpp>
       5             : 
       6             : namespace vset{
       7             : 
       8             : // TODO: сделать операции < > и пр.
       9             : template<typename T, size_t N, typename Compare = std::less<T> >
      10             : class sorted_array
      11             :   : public array<T, N>
      12             : {
      13             :   typedef array<T, N> super;
      14             : 
      15             : public:
      16             :   
      17             :   typedef Compare key_compare;
      18             :   typedef Compare value_compare;
      19             : 
      20             :   typedef typename super::value_type value_type;
      21             :   typedef typename super::data_type data_type;
      22             :   typedef typename super::size_type size_type;
      23             : 
      24             :   typedef typename super::reference reference;
      25             :   typedef typename super::const_reference const_reference;
      26             : 
      27             :   typedef typename super::pointer pointer;
      28             :   typedef typename super::const_pointer const_pointer;
      29             : 
      30             :   typedef typename super::const_iterator const_iterator;
      31             :   typedef typename super::iterator iterator;
      32             : 
      33             :   typedef typename super::reverse_iterator reverse_iterator;
      34             :   typedef typename super::const_reverse_iterator const_reverse_iterator;
      35             : 
      36             :   typedef std::ptrdiff_t difference_type;
      37             : 
      38             : 
      39        1437 :   sorted_array( )
      40        1437 :     : super()
      41        1437 :   {}
      42             : 
      43       16918 :   void resize ( size_type sz, T value /*= value_type()*/, const value_compare& comp /*= value_compare()*/ )
      44             :   {
      45       16918 :     bool f = this->size() < sz;
      46       16918 :     super_()->resize(sz, value);
      47       16918 :     if ( f ) this->sort(comp);
      48       16918 :   }
      49             : 
      50             :   template <class InputIterator>
      51          62 :   void assign( InputIterator f, InputIterator l, const value_compare& comp /*= value_compare()*/ )
      52             :   {
      53          62 :     super_()->assign(f, l);
      54          62 :     this->sort(comp);
      55          62 :   }
      56             : 
      57        2432 :   void push_back ( const T& x, const value_compare& comp /*= value_compare()*/ )
      58             :   {
      59        2432 :     super_()->push_back(x);
      60        2432 :     this->sort(comp);
      61        2432 :   }
      62             : 
      63       21356 :   iterator insert ( const T& x, const value_compare& comp /*= value_compare()*/ )
      64             :   {
      65       21356 :     iterator position = std::upper_bound(super_()->begin(), super_()->end(), x, comp );
      66       21356 :     return static_cast<super*>(this)->insert(position, x);
      67             :   }
      68             : 
      69             :   
      70             :   void insert ( size_type n, const T& x, const value_compare& comp /*= value_compare()*/ )
      71             :   {
      72             :     iterator position = std::upper_bound(super_()->begin(), super_()->end(), x, comp );
      73             :     return super_()->insert(position, n, x);
      74             :   }
      75             :   
      76             : 
      77             :   template <class InputIterator>
      78             :   void insert ( InputIterator first, InputIterator last, const value_compare& comp /*= value_compare()*/ )
      79             :   {
      80             :     super_()->insert( super_()->end(), first, last );
      81             :     this->sort(comp);
      82             :   }
      83             : 
      84             :   //using super_()->erase;
      85             :   //using super_()->cbegin;
      86             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
      87       16856 :   iterator erase ( const_iterator position, const value_compare& comp )
      88             :   {
      89       16856 :     if ( position == this->cend() )
      90           0 :       throw std::out_of_range("iterator array<>::erase ( iterator position )");
      91             : 
      92       16856 :     iterator dst = this->begin() + std::distance(this->cbegin(), position);
      93       16856 :     std::copy( position + 1, this->cend(), dst);
      94       16856 :     if ( this->size() > 0 )
      95       16856 :       this->resize( this->size() - 1, value_type(), comp );
      96       16856 :     return dst;
      97             :   }
      98             : #else
      99             :   iterator erase ( iterator position, const value_compare& comp )
     100             :   {
     101             :     if ( position == this->end() )
     102             :       throw std::out_of_range("iterator array<>::erase ( iterator position )");
     103             : 
     104             :     std::copy( position + 1, this->end(), position);
     105             :     if ( this->size() > 0 )
     106             :       this->resize( this->size() - 1, value_type(), comp );
     107             :     return position;
     108             :   }
     109             : #endif
     110             : 
     111             : private:
     112             :   /// BUG 
     113             :   size_type erase( const T& x, const value_compare& comp )
     114             :   {
     115             :     size_type count = 0;
     116             :     std::pair<iterator, iterator> range = std::equal_range(super_()->begin(), super_()->end(), x, comp );
     117             :     for (;range.first!=range.second;++range.first, ++count)
     118             :       super_()->erase(range.first);
     119             :     return count;
     120             :   }
     121             : public:
     122             : 
     123        2494 :   void sort(const value_compare& comp )
     124             :   {
     125        2494 :     std::sort( super_()->begin(), super_()->end(), comp );
     126        2494 :   }
     127             : private:
     128             :   const super* super_() const { return static_cast< const super*>(this);}
     129       67112 :   super* super_(){ return static_cast<super*>(this);}
     130             :   
     131             : };
     132             : 
     133             : }
     134             : 
     135             : #endif