view release on metacpan or  search on metacpan

include/boost/container/detail/flat_tree.hpp  view on Meta::CPAN

template<class SequenceContainer, class Compare>
void flat_tree_adopt_sequence_unique// is_contiguous_container == false
   (SequenceContainer &tseq, BOOST_RV_REF(SequenceContainer) seq, Compare comp, dtl::false_)
{
   boost::movelib::pdqsort(seq.begin(), seq.end(), comp);
   seq.erase(boost::movelib::unique
      (seq.begin(), seq.end(), boost::movelib::negate<Compare>(comp)), seq.cend());
   tseq = boost::move(seq);
}

///////////////////////////////////////
//
//       flat_tree_reserve
//
///////////////////////////////////////
template<class SequenceContainer>
BOOST_CONTAINER_FORCEINLINE void // has_reserve == true
   flat_tree_reserve(SequenceContainer &tseq, typename SequenceContainer::size_type cap, dtl::true_)
{
   tseq.reserve(cap);
}

template<class SequenceContainer>
BOOST_CONTAINER_FORCEINLINE void // has_reserve == false
   flat_tree_reserve(SequenceContainer &, typename SequenceContainer::size_type, dtl::false_)
{
}

///////////////////////////////////////
//
//       flat_tree_capacity
//
///////////////////////////////////////
template<class SequenceContainer>   // has_capacity == true
BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
   flat_tree_capacity(const SequenceContainer &tseq, dtl::true_)
{
   return tseq.capacity();
}

template<class SequenceContainer>   // has_capacity == false
BOOST_CONTAINER_FORCEINLINE typename SequenceContainer::size_type
   flat_tree_capacity(const SequenceContainer &tseq, dtl::false_)
{
   return tseq.size();
}

///////////////////////////////////////
//
//       flat_tree_value_compare
//
///////////////////////////////////////

template<class Compare, class Value, class KeyOfValue>
class flat_tree_value_compare
   : private Compare
{
   typedef Value              first_argument_type;
   typedef Value              second_argument_type;
   typedef bool               return_type;
   public:
   flat_tree_value_compare()
      : Compare()
   {}

   flat_tree_value_compare(const Compare &pred)
      : Compare(pred)
   {}

   bool operator()(const Value& lhs, const Value& rhs) const
   {
      KeyOfValue key_extract;
      return Compare::operator()(key_extract(lhs), key_extract(rhs));
   }

   const Compare &get_comp() const
      {  return *this;  }

   Compare &get_comp()
      {  return *this;  }
};

///////////////////////////////////////
//
//       select_container_type
//
///////////////////////////////////////
template < class Value, class AllocatorOrContainer
         , bool = boost::container::dtl::is_container<AllocatorOrContainer>::value >
struct select_container_type
{
   typedef AllocatorOrContainer type;
};

template <class Value, class AllocatorOrContainer>
struct select_container_type<Value, AllocatorOrContainer, false>
{
   typedef boost::container::vector<Value, AllocatorOrContainer> type;
};


///////////////////////////////////////
//
//          flat_tree
//
///////////////////////////////////////
template <class Value, class KeyOfValue,
          class Compare, class AllocatorOrContainer>
class flat_tree
{
   public:
   typedef typename select_container_type<Value, AllocatorOrContainer>::type container_type;
   typedef container_type sequence_type;  //For backwards compatibility

   private:
   typedef typename container_type::allocator_type        allocator_t;
   typedef allocator_traits<allocator_t>                 allocator_traits_type;

   public:
   typedef flat_tree_value_compare<Compare, Value, KeyOfValue> value_compare;

   private:
   
   struct Data
      //Inherit from value_compare to do EBO
      : public value_compare
   {
      BOOST_COPYABLE_AND_MOVABLE(Data)

      public:
      Data()
         : value_compare(), m_seq()
      {}

      explicit Data(const allocator_t &alloc)
         : value_compare(), m_seq(alloc)
      {}

      explicit Data(const Compare &comp)
         : value_compare(comp), m_seq()
      {}

      Data(const Compare &comp, const allocator_t &alloc)
         : value_compare(comp), m_seq(alloc)
      {}

      explicit Data(const Data &d)
         : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq)
      {}

