4 #include <rudiments/stdio.h>
5 #include <rudiments/private/rudimentsinlines.h>
6 #include <rudiments/private/linkedlistutilinlines.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) {
142 if (nodetomove==first) {
144 }
else if (nodetomove==last) {
155 nodetomove->setNext(node);
157 node->setPrevious(nodetomove);
162 nodetomove->setNext(node->
getNext());
163 nodetomove->setPrevious(node);
164 node->setNext(nodetomove);
172 RUDIMENTS_TEMPLATE_INLINE
188 node->setPrevious(NULL);
193 RUDIMENTS_TEMPLATE_INLINE
194 bool LINKEDLIST_CLASS::remove(valuetype value) {
196 return (current)?
remove(current):
false;
200 RUDIMENTS_TEMPLATE_INLINE
201 bool LINKEDLIST_CLASS::removeAll(valuetype value) {
207 if (!current->
compare(value) && !
remove(current)) {
216 RUDIMENTS_TEMPLATE_INLINE
239 RUDIMENTS_TEMPLATE_INLINE
240 uint64_t LINKEDLIST_CLASS::getLength()
const {
245 RUDIMENTS_TEMPLATE_INLINE
251 RUDIMENTS_TEMPLATE_INLINE
257 RUDIMENTS_TEMPLATE_INLINE
264 RUDIMENTS_TEMPLATE_INLINE
267 return (node)?node->
getNext():NULL;
271 RUDIMENTS_TEMPLATE_INLINE
277 RUDIMENTS_TEMPLATE_INLINE
282 current; current=current->
getNext()) {
283 if (!current->
compare(value)) {
291 RUDIMENTS_TEMPLATE_INLINE
292 void LINKEDLIST_CLASS::insertionSort() {
319 node->setPrevious(NULL);
327 if (newfirst->
compare(node)>0) {
328 node->setNext(newfirst);
329 node->setPrevious(NULL);
330 newfirst->setPrevious(node);
336 if (newlast->
compare(node)<=0) {
337 node->setPrevious(newlast);
339 newlast->setNext(node);
348 currentfromfirst=newfirst->
getNext();
350 while (currentfromfirst) {
354 if (currentfromfirst->
compare(node)>0) {
357 node->setNext(currentfromfirst);
358 node->setPrevious(currentfromfirst->
361 getPrevious()->setNext(node);
370 if (currentfromlast->
compare(node)<=0) {
373 node->setPrevious(currentfromlast);
374 node->setNext(currentfromlast->
377 getNext()->setPrevious(node);
384 currentfromfirst=currentfromfirst->
getNext();
399 RUDIMENTS_TEMPLATE_INLINE
400 void LINKEDLIST_CLASS::heapSort() {
423 uint64_t child=heapend;
427 uint64_t parent=(child-1)/2;
430 if (heap[parent]->compare(heap[child])<0) {
432 heap[parent]=heap[child];
466 node->setPrevious(NULL);
471 node->setPrevious(NULL);
472 node->setNext(newfirst);
473 newfirst->setPrevious(node);
491 heap[0]=heap[heapend];
500 uint64_t leftchild=parent*2+1;
501 if (leftchild>heapend) {
506 uint64_t greater=parent;
507 if (heap[parent]->compare(heap[leftchild])<0) {
512 uint64_t rightchild=leftchild+1;
513 if (rightchild<=heapend &&
514 heap[rightchild]->compare(heap[greater])>0) {
520 if (greater==parent) {
528 heap[parent]=heap[greater];
536 RUDIMENTS_TEMPLATE_INLINE
537 void LINKEDLIST_CLASS::clear() {
551 RUDIMENTS_TEMPLATE_INLINE
552 void LINKEDLIST_CLASS::print()
const {
557 RUDIMENTS_TEMPLATE_INLINE
558 void LINKEDLIST_CLASS::print(uint64_t count)
const {
561 current && i<count; current=current->
getNext()) {
562 stdoutput.
printf(
"index %lld: ",(
long long)i);
569 #define LINKEDLISTNODE_TEMPLATE template <class valuetype>
571 #define LINKEDLISTNODE_CLASS linkedlistnode<valuetype>
573 LINKEDLISTNODE_TEMPLATE
574 RUDIMENTS_TEMPLATE_INLINE
575 LINKEDLISTNODE_CLASS::linkedlistnode(valuetype value) {
581 LINKEDLISTNODE_TEMPLATE
582 RUDIMENTS_TEMPLATE_INLINE
583 LINKEDLISTNODE_CLASS::~linkedlistnode() {
586 LINKEDLISTNODE_TEMPLATE
587 RUDIMENTS_TEMPLATE_INLINE
588 void LINKEDLISTNODE_CLASS::setValue(valuetype value) {
592 LINKEDLISTNODE_TEMPLATE
593 RUDIMENTS_TEMPLATE_INLINE
594 valuetype LINKEDLISTNODE_CLASS::getValue()
const {
598 LINKEDLISTNODE_TEMPLATE
599 RUDIMENTS_TEMPLATE_INLINE
600 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getPrevious() {
604 LINKEDLISTNODE_TEMPLATE
605 RUDIMENTS_TEMPLATE_INLINE
606 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getNext() {
610 LINKEDLISTNODE_TEMPLATE
611 RUDIMENTS_TEMPLATE_INLINE
612 int32_t LINKEDLISTNODE_CLASS::compare(valuetype value)
const {
613 return _linkedlistutil_compare(this->value,value);
616 LINKEDLISTNODE_TEMPLATE
617 RUDIMENTS_TEMPLATE_INLINE
619 return _linkedlistutil_compare(this->value,peer->value);
622 LINKEDLISTNODE_TEMPLATE
623 RUDIMENTS_TEMPLATE_INLINE
624 void LINKEDLISTNODE_CLASS::print()
const {
625 _linkedlistutil_print(value);
628 LINKEDLISTNODE_TEMPLATE
629 RUDIMENTS_TEMPLATE_INLINE
630 void LINKEDLISTNODE_CLASS::setPrevious(LINKEDLISTNODE_CLASS *previous) {
631 this->previous=previous;
634 LINKEDLISTNODE_TEMPLATE
635 RUDIMENTS_TEMPLATE_INLINE
636 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()