//======================================================== // Filename: llist.cpp // Author: Roger Z. Rios-Mercado // Date: 04/OC/93 // Modified: SP/94 // Comment: For the FUTMEX project, this file // should NOT be further modified // (with exception of the first comment // below) //======================================================== // RZRM: The following line might need to be uncommented for // some compilers: #include. //#include #include "llist.hpp" //********************************************************* // Destructor //********************************************************* // // Before invoking the destructor you should use either // flush() (to delete every node and data entity) or // flush_nodes() (to delete every node). //********************************************************* llist::~llist() { // delete [] name; Use this line in unix delete name; head = tail = current = NULL; keycount = 0; compare = NULL; } // end destructor (llist) //********************************************************* // Function: llist::insert //********************************************************* // // INPUT: Ptr to data entity. // JOB: Inserts an entity in the structure. Copies // only the data ptr. Ordered insertion. Set // to the just inserted element. // RETURNS: 1 if insertion OK; 0 otherwise. //********************************************************* int llist::insert(void *data) { llist_node *prev = NULL, *here = NULL; // // If there is no data, return (0). // if (data == NULL) return (0); // // Insert at beginning of list. Empty list or // data < head->data. // if (head == NULL || compare(data, head->data) < 0) { return (insertfirst(data)); } // // Insert at middle of list. Must remember ptr to // previous element to insert the new element // between the previous element and this element // (prev and here). // prev = head; here = head->next; while(here != NULL) { if (compare(data, here->data) < 0) { current = new llist_node (data, here); assert (current); prev->next = current; keycount++; return (1); } prev = here; here = here->next; } // end while (here!=NULL) // // End-of-list insertion. // return insertlast(data); } // end function (insert) //********************************************************* // Function: llist::insertfirst //********************************************************* // // INPUT: Ptr to data entity. // JOB: Inserts data entity at beginning of structure. // RETURNS: 1 if insertion OK; 0 otherwise. //********************************************************* int llist::insertfirst(void* data) { // // If there is no data, return (0). // if (data == NULL) return (0); // // Create current. // current = new llist_node (data, head); assert (current); // // If unable to create current, return (0). // if (current == NULL) return (0); // // If list is empty, set tail to current. // if (tail == NULL) tail = current; // // Set head to current. // head = current; keycount++; return (1); } // end function (insertfirst) //********************************************************* // Function: llist::insertlast //********************************************************* // // INPUT: Ptr to data entity. // JOB: Inserts data entity at end of structure. // RETURN: 1 if insertion OK; 0 otherwise. //********************************************************* int llist::insertlast(void* data) { // // If there is no data return (0). // if (data == NULL) return (0); // // Create current. // current = new llist_node(data); assert (current); // // If unable to create it, return (0). // if (current == NULL) return (0); // // If struct is empty, set head to current; // otherwise set tail->next to current. // if (tail == NULL) head = current; else tail->next = current; // // Set tail to current. // tail = current; keycount++; return (1); } // end function (insertlast) //********************************************************* // Function: llist::print //********************************************************* // // INPUT: No arguments. // JOB: Prints structure. // RETURNS: Nothing //********************************************************* void llist::print() { int i = 0; current = head; printf(" Elements of structure\n"); printf("---------------------------\n\n"); while (current != NULL) { printf("%3d %s\n", ++i, current->data); current = current->next; } printf("---------------------------\n\n"); // // Reset. // current = head; } // end function (print) //********************************************************* // Function: llist::flush //********************************************************* // // INPUT: No arguments. // JOB: Empties out the structure, but leave structure. // Reinitialize it to an empty structure. // Deletes both, list node and corresponding data // entity. // RETURNS: Nothing. //********************************************************* void llist::flush() { while (head != NULL) { current = head; head = current->next; delete current->data; delete current; keycount--; } } // end function (flush) //********************************************************* // Function: llist::flush //********************************************************* // // INPUT: No arguments. // JOB: Empties out the structure, but leave structure. // DOESN'T DELETE data entities, just the nodes. // Reinitialize it to an empty structure. // Use it before calling destructor when data // entities also belong to some other structure. // RETURNS: Nothing. //********************************************************* void llist::flush_nodes() { while (head != NULL) { current = head; head = current->next; delete current; keycount--; } } // end function (flush) //********************************************************* // Function: llist::remove //********************************************************* // // INPUT: Ptr to data entity. // JOB: Remove data entity from structure. // RETURNS: Ptr to data. //********************************************************* void* llist::remove(void* data) { llist_node **anchor = &head; llist_node *prev = NULL; llist_node *here = head; // // If list is empty or there is no data return (NULL). // if (head == NULL || data == NULL) return (NULL); while (here) { if (compare(data, here->data) == 0) { data = here->data; *anchor = here->next; if (tail == here) tail = prev; // // Set current to predecesor of deleted element. // current = prev; delete here; keycount--; return (data); } // end if (compare) prev = here; anchor = &(here->next); here = here->next; } // end while (here) // // Data not found. // return (NULL); } // end function (remove) //********************************************************* // Function: llist::find //********************************************************* // // INPUT: Ptr to data. // JOB: Finds data entity in structure, but it does // not remove it. // RETURNS: Ptr to data. //********************************************************* void* llist::find(void* data) { // // If there is no data, return (NULL). // if (data == NULL) return (NULL); // // Set current to head. // current = head; // // While there are elements in the structure: // o Return if data is matched. // while(current != NULL) { if (compare(data, current->data) == 0) return (current->data); current = current->next; } // // Data not found. Reset. // current = head; return (NULL); } // end function (find) //********************************************************* // Function: llist::first //********************************************************* // // INPUT: No arguments. // OUTPUT: Ptr to the first data entity in the // structure. //********************************************************* void* llist::first() { current = head; if (current != NULL) return (current->data); else return (NULL); } // end function (first) //********************************************************* // Function: llist::last //********************************************************* // // INPUT: No arguments. // OUTPUT: Ptr to the last data entity in the // structure. //********************************************************* void* llist::last() { current = tail; if (current != NULL) return (current->data); else return (NULL); } // end function (last) //********************************************************* // Function: llist::next //********************************************************* // // INPUT: No arguments. // OUTPUT: Ptr to the next data entity, affected by // access. //********************************************************* void* llist::next() { // // If there is no current or current is the tail // there is no next element. Return (NULL). // if (current == NULL || current == tail) return (NULL); current = current->next; // // If current is not NULL, return pointer to // data; otherwise, return (NULL). // if (current != NULL) return (current->data); else return (NULL); } // end function (next) //********************************************************* // Function: llist::prev //********************************************************* // // INPUT: No arguments. // RETURNS: ptr to previous data entity, // affected by access. // // This is really expensive in single linked // lists. //********************************************************* void* llist::prev() { llist_node *previous = NULL; // Ptr to previous element // // If current element is head of list, there is no // previous element. Return (0). // if (current == head) return (NULL); // // Now, previous points to head of list. // previous = head; // // Find current. If there is no current, previous // will be NULL at end of while. // while(previous != NULL && previous->next != current) previous = previous->next; // // Make current point to previous element. // current = previous; // // If current is not NULL, return data; // otherwise return NULL. // if (current != NULL) return (current->data); else return (NULL); } // end function (prev)