List
// list.cc // Jesse B. Dooley // 28 May 1996 // template double linked list class // The following overloaded operators are // assumed for the L data type. // < less than // > greater than // == equals // << output stream // >> input stream // = assignment // list.cc #ifndef LIST_CC #define LIST_CC #include <iostream.h> // UNIX // prototype class template <class L> class list; // prototype input function template <class L> istream& operator >> (istream&, list<L>&); // prototype output function template <class L> ostream& operator << (ostream&, list<L>& ); template<class L> class list { struct listnode { L ListData; listnode *next, *previous; }; listnode *first, *current, *last; unsigned long m_ulPopulation; friend istream& operator >> (istream &IS , list<L> &A); friend ostream& operator << (ostream &OS , list<L>& A ); int crown( L d ) { listnode *newnode = new listnode; if (newnode == NULL) return 0; newnode->next = first; newnode->previous = NULL; newnode->ListData = d; if (first != NULL) first->previous = newnode; if (last == NULL) last = newnode; current = first = newnode; m_ulPopulation++; return 1; } int cuttail() { if (last == NULL) return 0; current = last->previous; current->next = NULL; delete last; last = current; getfirst(); m_ulPopulation--; return 1; } int decapitate() { if (first == NULL) return 0; getfirst(); first = current->next; if (first != NULL) first->previous = NULL; if (last == current) last = NULL; delete current; getfirst(); m_ulPopulation--; return 1; } void getfirst () { current = first; } void getlast () { current = last; } int getnext () { if (current) { current = current->next; return 1; } return 0; } int getprevious () { if (current->previous) { current = current->previous; return 1; } return 0; } int gut() { if ((current->next == NULL) || (current->previous == NULL)) return 0; current->previous->next = current->next; current->next->previous = current->previous; delete current; getfirst(); m_ulPopulation--; return 1; } int offEOL () { return (current == NULL); } // offEOL int pintogut( L &d ) { listnode *newnode = new listnode; if (newnode == NULL) return 0; newnode->ListData = d; newnode->next = current->next; newnode->previous = current; current->next->previous = newnode; current->next = newnode; m_ulPopulation++; return 1; } int pintotail( L &d ) { listnode *newnode = new listnode; if (newnode == NULL) return 0; newnode->next = NULL; newnode->previous = last; newnode->ListData = d; last->next = newnode; last = newnode; m_ulPopulation++; return 1; } public: list() // first = current = last = 0, m_population = 0 { first = current = last = NULL; m_ulPopulation = 0; } list( const list<L> &P ) // copy list P to list *this { if (P.first) { first = new listnode; first->ListData = P.first->ListData; first->next = NULL; first->previous = NULL; current = first; listnode *currL = P.first->next; while (currL) { current->next = new listnode; current->previous = current; current = current->next; current->ListData = currL->ListData; current->next = NULL; currL = currL->next; } last = current; } else first = current = last = NULL; m_ulPopulation = P.m_ulPopulation; } ~list() // deletes and frees list nodes from first to last { while (first) { listnode *ptr = first; first = first ->next; delete ptr; } first = last = current = NULL; } list<L> operator = ( const list<L> &P ) { if( P.first ) { erase(); first = new listnode; first->ListData = P.first->ListData; first->next = NULL; first->previous = NULL; current = first; listnode *currL = P.first->next; while( currL ) { current->next = new listnode; current->previous = current; current = current->next; current->ListData = currL->ListData; current->next = NULL; currL = currL->next; } last = current; } else { first = current = last = NULL; } m_ulPopulation = P.m_ulPopulation; return *this; } // = int operator += ( list<L> &d) { d.getfirst(); unsigned long lhold_population = d.census(); while ( !d.offEOL() ) { if ( *this += d.current->ListData ) { lhold_population--; } else return 0; d.getnext(); } return (lhold_population == 0); } int operator += ( L d) { if ( !locate( d ) ) { if( current && current->ListData < d) { return pintogut( d ); } else if ( current == first ) { return crown( d ); } else { if ( offEOL() ) return pintotail( d ); else return pintogut( d ); } } return 0; } int operator -= ( list<L> &D ) { D.getfirst(); int hold_population = D.census(); while ( !D.offEOL() ) { if( *this -= D.current->ListData) { hold_population--; } D.getnext(); } return (hold_population == 0); } int operator -= ( L d ) { if (locate( d )) { if (current == first) return decapitate(); else if (current == last) return cuttail(); else return gut(); } return 0; } int operator==( list<L>& list2 ) { unsigned long i_list1census = census(); unsigned long i_list2census = list2.census(); if (i_list1census != i_list2census) return 0; while( i_list1census >= 0 ) { L Temp1; L Temp2; returncurrent(Temp1); list2.returncurrent(Temp2); if (Temp2 != Temp1) return 0; getnext(); list2.getnext(); } return 1; } int AddToList( L d) { locate( d ); if( current && current->ListData < d) { return pintogut( d ); } else if ( current == first ) { return crown( d ); } else { if ( offEOL() ) return pintotail( d ); else return pintogut( d ); } return 0; } unsigned long census() { return m_ulPopulation; } void erase() { while (current) { decapitate(); } } int isempty () { return (first == NULL); } int locate( const L &K ) { int i_ReturnCount = 0; getfirst(); if ( !isempty() ) { while ( !offEOL() ) { i_ReturnCount++; if ( current->ListData == K ) return i_ReturnCount; if ( current->ListData > K ) { getprevious(); return 0; } getnext(); } } return 0; } // locate int locatenum( const L &K ) { int i_ReturnCount = 0; listnode *p_Temp = NULL; getfirst(); if ( !isempty() ) { while ( !offEOL() ) { if ( current->ListData == K ) { i_ReturnCount++; p_Temp = current; } getnext(); } } current = p_Temp; return i_ReturnCount; } // locatenum L* returncurrent () { if (current != NULL) { return ¤t->ListData; } return NULL; } int returncurrent ( L &d ) { if (current != NULL) { d = current->ListData; return 1; } return 0; } L* returnfirst ( ) { return &first->ListData; } int returnfirst ( L &d ) { if (first != NULL) { d = first->ListData; return 1; } return 0; } L* returnlast ( ) { if (last != NULL) { return &last->ListData; } return NULL; } int returnlast ( L &d ) { if (last != NULL) { d = last->ListData; return 1; } return 0; } }; template <class L> istream& operator >> (istream &IS , list<L> &A) { if( IS ) { L D; IS >> D; A += D; } return IS; } template <class L> ostream& operator << (ostream &OS , list<L>& A ) { A.getfirst(); while ( !A.offEOL() ) { OS << A.returncurrent(); A.getnext(); } return OS; } #endif // LIST_CC
Internal Links
Parent Article: Programming Portfolio