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_FIRST_PROPER_NODE_HPP
       8             : #define VSET_VTREE_ASPECT_AD_FIRST_PROPER_NODE_HPP
       9             : 
      10             : #include <vset/vtree/aspect/tags.hpp>
      11             : #include <stdexcept>
      12             : 
      13             : namespace vset{ namespace vtree{
      14             : 
      15          29 : struct ad_first_proper_node
      16             : {
      17             :   template<typename T, typename V>
      18        9733 :   bool not_equal(T& t, const V& first, const V& second) const
      19             :   {
      20        9733 :     return t.get_aspect().template get<_key_compare_>()(first, second)
      21        9733 :       || t.get_aspect().template get<_key_compare_>()(second, first);
      22             :   }
      23             :   
      24             :   template<typename T, typename Itr>
      25       21328 :   Itr operator()(T& t, Itr itr ) const
      26             :   {
      27             :     typedef typename T::key_type key_type;
      28       21328 :     Itr beg = itr;
      29       21328 :     Itr end = t.get_container().end();
      30             : 
      31       21328 :     if (itr == end)
      32             :     {
      33           0 :       abort();
      34             :     }
      35             :     
      36       21328 :     if (beg == end)
      37             :     {
      38           0 :       return itr;
      39             :     }
      40             :     
      41       21328 :     const key_type& value = itr->first.first;
      42       21328 :     for ( ++beg; beg != end; ++beg )
      43             :     {
      44        9733 :       if ( not_equal(t, beg->first.first, value) )
      45             :       {
      46        9733 :         return itr;
      47             :       }
      48             : 
      49           0 :       if ( !beg->second->filled() )
      50             :       {
      51           0 :         return beg;
      52             :       }
      53             :     }
      54             : 
      55       11595 :     if (itr == end)
      56             :     {
      57           0 :       abort();
      58             :     }
      59             : 
      60       11595 :     return itr;
      61             :   }
      62             : };
      63             :   
      64             : }}
      65             : 
      66             : #endif