4 #include <rudiments/stdio.h>
5 #include <rudiments/private/rudimentsinlines.h>
6 #include <rudiments/private/linkedlistutilinlines.h>
8 #define SINGLYLINKEDLIST_TEMPLATE template <class valuetype>
10 #define SINGLYLINKEDLIST_CLASS singlylinkedlist<valuetype>
12 SINGLYLINKEDLIST_TEMPLATE
13 RUDIMENTS_TEMPLATE_INLINE
14 SINGLYLINKEDLIST_CLASS::singlylinkedlist() {
20 SINGLYLINKEDLIST_TEMPLATE
21 RUDIMENTS_TEMPLATE_INLINE
22 SINGLYLINKEDLIST_CLASS::~singlylinkedlist() {
26 SINGLYLINKEDLIST_TEMPLATE
27 RUDIMENTS_TEMPLATE_INLINE
28 void SINGLYLINKEDLIST_CLASS::prepend(valuetype value) {
32 SINGLYLINKEDLIST_TEMPLATE
33 RUDIMENTS_TEMPLATE_INLINE
47 SINGLYLINKEDLIST_TEMPLATE
48 RUDIMENTS_TEMPLATE_INLINE
49 void SINGLYLINKEDLIST_CLASS::append(valuetype value) {
53 SINGLYLINKEDLIST_TEMPLATE
54 RUDIMENTS_TEMPLATE_INLINE
68 SINGLYLINKEDLIST_TEMPLATE
69 RUDIMENTS_TEMPLATE_INLINE
70 void SINGLYLINKEDLIST_CLASS::insertAfter(
76 SINGLYLINKEDLIST_TEMPLATE
77 RUDIMENTS_TEMPLATE_INLINE
78 void SINGLYLINKEDLIST_CLASS::insertAfter(
83 }
else if (node==last) {
86 newnode->setNext(node->
getNext());
87 node->setNext(newnode);
92 SINGLYLINKEDLIST_TEMPLATE
93 RUDIMENTS_TEMPLATE_INLINE
94 void SINGLYLINKEDLIST_CLASS::moveAfter(
98 if (!node || !nodetomove || node==nodetomove) {
102 if (nodetomove==first) {
104 }
else if (nodetomove==last) {
106 while (secondtolast->
getNext()!=last) {
107 secondtolast=secondtolast->
getNext();
110 secondtolast->setNext(NULL);
113 while (previous->
getNext()!=nodetomove) {
116 previous->setNext(nodetomove->
getNext());
119 nodetomove->setNext(node->
getNext());
120 node->setNext(nodetomove);
126 SINGLYLINKEDLIST_TEMPLATE
127 RUDIMENTS_TEMPLATE_INLINE
130 if (node==first && node==last) {
133 }
else if (node==first) {
135 }
else if (node==last) {
137 while (secondtolast->
getNext()!=last) {
138 secondtolast=secondtolast->
getNext();
141 secondtolast->setNext(NULL);
144 while (previous->
getNext()!=node) {
147 previous->setNext(node->
getNext());
153 SINGLYLINKEDLIST_TEMPLATE
154 RUDIMENTS_TEMPLATE_INLINE
155 bool SINGLYLINKEDLIST_CLASS::remove(valuetype value) {
157 if (!current->
compare(value)) {
162 first=first->getNext();
168 if (!current->
compare(value)) {
169 prev->setNext(current->
getNext());
187 SINGLYLINKEDLIST_TEMPLATE
188 RUDIMENTS_TEMPLATE_INLINE
189 bool SINGLYLINKEDLIST_CLASS::removeAll(valuetype value) {
192 if (!current->
compare(value)) {
201 first=first->getNext();
210 if (!current->
compare(value)) {
229 SINGLYLINKEDLIST_TEMPLATE
230 RUDIMENTS_TEMPLATE_INLINE
241 first=first->getNext();
248 prev->setNext(current->
getNext());
266 SINGLYLINKEDLIST_TEMPLATE
267 RUDIMENTS_TEMPLATE_INLINE
268 uint64_t SINGLYLINKEDLIST_CLASS::getLength()
const {
272 SINGLYLINKEDLIST_TEMPLATE
273 RUDIMENTS_TEMPLATE_INLINE
278 SINGLYLINKEDLIST_TEMPLATE
279 RUDIMENTS_TEMPLATE_INLINE
284 SINGLYLINKEDLIST_TEMPLATE
285 RUDIMENTS_TEMPLATE_INLINE
288 return (node)?node->
getNext():NULL;
291 SINGLYLINKEDLIST_TEMPLATE
292 RUDIMENTS_TEMPLATE_INLINE
297 SINGLYLINKEDLIST_TEMPLATE
298 RUDIMENTS_TEMPLATE_INLINE
303 current; current=current->
getNext()) {
304 if (!current->
compare(value)) {
311 SINGLYLINKEDLIST_TEMPLATE
312 RUDIMENTS_TEMPLATE_INLINE
313 void SINGLYLINKEDLIST_CLASS::insertionSort() {
347 if (newfirst->
compare(node)>0) {
348 node->setNext(newfirst);
354 if (newlast->
compare(node)<=0) {
356 newlast->setNext(node);
368 if (current->
compare(node)>0) {
371 node->setNext(current);
372 previous->setNext(node);
391 SINGLYLINKEDLIST_TEMPLATE
392 RUDIMENTS_TEMPLATE_INLINE
393 void SINGLYLINKEDLIST_CLASS::heapSort() {
416 uint64_t child=heapend;
420 uint64_t parent=(child-1)/2;
423 if (heap[parent]->compare(heap[child])<0) {
425 heap[parent]=heap[child];
463 node->setNext(newfirst);
481 heap[0]=heap[heapend];
490 uint64_t leftchild=parent*2+1;
491 if (leftchild>heapend) {
496 uint64_t greater=parent;
497 if (heap[parent]->compare(heap[leftchild])<0) {
502 uint64_t rightchild=leftchild+1;
503 if (rightchild<=heapend &&
504 heap[rightchild]->compare(heap[greater])>0) {
510 if (greater==parent) {
518 heap[parent]=heap[greater];
525 SINGLYLINKEDLIST_TEMPLATE
526 RUDIMENTS_TEMPLATE_INLINE
527 void SINGLYLINKEDLIST_CLASS::clear() {
540 SINGLYLINKEDLIST_TEMPLATE
541 RUDIMENTS_TEMPLATE_INLINE
542 void SINGLYLINKEDLIST_CLASS::print()
const {
546 SINGLYLINKEDLIST_TEMPLATE
547 RUDIMENTS_TEMPLATE_INLINE
548 void SINGLYLINKEDLIST_CLASS::print(uint64_t count)
const {
551 current && i<count; current=current->
getNext()) {
552 stdoutput.
printf(
"index %lld: ",(
long long)i);
559 #define SINGLYLINKEDLISTNODE_TEMPLATE template <class valuetype>
561 #define SINGLYLINKEDLISTNODE_CLASS singlylinkedlistnode<valuetype>
563 SINGLYLINKEDLISTNODE_TEMPLATE
564 RUDIMENTS_TEMPLATE_INLINE
565 SINGLYLINKEDLISTNODE_CLASS::singlylinkedlistnode(valuetype value) {
570 SINGLYLINKEDLISTNODE_TEMPLATE
571 RUDIMENTS_TEMPLATE_INLINE
572 SINGLYLINKEDLISTNODE_CLASS::~singlylinkedlistnode() {
575 SINGLYLINKEDLISTNODE_TEMPLATE
576 RUDIMENTS_TEMPLATE_INLINE
577 void SINGLYLINKEDLISTNODE_CLASS::setValue(valuetype value) {
581 SINGLYLINKEDLISTNODE_TEMPLATE
582 RUDIMENTS_TEMPLATE_INLINE
583 valuetype SINGLYLINKEDLISTNODE_CLASS::getValue()
const {
587 SINGLYLINKEDLISTNODE_TEMPLATE
588 RUDIMENTS_TEMPLATE_INLINE
589 SINGLYLINKEDLISTNODE_CLASS *SINGLYLINKEDLISTNODE_CLASS::getNext() {
593 SINGLYLINKEDLISTNODE_TEMPLATE
594 RUDIMENTS_TEMPLATE_INLINE
595 int32_t SINGLYLINKEDLISTNODE_CLASS::compare(valuetype value)
const {
596 return _linkedlistutil_compare(this->value,value);
599 SINGLYLINKEDLISTNODE_TEMPLATE
600 RUDIMENTS_TEMPLATE_INLINE
601 int32_t SINGLYLINKEDLISTNODE_CLASS::compare(
603 return _linkedlistutil_compare(this->value,peer->value);
606 SINGLYLINKEDLISTNODE_TEMPLATE
607 RUDIMENTS_TEMPLATE_INLINE
608 void SINGLYLINKEDLISTNODE_CLASS::print()
const {
609 _linkedlistutil_print(value);
612 SINGLYLINKEDLISTNODE_TEMPLATE
613 RUDIMENTS_TEMPLATE_INLINE
614 void SINGLYLINKEDLISTNODE_CLASS::setNext(SINGLYLINKEDLISTNODE_CLASS *next) {
singlylinkedlistnode< valuetype > * getNext()
size_t printf(const char *format,...)
Definition: singlylinkedlist.h:12
int32_t compare(valuetype value) const