Rudiments

- Main Page
- Classes

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