README.md

*

| MyClass |    | MyClass |    | MyClass |




^          ^          ^



| (pointer to)   |          |



|          |          |



|          |          |





| Internal.|<------>| Internal.|<------>| Internal.|<------> \




*

• This file declares three template classes which operate together to implement
• the class file. Note that these classes should be defined in the same file since
• the C++ 'friend' modifier was used. As a result, the CTL_DoublyLinkedListIterator and the
• RecordInterface classes should be considered to be part of the interface of the
• CTL_DoublyLinkedList, and therefore should be defined in the same file to avoid 'long-distance
• friendships' (as per the literature).
• The following is an example of how to use this template.

• ---

• CTL_DoublyLinkedList list;
• CTL_DoublyLinkedList::Iterator it;
• TestRecord a[10];
• int i;
• // initialize data
• for (i=0; i<10; i++)
• {

•  a[i].data1=i*10;
  

•  a[i].data2=i*100;
  

• }
• list.addRecord( &a[9] );
• list.addRecord( &a[4] );
• list.addRecord( &a[3] );
• list.addRecord( &a[2] );
• list.addRecord( &a[8] );
• printf( "Displaying records: 9,4,3,2,8\n" );
• for (it=list; it(); ++it)

•  printf( "record: %d, %d\n", it()->data1, it()->data2 );
  

• ---

