Line data    Source code

       1             : //
       2             : // Author: Vladimir Migashko <migashko@gmail.com>, (C) 2012
       3             : //
       4             : // Copyright: See COPYING file that comes with this distribution
       5             : //
       6             : 
       7             : #ifndef VSET_VTREE_ASPECT_AD_SPLIT_NODE_HPP
       8             : #define VSET_VTREE_ASPECT_AD_SPLIT_NODE_HPP
       9             : 
      10             : #include <fas/system/nullptr.hpp>
      11             : #include <vset/vtree/aspect/tags.hpp>
      12             : #include <stdlib.h>
      13             : 
      14             : namespace vset{ namespace vtree{
      15             : 
      16          29 : struct ad_split_node
      17             : {
      18             :   template<typename T>
      19             :   struct helper
      20             :   {
      21             :     typedef typename T::container_type container_type;
      22             :     typedef typename container_type::iterator iterator;
      23             :   };
      24             : 
      25             :   template<typename T>
      26             :   typename helper<T>::iterator
      27          62 :   operator()(T& t, typename helper<T>::iterator itr, const typename T::key_type& value)
      28             :   {
      29             :     typedef typename T::key_type key_type;
      30             :     typedef typename T::value_type value_type;
      31             :     typedef typename helper<T>::iterator container_iterator;
      32             :     typedef typename helper<T>::container_type container_type;
      33             : 
      34             :     typedef typename T::allocator_type allocator_type;
      35             :     typedef typename allocator_type::pointer array_pointer;
      36             : 
      37          62 :     container_type& container = t.get_container();
      38          62 :     if ( itr == container.end() )
      39             :     {
      40           0 :       return itr;
      41             :     }
      42             : 
      43          62 :     array_pointer arr1 = itr->second;
      44          62 :     array_pointer arr2 = t.get_allocator().allocate(1, fas_nullptr);
      45          62 :     if ( !arr2 )
      46             :     {
      47           0 :       abort();//return container.end(); // TODO: проверить что offset_pointer при сравнении с числом не сравнивает оффыеты
      48             :     }
      49             : 
      50          62 :     size_t offset = arr1->size();
      51             : 
      52          62 :     if ( offset < 2 )
      53             :     {
      54           0 :       return itr;
      55             :     }
      56             : 
      57          62 :     offset /= 2;
      58             : 
      59          62 :     arr2->assign( arr1->begin() + offset, arr1->end(), t.get_aspect().template get<_value_compare_>() );
      60          62 :     arr1->resize( offset, value_type(), t.get_aspect().template get<_value_compare_>() );
      61          62 :     container.erase( itr );
      62             :     
      63          62 :     const typename T::aspect::template advice_cast<_get_key_>::type& get_key = t.get_aspect().template get<_get_key_>();
      64             :     
      65          62 :     const key_type& k1f = get_key(t, arr1->front());
      66          62 :     const key_type& k1b = get_key(t, arr1->back());
      67          62 :     container_iterator itr1 = t.get_aspect().template get<_insert_to_container_>()(t, std::make_pair(k1f, k1b/*arr1->front(), arr1->back()*/), arr1);
      68          62 :     const key_type& k2f = get_key(t, arr2->front());
      69          62 :     const key_type& k2b = get_key(t, arr2->back());
      70          62 :     container_iterator itr2 = t.get_aspect().template get<_insert_to_container_>()(t, std::make_pair(k2f, k2b/*arr2->front(), arr2->back()*/), arr2);
      71             : 
      72          62 :     itr = t.get_aspect().template get<_node_for_insert_>()(t, itr1, itr2, value);
      73             : 
      74          62 :     arr1 = itr->second;
      75          62 :     return itr;
      76             :   }
      77             : };
      78             : 
      79             : }}
      80             : 
      81             : #endif