· 5 years ago · Mar 02, 2020, 12:10 AM
1#ifndef _RMQLIST_H
2#define _RMQLIST_H
3
4#include <iostream>
5#include <stdexcept>
6#include <cmath>
7
8using std::swap;
9using std::ostream;
10using std::cout;
11using std::endl;
12using std::sqrt;
13using std::range_error;
14using std::invalid_argument;
15
16// Macro for a two-argument min function
17#define MIN(a, b) ((a) < (b) ? (a) : (b))
18
19// forward declarations
20template <class K, class V> class RMQList;
21template <class K, class V> class Node;
22template <class K, class V> ostream& operator<<(ostream& sout, const Node<K, V>& x);
23
24// *********************************************
25// Node - node class for the RMQList linked list
26// key and value are templated (types K and V)
27// *********************************************
28
29template <class K, class V>
30class Node {
31 friend RMQList<K, V>;
32public:
33 Node(K key = K(), V value = V(), Node<K, V>* next = nullptr) {
34 _key = key;
35 _value = value;
36 _next = next;
37 }
38 friend ostream& operator<< <K, V>(ostream& sout, const Node<K, V>& x);
39private:
40 K _key;
41 V _value;
42 Node* _next;
43};
44
45// Overloaded insertion operator for Node
46template <class K, class V>
47ostream& operator<<(ostream& sout, const Node<K, V>& x) {
48 sout << "Key: " << x._key << ", Value: " << x._value;
49 return sout;
50}
51
52// *******************************************************
53// RMQList - list container (linked list) with RMQ support
54// key and value are templated (types K and V)
55// *******************************************************
56
57template <class K, class V>
58class RMQList {
59public:
60 // Create an empty RMQList object
61 RMQList();
62
63 // Destructor, Copy Constructor, Assignment Operator
64 ~RMQList();
65 RMQList(const RMQList<K, V>& rhs);
66 const RMQList<K, V>& operator=(const RMQList<K, V>& rhs);
67
68 // In-line function. Returns the size (number of elements).
69 int size() const { return _listSize; }
70
71 // In-line function. Returns true if the list is empty; false
72 // otherwise.
73 bool empty() const { return _head == nullptr; }
74
75 // Insert an element into the list; list must be kept in increasing
76 // order by key; duplicate keys are not allowed, so return false if
77 // there is already an entry with the specified key, true otherwise.
78 // Should check if key > largest current key and, if so, append to
79 // the end of the list without iteration.
80 bool insert(const K& key, const V& value);
81
82 // Remove an element from the list; return false if no element
83 // exists with the specified key value, true otherwise
84 bool remove(const K& key);
85
86 // Update value for the element with given key; return false if
87 // there is no element with the given key, true otherwise
88 bool update(const K& key, const V& value);
89
90 // RMQ Query for k1 to k2. Throws exceptions (see documentation).
91 V query(const K& k1, const K& k2);
92
93 // Dump the list entries
94 void dumpList() const;
95
96 // Dump the RMQ info and table. What gets dumped depends on which
97 // RMQ method is used.
98 void dumpTable() const;
99
100 // Clear the data data strucures
101 void clear();
102
103private:
104 Node<K, V>* _head;
105 Node<K, V>* _tail;
106 int _listSize;
107
108
109 // **********************************
110 // Private variables for RMQ go here!
111 // **********************************
112
113 // *******************************************
114 // Declarations for private functions go here!
115 // *******************************************
116 void sort();
117};
118
119
120template <class K, class V>
121RMQList<K, V>::RMQList() {
122 _head = nullptr;
123 _tail = nullptr;
124 _listSize = 0;
125}
126
127template <class K, class V>
128RMQList<K, V>::~RMQList() {
129
130 while (_head != nullptr)
131 {
132 Node<K,V>* currentNode = _head;
133 _head = _head->_next;
134 delete(currentNode);
135 }
136
137}
138
139template <class K, class V>
140RMQList<K, V>::RMQList(const RMQList<K, V>& rhs) {
141 _listSize = rhs._listSize;
142 _head = rhs._head;
143 _tail = rhs._tail;
144 Node <K, V>* copytemp = _head;
145 for (Node <K, V> *temp = rhs._head; rhs != rhs._tail; temp = temp->_next){
146
147 if (temp != nullptr) {
148 copytemp = new Node<K, V>(temp->_key, temp->_value, nullptr);
149 }
150 }
151 {
152 copytemp = copytemp->next;
153 }
154
155 }
156
157template <class K, class V>
158const RMQList<K, V>& RMQList<K, V>::operator=(const RMQList<K, V>& rhs) {
159 if (!empty()) {
160 if (this != &rhs) {
161 for (Node <K, V>* temp = _head; temp != _tail; temp = temp->_next) {
162 if (temp != nullptr) {
163 delete temp;
164 }
165 }
166
167 }
168 }
169 _listSize = rhs._listSize;
170 _head = rhs._head;
171 _tail = rhs._tail;
172 Node <K, V>* copytemp = _head;
173 for (Node <K, V> *temp = rhs._head; rhs != this._tail; temp = temp->_next) {
174
175 if (temp != nullptr) {
176 copytemp = new Node<K, V>(temp->_key, temp->_value, nullptr);
177 }
178 }
179 {
180 copytemp = copytemp->next;
181 }
182
183}
184
185
186template <class K, class V>
187bool RMQList<K, V>::insert(const K& key, const V& value) {
188
189}
190
191
192template <class K, class V>
193bool RMQList<K, V>::remove(const K& key) {
194}
195
196template <class K, class V>
197bool RMQList<K, V>::update(const K& key, const V& value) {
198}
199
200template <class K, class V>
201V RMQList<K, V>::query(const K& k1, const K& k2) {
202}
203
204template <class K, class V>
205void RMQList<K, V>::dumpList() const {
206}
207
208template <class K, class V>
209void RMQList<K, V>::dumpTable() const {
210}
211
212template <class K, class V>
213void RMQList<K, V>::clear() {
214 clear();
215}
216
217#endif