// templateClassList2.cpp
// this version: 2018-04-13
// template class List with 'merge sort' and 'insert sort'
// has private class members: 'pFront', 'pRear' and 'size'
// and public copy constructor and overloaded assignment operator
#include <iostream>
#include <fstream>
#define haveFile true
// FILE NAME: int.dat //
/*
1492
1776
1860
-23
1698
1935
1926
1953
1960
1492
1776
1860
-23
1698
2000
1935
1926
1953
1960
-47
*/
using namespace std;
template< typename T >
class List
{
public:
List();
~List();
List( const List <T> & obj ) // inline copy constructor ...
{
pFront = pRear = 0;
len = 0;
for( Node* p = obj.pFront; p; p = p->next )
push_back( p->data );
is_sorted = obj.is_sorted;
}
List& operator = ( const List <T> & obj ) // inline overloaded assignment
{
// return if lists are already the same list ...
if( this == &obj ) return *this;
// ok ... not same ... so ...
if( len ) clear(); // sets ...pFront=pRear=0; size=0; is_sorted=true
else {
pFront = pRear = 0;
len = 0;
}
// now ...
for( Node* p = obj.pFront; p; p = p->next )
push_back( p->data );
is_sorted = obj.is_sorted;
return *this;
}
void push_front( const T& e );
void push_back( const T& e );
void add_at_index( size_t c, const T& e );
void remove( const T& e );
void print() const;
bool exist( const T& e ) const;
size_t size() const;
T max() const;
T min() const;
// insert new element e in sorted order into a sorted list ...
void isort_insert( const T& e );
void isort(); // insert-sort the whole list in place ...
void update_pRear()
{
pRear = pFront;
while( pRear->next != 0 ) pRear = pRear->next;
}
// merge sort the whole list in place (a 'divide and sort' recursive sort)
void msort()
{
Node* p = pFront;
merge_sort( p, len ); // p is updated in recursion using pass by ref.
set_pFront_pRear( p );
is_sorted = true;
}
void remove_duplicates()
{
if( len <= 1 ) return;
if( !is_sorted ) msort();
Node* p = pFront;
while( p->next != 0 )
{
if( p->data == p->next->data )
{
Node* tmp = p->next;
p->next = p->next->next;
delete tmp;
-- len;
}
else p = p->next; // move up one ...
}
update_pRear();
}
private:
struct Node
{
T data;
Node* next;
} *pFront, *pRear;
size_t len; // number of list nodes
bool is_sorted;
void clear()
{
if( !len ) return;
for( Node* q = pFront; q; pFront = q )
{
q = pFront->next;
delete pFront;
}
pRear = 0; // Note: pFront is set to 0 above on last for loop
len = 0;
is_sorted = true;
}
void insert_sorted( Node*& pHead, Node* pNewNode );
void merge_sort( Node*& pFront, size_t size ); // returns updated pFront by ref.
// merge two sorted lists with heads 'a' and 'b' ... in sorted order
Node* merge( Node* a, Node* b )
{
if( !a ) return b;
if( !b ) return a;
Node* sorted; // now get appropriate new head for merged list
if( a->data <= b->data )
{
sorted = a;
a = a->next;
}
else
{
sorted = b;
b = b->next;
}
Node* new_merged_head = sorted;
// now merge lists ...
while( a && b )
{
if( a->data <= b->data )
{
sorted->next = a;
sorted = sorted->next;
a = a->next;
}
else
{
sorted->next = b;
sorted = sorted->next;
b = b->next;
}
}
// now ... append the ONE part that might have been left-over above ...
if( a )
sorted->next = a;
else // b //
sorted->next = b;
return new_merged_head;
}
void set_pFront_pRear(Node* p) {
pFront = p;
update_pRear();
}
};
// definitions ...
template< typename T >
List<T>::List()
{
pFront = pRear = 0;
len = 0;
is_sorted = true;
}
template< typename T >
List<T>::~List()
{
clear();
}
template< typename T >
void List<T>::push_front( const T& e ) // inserts e with type T at front of List
{
Node* n = new Node;
n->data = e;
n->next = pFront;
pFront = n;
if( !len ) pRear = pFront;
++len;
is_sorted = false;
}
template< typename T >
void List<T>::push_back( const T& e ) // inserts e with type T at end of List
{
Node* n = new Node;
n->data = e;
n->next = 0;
if( len )
{
pRear->next = n;
pRear = n;
}
else
pRear = pFront = n;
++len;
is_sorted = false;
}
template< typename T >
void List<T>::add_at_index( size_t c, const T& e) // inserts e with type T at index c
{
if( c < len )
{
if( c > 0 )
{
// insert at index c ... BUT after index 0 ... i.e. at 1 to size
Node* prev = pFront;
for( size_t i = 1; i < c; ++ i ) prev = prev->next;
Node* n = new Node;
n->data = e;
// now insert n at index c ... A -> B becomes A->C->B
n->next = prev->next; // C -> B
prev->next = n; // A -> C
++ len;
is_sorted = false;
} // here c is 0 ... so ...
else push_front( e ); // resets size, pFront and pRear ... as applicable
}
else if( c == len ) push_back( e );
else
{
cout << "\nHighest new index allowed is " << len
<< ". You requested index " << c << " ... push_back y/n ? ";
string reply;
getline( cin, reply );
if( reply == "n" || reply == "N" )
return;
// if reach hear ...
cout << "Ok ... will push_back ...\n";
push_back( e ); // resets size, pFront and pRear ... as applicable
}
}
template< typename T >
void List<T>::remove( const T& e )
{
if( !len )
{
cout << "\nCan not remove '" << e << "' since list is empty.\n";
return;
}
Node* q = pFront;
if( q->data == e ) // if at front ...
{
pFront = q->next;
delete q;
--len;
cout<<"\n'" << e <<"' removed ...";
if( len <= 1 ) {
pRear = pFront;
is_sorted = true;
}
return;
}
// if reach here ... 'e' is NOT the first
Node* prev = q;
q = q->next; // q now points to 2nd node in list ...
while( q ) // Note: also handles case of just one Node in list
{
if( q->data == e )
{
prev->next = q->next;
delete q;
cout<<"\n'" << e <<"' removed ...";
--len;
if( len == 1 ) {
pRear = prev;
is_sorted = true;
}
return;
}
// if reach here ... advance both nodes up the list ...
prev = q;
q = q->next;
}
cout<<"\n'" << e <<"' NOT found ...";
}
template< typename T >
void List<T>::print() const
{
for( Node* q = pFront; q; q = q->next )
cout << ' ' << q->data;
}
template< typename T >
bool List<T>::exist( const T& e ) const
{
for( Node* q = pFront; q; q = q->next )
if( q->data == e )
return true;
return false;
}
template< typename T >
size_t List<T>::size() const
{
return len;
}
template< typename T >
T List<T>::max() const
{
if( !len )
{
cout << "List is empty ... returning 'zero' ... ";
return T(0);
}
T max = pFront->data;
for( Node* q = pFront; q->next; q = q->next )
if( q->next->data > max )
max = q->next->data;
return max;
}
template< typename T >
T List<T>::min() const
{
if( !len )
{
cout << "List is empty ... returning 'zero' ... ";
return T(0);
}
T min = pFront->data;
for( Node* q = pFront; q->next; q = q->next )
if( q->next->data < min )
min = q->next->data;
return min;
}
//////////////////////////////// BEGIN MERGE SORT //////////////////////////////
// divide list into two halves and then recursively sort each half ...
// then merge the two sorted halves using the above merge function
// Note: calling 'pFront' is updated by using 'pass by ref'
template< typename T >
void List<T>::merge_sort( Node*& pFront, size_t size )
{
if( size <= 1 ) return;
Node* pHead2;
Node* pEnd1;
size_t size2 = size/2;
size_t size1 = size - size2;
// split the list into two lists ... the first half begins with pHead
pEnd1 = pFront; // first set pEnd1 to the head address ...
for( size_t i = 1; i < size1; ++ i )
pEnd1 = pEnd1->next;
pHead2 = pEnd1->next; // second half begins with pHead2
pEnd1->next = 0; // breaking the chain here... so we can have two lists
// merge the lists after recusively merge_sorting them
merge_sort( pFront, size1 );
merge_sort( pHead2, size2 );
pFront = merge( pFront, pHead2 );
}//////////////////////////////// END MERGE SORT ///////////////////////////////
/////////////////////////////////// BEGIN ISORT ////////////////////////////////
// does NOT update pRear ... so must call update_pRear() when all inserts done.
template< typename T >
void List<T>::isort_insert( const T& e )
{
Node* n = new Node;
n->data = e;
n->next = 0;
if( len > 1 && !is_sorted ) msort();
insert_sorted( pFront, n );
++ len;
}
// insert a new node in a list with its node data in proper order ... does NOT
// update size or pRear ... so must call update_pRear() when all inserts done.
template< typename T >
void List<T>::insert_sorted( Node*& pHead, Node* pNewNode )
{
// First ... handle case where new node should be first element
if( !pHead || pNewNode->data < pHead->data )
{
// It now becomes the first element
pNewNode->next = pHead; // old pHead becomes 2nd in list
pHead = pNewNode; // and this new node becomes the head of the list
}
else // If here ... search the nexted list for the right location
{
Node* q = pHead; // Get a working copy of pHead in q
// Start comparing with element AFTER 'q' ... i.e. the 'next in'
while( q->next && q->next->data <= pNewNode->data )
{
q = q->next; // Traverse the list ...
}
// Ok, insert after 'q' by 're-nexting' the pointers
// ( Includes inserting at end position ... where q->next == 0 )
// for A->B to become A->N->B ...
pNewNode->next = q->next; // first insert/link ... N->B
q->next = pNewNode; // and now link ... A->N
}
}
// insert sort a whole list ...
template< typename T >
void List<T>::isort()
{
// Note: pNewHead MUST be 0 to start ...
Node *pTmp, *pHead = pFront, *pNewHead = 0;
while( pHead ) // take each node from old list and insert in new
{
pTmp = pHead; // get 'this' node ...
pHead = pHead->next; // move 'start' up one, to be ready for next node
insert_sorted( pNewHead, pTmp ); // insert 'this' pTmp node
}
set_pFront_pRear( pNewHead );
is_sorted = true;
} ///////////////////////////////// END ISORT //////////////////////////////////
// used in main ...
void pause()
{
cout << "\n\nPress 'Enter' to continue ... ";
string line;
getline( cin, line );
}
int main() //////////////////// MAIN ///////////////////////////////
{
List <int> ml; // construct an empty list to hold int's
ml.remove(1);
cout<<"Number of elements = "<<ml.size();
ml.print();
cout << "\nml.max() = ";
cout << ml.max();
cout << "\nml.min() = ";
cout << ml.max();
cout << "\n\nAfter push_back(...) 's ...";
ml.push_back(3);
ml.push_back(2);
ml.push_back(1);
ml.push_back(6);
ml.push_back(5);
ml.push_back(4);
cout<<"\n'6' is in the list = " <<(ml.exist(6) ? "True." : "False.");
cout<<"\n'22' is in the list = " <<(ml.exist(22) ? "True." : "False.");
cout << "\nml.max() = ";
cout << ml.max();
cout << "\nml.min() = ";
cout << ml.max();
ml.print();
cout<<"\nNumber of elements = "<<ml.size();
pause();
ml.add_at_index(0,0);
ml.push_back(7);
ml.print();
cout<<"\nNumber of elements = "<<ml.size();
pause();
ml.add_at_index(8,8);
ml.print();
cout<<"\nNumber of elements = "<<ml.size();
pause();
ml.add_at_index(9,9);
ml.add_at_index(10,10);
ml.print();
cout<<"\nNumber of elements = "<<ml.size();
pause();
// before isort ... get a copy ...
List <int> mlcopy( ml );
ml.isort();
ml.print();
cout<<"\nNumber of (isort sorted) elements = "<<ml.size();
pause();
cout << "\nEnlarged mlcopy (before msort) ... ";
mlcopy.push_front(10);
mlcopy.push_front(44);
mlcopy.push_front(10);
mlcopy.push_front(44);
mlcopy.print();
cout<<"\nNumber of elements = "<<mlcopy.size();
pause();
mlcopy.msort();
mlcopy.print();
cout<<"\nNumber of (msort sorted) elements = "<<mlcopy.size();
pause();
mlcopy.remove_duplicates();
cout << "\nAfter mlcopy.remove_duplicates() ...";
mlcopy.print();
cout<<"\nNumber of elements = "<<mlcopy.size();
pause();
cout << "\nNow returning to original list ... ml.print() ...";
ml.print();
cout<<"\nNumber of elements = "<<ml.size();
pause();
ml.remove(4); // now back to ml (original ...)
ml.remove(3);
ml.remove(5);
ml.remove(66);
ml.remove(0);
ml.remove(10);
ml.print();
cout<<"\nNumber of elements = "<<ml.size();
pause();
List < int > asn = ml;
cout << "\nAfter List < int > asn = ml ...";
asn.print();
cout<<"\nAnd ... asn.length() = " << asn.size();
pause();
# if haveFile
//=============================================================//
cout << "\n\nNOW reading file \"int.dat\" ... \n";
List < int > list; // construct a new empty list 'list' to hold int's ...
ifstream fin("int.dat");
int x;
cout<< "\nA new list of unique elements from file, "
<< "using list.isort_insert(x) \n";
while( fin >> x )
{
if(!list.exist(x))
list.isort_insert(x);
}
list.update_pRear(); // RECALL: *MUST* update pRear when all insertions done
list.print();
cout << "\nNumber of elements = "<<list.size();
pause();
list.isort_insert(1492);
list.update_pRear(); // RECALL: *MUST* update pRear when all insertions done
cout << "\n\nAfter list.isort_insert(1492) \n";
list.print();
cout << "\nNumber of elements = "<<list.size();
pause();
list.remove(-47);
list.remove(-23);
while( list.exist(1492) ) list.remove(1492);
list.remove(-1);
if( list.exist(-2) ) list.remove(-2);
list.remove(1926);
list.remove(1935);
cout << "\nList Max = " << list.max();
cout << "\nList Min = " << list.min();
cout << "\n\n";
list.print();
cout << "\nNumber of elements = "<<list.size();
pause();
#endif
} ///////////////////////// END MAIN ////////////////////////////
// List2IterNode_h_test.cpp // this version 2010-10-15 //
#include <fstream>
//#include <string>
#include <ctime> // re. clock ...
// defaults to testing file "List1IterNode.h"
#define link2 false // change 'false' to 'true' to test file "List2IterNode.h"
#define do_part1 true // change 'true' to 'false' to skip file test in 'part1'
#if link2
#define links "double-link linked list"
#include "List2IterNode.h"
// includes <iostream>, <string>, <cstdlib>, using namespace std; and myAssert
#else
#define links "single-link linked list"
#define insert_before insert
#include "List1IterNode.h"
// includes <iostream>, <string>, <cstdlib>, using namespace std; and myAssert
#endif
// above ListxIterNode.h includes ...
/*
#include <iostream>
#include <string>
#include <cstdlib> // re. exit ...
using namespace std;
*/
const char DATAFILE[] = "randInt3M.txt";
bool fillFromFile( List< int >& il )
{
ifstream fin( DATAFILE );
if( !fin ) return false;
int tmp;
while( fin >> tmp ) il.push_back( tmp );
fin.close();
return true;
}
#if link2
bool writeFile( const List< int >& il )
{
ofstream fout( "randInt3M_rev_sorted.txt" );
if( !fout ) return false;
for( Iter< int > pos = il.end(); pos != il.begin(); )
fout << *--pos << "\n";
return true;
}
#else
bool writeFile( const List< int >& il )
{
ofstream fout( "randInt3M_sorted.txt" );
if( !fout ) return false;
for( Iter< int > pos = il.begin(), end = il.end(); pos != end; ++pos )
fout << *pos << "\n";
return true;
}
#endif
bool createFile( List< int >& il )
{
ofstream fout( DATAFILE );
if( !fout ) return false;
srand( (unsigned) time(0) );
for( int i = 0; i < 3000000; ++i )
{
int tmp = rand();
il.push_back( tmp );
fout << tmp << " ";
if( i % 10 == 0 ) fout << endl;
}
fout.close();
return true;
}
int main()
{
cout << "For " << links << " ...\n\n";
cout << "sizeof(List<int>) = " << sizeof(List<int>)
<< ", sizeof(Iter<int>) = " << sizeof(Iter<int>)
<< ", sizeof(Node<int>) = " << sizeof(Node<int>) << " ...\n\n";
#if do_part1
List< int > ml; // construct an empty list to hold int's ...(here 3 Million)
cout << "time in sec's to execute fillFromFile( ml ) = " << flush;
double ti = clock();
if( !fillFromFile( ml ))
{
if( createFile( ml )) cout << "\n(created) ";
else
{
cerr << "\nError in creating data file!"
<< "\nPress 'Enter' to continue/exit ... " << flush;
cin.get();
return 1;
}
}
double tp = clock() - ti;
cout << tp/CLOCKS_PER_SEC << " and ml.get_size() = " << ml.get_size();
cout << "\ntime in sec's to execute ml.msort() = " << flush;
ti = clock();
ml.msort();
tp = clock() - ti;
cout << tp/CLOCKS_PER_SEC << " and ml.isSorted() = "<< ml.isSorted() << endl;
cout << "time in sec's (pre-sorted) to execute ml.msort() = " << flush;
ti = clock();
ml.msort();
tp = clock() - ti;
cout << tp/CLOCKS_PER_SEC << " and ml.isSorted() = "<< ml.isSorted() << endl;
List< int > mlRev;
for( Iter< int > it = ml.begin(), end = ml.end(); it != end; ++it )
mlRev.push_front( *it );
cout << "time in sec's (rev-sorted) to execute ml.msort() = "
<< flush;
ti = clock();
mlRev.msort();
tp = clock() - ti;
cout << tp/CLOCKS_PER_SEC << " and ml.isSorted() = "<< mlRev.isSorted() << endl;
int count = 0;
#if link2
// for double-link linked list ...
for( Iter< int > it = ml.begin(), end = ml.end(); it != end; )
{
if( *it == 32767 ) // try also removing all 0's ...
{
++count;
it = ml.erase( it );
}
else ++it;
}
#else
// for single-link linked list ...
for( Iter< int > it = ml.begin(), end = ml.end(), prev = end ; it != end ; )
{
if( *it == 32767 ) // try also removing all 0's ...
{
++count;
it = ml.erase( it, prev ); // for single linked-list ...
}
else
{
prev = it;
++it;
}
}
#endif // link2
cout << "\nThe count of 32767's = " << count << endl;
cout << "\nThe new size is ml.get_size() = " << ml.get_size() << endl;
ml.remove_duplicates();
cout << "\nThe new size is ml.get_size() = " << ml.get_size() << endl;
count = 0;
Iter< int > it = ml.begin(), end = ml.end();
while( it != end )
{
if( *it == 32767 ) ++count;
++it;
}
cout << "\nThe count NOW of 32767's = " << count << endl;
cout << "time in sec's, for REDUCED list, to execute writeFile( ml ) = "
<< flush;
ti = clock();
writeFile( ml ); // test of reverse iter & previous links after msort was ok
tp = clock() - ti;
cout << tp/CLOCKS_PER_SEC << "\nand ml.get_size() = "<< ml.get_size() << endl;
cout << "\nWait briefly ... freeing large list now ..." << flush;
ml.free();
cout << "\nPress 'Enter' to continue ... " << flush;
cin.get();
#endif // do_part1
List< string > students; // construct an empty List (of strings) ...
cout << "\nstudents.get_size() = " << students.get_size() << "\n";
students.push_back( "Cane, Sugar" );
students.push_back( "Dame, Lady" );
students.push_back( "Fame, Fanny" );
students.push_back( "Game, Pretty" );
cout << "students.get_size() = " << students.get_size() << "\n";
// add a value in 5th position ...
Iter< string > pos, poscpy;
pos = students.begin();
++pos;
++pos;
++pos;
++pos;
students.insert( pos, "Tame, Very" );
cout << "students.get_size() = " << students.get_size() << "\n";
students.insert( pos, "Tame, Very Very" );
//print the list ...
for( pos = students.begin(); pos != students.end(); ++pos )
cout << *pos << "\n";
cout << "students.get_size() = " << students.get_size() << "\n";
#if link2
// remove the 3rd last value ...
pos = students.end();
--pos;
--pos;
--pos;
#else
// remove the 4th value ...
pos = students.begin();
++pos;
++pos;
++pos;
#endif
poscpy = students.erase(pos);
//print the list ...
cout << "\nAter removing 3rd last value ...\n";
for( pos = students.begin(); pos != students.end(); ++pos )
cout << *pos << "\n";
cout << "students.get_size() = " << students.get_size() << "\n";
// insert a student at 'poscpy' returned above ...
students.insert( poscpy, "Anthony, Timothy Horton" );
//print the list ...
cout << "\nAfter insertion ...\n";
for( pos = students.begin(); pos != students.end(); ++pos )
cout << *pos << "\n";
cout << "students.get_size() = " << students.get_size() << "\n";
#if link2
//print the list in reverse order ...
cout << "\nPrinting list in reverse order ...\n";
for( pos = students.end(); pos != students.begin(); )
cout << *--pos << "\n";
cout << "students.get_size() = " << students.get_size() << "\n";
#else
//print the list
cout << "\nPrinting list ...\n";
for( pos = students.begin(); pos != students.end(); ++pos )
cout << *pos << "\n";
cout << "students.get_size() = " << students.get_size() << "\n";
#endif
List < string > s_copy( students );
students.free();
cout << "\nAfter students.free() ... ";
cout << "students.get_size() = " << students.get_size() << "\n";
cout << "\nPrinting s_copy ...\n";
for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
cout << *pos << "\n";
cout << "s_copy.get_size() = " << s_copy.get_size() << "\n";
s_copy.push_front( "Saucer, Lucy" );
if( !s_copy.isSorted() ) { cout << "\nsorting ..."; s_copy.isort(); }
#if link2
cout << "\nPrinting s_copy rev...\n";
for( pos = s_copy.end(); pos != s_copy.begin(); )
cout << *--pos << "\n";
#else
cout << "\nPrinting s_copy ...\n";
for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
cout << *pos << "\n";
#endif
cout << "s_copy.get_size() = " << s_copy.get_size() << "\n";
s_copy.isort_insert( "Georgette, Baby" );
s_copy.update_pRear(); // update links ...
#if link2
cout << "\nAfter isort_insert(...) ... printing s_copy now rev...\n";
for( pos = s_copy.end(); pos != s_copy.begin(); )
cout << *--pos << "\n";
#else
cout << "\nAfter isort_insert(...) ... printing s_copy now ...\n";
for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
cout << *pos << "\n";
List< string > rev;
for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
rev.push_front( *pos );
cout << "\nAfter making a rev copy ... printing rev now ...\n";
for( pos = rev.begin(); pos != rev.end(); ++pos )
cout << *pos << "\n";
cout << "rev.get_size() = " << rev.get_size() << "\n";
#endif
cout << "s_copy.get_size() = " << s_copy.get_size() << "\n";
pos = s_copy.find( "Anthony, Timothy Horto" ); // test can't find ...
s_copy.insert( pos, "Lace, Fanny" );
cout << "\nAfter insert ... printing s_copy ...\n";
for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
cout << *pos << endl;
if( (pos = s_copy.find( "Anthony, Timothy Horton" )) != s_copy.end() )
s_copy.erase( pos );
cout << "\nAfter erase ... printing s_copy ...\n";
for( pos = s_copy.begin(); pos != s_copy.end(); ++pos )
cout << *pos << endl;
cout << "\nPress 'Enter' to continue ... " << flush;
cin.get();
}
// example output ...
/*
For single-link linked list ...
sizeof(List<int>) = 16, sizeof(Iter<int>) = 4, sizeof(Node<int>) = 8 ...
time in sec's to execute fillFromFile( ml ) = 3.828 and ml.get_size() = 3000000
time in sec's to execute ml.msort() = 6.875 and ml.isSorted() = 1
time in sec's (pre-sorted) to execute ml.msort() = 8.688 and ml.isSorted() = 1
time in sec's (rev-sorted) to execute ml.msort() = 0.875 and ml.isSorted() = 1
The count of 32767's = 92
The new size is ml.get_size() = 2999908
The new size is ml.get_size() = 32767
The count NOW of 32767's = 0
time in sec's, for REDUCED list, to execute writeFile( ml ) = 0.078
and ml.get_size() = 32767
Wait briefly ... freeing large list now ...
Press 'Enter' to continue ...
students.get_size() = 0
students.get_size() = 4
students.get_size() = 5
Cane, Sugar
Dame, Lady
Fame, Fanny
Game, Pretty
Tame, Very
Tame, Very Very
students.get_size() = 6
Ater removing 3rd last value ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Tame, Very
Tame, Very Very
students.get_size() = 5
After insertion ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Anthony, Timothy Horton
Tame, Very
Tame, Very Very
students.get_size() = 6
Printing list ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Anthony, Timothy Horton
Tame, Very
Tame, Very Very
students.get_size() = 6
After students.free() ... students.get_size() = 0
Printing s_copy ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Anthony, Timothy Horton
Tame, Very
Tame, Very Very
s_copy.get_size() = 6
sorting ...
Printing s_copy ...
Anthony, Timothy Horton
Cane, Sugar
Dame, Lady
Fame, Fanny
Saucer, Lucy
Tame, Very
Tame, Very Very
s_copy.get_size() = 7
After isort_insert(...) ... printing s_copy now ...
Anthony, Timothy Horton
Cane, Sugar
Dame, Lady
Fame, Fanny
Georgette, Baby
Saucer, Lucy
Tame, Very
Tame, Very Very
After making a rev copy ... printing rev now ...
Tame, Very Very
Tame, Very
Saucer, Lucy
Georgette, Baby
Fame, Fanny
Dame, Lady
Cane, Sugar
Anthony, Timothy Horton
rev.get_size() = 8
s_copy.get_size() = 8
After insert ... printing s_copy ...
Anthony, Timothy Horton
Cane, Sugar
Dame, Lady
Fame, Fanny
Georgette, Baby
Saucer, Lucy
Tame, Very
Tame, Very Very
Lace, Fanny
After erase ... printing s_copy ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Georgette, Baby
Saucer, Lucy
Tame, Very
Tame, Very Very
Lace, Fanny
Press 'Enter' to continue ...
////////////////////////////////////////////////////////////////////////////////
For double-link linked list ...
sizeof(List<int>) = 16, sizeof(Iter<int>) = 8, sizeof(Node<int>) = 12 ...
time in sec's to execute fillFromFile( ml ) = 5.343 and ml.get_size() = 3000000
time in sec's to execute ml.msort() = 7.282 and ml.isSorted() = 1
time in sec's (pre-sorted) to execute ml.msort() = 9.125 and ml.isSorted() = 1
time in sec's (rev-sorted) to execute ml.msort() = 1.172 and ml.isSorted() = 1
The count of 32767's = 92
The new size is ml.get_size() = 2999908
The new size is ml.get_size() = 32767
The count NOW of 32767's = 0
time in sec's, for REDUCED list, to execute writeFile( ml ) = 0.063
and ml.get_size() = 32767
Wait briefly ... freeing large list now ...
Press 'Enter' to continue ...
students.get_size() = 0
students.get_size() = 4
students.get_size() = 5
Cane, Sugar
Dame, Lady
Fame, Fanny
Game, Pretty
Tame, Very
Tame, Very Very
students.get_size() = 6
Ater removing 3rd last value ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Tame, Very
Tame, Very Very
students.get_size() = 5
After insertion ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Anthony, Timothy Horton
Tame, Very
Tame, Very Very
students.get_size() = 6
Printing list in reverse order ...
Tame, Very Very
Tame, Very
Anthony, Timothy Horton
Fame, Fanny
Dame, Lady
Cane, Sugar
students.get_size() = 6
After students.free() ... students.get_size() = 0
Printing s_copy ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Anthony, Timothy Horton
Tame, Very
Tame, Very Very
s_copy.get_size() = 6
sorting ...
Printing s_copy rev...
Tame, Very Very
Tame, Very
Saucer, Lucy
Fame, Fanny
Dame, Lady
Cane, Sugar
Anthony, Timothy Horton
s_copy.get_size() = 7
After isort_insert(...) ... printing s_copy now rev...
Tame, Very Very
Tame, Very
Saucer, Lucy
Georgette, Baby
Fame, Fanny
Dame, Lady
Cane, Sugar
Anthony, Timothy Horton
s_copy.get_size() = 8
After insert ... printing s_copy ...
Anthony, Timothy Horton
Cane, Sugar
Dame, Lady
Fame, Fanny
Georgette, Baby
Saucer, Lucy
Tame, Very
Tame, Very Very
Lace, Fanny
After erase ... printing s_copy ...
Cane, Sugar
Dame, Lady
Fame, Fanny
Georgette, Baby
Saucer, Lucy
Tame, Very
Tame, Very Very
Lace, Fanny
Press 'Enter' to continue ...
*/
// List2IterNode.h // this version 2011-11-30 //
// a 'double-link' linked-list ...
// template class List with 'merge sort' and 'insert sort'
// has private class members: 'head', 'tail', 'size', 'is_sorted' ...
// now includes template class Node and template class Iter
#ifndef LIST2_ITER_NODE_H
#define LIST2_ITER_NODE_H
#include <iostream>
#include <string>
#include <cstdlib> // re. exit ...
using namespace std;
void myAssert( int a, const string& msg )
{
if( !a )
{
cerr << msg << " ... Press 'Enter' to exit ... " << flush;
cin.clear(); cin.sync(); cin.get(); exit(1);
}
}
// forward declarations ...
template < typename T > class Iter;
template < typename T > class List;
template < typename T >
class Node
{
public:
Node( T n ) : data( n ), prev( NULL ), next( NULL ) {}
private:
T data;
Node< T >* prev;
Node< T >* next;
friend class Iter< T >;
friend class List< T >;
};
// an Iter 'points' to a Node's position in a list ... or a 'NULL' i.e. end()
// (i.e. ... past the end of the list)
template< typename T >
class Iter
{
public:
// construct an Iter (not attached to any particular list) ...
Iter() : cur( NULL ), tail( NULL ) {}
// return T value at Node of this Iter ...
T operator * () const
{
myAssert( (cur != NULL), "Iter operator * cannot return NULL (1)" );
return cur->data;
}
T& operator * ()
{
myAssert( (cur != NULL), "Iter operator * cannot return NULL (1)" );
return cur->data;
}
Iter operator ++ ()
{
myAssert( (cur != NULL), "Iter operator ++ cannot ++ NULL (2)" );
cur = cur->next;
return *this;
}
Iter operator ++ ( int anIntDummyHereToIndicatePostPP )
{
myAssert( (cur != NULL), "Iter operator ++ cannot ++ NULL (3)" );
cur = cur->next;
return *this;
}
Iter operator -- ()
{
if( cur == NULL ) cur = tail;
else cur = cur->prev;
myAssert( (cur != NULL), "Iter operator -- cannot return NULL (4)" );
return *this;
}
Iter operator -- ( int anIntDummyHereToIndicatePostPP )
{
if( cur == NULL ) cur = tail;
else cur = cur->prev;
myAssert( (cur != NULL), "Iter operator -- cannot return NULL (5)" );
return *this;
}
bool operator == ( Iter< T > it ) const { return cur == it.cur; }
bool operator != ( Iter< T > it ) const { return cur != it.cur; }
private:
Node< T >* cur;
Node< T >* tail;
friend class List< T >;
};
template< typename T >
class List
{
public:
// default ctor ...
List() : head( NULL ), tail( NULL ), size(0), is_sorted(true) {} // default ctor ...
// dtor ...
~List() { free(); }
void free() // free all ...
{
for( Node< T >* q = head; q != NULL; head = q )
{
q = head->next;
delete head;
}
tail = NULL; // Note: head is set to NULL above on last for loop
size = 0;
is_sorted = true;
}
// copy ctor ...
List( const List< T >& obj ) : head( NULL ), tail( NULL ), size( 0 ),
is_sorted( obj.is_sorted ) //{ copy( obj ); }
{
for( Node< T >* p = obj.head; p != NULL; p = p->next )
push_back( p->data );
}
// overloaded assignment ...
List< T >& operator = ( const List< T >& obj )
{
if( this != &obj )
{
free();
is_sorted = obj.is_sorted;
for( Node< T >* p = obj.head; p != NULL; p = p->next )
push_back( p->data );
}
return *this;
}
//Node< T >* get_head() const { return head; }
void push_front( T e )
{
Node< T >* newnode = new Node< T > ( e );
if( head != NULL ) // NOT empty ...
{
head->prev = newnode;
newnode->next = head;
head = newnode;
}
else head = tail = newnode;
++size;
is_sorted = false;
}
void push_back( T e )
{
Node< T >* newnode = new Node< T > ( e );
if( tail != NULL ) // NOT empty ...
{
newnode->prev = tail;
tail->next = newnode;
tail = newnode;
}
else head = tail = newnode;
++size;
is_sorted = false;
}
void insert( Iter< T > it, T e )
{
if( it.cur != NULL )
{
Node< T >* after = it.cur;
Node< T >* before = after->prev;
Node< T >* newnode = new Node< T > ( e );
newnode->prev = before;
newnode->next = after;
after->prev = newnode;
if( before != NULL )
before->next = newnode;
else // insert at beginning ...
head = newnode;
++size;
is_sorted = false;
}
else push_back( e );
}
int get_size() const { return size; }
int length() const { return size; }
Iter< T > erase( Iter< T > it )
{
myAssert( (it.cur != NULL), "List canNOT erase itr.cur = NULL (5)" );
Node< T >* remove = it.cur;
Node< T >* before = remove->prev;
Node< T >* after = remove->next;
if( remove == head ) head = after;
else before->next = after;
if( remove == tail ) tail = before;
else after->prev = before;
it.cur = after;
delete remove;
--size;
return it;
}
Iter< T > find( T e ) const
{
Iter< T > pos;
for( pos = begin(); pos != end(); pos++ )
if( *pos == e ) return pos;
return pos; // i.e. return end();
}
Iter< T > begin() const
{
Iter< T > itr;
itr.cur = head;
itr.tail = tail;
return itr;
}
Iter< T > end() const
{
Iter< T > itr;
itr.cur = NULL;
itr.tail = tail;
return itr;
}
// insert new element e in sorted order into a sorted list ...
void isort_insert( T e );
void isort(); // insert-sort the whole list in place ...
void update_pRear() // and update all 'prev' links also ... (after sorts)
{
if( head == NULL ) { tail = NULL; return; }
Node< T >* prev = tail = head; // initial tail and prev to head ...
head->prev = NULL; // set head prev value ...
while( tail->next != NULL ) // traversing in 'front-to-back' direction
{
tail = tail->next;
tail->prev = prev;
prev = prev->next;
}
}
// merge sort the whole list in place (a 'divide and sort' recursive sort)
void msort()
{
Node< T >* p = head;
merge_sort( p, size ); // p is updated in recursion using pass by ref.
set_pFront_pRear( p ); // update all 'prev' links also ...
is_sorted = true;
}
bool get_is_sorted() const { return is_sorted; }
void set_issorted( bool is ) {is_sorted = is; }
bool isSorted( bool a = true ) const
{
if( size < 2 ) return true;
if( a )
{
for( Node< T >* q = head; q->next != NULL; q = q->next )
if( q->next->data < q->data ) return false;
}
if( !a ) // i.e ... if descending
{
for( Node< T >* q = head; q->next != NULL; q = q->next )
if( q->data < q->next->data ) return false;
}
//
return true;
}
void remove_duplicates()
{
if( size < 2 ) return;
if( !is_sorted ) msort();
Node< T >* p = head;
while( p->next != NULL )
{
if( p->data == p->next->data )
{
Node< T >* tmp = p->next;
p->next = p->next->next;
delete tmp;
--size;
}
else p = p->next; // move up one ...
}
update_pRear(); // updates all prev links also ...
}
private:
void insert_sorted( Node < T >*& pHead, Node< T >* pNewNode );
// returns updated pFront by ref...
void merge_sort( Node< T >*& pFront, int size );
// merge two sorted lists with heads 'a' and 'b' ... in sorted order
Node< T >* merge( Node< T >* a, Node< T >* b )
{
if( a == NULL ) return b;
if( b == NULL ) return a;
Node< T >* sorted; // now get appropriate new head for merged list
if( a->data <= b->data )
{
sorted = a;
a = a->next;
}
else
{
sorted = b;
b = b->next;
}
Node< T >* new_merged_head = sorted;
// now merge lists ...
while( a != NULL && b != NULL )
{
if( a->data <= b->data )
{
sorted->next = a;
sorted = sorted->next;
a = a->next;
}
else
{
sorted->next = b;
sorted = sorted->next;
b = b->next;
}
}
// now ... append the ONE part that might have been left-over above ...
if( a != NULL )
sorted->next = a;
else if( b != NULL )
sorted->next = b;
return new_merged_head;
}
void set_pFront_pRear(Node< T >* p) { head = p; update_pRear(); }
Node< T >* head;
Node< T >* tail;
int size;
bool is_sorted;
};
//////////////////////////////// BEGIN MERGE SORT //////////////////////////////
// divide list into two halves and then recursively sort each half ...
// then merge the two sorted halves using the above merge function
// Note: calling 'pFront' is updated by using 'pass by ref'
template< typename T >
void List< T >::merge_sort( Node< T >*& pFront, int size )
{
if( size < 2 ) return;
Node< T >* pHead2;
Node< T >* pEnd1;
int size2 = size/2;
int size1 = size - size2;
// split the list into two lists ... the first half begins with pHead
pEnd1 = pFront; // first set pEnd1 to the head address ...
for( int i=1; i<size1; ++i )
pEnd1 = pEnd1->next;
pHead2 = pEnd1->next; // second half begins with pHead2
pEnd1->next = NULL; // breaking the chain here... so we can have two lists
// merge the lists after recusively merge_sorting them
merge_sort( pFront, size1 );
merge_sort( pHead2, size2 );
pFront=merge( pFront, pHead2 );
}//////////////////////////////// END MERGE SORT ///////////////////////////////
/////////////////////////////////// BEGIN ISORT ////////////////////////////////
// does NOT update pRear ... so must call update_pRear() when all inserts done.
template < typename T >
void List< T >::isort_insert( T e )
{
Node< T >* n = new Node< T > ( e );
if( size > 0 && !is_sorted ) msort();
insert_sorted( head, n );
++size;
}
// insert a new node in a list with its node data in proper order ... does NOT
// update size or pRear ... so must call update_pRear() when all inserts done.
template < typename T >
void List< T >::insert_sorted( Node< T >*& pHead, Node< T >* pNewNode )
{
// First handle most likely cases where new node is NOT first element ...
if( pHead != NULL && pNewNode->data >= pHead->data )
{
// If here ... search the list for the right location
Node< T >* q = pHead; // Get a working copy of pHead in q
// Start comparing with element AFTER 'q' ... i.e. the 'next in'
while( q->next != NULL && q->next->data <= pNewNode->data )
q = q->next; // Traverse the list ...
// Ok, insert after 'q' by 're-nexting' the pointers ...
// ( Includes inserting at end position ... where q->next is NULL )
// for A->B to become A->N->B ...
pNewNode->next = q->next; // first insert/link ... N->B
q->next = pNewNode; // and now link ... A->N
}
else // becomes the first element ...
{
pNewNode->next = pHead; // old pHead becomes 2nd in list
pHead = pNewNode; // and this new node becomes the head of the list
}
}
// insert sort a whole list ...
template < typename T >
void List< T >::isort()
{
// Note: pNewHead MUST be NULL to start ...
Node< T > *pTmp, *pHead = head, *pNewHead = NULL;
while( pHead != NULL ) // take each node from old list and insert in new
{
pTmp = pHead; // get 'this' node ...
pHead = pHead->next; // move 'start' up one, to be ready for next node
insert_sorted( pNewHead, pTmp ); // insert 'this' pTmp node
}
set_pFront_pRear( pNewHead );
is_sorted = true;
} ///////////////////////////////// END ISORT //////////////////////////////////
#endif
// List1IterNode.h // this version 2011-11-30 //
// a 'single-link' linked-list //
// template class List with 'merge sort' and 'insert sort'
// has private class members: 'pFront', 'pRear', 'size', 'is_sorted' ...
// now includes template class Node and template class Iter
#ifndef LIST1_ITER_NODE_H
#define LIST1_ITER_NODE_H
#include <iostream>
#include <string>
#include <cstdlib> // re. exit ...
using namespace std;
void myAssert( int a, const string& msg )
{
if( !a )
{
cerr << msg << " ... Press 'Enter' to exit ... " << flush;
cin.clear(); cin.sync(); cin.get(); exit(1);
}
}
// forward declarations ...
template < typename T > class Iter;
template < typename T > class List;
template < typename T >
class Node
{
public:
Node( T n ) : data( n ), next( NULL ) {}
private:
T data;
Node* next;
friend class Iter< T >;
friend class List< T >;
};
// an Iter 'points' to a Node's position in a list ... or a 'NULL' i.e. end()
// (i.e. ... past the end of the list)
template< typename T >
class Iter
{
public:
// construct an Iter (not attached to any particular list) ...
Iter() : cur( NULL ) {}
// return T value at Node of this Iter ...
T operator * () const
{
myAssert( (cur != NULL), "Iter operator * cannot return NULL (1)" );
return cur->data;
}
T& operator * ()
{
myAssert( (cur != NULL), "Iter operator * cannot return NULL (1)" );
return cur->data;
}
// pre ++ ...
Iter& operator ++ ()
{
myAssert( (cur != NULL), "Iter operator ++ cannot ++ NULL (2)" );
cur = cur->next;
return *this;
}
// post ++ ...
Iter& operator ++ ( int anIntDummyHereToIndicatePostPP )
{
myAssert( (cur != NULL), "Iter operator ++ cannot ++ NULL (3)" );
cur = cur->next;
return *this;
}
bool operator == ( Iter< T > it ) const { return cur == it.cur; }
bool operator != ( Iter< T > it ) const { return cur != it.cur; }
private:
Node< T >* cur;
friend class List< T >;
};
template< typename T >
class List
{
public:
// default ctor ...
List() : pFront( NULL ), pRear( NULL ), size( 0 ), is_sorted( true ) {}
// dtor ...
~List() { free(); }
void free() // free all ...
{
for( Node< T >* q = pFront; q != NULL; pFront = q )
{
q = pFront->next;
delete pFront;
}
pRear = NULL; // Note: pFront is set to NULL above on last for loop
size = 0;
is_sorted = true;
}
List( const List < T > & obj ) // inline copy constructor ...
{
pFront = pRear = NULL;
size = 0;
for( Node< T >* p = obj.pFront; p != NULL; p = p->next )
push_back( p->data );
is_sorted = obj.is_sorted;
}
List& operator = ( const List < T > & obj ) // inline overloaded assignment
{
if( this != &obj )
{
free();
for( Node< T >* p = obj.pFront; p != NULL; p = p->next )
push_back( p->data );
is_sorted = obj.is_sorted;
}
return *this;
}
void push_front( T e );
void push_back( T e );
void add_at_index( int c, T e );
void remove( T e );
void show_all() const;
bool exist( T e ) const;
int length() const { return size; }
int get_size() const { return size; }
bool get_is_sorted() const { return is_sorted; }
void set_issorted( bool is ) {is_sorted = is; }
bool isSorted( bool a = true ) const
{
if( size < 2 ) return true;
if( a )
{
for( Node< T >* q = pFront; q->next != NULL; q = q->next )
if( q->next->data < q->data ) return false;
}
if( !a ) // i.e ... if descending
{
for( Node< T >* q = pFront; q->next != NULL; q = q->next )
if( q->data < q->next->data ) return false;
}
//
return true;
}
T max() const;
T min() const;
// insert new element e in sorted order into a sorted list ...
void isort_insert( T e );
void isort(); // insert-sort the whole list in place ...
void update_pRear()
{
pRear = pFront;
if( pRear == NULL ) return;
while( pRear->next != NULL ) pRear = pRear->next;
}
// merge sort the whole list in place (a 'divide and sort' recursive sort)
void msort()
{
Node< T >* p = pFront;
merge_sort( p, size ); // p is updated in recursion using pass by ref.
set_pFront_pRear( p );
is_sorted = true;
}
void remove_duplicates()
{
if( size <= 1 ) return;
if( !is_sorted ) msort();
Node< T >* p = pFront;
while( p->next != NULL )
{
if( p->data == p->next->data )
{
Node< T >* tmp = p->next;
p->next = p->next->next;
delete tmp;
--size;
}
else p = p->next; // move up one ...
}
update_pRear();
}
//Node< T >* get_pFront() const { return pFront; }
void insert_after( Iter< T > it, T e ) // insert after 'it' ....
{
if( it.cur != NULL )
{
Node< T >* newnode = new Node< T >( e );
// for A->B to become A->N->B ...
newnode->next = it.cur->next; // ....... set N->B
it.cur->next = newnode; // now can set ... A->N
++size;
is_sorted = false;
}
else push_back( e );
}
void insert_before( Iter< T > it, T e ) // insert before 'it' ....
{
if( it.cur == pFront ) push_front( e );
//else if( it.cur == NULL ) push_back( e);
else
{
Node< T >* newnode = new Node< T >( e );
Node< T >* before = pFront;
while( before->next != it.cur )
before = before->next;
// for A->B to become A->N->B ...
before->next = newnode; // ... set A->N
newnode->next = it.cur; // and N->B
++size;
is_sorted = false;
}
}
Iter< T > erase( Iter< T > it )
{
myAssert( (it.cur != NULL), "List canNOT erase it.cur = NULL (4)" );
Node< T >* remove = it.cur;
Node< T >* before = NULL;
Node< T >* after = remove->next;
if( remove == pFront ) pFront = after;
else
{
before = pFront;
while( before->next != remove )
before = before->next;
before->next = after; // skip over this 'remove node' address ...
}
if( remove == pRear ) pRear = before;
it.cur = after;
delete remove;
--size;
return it;
}
Iter< T > erase( Iter< T > it, Iter< T > prev )
{
myAssert( (it.cur != NULL), "List canNOT erase it.cur = NULL (5)" );
Node< T >* remove = it.cur;
Node< T >* before = prev.cur;
Node< T >* after = remove->next;
if( remove == pFront )
pFront = after;
else
before->next = after; // skip over this 'remove node' address ...
if( remove == pRear )
pRear = before;
it.cur = after;
delete remove;
--size;
return it;
}
Iter< T > find( T e ) const
{
Iter< T > pos;
for( pos = begin(); pos != end(); ++pos )
if( *pos == e ) return pos;
return pos; // i.e. return end();
}
Iter< T > begin() const
{
Iter< T > itr;
itr.cur = pFront;
return itr;
}
Iter< T > end() const
{
Iter< T > itr;
itr.cur = NULL;
return itr;
}
private:
Node < T > *pFront, *pRear;
int size; // number of list nodes
bool is_sorted;
void insert_sorted( Node < T >*& pHead, Node< T >* pNewNode );
void merge_sort( Node< T >*& pFront, int size ); // returns updated pFront by ref.
// merge two sorted lists with heads 'a' and 'b' ... in sorted order
Node< T >* merge( Node< T >* a, Node< T >* b )
{
if( a == NULL ) return b;
if( b == NULL ) return a;
Node< T >* sorted; // now get appropriate new head for merged list
if( a->data <= b->data )
{
sorted = a;
a = a->next;
}
else
{
sorted = b;
b = b->next;
}
Node< T >* new_merged_head = sorted;
// now merge lists ...
while( a != NULL && b != NULL )
{
if( a->data <= b->data )
{
sorted->next = a;
sorted = sorted->next;
a = a->next;
}
else
{
sorted->next = b;
sorted = sorted->next;
b = b->next;
}
}
// now ... append the ONE part that might have been left-over above ...
if( a != NULL )
sorted->next = a;
else if( b != NULL )
sorted->next = b;
return new_merged_head;
}
void set_pFront_pRear(Node< T >* p) { pFront = p; update_pRear(); }
};
// definitions ...
template< typename T >
void List< T >::push_front( T e ) // inserts e with type T at front of List
{
Node< T >* n = new Node< T > ( e );
n->next = pFront;
pFront = n;
if( pRear == NULL ) pRear = pFront;
++size;
is_sorted = false;
}
template< typename T >
void List< T >::push_back( T e ) // inserts e with type T at end of List
{
Node< T >* n = new Node< T > ( e );
if( pFront != NULL )
{
pRear->next = n;
pRear = n;
}
else
pRear = pFront = n;
++size;
is_sorted = false;
}
template< typename T >
void List< T >::add_at_index( int c, T e ) // inserts e with type T at index c
{
if( c >= 0 && c < size )
{
if( c > 0 )
{
// insert at index c ... BUT after index 0 ... i.e. at 1 to size
Node< T >* prev = pFront;
for( int i = 1; i < c; ++i ) prev = prev->next;
Node< T >* n = new Node< T > ( e );
n->data = e;
// now insert n at index c ... A -> B becomes A->C->B
n->next = prev->next; // C -> B
prev->next = n; // A -> C
++ size;
is_sorted = false;
} // here c is 0 ... so ...
else push_front( e ); // resets size, pFront and pRear ... as applicable
}
else if( c == size ) push_back( e );
else
{
cout << "\nHighest new index allowed is " << size
<< ". You requested index " << c << " ... push_back y/n ? ";
int reply = cin.get();
cin.sync();
if( reply == 'n' || reply =='N' )
return;
// if reach hear ...
cout <<"Ok ... will push_back ...\n";
push_back( e ); // resets size, pFront and pRear ... as applicable
}
}
template< typename T >
void List< T >::remove( T e )
{
if( !size )
{
cout << "\nCan not remove '" << e << "' since list is empty.\n";
return;
}
Node< T >* q = pFront;
if( q->data == e ) // if at front ...
{
pFront = q->next;
delete q;
--size;
cout<<"\n'" << e <<"' removed ...";
if( size <= 1 ) { pRear = pFront; is_sorted = true; }
return;
}
// if reach here ... 'e' is NOT the first
Node< T >* prev = q;
q = q->next; // q now points to 2nd node in list ...
while( q != NULL ) // Note: also handles case of just one Node in list
{
if( q->data == e )
{
prev->next = q->next;
delete q;
cout<<"\n'" << e <<"' removed ...";
--size;
if( prev->next == NULL ) pRear = prev; // update 'rear' ...
if( size == 1 ) is_sorted = true;
return;
}
// if reach here ... advance both nodes up the list ...
prev = q;
q = q->next;
}
cout<<"\n'" << e <<"' NOT found ...";
}
template< typename T >
void List< T >::show_all() const
{
for( Node< T >* q = pFront; q != NULL; q = q->next )
cout << endl << q->data;
}
template < typename T >
bool List< T >::exist( T e ) const
{
for( Node< T >* q = pFront; q != NULL; q = q->next )
if( q->data == e )
return true;
return false;
}
template < typename T >
T List< T >::max() const
{
if( !size )
{
cout << "List is empty ... returning 'zero' ... ";
return T(0);
}
T max = pFront->data;
for( Node< T >* q = pFront; q->next != NULL; q = q->next )
if( q->next->data > max )
max = q->next->data;
return max;
}
template < typename T >
T List< T >::min() const
{
if( !size )
{
cout << "List is empty ... returning 'zero' ... ";
return T(0);
}
T min = pFront->data;
for( Node< T >* q = pFront; q->next != NULL; q = q->next )
if( q->next->data < min )
min = q->next->data;
return min;
}
//////////////////////////////// BEGIN MERGE SORT //////////////////////////////
// divide list into two halves and then recursively sort each half ...
// then merge the two sorted halves using the above merge function
// Note: calling 'pFront' is updated by using 'pass by ref'
template < typename T >
void List< T >::merge_sort( Node< T >*& pFront, int size )
{
if( size < 2 ) return;
Node< T >* pHead2;
Node< T >* pEnd1;
int size2 = size/2;
int size1 = size - size2;
// split the list into two lists ... the first half begins with pHead
pEnd1 = pFront; // first set pEnd1 to the head address ...
for( int i=1; i<size1; ++i )
pEnd1 = pEnd1->next;
pHead2 = pEnd1->next; // second half begins with pHead2
pEnd1->next = NULL; // breaking the chain here... so we can have two lists
// merge the lists after recusively merge_sorting them
merge_sort( pFront, size1 );
merge_sort( pHead2, size2 );
pFront=merge( pFront, pHead2 );
}//////////////////////////////// END MERGE SORT ///////////////////////////////
/////////////////////////////////// BEGIN ISORT ////////////////////////////////
// does NOT update pRear ... so must call update_pRear() when all inserts done.
template < typename T >
void List< T >::isort_insert( T e )
{
Node< T >* n = new Node< T > ( e );
if( size > 0 && !is_sorted ) msort();
insert_sorted( pFront, n );
++size;
}
// insert a new node in a list with its node data in proper order ... does NOT
// update size or pRear ... so must call update_pRear() when all inserts done.
template < typename T >
void List< T >::insert_sorted( Node< T >*& pHead, Node< T >* pNewNode )
{
// First handle most likely cases where new node is NOT first element ...
if( pHead != NULL && pNewNode->data >= pHead->data )
{
// If here ... search the list for the right location
Node< T >* q = pHead; // Get a working copy of pHead in q
// Start comparing with element AFTER 'q' ... i.e. the 'next in'
while( q->next != NULL && q->next->data <= pNewNode->data )
q = q->next; // Traverse the list ...
// Ok, insert after 'q' by 're-nexting' the pointers ...
// ( Includes inserting at end position ... where q->next is NULL )
// for A->B to become A->N->B ...
pNewNode->next = q->next; // first insert/link ... N->B
q->next = pNewNode; // and now link ... A->N
}
else // becomes the first element ...
{
pNewNode->next = pHead; // old pHead becomes 2nd in list
pHead = pNewNode; // and this new node becomes the head of the list
}
}
// insert sort a whole list ...
template < typename T >
void List< T >::isort()
{
// Note: pNewHead MUST be NULL to start ...
Node< T > *pTmp, *pHead = pFront, *pNewHead = NULL;
while( pHead != NULL ) // take each node from old list and insert in new
{
pTmp = pHead; // get 'this' node ...
pHead = pHead->next; // move 'start' up one, to be ready for next node
insert_sorted( pNewHead, pTmp ); // insert 'this' pTmp node
}
set_pFront_pRear( pNewHead );
is_sorted = true;
} ///////////////////////////////// END ISORT //////////////////////////////////
#endif
// simpleSLL_Set.cpp // 2012-01-04 //
#include <iostream>
#include <fstream>
using namespace std;
class LinkedList
{
protected:
struct Node
{
int data;
Node* link;
Node( int d = 0 ) : data(d), link(0) {} // default ctor
} *front, *back ;
int len;
friend ostream& operator << ( ostream&, const LinkedList& );
public:
LinkedList() : front(0), back(0), len(0) {} // default ctor
~LinkedList() { clear(); }
LinkedList( const LinkedList& ); // copy ctor
LinkedList& operator = ( const LinkedList& ); // overloaded assignment
void push_front( int e );
void push_back( int e );
int pop_front();
int pop_back();
int size() const { return len; }
bool exists( const int& e ) const;
void clear();
} ;
ostream& operator << ( ostream& os, const LinkedList& obj )
{
for( LinkedList::Node* cur = obj.front; cur != 0; cur = cur->link )
os << cur->data << " ";
return os;
}
LinkedList::LinkedList( const LinkedList& old )
{
for( Node* cur = old.front; cur != 0; cur = cur->link )
push_back( cur->data );
}
LinkedList& LinkedList::operator = ( const LinkedList& old )
{
if( this != &old )
{
for( Node* cur = old.front; cur != 0; cur = cur->link )
push_back( cur->data );
}
return *this;
}
void LinkedList::push_front( int e )
{
Node* newNode = new Node(e);
newNode->link = front;
front = newNode;
if( !back ) back = front;
++len;
}
void LinkedList::push_back( int e )
{
Node* newNode = new Node(e);
if( back )
{
back->link = newNode;
back = newNode;
}
else back = front = newNode;
++len;
}
int LinkedList::pop_front()
{
int tmp = 0;
if( front )
{
Node* cur = front;
tmp = front->data;
front = front->link;
delete cur;
--len;
if( !front ) back = 0;
}
else cout << "\nList was empty ... so returning data value '0'\n";
return tmp;
}
int LinkedList::pop_back()
{
int tmp = 0;
if( len > 1 )
{
Node* prev = front;
Node* cur = front->link;
while( cur != back )
{
prev = cur;
cur = cur->link;
}
tmp = back->data; // cur->data
prev->link = 0;
back = prev;
delete cur;
--len;
}
else if( len == 1 )
{
tmp = front->data;
delete front;
--len;
back = front = 0;
}
else cout << "\nList was empty ... so returning data value '0'\n";
return tmp;
}
bool LinkedList::exists( const int& e ) const
{
for( Node* cur = front; cur != 0; cur = cur->link )
if( e == cur->data ) return true;
// else ...
return false;
}
void LinkedList::clear()
{
for( Node* cur = front; cur != 0; cur = front )
{
front = front->link;
delete cur;
}
back = 0;
len = 0;
}
////////////////////////////////////////////////////////////////////////////////
class Set : public LinkedList
{
public:
void insert( int e );
Set create_union( const Set& b ) const ;
Set create_intersection( const Set& b ) const ;
} ;
void Set::insert( int e )
{
if( !exists( e ) ) push_back( e );
}
Set Set::create_union( const Set& b ) const
{
Set tmp; // to hold copy of first set ...
for( Node* cur = front; cur != 0; cur = cur->link )
tmp.push_back( cur->data );
for( Node* cur = b.front; cur != 0; cur = cur->link )
tmp.insert( cur->data );
return tmp;
}
Set Set::create_intersection( const Set& b ) const
{
Set tmp; // to hold intersection set ...
for( Node* cur = front; cur != 0; cur = cur->link )
if( b.exists( cur->data ) ) tmp.push_back( cur->data );
return tmp;
}
////////////////////////////////////////////////////////////////////////////////
int main()
{
cout << "Testing the class LinkedList ...\n\n";
LinkedList myLst;
myLst.push_front( 5 );
myLst.push_front( 6 );
myLst.push_front( 7 );
cout << "The list now is: " << myLst << endl;
myLst.push_back( 1 );
myLst.push_back( 2 );
myLst.push_back( 3 );
cout << "The list now is: " << myLst << endl;
cout << "\npopping front the first 3 values: ";
while( myLst.size() > 3 ) cout << myLst.pop_front() << " ";
cout << "\npopping back the last 3 values: ";
while( myLst.size() ) cout << myLst.pop_back() << " ";
cout << "\n\n\nTesting the class Set ...\n\n";
int ary[] = { 0, 1, 6, 0, 6, 1, 5, 7, 5, 1 };
const int ary_size = sizeof ary / sizeof ary[0];
cout << "ary is: ";
for( int i = 0; i < ary_size; ++i ) cout<< ary[i] << " ";
Set mySet;
for( int i = 0; i < ary_size; ++i ) mySet.insert( ary[i] );
cout << "\nmySet is: " << mySet;
int ary2[] = { 9, 8, 7, 6, 9, 1, 7 };
const int ary2_size = sizeof ary2 / sizeof ary2[0];
cout << "\n\nary2 is: ";
for( int i = 0; i < ary2_size; ++i ) cout<< ary2[i] << " ";
Set mySet2;
for( int i = 0; i < ary2_size; ++i ) mySet2.insert( ary2[i] );
cout << "\nmySet2 is: " << mySet2;
cout << "\n\nUnion is: " << mySet.create_union( mySet2 );
cout << "\nIntersection is: " << mySet.create_intersection( mySet2 );
cout << "\n\nPress 'Enter' to continue ... " << flush;
cin.get();
}
// template_simpleSLL_Set.cpp // 2012-01-04 //
#include <iostream>
#include <string>
using namespace std;
template< typename T >
class LinkedList
{
protected:
struct Node
{
T data;
Node* link;
Node( T d = 0 ) : data(d), link(0) {} // default ctor
} *front, *back ;
int len;
public:
LinkedList() : front(0), back(0), len(0) {} // default ctor
~LinkedList() { clear(); }
LinkedList( const LinkedList< T >& ); // copy ctor
LinkedList< T >& operator = ( const LinkedList< T >& ); // overloaded assignment
void push_front( T e );
void push_back( T e );
T pop_front();
T pop_back();
int size() const { return len; }
bool exists( const T& ) const;
void clear();
void print() const;
} ;
template< typename T >
void LinkedList< T >::print() const
{
for( Node* cur = front; cur != 0; cur = cur->link )
cout << cur->data << " ";
}
template< typename T >
LinkedList< T >::LinkedList( const LinkedList< T >& old )
{
for( Node* cur = old.front; cur != 0; cur = cur->link )
push_back( cur->data );
}
template< typename T >
LinkedList< T >& LinkedList< T >::operator = ( const LinkedList< T >& old )
{
if( this != &old )
{
for( Node* cur = old.front; cur != 0; cur = cur->link )
push_back( cur->data );
}
return *this;
}
template< typename T >
void LinkedList< T >::push_front( T e )
{
Node* newNode = new Node(e);
newNode->link = front;
front = newNode;
if( !back ) back = front;
++len;
}
template< typename T >
void LinkedList< T >::push_back( T e )
{
Node* newNode = new Node(e);
if( back )
{
back->link = newNode;
back = newNode;
}
else back = front = newNode;
++len;
}
template< typename T >
T LinkedList< T >::pop_front()
{
int tmp = 0;
if( front )
{
Node* cur = front;
tmp = front->data;
front = front->link;
delete cur;
--len;
if( !front ) back = front;
}
else cout << "\nList was empty ... so returning data value '0'\n";
return tmp;
}
template< typename T >
T LinkedList< T >::pop_back()
{
int tmp = 0;
if( len > 1 )
{
Node* prev = front;
Node* cur = front->link;
while( cur != back )
{
prev = cur;
cur = cur->link;
}
tmp = back->data; // cur->data
prev->link = 0;
back = prev;
delete cur;
--len;
}
else if( len == 1 )
{
tmp = front->data;
delete front;
--len;
back = front = 0;
}
else cout << "\nList was empty ... so returning data value '0'\n";
return tmp;
}
template< typename T >
bool LinkedList< T >::exists( const T& e ) const
{
for( Node* cur = front; cur != 0; cur = cur->link )
if( e == cur->data ) return true;
// else ...
return false;
}
template< typename T >
void LinkedList< T >::clear()
{
for( Node* cur = front; cur != 0; cur = front )
{
front = front->link;
delete cur;
}
back = 0;
len = 0;
}
////////////////////////////////////////////////////////////////////////////////
template< typename T >
class Set : public LinkedList< T >
{
public:
void insert( T e );
Set create_union( const Set< T >& b ) const ;
Set create_intersection( const Set< T >& b ) const ;
} ;
template< typename T >
void Set< T >::insert( T e )
{
if( !exists( e ) ) push_back( e );
}
template< typename T >
Set< T > Set< T >::create_union( const Set< T >& b ) const
{
Set< T > tmp; // to hold copy of first set ...
for( typename LinkedList< T >::Node* cur = LinkedList< T >::front;
cur != 0; cur = cur->link )
tmp.push_back( cur->data );
for( typename LinkedList< T >::Node* cur = b.front;
cur != 0; cur = cur->link )
tmp.insert( cur->data );
return tmp;
}
template< typename T >
Set< T > Set< T >::create_intersection( const Set< T >& b ) const
{
Set< T > tmp; // to hold intersection set ...
for( typename LinkedList< T >::Node* cur = LinkedList< T >::front;
cur != 0; cur = cur->link )
if( b.exists( cur->data ) ) tmp.push_back( cur->data );
return tmp;
}
////////////////////////////////////////////////////////////////////////////////
int main()
{
cout << "Testing the template class LinkedList ...\n\n";
LinkedList< int > myLst;
myLst.push_front( 5 );
myLst.push_front( 6 );
myLst.push_front( 7 );
cout << "The list now is: ";
myLst.print();
myLst.push_back( 1 );
myLst.push_back( 2 );
myLst.push_back( 3 );
cout << "\nThe list now is: ";
myLst.print();
cout << "\n\npopping front the first 3 values: ";
while( myLst.size() > 3 ) cout << myLst.pop_front() << " ";
cout << "\npopping back the last 3 values: ";
while( myLst.size() ) cout << myLst.pop_back() << " ";
cout << "\n\nTesting the template class Set ...\n\n";
string ary[] = { "0", "1", "6", "0", "6", "1", "5", "7", "5", "1" };
const int ary_size = sizeof ary / sizeof ary[0];
cout << "ary is: ";
for( int i = 0; i < ary_size; ++i ) cout<< ary[i] << " ";
Set< string > mySet;
for( int i = 0; i < ary_size; ++i ) mySet.insert( ary[i] );
cout << "\nmySet is: ";
mySet.print();
string ary2[] = { "9", "8", "7", "6", "9", "1", "7" };
const int ary2_size = sizeof ary2 / sizeof ary2[0];
cout << "\n\nary2 is: ";
for( int i = 0; i < ary2_size; ++i ) cout<< ary2[i] << " ";
Set< string > mySet2;
for( int i = 0; i < ary2_size; ++i ) mySet2.insert( ary2[i] );
cout << "\nmySet2 is: ";
mySet2.print();
cout << "\n\nUnion is: ";
mySet.create_union( mySet2 ).print();
cout << "\nIntersection is: ";
mySet.create_intersection( mySet2 ).print();
cout << "\n\nPress 'Enter' to continue ... " << flush;
cin.get();
}
// classList1.h // 2011-12-18 //
// a template class for a single-link linked list ...
// with template functions for bsort (an array like bubble sort, swaps values)
// and a template function quicksort (a list type quick sort that moves nodes)
#ifndef CLASSLIST1_H
#define CLASSLIST1_H
#include <string> // should include this ...
////////////////////////////////////////////////////////////////////////////////
template < typename T >
class List1
{
private:
class Node
{
public:
T value;
Node *next;
};
Node *head, *tail;
int len;
public:
List1();
~List1();
List1( const List1< T >& );
List1< T >& operator = ( const List1< T >& );
void clear();
int size() const;
class iterator
{
friend class List1< T >; // to give class List access to private ptr
public:
iterator& operator ++ (); // { ptr = ptr->next; return *this; }
iterator& operator ++ ( int dummy ) { ptr = ptr->next; return *this; }
bool operator != (const iterator & it2) const;
T operator * () const;
T& operator * ();
private:
Node* ptr;
};
iterator begin();
iterator end();
void push_front( const T& );
void push_back( const T& );
void pop_front_push_other_front( List1< T >& );
void append_clear_other( List1< T >& );
};
////////////////////////////////////////////////////////////////////////////////
// Begin definitions of List member functions ...
////////////////////////////////////////////////////////////////////////////////
template < typename T >
List1< T >::List1() : head(0), tail(0), len(0) {} // default constructor ...
template < typename T >
List1< T >::~List1() { clear(); } // destructor ...
template < typename T > // copy constructor ...
List1< T >::List1( const List1< T >& old_list )
{
head = tail = 0;
len = 0;
for( Node* n = old_list.head; n != 0; n = n->next )
push_back( n->value );
}
template < typename T > // overloaded operator = ...
List1< T >& List1< T>::operator = ( const List1< T >& old_list )
{
if( this != &old_list )
{
clear();
for( Node* n = old_list.head; n != 0; n = n->next )
push_back( n->value );
}
return *this;
}
template < typename T >
int List1< T >::size() const { return len; }
template < typename T >
void List1< T >::clear()
{
for( Node* tmp = head; head != 0; tmp = head )
{
head = head->next;
delete tmp;
}
tail = 0;
len = 0;
}
// Assigns the iterator to the next Node and returns that iterator.
template < typename T >
typename List1< T >::iterator& List1 < T >::iterator::operator ++ ()
{
ptr = ptr->next;
return *this;
}
// Compares two iterators and returns true or false depending on whether
// or not ... they are referencing the same Node.
template < typename T >
bool List1< T >::iterator::operator != (
const typename List1< T >::iterator& it2 ) const
{
return ptr != it2.ptr;
}
// Returns the value of the Node that the iterator is referencing.
template < typename T >
T List1< T >::iterator::operator * () const
{
return ptr->value;
}
// Permits assigning a Node a new value, via an iterator.
template < typename T >
T& List1< T >::iterator::operator * ()
{
return ptr->value;
}
template < typename T >
typename List1< T >::iterator List1< T >::begin()
{
typename List1< T >::iterator it;
it.ptr = head;
return it;
}
template < typename T >
typename List1< T >::iterator List1< T >::end()
{
typename List1< T >::iterator it;
it.ptr = 0;;
return it;
}
template < typename T >
void List1< T >::push_front( const T& val )
{
Node* n = new Node;
n->value = val;
if( head == 0 ) tail = n;
n->next = head;
head = n;
++len;
}
template < typename T >
void List1< T >::push_back( const T& val )
{
Node* n = new Node;
n->value = val;
n->next = 0;
if( head != 0 )
{
tail->next = n;
tail = n;
}
else head = tail = n;
++len;
}
/****************************************************************
* This function removes the Node pointed to by the head pointer
* and pushs that Node onto the front of the list that is passed
* in as a parameter.
****************************************************************/
template < typename T >
void List1< T >::pop_front_push_other_front( List1< T >& y )
{
if( head )
{
Node* tmp = head;
head = head->next;
y.push_front( tmp->value);
delete tmp;
--len;
if( !len ) tail = 0;
}
}
/****************************************************************
* This function takes a singly linked list in as a parameter,
* appends it to the end of the current singly linked list, sets
* the appropriate private members, and clears the other list.
****************************************************************/
template < typename T >
void List1< T >::append_clear_other( List1< T >& y )
{
if( head )
{
tail->next = y.head;
tail = y.tail;
len += y.len;
}
else
{
head = y.head;
tail = y.tail;
len = y.len;
}
y.head = y.tail = 0;
y.len = 0;
}
////////////////////////////////////////////////////////////////////////////////
// End ... definitions of List member functions
////////////////////////////////////////////////////////////////////////////////
// Utility function to quick sort a List1< T > ... (uses function pointers)
// 1. needs a 'compare' function passed in ... here see ...
// bool ( *before )( const T&, const T& ) )
// 2. also needs TWO List1 < T > member functions defined above ...
// see example below: A.pop_front_push_other_front( pivot );
// see example below: A.append_clear_other( pivot );
// 3. also needs List1< T > copy constructor and overloaded assignment ...
// see example below: A = Abefore;
template < typename T >
void quicksort( List1 < T > & A, bool ( *before )( const T&, const T& ) )
{
List1 < T > Abefore, Aafter, pivot;
typename List1 < T >::iterator toSort, toPivot;
// sufficent recursion end condition ... since ...
// prev pass took pivot and then was sorted or split into two one (or zero) node lists
if( A.size() < 2 ) return;
// firstly, get (and remove/save) pivot for this (recursive) pass ...
A.pop_front_push_other_front( pivot );
// then get pointer to pivot value
toPivot = pivot.begin();
// now traverse the list 'A 'from begin to end and create ...
// two lists ... 'Abefore' ... and ... 'Aafter' ...
for( toSort = A.begin(); toSort != A.end(); toSort = A.begin() )
{
if( before( *toSort, *toPivot ) )
A.pop_front_push_other_front( Abefore );
else
A.pop_front_push_other_front( Aafter );
}
// now recutsively quick sort these two lists ...
quicksort( Abefore, before );
quicksort( Aafter, before );
// now reconstruct A from recursively sorted 2 pieces ...
A = Abefore; // get 'first section' ... ( needs copy ctor and overloaded = )
A.append_clear_other( pivot ); // add pivot back to its 'mid' place ...
A.append_clear_other( Aafter ); // append 'last section'
}
// Utility functions to bubble sort a List1< T > ...
// Simple bubble sort ... uses a similar method as used to bubble sort an array
// Uses function pointer to handle different compare functions passed in
template < typename T >
void bsort( List1<T>& a, bool ( *yourCmp )( const T&, const T& ) )
{
// traverse list, n-1 compares ...
int j, new_size = a.size();
typename List1< T >::iterator it, it2;
T tmp;
bool swap;
do
{
swap = false;
for( j = 1, it2 = a.begin(); j < new_size; ++j )
{
it = it2;
++it2; // advance to next element in to compare it ...
if( yourCmp( *it2, *it ) ) // then ... swap values at nodes
{
tmp = *it;
*it = *it2;
*it2 = tmp;
swap = true;
}
}
-- new_size;
}
while( swap );
}
// Simple bubble sort using a similar method as used to bubble sort an array
// Uses function pointer to handle different compare functions passed in
template < typename T >
void bsort
(
List1< T >& s,
typename List1< T >::iterator a, typename List1< T >::iterator b,
bool ( *yourCmp )( const T&, const T& )
)
{
// traverse list ... n-1 compares each pass, with --n before next pass
// done if no swap ...
// first .. count the len of this sub-list to be sorted
int j, new_size = 0;
typename List1< T >::iterator it, it2;
T tmp;
for( it = a; it != s.end(); ++it )
{
++new_size; // count the len of this sub-list to be sorted ...
if( it == b ) break;
}
// now can do bubble sort ... in simple similar manner as per an array
bool swap;
do
{
swap = false; // if swap not set to true on this pass ... then done
for( j = 1, it2 = a; j < new_size; ++j )
{
it = it2;
++it2; // advance to next element in ... to compare it
if( yourCmp( *it2, *it ) ) // then ... swap values at nodes
{
tmp = *it;
*it = *it2;
*it2 = tmp;
swap = true;
}
}
// decrement before next pass since top element(s) already in sorted order
-- new_size;
}
while( swap );
}
#endif
// classList1_test.cpp // 2011-12-19 //
#include <iostream>
// a template class for a single-link linked ...
// with template functions for bsort ... (a bubble sort)
// ... call like this: bsort( yourList, ascendingCmp );
// and a template function quicksort ... (a quick sort)
// ... call like this: quicksort( yourList, ascendingCmp );
#include "classList1.h" // has include <string>
// Compare function 'ascendingCmp' handed to bsort ...
template < typename T >
bool ascendingCmp( const T& a, const T& b )
{
return a < b;
}
template < typename T >
bool descendingCmp( const T& a, const T& b )
{
return a > b;
}
int main( int argc, char *argv[] )
{
using std::string;
using std::cout;
using std::endl;
using std::flush;
using std::cin;
List1< string > s1;
s1.push_back( "Hi" );
s1.push_back( "there" );
s1.push_back( "my" );
s1.push_back( "friend" );
s1.push_back( "Bob" );
s1.push_back( "Attfield" );
List1< string >::iterator it;
cout << "After " << s1.size()
<< " calls to s1.push_back( \"cppStr\" ) ... s1 =\n";
for( it = s1.begin(); it != s1.end(); ++it ) cout << *it << " ";
List1< string > s2 = s1;
cout << "\n\nAfter List< string > s2 = s1 ... s2 = \n";
for( it = s2.begin(); it != s2.end(); it++ ) cout << *it << " ";
bsort( s2, ascendingCmp );
cout << "\n\nAfter bsort( s2, ascendingCmp ) ... s2 = \n";
for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
s1 = s2;
cout << "\n\nAfter s1 = s2 ... s1 = \n";
for( it = s1.begin(); it != s2.end(); it++ ) cout << *it << " ";
quicksort( s1, ascendingCmp );
cout << "\n\nquicksort( s1, ascendingCmp ), s1 = \n";
for( it = s1.begin(); it != s1.end(); ++it ) cout << *it << " ";
quicksort( s2, descendingCmp );
cout << "\n\nquicksort( s2, descendingCmp ), s2 = \n";
for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
cout << "\nPress 'Enter' to continue ... " << flush;
cin.get();
}
// classList2.h // 2012-01-04 //
// a template class for a double-link linked list...
// with template functions for bsort (an array like bubble sort, swaps values)
// and a template function qSort2 (an array like quick sort, swaps values)
// and a member function for isort (insert sort) and isort_insert
#ifndef CLASSLIST2_H
#define CLASSLIST2_H
#include <string> // should include this ...
////////////////////////////////////////////////////////////////////////////////
template < typename T >
class List
{
struct Node; // forward declaration ...
public:
List() : head(0), tail(0), len(0) {}
~List() { clear(); }
List( const List< T >& ); // copy ctor ...
List< T >& operator = ( const List< T >& ); // overloaded operator =
int size() const { return len; }
void clear();
class iterator
{
friend class List< T >; // to give class List access to private ptr
public:
iterator( Node* p = 0, Node* t = 0 ) : ptr(p), ptl(t) {}
iterator& operator ++ () { ptr = ptr->next; return *this; }
iterator& operator ++ ( int dummy ) { ptr = ptr->next; return *this; }
iterator& operator -- () { if( ptr == 0 ) ptr = ptl;
else ptr = ptr->prev; return *this; }
iterator& operator -- ( int dummy ) { if( ptr == 0 ) ptr = ptl;
else ptr = ptr->prev; return *this; }
bool operator != (const iterator & it2) const { return ptr != it2.ptr; }
bool operator == (const iterator & it2) const { return ptr == it2.ptr; }
T operator * () const { return ptr->value; }
T& operator * () { return ptr->value; }
private:
Node* ptr; // cur
Node* ptl; // tail
};
iterator begin() { iterator it( head, tail ); return it; }
iterator end() { iterator it( 0, tail ); return it; }
void push_front( const T& );
void push_back( const T& );
void isort_insert( const T& e, bool ( *yourCmp )( const T&, const T& ) );
void isort( bool ( *yourCmp )( const T&, const T& ) );
bool isSorted( bool ( *yourCmp )( const T&, const T& ) );
private:
void insert_sorted( typename List< T >::Node*& pHead,
typename List< T >::Node*& pTail,
typename List < T >::Node* pNewNode,
bool ( *yourCmp )( const T&, const T& ) );
struct Node
{
T value;
Node* next;
Node* prev;
} *head, *tail ;
int len;
} ;
////////////////////////////////////////////////////////////////////////////////
// begin class member definitions ...
// copy ctor
template < typename T >
List< T >::List( const List< T >& old_list )
{
head = tail = 0;
len = 0;
for( Node* n = old_list.head; n != 0; n = n->next )
push_back( n->value );
}
// overloaded operator =
template < typename T >
List< T >& List< T>::operator = ( const List< T >& old_list )
{
if( this != &old_list )
{
clear();
for( Node* n = old_list.head; n != 0; n = n->next )
push_back( n->value );
}
return *this;
}
template < typename T >
void List< T >::clear()
{
for( Node* tmp = head; head != 0; tmp = head )
{
head = head->next;
delete tmp;
}
tail = 0;
len = 0;
}
template < typename T >
void List< T >::push_front( const T& val )
{
Node* n = new Node;
n->value = val;
n->prev = 0;
n->next = head;
if( head ) head->prev = n;
else tail = n;
head = n;
++len;
}
template < typename T >
void List< T >::push_back( const T& val )
{
Node* n = new Node;
n->value = val;
n->next = 0;
n->prev = tail;
if( head ) tail->next = n;
else head = n;
tail = n;
++len;
}
template < typename T >
bool List< T >::isSorted( bool ( *yourCmp )( const T&, const T& ) )
{
typename List< T >::Node* i;
typename List< T >::Node* j;
for( j = i = head ; i != 0; i = j )
{
j = j->next;
if( j && yourCmp( j->value, i->value ) ) return false;
}
// else ...
return true;
}
//////////////////////////////// BEGIN ISORT's /////////////////////////////////
// call this function only if pre-sorted in appropriate order ...
template < typename T >
void List< T >::isort_insert( const T& e, bool ( *yourCmp )( const T&, const T& ) )
{
typename List< T >::Node* n = new Node;
n->value = e;
insert_sorted( head, tail, n, yourCmp );
++len;
}
// insert a new node in a list with its node data in proper order ...
template < typename T >
void List< T >::insert_sorted( typename List < T >::Node*& pHead,
typename List < T >::Node*& pTail,
typename List < T >::Node* pNewNode,
bool ( *yourCmp )( const T&, const T& ) )
{
// First handle most likely cases where new node is NOT first element ...
if( pHead != 0 && yourCmp(pNewNode->value, pHead->value) ) // pNewNode->value >= pHead->value
{
// If here ... search the list for the right location
typename List< T >::Node* q = pHead; // Get a working copy of pHead in q
// Start comparing with element AFTER 'q' ... i.e. the 'next in'
while( q->next != 0 && yourCmp(pNewNode->value, q->next->value) ) // pNewNode->value >= q->next->value
q = q->next; // Traverse the list ...
// Ok, insert after 'q' by 're-nexting' the pointers ...
// ( Includes inserting at end position ... where q->next is NULL )
// for A->B and A<-B to become A->N->B ... and ... A<-N<-B
pNewNode->next = q->next; // first insert/link ... N->B
pNewNode->prev = q; // then link ... A<-N
if( q->next ) q->next->prev = pNewNode; // then link ... N<-B
else pTail = pNewNode;
q->next = pNewNode; // and now link ... A->N
}
else // becomes the first element ...
{
pNewNode->prev = 0;
pNewNode->next = pHead; // old pHead becomes 2nd in list
if( pHead ) pHead->prev = pNewNode;
else pTail = pNewNode;
pHead = pNewNode; // and this new node becomes the head of the list
}
}
// insert sort a whole list ...
template < typename T >
void List< T >::isort( bool ( *yourCmp )( const T&, const T& ) )
{
// Note: pNewHead MUST be 0 to start ...
typename List< T >::Node *pTmp, *pHead = head, *pNewHead = 0, *pNewTail = 0;
while( pHead != 0 ) // take each node from old list and insert in new
{
pTmp = pHead; // get 'this' node ...
pHead = pHead->next; // move 'start' up one, to be ready for next node
insert_sorted( pNewHead, pNewTail, pTmp, yourCmp ); // insert 'this' pTmp node
}
head = pNewHead;
tail = pNewTail;
} ////////////////////////////// END ISORT 's //////////////////////////////////
// end of class member definitions
////////////////////////////////////////////////////////////////////////////////
// Utility function to bubble sort a List< T > ...
// Uses function pointer to handle different compare functions passed in
template < typename T >
void bsort( List<T>& a, bool ( *yourCmp )( const T&, const T& ) )
{
// traverse list, n-1 compares ...
int j, new_size = a.size();
typename List< T >::iterator it, it2;
T tmp;
bool swap;
do
{
swap = false;
for( j = 1, it2 = a.begin(); j < new_size; ++j )
{
it = it2;
++it2; // advance to next element in to compare it ...
if( yourCmp( *it2, *it ) ) // then ... swap values at nodes ...
{
tmp = *it;
*it = *it2;
*it2 = tmp;
swap = true;
}
}
-- new_size;
}
while( swap );
}
// simple bubble sort ... uses a similar method as used to bubble sort an array
// Uses function pointer to handle different compare functions passed in
template < typename T >
void bsort( List< T >& s,
typename List< T >::iterator a,
typename List< T >::iterator b,
bool ( *yourCmp )( const T&, const T& ) )
{
// traverse list ... n-1 compares each pass, with --n before next pass
// done if no swap ...
// first .. count the len of this sub-list to be sorted
int j, new_size = 0;
typename List< T >::iterator it, it2 = s.end();
T tmp;
if( b == it2 ) --b;
for( it = a; it != it2; ++it )
{
++new_size; // count the len of this sub-list to be sorted ...
if( it == b ) break;
}
// now can do bubble sort ... in simple similar manner as per an array ...
bool swap;
do
{
swap = false; // if swap not set to true on this pass ... then done
for( j = 1, it2 = a; j < new_size; ++j )
{
it = it2;
++it2; // advance to next element in ... to compare it
if( yourCmp( *it2, *it ) ) // then ... swap values at nodes
{
tmp = *it;
*it = *it2;
*it2 = tmp;
swap = true;
}
}
// decrement before next pass since top element(s) already sorted ...
-- new_size;
}
while( swap );
}
////////////////////////////////////////////////////////////////////////////////
// a simple recursive quick sort of a list ...
// patterned after ...
// a fairly efficent recursive quick sort of an array
// Note: this quick sort needs to be able to traverse the list ----> and <----
// which implies it will only work with a double-link linked-list
template< typename T >
void qSort2It
(
typename List< T >::iterator old_lft,
typename List< T >::iterator old_rht,
bool ( *myCmp )( const T&, const T& )
)
{
typename List< T >::iterator lft = old_lft, rht = old_rht;
int len = 1;
while( lft != rht ) // find mid element ...
{
--rht;
++len;
if( lft != rht ) ++lft, ++len;
}
T tmp, comp = *rht; // get this comp element ...
lft = old_lft, rht = old_rht; // reset now that found above
bool c1 = true, c2 = true;
do
{
while( myCmp(*lft, comp) ) ++lft, --len; if( lft == old_rht ) c1 = false;
while( myCmp(comp, *rht) ) --rht, --len; if( old_lft == rht ) c2 = false;
if( len > 0 ) // if(lft <= rht) // swap ...
{
tmp = *lft;
*lft = *rht;
*rht = tmp;
++lft, --len;
if( lft == old_rht ) c1 = false;
--rht, --len;
if( old_lft == rht ) c2 = false;
}
}while( len > 0 ); // while( lft <= rht );
//if( old_lft < rht )
if( c2 ) qSort2It( old_lft, rht, myCmp );
//if( lft < old_rht )
if( c1 ) qSort2It( lft, old_rht, myCmp );
}
// must pass in two valid iterators in correct left to right order ...
template< typename T >
void qSort2
(
List< T >& a,
typename List< T >::iterator old_lft,
typename List< T >::iterator old_rht,
bool ( *myCmp )( const T&, const T& )
)
{
if( a.size() < 2 ) return;
if ( old_rht == a.end() ) --old_rht;
qSort2It( old_lft, old_rht, myCmp );
}
#endif
// classList2_test.cpp // 2011-12-22 // a test of classList2.h //
#include <iostream>
// a template class for a single-link linked ...
// with a template function for bsort ... (a bubble sort) ... call like this:
// bsort( yourList, ascendingCmp );
// and a template function for bsort ... (a bubble sort) ... call like this:
// bsort( yourList, yourList.begin(), yourList.end(), ascendingCmp );
// and a template function qSort2 ... (a quick sort) ... call like this:
// qSort2( yourList, yourList.begin(), yourList.end(), ascendingCmp );
// and a member function for isort ... (an insert sort) ... and isort_inserted
// yourList.isort( isortCmp ) ... or ... yourList.isort_insert( new_obj );
#include "classList2.h" // has include <string>
#define push_x push_back
#define x "back"
// Compare function 'ascendingCmp' handed to bsort ...
template < typename T >
bool ascendingCmp( const T& a, const T& b )
{
return a < b;
}
template < typename T >
bool descendingCmp( const T& a, const T& b )
{
return a > b;
}
template < typename T >
bool isortCmp( const T& a, const T& b )
{
return a >= b;
}
template < typename T >
bool isortCmpDwn( const T& a, const T& b )
{
return a <= b;
}
int main( int argc, char *argv[] )
{
using std::string;
using std::cout;
using std::endl;
using std::flush;
using std::cin;
string test[] = { "Hi", "there", "my", "friend", "Bob", "Attfield" };
List< string > s1;
const int size = sizeof test / sizeof test[0];
for( int i = 0; i < size; ++i ) s1.push_x( test[i] );
List< string >::iterator it;
cout << "After " << size
<< " calls to s1.push_" << x << "( test[i] ) ... s1 =\n";
for( it = s1.begin(); it != s1.end(); ++it ) cout << *it << " ";
List< string > s2 = s1;
cout << "\n\nAfter List< string > s2 = s1 ... s2 = \n";
for( it = s2.begin(); it != s2.end(); it++ ) cout << *it << " ";
s2.isort( isortCmp );
cout << "\n\nAfter s2.isort( isortCmp ) ... s2 = \n";
for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
s2.isort_insert( "old", isortCmp );
cout << "\n\nAfter s2.isort_insert( \"old\", isortCmp ) ... s2 = \n";
for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
s2.isort( isortCmpDwn );
cout << "\n\nAfter s2.isort( isortCmpDwn ) ... s2 = \n";
for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
s2.isort_insert( "fine", isortCmpDwn );
cout << "\n\nAfter s2.isort_insert( \"fine\", isortCmpDwn ) ... s2 = \n";
for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
s1 = s2;
cout << "\n\nAfter s1 = s2 ... s1 = \n";
for( it = s1.begin(); it != s2.end(); it++ ) cout << *it << " ";
qSort2( s1, s1.begin(), s1.end(), ascendingCmp );
cout << "\n\nqSort2( s1, s1.begin(), s1.end(), ascendingCmp ), s1 = \n";
for( it = s1.begin(); it != s1.end(); ++it ) cout << *it << " ";
qSort2( s2, s2.begin(), s2.end(), descendingCmp );
cout << "\n\nqSort2( s2, s2.begin(), s2.end(), descendingCmp ), s2 = \n";
for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
bsort( s2, s2.begin(), s2.end(), ascendingCmp );
cout << "\n\nAfter bsort( s2, s2.begin(), s2.end(), ascendingCmp ) ... s2 = \n";
for( it = s2.begin(); it != s2.end(); ++it ) cout << *it << " ";
cout << "\n\nPress 'Enter' to continue ... " << flush;
cin.get();
}