      Data(BOOST_RV_REF(Data) d)
         : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq))
      {}

      Data(const Data &d, const allocator_t &a)
         : value_compare(static_cast<const value_compare&>(d)), m_seq(d.m_seq, a)
      {}

      Data(BOOST_RV_REF(Data) d, const allocator_t &a)
         : value_compare(boost::move(static_cast<value_compare&>(d))), m_seq(boost::move(d.m_seq), a)
      {}

      Data& operator=(BOOST_COPY_ASSIGN_REF(Data) d)
      {
         this->value_compare::operator=(d);
         m_seq = d.m_seq;
         return *this;
      }

      Data& operator=(BOOST_RV_REF(Data) d)
      {
         this->value_compare::operator=(boost::move(static_cast<value_compare &>(d)));
         m_seq = boost::move(d.m_seq);
         return *this;
      }

      void swap(Data &d)
      {
         value_compare& mycomp    = *this, & othercomp = d;
         boost::adl_move_swap(mycomp, othercomp);
         this->m_seq.swap(d.m_seq);
      }

      container_type m_seq;
   };

   Data m_data;
   BOOST_COPYABLE_AND_MOVABLE(flat_tree)

   public:

   typedef typename container_type::value_type               value_type;
   typedef typename container_type::pointer                  pointer;
   typedef typename container_type::const_pointer            const_pointer;
   typedef typename container_type::reference                reference;
   typedef typename container_type::const_reference          const_reference;
   typedef typename KeyOfValue::type                        key_type;
   typedef Compare                                          key_compare;
   typedef typename container_type::allocator_type           allocator_type;
   typedef typename container_type::size_type                size_type;
   typedef typename container_type::difference_type          difference_type;
   typedef typename container_type::iterator                 iterator;
   typedef typename container_type::const_iterator           const_iterator;
   typedef typename container_type::reverse_iterator         reverse_iterator;
   typedef typename container_type::const_reverse_iterator   const_reverse_iterator;

   //!Standard extension
   typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
      (boost::container::dtl::, container_type
      ,stored_allocator_type, allocator_type)               stored_allocator_type;

   static const bool has_stored_allocator_type =
      BOOST_INTRUSIVE_HAS_TYPE(boost::container::dtl::, container_type, stored_allocator_type);

   private:
   typedef allocator_traits<stored_allocator_type> stored_allocator_traits;

   public:
   typedef typename dtl::if_c
      <has_stored_allocator_type, const stored_allocator_type &, allocator_type>::type get_stored_allocator_const_return_t;

   typedef typename dtl::if_c
      <has_stored_allocator_type, stored_allocator_type &, allocator_type>::type get_stored_allocator_noconst_return_t;

   BOOST_CONTAINER_FORCEINLINE flat_tree()
      : m_data()
   { }

   BOOST_CONTAINER_FORCEINLINE explicit flat_tree(const Compare& comp)
      : m_data(comp)
   { }

   BOOST_CONTAINER_FORCEINLINE explicit flat_tree(const allocator_type& a)
      : m_data(a)
   { }

   BOOST_CONTAINER_FORCEINLINE flat_tree(const Compare& comp, const allocator_type& a)
      : m_data(comp, a)
   { }

   BOOST_CONTAINER_FORCEINLINE flat_tree(const flat_tree& x)
      :  m_data(x.m_data)
   { }

   BOOST_CONTAINER_FORCEINLINE flat_tree(BOOST_RV_REF(flat_tree) x)
      BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
      :  m_data(boost::move(x.m_data))
   { }

   BOOST_CONTAINER_FORCEINLINE flat_tree(const flat_tree& x, const allocator_type &a)
      :  m_data(x.m_data, a)
   { }

   BOOST_CONTAINER_FORCEINLINE flat_tree(BOOST_RV_REF(flat_tree) x, const allocator_type &a)
      :  m_data(boost::move(x.m_data), a)
   { }

   template <class InputIterator>
   BOOST_CONTAINER_FORCEINLINE
   flat_tree( ordered_range_t, InputIterator first, InputIterator last)
      : m_data()
   {
      this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
      BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
   }

   template <class InputIterator>
   BOOST_CONTAINER_FORCEINLINE
   flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
      : m_data(comp)
   {
      this->m_data.m_seq.insert(this->m_data.m_seq.end(), first, last);
      BOOST_ASSERT((is_sorted)(this->m_data.m_seq.cbegin(), this->m_data.m_seq.cend(), this->priv_value_comp()));
   }

   template <class InputIterator>
   BOOST_CONTAINER_FORCEINLINE
   flat_tree( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)

