priority_deque.hpp

Go to the documentation of this file.

/*----------------------------------------------------------------------------*\
|   Copyright (C) 2012-2013 Nathaniel McClatchey                               |
|   Released under the Boost Software License Version 1.0, which may be found  |
| at http://www.boost.org/LICENSE_1_0.txt                                      |
\*----------------------------------------------------------------------------*/

#ifndef BOOST_CONTAINER_PRIORITY_DEQUE_HPP_
#define BOOST_CONTAINER_PRIORITY_DEQUE_HPP_

#ifndef __cplusplus
#error priority_deque.hpp requires a C++ compiler.
#endif

//  Default comparison (std::less)
#include <functional>
//  Default container (std::vector)
#include <vector>
//  Grab std::move, if available.
#if (__cplusplus >= 201103L)
#include <utility>
#endif
//  Interval-heap management.
#include "interval_heap.hpp"

//  Choose the best available version of the assert macro.
#ifdef BOOST_ASSERT_MSG
#define BOOST_CONTAINER_PRIORITY_DEQUE_ASSERT(x,m) BOOST_ASSERT_MSG(x,m)
#elif defined assert
#define BOOST_CONTAINER_PRIORITY_DEQUE_ASSERT(x,m) assert(x)
#else
#define BOOST_CONTAINER_PRIORITY_DEQUE_ASSERT(x,m)
#endif

namespace boost {
namespace container {
template <typename Type, typename Sequence =std::vector<Type>,
          typename Compare =::std::less<typename Sequence::value_type> >
class priority_deque;

template <typename Type, typename Sequence, typename Compare>
void swap (priority_deque<Type, Sequence, Compare>& deque1,
           priority_deque<Type, Sequence, Compare>& deque2);

//----------------------------Priority Deque Class-----------------------------|
template <typename Type, typename Sequence, typename Compare>
class priority_deque {
//----------------------------------Public-------------------------------------|
 public:
//---------------------------------Typedefs------------------------------------|
  typedef Sequence                                    container_type;
  typedef typename container_type::value_type         value_type;
  typedef Compare                                     value_compare;
  typedef typename container_type::size_type          size_type;
  typedef typename container_type::const_reference    const_reference;
  typedef typename container_type::reference          reference;
  typedef typename container_type::pointer            pointer;
  typedef pointer                                     const_pointer;
  typedef typename container_type::const_iterator     const_iterator;
  typedef const_iterator                              iterator;
  typedef typename container_type::difference_type    difference_type;
//-------------------------------Constructors----------------------------------|
#if (__cplusplus >= 201103L)
  explicit priority_deque             (const Compare& =Compare(),
                                       Sequence&& =Sequence());
  priority_deque                      (const Compare&, const Sequence&);
#else
  explicit priority_deque             (const Compare& =Compare(),
                                       const Sequence& =Sequence());
#endif
#if (__cplusplus >= 201103L)
  template <typename InputIterator>
  priority_deque                      (InputIterator first, InputIterator last,
                                       const Compare& =Compare(),
                                       Sequence&& =Sequence());
  template <typename InputIterator>
  priority_deque                      (InputIterator first, InputIterator last,
                                       const Compare&, const Sequence&);
#else
  template <typename InputIterator>
  priority_deque                      (InputIterator first, InputIterator last,
                                       const Compare& =Compare(),
                                       const Sequence& =Sequence());
#endif
//-----------------------------Restricted Access-------------------------------|
  void                    push        (const value_type&);
#if (__cplusplus >= 201103L)
  void                    push        (value_type&&);
  template<typename... Args>
  void                    emplace     (Args&&...);
#endif

