Rudiments

- Main Page
- Classes

singlylinkedlistinlines.h
1 // Copyright (c) 2014 David Muse
2 // See the COPYING file for more information
3
4 #include <rudiments/stdio.h>
5 #include <rudiments/private/rudimentsinlines.h>
6 #include <rudiments/private/linkedlistutilinlines.h>
7
8 #define SINGLYLINKEDLIST_TEMPLATE template <class valuetype>
9
10 #define SINGLYLINKEDLIST_CLASS singlylinkedlist<valuetype>
11
12 SINGLYLINKEDLIST_TEMPLATE
13 RUDIMENTS_TEMPLATE_INLINE
14 SINGLYLINKEDLIST_CLASS::singlylinkedlist() {
15 first=NULL;
16 last=NULL;
17 length=0;
18 }
19
20 SINGLYLINKEDLIST_TEMPLATE
21 RUDIMENTS_TEMPLATE_INLINE
22 SINGLYLINKEDLIST_CLASS::~singlylinkedlist() {
23 clear();
24 }
25
26 SINGLYLINKEDLIST_TEMPLATE
27 RUDIMENTS_TEMPLATE_INLINE
28 void SINGLYLINKEDLIST_CLASS::prepend(valuetype value) {
29 prepend(new singlylinkedlistnode<valuetype>(value));
30 }
31
32 SINGLYLINKEDLIST_TEMPLATE
33 RUDIMENTS_TEMPLATE_INLINE
34 void SINGLYLINKEDLIST_CLASS::prepend(singlylinkedlistnode<valuetype> *node) {
35 if (!node) {
36 return;
37 } else if (first) {
38 node->setNext(first);
39 first=node;
40 } else {
41 first=node;
42 last=first;
43 }
44 length++;
45 }
46
47 SINGLYLINKEDLIST_TEMPLATE
48 RUDIMENTS_TEMPLATE_INLINE
49 void SINGLYLINKEDLIST_CLASS::append(valuetype value) {
50 append(new singlylinkedlistnode<valuetype>(value));
51 }
52
53 SINGLYLINKEDLIST_TEMPLATE
54 RUDIMENTS_TEMPLATE_INLINE
55 void SINGLYLINKEDLIST_CLASS::append(singlylinkedlistnode<valuetype> *node) {
56 if (!node) {
57 return;
58 } else if (last) {
59 last->setNext(node);
60 last=node;
61 } else {
62 first=node;
63 last=first;
64 }
65 length++;
66 }
67
68 SINGLYLINKEDLIST_TEMPLATE
69 RUDIMENTS_TEMPLATE_INLINE
70 void SINGLYLINKEDLIST_CLASS::insertAfter(
71 singlylinkedlistnode<valuetype> *node,
72 valuetype value) {
73 insertAfter(node,new singlylinkedlistnode<valuetype>(value));
74 }
75
76 SINGLYLINKEDLIST_TEMPLATE
77 RUDIMENTS_TEMPLATE_INLINE
78 void SINGLYLINKEDLIST_CLASS::insertAfter(
79 singlylinkedlistnode<valuetype> *node,
80 singlylinkedlistnode<valuetype> *newnode) {
81 if (!node) {
82 return;
83 } else if (node==last) {
84 append(newnode);
85 } else {
86 newnode->setNext(node->getNext());
87 node->setNext(newnode);
88 length++;
89 }
90 }
91
92 SINGLYLINKEDLIST_TEMPLATE
93 RUDIMENTS_TEMPLATE_INLINE
94 void SINGLYLINKEDLIST_CLASS::moveAfter(
95 singlylinkedlistnode<valuetype> *node,
96 singlylinkedlistnode<valuetype> *nodetomove) {
97
98 if (!node || !nodetomove || node==nodetomove) {
99 return;
100 }
101
102 if (nodetomove==first) {
103 first=nodetomove->getNext();
104 } else if (nodetomove==last) {
105 singlylinkedlistnode<valuetype> *secondtolast=first;
106 while (secondtolast->getNext()!=last) {
107 secondtolast=secondtolast->getNext();
108 }
109 last=secondtolast;
110 secondtolast->setNext(NULL);
111 } else {
112 singlylinkedlistnode<valuetype> *previous=first;
113 while (previous->getNext()!=nodetomove) {
114 previous=previous->getNext();
115 }
116 previous->setNext(nodetomove->getNext());
117 }
118
119 nodetomove->setNext(node->getNext());
120 node->setNext(nodetomove);
121 if (node==last) {
122 last=nodetomove;
123 }
124 }
125
126 SINGLYLINKEDLIST_TEMPLATE
127 RUDIMENTS_TEMPLATE_INLINE
128 void SINGLYLINKEDLIST_CLASS::detach(singlylinkedlistnode<valuetype> *node) {
129
130 if (node==first && node==last) {
131 first=NULL;
132 last=NULL;
133 } else if (node==first) {
134 first=node->getNext();
135 } else if (node==last) {
136 singlylinkedlistnode<valuetype> *secondtolast=first;
137 while (secondtolast->getNext()!=last) {
138 secondtolast=secondtolast->getNext();
139 }
140 last=secondtolast;
141 secondtolast->setNext(NULL);
142 } else {
143 singlylinkedlistnode<valuetype> *previous=first;
144 while (previous->getNext()!=node) {
145 previous=previous->getNext();
146 }
147 previous->setNext(node->getNext());
148 }
149 node->setNext(NULL);
150 length--;
151 }
152
153 SINGLYLINKEDLIST_TEMPLATE
154 RUDIMENTS_TEMPLATE_INLINE
155 bool SINGLYLINKEDLIST_CLASS::remove(valuetype value) {
156 singlylinkedlistnode<valuetype> *current=first;
157 if (!current->compare(value)) {
158 if (first==last) {
159 first=NULL;
160 last=NULL;
161 } else {
162 first=first->getNext();
163 }
164 } else {
165 singlylinkedlistnode<valuetype> *prev=first;
166 current=current->getNext();
167 while (current) {
168 if (!current->compare(value)) {
169 prev->setNext(current->getNext());
170 break;
171 }
172 prev=current;
173 current=current->getNext();
174 }
175 if (last==current) {
176 last=prev;
177 }
178 }
179 if (current) {
180 delete current;
181 length--;
182 return true;
183 }
184 return false;
185 }
186
187 SINGLYLINKEDLIST_TEMPLATE
188 RUDIMENTS_TEMPLATE_INLINE
189 bool SINGLYLINKEDLIST_CLASS::removeAll(valuetype value) {
190 if (!first) {
191 return true;
192 }
193 bool retval=false;
194 singlylinkedlistnode<valuetype> *current=first;
195 while (!current->compare(value)) {
196 retval=true;
197 if (first==last) {
198 first=NULL;
199 last=NULL;
200 delete current;
201 length--;
202 return true;
203 } else {
204 first=first->getNext();
205 delete current;
206 length--;
207 current=first;
208 }
209 }
210 singlylinkedlistnode<valuetype> *prev=first;
211 current=current->getNext();
212 while (current) {
213 if (!current->compare(value)) {
214 retval=true;
215 singlylinkedlistnode<valuetype> *temp=
216 current->getNext();
217 prev->setNext(temp);
218 if (last==current) {
219 last=prev;
220 }
221 delete current;
222 length--;
223 current=temp;
224 } else {
225 prev=current;
226 current=current->getNext();
227 }
228 }
229 return retval;
230 }
231
232 SINGLYLINKEDLIST_TEMPLATE
233 RUDIMENTS_TEMPLATE_INLINE
234 bool SINGLYLINKEDLIST_CLASS::remove(singlylinkedlistnode<valuetype> *node) {
235 if (!node) {
236 return false;
237 }
238 singlylinkedlistnode<valuetype> *current=first;
239 if (current==node) {
240 if (first==last) {
241 first=NULL;
242 last=NULL;
243 } else {
244 first=first->getNext();
245 }
246 } else {
247 singlylinkedlistnode<valuetype> *prev=first;
248 current=current->getNext();
249 while (current) {
250 if (current==node) {
251 prev->setNext(current->getNext());
252 break;
253 }
254 prev=current;
255 current=current->getNext();
256 }
257 if (last==current) {
258 last=prev;
259 }
260 }
261 if (current) {
262 delete current;
263 length--;
264 return true;
265 }
266 return false;
267 }
268
269 SINGLYLINKEDLIST_TEMPLATE
270 RUDIMENTS_TEMPLATE_INLINE
271 uint64_t SINGLYLINKEDLIST_CLASS::getLength() const {
272 return length;
273 }
274
275 SINGLYLINKEDLIST_TEMPLATE
276 RUDIMENTS_TEMPLATE_INLINE
277 singlylinkedlistnode<valuetype> *SINGLYLINKEDLIST_CLASS::getFirst() {
278 return first;
279 }
280
281 SINGLYLINKEDLIST_TEMPLATE
282 RUDIMENTS_TEMPLATE_INLINE
283 singlylinkedlistnode<valuetype> *SINGLYLINKEDLIST_CLASS::getLast() {
284 return last;
285 }
286
287 SINGLYLINKEDLIST_TEMPLATE
288 RUDIMENTS_TEMPLATE_INLINE
289 singlylinkedlistnode<valuetype> *SINGLYLINKEDLIST_CLASS::getNext(
290 singlylinkedlistnode<valuetype> *node) {
291 return (node)?node->getNext():NULL;
292 }
293
294 SINGLYLINKEDLIST_TEMPLATE
295 RUDIMENTS_TEMPLATE_INLINE
296 singlylinkedlistnode<valuetype> *SINGLYLINKEDLIST_CLASS::find(valuetype value) {
297 return find((singlylinkedlistnode<valuetype> *)first,value);
298 }
299
300 SINGLYLINKEDLIST_TEMPLATE
301 RUDIMENTS_TEMPLATE_INLINE
302 singlylinkedlistnode<valuetype> *SINGLYLINKEDLIST_CLASS::find(
303 singlylinkedlistnode<valuetype> *startnode,
304 valuetype value) {
305 for (singlylinkedlistnode<valuetype> *current=startnode;
306 current; current=current->getNext()) {
307 if (!current->compare(value)) {
308 return current;
309 }
310 }
311 return NULL;
312 }
313
314 SINGLYLINKEDLIST_TEMPLATE
315 RUDIMENTS_TEMPLATE_INLINE
316 void SINGLYLINKEDLIST_CLASS::insertionSort() {
317
318 // insertion sort with a few optimization...
319
320 // if there are 0 or 1 items in the list then it's already sorted
321 if (length<2) {
322 return;
323 }
324
325 // first and last pointers for the new list
326 singlylinkedlistnode<valuetype> *newfirst=NULL;
327 singlylinkedlistnode<valuetype> *newlast=NULL;
328
329 // pointers for iterating through the new list
330 singlylinkedlistnode<valuetype> *current=NULL;
331 singlylinkedlistnode<valuetype> *previous=NULL;
332
333 // iterate through the current list, building a new one as we go
334 singlylinkedlistnode<valuetype> *node=first;
335 singlylinkedlistnode<valuetype> *next=NULL;
336 while (node) {
337
338 // get the next node so we can move on later
339 next=node->getNext();
340
341 // if the new list is empty
342 if (!newfirst) {
343 node->setNext(NULL);
344 newfirst=node;
345 newlast=node;
346 } else
347
348 // if the node belongs at the beginning of the new list
349 // (optimization for lists that are already largely forwards)
350 if (newfirst->compare(node)>0) {
351 node->setNext(newfirst);
352 newfirst=node;
353 } else
354
355 // if the node belongs at the end of the new list
356 // (optimization for lists that are already largely backwards)
357 if (newlast->compare(node)<=0) {
358 node->setNext(NULL);
359 newlast->setNext(node);
360 newlast=node;
361 } else
362
363 // if the node belongs somewhere in the middle of the new list
364 {
365 // search from the left...
366 current=newfirst->getNext();
367 previous=newfirst;
368 while (current) {
369
370 // if the current node is greater than...
371 if (current->compare(node)>0) {
372
373 // insert before
374 node->setNext(current);
375 previous->setNext(node);
376 break;
377 }
378
379 // move on
380 previous=current;
381 current=current->getNext();
382 }
383 }
384
385 // move on
386 node=next;
387 }
388
389 // make the new list the current list
390 first=newfirst;
391 last=newlast;
392 }
393
394 SINGLYLINKEDLIST_TEMPLATE
395 RUDIMENTS_TEMPLATE_INLINE
396 void SINGLYLINKEDLIST_CLASS::heapSort() {
397
398 // if there are 0 or 1 items in the list then it's already sorted
399 if (length<2) {
400 return;
401 }
402
403 // build heap as a binary tree mapped to an array:
404 // parentindex = floor((childindex-1)/2)
405 // leftchildindex = parent*2+1
406 // rightchildindex = parent*2+2
407 singlylinkedlistnode<valuetype> **heap=
408 new singlylinkedlistnode<valuetype> *[length];
409 singlylinkedlistnode<valuetype> *temp=NULL;
410 uint64_t heapend=0;
411 for (singlylinkedlistnode<valuetype> *node=first;
412 node; node=node->getNext()) {
413
414 // insert node into heap
415 heap[heapend]=node;
416
417 // walk up the tree, maintaining the heap property
418 // (higher values higher up in the tree)
419 uint64_t child=heapend;
420 while (child) {
421
422 // get the parent index
423 uint64_t parent=(child-1)/2;
424
425 // swap nodes if necessary
426 if (heap[parent]->compare(heap[child])<0) {
427 temp=heap[parent];
428 heap[parent]=heap[child];
429 heap[child]=temp;
430 }
431
432 // move up
433 child=parent;
434 }
435
436 // move on
437 heapend++;
438 }
439
440 // reset the heap end index
441 heapend--;
442
443 // Build a new list from the heap by swapping the root and last leaf
444 // node (index 0 is the root and the last index is the last leaf),
445 // pulling the value off of the last leaf node, and sifting the tree to
446 // maintain the heap property (higher values higher up in the tree),
447 // over and over again. We'll shortcut the swap and pull-off part a
448 // bit...
449
450 // first and last pointers for the new list
451 singlylinkedlistnode<valuetype> *newfirst=NULL;
452 singlylinkedlistnode<valuetype> *newlast=NULL;
453
454 // extract values from the heap...
455 for (;;) {
456
457 // pull off the highest value (which is always at the root
458 // of the tree, index 0 in the array) and prepend it to the
459 // new array
460 singlylinkedlistnode<valuetype> *node=heap[0];
461 if (!newfirst) {
462 node->setNext(NULL);
463 newfirst=node;
464 newlast=node;
465 } else {
466 node->setNext(newfirst);
467 newfirst=node;
468 }
469
470 // when the tree is empty, we're done
471 if (!heapend) {
472
473 // make the new list the current list
474 first=newfirst;
475 last=newlast;
476
477 // clean up
478 delete[] heap;
479 return;
480 }
481
482 // move the value at the last leaf node (end of the array)
483 // to the root node (index 0 of the array)
484 heap[0]=heap[heapend];
485 heapend--;
486
487 // sift the tree to maintain the heap property
488 // (higher values higher up in the tree)
489 uint64_t parent=0;
490 for (;;) {
491
492 // make sure there's at least a left child
493 uint64_t leftchild=parent*2+1;
494 if (leftchild>heapend) {
495 break;
496 }
497
498 // is the left child greater?
499 uint64_t greater=parent;
500 if (heap[parent]->compare(heap[leftchild])<0) {
501 greater=leftchild;
502 }
503
504 // is the right child greater?
505 uint64_t rightchild=leftchild+1;
506 if (rightchild<=heapend &&
507 heap[rightchild]->compare(heap[greater])>0) {
508 greater=rightchild;
509 }
510
511 // if the parent was greater than each child then
512 // we don't need to continue sifting
513 if (greater==parent) {
514 break;
515 }
516
517 // if one of the children was greater than the parent
518 // then swap them and continue down the tree in the
519 // direction of the child that was swapped
520 temp=heap[parent];
521 heap[parent]=heap[greater];
522 heap[greater]=temp;
523 parent=greater;
524 }
525 }
526 }
527
528 SINGLYLINKEDLIST_TEMPLATE
529 RUDIMENTS_TEMPLATE_INLINE
530 void SINGLYLINKEDLIST_CLASS::clear() {
531 singlylinkedlistnode<valuetype> *next;
532 singlylinkedlistnode<valuetype> *current=first;
533 while (current) {
534 next=current->getNext();
535 delete current;
536 current=next;
537 }
538 first=NULL;
539 last=NULL;
540 length=0;
541 }
542
543 SINGLYLINKEDLIST_TEMPLATE
544 RUDIMENTS_TEMPLATE_INLINE
545 void SINGLYLINKEDLIST_CLASS::print() const {
546 print(length);
547 }
548
549 SINGLYLINKEDLIST_TEMPLATE
550 RUDIMENTS_TEMPLATE_INLINE
551 void SINGLYLINKEDLIST_CLASS::print(uint64_t count) const {
552 uint64_t i=0;
553 for (singlylinkedlistnode<valuetype> *current=first;
554 current && i<count; current=current->getNext()) {
555 #ifdef RUDIMENTS_HAVE_LONG_LONG
556 stdoutput.printf("index %lld: ",(long long)i);
557 #else
558 stdoutput.printf("index %ld: ",(long)i);
559 #endif
560 current->print();
561 stdoutput.printf("\n");
562 i++;
563 }
564 }
565
566 #define SINGLYLINKEDLISTNODE_TEMPLATE template <class valuetype>
567
568 #define SINGLYLINKEDLISTNODE_CLASS singlylinkedlistnode<valuetype>
569
570 SINGLYLINKEDLISTNODE_TEMPLATE
571 RUDIMENTS_TEMPLATE_INLINE
572 SINGLYLINKEDLISTNODE_CLASS::singlylinkedlistnode(valuetype value) {
573 this->value=value;
574 next=NULL;
575 }
576
577 SINGLYLINKEDLISTNODE_TEMPLATE
578 RUDIMENTS_TEMPLATE_INLINE
579 SINGLYLINKEDLISTNODE_CLASS::~singlylinkedlistnode() {
580 }
581
582 SINGLYLINKEDLISTNODE_TEMPLATE
583 RUDIMENTS_TEMPLATE_INLINE
584 void SINGLYLINKEDLISTNODE_CLASS::setValue(valuetype value) {
585 this->value=value;
586 }
587
588 SINGLYLINKEDLISTNODE_TEMPLATE
589 RUDIMENTS_TEMPLATE_INLINE
590 valuetype SINGLYLINKEDLISTNODE_CLASS::getValue() const {
591 return value;
592 }
593
594 SINGLYLINKEDLISTNODE_TEMPLATE
595 RUDIMENTS_TEMPLATE_INLINE
596 SINGLYLINKEDLISTNODE_CLASS *SINGLYLINKEDLISTNODE_CLASS::getNext() {
597 return next;
598 }
599
600 SINGLYLINKEDLISTNODE_TEMPLATE
601 RUDIMENTS_TEMPLATE_INLINE
602 int32_t SINGLYLINKEDLISTNODE_CLASS::compare(valuetype value) const {
603 return _linkedlistutil_compare(this->value,value);
604 }
605
606 SINGLYLINKEDLISTNODE_TEMPLATE
607 RUDIMENTS_TEMPLATE_INLINE
608 int32_t SINGLYLINKEDLISTNODE_CLASS::compare(
609 singlylinkedlistnode<valuetype> *peer) const {
610 return _linkedlistutil_compare(this->value,peer->value);
611 }
612
613 SINGLYLINKEDLISTNODE_TEMPLATE
614 RUDIMENTS_TEMPLATE_INLINE
615 void SINGLYLINKEDLISTNODE_CLASS::print() const {
616 _linkedlistutil_print(value);
617 }
618
619 SINGLYLINKEDLISTNODE_TEMPLATE
620 RUDIMENTS_TEMPLATE_INLINE
621 void SINGLYLINKEDLISTNODE_CLASS::setNext(SINGLYLINKEDLISTNODE_CLASS *next) {
622 this->next=next;
623 }
singlylinkedlistnode::getNext
singlylinkedlistnode< valuetype > * getNext()
singlylinkedlistnode::print
void print() const
filedescriptor::printf
size_t printf(const char *format,...)
singlylinkedlistnode
Definition: singlylinkedlist.h:12
singlylinkedlistnode::compare
int32_t compare(valuetype value) const