Rudiments
singlylinkedlistinlines.h
1 // Copyright (c) 1999-2018 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::removeAndDelete(valuetype value) {
189  singlylinkedlistnode<valuetype> *current=first;
190  if (!current->compare(value)) {
191  if (first==last) {
192  first=NULL;
193  last=NULL;
194  } else {
195  first=first->getNext();
196  }
197  } else {
199  current=current->getNext();
200  while (current) {
201  if (!current->compare(value)) {
202  prev->setNext(current->getNext());
203  break;
204  }
205  prev=current;
206  current=current->getNext();
207  }
208  if (last==current) {
209  last=prev;
210  }
211  }
212  if (current) {
213  delete current->getValue();
214  delete current;
215  length--;
216  return true;
217  }
218  return false;
219 }
220 
221 SINGLYLINKEDLIST_TEMPLATE
222 inline
223 bool SINGLYLINKEDLIST_CLASS::removeAndArrayDelete(valuetype value) {
224  singlylinkedlistnode<valuetype> *current=first;
225  if (!current->compare(value)) {
226  if (first==last) {
227  first=NULL;
228  last=NULL;
229  } else {
230  first=first->getNext();
231  }
232  } else {
234  current=current->getNext();
235  while (current) {
236  if (!current->compare(value)) {
237  prev->setNext(current->getNext());
238  break;
239  }
240  prev=current;
241  current=current->getNext();
242  }
243  if (last==current) {
244  last=prev;
245  }
246  }
247  if (current) {
248  delete[] current->getValue();
249  delete current;
250  length--;
251  return true;
252  }
253  return false;
254 }
255 
256 SINGLYLINKEDLIST_TEMPLATE
257 inline
258 bool SINGLYLINKEDLIST_CLASS::removeAll(valuetype value) {
259  if (!first) {
260  return true;
261  }
262  bool retval=false;
263  singlylinkedlistnode<valuetype> *current=first;
264  while (!current->compare(value)) {
265  retval=true;
266  if (first==last) {
267  first=NULL;
268  last=NULL;
269  delete current;
270  length--;
271  return true;
272  } else {
273  first=first->getNext();
274  delete current;
275  length--;
276  current=first;
277  }
278  }
280  current=current->getNext();
281  while (current) {
282  if (!current->compare(value)) {
283  retval=true;
285  current->getNext();
286  prev->setNext(temp);
287  if (last==current) {
288  last=prev;
289  }
290  delete current;
291  length--;
292  current=temp;
293  } else {
294  prev=current;
295  current=current->getNext();
296  }
297  }
298  return retval;
299 }
300 
301 SINGLYLINKEDLIST_TEMPLATE
302 inline
303 bool SINGLYLINKEDLIST_CLASS::removeAllAndDelete(valuetype value) {
304  if (!first) {
305  return true;
306  }
307  bool retval=false;
308  singlylinkedlistnode<valuetype> *current=first;
309  while (!current->compare(value)) {
310  retval=true;
311  if (first==last) {
312  first=NULL;
313  last=NULL;
314  delete current->getValue();
315  delete current;
316  length--;
317  return true;
318  } else {
319  first=first->getNext();
320  delete current->getValue();
321  delete current;
322  length--;
323  current=first;
324  }
325  }
327  current=current->getNext();
328  while (current) {
329  if (!current->compare(value)) {
330  retval=true;
332  current->getNext();
333  prev->setNext(temp);
334  if (last==current) {
335  last=prev;
336  }
337  delete current->getValue();
338  delete current;
339  length--;
340  current=temp;
341  } else {
342  prev=current;
343  current=current->getNext();
344  }
345  }
346  return retval;
347 }
348 
349 SINGLYLINKEDLIST_TEMPLATE
350 inline
351 bool SINGLYLINKEDLIST_CLASS::removeAllAndArrayDelete(valuetype value) {
352  if (!first) {
353  return true;
354  }
355  bool retval=false;
356  singlylinkedlistnode<valuetype> *current=first;
357  while (!current->compare(value)) {
358  retval=true;
359  if (first==last) {
360  first=NULL;
361  last=NULL;
362  delete[] current->getValue();
363  delete current;
364  length--;
365  return true;
366  } else {
367  first=first->getNext();
368  delete[] current->getValue();
369  delete current;
370  length--;
371  current=first;
372  }
373  }
375  current=current->getNext();
376  while (current) {
377  if (!current->compare(value)) {
378  retval=true;
380  current->getNext();
381  prev->setNext(temp);
382  if (last==current) {
383  last=prev;
384  }
385  delete[] current->getValue();
386  delete current;
387  length--;
388  current=temp;
389  } else {
390  prev=current;
391  current=current->getNext();
392  }
393  }
394  return retval;
395 }
396 
397 SINGLYLINKEDLIST_TEMPLATE
398 inline
399 bool SINGLYLINKEDLIST_CLASS::remove(singlylinkedlistnode<valuetype> *node) {
400  if (!node) {
401  return false;
402  }
403  singlylinkedlistnode<valuetype> *current=first;
404  if (current==node) {
405  if (first==last) {
406  first=NULL;
407  last=NULL;
408  } else {
409  first=first->getNext();
410  }
411  } else {
413  current=current->getNext();
414  while (current) {
415  if (current==node) {
416  prev->setNext(current->getNext());
417  break;
418  }
419  prev=current;
420  current=current->getNext();
421  }
422  if (last==current) {
423  last=prev;
424  }
425  }
426  if (current) {
427  delete current;
428  length--;
429  return true;
430  }
431  return false;
432 }
433 
434 SINGLYLINKEDLIST_TEMPLATE
435 inline
436 bool SINGLYLINKEDLIST_CLASS::removeAndDelete(
438  if (!node) {
439  return false;
440  }
441  singlylinkedlistnode<valuetype> *current=first;
442  if (current==node) {
443  if (first==last) {
444  first=NULL;
445  last=NULL;
446  } else {
447  first=first->getNext();
448  }
449  } else {
451  current=current->getNext();
452  while (current) {
453  if (current==node) {
454  prev->setNext(current->getNext());
455  break;
456  }
457  prev=current;
458  current=current->getNext();
459  }
460  if (last==current) {
461  last=prev;
462  }
463  }
464  if (current) {
465  delete current->getValue();
466  delete current;
467  length--;
468  return true;
469  }
470  return false;
471 }
472 
473 SINGLYLINKEDLIST_TEMPLATE
474 inline
475 bool SINGLYLINKEDLIST_CLASS::removeAndArrayDelete(
477  if (!node) {
478  return false;
479  }
480  singlylinkedlistnode<valuetype> *current=first;
481  if (current==node) {
482  if (first==last) {
483  first=NULL;
484  last=NULL;
485  } else {
486  first=first->getNext();
487  }
488  } else {
490  current=current->getNext();
491  while (current) {
492  if (current==node) {
493  prev->setNext(current->getNext());
494  break;
495  }
496  prev=current;
497  current=current->getNext();
498  }
499  if (last==current) {
500  last=prev;
501  }
502  }
503  if (current) {
504  delete[] current->getValue();
505  delete current;
506  length--;
507  return true;
508  }
509  return false;
510 }
511 
512 SINGLYLINKEDLIST_TEMPLATE
513 inline
514 uint64_t SINGLYLINKEDLIST_CLASS::getLength() const {
515  return length;
516 }
517 
518 SINGLYLINKEDLIST_TEMPLATE
519 inline
520 singlylinkedlistnode<valuetype> *SINGLYLINKEDLIST_CLASS::getFirst() {
521  return first;
522 }
523 
524 SINGLYLINKEDLIST_TEMPLATE
525 inline
526 singlylinkedlistnode<valuetype> *SINGLYLINKEDLIST_CLASS::getLast() {
527  return last;
528 }
529 
530 SINGLYLINKEDLIST_TEMPLATE
531 inline
532 singlylinkedlistnode<valuetype> *SINGLYLINKEDLIST_CLASS::getNext(
534  return (node)?node->getNext():NULL;
535 }
536 
537 SINGLYLINKEDLIST_TEMPLATE
538 inline
539 singlylinkedlistnode<valuetype> *SINGLYLINKEDLIST_CLASS::find(valuetype value) {
540  return find((singlylinkedlistnode<valuetype> *)first,value);
541 }
542 
543 SINGLYLINKEDLIST_TEMPLATE
544 inline
545 singlylinkedlistnode<valuetype> *SINGLYLINKEDLIST_CLASS::find(
547  valuetype value) {
548  for (singlylinkedlistnode<valuetype> *current=startnode;
549  current; current=current->getNext()) {
550  if (!current->compare(value)) {
551  return current;
552  }
553  }
554  return NULL;
555 }
556 
557 SINGLYLINKEDLIST_TEMPLATE
558 inline
559 void SINGLYLINKEDLIST_CLASS::insertionSort() {
560 
561  // insertion sort with a few optimization...
562 
563  // if there are 0 or 1 items in the list then it's already sorted
564  if (length<2) {
565  return;
566  }
567 
568  // first and last pointers for the new list
569  singlylinkedlistnode<valuetype> *newfirst=NULL;
570  singlylinkedlistnode<valuetype> *newlast=NULL;
571 
572  // pointers for iterating through the new list
573  singlylinkedlistnode<valuetype> *current=NULL;
574  singlylinkedlistnode<valuetype> *previous=NULL;
575 
576  // iterate through the current list, building a new one as we go
579  while (node) {
580 
581  // get the next node so we can move on later
582  next=node->getNext();
583 
584  // if the new list is empty
585  if (!newfirst) {
586  node->setNext(NULL);
587  newfirst=node;
588  newlast=node;
589  } else
590 
591  // if the node belongs at the beginning of the new list
592  // (optimization for lists that are already largely forwards)
593  if (newfirst->compare(node)>0) {
594  node->setNext(newfirst);
595  newfirst=node;
596  } else
597 
598  // if the node belongs at the end of the new list
599  // (optimization for lists that are already largely backwards)
600  if (newlast->compare(node)<=0) {
601  node->setNext(NULL);
602  newlast->setNext(node);
603  newlast=node;
604  } else
605 
606  // if the node belongs somewhere in the middle of the new list
607  {
608  // search from the left...
609  current=newfirst->getNext();
610  previous=newfirst;
611  while (current) {
612 
613  // if the current node is greater than...
614  if (current->compare(node)>0) {
615 
616  // insert before
617  node->setNext(current);
618  previous->setNext(node);
619  break;
620  }
621 
622  // move on
623  previous=current;
624  current=current->getNext();
625  }
626  }
627 
628  // move on
629  node=next;
630  }
631 
632  // make the new list the current list
633  first=newfirst;
634  last=newlast;
635 }
636 
637 SINGLYLINKEDLIST_TEMPLATE
638 inline
639 void SINGLYLINKEDLIST_CLASS::heapSort() {
640 
641  // if there are 0 or 1 items in the list then it's already sorted
642  if (length<2) {
643  return;
644  }
645 
646  // build heap as a binary tree mapped to an array:
647  // parentindex = floor((childindex-1)/2)
648  // leftchildindex = parent*2+1
649  // rightchildindex = parent*2+2
651  new singlylinkedlistnode<valuetype> *[length];
653  uint64_t heapend=0;
654  for (singlylinkedlistnode<valuetype> *node=first;
655  node; node=node->getNext()) {
656 
657  // insert node into heap
658  heap[heapend]=node;
659 
660  // walk up the tree, maintaining the heap property
661  // (higher values higher up in the tree)
662  uint64_t child=heapend;
663  while (child) {
664 
665  // get the parent index
666  uint64_t parent=(child-1)/2;
667 
668  // swap nodes if necessary
669  if (heap[parent]->compare(heap[child])<0) {
670  temp=heap[parent];
671  heap[parent]=heap[child];
672  heap[child]=temp;
673  }
674 
675  // move up
676  child=parent;
677  }
678 
679  // move on
680  heapend++;
681  }
682 
683  // reset the heap end index
684  heapend--;
685 
686  // Build a new list from the heap by swapping the root and last leaf
687  // node (index 0 is the root and the last index is the last leaf),
688  // pulling the value off of the last leaf node, and sifting the tree to
689  // maintain the heap property (higher values higher up in the tree),
690  // over and over again. We'll shortcut the swap and pull-off part a
691  // bit...
692 
693  // first and last pointers for the new list
694  singlylinkedlistnode<valuetype> *newfirst=NULL;
695  singlylinkedlistnode<valuetype> *newlast=NULL;
696 
697  // extract values from the heap...
698  for (;;) {
699 
700  // pull off the highest value (which is always at the root
701  // of the tree, index 0 in the array) and prepend it to the
702  // new array
703  singlylinkedlistnode<valuetype> *node=heap[0];
704  if (!newfirst) {
705  node->setNext(NULL);
706  newfirst=node;
707  newlast=node;
708  } else {
709  node->setNext(newfirst);
710  newfirst=node;
711  }
712 
713  // when the tree is empty, we're done
714  if (!heapend) {
715 
716  // make the new list the current list
717  first=newfirst;
718  last=newlast;
719 
720  // clean up
721  delete[] heap;
722  return;
723  }
724 
725  // move the value at the last leaf node (end of the array)
726  // to the root node (index 0 of the array)
727  heap[0]=heap[heapend];
728  heapend--;
729 
730  // sift the tree to maintain the heap property
731  // (higher values higher up in the tree)
732  uint64_t parent=0;
733  for (;;) {
734 
735  // make sure there's at least a left child
736  uint64_t leftchild=parent*2+1;
737  if (leftchild>heapend) {
738  break;
739  }
740 
741  // is the left child greater?
742  uint64_t greater=parent;
743  if (heap[parent]->compare(heap[leftchild])<0) {
744  greater=leftchild;
745  }
746 
747  // is the right child greater?
748  uint64_t rightchild=leftchild+1;
749  if (rightchild<=heapend &&
750  heap[rightchild]->compare(heap[greater])>0) {
751  greater=rightchild;
752  }
753 
754  // if the parent was greater than each child then
755  // we don't need to continue sifting
756  if (greater==parent) {
757  break;
758  }
759 
760  // if one of the children was greater than the parent
761  // then swap them and continue down the tree in the
762  // direction of the child that was swapped
763  temp=heap[parent];
764  heap[parent]=heap[greater];
765  heap[greater]=temp;
766  parent=greater;
767  }
768  }
769 }
770 
771 // NOTE: Don't collapse the clear methods into a single method, or the compiler
772 // will attempt to compile calls to:
773 // delete current->getValue();
774 // and
775 // delete[] current->getValue();
776 // even if the app just calls clear(). This will fail for primitive types or
777 // when the type has a private destructor.
778 
779 SINGLYLINKEDLIST_TEMPLATE
780 inline
781 void SINGLYLINKEDLIST_CLASS::clear() {
783  singlylinkedlistnode<valuetype> *current=first;
784  while (current) {
785  next=current->getNext();
786  delete current;
787  current=next;
788  }
789  first=NULL;
790  last=NULL;
791  length=0;
792 }
793 
794 SINGLYLINKEDLIST_TEMPLATE
795 inline
796 void SINGLYLINKEDLIST_CLASS::clearAndDelete() {
798  singlylinkedlistnode<valuetype> *current=first;
799  while (current) {
800  next=current->getNext();
801  delete current->getValue();
802  delete current;
803  current=next;
804  }
805  first=NULL;
806  last=NULL;
807  length=0;
808 }
809 
810 SINGLYLINKEDLIST_TEMPLATE
811 inline
812 void SINGLYLINKEDLIST_CLASS::clearAndArrayDelete() {
814  singlylinkedlistnode<valuetype> *current=first;
815  while (current) {
816  next=current->getNext();
817  delete[] current->getValue();
818  delete current;
819  current=next;
820  }
821  first=NULL;
822  last=NULL;
823  length=0;
824 }
825 
826 SINGLYLINKEDLIST_TEMPLATE
827 inline
828 void SINGLYLINKEDLIST_CLASS::print() const {
829  print(length);
830 }
831 
832 SINGLYLINKEDLIST_TEMPLATE
833 inline
834 void SINGLYLINKEDLIST_CLASS::print(uint64_t count) const {
835  uint64_t i=0;
836  for (singlylinkedlistnode<valuetype> *current=first;
837  current && i<count; current=current->getNext()) {
838  #ifdef RUDIMENTS_HAVE_LONG_LONG
839  stdoutput.printf("index %lld: ",(long long)i);
840  #else
841  stdoutput.printf("index %ld: ",(long)i);
842  #endif
843  current->print();
844  stdoutput.printf("\n");
845  i++;
846  }
847 }
848 
849 #define SINGLYLINKEDLISTNODE_TEMPLATE template <class valuetype>
850 
851 #define SINGLYLINKEDLISTNODE_CLASS singlylinkedlistnode<valuetype>
852 
853 SINGLYLINKEDLISTNODE_TEMPLATE
854 inline
855 SINGLYLINKEDLISTNODE_CLASS::singlylinkedlistnode(valuetype value) {
856  this->value=value;
857  next=NULL;
858 }
859 
860 SINGLYLINKEDLISTNODE_TEMPLATE
861 inline
862 SINGLYLINKEDLISTNODE_CLASS::~singlylinkedlistnode() {
863 }
864 
865 SINGLYLINKEDLISTNODE_TEMPLATE
866 inline
867 void SINGLYLINKEDLISTNODE_CLASS::setValue(valuetype value) {
868  this->value=value;
869 }
870 
871 SINGLYLINKEDLISTNODE_TEMPLATE
872 inline
873 valuetype SINGLYLINKEDLISTNODE_CLASS::getValue() const {
874  return value;
875 }
876 
877 SINGLYLINKEDLISTNODE_TEMPLATE
878 inline
879 SINGLYLINKEDLISTNODE_CLASS *SINGLYLINKEDLISTNODE_CLASS::getNext() {
880  return next;
881 }
882 
883 SINGLYLINKEDLISTNODE_TEMPLATE
884 inline
885 int32_t SINGLYLINKEDLISTNODE_CLASS::compare(valuetype value) const {
886  return node_compare(this->value,value);
887 }
888 
889 SINGLYLINKEDLISTNODE_TEMPLATE
890 inline
891 int32_t SINGLYLINKEDLISTNODE_CLASS::compare(
892  singlylinkedlistnode<valuetype> *peer) const {
893  return node_compare(this->value,peer->value);
894 }
895 
896 SINGLYLINKEDLISTNODE_TEMPLATE
897 inline
898 void SINGLYLINKEDLISTNODE_CLASS::print() const {
899  node_print(value);
900 }
901 
902 SINGLYLINKEDLISTNODE_TEMPLATE
903 inline
904 void SINGLYLINKEDLISTNODE_CLASS::setNext(SINGLYLINKEDLISTNODE_CLASS *next) {
905  this->next=next;
906 }
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