Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#ifndef JARJAR_PQ_H
#define JARJAR_PQ_H
#include "Eecs281PQ.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <vector>
//A bad priority queue that linearly searches for the maximum element every
//time it is requested. You do not need to implement this; it is already done
//for you.
template<typename TYPE, typename COMP_FUNCTOR = std::less<TYPE>>
class JarJarPQ : public Eecs281PQ<TYPE, COMP_FUNCTOR> {
public:
typedef unsigned size_type;
template<typename InputIterator>
JarJarPQ(InputIterator start, InputIterator end, COMP_FUNCTOR comp = COMP_FUNCTOR())
: data(start, end)
{
this->compare = comp;
}
JarJarPQ(COMP_FUNCTOR comp = COMP_FUNCTOR()) {
this->compare = comp;
}
virtual void push(const TYPE& val) {
data.push_back(val);
}
virtual void pop() {
assert(!data.empty());
typename std::vector<TYPE>::iterator it = std::max_element(data.begin(), data.end(), this->compare);
std::iter_swap(it, std::prev(data.end()));
data.pop_back();
}
virtual const TYPE& top() const {
return *std::max_element(data.begin(), data.end(), this->compare);
}
virtual size_type size() const {
return data.size();
}
virtual bool empty() const {
return data.empty();
}
private:
std::vector<TYPE> data;
};
#endif