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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#ifndef PAIRING_PQ_H
#define PAIRING_PQ_H
#include "Eecs281PQ.h"
//A specialized version of the 'priority_queue' ADT implemented as a pairing priority_queue.
template<typename TYPE, typename COMP_FUNCTOR = std::less<TYPE>>
class PairingPQ : 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) where n is number of elements in range.
template<typename InputIterator>
PairingPQ(InputIterator start, InputIterator end, COMP_FUNCTOR comp = COMP_FUNCTOR());
//Description: Construct an empty priority_queue with an optional comparison functor.
//Runtime: O(1)
PairingPQ(COMP_FUNCTOR comp = COMP_FUNCTOR());
//Description: Copy constructor.
//Runtime: O(n)
PairingPQ(const PairingPQ& other);
//Description: Copy assignment operator.
//Runtime: O(n)
PairingPQ& operator=(const PairingPQ& rhs);
//Description: Destructor
//Runtime: O(n)
~PairingPQ();
//Description: Add a new element to the priority_queue.
//Runtime: Amortized O(1)
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(log(n))
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.
//Runtime: O(1)
virtual size_type size() const {
//Fill this in
return 0;
}
//Description: Return true if the priority_queue is empty.
//Runtime: O(1)
virtual bool empty() const {
//Fill this in
return true;
}
class Node {
public:
Node(const TYPE & val)
: elt(val), sibling(nullptr), child(nullptr)
{}
public:
//Description: Allows access to the element at that Node's position.
//Runtime: O(1) - this has been provided for you.
const TYPE& operator*() const { return elt; }
const Node* sibling_ptr() const { return sibling; }
const Node* child_ptr() const { return child; }
//The following line allows you to access any private data members of this
//Node class from within the pairing_priority_queue class. (ie: myNode.elt is a legal
//statement in PairingPQ's add_node() function).
friend PairingPQ;
private:
TYPE elt;
Node* sibling;
Node* child;
};
const Node* root_ptr() const { return root; }
private:
Node* root;
//***Add any additional member functions or data you require here.
//***We recommend creating a 'meld' function (see the spec).
};
template<typename TYPE, typename COMP_FUNCTOR>
template<typename InputIterator>
PairingPQ<TYPE, COMP_FUNCTOR>::PairingPQ(
InputIterator,
InputIterator,
COMP_FUNCTOR
) {
//Your code.
}
template<typename TYPE, typename COMP_FUNCTOR>
PairingPQ<TYPE, COMP_FUNCTOR>::PairingPQ(COMP_FUNCTOR) {
//Your code.
}
template<typename TYPE, typename COMP_FUNCTOR>
PairingPQ<TYPE, COMP_FUNCTOR>::PairingPQ(const PairingPQ&) {
//Your code.
}
template<typename TYPE, typename COMP_FUNCTOR>
PairingPQ<TYPE, COMP_FUNCTOR>&
PairingPQ<TYPE, COMP_FUNCTOR>::operator=(const PairingPQ&) {
//Your code.
return *this;
}
template<typename TYPE, typename COMP_FUNCTOR>
PairingPQ<TYPE, COMP_FUNCTOR>::~PairingPQ() {
//Your code.
}
template<typename TYPE, typename COMP_FUNCTOR>
void PairingPQ<TYPE, COMP_FUNCTOR>::pop() {
//Your code.
}
template<typename TYPE, typename COMP_FUNCTOR>
const TYPE& PairingPQ<TYPE, COMP_FUNCTOR>::top() const {
//Your code.
//These lines present only so that this provided file compiles.
static TYPE removeTheseLines;
return removeTheseLines;
}
template<typename TYPE, typename COMP_FUNCTOR>
void PairingPQ<TYPE, COMP_FUNCTOR>::push(const TYPE&) {
//Your code.
}
#endif //PAIRING_H