ordered_index.hpp

CGAL is a collaborative effort of several sites in Europe and Israel. The goal is to make the most i

         ordered_index_node_impl::maximum(root()->impl()))
        return false;
    }

    return Super::invariant_();
  }

  
  /* This forwarding function eases things for the boost::mem_fn construct
   * in BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT. Actually,
   * final_check_invariant is already an inherited member function of
   * ordered_index.
   */
  void check_invariant_()const{this->final_check_invariant_();}
#endif

private:
  node_type* header()const{return this->final_header();}
  node_type* root()const{return node_type::from_impl(header()->parent());}
  node_type* leftmost()const{return node_type::from_impl(header()->left());}
  node_type* rightmost()const{return node_type::from_impl(header()->right());}

  void empty_initialize()
  {
    header()->color()=red;
    /* used to distinguish header() from root, in iterator.operator++ */
    
    header()->parent()=0;
    header()->left()=header()->impl();
    header()->right()=header()->impl();
  }

  node_type* link4(key_param_type k,node_type* x,node_type* y,node_type* z)
  {
    if(x!=0||y==header()||comp(k,key(y->value))){
      y->left()=z->impl(); /* also makes leftmost()=z when y==header() */
      if (y==header()){
        header()->parent()=z->impl();
        header()->right()=z->impl();
      }
      else if(y==leftmost()){
        header()->left()=z->impl();
        /* maintain leftmost() pointing to min node */
      }
    }
    else{
      y->right()=z->impl();
      if(y==rightmost()){
        header()->right()=z->impl();
        /* maintain rightmost() pointing to max node */
      }
    }
    z->parent()=y->impl();
    z->left()=0;
    z->right()=0;
    ordered_index_node_impl::rebalance(z->impl(),header()->parent());
    return z;
  }

  node_type* link2(key_param_type k,node_type* z,ordered_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());
    }
    iterator j=make_iterator(y);   
    if(c){
      if(j==begin())return link4(k,x,y,z);
      else --j;
    }

    if(comp(key(*j),k))return link4(k,x,y,z);
    else return j.get_node();
  }

  node_type* link2(key_param_type k,node_type* z,ordered_non_unique_tag)
  {
    node_type* y=header();
    node_type* x=root();
    while (x){
     y=x;
     x=node_type::from_impl(comp(k,key(x->value))?x->left():x->right());
    }
    return link4(k,x,y,z);
  }

  node_type* link3(
    key_param_type k,node_type* position,node_type* z,ordered_unique_tag)
  {
    if(position->impl()==header()->left()){ 
      if(size()>0&&comp(k,key(position->value))){
        return link4(k,position,position,z);
      }
      else return link2(k,z,ordered_unique_tag());
    } 
    else if(position==header()){ 
      if(comp(key(rightmost()->value),k)){
        return link4(k,0,rightmost(),z);
      }
      else return link2(k,z,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)return link4(k,0,before,z); 
        else return link4(k,position,position,z);
      } 
      else return link2(k,z,ordered_unique_tag());
    }
  }

  node_type* link3(
    key_param_type k,node_type* position,node_type* z,ordered_non_unique_tag)
  {
    if(position->impl()==header()->left()){ 
      if(size()>0&&!comp(key(position->value),k)){
        return link4(k,position,position,z);
      }
      else return link2(k,z,ordered_non_unique_tag());
    } 
    else if(position==header()){
      if(!comp(k,key(rightmost()->value))){
        return link4(k,0,rightmost(),z);
      }
      else return link2(k,z,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)return link4(k,0,before,z); 
        else return link4(k,position,position,z);
      } 
      else return link2(k,z,ordered_non_unique_tag());
    }
  }

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

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

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

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

#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>
  const_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);
  }

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

  template<typename UpperBounder>
  const_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);
  }

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

  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 Super1,typename TagList1,typename Category1,
  typename KeyFromValue2,typename Compare2,
  typename Super2,typename TagList2,typename Category2
>
bool operator==(
  const ordered_index<KeyFromValue1,Compare1,Super1,TagList1,Category1>& x,
  const ordered_index<KeyFromValue2,Compare2,Super2,TagList2,Category2>& y)
{
  return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
}

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

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

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

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

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

/*  specialized algorithms */

template<
  typename KeyFromValue,typename Compare,
  typename Super,typename TagList,typename Category
>
void swap(
  ordered_index<KeyFromValue,Compare,Super,TagList,Category>& x,
  ordered_index<KeyFromValue,Compare,Super,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       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 Super>
  struct index_class
  {
    typedef detail::ordered_index<
      key_from_value_type,compare_type,
      Super,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       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 Super>
  struct index_class
  {
    typedef detail::ordered_index<
      key_from_value_type,compare_type,
      Super,tag_list_type,detail::ordered_non_unique_tag> type;
  };
};

} /* namespace multi_index */

} /* namespace boost */

#undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT

#endif