00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #ifndef CPRIORITYQUEUE_H
00016 #define CPRIORITYQUEUE_H
00017
00018 #include "stdvector.h"
00019 #include <algorithm>
00020 #include <functional>
00021
00023
00028 template <class T, class Container = std::vector<T>,
00029 #if defined(_MSC_VER)
00030 class Compare = std::greater<Container::value_type> >
00031 #else
00032 class Compare = std::greater<typename Container::value_type> >
00033 #endif
00034 class CPriorityQueue {
00035 public:
00036 typedef typename Container::value_type value_type;
00037 typedef typename Container::size_type size_type;
00038 typedef typename Container::iterator iterator;
00039 typedef typename Container::const_iterator const_iterator;
00040 typedef Container container_type;
00041
00042 CPriorityQueue() { }
00043 CPriorityQueue(Container& swappedIn) { swap(swappedIn); }
00044 ~CPriorityQueue() { }
00045
00047
00048
00050 void push(const value_type& v)
00051 {
00052 c.push_back(v);
00053 std::push_heap(c.begin(), c.end(), comp);
00054 }
00055
00057 void pop()
00058 {
00059 std::pop_heap(c.begin(), c.end(), comp);
00060 c.pop_back();
00061 }
00062
00064 void erase(iterator i)
00065 {
00066 c.erase(i);
00067 std::make_heap(c.begin(), c.end(), comp);
00068 }
00069
00071 iterator begin()
00072 {
00073 return c.begin();
00074 }
00075
00077 iterator end()
00078 {
00079 return c.end();
00080 }
00081
00083 void swap(CPriorityQueue<T, Container, Compare>& q)
00084 {
00085 c.swap(q.c);
00086 }
00087
00089 void swap(Container& c2)
00090 {
00091 c.swap(c2);
00092 std::make_heap(c.begin(), c.end(), comp);
00093 }
00094
00096
00097
00098
00100 bool empty() const
00101 {
00102 return c.empty();
00103 }
00104
00106 size_type size() const
00107 {
00108 return c.size();
00109 }
00110
00112 const value_type& top() const
00113 {
00114 return c.front();
00115 }
00116
00118 const_iterator begin() const
00119 {
00120 return c.begin();
00121 }
00122
00124 const_iterator end() const
00125 {
00126 return c.end();
00127 }
00128
00130
00131 private:
00132 Container c;
00133 Compare comp;
00134 };
00135
00136 #endif