// FILE: DPQueue.h // CLASS PROVIDED: p_queue (priority queue ADT) // // TYPEDEFS and MEMBER CONSTANTS for the p_queue class: // typedef _____ value_type // p_queue::value_type is the data type of the items in // the p_queue. It may be any of the C++ built-in types // (int, char, etc.), or a class with a default constructor, a // copy constructor, an assignment operator, and a less-than // operator forming a strict weak ordering. // // typedef _____ size_type // p_queue::size_type is the data type considered best-suited // for any variable meant for counting and sizing (as well as // array-indexing) purposes; e.g.: it is the data type for a // variable representing how many items are in the p_queue. // It is also the data type of the priority associated with // each item in the p_queue // // static const size_type DEFAULT_CAPACITY = _____ // p_queue::DEFAULT_CAPACITY is the default initial capacity of a // p_queue that is created by the default constructor. // // CONSTRUCTOR for the p_queue class: // p_queue(size_type initial_capacity = DEFAULT_CAPACITY) // Pre: initial_capacity > 0 // Post: The p_queue has been initialized to an empty p_queue. // The push function will work efficiently (without allocating // new memory) until this capacity is reached. // Note: If Pre is not met, initial_capacity will be adjusted to // DEFAULT_CAPACITY. I.e., when creating a p_queue object, // client can override initial_capacity with something deemed // more appropriate than DEFAULT_CAPACITY; but if (in doing so) // client mis-specifies 0 (NOTE: size_type is unsigned, thus // can't be negative) as the overriding size, DEFAULT_CAPACITY // remains as the value to be used for initial_capacity (this // is to ensure no attempt is made at allocating memory that's // 0 in amount). // // MODIFICATION MEMBER FUNCTIONS for the p_queue class: // void push(const value_type& entry, size_type priority) // Pre: (none) // Post: A new copy of item with the specified data and priority // has been added to the p_queue. // // void pop() // Pre: size() > 0. // Post: The highest priority item has been removed from the // p_queue. (If several items have the equal priority, // then the implementation may decide which one to remove.) // // CONSTANT MEMBER FUNCTIONS for the p_queue class: // size_type size() const // Pre: (none) // Post: The return value is the total number of items in the // p_queue. // // value_type front() const // Pre: size() > 0. // Post: The return value is the data of the highest priority // item in the p_queue, but the p_queue is unchanged. // (If several items have equal priority, then the // implementation may decide which one to return.) // // bool empty() const // Pre: (none) // Post: The return value is true if the p_queue is empty, // otherwise false. // // VALUE SEMANTICS for the p_queue class: // Assignments and the copy constructor may be used with p_queue // objects. #ifndef D_P_QUEUE_H #define D_P_QUEUE_H #include // provides size_t namespace CS3358_SP2023_A7 { class p_queue { public: // TYPEDEFS and MEMBER CONSTANTS typedef int value_type; typedef size_t size_type; static const size_type DEFAULT_CAPACITY = 1; // CONSTRUCTORS AND DESTRUCTOR p_queue(size_type initial_capacity = DEFAULT_CAPACITY); p_queue(const p_queue& src); ~p_queue(); // MODIFICATION MEMBER FUNCTIONS p_queue& operator=(const p_queue& rhs); void push(const value_type& entry, size_type priority); void pop(); // CONSTANT MEMBER FUNCTIONS size_type size() const; bool empty() const; value_type front() const; // EXTRA CONSTANT MEMBER FUNCTION FOR DEBUG PRINTING void print_tree(const char message[] = "", size_type i = 0) const; void print_array(const char message[] = "") const; private: // STRUCT to store information about one item in the p_queue struct ItemType { value_type data; size_type priority; }; // PRIVATE MEMBER VARIABLES ItemType *heap; size_type capacity; size_type used; // HELPER FUNCTIONS void resize(size_type new_capacity); bool is_leaf(size_type i) const; size_type parent_index(size_type i) const; size_type parent_priority(size_type i) const; size_type big_child_index(size_type i) const; size_type big_child_priority(size_type i) const; void swap_with_parent(size_type i); }; } #endif
// FILE: DPQueue.h
// CLASS PROVIDED: p_queue (priority queue ADT)
//
// TYPEDEFS and MEMBER CONSTANTS for the p_queue class:
// typedef _____ value_type
// p_queue::value_type is the data type of the items in
// the p_queue. It may be any of the C++ built-in types
// (int, char, etc.), or a class with a default constructor, a
// copy constructor, an assignment operator, and a less-than
// operator forming a strict weak ordering.
//
// typedef _____ size_type
// p_queue::size_type is the data type considered best-suited
// for any variable meant for counting and sizing (as well as
// array-indexing) purposes; e.g.: it is the data type for a
// variable representing how many items are in the p_queue.
// It is also the data type of the priority associated with
// each item in the p_queue
//
// static const size_type DEFAULT_CAPACITY = _____
// p_queue::DEFAULT_CAPACITY is the default initial capacity of a
// p_queue that is created by the default constructor.
//
// CONSTRUCTOR for the p_queue class:
// p_queue(size_type initial_capacity = DEFAULT_CAPACITY)
// Pre: initial_capacity > 0
// Post: The p_queue has been initialized to an empty p_queue.
// The push function will work efficiently (without allocating
// new memory) until this capacity is reached.
// Note: If Pre is not met, initial_capacity will be adjusted to
// DEFAULT_CAPACITY. I.e., when creating a p_queue object,
// client can override initial_capacity with something deemed
// more appropriate than DEFAULT_CAPACITY; but if (in doing so)
// client mis-specifies 0 (NOTE: size_type is unsigned, thus
// can't be negative) as the overriding size, DEFAULT_CAPACITY
// remains as the value to be used for initial_capacity (this
// is to ensure no attempt is made at allocating memory that's
// 0 in amount).
//
// MODIFICATION MEMBER FUNCTIONS for the p_queue class:
// void push(const value_type& entry, size_type priority)
// Pre: (none)
// Post: A new copy of item with the specified data and priority
// has been added to the p_queue.
//
// void pop()
// Pre: size() > 0.
// Post: The highest priority item has been removed from the
// p_queue. (If several items have the equal priority,
// then the implementation may decide which one to remove.)
//
// CONSTANT MEMBER FUNCTIONS for the p_queue class:
// size_type size() const
// Pre: (none)
// Post: The return value is the total number of items in the
// p_queue.
//
// value_type front() const
// Pre: size() > 0.
// Post: The return value is the data of the highest priority
// item in the p_queue, but the p_queue is unchanged.
// (If several items have equal priority, then the
// implementation may decide which one to return.)
//
// bool empty() const
// Pre: (none)
// Post: The return value is true if the p_queue is empty,
// otherwise false.
//
// VALUE SEMANTICS for the p_queue class:
// Assignments and the copy constructor may be used with p_queue
// objects.
#ifndef D_P_QUEUE_H
#define D_P_QUEUE_H
#include <cstdlib> // provides size_t
namespace CS3358_SP2023_A7
{
class p_queue
{
public:
// TYPEDEFS and MEMBER CONSTANTS
typedef int value_type;
typedef size_t size_type;
static const size_type DEFAULT_CAPACITY = 1;
// CONSTRUCTORS AND DESTRUCTOR
p_queue(size_type initial_capacity = DEFAULT_CAPACITY);
p_queue(const p_queue& src);
~p_queue();
// MODIFICATION MEMBER FUNCTIONS
p_queue& operator=(const p_queue& rhs);
void push(const value_type& entry, size_type priority);
void pop();
// CONSTANT MEMBER FUNCTIONS
size_type size() const;
bool empty() const;
value_type front() const;
// EXTRA CONSTANT MEMBER FUNCTION FOR DEBUG PRINTING
void print_tree(const char message[] = "", size_type i = 0) const;
void print_array(const char message[] = "") const;
private:
// STRUCT to store information about one item in the p_queue
struct ItemType
{
value_type data;
size_type priority;
};
// PRIVATE MEMBER VARIABLES
ItemType *heap;
size_type capacity;
size_type used;
// HELPER FUNCTIONS
void resize(size_type new_capacity);
bool is_leaf(size_type i) const;
size_type parent_index(size_type i) const;
size_type parent_priority(size_type i) const;
size_type big_child_index(size_type i) const;
size_type big_child_priority(size_type i) const;
void swap_with_parent(size_type i);
};
}
#endif
![140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
// Post: If the item at heap[i] has no children, true has been
returned, otherwise false has been returned.
{
cerr << "is_leaf (size_type) not implemented yet" << endl;
return false; // dummy return value
P_queue: :size_type
p_queue: :parent_index(size_type i) const
// Pre:
(i > 0) && (i < used)
// Post: The index of "the parent of the item at heap[i]" has
been returned.
{
cerr << "parent_index(size_type) not implemented yet" << endl;
return 0; // dummy return value
p_queue: :size_type
p_queue: :parent_priority (size_type i) const
// Pre:
(i > 0) && (i < used)
// Post: The priority of "the parent of the item at heap[i]" has
been returned.
cerr << "parent_priority (size_type) not implemented yet" << endl;
return 0; // dummy return value
p_queue: :size_type
p_queue:
// Pre:
// Post:
:big_child_index(size_type i) const
is_leaf(i) returns false
The index of "the bigger child of the item at heap[i]"
has been returned.
(The bigger child is the one whose priority is no smaller
than that of the other child, if there is one.)
cerr << "big_child_index(size_type) not implemented yet" << endl;
return 0; // dummy return value
P_queue: :size_type
p_queue: :big_child_priority (size_type i) const
// Pre:
is_leaf(i) returns false
// Post: The priority of "the bigger child of the item at heap[i]"
has been returned.
(The bigger child is the one whose priority is no smaller
than that of the other child, if there is one.)
cerr << "big_child_priority (size_type) not implemented yet" << endl;
return 0; // dummy return value
}
void p_queue: :swap_with_parent (size_type i)
// Pre:
(i > 0) && (i < used)
// Post: The item at heap[i] has been swapped with its parent.
{
cerr << "swap_with_parent (size_type) not implemented yet" << endl;](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fb51b654d-3a22-424d-90a5-d3d04b635cc6%2Fb1ce36e6-5410-4d97-a2e9-f3a6c8109c62%2F3881avm_processed.png&w=3840&q=75)
![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
// CONSTRUCTORS AND DESTRUCTOR
P_queue: :p_queue (size_type initial_capacity)
cerr << "p_queue () not implemented yet" << endl;
P_queue: :p_queue (const p_queue& src)
cerr << "p_queue (const p_queue&) not implemented yet" << endl;
p_queue::~p_queue ()
cerr << "~p_queue () not implemented yet" << endl;
}
// MODIFICATION MEMBER FUNCTIONS
p_queue& p_queue::operator=(const p_queue& rhs)
cerr << "operator= (const p_queue&) not implemented yet" << endl;
return *this;
}
void p_queue: :push(const value_type& entry, size_type priority)
cerr << "push(const value_type&, size_type) not implemented yet" << endl;
}
void p_queue: :pop()
cerr << "pop() not implemented yet" << endl;
}
// CONSTANT MEMBER FUNCTIONS
P_queue: :size_type p_queue: :size() const
cerr << "size() not implemented yet" << endl;
return 0; // dummy return value
bool p_queue::empty() const
cerr << "empty() not implemented yet" << endl;
return false; // dummy return value
p_queue::value_type p_queue: :front () const
cerr << "front () not implemented yet" << endl;
return value_type(); // dummy return value
}
// PRIVATE HELPER FUNCTIONS
void p_queue: :resize(size_type new_capacity)
// Pre:
// Post:
S
(none)
The size of the dynamic array pointed to by heap (thus
the capacity of the p_queue) has been resized up or down
to new_capacity, but never Less than used (to prevent
Loss of existing data).
NOTE: ALL existing items in the p_queue are preserved and
used remains unchanged.
cerr << "resize(size_type) not implemented yet" << endl;
bool p_queue::is_leaf (size_type i) const
// Pre: (i < used)
// Post: If the item at heap[i] has no children, true has been
returned, otherwise false has been returned.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fb51b654d-3a22-424d-90a5-d3d04b635cc6%2Fb1ce36e6-5410-4d97-a2e9-f3a6c8109c62%2F51kpsn9_processed.png&w=3840&q=75)
Step by step
Solved in 4 steps with 2 images
