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_UPPER_BOUND_HPP
       8             : #define VSET_VTREE_ASPECT_AD_UPPER_BOUND_HPP
       9             : 
      10             : #include <vset/vtree/aspect/tags.hpp>
      11             : #include <algorithm>
      12             : 
      13             : namespace vset{ namespace vtree{
      14             : 
      15          29 : struct ad_upper_bound
      16             : {
      17             :   template<typename T>
      18             :   typename T::iterator
      19       27771 :   operator()(T& t, const typename T::key_type& value)
      20             :   {
      21             :     typedef typename T::container_type container_type;
      22             :     typedef typename container_type::iterator container_iterator;
      23             :     typedef typename T::difference_type difference_type;
      24             :     
      25             :     typedef typename T::iterator iterator;
      26             :     typedef typename T::allocator_type allocator_type;
      27             :     typedef typename allocator_type::value_type array_type;
      28             :     typedef typename array_type::iterator array_iterator;
      29             : 
      30       27771 :     container_type& container = t.get_container();
      31             : 
      32       27771 :     if ( container.empty() )
      33             :     {
      34           1 :       return t.end();
      35             :     }
      36             : 
      37       27770 :     container_iterator cont_itr = t.get_aspect().template get<_upper_node_>()(t, value);
      38             : 
      39       27770 :     if ( cont_itr == container.end() )
      40             :     {
      41           0 :       return t.end();
      42             :     }
      43             : 
      44             :     array_iterator itr = std::upper_bound(
      45       27770 :       cont_itr->second->begin(),
      46       27770 :       cont_itr->second->end(),
      47             :       value,
      48             :       t.get_aspect().template get<_key_compare_>()
      49       83310 :     );
      50             : 
      51       27770 :     if ( itr == cont_itr->second->end() )
      52             :     {
      53       10963 :       return ++iterator( cont_itr, static_cast<difference_type>(cont_itr->second->size()-1) );
      54             :     }
      55             : 
      56       16807 :     return iterator( cont_itr, std::distance(cont_itr->second->begin(), itr) );
      57             :   }
      58             : 
      59             :   template<typename T>
      60             :   typename T::const_iterator
      61           7 :   operator()(const T& t, const typename T::key_type& value) const
      62             :   {
      63             :     typedef typename T::container_type container_type;
      64             :     typedef typename T::difference_type difference_type;
      65             :     typedef typename container_type::const_iterator const_container_iterator;
      66             : 
      67             :     typedef typename T::const_iterator const_iterator;
      68             :     typedef typename T::allocator_type allocator_type;
      69             :     typedef typename allocator_type::value_type array_type;
      70             :     typedef typename array_type::const_iterator const_array_iterator;
      71             :     
      72           7 :     const container_type& container = t.get_container();
      73             : 
      74           7 :     if ( container.empty() )
      75             :     {
      76           0 :       return t.cend();
      77             :     }
      78             : 
      79           7 :     const_container_iterator cont_itr = t.get_aspect().template get<_upper_node_>()(t, value);
      80           7 :     if ( cont_itr == container.cend() )
      81             :     {
      82           0 :       return t.cend();
      83             :     }
      84             : 
      85             :     const_array_iterator itr = std::upper_bound(
      86           7 :       cont_itr->second->begin(),
      87           7 :       cont_itr->second->end(),
      88             :       value,
      89             :       t.get_aspect().template get<_compare_>()
      90          21 :     );
      91             : 
      92           7 :     if ( itr == cont_itr->second->cend() )
      93             :     {
      94           5 :       return ++const_iterator( cont_itr, static_cast<difference_type>(cont_itr->second->size() - 1) );
      95             :     }
      96             : 
      97           2 :     return const_iterator( cont_itr, std::distance(cont_itr->second->cbegin(), itr) );
      98             :   }
      99             : };
     100             : 
     101             : }}
     102             : 
     103             : #endif