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