4 #include <rudiments/stdio.h> 5 #include <rudiments/private/rudimentsinlines.h> 6 #include <rudiments/private/nodeinlines.h> 8 #define LINKEDLIST_TEMPLATE template <class valuetype> 10 #define LINKEDLIST_CLASS linkedlist<valuetype> 13 RUDIMENTS_TEMPLATE_INLINE
14 LINKEDLIST_CLASS::linkedlist() {
21 RUDIMENTS_TEMPLATE_INLINE
22 LINKEDLIST_CLASS::~linkedlist() {
27 RUDIMENTS_TEMPLATE_INLINE
28 void LINKEDLIST_CLASS::prepend(valuetype value) {
33 RUDIMENTS_TEMPLATE_INLINE
38 first->setPrevious(node);
49 RUDIMENTS_TEMPLATE_INLINE
50 void LINKEDLIST_CLASS::append(valuetype value) {
55 RUDIMENTS_TEMPLATE_INLINE
61 node->setPrevious(last);
71 RUDIMENTS_TEMPLATE_INLINE
78 RUDIMENTS_TEMPLATE_INLINE
83 }
else if (node==first) {
86 newnode->setNext(node);
89 node->setPrevious(newnode);
95 RUDIMENTS_TEMPLATE_INLINE
102 RUDIMENTS_TEMPLATE_INLINE
107 }
else if (node==last) {
110 newnode->setNext(node->
getNext());
111 newnode->setPrevious(node);
112 node->
getNext()->setPrevious(newnode);
113 node->setNext(newnode);
119 RUDIMENTS_TEMPLATE_INLINE
122 move(node,nodetomove,
true);
126 RUDIMENTS_TEMPLATE_INLINE
129 move(node,nodetomove,
false);
133 RUDIMENTS_TEMPLATE_INLINE
138 if (!node || !nodetomove || node==nodetomove) {
144 insertBefore(node,nodetomove);
146 insertAfter(node,nodetomove);
151 RUDIMENTS_TEMPLATE_INLINE
167 node->setPrevious(NULL);
172 RUDIMENTS_TEMPLATE_INLINE
173 bool LINKEDLIST_CLASS::remove(valuetype value) {
175 return (current)?
remove(current):
false;
179 RUDIMENTS_TEMPLATE_INLINE
180 bool LINKEDLIST_CLASS::removeAll(valuetype value) {
186 if (!current->
compare(value) && !
remove(current)) {
195 RUDIMENTS_TEMPLATE_INLINE
218 RUDIMENTS_TEMPLATE_INLINE
219 uint64_t LINKEDLIST_CLASS::getLength()
const {
224 RUDIMENTS_TEMPLATE_INLINE
230 RUDIMENTS_TEMPLATE_INLINE
236 RUDIMENTS_TEMPLATE_INLINE
243 RUDIMENTS_TEMPLATE_INLINE
246 return (node)?node->
getNext():NULL;
250 RUDIMENTS_TEMPLATE_INLINE
256 RUDIMENTS_TEMPLATE_INLINE
261 current; current=current->
getNext()) {
262 if (!current->
compare(value)) {
270 RUDIMENTS_TEMPLATE_INLINE
271 void LINKEDLIST_CLASS::insertionSort() {
298 node->setPrevious(NULL);
306 if (newfirst->
compare(node)>0) {
307 node->setNext(newfirst);
308 node->setPrevious(NULL);
309 newfirst->setPrevious(node);
315 if (newlast->
compare(node)<=0) {
316 node->setPrevious(newlast);
318 newlast->setNext(node);
327 currentfromfirst=newfirst->
getNext();
329 while (currentfromfirst) {
333 if (currentfromfirst->
compare(node)>0) {
336 node->setNext(currentfromfirst);
337 node->setPrevious(currentfromfirst->
340 getPrevious()->setNext(node);
349 if (currentfromlast->
compare(node)<=0) {
352 node->setPrevious(currentfromlast);
353 node->setNext(currentfromlast->
356 getNext()->setPrevious(node);
363 currentfromfirst=currentfromfirst->
getNext();
378 RUDIMENTS_TEMPLATE_INLINE
379 void LINKEDLIST_CLASS::heapSort() {
402 uint64_t child=heapend;
406 uint64_t parent=(child-1)/2;
409 if (heap[parent]->compare(heap[child])<0) {
411 heap[parent]=heap[child];
445 node->setPrevious(NULL);
450 node->setPrevious(NULL);
451 node->setNext(newfirst);
452 newfirst->setPrevious(node);
470 heap[0]=heap[heapend];
479 uint64_t leftchild=parent*2+1;
480 if (leftchild>heapend) {
485 uint64_t greater=parent;
486 if (heap[parent]->compare(heap[leftchild])<0) {
491 uint64_t rightchild=leftchild+1;
492 if (rightchild<=heapend &&
493 heap[rightchild]->compare(heap[greater])>0) {
499 if (greater==parent) {
507 heap[parent]=heap[greater];
515 RUDIMENTS_TEMPLATE_INLINE
516 void LINKEDLIST_CLASS::clear() {
530 RUDIMENTS_TEMPLATE_INLINE
531 void LINKEDLIST_CLASS::print()
const {
536 RUDIMENTS_TEMPLATE_INLINE
537 void LINKEDLIST_CLASS::print(uint64_t count)
const {
540 current && i<count; current=current->
getNext()) {
541 #ifdef RUDIMENTS_HAVE_LONG_LONG 542 stdoutput.
printf(
"index %lld: ",(
long long)i);
544 stdoutput.
printf(
"index %ld: ",(
long)i);
552 #define LINKEDLISTNODE_TEMPLATE template <class valuetype> 554 #define LINKEDLISTNODE_CLASS linkedlistnode<valuetype> 556 LINKEDLISTNODE_TEMPLATE
557 RUDIMENTS_TEMPLATE_INLINE
558 LINKEDLISTNODE_CLASS::linkedlistnode(valuetype value) {
564 LINKEDLISTNODE_TEMPLATE
565 RUDIMENTS_TEMPLATE_INLINE
566 LINKEDLISTNODE_CLASS::~linkedlistnode() {
569 LINKEDLISTNODE_TEMPLATE
570 RUDIMENTS_TEMPLATE_INLINE
571 void LINKEDLISTNODE_CLASS::setValue(valuetype value) {
575 LINKEDLISTNODE_TEMPLATE
576 RUDIMENTS_TEMPLATE_INLINE
577 valuetype LINKEDLISTNODE_CLASS::getValue()
const {
581 LINKEDLISTNODE_TEMPLATE
582 RUDIMENTS_TEMPLATE_INLINE
583 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getPrevious() {
587 LINKEDLISTNODE_TEMPLATE
588 RUDIMENTS_TEMPLATE_INLINE
589 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getNext() {
593 LINKEDLISTNODE_TEMPLATE
594 RUDIMENTS_TEMPLATE_INLINE
595 int32_t LINKEDLISTNODE_CLASS::compare(valuetype value)
const {
596 return node_compare(this->value,value);
599 LINKEDLISTNODE_TEMPLATE
600 RUDIMENTS_TEMPLATE_INLINE
602 return node_compare(this->value,peer->value);
605 LINKEDLISTNODE_TEMPLATE
606 RUDIMENTS_TEMPLATE_INLINE
607 void LINKEDLISTNODE_CLASS::print()
const {
611 LINKEDLISTNODE_TEMPLATE
612 RUDIMENTS_TEMPLATE_INLINE
613 void LINKEDLISTNODE_CLASS::setPrevious(LINKEDLISTNODE_CLASS *previous) {
614 this->previous=previous;
617 LINKEDLISTNODE_TEMPLATE
618 RUDIMENTS_TEMPLATE_INLINE
619 void LINKEDLISTNODE_CLASS::setNext(LINKEDLISTNODE_CLASS *next) {
size_t printf(const char *format,...)
linkedlistnode< valuetype > * getPrevious()
Definition: linkedlist.h:11
int32_t compare(valuetype value) const
linkedlistnode< valuetype > * getNext()