• The following template classes defined in this file:
• CTL_DoublyLinkedList
• CTL_DoublyLinkedList::Iterator / template class CTL_DoublyLinkedList { public: // constructor/destructor CTL_DoublyLinkedList(); ~CTL_DoublyLinkedList(); /* IMPORTANT! The copy iterator will copy the list by allocating new internal nodes * that point to the SAME records that the other list points to. I.E., don't delete * that data unless you remove the record first from both lists. / void operator = ( CTL_DoublyLinkedList& copyList ); /* returns the number of records in the list / int getNumberOfRecords(void); /* returns the requested record in O(n) time / RecordClass getRecord( int recordID ); /** determines if the item is a member of the list / Boolean isElement( RecordClass lprecord ); // ---- list manipulation interface /** * Clears the linked list, resets to an empty list * * This method clears the list to an empty list. The internal * data is deallocated, but the records that the list was * pointing to is not! / void clearList(void); /* adds the record to the list / int addRecord( RecordClass lpRecord ); /** adds the record to the list and ensures there is only one of the elements in the list / void addRecordUnrepeated( RecordClass lpRecord ); /** adds the record to the start of the list / int addRecordToStart( RecordClass lpRecord ); /** adds the record to the end of the list / int addRecordToEnd( RecordClass lpRecord ); /** removes and returns the recordID'th record from the list / RecordClass removeRecord( int recordID ); /** removes the specified record from the list / RecordClass removeRecord( RecordClass* lpRemoveNode ); /** removes the first record from the list / RecordClass removeFirstRecord(void); /** removes the last record from the list / RecordClass removeLastRecord(void); /** moves the specified record up one position in the list / void promoteRecord(RecordClass lpRecordToPromote ); /** moves the specified record down one position in the list / void demoteRecord(RecordClass lpRecordToDemote ); private: struct RecordClassNode { RecordClass* m_lpRecord; RecordClassNode* m_lpNext; RecordClassNode* m_lpPrevious; }; RecordClassNode* m_lpRoot; int m_numberOfRecords; // protected helper functions RecordClassNode* f_getLastRecordNode(void); RecordClassNode* f_getRecordNode( int recordID ); public: /** Iterator class to access elements in the CTL_DoublyLinkedList * * Iterator to access the elements of the CTL_DoublyLinkedList. The following * example shows how to use this class. * *

  * ---------------------------------------------------
  * class MyRecord;
  *	CTL_DoublyLinkedList list;
  *	CTL_DoublyLinkedList::Iterator iter;
  *
  * // ....
  *
  *	for (iter=list; iter(); ++iter)
  *	{
  *   // access iter()
  * }
  * ---------------------------------------------------
  * 

  * / class Iterator { public: Iterator( ) { lpCurrent = NULL; }; / Points the iterator to the first record in the list / inline void operator=(CTL_DoublyLinkedList &src) { lpCurrent = src.m_lpRoot; }; /* Copy the location of another iterator / inline void operator=(Iterator &copyIt) { lpCurrent = copyIt.lpCurrent; }; friend Iterator; /* Moves to the next record / inline void operator++(void) { if (lpCurrent != NULL) lpCurrent = lpCurrent->m_lpNext; }; /* Moves to the previous record / inline void operator--(void) { if (lpCurrent != NULL) lpCurrent = lpCurrent->m_lpPrevious; }; /* Peek at the next record / inline RecordClass peekAtNext(void) { if (lpCurrent != NULL) if (lpCurrent->m_lpNext != NULL) return lpCurrent->m_lpNext->m_lpRecord; return NULL; }; /** Peek at the previous record / inline RecordClass peekAtPrevious(void) { if (lpCurrent != NULL) if (lpCurrent->m_lpPrevious != NULL) return lpCurrent->m_lpPrevious->m_lpRecord; return NULL; }; /** Returns the current record being accessed / inline RecordClass operator()() { if (lpCurrent == NULL) return NULL; return lpCurrent->m_lpRecord; }; /** Clears the content of the iterator / inline void clear() { lpCurrent = NULL; }; protected: RecordClassNode lpCurrent; }; /** allow our iterator class to access our internals / friend void Iterator::operator=(CTL_DoublyLinkedList &src); }; // ------------------------------------------------------- // ---- implementation of the CTL_DoublyLinkedList class // -------------------------------------------------------- // constructor/destructor template CTL_DoublyLinkedList::CTL_DoublyLinkedList() { m_lpRoot = NULL; m_numberOfRecords = 0; } template CTL_DoublyLinkedList::~CTL_DoublyLinkedList() { clearList(); } template CTL_DoublyLinkedList::RecordClassNode CTL_DoublyLinkedList::f_getLastRecordNode(void) { int nodeCounter = 0; RecordClassNode* lpRecordNode = m_lpRoot; if (m_lpRoot == NULL) return NULL; while (lpRecordNode->m_lpNext != NULL) { nodeCounter++; lpRecordNode = lpRecordNode->m_lpNext; } // do an error checking here if (m_numberOfRecords != nodeCounter+1) { m_numberOfRecords = nodeCounter+1; fprintf(stderr, "WARNING! CTL_DoublyLinkedList has lost count!\n"); } return lpRecordNode; } // record access interface template int CTL_DoublyLinkedList::getNumberOfRecords(void) { return m_numberOfRecords; } template void CTL_DoublyLinkedList::operator = ( CTL_DoublyLinkedList& copyList ) { Iterator it; clearList(); for (it = copyList; it(); ++it) { addRecordToEnd( it() ); } } template CTL_DoublyLinkedList::RecordClassNode CTL_DoublyLinkedList::f_getRecordNode( int recordID ) { if (recordID <= 0) { if (m_lpRoot == NULL) return NULL; return m_lpRoot; } else if (recordID > m_numberOfRecords-1) return NULL; int nodeCounter = 0; RecordClassNode lpRecordNode = m_lpRoot; while (nodeCounter < recordID && lpRecordNode != NULL) { nodeCounter++; lpRecordNode = lpRecordNode->m_lpNext; } // error checking if (lpRecordNode == NULL) { fprintf(stderr, "WARNING!- SFC Library\n Class CTL_DoublyLinkedList (a linked-list structure) has lost count of its list.\n"); m_numberOfRecords = nodeCounter; } return lpRecordNode; } template RecordClass CTL_DoublyLinkedList::getRecord( int recordID ) { RecordClassNode lpNode = f_getRecordNode(recordID); if (lpNode == NULL) return NULL; else return lpNode->m_lpRecord; } template Boolean CTL_DoublyLinkedList::isElement( RecordClass lpRecord ) { RecordClassNode lpNode = m_lpRoot; while (lpNode != NULL) { if (lpRecord == lpNode->m_lpRecord) return TRUE; lpNode = lpNode->m_lpNext; } return FALSE; } // list manipulation interface template void CTL_DoublyLinkedList::clearList( void ) { while( removeFirstRecord() ) { } } template void CTL_DoublyLinkedList::addRecordUnrepeated( RecordClass lpRecord ) { if (lpRecord == NULL) return; // remove existing copies RecordClassNode lpNode = m_lpRoot; Boolean alreadyExists = FALSE; while (lpNode != NULL) { if (lpNode->m_lpRecord == lpRecord) { if (alreadyExists==TRUE) { // we already found an occurance- lets delete this one removeRecord(lpNode->m_lpRecord); // must be a better way to do this, but lets go ahead and reset to the beginning // of the list and try again alreadyExists = FALSE; lpNode = m_lpRoot; } else { alreadyExists = TRUE; lpNode = lpNode->m_lpNext; } } else lpNode = lpNode->m_lpNext; } // did we find it? If not, then add it if (alreadyExists == FALSE) addRecordToStart(lpRecord); } template int CTL_DoublyLinkedList::addRecord( RecordClass lpRecord ) { return addRecordToEnd(lpRecord); } template int CTL_DoublyLinkedList::addRecordToStart( RecordClass* lpRecord ) { if (lpRecord == NULL) return -1; // create node for record RecordClassNode* lpNode = new RecordClassNode; lpNode->m_lpRecord = lpRecord; // add to the beginning lpNode->m_lpNext = m_lpRoot; lpNode->m_lpPrevious = NULL; if ( m_lpRoot != NULL ) { m_lpRoot->m_lpPrevious = lpNode; } m_lpRoot = lpNode; m_numberOfRecords++; return 0; } template int CTL_DoublyLinkedList::addRecordToEnd( RecordClass* lpRecord ) { if (lpRecord == NULL) return -1; if (m_lpRoot == NULL) return addRecordToStart(lpRecord); else { // create a new record struct RecordClassNode* lpStruct = new RecordClassNode; lpStruct->m_lpRecord = lpRecord; // get last record node RecordClassNode lpInsertPtr = f_getLastRecordNode(); // insert after last node lpInsertPtr->m_lpNext = lpStruct; lpStruct->m_lpPrevious = lpInsertPtr; lpStruct->m_lpNext = NULL; m_numberOfRecords++; } return m_numberOfRecords-1; } template RecordClass CTL_DoublyLinkedList::removeRecord( int recordID ) { if (m_lpRoot == NULL) return NULL; if (recordID <= 0 || m_numberOfRecords == 1) return removeFirstRecord(); else { // removing node is neither the first nor the last item // get the node before and after the item to be removed RecordClass* lpRemovedRecord; RecordClassNode* lpPreviousNode = f_getRecordNode(recordID-1); if (lpPreviousNode == NULL) return NULL; RecordClassNode* lpNode = lpPreviousNode->m_lpNext; if (lpNode == NULL) return NULL; RecordClassNode* lpNextNode = f_getRecordNode(recordID+1); // remove lpNode lpPreviousNode->m_lpNext = lpNextNode; if (lpNextNode != NULL) { lpNextNode->m_lpPrevious = lpPreviousNode; } // reset the node lpRemovedRecord = lpNode->m_lpRecord; delete lpNode; // update count m_numberOfRecords--; // return the removed node return lpRemovedRecord; } } template RecordClass* CTL_DoublyLinkedList::removeRecord( RecordClass* lpRemoveRecord ) { if (lpRemoveRecord == NULL || m_lpRoot == NULL) return NULL; // find the remove record node RecordClassNode* lpRemoveNode = m_lpRoot; while (lpRemoveNode != NULL) { if (lpRemoveNode->m_lpRecord != lpRemoveRecord) lpRemoveNode = lpRemoveNode->m_lpNext; else break; } if (lpRemoveNode == NULL) return NULL; // set the next and previous RecordClassNode* lpPrevious = lpRemoveNode->m_lpPrevious; RecordClassNode* lpNext = lpRemoveNode->m_lpNext; if (lpPrevious != NULL) lpPrevious->m_lpNext = lpNext; else m_lpRoot = lpNext; if (lpNext != NULL) lpNext->m_lpPrevious = lpPrevious; // delete the node delete lpRemoveNode; m_numberOfRecords--; return lpRemoveRecord; } template RecordClass* CTL_DoublyLinkedList::removeFirstRecord(void) { if (m_lpRoot != NULL) { RecordClass* lpRemoveRecord; RecordClassNode* lpRemoveNode = m_lpRoot; m_lpRoot = m_lpRoot->m_lpNext; if (m_lpRoot != NULL) m_lpRoot->m_lpPrevious = NULL; // reset the node lpRemoveRecord = lpRemoveNode->m_lpRecord; delete lpRemoveNode; m_numberOfRecords--; return lpRemoveRecord; } return NULL; } template RecordClass* CTL_DoublyLinkedList::removeLastRecord(void) { return removeRecord( m_numberOfRecords-1 ); } template void CTL_DoublyLinkedList::promoteRecord(RecordClass* lpRecordToPromote) { // if there is only 1 node, or no nodes, do nothing if (m_lpRoot == NULL || lpRecordToPromote == NULL || m_numberOfRecords <= 1) return; // find this record's node RecordClassNode* lpNodeToPromote = m_lpRoot; while (lpNodeToPromote != NULL) { if (lpNodeToPromote->m_lpRecord == lpRecordToPromote) break; else lpNodeToPromote = lpNodeToPromote->m_lpNext; } if (lpNodeToPromote== NULL) return; // if first item, do nothing if (lpNodeToPromote->m_lpPrevious == NULL) return; // get pointers to the nodes RecordClassNode* lpNode = lpNodeToPromote; RecordClassNode* lpPreviousNode = lpNode->m_lpPrevious; RecordClassNode* lpNextNode = lpNode->m_lpNext; // extract item from list lpPreviousNode->m_lpNext = lpNextNode; if (lpNextNode != NULL) lpNextNode->m_lpPrevious = lpPreviousNode; // insert before the previous node lpNode->m_lpPrevious = lpPreviousNode->m_lpPrevious; lpNode->m_lpNext = lpPreviousNode; lpPreviousNode->m_lpPrevious= lpNode; if (lpNode->m_lpPrevious != NULL) lpNode->m_lpPrevious->m_lpNext = lpNode; else m_lpRoot = lpNode; } template void CTL_DoublyLinkedList::demoteRecord(RecordClass* lpRecordToDemote) { // if there is only 1 node, or no nodes, do nothing if (m_lpRoot == NULL || lpRecordToDemote == NULL || m_numberOfRecords <= 1) return; // find this record's node RecordClassNode* lpNodeToDemote = m_lpRoot; while (lpNodeToDemote != NULL) { if (lpNodeToDemote->m_lpRecord == lpRecordToDemote) break; else lpNodeToDemote = lpNodeToDemote->m_lpNext; } if (lpNodeToDemote== NULL) return; // if last item, do nothing if (lpNodeToDemote->m_lpNext == NULL) return; // get pointers to the nodes RecordClassNode* lpNode = lpNodeToDemote; RecordClassNode* lpPreviousNode = lpNode->m_lpPrevious; RecordClassNode* lpNextNode = lpNode->m_lpNext; // extract item from list lpNextNode->m_lpPrevious = lpPreviousNode; if (lpPreviousNode == NULL) m_lpRoot = lpNextNode; else lpPreviousNode->m_lpNext = lpNextNode; // insert after the next node lpNode->m_lpPrevious = lpNextNode; lpNode->m_lpNext = lpNextNode->m_lpNext; lpNextNode->m_lpNext = lpNode; if (lpNode->m_lpNext != NULL) lpNode->m_lpNext->m_lpPrevious = lpNode; } #endif