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/rudimentsinlines.h>
6 #include <rudiments/private/nodeinlines.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(
72  valuetype value) {
73  insertAfter(node,new singlylinkedlistnode<valuetype>(value));
74 }
75 
76 SINGLYLINKEDLIST_TEMPLATE
77 RUDIMENTS_TEMPLATE_INLINE
78 void SINGLYLINKEDLIST_CLASS::insertAfter(
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(
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 {
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  }
211  current=current->getNext();
212  while (current) {
213  if (!current->compare(value)) {
214  retval=true;
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 {
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(
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(
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
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
408  new singlylinkedlistnode<valuetype> *[length];
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() {
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 node_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 node_compare(this->value,peer->value);
611 }
612 
613 SINGLYLINKEDLISTNODE_TEMPLATE
614 RUDIMENTS_TEMPLATE_INLINE
615 void SINGLYLINKEDLISTNODE_CLASS::print() const {
616  node_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< valuetype > * getNext()
void print() const
size_t printf(const char *format,...)
Definition: singlylinkedlist.h:12
int32_t compare(valuetype value) const