Quad tree search list.cc
Revision as of 20:41, 3 July 2016 by Maintenance script (talk)
// 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.cpp #ifndef LIST_CPP #define LIST_CPP #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 node { L ListData; node *next, *previous; }; node *first, *current, *last; unsigned int m_ulPopulation; unsigned int Counter_unsigned_int; friend istream& operator >> (istream &IS , List<L> &A); friend ostream& operator << (ostream &OS , List<L>& A ); public: bool offEOL () { return (current == NULL); } // offEOL bool push_front( L d ) { // case 1. List is empty if( empty() ) { node *newnode = new node; if (newnode == NULL) return false; newnode->next = NULL; newnode->previous = NULL; newnode->ListData = d; first = newnode; current = newnode; last = newnode; m_ulPopulation++; return true; } // case 2. one or more nodes in the List if( first->ListData < d ) return push_back( d ); node *newnode = new node; if (newnode == NULL) return false; newnode->next = NULL; newnode->previous = NULL; newnode->ListData = d; first->previous = newnode; newnode->next = first; current = newnode; first = newnode; m_ulPopulation++; return true; } // push_front bool push_current( L d ) { // case 1. List is empty if( size() == 0 ) return push_front( d ); if( offEOL() ) return push_back( d ); // case 2. one node in List if( size() == 1 ) { // case 2.1 new node is less if( first->ListData > d ) return push_front( d ); // case 2.2 new node is greater if( first->ListData < d ) return push_back( d ); } // case 3. two or more nodes. push BEFORE current if( current == NULL ) return push_back( d ); node *newnode = new node; if (newnode == NULL) return 0; node *Prev = current->previous; newnode->ListData = d; newnode->next = current; newnode->previous = Prev; Prev->next = newnode; current->previous = newnode; m_ulPopulation++; return true; } // bool push_back( L d ) { // case 1. no nodes in the List. if( size() == 0 ) { node *newnode = new node; if (newnode == NULL) return false; newnode->next = NULL; newnode->previous = NULL; newnode->ListData = d; first = newnode; current = newnode; last = newnode; m_ulPopulation++; return true; } // case 2. one node in the List if( size() >= 1 ) { node *newnode = new node; if (newnode == NULL) return false; newnode->next = NULL; newnode->previous = last; newnode->ListData = d; last->next = newnode; current = newnode; last = newnode; m_ulPopulation++; return true; } return false; } // push_back bool pop_back() { if (last == NULL) return false; if( last == first ) { delete last; first = NULL; current = NULL; last = NULL; m_ulPopulation--; return true; } current = last->previous; current->next = NULL; delete last; last = current; begin(); m_ulPopulation--; return true; } bool pop_front() { if (first == NULL) return false; begin(); first = current->next; if (first != NULL) first->previous = NULL; if (last == current) last = NULL; delete current; begin(); m_ulPopulation--; return true; } void begin() { current = first; } void end() { current = last; } void next() { if( current != NULL ) current = current->next; } void previous () { if( current != NULL ) current = current->previous; } bool pop_current() { if(current == NULL) return false; if( current == first ) return pop_front(); if( current == last ) return pop_back(); current->previous->next = current->next; current->next->previous = current->previous; delete current; begin(); m_ulPopulation--; return true; } List() { first = current = last = NULL; m_ulPopulation = 0; Counter_unsigned_int = 0; } List( const List<L> &P ) // copy List P to List *this { if (P.first) { first = new node; first->ListData = P.first->ListData; first->next = NULL; first->previous = NULL; current = first; node *currL = P.first->next; while (currL) { current->next = new node; current->previous = current; current = current->next; current->ListData = currL->ListData; current->next = NULL; currL = currL->next; } last = current; } else { first = NULL; current = NULL; last = NULL; } m_ulPopulation = P.m_ulPopulation; Counter_unsigned_int = P.Counter_unsigned_int; } ~List() // deletes and frees List nodes from first to last { while (first) { node *ptr = first; first = first ->next; delete ptr; } first = NULL; last = NULL; current = NULL; m_ulPopulation = 0; } List<L> operator = ( const List<L> &P ) { if( P.first ) { erase(); first = new node; first->ListData = P.first->ListData; first->next = NULL; first->previous = NULL; current = first; node *currL = P.first->next; while( currL ) { current->next = new node; current->previous = current; current = current->next; current->ListData = currL->ListData; current->next = NULL; currL = currL->next; } last = current; } else { first = NULL; current = NULL; last = NULL; } m_ulPopulation = P.m_ulPopulation; Counter_unsigned_int = P.Counter_unsigned_int; return *this; } // = List<L> operator += ( List<L> P ) { node *currL = P.first; while( currL ) { AddToList( currL->ListData ); currL = currL->next; } return *this; } List<L> operator += ( L d) { if ( !find( d ) ) AddToList( d ); return *this; } int operator -= ( List<L> &D ) { D.begin(); int hold_population = D.size(); while ( !D.offEOL() ) { if( *this -= D.current->ListData) { hold_population--; } D.next(); } return (hold_population == 0); } bool operator -= ( L d ) { if (find( d )) { if (current == first) return pop_front(); else if (current == last) return pop_back(); else return pop_current(); } return false; } bool operator==( List<L>& List2 ) { unsigned int i_List1size = size(); unsigned int i_List2size = List2.size(); if (i_List1size != i_List2size) return 0; while( i_List1size >= 0 ) { L Temp1; L Temp2; getcurrent(Temp1); List2.getcurrent(Temp2); if (Temp2 != Temp1) return 0; next(); List2.next(); } return true; } bool AddToList( L d ) { if( find( d ) ) return false; // d > first if( current == first ) return push_front( d ); if( offEOL() ) return push_back( d ); return push_current( d ); } unsigned int size() { // if( Counter_unsigned_int > 0 && // Counter_unsigned_int < m_ulPopulation ) // Counter_unsigned_int++; // else // Counter_unsigned_int = 0; return m_ulPopulation; } void erase() { while( first ) pop_front(); } bool empty () { return (first == NULL); } bool find( L K ) { begin(); while ( current != NULL ) { if ( current->ListData == K ) return true; if ( current->ListData > K ) return false; next(); } return false; } // find int findnum( const L &K ) { int i_ReturnCount = 0; node *p_Temp = NULL; begin(); if ( !empty() ) { while ( !offEOL() ) { if ( current->ListData == K ) { i_ReturnCount++; p_Temp = current; } next(); } } current = p_Temp; return i_ReturnCount; } // findnum L* getcurrent () { if (current != NULL) return ¤t->ListData; return NULL; } bool getcurrent ( L &d ) { if (current != NULL) { d = current->ListData; return true; } return false; } int setcurrent ( L d ) { if (current != NULL) { current->ListData = d; return 1; } return 0; } L* front ( ) { if (first != NULL) return &first->ListData; else return NULL; } L* back() { if (last != NULL) return &last->ListData; return NULL; } void OutPut() { begin(); for( int i = 0; i < size(); i++ ) { getcurrent()->OutPut(); next(); } } }; 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.begin(); for( int i = 0; i < A.size(); i++ ) { OS << A.getcurrent(); A.next(); } return OS; } #endif // LIST_CPP