Rudiments
/home/dmuse/src/rudiments/include/rudiments/private/linkedlistinlines.h
00001 // Copyright (c) 2003 David Muse
00002 // See the COPYING file for more information
00003 
00004 #ifndef EXCLUDE_RUDIMENTS_TEMPLATE_IMPLEMENTATIONS
00005 
00006 #ifdef RUDIMENTS_HAVE_STDLIB_H
00007         #include <stdlib.h>
00008 #endif
00009 #include <stdio.h>
00010 
00011 #include <rudiments/private/rudimentsinlines.h>
00012 
00013 #ifdef RUDIMENTS_NAMESPACE
00014 namespace rudiments {
00015 #endif
00016 
00017 #define LINKEDLIST_TEMPLATE template <class datatype, class linkedlistnodetype>
00018 
00019 #define LINKEDLIST_CLASS linkedlist<datatype,linkedlistnodetype>
00020 
00021 LINKEDLIST_TEMPLATE
00022 RUDIMENTS_TEMPLATE_INLINE
00023 LINKEDLIST_CLASS::linkedlist() {
00024         first=NULL;
00025         last=NULL;
00026 }
00027 
00028 LINKEDLIST_TEMPLATE
00029 RUDIMENTS_TEMPLATE_INLINE
00030 LINKEDLIST_CLASS::~linkedlist() {
00031         clear();
00032 }
00033 
00034 LINKEDLIST_TEMPLATE
00035 RUDIMENTS_TEMPLATE_INLINE
00036 void LINKEDLIST_CLASS::append(datatype data) {
00037         linkedlistnodetype      *node=new linkedlistnodetype();
00038         node->setData(data);
00039         append(node);
00040 }
00041 
00042 LINKEDLIST_TEMPLATE
00043 RUDIMENTS_TEMPLATE_INLINE
00044 void LINKEDLIST_CLASS::append(linkedlistnodetype *node) {
00045         if (last) {
00046                 last->setNext(node);
00047                 node->setPrevious(last);
00048                 last=node;
00049         } else {
00050                 first=node;
00051                 last=first;
00052         }
00053 }
00054 
00055 LINKEDLIST_TEMPLATE
00056 RUDIMENTS_TEMPLATE_INLINE
00057 bool LINKEDLIST_CLASS::insert(uint64_t index, datatype data) {
00058         linkedlistnodetype      *node=new linkedlistnodetype();
00059         node->setData(data);
00060         return insert(index,node);
00061 }
00062 
00063 LINKEDLIST_TEMPLATE
00064 RUDIMENTS_TEMPLATE_INLINE
00065 bool LINKEDLIST_CLASS::insert(uint64_t index, linkedlistnodetype *node) {
00066 
00067         // handle insert into index 0
00068         if (!index) {
00069                 node->setNext(first);
00070                 first->setPrevious(node);
00071                 first=(linkedlistnodetype *)node;
00072                 return true;
00073         }
00074 
00075         // handle general insert
00076         linkedlistnodetype      *current=getNodeByIndex(index-1);
00077         if (!current) {
00078                 return false;
00079         }
00080         node->setPrevious(current);
00081         node->setNext(current->getNext());
00082         current->getNext()->setPrevious(node);
00083         current->setNext(node);
00084         return true;
00085 }
00086 
00087 LINKEDLIST_TEMPLATE
00088 RUDIMENTS_TEMPLATE_INLINE
00089 bool LINKEDLIST_CLASS::setDataByIndex(uint64_t index, datatype data) {
00090         linkedlistnodetype      *current=getNodeByIndex(index);
00091         if (current) {
00092                 current->setData(data);
00093                 return true;
00094         }
00095         return false;
00096 }
00097 
00098 LINKEDLIST_TEMPLATE
00099 RUDIMENTS_TEMPLATE_INLINE
00100 bool LINKEDLIST_CLASS::removeByIndex(uint64_t index) {
00101         return removeNode(getNodeByIndex(index));
00102 }
00103 
00104 LINKEDLIST_TEMPLATE
00105 RUDIMENTS_TEMPLATE_INLINE
00106 bool LINKEDLIST_CLASS::removeByData(datatype data) {
00107         for (linkedlistnodetype *current=first; current;
00108                         current=(linkedlistnodetype *)current->getNext()) {
00109                 if (!current->compare(data)) {
00110                         return removeNode(current);
00111                 }
00112         }
00113         return false;
00114 }
00115 
00116 LINKEDLIST_TEMPLATE
00117 RUDIMENTS_TEMPLATE_INLINE
00118 bool LINKEDLIST_CLASS::removeAllByData(datatype data) {
00119 
00120         linkedlistnodetype      *current=first;
00121         linkedlistnodetype      *next;
00122         while (current) {
00123                 if (!current->compare(data)) {
00124                         next=(linkedlistnodetype *)current->getNext();
00125                         if (!removeNode(current)) {
00126                                 return false;
00127                         }
00128                         current=next;
00129                 } else {
00130                         current=(linkedlistnodetype *)current->getNext();
00131                 }
00132         }
00133         return true;
00134 }
00135 
00136 LINKEDLIST_TEMPLATE
00137 RUDIMENTS_TEMPLATE_INLINE
00138 bool LINKEDLIST_CLASS::removeNode(linkedlistnodetype *node) {
00139         if (!node) {
00140                 return false;
00141         }
00142         if (node->getNext()) {
00143                 node->getNext()->setPrevious(node->getPrevious());
00144         }
00145         if (node->getPrevious()) {
00146                 node->getPrevious()->setNext(node->getNext());
00147         }
00148         if (node==first) {
00149                 first=(linkedlistnodetype *)node->getNext();
00150         }
00151         if (node==last) {
00152                 last=(linkedlistnodetype *)node->getPrevious();
00153         }
00154         delete node;
00155         return true;
00156 }
00157 
00158 LINKEDLIST_TEMPLATE
00159 RUDIMENTS_TEMPLATE_INLINE
00160 bool LINKEDLIST_CLASS::getDataByIndex(uint64_t index, datatype *data) {
00161         linkedlistnodetype      *current=getNodeByIndex(index);
00162         if (current) {
00163                 *data=current->getData();
00164                 return true;
00165         }
00166         return false;
00167 }
00168 
00169 LINKEDLIST_TEMPLATE
00170 RUDIMENTS_TEMPLATE_INLINE
00171 uint64_t LINKEDLIST_CLASS::getLength() const {
00172         uint64_t        length=0;
00173         for (linkedlistnodetype *current=first; current;
00174                         current=(linkedlistnodetype *)current->getNext()) {
00175                 length++;
00176         }
00177         return length;
00178 }
00179 
00180 LINKEDLIST_TEMPLATE
00181 RUDIMENTS_TEMPLATE_INLINE
00182 linkedlistnodetype *LINKEDLIST_CLASS::getFirstNode() {
00183         return (linkedlistnodetype *)first;
00184 }
00185 
00186 LINKEDLIST_TEMPLATE
00187 RUDIMENTS_TEMPLATE_INLINE
00188 linkedlistnodetype *LINKEDLIST_CLASS::getLastNode() {
00189         return (linkedlistnodetype *)last;
00190 }
00191 
00192 LINKEDLIST_TEMPLATE
00193 RUDIMENTS_TEMPLATE_INLINE
00194 linkedlistnodetype *LINKEDLIST_CLASS::getNodeByIndex(uint64_t index) {
00195         linkedlistnodetype      *current=(linkedlistnodetype *)first;
00196         for (uint64_t i=0; current && i<index; i++) {
00197                 current=(linkedlistnodetype *)current->getNext();
00198         }
00199         return current;
00200 }
00201 
00202 LINKEDLIST_TEMPLATE
00203 RUDIMENTS_TEMPLATE_INLINE
00204 linkedlistnodetype *LINKEDLIST_CLASS::getNodeByData(datatype data) {
00205         return getNodeByData((linkedlistnodetype *)first,data);
00206 }
00207 
00208 LINKEDLIST_TEMPLATE
00209 RUDIMENTS_TEMPLATE_INLINE
00210 linkedlistnodetype *LINKEDLIST_CLASS::getNodeByData(
00211                                                 linkedlistnodetype *startnode,
00212                                                         datatype data) {
00213         for (linkedlistnodetype *current=startnode; current;
00214                         current=(linkedlistnodetype *)current->getNext()) {
00215                 if (!current->compare(data)) {
00216                         return current;
00217                 }
00218         }
00219         return NULL;
00220 }
00221 
00222 LINKEDLIST_TEMPLATE
00223 RUDIMENTS_TEMPLATE_INLINE
00224 void LINKEDLIST_CLASS::clear() {
00225         linkedlistnodetype      *next;
00226         linkedlistnodetype      *current=first;
00227         while (current) {
00228                 next=(linkedlistnodetype *)current->getNext();
00229                 delete current;
00230                 current=next;
00231         }
00232         first=NULL;
00233         last=NULL;
00234 }
00235 
00236 LINKEDLIST_TEMPLATE
00237 RUDIMENTS_TEMPLATE_INLINE
00238 void LINKEDLIST_CLASS::print() const {
00239         uint64_t        i=0;
00240         for (linkedlistnodetype *current=first; current;
00241                 current=(linkedlistnodetype *)current->getNext()) {
00242                 printf("index %lld: ",(long long)i);
00243                 current->print();
00244                 printf("\n");
00245                 i++;
00246         }
00247 }
00248 
00249 #ifdef RUDIMENTS_NAMESPACE
00250 }
00251 #endif
00252 
00253 #endif