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::removeAll(valuetype value) {
185 if (!current->
compare(value) && !
remove(current)) {
218 uint64_t LINKEDLIST_CLASS::getLength()
const {
245 return (node)?node->
getNext():NULL;
260 current; current=current->
getNext()) {
261 if (!current->
compare(value)) {
270 void LINKEDLIST_CLASS::insertionSort() {
297 node->setPrevious(NULL);
305 if (newfirst->
compare(node)>0) {
306 node->setNext(newfirst);
307 node->setPrevious(NULL);
308 newfirst->setPrevious(node);
314 if (newlast->
compare(node)<=0) {
315 node->setPrevious(newlast);
317 newlast->setNext(node);
326 currentfromfirst=newfirst->
getNext();
328 while (currentfromfirst) {
332 if (currentfromfirst->
compare(node)>0) {
335 node->setNext(currentfromfirst);
336 node->setPrevious(currentfromfirst->
339 getPrevious()->setNext(node);
348 if (currentfromlast->
compare(node)<=0) {
351 node->setPrevious(currentfromlast);
352 node->setNext(currentfromlast->
355 getNext()->setPrevious(node);
362 currentfromfirst=currentfromfirst->
getNext();
378 void LINKEDLIST_CLASS::heapSort() {
401 uint64_t child=heapend;
405 uint64_t parent=(child-1)/2;
408 if (heap[parent]->compare(heap[child])<0) {
410 heap[parent]=heap[child];
444 node->setPrevious(NULL);
449 node->setPrevious(NULL);
450 node->setNext(newfirst);
451 newfirst->setPrevious(node);
469 heap[0]=heap[heapend];
478 uint64_t leftchild=parent*2+1;
479 if (leftchild>heapend) {
484 uint64_t greater=parent;
485 if (heap[parent]->compare(heap[leftchild])<0) {
490 uint64_t rightchild=leftchild+1;
491 if (rightchild<=heapend &&
492 heap[rightchild]->compare(heap[greater])>0) {
498 if (greater==parent) {
506 heap[parent]=heap[greater];
523 void LINKEDLIST_CLASS::clear() {
538 void LINKEDLIST_CLASS::clearAndDelete() {
554 void LINKEDLIST_CLASS::clearAndArrayDelete() {
570 void LINKEDLIST_CLASS::print()
const {
576 void LINKEDLIST_CLASS::print(uint64_t count)
const {
579 current && i<count; current=current->
getNext()) {
580 #ifdef RUDIMENTS_HAVE_LONG_LONG 581 stdoutput.
printf(
"index %lld: ",(
long long)i);
583 stdoutput.
printf(
"index %ld: ",(
long)i);
591 #define LINKEDLISTNODE_TEMPLATE template <class valuetype> 593 #define LINKEDLISTNODE_CLASS linkedlistnode<valuetype> 595 LINKEDLISTNODE_TEMPLATE
597 LINKEDLISTNODE_CLASS::linkedlistnode(valuetype value) {
603 LINKEDLISTNODE_TEMPLATE
605 LINKEDLISTNODE_CLASS::~linkedlistnode() {
608 LINKEDLISTNODE_TEMPLATE
610 void LINKEDLISTNODE_CLASS::setValue(valuetype value) {
614 LINKEDLISTNODE_TEMPLATE
616 valuetype LINKEDLISTNODE_CLASS::getValue()
const {
620 LINKEDLISTNODE_TEMPLATE
622 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getPrevious() {
626 LINKEDLISTNODE_TEMPLATE
628 LINKEDLISTNODE_CLASS *LINKEDLISTNODE_CLASS::getNext() {
632 LINKEDLISTNODE_TEMPLATE
634 int32_t LINKEDLISTNODE_CLASS::compare(valuetype value)
const {
635 return node_compare(this->value,value);
638 LINKEDLISTNODE_TEMPLATE
641 return node_compare(this->value,peer->value);
644 LINKEDLISTNODE_TEMPLATE
646 void LINKEDLISTNODE_CLASS::print()
const {
650 LINKEDLISTNODE_TEMPLATE
652 void LINKEDLISTNODE_CLASS::setPrevious(LINKEDLISTNODE_CLASS *previous) {
653 this->previous=previous;
656 LINKEDLISTNODE_TEMPLATE
658 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()