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/linkedlistutilinlines.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  if (nodetomove==first) {
143  first=nodetomove->getNext();
144  } else if (nodetomove==last) {
145  last=nodetomove->getPrevious();
146  }
147  if (nodetomove->getPrevious()) {
148  nodetomove->getPrevious()->setNext(nodetomove->getNext());
149  }
150  if (nodetomove->getNext()) {
151  nodetomove->getNext()->setPrevious(nodetomove->getPrevious());
152  }
153 
154  if (before) {
155  nodetomove->setNext(node);
156  nodetomove->setPrevious(node->getPrevious());
157  node->setPrevious(nodetomove);
158  if (node==first) {
159  first=nodetomove;
160  }
161  } else {
162  nodetomove->setNext(node->getNext());
163  nodetomove->setPrevious(node);
164  node->setNext(nodetomove);
165  if (node==last) {
166  last=nodetomove;
167  }
168  }
169 }
170 
171 LINKEDLIST_TEMPLATE
172 RUDIMENTS_TEMPLATE_INLINE
173 void LINKEDLIST_CLASS::detach(linkedlistnode<valuetype> *node) {
174 
175  if (node==first) {
176  first=node->getNext();
177  }
178  if (node==last) {
179  last=node->getPrevious();
180  }
181  if (node->getPrevious()) {
182  node->getPrevious()->setNext(node->getNext());
183  }
184  if (node->getNext()) {
185  node->getNext()->setPrevious(node->getPrevious());
186  }
187  node->setNext(NULL);
188  node->setPrevious(NULL);
189  length--;
190 }
191 
192 LINKEDLIST_TEMPLATE
193 RUDIMENTS_TEMPLATE_INLINE
194 bool LINKEDLIST_CLASS::remove(valuetype value) {
195  linkedlistnode<valuetype> *current=find(value);
196  return (current)?remove(current):false;
197 }
198 
199 LINKEDLIST_TEMPLATE
200 RUDIMENTS_TEMPLATE_INLINE
201 bool LINKEDLIST_CLASS::removeAll(valuetype value) {
202 
203  linkedlistnode<valuetype> *current=first;
205  while (current) {
206  next=current->getNext();
207  if (!current->compare(value) && !remove(current)) {
208  return false;
209  }
210  current=next;
211  }
212  return true;
213 }
214 
215 LINKEDLIST_TEMPLATE
216 RUDIMENTS_TEMPLATE_INLINE
217 bool LINKEDLIST_CLASS::remove(linkedlistnode<valuetype> *node) {
218  if (!node) {
219  return false;
220  }
221  if (node->getNext()) {
222  node->getNext()->setPrevious(node->getPrevious());
223  }
224  if (node->getPrevious()) {
225  node->getPrevious()->setNext(node->getNext());
226  }
227  if (node==first) {
228  first=node->getNext();
229  }
230  if (node==last) {
231  last=node->getPrevious();
232  }
233  delete node;
234  length--;
235  return true;
236 }
237 
238 LINKEDLIST_TEMPLATE
239 RUDIMENTS_TEMPLATE_INLINE
240 uint64_t LINKEDLIST_CLASS::getLength() const {
241  return length;
242 }
243 
244 LINKEDLIST_TEMPLATE
245 RUDIMENTS_TEMPLATE_INLINE
246 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getFirst() {
247  return first;
248 }
249 
250 LINKEDLIST_TEMPLATE
251 RUDIMENTS_TEMPLATE_INLINE
252 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getLast() {
253  return last;
254 }
255 
256 LINKEDLIST_TEMPLATE
257 RUDIMENTS_TEMPLATE_INLINE
258 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getPrevious(
260  return (node)?node->getPrevious():NULL;
261 }
262 
263 LINKEDLIST_TEMPLATE
264 RUDIMENTS_TEMPLATE_INLINE
265 linkedlistnode<valuetype> *LINKEDLIST_CLASS::getNext(
267  return (node)?node->getNext():NULL;
268 }
269 
270 LINKEDLIST_TEMPLATE
271 RUDIMENTS_TEMPLATE_INLINE
272 linkedlistnode<valuetype> *LINKEDLIST_CLASS::find(valuetype value) {
273  return find((linkedlistnode<valuetype> *)first,value);
274 }
275 
276 LINKEDLIST_TEMPLATE
277 RUDIMENTS_TEMPLATE_INLINE
278 linkedlistnode<valuetype> *LINKEDLIST_CLASS::find(
279  linkedlistnode<valuetype> *startnode,
280  valuetype value) {
281  for (linkedlistnode<valuetype> *current=startnode;
282  current; current=current->getNext()) {
283  if (!current->compare(value)) {
284  return current;
285  }
286  }
287  return NULL;
288 }
289 
290 LINKEDLIST_TEMPLATE
291 RUDIMENTS_TEMPLATE_INLINE
292 void LINKEDLIST_CLASS::insertionSort() {
293 
294  // insertion sort with a few optimizations...
295 
296  // if there are 0 or 1 items in the list then it's already sorted
297  if (length<2) {
298  return;
299  }
300 
301  // first and last pointers for the new list
302  linkedlistnode<valuetype> *newfirst=NULL;
303  linkedlistnode<valuetype> *newlast=NULL;
304 
305  // pointer for iterating through the new list
306  linkedlistnode<valuetype> *currentfromfirst=NULL;
307  linkedlistnode<valuetype> *currentfromlast=NULL;
308 
309  // iterate through the current list, building a new one as we go
310  linkedlistnode<valuetype> *node=first;
311  linkedlistnode<valuetype> *next=NULL;
312  while (node) {
313 
314  // get the next node so we can move on later
315  next=node->getNext();
316 
317  // if the new list is empty...
318  if (!newfirst) {
319  node->setPrevious(NULL);
320  node->setNext(NULL);
321  newfirst=node;
322  newlast=node;
323  } else
324 
325  // if the node belongs at the beginning of the new list
326  // (optimization for lists that are already largely forwards)
327  if (newfirst->compare(node)>0) {
328  node->setNext(newfirst);
329  node->setPrevious(NULL);
330  newfirst->setPrevious(node);
331  newfirst=node;
332  } else
333 
334  // if the node belongs at the end of the new list
335  // (optimization for lists that are already largely backwards)
336  if (newlast->compare(node)<=0) {
337  node->setPrevious(newlast);
338  node->setNext(NULL);
339  newlast->setNext(node);
340  newlast=node;
341  } else
342 
343  // if the node belongs somewhere in the middle of the new list
344  {
345 
346  // search from both ends toward the middle...
347  // (optimization for data that is more random)
348  currentfromfirst=newfirst->getNext();
349  currentfromlast=newlast->getPrevious();
350  while (currentfromfirst) {
351 
352  // if the current node (from the left)
353  // is greater than...
354  if (currentfromfirst->compare(node)>0) {
355 
356  // insert before
357  node->setNext(currentfromfirst);
358  node->setPrevious(currentfromfirst->
359  getPrevious());
360  currentfromfirst->
361  getPrevious()->setNext(node);
362  currentfromfirst->
363  setPrevious(node);
364  break;
365 
366  } else
367 
368  // if the current node (from the right)
369  // is less than or equal to...
370  if (currentfromlast->compare(node)<=0) {
371 
372  // insert after
373  node->setPrevious(currentfromlast);
374  node->setNext(currentfromlast->
375  getNext());
376  currentfromlast->
377  getNext()->setPrevious(node);
378  currentfromlast->
379  setNext(node);
380  break;
381  }
382 
383  // move on
384  currentfromfirst=currentfromfirst->getNext();
385  currentfromlast=currentfromlast->getPrevious();
386  }
387  }
388 
389  // move on
390  node=next;
391  }
392 
393  // make the new list the current list
394  first=newfirst;
395  last=newlast;
396 }
397 
398 LINKEDLIST_TEMPLATE
399 RUDIMENTS_TEMPLATE_INLINE
400 void LINKEDLIST_CLASS::heapSort() {
401 
402  // if there are 0 or 1 items in the list then it's already sorted
403  if (length<2) {
404  return;
405  }
406 
407  // build heap as a binary tree mapped to an array:
408  // parentindex = floor((childindex-1)/2)
409  // leftchildindex = parent*2+1
410  // rightchildindex = parent*2+2
412  new linkedlistnode<valuetype> *[length];
413  linkedlistnode<valuetype> *temp=NULL;
414  uint64_t heapend=0;
415  for (linkedlistnode<valuetype> *node=first;
416  node; node=node->getNext()) {
417 
418  // insert node into heap
419  heap[heapend]=node;
420 
421  // walk up the tree, maintaining the heap property
422  // (higher values higher up in the tree)
423  uint64_t child=heapend;
424  while (child) {
425 
426  // get the parent index
427  uint64_t parent=(child-1)/2;
428 
429  // swap nodes if necessary
430  if (heap[parent]->compare(heap[child])<0) {
431  temp=heap[parent];
432  heap[parent]=heap[child];
433  heap[child]=temp;
434  }
435 
436  // move up
437  child=parent;
438  }
439 
440  // move on
441  heapend++;
442  }
443 
444  // reset the heap end index
445  heapend--;
446 
447  // Build a new list from the heap by swapping the root and last leaf
448  // node (index 0 is the root and the last index is the last leaf),
449  // pulling the value off of the last leaf node, and sifting the tree to
450  // maintain the heap property (higher values higher up in the tree),
451  // over and over again. We'll shortcut the swap and pull-off part a
452  // bit...
453 
454  // first and last pointers for the new list
455  linkedlistnode<valuetype> *newfirst=NULL;
456  linkedlistnode<valuetype> *newlast=NULL;
457 
458  // extract values from the heap...
459  for (;;) {
460 
461  // pull off the highest value (which is always at the root
462  // of the tree, index 0 in the array) and prepend it to the
463  // new array
464  linkedlistnode<valuetype> *node=heap[0];
465  if (!newfirst) {
466  node->setPrevious(NULL);
467  node->setNext(NULL);
468  newfirst=node;
469  newlast=node;
470  } else {
471  node->setPrevious(NULL);
472  node->setNext(newfirst);
473  newfirst->setPrevious(node);
474  newfirst=node;
475  }
476 
477  // when the tree is empty, we're done
478  if (!heapend) {
479 
480  // make the new list the current list
481  first=newfirst;
482  last=newlast;
483 
484  // clean up
485  delete[] heap;
486  return;
487  }
488 
489  // move the value at the last leaf node (end of the array)
490  // to the root node (index 0 of the array)
491  heap[0]=heap[heapend];
492  heapend--;
493 
494  // sift the tree to maintain the heap property
495  // (higher values higher up in the tree)
496  uint64_t parent=0;
497  for (;;) {
498 
499  // make sure there's at least a left child
500  uint64_t leftchild=parent*2+1;
501  if (leftchild>heapend) {
502  break;
503  }
504 
505  // is the left child greater?
506  uint64_t greater=parent;
507  if (heap[parent]->compare(heap[leftchild])<0) {
508  greater=leftchild;
509  }
510 
511  // is the right child greater?
512  uint64_t rightchild=leftchild+1;
513  if (rightchild<=heapend &&
514  heap[rightchild]->compare(heap[greater])>0) {
515  greater=rightchild;
516  }
517 
518  // if the parent was greater than each child then
519  // we don't need to continue sifting
520  if (greater==parent) {
521  break;
522  }
523 
524  // if one of the children was greater than the parent
525  // then swap them and continue down the tree in the
526  // direction of the child that was swapped
527  temp=heap[parent];
528  heap[parent]=heap[greater];
529  heap[greater]=temp;
530  parent=greater;
531  }
532  }
533 }
534 
535 LINKEDLIST_TEMPLATE
536 RUDIMENTS_TEMPLATE_INLINE
537 void LINKEDLIST_CLASS::clear() {
539  linkedlistnode<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 LINKEDLIST_TEMPLATE
551 RUDIMENTS_TEMPLATE_INLINE
552 void LINKEDLIST_CLASS::print() const {
553  print(length);
554 }
555 
556 LINKEDLIST_TEMPLATE
557 RUDIMENTS_TEMPLATE_INLINE
558 void LINKEDLIST_CLASS::print(uint64_t count) const {
559  uint64_t i=0;
560  for (linkedlistnode<valuetype> *current=first;
561  current && i<count; current=current->getNext()) {
562  stdoutput.printf("index %lld: ",(long long)i);
563  current->print();
564  stdoutput.printf("\n");
565  i++;
566  }
567 }
568 
569 #define LINKEDLISTNODE_TEMPLATE template <class valuetype>
570 
571 #define LINKEDLISTNODE_CLASS linkedlistnode<valuetype>
572 
573 LINKEDLISTNODE_TEMPLATE
574 RUDIMENTS_TEMPLATE_INLINE
575 LINKEDLISTNODE_CLASS::linkedlistnode(valuetype value) {
576  this->value=value;
577  previous=NULL;
578  next=NULL;
579 }
580 
581 LINKEDLISTNODE_TEMPLATE
582 RUDIMENTS_TEMPLATE_INLINE
583 LINKEDLISTNODE_CLASS::~linkedlistnode() {
584 }
585 
586 LINKEDLISTNODE_TEMPLATE
587 RUDIMENTS_TEMPLATE_INLINE
588 void LINKEDLISTNODE_CLASS::setValue(valuetype value) {
589  this->value=value;
590 }
591 
592 LINKEDLISTNODE_TEMPLATE
593 RUDIMENTS_TEMPLATE_INLINE
594 valuetype LINKEDLISTNODE_CLASS::getValue() const {
595  return value;
596 }
597 
598 LINKEDLISTNODE_TEMPLATE
599 RUDIMENTS_TEMPLATE_INLINE
600 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getPrevious() {
601  return previous;
602 }
603 
604 LINKEDLISTNODE_TEMPLATE
605 RUDIMENTS_TEMPLATE_INLINE
606 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getNext() {
607  return next;
608 }
609 
610 LINKEDLISTNODE_TEMPLATE
611 RUDIMENTS_TEMPLATE_INLINE
612 int32_t LINKEDLISTNODE_CLASS::compare(valuetype value) const {
613  return _linkedlistutil_compare(this->value,value);
614 }
615 
616 LINKEDLISTNODE_TEMPLATE
617 RUDIMENTS_TEMPLATE_INLINE
618 int32_t LINKEDLISTNODE_CLASS::compare(linkedlistnode<valuetype> *peer) const {
619  return _linkedlistutil_compare(this->value,peer->value);
620 }
621 
622 LINKEDLISTNODE_TEMPLATE
623 RUDIMENTS_TEMPLATE_INLINE
624 void LINKEDLISTNODE_CLASS::print() const {
625  _linkedlistutil_print(value);
626 }
627 
628 LINKEDLISTNODE_TEMPLATE
629 RUDIMENTS_TEMPLATE_INLINE
630 void LINKEDLISTNODE_CLASS::setPrevious(LINKEDLISTNODE_CLASS *previous) {
631  this->previous=previous;
632 }
633 
634 LINKEDLISTNODE_TEMPLATE
635 RUDIMENTS_TEMPLATE_INLINE
636 void LINKEDLISTNODE_CLASS::setNext(LINKEDLISTNODE_CLASS *next) {
637  this->next=next;
638 }
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()