00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #include "copyright.h"
00020
00021
00022
00023
00024
00025
00026
00027
00028 template <class T>
00029 ListElement<T>::ListElement(T itm)
00030 {
00031 item = itm;
00032 next = NULL;
00033 }
00034
00035
00036
00037
00038
00039
00040
00041
00042 template <class T>
00043 List<T>::List()
00044 {
00045 first = last = NULL;
00046 numInList = 0;
00047 }
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057 template <class T>
00058 List<T>::~List()
00059 {
00060 }
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073 template <class T>
00074 void
00075 List<T>::Append(T item)
00076 {
00077 ListElement<T> *element = new ListElement<T>(item);
00078
00079 ASSERT(!IsInList(item));
00080 if (IsEmpty()) {
00081 first = element;
00082 last = element;
00083 } else {
00084 last->next = element;
00085 last = element;
00086 }
00087 numInList++;
00088 ASSERT(IsInList(item));
00089 }
00090
00091
00092
00093
00094
00095
00096 template <class T>
00097 void
00098 List<T>::Prepend(T item)
00099 {
00100 ListElement<T> *element = new ListElement<T>(item);
00101
00102 ASSERT(!IsInList(item));
00103 if (IsEmpty()) {
00104 first = element;
00105 last = element;
00106 } else {
00107 element->next = first;
00108 first = element;
00109 }
00110 numInList++;
00111 ASSERT(IsInList(item));
00112 }
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123 template <class T>
00124 T
00125 List<T>::RemoveFront()
00126 {
00127 ListElement<T> *element = first;
00128 T thing;
00129
00130 ASSERT(!IsEmpty());
00131
00132 thing = first->item;
00133 if (first == last) {
00134 first = NULL;
00135 last = NULL;
00136 } else {
00137 first = element->next;
00138 }
00139 numInList--;
00140 delete element;
00141 return thing;
00142 }
00143
00144
00145
00146
00147
00148
00149 template <class T>
00150 void
00151 List<T>::Remove(T item)
00152 {
00153 ListElement<T> *prev, *ptr;
00154 T removed;
00155
00156 ASSERT(IsInList(item));
00157
00158
00159 if (item == first->item) {
00160 removed = RemoveFront();
00161 ASSERT(item == removed);
00162 } else {
00163 prev = first;
00164 for (ptr = first->next; ptr != NULL; prev = ptr, ptr = ptr->next) {
00165 if (item == ptr->item) {
00166 prev->next = ptr->next;
00167 if (prev->next == NULL) {
00168 last = prev;
00169 }
00170 delete ptr;
00171 numInList--;
00172 break;
00173 }
00174 }
00175 ASSERT(ptr != NULL);
00176 }
00177 ASSERT(!IsInList(item));
00178 }
00179
00180
00181
00182
00183
00184
00185 template <class T>
00186 bool
00187 List<T>::IsInList(T item) const
00188 {
00189 ListElement<T> *ptr;
00190
00191 for (ptr = first; ptr != NULL; ptr = ptr->next) {
00192 if (item == ptr->item) {
00193 return TRUE;
00194 }
00195 }
00196 return FALSE;
00197 }
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207 template <class T>
00208 void
00209 List<T>::Apply(void (*func)(T)) const
00210 {
00211 ListElement<T> *ptr;
00212
00213 for (ptr = first; ptr != NULL; ptr = ptr->next) {
00214 (*func)(ptr->item);
00215 }
00216 }
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231
00232 template <class T>
00233 void
00234 SortedList<T>::Insert(T item)
00235 {
00236 ListElement<T> *element = new ListElement<T>(item);
00237 ListElement<T> *ptr;
00238
00239 ASSERT(!IsInList(item));
00240 if (this->IsEmpty()) {
00241 this->first = element;
00242 this->last = element;
00243 } else if (compare(item, this->first->item) < 0) {
00244 element->next = this->first;
00245 this->first = element;
00246 } else {
00247 for (ptr = this->first; ptr->next != NULL; ptr = ptr->next) {
00248 if (compare(item, ptr->next->item) < 0) {
00249 element->next = ptr->next;
00250 ptr->next = element;
00251 this->numInList++;
00252 return;
00253 }
00254 }
00255 this->last->next = element;
00256 this->last = element;
00257 }
00258 this->numInList++;
00259 ASSERT(IsInList(item));
00260 }
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270 template <class T>
00271 void
00272 List<T>::SanityCheck() const
00273 {
00274 ListElement<T> *ptr;
00275 int numFound;
00276
00277 if (first == NULL) {
00278 ASSERT((numInList == 0) && (last == NULL));
00279 } else if (first == last) {
00280 ASSERT((numInList == 1) && (last->next == NULL));
00281 } else {
00282 for (numFound = 1, ptr = first; ptr != last; ptr = ptr->next) {
00283 numFound++;
00284 ASSERT(numFound <= numInList);
00285 }
00286 ASSERT(numFound == numInList);
00287 ASSERT(last->next == NULL);
00288 }
00289 }
00290
00291
00292
00293
00294
00295
00296 template <class T>
00297 void
00298 List<T>::SelfTest(T *p, int numEntries)
00299 {
00300 int i;
00301 ListIterator<T> *iterator = new ListIterator<T>(this);
00302
00303 SanityCheck();
00304
00305 ASSERT(IsEmpty() && (first == NULL));
00306 for (; !iterator->IsDone(); iterator->Next()) {
00307 ASSERTNOTREACHED();
00308 }
00309
00310 for (i = 0; i < numEntries; i++) {
00311 Append(p[i]);
00312 ASSERT(IsInList(p[i]));
00313 ASSERT(!IsEmpty());
00314 }
00315 SanityCheck();
00316
00317
00318 for (i = 0; i < numEntries; i++) {
00319 Remove(p[i]);
00320 ASSERT(!IsInList(p[i]));
00321 }
00322 ASSERT(IsEmpty());
00323 SanityCheck();
00324 delete iterator;
00325 }
00326
00327
00328
00329
00330
00331
00332
00333
00334 template <class T>
00335 void
00336 SortedList<T>::SanityCheck() const
00337 {
00338 ListElement<T> *prev, *ptr;
00339
00340 List<T>::SanityCheck();
00341 if (this->first !=this-> last) {
00342 for (prev = this->first, ptr = this->first->next; ptr != NULL;
00343 prev = ptr, ptr = ptr->next) {
00344 ASSERT(compare(prev->item, ptr->item) <= 0);
00345 }
00346 }
00347 }
00348
00349
00350
00351
00352
00353
00354 template <class T>
00355 void
00356 SortedList<T>::SelfTest(T *p, int numEntries)
00357 {
00358 int i;
00359 T *q = new T[numEntries];
00360
00361 List<T>::SelfTest(p, numEntries);
00362
00363 for (i = 0; i < numEntries; i++) {
00364 Insert(p[i]);
00365 ASSERT(IsInList(p[i]));
00366 }
00367 SanityCheck();
00368
00369
00370 for (i = 0; i < numEntries; i++) {
00371 q[i] = this->RemoveFront();
00372 ASSERT(!IsInList(q[i]));
00373 }
00374 ASSERT(this->IsEmpty());
00375
00376
00377 for (i = 0; i < (numEntries - 1); i++) {
00378 ASSERT(compare(q[i], q[i + 1]) <= 0);
00379 }
00380 SanityCheck();
00381
00382 delete q;
00383 }