  const_reference         maximum     (void) const;
  const_reference         minimum     (void) const;
  inline const_reference  top         (void) const  { return maximum(); };
  void                    pop_maximum (void);
  void                    pop_minimum (void);
  inline void             pop         (void)        { pop_maximum(); };

//--------------------------------Deque Size-----------------------------------|
  inline bool             empty       (void) const  {return sequence_.empty();};
  inline size_type        size        (void) const  {return sequence_.size(); };
  inline size_type        max_size    (void) const  {
    return sequence_.max_size();
  };

//--------------------------Whole-Deque Operations-----------------------------|
  inline void             clear       (void)        { sequence_.clear();      };
  void                    swap        (priority_deque<Type, Sequence,Compare>&);
  template <typename InputIterator>
  void                    merge       (InputIterator first, InputIterator last);
  template <typename SourceContainer>
  inline void             merge       (const SourceContainer& source) {
    merge(source.begin(), source.end());
  }

//-------------------------------Random Access---------------------------------|
  inline const_iterator   begin       (void) const  {return sequence_.begin();};
  inline const_iterator   end         (void) const  { return sequence_.end(); };
  void                    update      (const_iterator, const value_type&);
#if (__cplusplus >= 201103L)
  void                    update      (const_iterator, value_type&&);
#endif
  void                    erase       (const_iterator);

//---------------------------Boost.Heap Concepts-------------------------------|
// size() has constant complexity
  static const bool constant_time_size    = true;
// priority deque does not have ordered iterators
  static const bool has_ordered_iterators = false;
// priority deque is efficiently mergable
  static const bool is_mergable           = true;
// priority deque does not have a stable heap order
  static const bool is_stable             = false;
// priority deque does not have a reserve() member
  static const bool has_reserve           = false;

//--------------------------------Protected------------------------------------|
 protected:
  inline container_type&        sequence  (void)        { return sequence_; };
  inline const container_type&  sequence  (void) const  { return sequence_; };
  inline value_compare&         compare   (void)        { return compare_; };
  inline const value_compare&   compare   (void) const  { return compare_; };
//---------------------------------Private-------------------------------------|
 private:
  Sequence sequence_;
  Compare compare_;
};

//-------------------------------Constructors----------------------------------|
//----------------------------Default Constructor------------------------------|
template <typename T, typename S, typename C>
priority_deque<T, S, C>::priority_deque (const C& comp, const S& seq)
  : sequence_(seq), compare_(comp)
{
  heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
}
#if (__cplusplus >= 201103L)
template <typename T, typename S, typename C>
priority_deque<T, S, C>::priority_deque (const C& comp, S&& seq)
  : sequence_(std::move(seq)), compare_(comp)
{
  heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
}
#endif

//---------------------------Create from Iterators-----------------------------|
template <typename T, typename S, typename C>
template <typename InputIterator>
priority_deque<T, S, C>::priority_deque (InputIterator first,InputIterator last,
                                         const C& comp, const S& seq)
: sequence_(seq), compare_(comp)
{
  try {
    sequence_.insert(sequence_.end(), first, last);
    heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
  } catch (...) {
    heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
    throw;
  }
}
#if (__cplusplus >= 201103L)
template <typename T, typename S, typename C>
template <typename InputIterator>
priority_deque<T, S, C>::priority_deque (InputIterator first,InputIterator last,
                                         const C& comp, S&& seq)
: sequence_(std::move(seq)), compare_(comp)
{
  try {
    sequence_.insert(sequence_.end(), first, last);
    heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
  } catch (...) {
    heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
    throw;
  }
}
#endif

//-----------------------------Restricted Access-------------------------------|
//------------------------------Insert / Emplace-------------------------------|
template <typename T, typename Sequence, typename Compare>
void priority_deque<T, Sequence, Compare>::push (const value_type& value) {
  try {
    sequence_.push_back(value);
  } catch (...) {
    heap::push_interval_heap(sequence_.begin(), sequence_.end(), compare_);
    throw;
  }
  heap::push_interval_heap(sequence_.begin(), sequence_.end(), compare_);
}
#if (__cplusplus >= 201103L)
template <typename T, typename Sequence, typename Compare>
void priority_deque<T, Sequence, Compare>::push (value_type&& value) {
  try {
    sequence_.push_back(std::move(value));
  } catch (...) {
    heap::push_interval_heap(sequence_.begin(), sequence_.end(), compare_);
    throw;
  }
  heap::push_interval_heap(sequence_.begin(), sequence_.end(), compare_);
}

template <typename T, typename Sequence, typename Compare>
template<typename... Args>
void priority_deque<T, Sequence, Compare>::emplace (Args&&... args) {
  try {
    sequence_.emplace_back(std::forward<Args>(args)...);
  } catch (...) {
    heap::push_interval_heap(sequence_.begin(), sequence_.end(), compare_);
    throw;
  }
  heap::push_interval_heap(sequence_.begin(), sequence_.end(), compare_);
}
#endif

//---------------------------Observe Maximum/Minimum---------------------------|
template <typename T, typename Sequence, typename Compare>
inline typename priority_deque<T, Sequence, Compare>::const_reference
  priority_deque<T, Sequence, Compare>::maximum  (void) const
{
  BOOST_CONTAINER_PRIORITY_DEQUE_ASSERT(!empty(),
    "Empty priority deque has no maximal element. Reference undefined.");
  const_iterator it = sequence_.begin() + 1;
  return (it == sequence_.end()) ? sequence_.front() : *it;
}
template <typename T, typename Sequence, typename Compare>
typename priority_deque<T, Sequence, Compare>::const_reference
  priority_deque<T, Sequence, Compare>::minimum  (void) const
{
  BOOST_CONTAINER_PRIORITY_DEQUE_ASSERT(!empty(),
    "Empty priority deque has no minimal element. Reference undefined.");
  return sequence_.front();
}
//---------------------------Remove Maximum/Minimum----------------------------|
template <typename T, typename Sequence, typename Compare>
void priority_deque<T, Sequence, Compare>::pop_minimum (void) {
  BOOST_CONTAINER_PRIORITY_DEQUE_ASSERT(!empty(),
    "Empty priority deque has no maximal element. Removal impossible.");
  heap::pop_interval_heap_min(sequence_.begin(), sequence_.end(), compare_);
  try {
    sequence_.pop_back();
  } catch (...) {
//  If pop_back has a strong guarantee, this will restore the heap.
    heap::push_interval_heap(sequence_.begin(), sequence_.end(), compare_);
    throw;
  }
}
template <typename T, typename Sequence, typename Compare>
void priority_deque<T, Sequence, Compare>::pop_maximum (void) {
  BOOST_CONTAINER_PRIORITY_DEQUE_ASSERT(!empty(),
    "Empty priority deque has no minimal element. Removal undefined.");
  heap::pop_interval_heap_max(sequence_.begin(), sequence_.end(), compare_);
  try {
    sequence_.pop_back();
  } catch (...) {
//  If pop_back has a strong guarantee, this will restore the heap.
    heap::push_interval_heap(sequence_.begin(), sequence_.end(), compare_);
    throw;
  }
}

//--------------------------Whole-Deque Operations-----------------------------|
//-----------------------------------Merge-------------------------------------|
template <typename T, typename S, typename C>
template <typename InputIterator>
void priority_deque<T, S, C>::merge (InputIterator first, InputIterator last) {
  try {
    sequence_.insert(sequence_.end(), first, last);
    heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
  } catch (...) { //  Try to fix the problem.
    heap::make_interval_heap(sequence_.begin(), sequence_.end(), compare_);
    throw;
  }
}

//----------------------------Swap Specialization------------------------------|
template <typename T, typename S, typename C>
inline void priority_deque<T, S, C>::swap (priority_deque<T, S, C>& other) {
  sequence_.swap(other.sequence_);
}

template <typename T, typename S, typename C>
inline void swap (priority_deque<T, S, C>& deque1,
                  priority_deque<T, S, C>& deque2)
{
  deque1.swap(deque2);
}

//---------------------------Random-Access Mutators----------------------------|
template <typename T, typename S, typename C>
void priority_deque<T, S, C>::update (const_iterator random_it,
                                      const value_type& value)
{
  const difference_type index = random_it - begin();
  BOOST_CONTAINER_PRIORITY_DEQUE_ASSERT((0 <= index) &&
    (index < end() - begin()), "Iterator out of bounds; can't set element.");
//  Providing the strong guarantee would require saving a copy.
  *(sequence_.begin() + index) = value;
  heap::update_interval_heap(sequence_.begin(),sequence_.end(),index,compare_);
}
#if (__cplusplus >= 201103L)
template <typename T, typename S, typename C>
void priority_deque<T, S, C>::update (const_iterator random_it,
                                      value_type&& value)
{
  const difference_type index = random_it - begin();
  BOOST_CONTAINER_PRIORITY_DEQUE_ASSERT((0 <= index) &&
    (index < end() - begin()), "Iterator out of bounds; can't set element.");
//  Providing the strong guarantee would require saving a copy.
  *(sequence_.begin() + index) = std::move(value);
  heap::update_interval_heap(sequence_.begin(),sequence_.end(),index,compare_);
}
#endif

template <typename T, typename Sequence, typename Compare>
void priority_deque<T, Sequence, Compare>::erase (const_iterator random_it) {
  const difference_type index = random_it - begin();
  BOOST_CONTAINER_PRIORITY_DEQUE_ASSERT((0 <= index) &&
    (index < end() - begin()), "Iterator out of bounds; can't erase element.");
  heap::pop_interval_heap(sequence_.begin(), sequence_.end(),index,compare_);
  try {
    sequence_.pop_back();
  } catch (...) {
//  If pop_back has the strong guarantee, this will re-make the interval heap.
    heap::push_interval_heap(sequence_.begin(), sequence_.end(), compare_);
    throw;
  }
}

} //  Namespace boost::container
} //  Namespace boost

#endif