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