4 #include <rudiments/stdio.h> 5 #include <rudiments/private/nodeinlines.h> 7 #define SINGLYLINKEDLIST_TEMPLATE template <class valuetype> 9 #define SINGLYLINKEDLIST_CLASS singlylinkedlist<valuetype> 11 SINGLYLINKEDLIST_TEMPLATE
13 SINGLYLINKEDLIST_CLASS::singlylinkedlist() {
19 SINGLYLINKEDLIST_TEMPLATE
21 SINGLYLINKEDLIST_CLASS::~singlylinkedlist() {
25 SINGLYLINKEDLIST_TEMPLATE
27 void SINGLYLINKEDLIST_CLASS::prepend(valuetype value) {
31 SINGLYLINKEDLIST_TEMPLATE
46 SINGLYLINKEDLIST_TEMPLATE
48 void SINGLYLINKEDLIST_CLASS::append(valuetype value) {
52 SINGLYLINKEDLIST_TEMPLATE
67 SINGLYLINKEDLIST_TEMPLATE
69 void SINGLYLINKEDLIST_CLASS::insertAfter(
75 SINGLYLINKEDLIST_TEMPLATE
77 void SINGLYLINKEDLIST_CLASS::insertAfter(
82 }
else if (node==last) {
85 newnode->setNext(node->
getNext());
86 node->setNext(newnode);
91 SINGLYLINKEDLIST_TEMPLATE
93 void SINGLYLINKEDLIST_CLASS::moveAfter(
97 if (!node || !nodetomove || node==nodetomove) {
101 if (nodetomove==first) {
103 }
else if (nodetomove==last) {
105 while (secondtolast->
getNext()!=last) {
106 secondtolast=secondtolast->
getNext();
109 secondtolast->setNext(NULL);
112 while (previous->
getNext()!=nodetomove) {
115 previous->setNext(nodetomove->
getNext());
118 nodetomove->setNext(node->
getNext());
119 node->setNext(nodetomove);
125 SINGLYLINKEDLIST_TEMPLATE
129 if (node==first && node==last) {
132 }
else if (node==first) {
134 }
else if (node==last) {
136 while (secondtolast->
getNext()!=last) {
137 secondtolast=secondtolast->
getNext();
140 secondtolast->setNext(NULL);
143 while (previous->
getNext()!=node) {
146 previous->setNext(node->
getNext());
152 SINGLYLINKEDLIST_TEMPLATE
154 bool SINGLYLINKEDLIST_CLASS::remove(valuetype value) {
156 if (!current->
compare(value)) {
161 first=first->getNext();
167 if (!current->
compare(value)) {
168 prev->setNext(current->
getNext());
186 SINGLYLINKEDLIST_TEMPLATE
188 bool SINGLYLINKEDLIST_CLASS::removeAll(valuetype value) {
194 while (!current->
compare(value)) {
203 first=first->getNext();
212 if (!current->
compare(value)) {
231 SINGLYLINKEDLIST_TEMPLATE
243 first=first->getNext();
250 prev->setNext(current->
getNext());
268 SINGLYLINKEDLIST_TEMPLATE
270 uint64_t SINGLYLINKEDLIST_CLASS::getLength()
const {
274 SINGLYLINKEDLIST_TEMPLATE
280 SINGLYLINKEDLIST_TEMPLATE
286 SINGLYLINKEDLIST_TEMPLATE
290 return (node)?node->
getNext():NULL;
293 SINGLYLINKEDLIST_TEMPLATE
299 SINGLYLINKEDLIST_TEMPLATE
305 current; current=current->
getNext()) {
306 if (!current->
compare(value)) {
313 SINGLYLINKEDLIST_TEMPLATE
315 void SINGLYLINKEDLIST_CLASS::insertionSort() {
349 if (newfirst->
compare(node)>0) {
350 node->setNext(newfirst);
356 if (newlast->
compare(node)<=0) {
358 newlast->setNext(node);
370 if (current->
compare(node)>0) {
373 node->setNext(current);
374 previous->setNext(node);
393 SINGLYLINKEDLIST_TEMPLATE
395 void SINGLYLINKEDLIST_CLASS::heapSort() {
418 uint64_t child=heapend;
422 uint64_t parent=(child-1)/2;
425 if (heap[parent]->compare(heap[child])<0) {
427 heap[parent]=heap[child];
465 node->setNext(newfirst);
483 heap[0]=heap[heapend];
492 uint64_t leftchild=parent*2+1;
493 if (leftchild>heapend) {
498 uint64_t greater=parent;
499 if (heap[parent]->compare(heap[leftchild])<0) {
504 uint64_t rightchild=leftchild+1;
505 if (rightchild<=heapend &&
506 heap[rightchild]->compare(heap[greater])>0) {
512 if (greater==parent) {
520 heap[parent]=heap[greater];
535 SINGLYLINKEDLIST_TEMPLATE
537 void SINGLYLINKEDLIST_CLASS::clear() {
550 SINGLYLINKEDLIST_TEMPLATE
552 void SINGLYLINKEDLIST_CLASS::clearAndDelete() {
566 SINGLYLINKEDLIST_TEMPLATE
568 void SINGLYLINKEDLIST_CLASS::clearAndArrayDelete() {
582 SINGLYLINKEDLIST_TEMPLATE
584 void SINGLYLINKEDLIST_CLASS::print()
const {
588 SINGLYLINKEDLIST_TEMPLATE
590 void SINGLYLINKEDLIST_CLASS::print(uint64_t count)
const {
593 current && i<count; current=current->
getNext()) {
594 #ifdef RUDIMENTS_HAVE_LONG_LONG 595 stdoutput.
printf(
"index %lld: ",(
long long)i);
597 stdoutput.
printf(
"index %ld: ",(
long)i);
605 #define SINGLYLINKEDLISTNODE_TEMPLATE template <class valuetype> 607 #define SINGLYLINKEDLISTNODE_CLASS singlylinkedlistnode<valuetype> 609 SINGLYLINKEDLISTNODE_TEMPLATE
611 SINGLYLINKEDLISTNODE_CLASS::singlylinkedlistnode(valuetype value) {
616 SINGLYLINKEDLISTNODE_TEMPLATE
618 SINGLYLINKEDLISTNODE_CLASS::~singlylinkedlistnode() {
621 SINGLYLINKEDLISTNODE_TEMPLATE
623 void SINGLYLINKEDLISTNODE_CLASS::setValue(valuetype value) {
627 SINGLYLINKEDLISTNODE_TEMPLATE
629 valuetype SINGLYLINKEDLISTNODE_CLASS::getValue()
const {
633 SINGLYLINKEDLISTNODE_TEMPLATE
635 SINGLYLINKEDLISTNODE_CLASS *SINGLYLINKEDLISTNODE_CLASS::getNext() {
639 SINGLYLINKEDLISTNODE_TEMPLATE
641 int32_t SINGLYLINKEDLISTNODE_CLASS::compare(valuetype value)
const {
642 return node_compare(this->value,value);
645 SINGLYLINKEDLISTNODE_TEMPLATE
647 int32_t SINGLYLINKEDLISTNODE_CLASS::compare(
649 return node_compare(this->value,peer->value);
652 SINGLYLINKEDLISTNODE_TEMPLATE
654 void SINGLYLINKEDLISTNODE_CLASS::print()
const {
658 SINGLYLINKEDLISTNODE_TEMPLATE
660 void SINGLYLINKEDLISTNODE_CLASS::setNext(SINGLYLINKEDLISTNODE_CLASS *next) {
singlylinkedlistnode< valuetype > * getNext()
size_t printf(const char *format,...)
int32_t compare(valuetype value) const
valuetype getValue() const
Definition: singlylinkedlist.h:12