ordered_index.hpp

来自「support vector clustering for vc++」· HPP 代码 · 共 1,240 行 · 第 1/3 页

    else{
      inf.pos=yy->impl();
      return false;
    }
  }

  bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
  {
    node_type* y=header();
    node_type* x=root();
    bool c=true;
    while (x){
     y=x;
     c=comp(k,key(x->value()));
     x=node_type::from_impl(c?x->left():x->right());
    }
    inf.side=c?to_left:to_right;
    inf.pos=y->impl();
    return true;
  }

  bool hinted_link_point(
    key_param_type k,node_type* position,link_info& inf,ordered_unique_tag)
  {
    if(position->impl()==header()->left()){ 
      if(size()>0&&comp(k,key(position->value()))){
        inf.side=to_left;
        inf.pos=position->impl();
        return true;
      }
      else return link_point(k,inf,ordered_unique_tag());
    } 
    else if(position==header()){ 
      if(comp(key(rightmost()->value()),k)){
        inf.side=to_right;
        inf.pos=rightmost()->impl();
        return true;
      }
      else return link_point(k,inf,ordered_unique_tag());
    } 
    else{
      node_type* before=position;
      node_type::decrement(before);
      if(comp(key(before->value()),k)&&comp(k,key(position->value()))){
        if(before->right()==0){
          inf.side=to_right;
          inf.pos=before->impl();
          return true;
        }
        else{
          inf.side=to_left;
          inf.pos=position->impl();
          return true;
        }
      } 
      else return link_point(k,inf,ordered_unique_tag());
    }
  }

  bool hinted_link_point(
    key_param_type k,node_type* position,link_info& inf,ordered_non_unique_tag)
  {
    if(position->impl()==header()->left()){ 
      if(size()>0&&!comp(key(position->value()),k)){
        inf.side=to_left;
        inf.pos=position->impl();
        return true;
      }
      else return link_point(k,inf,ordered_non_unique_tag());
    } 
    else if(position==header()){
      if(!comp(k,key(rightmost()->value()))){
        inf.side=to_right;
        inf.pos=rightmost()->impl();
        return true;
      }
      else return link_point(k,inf,ordered_non_unique_tag());
    } 
    else{
      node_type* before=position;
      node_type::decrement(before);
      if (!comp(k,key(before->value()))&&!comp(key(position->value()),k)){
        if(before->right()==0){
          inf.side=to_right;
          inf.pos=before->impl();
          return true;
        }
        else{
          inf.side=to_left;
          inf.pos=position->impl();
          return true;
        }
      } 
      else return link_point(k,inf,ordered_non_unique_tag());
    }
  }

  void delete_all_nodes(node_type* x)
  {
    if(!x)return;

    delete_all_nodes(node_type::from_impl(x->left()));
    delete_all_nodes(node_type::from_impl(x->right()));
    this->final_delete_node_(static_cast<final_node_type*>(x));
  }

  bool in_place(value_param_type v,node_type* x,ordered_unique_tag)
  {
    node_type* y;
    if(x!=leftmost()){
      y=x;
      node_type::decrement(y);
      if(!comp(key(y->value()),key(v)))return false;
    }

    y=x;
    node_type::increment(y);
    return y==header()||comp(key(v),key(y->value()));
  }

  bool in_place(value_param_type v,node_type* x,ordered_non_unique_tag)
  {
    node_type* y;
    if(x!=leftmost()){
      y=x;
      node_type::decrement(y);
      if(comp(key(v),key(y->value())))return false;
    }

    y=x;
    node_type::increment(y);
    return y==header()||!comp(key(y->value()),key(v));
  }

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  void detach_iterators(node_type* x)
  {
    iterator it=make_iterator(x);
    safe_mode::detach_equivalent_iterators(it);
  }
#endif

  template<typename LowerBounder>
  iterator lower_range(LowerBounder lower)const
  {
    node_type* y=header();
    node_type* z=root();

    while(z){
      if(lower(key(z->value()))){
        y=z;
        z=node_type::from_impl(z->left());
      }
      else z=node_type::from_impl(z->right());
    }

    return make_iterator(y);
  }

  iterator lower_range(unbounded_type)const
  {
    return begin();
  }

  template<typename UpperBounder>
  iterator upper_range(UpperBounder upper)const
  {
    node_type* y=header();
    node_type* z=root();

    while(z){
      if(!upper(key(z->value()))){
        y=z;
        z=node_type::from_impl(z->left());
      }
      else z=node_type::from_impl(z->right());
    }

    return make_iterator(y);
  }

  iterator upper_range(unbounded_type)const
  {
    return end();
  }

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  template<typename Archive>
  void save_(
    Archive& ar,const unsigned int version,const index_saver_type& sm,
    ordered_unique_tag)const
  {
    super::save_(ar,version,sm);
  }

  template<typename Archive>
  void load_(
    Archive& ar,const unsigned int version,const index_loader_type& lm,
    ordered_unique_tag)
  {
    super::load_(ar,version,lm);
  }

  template<typename Archive>
  void save_(
    Archive& ar,const unsigned int version,const index_saver_type& sm,
    ordered_non_unique_tag)const
  {
    typedef duplicates_iterator<node_type,value_compare> dup_iterator;

    sm.save(
      dup_iterator(begin().get_node(),end().get_node(),value_comp()),
      dup_iterator(end().get_node(),value_comp()),
      ar,version);
    super::save_(ar,version,sm);
  }

  template<typename Archive>
  void load_(
    Archive& ar,const unsigned int version,const index_loader_type& lm,
    ordered_non_unique_tag)
  {
    lm.load(
      ::boost::bind(&ordered_index::rearranger,this,_1,_2),
      ar,version);
    super::load_(ar,version,lm);
  }

  void rearranger(node_type* position,node_type *x)
  {
    if(!position||comp(key(position->value()),key(x->value()))){
      position=lower_bound(key(x->value())).get_node();
    }
    else if(comp(key(x->value()),key(position->value()))){
      /* inconsistent rearrangement */
      throw_exception(
        archive::archive_exception(
          archive::archive_exception::other_exception));
    }
    else node_type::increment(position);

    if(position!=x){
      ordered_index_node_impl::rebalance_for_erase(
        x->impl(),header()->parent(),header()->left(),header()->right());
      ordered_index_node_impl::restore(
        x->impl(),position->impl(),header()->impl());
    }
  }
