index/detail/priority_dequeue.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2021, Oracle and/or its affiliates.
0004 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0005
0006 // Licensed under the Boost Software License version 1.0.
0007 // http://www.boost.org/users/license.html
0008
0009 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_PRIORITY_DEQUEUE_HPP
0010 #define BOOST_GEOMETRY_INDEX_DETAIL_PRIORITY_DEQUEUE_HPP
0011
0012 #include <vector>
0013
0014 #include <boost/geometry/index/detail/maxmin_heap.hpp>
0015
0016 namespace boost { namespace geometry { namespace index { namespace detail
0017 {
0018
0019 template
0020 <
0021     typename T,
0022     typename Container = std::vector<T>,
0023     typename Compare = std::less<typename Container::value_type>
0024 >
0025 class priority_dequeue
0026 {
0027 public:
0028     using container_type = Container;
0029     using value_compare = Compare;
0030     using value_type = typename Container::value_type;
0031     using size_type = typename Container::size_type;
0032     using reference = typename Container::reference;
0033     using const_reference = typename Container::const_reference;
0034
0035     priority_dequeue()
0036         : c(), comp()
0037     {}
0038
0039     explicit priority_dequeue(Compare const& compare)
0040         : c(), comp(compare)
0041     {}
0042
0043     priority_dequeue(Compare const& compare, Container const& cont)
0044         : c(cont), comp(compare)
0045     {
0046         make_maxmin_heap(c.begin(), c.end(), comp);
0047     }
0048
0049     priority_dequeue(Compare const& compare, Container&& cont)
0050         : c(std::move(cont)), comp(compare)
0051     {
0052         make_maxmin_heap(c.begin(), c.end(), comp);
0053     }
0054
0055     template <typename It>
0056     priority_dequeue(It first, It last)
0057         : c(first, last), comp()
0058     {
0059         make_maxmin_heap(c.begin(), c.end(), comp);
0060     }
0061
0062     template <typename It>
0063     priority_dequeue(It first, It last, Compare const& compare)
0064         : c(first, last), comp(compare)
0065     {
0066         make_maxmin_heap(c.begin(), c.end(), comp);
0067     }
0068
0069     template <typename It>
0070     priority_dequeue(It first, It last, Compare const& compare, Container const& cont)
0071         : c(cont), comp(compare)
0072     {
0073         c.insert(first, last);
0074         make_maxmin_heap(c.begin(), c.end(), comp);
0075     }
0076
0077     template <typename It>
0078     priority_dequeue(It first, It last, Compare const& compare, Container&& cont)
0079         : c(std::move(cont)), comp(compare)
0080     {
0081         c.insert(first, last);
0082         make_maxmin_heap(c.begin(), c.end(), comp);
0083     }
0084
0085     const_reference top() const
0086     {
0087         return *c.begin();
0088     }
0089
0090     const_reference bottom() const
0091     {
0092         return bottom_maxmin_heap(c.begin(), c.end(), comp);
0093     }
0094
0095     void push(const value_type& value)
0096     {
0097         c.push_back(value);
0098         push_maxmin_heap(c.begin(), c.end(), comp);
0099     }
0100
0101     void push(value_type&& value)
0102     {
0103         c.push_back(std::move(value));
0104         push_maxmin_heap(c.begin(), c.end(), comp);
0105     }
0106
0107     template <typename ...Args>
0108     void emplace(Args&& ...args)
0109     {
0110         c.emplace_back(std::forward<Args>(args)...);
0111         push_maxmin_heap(c.begin(), c.end(), comp);
0112     }
0113
0114     void pop_top()
0115     {
0116         pop_top_maxmin_heap(c.begin(), c.end(), comp);
0117         c.pop_back();
0118     }
0119
0120     void pop_bottom()
0121     {
0122         pop_bottom_maxmin_heap(c.begin(), c.end(), comp);
0123         c.pop_back();
0124     }
0125
0126     bool empty() const
0127     {
0128         return c.empty();
0129     }
0130
0131     size_t size() const
0132     {
0133         return c.size();
0134     }
0135
0136     void swap(priority_dequeue& other)
0137     {
0138         using std::swap;
0139         std::swap(c, other.c);
0140         std::swap(comp, other.comp);
0141     }
0142
0143 protected:
0144     Container c;
0145     Compare comp;
0146 };
0147
0148 }}}} // namespace boost::geometry::index::detail
0149
0150 #endif // BOOST_GEOMETRY_INDEX_DETAIL_PRIORITY_DEQUEUE_HPP