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/rudimentsinlines.h>
6 #include <rudiments/private/nodeinlines.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;
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(
239  return (node)?node->getPrevious():NULL;
240 }
241 
242 LINKEDLIST_TEMPLATE
243 RUDIMENTS_TEMPLATE_INLINE
244 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getNext(
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
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() {
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 node_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 node_compare(this->value,peer->value);
603 }
604 
605 LINKEDLISTNODE_TEMPLATE
606 RUDIMENTS_TEMPLATE_INLINE
607 void LINKEDLISTNODE_CLASS::print() const {
608  node_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 }
size_t printf(const char *format,...)
linkedlistnode< valuetype > * getPrevious()
Definition: linkedlist.h:11
int32_t compare(valuetype value) const
void print() const
linkedlistnode< valuetype > * getNext()