#endif /* serialization */

  key_from_value key;
  key_compare    comp;

#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
    BOOST_WORKAROUND(__MWERKS__,<=0x3003)
#pragma parse_mfunc_templ reset
#endif
};

/* comparison */

template<
  typename KeyFromValue1,typename Compare1,
  typename SuperMeta1,typename TagList1,typename Category1,
  typename KeyFromValue2,typename Compare2,
  typename SuperMeta2,typename TagList2,typename Category2
>
bool operator==(
  const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
{
  return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
}

template<
  typename KeyFromValue1,typename Compare1,
  typename SuperMeta1,typename TagList1,typename Category1,
  typename KeyFromValue2,typename Compare2,
  typename SuperMeta2,typename TagList2,typename Category2
>
bool operator<(
  const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
{
  return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
}

template<
  typename KeyFromValue1,typename Compare1,
  typename SuperMeta1,typename TagList1,typename Category1,
  typename KeyFromValue2,typename Compare2,
  typename SuperMeta2,typename TagList2,typename Category2
>
bool operator!=(
  const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
{
  return !(x==y);
}

template<
  typename KeyFromValue1,typename Compare1,
  typename SuperMeta1,typename TagList1,typename Category1,
  typename KeyFromValue2,typename Compare2,
  typename SuperMeta2,typename TagList2,typename Category2
>
bool operator>(
  const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
{
  return y<x;
}

template<
  typename KeyFromValue1,typename Compare1,
  typename SuperMeta1,typename TagList1,typename Category1,
  typename KeyFromValue2,typename Compare2,
  typename SuperMeta2,typename TagList2,typename Category2
>
bool operator>=(
  const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
{
  return !(x<y);
}

template<
  typename KeyFromValue1,typename Compare1,
  typename SuperMeta1,typename TagList1,typename Category1,
  typename KeyFromValue2,typename Compare2,
  typename SuperMeta2,typename TagList2,typename Category2
>
bool operator<=(
  const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
{
  return !(x>y);
}

/*  specialized algorithms */

template<
  typename KeyFromValue,typename Compare,
  typename SuperMeta,typename TagList,typename Category
>
void swap(
  ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x,
  ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& y)
{
  x.swap(y);
}

} /* namespace multi_index::detail */

/* ordered_index specifiers */

template<typename Arg1,typename Arg2,typename Arg3>
struct ordered_unique
{
  typedef typename detail::ordered_index_args<
    Arg1,Arg2,Arg3>                                index_args;
  typedef typename index_args::tag_list_type::type tag_list_type;
  typedef typename index_args::key_from_value_type key_from_value_type;
  typedef typename index_args::compare_type        compare_type;

  template<typename Super>
  struct node_class
  {
    typedef detail::ordered_index_node<Super> type;
  };

  template<typename SuperMeta>
  struct index_class
  {
    typedef detail::ordered_index<
      key_from_value_type,compare_type,
      SuperMeta,tag_list_type,detail::ordered_unique_tag> type;
  };
};

template<typename Arg1,typename Arg2,typename Arg3>
struct ordered_non_unique
{
  typedef detail::ordered_index_args<
    Arg1,Arg2,Arg3>                                index_args;
  typedef typename index_args::tag_list_type::type tag_list_type;
  typedef typename index_args::key_from_value_type key_from_value_type;
  typedef typename index_args::compare_type        compare_type;

  template<typename Super>
  struct node_class
  {
    typedef detail::ordered_index_node<Super> type;
  };

  template<typename SuperMeta>
  struct index_class
  {
    typedef detail::ordered_index<
      key_from_value_type,compare_type,
      SuperMeta,tag_list_type,detail::ordered_non_unique_tag> type;
  };
};

} /* namespace multi_index */

} /* namespace boost */

#undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT

#endif