Bridges-C++ 3.5.0-dev2-1-ge3e57bf
Bridges(C++ API)
DLelement.h
Go to the documentation of this file.
1#ifndef DLelement_H
2#define DLelement_H
3
4#include "SLelement.h" //string, using std
5
6namespace bridges {
7 namespace datastructure {
23 template<typename E>
24 class DLelement: public SLelement<E> {
25 private:
26
27 DLelement* prev = nullptr;// The pointer to the previous DLelement
28
29 public:
40 DLelement(DLelement* n, DLelement* p = nullptr, const E& val = E(),
41 const string& lab = string()) : SLelement<E>(n, val, lab) {
42 setPrev(p);
43 }
44
53 DLelement (const E& val = E(), const string& lab = string()) :
54 DLelement(nullptr, nullptr, val, lab) {
55 }
56
63 virtual const string getDStype() const override {
64 return "DoublyLinkedList";
65 }
71 virtual DLelement* getNext() override {
72 return static_cast<DLelement*>(SLelement<E>::getNext());
73 }
74
80 virtual const DLelement* getNext() const override {
81 return static_cast<const DLelement*>(SLelement<E>::getNext());
82 }
89 void setNext(DLelement* n) {
90 if (this->next != n && this->next != prev) {
91 //if different, remove old link data
92 this->links.erase(this->next);
93 }
94 if ((this->next = n)) {
95 this->links[this->next];
96 }
97 }
102 virtual DLelement* getPrev() {
103 return prev;
104 }
110 virtual const DLelement* getPrev() const {
111 return prev;
112 }
118 virtual void setPrev(DLelement* p) {
119 if (prev != p && this->next != prev) {
120 this->links.erase(prev); //if different, remove old link data
121 }
122 // set prev to p and if not null, create
123 // default link data if none already present
124 if ((prev = p)) {
125 this->links[prev];
126 }
127 }
128
129 private:
130
131 virtual const string getDataStructureRepresentation() const override {
132
133 vector<const DLelement<E>*> nodes;
134
135 // get the list of nodes
136
137 getListElements(nodes);
138
139 // generate the JSON string
140
141 if (MAX_ELEMENTS_ALLOWED <= nodes.size()) {
142 // cant exceed max number of elements
143 throw "Max allowed elements(for visualization) exceeded.. " +
144 to_string(nodes.size()) + " Must be less than " +
145 to_string(MAX_ELEMENTS_ALLOWED);
146 }
147
148 // map the nodes to a sequence of ids, 0...N-1
149 // then get the JSON string for nodes placeholder
150 // nullptr prevents insertion of other nullptrs
151 unordered_map<const DLelement*, int> node_map { {nullptr, -1} };
152
153 string nodes_JSON, links_JSON;
154
155 int i = 0; // get the JSON string for nodes
156 for (const auto * e : nodes) {
157 if (node_map.emplace(e, i).second) {
158 // successful emplacement
159 i++;
160 nodes_JSON += e->getElementRepresentation() + COMMA;
161 }
162 }
163
164 //Remove trailing comma and nullptr entry
165 node_map.erase(nullptr);
166 if (nodes_JSON.size()) {
167 nodes_JSON = nodes_JSON.erase(nodes_JSON.size() - 1);
168 }
169
170 // generate the links using the node map ids
171 for (int k = 0; k < nodes.size(); k++) {
172 if (nodes[k]->next != nullptr) { // link exists
173 links_JSON += this->getLinkRepresentation(nodes[k]->links.at(nodes[k]->next),
174 to_string(node_map[nodes[k]]),
175 to_string(node_map[nodes[k]->getNext()]) ) + COMMA;
176 }
177 if (nodes[k]->prev != nullptr) { // link exists
178 links_JSON += this->getLinkRepresentation(nodes[k]->links.at(nodes[k]->prev),
179 to_string(node_map[nodes[k]]),
180 to_string(node_map[nodes[k]->prev]) ) + COMMA;
181 }
182 }
183
184 //Remove trailing comma
185 if (links_JSON.size()) {
186 links_JSON = links_JSON.erase(links_JSON.size() - 1);
187 }
188
189 string dl_list_json =
190 QUOTE + "nodes" + QUOTE + COLON +
191 OPEN_BOX + nodes_JSON + CLOSE_BOX + COMMA +
192 QUOTE + "links" + QUOTE + COLON +
193 OPEN_BOX + links_JSON + CLOSE_BOX +
195
196 return dl_list_json;
197 }
198
204 virtual void getListElements(vector<const DLelement<E>*>&
205 nodes) const {
206
207 //prevents potential infinite loop
208 unordered_set<const DLelement<E>*> visited;
209 auto it = this;
210
211 // using the visited array handles both regular and
212 // circular lists
213 while (it != nullptr && visited.emplace(it).second) {
214 nodes.push_back(it);
215 it = it->getNext();
216 }
217 }
218 public:
219
224 typename bridges::datastructure::DLelement<E> *start, *last;
225
226 public:
228 : start(s) {
229
230 // determine the last element
231 auto el = s;
232 if (el) {
233 for (el = s; el->getNext() != nullptr; el = el->getNext());
234 last = el;
235 }
236 }
237
238 class iterator {
239
240 typename bridges::datastructure::DLelement<E> *current;
241
242 public:
243
245 : current(c)
246 {}
247
248 bool operator!= (const iterator& it) const {
249 return this->current != it.current;
250 }
251
252 E const & operator* () const {
253 return current->getValue();
254 }
255
257 return current->getValue();
258 }
259
261 current = current->getNext();
262 return *this;
263 }
265 iterator clone(*this);
266 current = current->getNext();
267 return clone;
268 }
270 current = current->getPrev();
271 return *this;
272 }
274 iterator clone(*this);
275 current = current->getPrev();
276 return clone;
277 }
278 };
279
280 // forward iteration
282 return iterator(start);
283 }
284
286 return iterator(nullptr);
287 }
288
289 // reverse iteration
291 return iterator(last);
292 }
294 return iterator(nullptr);
295 }
296
297 };
298
302 typename bridges::datastructure::DLelement<E> const *start, *last;
303
304 public:
306 // determine the last element
307 auto el = s;
308 if (el) {
309 for (el = s; el->getNext() != nullptr; el = el->getNext());
310 last = el;
311 }
312 }
313 class iterator {
314
315 typename bridges::datastructure::DLelement< E > const * current;
316 public:
318 : current(c)
319 {}
320
321 bool operator!=(const iterator& it) const {
322 return this->current != it.current;
323 }
324
325 E const & operator*() const {
326 return current->getValue();
327 }
328
330 current = current->getNext();
331 return *this;
332 }
334 current = current->getPrev();
335 return *this;
336 }
338 iterator clone(*this);
339 current = current->getPrev();
340 return clone;
341 }
342 };
343
344 // forward iteration
346 return iterator(start);
347 }
349 return iterator(nullptr);
350 }
351 // reverse iteration
353 return iterator(last);
354 }
356 return iterator(nullptr);
357 }
358 };
359 }; //end of DLelement class
360 // use some aliases for accessing iterators
361 template <class E>
363 template <class E>
365
366 }
367}//end of bridges namespace
368#endif
iterator(typename bridges::datastructure::DLelement< E > const *c)
Definition: DLelement.h:317
bool operator!=(const iterator &it) const
Definition: DLelement.h:321
E const & operator*() const
Definition: DLelement.h:325
these are helper classes for DLelement for easy iteration in a range for loop. It is not meant to be ...
Definition: DLelement.h:301
DLelement_constlisthelper(typename bridges::datastructure::DLelement< E > const *s)
Definition: DLelement.h:305
iterator(typename bridges::datastructure::DLelement< E > *c)
Definition: DLelement.h:244
E const & operator*() const
Definition: DLelement.h:252
bool operator!=(const iterator &it) const
Definition: DLelement.h:248
these are helper classes for DLelement for easy iteration in a range for loop. It is not meant to be ...
Definition: DLelement.h:223
iterator end()
Definition: DLelement.h:285
iterator begin()
Definition: DLelement.h:281
iterator rbegin()
Definition: DLelement.h:290
iterator rend()
Definition: DLelement.h:293
DLelement_listhelper(typename bridges::datastructure::DLelement< E > *s)
Definition: DLelement.h:227
The doubly linked list element, derived from SLelement.
Definition: DLelement.h:24
virtual DLelement * getNext() override
Definition: DLelement.h:71
virtual const DLelement * getNext() const override
Definition: DLelement.h:80
virtual DLelement * getPrev()
Definition: DLelement.h:102
virtual const string getDStype() const override
Definition: DLelement.h:63
DLelement(DLelement *n, DLelement *p=nullptr, const E &val=E(), const string &lab=string())
Definition: DLelement.h:40
virtual void setPrev(DLelement *p)
Definition: DLelement.h:118
virtual const DLelement * getPrev() const
Definition: DLelement.h:110
void setNext(DLelement *n)
Definition: DLelement.h:89
DLelement(const E &val=E(), const string &lab=string())
Definition: DLelement.h:53
static const string getLinkRepresentation(const LinkVisualizer &lv, const string &src, const string &dest)
Definition: Element.h:310
E const & getValue() const
Gets the object held in the generic object E.
Definition: Element.h:207
unordered_map< Element *, LinkVisualizer > links
Definition: Element.h:92
The singly linked list element, derived from Element.
Definition: SLelement.h:26
virtual SLelement * getNext()
Returns the next element in the list.
Definition: SLelement.h:74
SLelement * next
Definition: SLelement.h:29
constexpr int MAX_ELEMENTS_ALLOWED
Definition: DataStructure.h:62
typename DLelement< E >::DLelement_listhelper DLelement_List
Definition: DLelement.h:362
typename DLelement< E >::DLelement_constlisthelper DLelement_ConstList
Definition: DLelement.h:364
these methods convert byte arrays in to base64 codes and are used in BRIDGES to represent the color a...
Definition: alltypes.h:4
const string COLON
Definition: DataStructure.h:52
const string OPEN_BOX
Definition: DataStructure.h:55
const string COMMA
Definition: DataStructure.h:51
const string CLOSE_BOX
Definition: DataStructure.h:56
const string CLOSE_CURLY
Definition: DataStructure.h:54
const string QUOTE
Definition: DataStructure.h:50