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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#ifndef SORTED_PQ_H
#define SORTED_PQ_H
#include "Eecs281PQ.h"
//A specialized version of the 'priority_queue' ADT that is implemented with an
//underlying sorted array-based container.
//Note: The most extreme element should be found at the end of the
//'data' container, such that traversing the iterators yields the elements in
//sorted order.
template<typename TYPE, typename COMP_FUNCTOR = std::less<TYPE>>
class SortedPQ : public Eecs281PQ<TYPE, COMP_FUNCTOR> {
public:
typedef unsigned size_type;
//Description: Construct a priority_queue out of an iterator range with an optional
// comparison functor.
//Runtime: O(n log n) where n is number of elements in range.
template<typename InputIterator>
SortedPQ(InputIterator start, InputIterator end, COMP_FUNCTOR comp = COMP_FUNCTOR());
//Description: Construct an empty priority_queue with an optional comparison functor.
//Runtime: O(1)
SortedPQ(COMP_FUNCTOR comp = COMP_FUNCTOR());
//Description: Add a new element to the priority_queue.
//Runtime: O(n)
virtual void push(const TYPE& val);
//Description: Remove the most extreme (defined by 'compare') element from
// the priority_queue.
//Note: We will not run tests on your code that would require it to pop an
//element when the priority_queue is empty. Though you are welcome to if you are
//familiar with them, you do not need to use exceptions in this project.
//Runtime: Amortized O(1)
virtual void pop();
//Description: Return the most extreme (defined by 'compare') element of
// the priority_queue.
//Runtime: O(1)
virtual const TYPE& top() const;
//Description: Get the number of elements in the priority_queue. This has been
// implemented for you.
//Runtime: O(1)
virtual size_type size() const { return data.size(); }
//Description: Return true if the priority_queue is empty. This has been implemented
// for you.
//Runtime: O(1)
virtual bool empty() const { return data.empty(); }
private:
//Note: This vector *must* be used by your priority_queue implementation.
std::vector<TYPE> data;
private:
//***Add any additional member functions or data you require here.
};
template<typename TYPE, typename COMP_FUNCTOR>
template<typename InputIterator>
SortedPQ<TYPE, COMP_FUNCTOR>::SortedPQ(
InputIterator,
InputIterator,
COMP_FUNCTOR
) {
//Your code.
}
template<typename TYPE, typename COMP_FUNCTOR>
SortedPQ<TYPE, COMP_FUNCTOR>::SortedPQ(COMP_FUNCTOR) {
//Your code.
}
template<typename TYPE, typename COMP_FUNCTOR>
void SortedPQ<TYPE, COMP_FUNCTOR>::push(const TYPE&) {
//Your code.
}
template<typename TYPE, typename COMP_FUNCTOR>
void SortedPQ<TYPE, COMP_FUNCTOR>::pop() {
//Your code.
}
template<typename TYPE, typename COMP_FUNCTOR>
const TYPE& SortedPQ<TYPE, COMP_FUNCTOR>::top() const {
//Your code.
//These lines present only so that this provided file compiles.
static TYPE removeTheseLines;
return removeTheseLines;
}
#endif //SORTED_H