4 #include <rudiments/stdio.h> 5 #include <rudiments/private/rudimentsinlines.h> 6 #include <rudiments/private/nodeinlines.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) {
195 while (!current->
compare(value)) {
204 first=first->getNext();
213 if (!current->
compare(value)) {
232 SINGLYLINKEDLIST_TEMPLATE
233 RUDIMENTS_TEMPLATE_INLINE
244 first=first->getNext();
251 prev->setNext(current->
getNext());
269 SINGLYLINKEDLIST_TEMPLATE
270 RUDIMENTS_TEMPLATE_INLINE
271 uint64_t SINGLYLINKEDLIST_CLASS::getLength()
const {
275 SINGLYLINKEDLIST_TEMPLATE
276 RUDIMENTS_TEMPLATE_INLINE
281 SINGLYLINKEDLIST_TEMPLATE
282 RUDIMENTS_TEMPLATE_INLINE
287 SINGLYLINKEDLIST_TEMPLATE
288 RUDIMENTS_TEMPLATE_INLINE
291 return (node)?node->
getNext():NULL;
294 SINGLYLINKEDLIST_TEMPLATE
295 RUDIMENTS_TEMPLATE_INLINE
300 SINGLYLINKEDLIST_TEMPLATE
301 RUDIMENTS_TEMPLATE_INLINE
306 current; current=current->
getNext()) {
307 if (!current->
compare(value)) {
314 SINGLYLINKEDLIST_TEMPLATE
315 RUDIMENTS_TEMPLATE_INLINE
316 void SINGLYLINKEDLIST_CLASS::insertionSort() {
350 if (newfirst->
compare(node)>0) {
351 node->setNext(newfirst);
357 if (newlast->
compare(node)<=0) {
359 newlast->setNext(node);
371 if (current->
compare(node)>0) {
374 node->setNext(current);
375 previous->setNext(node);
394 SINGLYLINKEDLIST_TEMPLATE
395 RUDIMENTS_TEMPLATE_INLINE
396 void SINGLYLINKEDLIST_CLASS::heapSort() {
419 uint64_t child=heapend;
423 uint64_t parent=(child-1)/2;
426 if (heap[parent]->compare(heap[child])<0) {
428 heap[parent]=heap[child];
466 node->setNext(newfirst);
484 heap[0]=heap[heapend];
493 uint64_t leftchild=parent*2+1;
494 if (leftchild>heapend) {
499 uint64_t greater=parent;
500 if (heap[parent]->compare(heap[leftchild])<0) {
505 uint64_t rightchild=leftchild+1;
506 if (rightchild<=heapend &&
507 heap[rightchild]->compare(heap[greater])>0) {
513 if (greater==parent) {
521 heap[parent]=heap[greater];
528 SINGLYLINKEDLIST_TEMPLATE
529 RUDIMENTS_TEMPLATE_INLINE
530 void SINGLYLINKEDLIST_CLASS::clear() {
543 SINGLYLINKEDLIST_TEMPLATE
544 RUDIMENTS_TEMPLATE_INLINE
545 void SINGLYLINKEDLIST_CLASS::print()
const {
549 SINGLYLINKEDLIST_TEMPLATE
550 RUDIMENTS_TEMPLATE_INLINE
551 void SINGLYLINKEDLIST_CLASS::print(uint64_t count)
const {
554 current && i<count; current=current->
getNext()) {
555 #ifdef RUDIMENTS_HAVE_LONG_LONG 556 stdoutput.
printf(
"index %lld: ",(
long long)i);
558 stdoutput.
printf(
"index %ld: ",(
long)i);
566 #define SINGLYLINKEDLISTNODE_TEMPLATE template <class valuetype> 568 #define SINGLYLINKEDLISTNODE_CLASS singlylinkedlistnode<valuetype> 570 SINGLYLINKEDLISTNODE_TEMPLATE
571 RUDIMENTS_TEMPLATE_INLINE
572 SINGLYLINKEDLISTNODE_CLASS::singlylinkedlistnode(valuetype value) {
577 SINGLYLINKEDLISTNODE_TEMPLATE
578 RUDIMENTS_TEMPLATE_INLINE
579 SINGLYLINKEDLISTNODE_CLASS::~singlylinkedlistnode() {
582 SINGLYLINKEDLISTNODE_TEMPLATE
583 RUDIMENTS_TEMPLATE_INLINE
584 void SINGLYLINKEDLISTNODE_CLASS::setValue(valuetype value) {
588 SINGLYLINKEDLISTNODE_TEMPLATE
589 RUDIMENTS_TEMPLATE_INLINE
590 valuetype SINGLYLINKEDLISTNODE_CLASS::getValue()
const {
594 SINGLYLINKEDLISTNODE_TEMPLATE
595 RUDIMENTS_TEMPLATE_INLINE
596 SINGLYLINKEDLISTNODE_CLASS *SINGLYLINKEDLISTNODE_CLASS::getNext() {
600 SINGLYLINKEDLISTNODE_TEMPLATE
601 RUDIMENTS_TEMPLATE_INLINE
602 int32_t SINGLYLINKEDLISTNODE_CLASS::compare(valuetype value)
const {
603 return node_compare(this->value,value);
606 SINGLYLINKEDLISTNODE_TEMPLATE
607 RUDIMENTS_TEMPLATE_INLINE
608 int32_t SINGLYLINKEDLISTNODE_CLASS::compare(
610 return node_compare(this->value,peer->value);
613 SINGLYLINKEDLISTNODE_TEMPLATE
614 RUDIMENTS_TEMPLATE_INLINE
615 void SINGLYLINKEDLISTNODE_CLASS::print()
const {
619 SINGLYLINKEDLISTNODE_TEMPLATE
620 RUDIMENTS_TEMPLATE_INLINE
621 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