// list.cc // Routines to manage a singly linked list of "things". // Lists are implemented as templates so that we can store // anything on the list in a type-safe manner. // // A "ListElement" is allocated for each item to be put on the // list; it is de-allocated when the item is removed. This means // we don't need to keep a "next" pointer in every object we // want to put on a list. // // NOTE: Mutual exclusion must be provided by the caller. // If you want a synchronized list, you must use the routines // in synchlist.cc. // // Copyright (c) 1992-1996 The Regents of the University of California. // All rights reserved. See copyright.h for copyright notice and limitation // of liability and disclaimer of warranty provisions. #include "copyright.h" //---------------------------------------------------------------------- // ListElement::ListElement // Initialize a list element, so it can be added somewhere on a list. // // "itm" is the thing to be put on the list. //---------------------------------------------------------------------- template ListElement::ListElement(T itm) { item = itm; next = NULL; // always initialize to something! } //---------------------------------------------------------------------- // List::List // Initialize a list, empty to start with. // Elements can now be added to the list. //---------------------------------------------------------------------- template List::List() { first = last = NULL; numInList = 0; } //---------------------------------------------------------------------- // List::~List // Prepare a list for deallocation. // This does *NOT* free list elements, nor does it // free the data those elements point to. // Normally, the list should be empty when this is called. //---------------------------------------------------------------------- template List::~List() { } //---------------------------------------------------------------------- // List::Append // Append an "item" to the end of the list. // // Allocate a ListElement to keep track of the item. // If the list is empty, then this will be the only element. // Otherwise, put it at the end. // // "item" is the thing to put on the list. //---------------------------------------------------------------------- template void List::Append(T item) { ListElement *element = new ListElement(item); ASSERT(!IsInList(item)); if (IsEmpty()) { // list is empty first = element; last = element; } else { // else put it after last last->next = element; last = element; } numInList++; ASSERT(IsInList(item)); } //---------------------------------------------------------------------- // List::Prepend // Same as Append, only put "item" on the front. //---------------------------------------------------------------------- template void List::Prepend(T item) { ListElement *element = new ListElement(item); ASSERT(!IsInList(item)); if (IsEmpty()) { // list is empty first = element; last = element; } else { // else put it before first element->next = first; first = element; } numInList++; ASSERT(IsInList(item)); } //---------------------------------------------------------------------- // List::RemoveFront // Remove the first "item" from the front of the list. // List must not be empty. // // Returns: // The removed item. //---------------------------------------------------------------------- template T List::RemoveFront() { ListElement *element = first; T thing; ASSERT(!IsEmpty()); thing = first->item; if (first == last) { // list had one item, now has none first = NULL; last = NULL; } else { first = element->next; } numInList--; delete element; return thing; } //---------------------------------------------------------------------- // List::Remove // Remove a specific item from the list. Must be in the list! //---------------------------------------------------------------------- template void List::Remove(T item) { ListElement *prev, *ptr; T removed; ASSERT(IsInList(item)); // if first item on list is match, then remove from front if (item == first->item) { removed = RemoveFront(); ASSERT(item == removed); } else { prev = first; for (ptr = first->next; ptr != NULL; prev = ptr, ptr = ptr->next) { if (item == ptr->item) { prev->next = ptr->next; if (prev->next == NULL) { last = prev; } delete ptr; numInList--; break; } } ASSERT(ptr != NULL); // should always find item! } ASSERT(!IsInList(item)); } //---------------------------------------------------------------------- // List::IsInList // Return TRUE if the item is in the list. //---------------------------------------------------------------------- template bool List::IsInList(T item) const { ListElement *ptr; for (ptr = first; ptr != NULL; ptr = ptr->next) { if (item == ptr->item) { return TRUE; } } return FALSE; } //---------------------------------------------------------------------- // List::Apply // Apply function to every item on a list. // // "func" -- the function to apply //---------------------------------------------------------------------- template void List::Apply(void (*func)(T)) const { ListElement *ptr; for (ptr = first; ptr != NULL; ptr = ptr->next) { (*func)(ptr->item); } } //---------------------------------------------------------------------- // SortedList::Insert // Insert an "item" into a list, so that the list elements are // sorted in increasing order. // // Allocate a ListElement to keep track of the item. // If the list is empty, then this will be the only element. // Otherwise, walk through the list, one element at a time, // to find where the new item should be placed. // // "item" is the thing to put on the list. //---------------------------------------------------------------------- template void SortedList::Insert(T item) { ListElement *element = new ListElement(item); ListElement *ptr; // keep track ASSERT(!IsInList(item)); if (IsEmpty()) { // if list is empty, put at front first = element; last = element; } else if (compare(item, first->item) < 0) { // item goes at front element->next = first; first = element; } else { // look for first elt in list bigger than item for (ptr = first; ptr->next != NULL; ptr = ptr->next) { if (compare(item, ptr->next->item) < 0) { element->next = ptr->next; ptr->next = element; numInList++; return; } } last->next = element; // item goes at end of list last = element; } numInList++; ASSERT(IsInList(item)); } //---------------------------------------------------------------------- // List::SanityCheck // Test whether this is still a legal list. // // Tests: do I get to last starting from first? // does the list have the right # of elements? //---------------------------------------------------------------------- template void List::SanityCheck() const { ListElement *ptr; int numFound; if (first == NULL) { ASSERT((numInList == 0) && (last == NULL)); } else if (first == last) { ASSERT((numInList == 1) && (last->next == NULL)); } else { for (numFound = 1, ptr = first; ptr != last; ptr = ptr->next) { numFound++; ASSERT(numFound } ASSERT(numFound == numInList); ASSERT(last->next == NULL); } } //---------------------------------------------------------------------- // List::SelfTest // Test whether this module is working. //---------------------------------------------------------------------- template void List::SelfTest(T *p, int numEntries) { int i; ListIterator *iterator = new ListIterator(this); SanityCheck(); // check various ways that list is empty ASSERT(IsEmpty() && (first == NULL)); for (; !iterator->IsDone(); iterator->Next()) { ASSERTNOTREACHED(); // nothing on list } for (i = 0; i < numEntries; i++) { Append(p[i]); ASSERT(IsInList(p[i])); ASSERT(!IsEmpty()); } SanityCheck(); // should be able to get out everything we put in for (i = 0; i < numEntries; i++) { Remove(p[i]); ASSERT(!IsInList(p[i])); } ASSERT(IsEmpty()); SanityCheck(); delete iterator; } //---------------------------------------------------------------------- // SortedList::SanityCheck // Test whether this is still a legal sorted list. // // Test: is the list sorted? //---------------------------------------------------------------------- template void SortedList::SanityCheck() const { ListElement *prev, *ptr; List::SanityCheck(); if (first != last) { for (prev = first, ptr = first->next; ptr != NULL; prev = ptr, ptr = ptr->next) { ASSERT(compare(prev->item, ptr->item) } } } //---------------------------------------------------------------------- // SortedList::SelfTest // Test whether this module is working. //---------------------------------------------------------------------- template void SortedList::SelfTest(T *p, int numEntries) { int i; T *q = new T[numEntries]; List::SelfTest(p, numEntries); for (i = 0; i < numEntries; i++) { Insert(p[i]); ASSERT(IsInList(p[i])); } SanityCheck(); // should be able to get out everything we put in for (i = 0; i < numEntries; i++) { q[i] = RemoveFront(); ASSERT(!IsInList(q[i])); } ASSERT(IsEmpty()); // make sure everything came out in the right order for (i = 0; i < (numEntries - 1); i++) { ASSERT(compare(q[i], q[i + 1]) } SanityCheck(); delete q; }
