Page principale | Liste des namespaces | Hiérarchie des classes | Liste des classes | Répertoires | Liste des fichiers | Membres de namespace | Membres de classe | Membres de fichier

list.cc

Aller à la documentation de ce fichier.
00001 // list.cc 
00002 //      Routines to manage a singly linked list of "things".
00003 //      Lists are implemented as templates so that we can store
00004 //      anything on the list in a type-safe manner.
00005 //
00006 //      A "ListElement" is allocated for each item to be put on the
00007 //      list; it is de-allocated when the item is removed. This means
00008 //      we don't need to keep a "next" pointer in every object we
00009 //      want to put on a list.
00010 // 
00011 //      NOTE: Mutual exclusion must be provided by the caller.
00012 //      If you want a synchronized list, you must use the routines 
00013 //      in synchlist.cc.
00014 //
00015 // Copyright (c) 1992-1996 The Regents of the University of California.
00016 // All rights reserved.  See copyright.h for copyright notice and limitation 
00017 // of liability and disclaimer of warranty provisions.
00018 
00019 #include "copyright.h"
00020 
00021 //----------------------------------------------------------------------
00022 // ListElement<T>::ListElement
00023 //      Initialize a list element, so it can be added somewhere on a list.
00024 //
00025 //      "itm" is the thing to be put on the list.
00026 //----------------------------------------------------------------------
00027 
00028 template <class T>
00029 ListElement<T>::ListElement(T itm)
00030 {
00031      item = itm;
00032      next = NULL;       // always initialize to something!
00033 }
00034 
00035 
00036 //----------------------------------------------------------------------
00037 // List<T>::List
00038 //      Initialize a list, empty to start with.
00039 //      Elements can now be added to the list.
00040 //----------------------------------------------------------------------
00041 
00042 template <class T>
00043 List<T>::List()
00044 { 
00045     first = last = NULL; 
00046     numInList = 0;
00047 }
00048 
00049 //----------------------------------------------------------------------
00050 // List<T>::~List
00051 //      Prepare a list for deallocation.  
00052 //      This does *NOT* free list elements, nor does it
00053 //      free the data those elements point to.
00054 //      Normally, the list should be empty when this is called.
00055 //----------------------------------------------------------------------
00056 
00057 template <class T>
00058 List<T>::~List()
00059 { 
00060 }
00061 
00062 //----------------------------------------------------------------------
00063 // List<T>::Append
00064 //      Append an "item" to the end of the list.
00065 //      
00066 //      Allocate a ListElement to keep track of the item.
00067 //      If the list is empty, then this will be the only element.
00068 //      Otherwise, put it at the end.
00069 //
00070 //      "item" is the thing to put on the list.
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()) {            // list is empty
00081         first = element;
00082         last = element;
00083     } else {                    // else put it after last
00084         last->next = element;
00085         last = element;
00086     }
00087     numInList++;
00088     ASSERT(IsInList(item));
00089 }
00090 
00091 //----------------------------------------------------------------------
00092 // List<T>::Prepend
00093 //      Same as Append, only put "item" on the front.
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()) {            // list is empty
00104         first = element;
00105         last = element;
00106     } else {                    // else put it before first
00107         element->next = first;
00108         first = element;
00109     }
00110     numInList++;
00111     ASSERT(IsInList(item));
00112 }
00113 
00114 //----------------------------------------------------------------------
00115 // List<T>::RemoveFront
00116 //      Remove the first "item" from the front of the list.
00117 //      List must not be empty.
00118 // 
00119 // Returns:
00120 //      The removed item.
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) {        // list had one item, now has none 
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 // List<T>::Remove
00146 //      Remove a specific item from the list.  Must be in the list!
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     // if first item on list is match, then remove from front
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);    // should always find item!
00176     }
00177    ASSERT(!IsInList(item));
00178 }
00179 
00180 //----------------------------------------------------------------------
00181 // List<T>::IsInList
00182 //      Return TRUE if the item is in the list.
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 // List<T>::Apply
00202 //      Apply function to every item on a list.
00203 //
00204 //      "func" -- the function to apply
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 // SortedList::Insert
00221 //      Insert an "item" into a list, so that the list elements are
00222 //      sorted in increasing order.
00223 //      
00224 //      Allocate a ListElement to keep track of the item.
00225 //      If the list is empty, then this will be the only element.
00226 //      Otherwise, walk through the list, one element at a time,
00227 //      to find where the new item should be placed.
00228 //
00229 //      "item" is the thing to put on the list. 
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;                // keep track
00238 
00239     ASSERT(!IsInList(item));
00240     if (this->IsEmpty()) {                      // if list is empty, put at front
00241         this->first = element;
00242         this->last = element;
00243     } else if (compare(item, this->first->item) < 0) {  // item goes at front 
00244         element->next = this->first;
00245         this->first = element;
00246     } else {            // look for first elt in list bigger than item
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;             // item goes at end of list
00256         this->last = element;
00257     }
00258     this->numInList++;
00259     ASSERT(IsInList(item));
00260 }
00261 
00262 //----------------------------------------------------------------------
00263 // List::SanityCheck
00264 //      Test whether this is still a legal list.
00265 //
00266 //      Tests: do I get to last starting from first?
00267 //             does the list have the right # of elements?
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);      // prevent infinite loop
00285         }
00286         ASSERT(numFound == numInList);
00287         ASSERT(last->next == NULL);
00288     }
00289 }
00290 
00291 //----------------------------------------------------------------------
00292 // List::SelfTest
00293 //      Test whether this module is working.
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     // check various ways that list is empty
00305     ASSERT(IsEmpty() && (first == NULL));
00306     for (; !iterator->IsDone(); iterator->Next()) {
00307         ASSERTNOTREACHED();     // nothing on list
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      // should be able to get out everything we put in
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 // SortedList::SanityCheck
00329 //      Test whether this is still a legal sorted list.
00330 //
00331 //      Test: is the list sorted?
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 // SortedList::SelfTest
00351 //      Test whether this module is working.
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      // should be able to get out everything we put in
00370      for (i = 0; i < numEntries; i++) {
00371          q[i] = this->RemoveFront();
00372          ASSERT(!IsInList(q[i]));
00373      }
00374      ASSERT(this->IsEmpty());
00375 
00376      // make sure everything came out in the right order
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 }

Généré le Sun Jan 15 00:45:45 2006 pour Système NachOS : par  doxygen 1.4.4