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_NODE_FOR_INSERT_HPP
       8             : #define VSET_VTREE_ASPECT_AD_NODE_FOR_INSERT_HPP
       9             : 
      10             : #include <vset/vtree/aspect/tags.hpp>
      11             : #include <stdexcept>
      12             : 
      13             : namespace vset{ namespace vtree{
      14             : 
      15          29 : struct ad_node_for_insert
      16             : {
      17             :   template<typename T, typename V>
      18         101 :   bool less(T& t, const V& first, const V& second) const
      19             :   {
      20         101 :     return t.get_aspect().template get<_key_compare_>()(first, second);
      21             :   }
      22             : 
      23             :   template<typename T, typename V>
      24          81 :   bool less_equal(T& t, const V& first, const V& second) const
      25             :   {
      26          81 :     return less(t, first, second) || !less(t, second, first);
      27             :   }
      28             : 
      29             :   template<typename T, typename Itr, typename V>
      30          62 :   Itr operator()(T& t, Itr itr1, Itr itr2, const V& value ) const
      31             :   {
      32          62 :     if ( less_equal(t, value, itr1->first.first) )
      33             :     {
      34          43 :       return itr1;
      35             :     }
      36             : 
      37          19 :     if ( less_equal(t, itr2->first.first, value  ) )
      38             :     {
      39          19 :       return itr2;
      40             :     }
      41             : 
      42           0 :     if ( less_equal(t, itr1->first.second, value)
      43           0 :       && less_equal(t, value, itr2->first.first) )
      44             :     {
      45             :       // Можно вставить в любой, выбираем меньший
      46           0 :       return itr1->second->size() < itr2->second->size() ? itr1 : itr2;
      47             :     }
      48             : 
      49           0 :     if ( less_equal(t, itr1->first.first, value )
      50           0 :       && less_equal(t, value, itr1->first.second ) )
      51             :     {
      52           0 :       return itr1;
      53             :     }
      54             : 
      55           0 :     if ( less_equal(t, itr2->first.first, value)
      56           0 :       && less_equal(t, value, itr2->first.second ) )
      57             :     {
      58           0 :       return itr2;
      59             :     }
      60             : 
      61           0 :     throw std::logic_error("ad_node_for_insert");
      62             :   }
      63             :   
      64             : };
      65             : 
      66             :   
      67             : }}
      68             : 
      69             : #endif