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