include/boost/container/detail/flat_tree.hpp  view on Meta::CPAN

   {
      this->priv_range_insertion_construct(unique_insertion, first, last);
   }

   template <class InputIterator>
   BOOST_CONTAINER_FORCEINLINE
   flat_tree( bool unique_insertion, InputIterator first, InputIterator last
            , const Compare& comp)
      : m_data(comp)
   {
      this->priv_range_insertion_construct(unique_insertion, first, last);
   }

   template <class InputIterator>
   BOOST_CONTAINER_FORCEINLINE
   flat_tree( bool unique_insertion, InputIterator first, InputIterator last
            , const allocator_type& a)
      : m_data(a)
   {
      this->priv_range_insertion_construct(unique_insertion, first, last);
   }

   template <class InputIterator>
   BOOST_CONTAINER_FORCEINLINE
   flat_tree( bool unique_insertion, InputIterator first, InputIterator last
            , const Compare& comp, const allocator_type& a)
      : m_data(comp, a)
   {
      this->priv_range_insertion_construct(unique_insertion, first, last);
   }

   BOOST_CONTAINER_FORCEINLINE ~flat_tree()
   {}

   BOOST_CONTAINER_FORCEINLINE flat_tree&  operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x)
   {  m_data = x.m_data;   return *this;  }

   BOOST_CONTAINER_FORCEINLINE flat_tree&  operator=(BOOST_RV_REF(flat_tree) x)
      BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
                          allocator_traits_type::is_always_equal::value) &&
                           boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
   {  m_data = boost::move(x.m_data); return *this;  }

   BOOST_CONTAINER_FORCEINLINE const value_compare &priv_value_comp() const
   { return static_cast<const value_compare &>(this->m_data); }

   BOOST_CONTAINER_FORCEINLINE value_compare &priv_value_comp()
   { return static_cast<value_compare &>(this->m_data); }

   BOOST_CONTAINER_FORCEINLINE const key_compare &priv_key_comp() const
   { return this->priv_value_comp().get_comp(); }

   BOOST_CONTAINER_FORCEINLINE key_compare &priv_key_comp()
   { return this->priv_value_comp().get_comp(); }

   struct insert_commit_data
   {
      const_iterator position;
   };

   public:
   // accessors:
   BOOST_CONTAINER_FORCEINLINE Compare key_comp() const
   { return this->m_data.get_comp(); }

   BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const
   { return this->m_data; }

   BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const
   { return this->m_data.m_seq.get_allocator(); }

   BOOST_CONTAINER_FORCEINLINE get_stored_allocator_const_return_t get_stored_allocator() const
   {
      return flat_tree_get_stored_allocator(this->m_data.m_seq, dtl::bool_<has_stored_allocator_type>());
   }

   BOOST_CONTAINER_FORCEINLINE get_stored_allocator_noconst_return_t get_stored_allocator()
   {
      return flat_tree_get_stored_allocator(this->m_data.m_seq, dtl::bool_<has_stored_allocator_type>());
   }

   BOOST_CONTAINER_FORCEINLINE iterator begin()
   { return this->m_data.m_seq.begin(); }

   BOOST_CONTAINER_FORCEINLINE const_iterator begin() const
   { return this->cbegin(); }

   BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const
   { return this->m_data.m_seq.begin(); }

   BOOST_CONTAINER_FORCEINLINE iterator end()
   { return this->m_data.m_seq.end(); }

   BOOST_CONTAINER_FORCEINLINE const_iterator end() const
   { return this->cend(); }

   BOOST_CONTAINER_FORCEINLINE const_iterator cend() const
   { return this->m_data.m_seq.end(); }

   BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin()
   { return reverse_iterator(this->end()); }

   BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const
   {  return this->crbegin();  }

   BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const
   {  return const_reverse_iterator(this->cend());  }

   BOOST_CONTAINER_FORCEINLINE reverse_iterator rend()
   { return reverse_iterator(this->begin()); }

   BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const
   { return this->crend(); }

   BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const
   { return const_reverse_iterator(this->cbegin()); }

   BOOST_CONTAINER_FORCEINLINE bool empty() const
   { return this->m_data.m_seq.empty(); }

   BOOST_CONTAINER_FORCEINLINE size_type size() const
   { return this->m_data.m_seq.size(); }

   BOOST_CONTAINER_FORCEINLINE size_type max_size() const
   { return this->m_data.m_seq.max_size(); }

   BOOST_CONTAINER_FORCEINLINE void swap(flat_tree& other)
      BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
                                 && boost::container::dtl::is_nothrow_swappable<Compare>::value )
   {  this->m_data.swap(other.m_data);  }

   public:
   // insert/erase
   std::pair<iterator,bool> insert_unique(const value_type& val)
   {
      std::pair<iterator,bool> ret;
      insert_commit_data data;
      ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data);
      ret.first = ret.second ? this->priv_insert_commit(data, val)
                             : this->begin() + (data.position - this->cbegin());
                             //: iterator(vector_iterator_get_ptr(data.position));
      return ret;
   }

   std::pair<iterator,bool> insert_unique(BOOST_RV_REF(value_type) val)
   {
      std::pair<iterator,bool> ret;
      insert_commit_data data;
      ret.second = this->priv_insert_unique_prepare(KeyOfValue()(val), data);
      ret.first = ret.second ? this->priv_insert_commit(data, boost::move(val))
                             : this->begin() + (data.position - this->cbegin());
                             //: iterator(vector_iterator_get_ptr(data.position));
      return ret;
   }

   iterator insert_equal(const value_type& val)
   {
      iterator i = this->upper_bound(KeyOfValue()(val));
      i = this->m_data.m_seq.insert(i, val);
      return i;
   }

   iterator insert_equal(BOOST_RV_REF(value_type) mval)
   {
      iterator i = this->upper_bound(KeyOfValue()(mval));
      i = this->m_data.m_seq.insert(i, boost::move(mval));
      return i;
   }

   iterator insert_unique(const_iterator hint, const value_type& val)
   {
      BOOST_ASSERT(this->priv_in_range_or_end(hint));
      insert_commit_data data;
      return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data)
            ? this->priv_insert_commit(data, val)
            : this->begin() + (data.position - this->cbegin());
            //: iterator(vector_iterator_get_ptr(data.position));
   }

   iterator insert_unique(const_iterator hint, BOOST_RV_REF(value_type) val)
   {
      BOOST_ASSERT(this->priv_in_range_or_end(hint));
      insert_commit_data data;
      return this->priv_insert_unique_prepare(hint, KeyOfValue()(val), data)
         ? this->priv_insert_commit(data, boost::move(val))
         : this->begin() + (data.position - this->cbegin());
         //: iterator(vector_iterator_get_ptr(data.position));
   }

   iterator insert_equal(const_iterator hint, const value_type& val)
   {
      BOOST_ASSERT(this->priv_in_range_or_end(hint));