4 #include <rudiments/stdio.h> 5 #include <rudiments/private/nodeinlines.h> 7 #define LINKEDLIST_TEMPLATE template <class valuetype> 9 #define LINKEDLIST_CLASS linkedlist<valuetype> 13 LINKEDLIST_CLASS::linkedlist() {
21 LINKEDLIST_CLASS::~linkedlist() {
27 void LINKEDLIST_CLASS::prepend(valuetype value) {
37 first->setPrevious(node);
49 void LINKEDLIST_CLASS::append(valuetype value) {
60 node->setPrevious(last);
82 }
else if (node==first) {
85 newnode->setNext(node);
88 node->setPrevious(newnode);
106 }
else if (node==last) {
109 newnode->setNext(node->
getNext());
110 newnode->setPrevious(node);
111 node->
getNext()->setPrevious(newnode);
112 node->setNext(newnode);
121 move(node,nodetomove,
true);
128 move(node,nodetomove,
false);
137 if (!node || !nodetomove || node==nodetomove) {
143 insertBefore(node,nodetomove);
145 insertAfter(node,nodetomove);
166 node->setPrevious(NULL);
172 bool LINKEDLIST_CLASS::remove(valuetype value) {
174 return (current)?remove(current):false;
179 bool LINKEDLIST_CLASS::removeAndDelete(valuetype value) {
181 return (current)?removeAndDelete(current):false;
186 bool LINKEDLIST_CLASS::removeAndArrayDelete(valuetype value) {
188 return (current)?removeAndArrayDelete(current):false;
193 bool LINKEDLIST_CLASS::removeAll(valuetype value) {
199 if (!current->
compare(value) &&
210 bool LINKEDLIST_CLASS::removeAllAndDelete(valuetype value) {
216 if (!current->
compare(value) &&
217 !removeAndDelete(current)) {
227 bool LINKEDLIST_CLASS::removeAllAndArrayDelete(valuetype value) {
233 if (!current->
compare(value) &&
234 !removeAndArrayDelete(current)) {
315 uint64_t LINKEDLIST_CLASS::getLength()
const {
342 return (node)?node->
getNext():NULL;
357 current; current=current->
getNext()) {
358 if (!current->
compare(value)) {
367 void LINKEDLIST_CLASS::insertionSort() {
394 node->setPrevious(NULL);
402 if (newfirst->
compare(node)>0) {
403 node->setNext(newfirst);
404 node->setPrevious(NULL);
405 newfirst->setPrevious(node);
411 if (newlast->
compare(node)<=0) {
412 node->setPrevious(newlast);
414 newlast->setNext(node);
423 currentfromfirst=newfirst->
getNext();
425 while (currentfromfirst) {
429 if (currentfromfirst->
compare(node)>0) {
432 node->setNext(currentfromfirst);
433 node->setPrevious(currentfromfirst->
436 getPrevious()->setNext(node);
445 if (currentfromlast->
compare(node)<=0) {
448 node->setPrevious(currentfromlast);
449 node->setNext(currentfromlast->
452 getNext()->setPrevious(node);
459 currentfromfirst=currentfromfirst->
getNext();
475 void LINKEDLIST_CLASS::heapSort() {
498 uint64_t child=heapend;
502 uint64_t parent=(child-1)/2;
505 if (heap[parent]->compare(heap[child])<0) {
507 heap[parent]=heap[child];
541 node->setPrevious(NULL);
546 node->setPrevious(NULL);
547 node->setNext(newfirst);
548 newfirst->setPrevious(node);
566 heap[0]=heap[heapend];
575 uint64_t leftchild=parent*2+1;
576 if (leftchild>heapend) {
581 uint64_t greater=parent;
582 if (heap[parent]->compare(heap[leftchild])<0) {
587 uint64_t rightchild=leftchild+1;
588 if (rightchild<=heapend &&
589 heap[rightchild]->compare(heap[greater])>0) {
595 if (greater==parent) {
603 heap[parent]=heap[greater];
620 void LINKEDLIST_CLASS::clear() {
635 void LINKEDLIST_CLASS::clearAndDelete() {
651 void LINKEDLIST_CLASS::clearAndArrayDelete() {
667 void LINKEDLIST_CLASS::print()
const {
673 void LINKEDLIST_CLASS::print(uint64_t count)
const {
676 current && i<count; current=current->
getNext()) {
677 #ifdef RUDIMENTS_HAVE_LONG_LONG 678 stdoutput.
printf(
"index %lld: ",(
long long)i);
680 stdoutput.
printf(
"index %ld: ",(
long)i);
688 #define LINKEDLISTNODE_TEMPLATE template <class valuetype> 690 #define LINKEDLISTNODE_CLASS linkedlistnode<valuetype> 692 LINKEDLISTNODE_TEMPLATE
694 LINKEDLISTNODE_CLASS::linkedlistnode(valuetype value) {
700 LINKEDLISTNODE_TEMPLATE
702 LINKEDLISTNODE_CLASS::~linkedlistnode() {
705 LINKEDLISTNODE_TEMPLATE
707 void LINKEDLISTNODE_CLASS::setValue(valuetype value) {
711 LINKEDLISTNODE_TEMPLATE
713 valuetype LINKEDLISTNODE_CLASS::getValue()
const {
717 LINKEDLISTNODE_TEMPLATE
719 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getPrevious() {
723 LINKEDLISTNODE_TEMPLATE
725 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getNext() {
729 LINKEDLISTNODE_TEMPLATE
731 int32_t LINKEDLISTNODE_CLASS::compare(valuetype value)
const {
732 return node_compare(this->value,value);
735 LINKEDLISTNODE_TEMPLATE
738 return node_compare(this->value,peer->value);
741 LINKEDLISTNODE_TEMPLATE
743 void LINKEDLISTNODE_CLASS::print()
const {
747 LINKEDLISTNODE_TEMPLATE
749 void LINKEDLISTNODE_CLASS::setPrevious(LINKEDLISTNODE_CLASS *previous) {
750 this->previous=previous;
753 LINKEDLISTNODE_TEMPLATE
755 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
valuetype getValue() const
linkedlistnode< valuetype > * getNext()