Rudiments
|
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