Developers Heaven Forum
Desktop Programming => C/C++ & Visual C++ => Topic started by: David on March 28, 2011, 02:42:15 AM
-
Here is a C++ template class Vector example ... similar to the Cvec example in C at this next link:
http://developers-heaven.net/forum/index.php/topic,2473.msg2740.html#msg2740
It demos push_back, enlarge, reserve, merge sort, insertion sort, find, erase ... since these are fairly common student requests. It also demonstrates friend functions that overload operators << and >> ... so you can use these to output and input Vector objects.
First the template class Vector file ... followed then by a test program.
// vector.h // // this version 2011-03-27 //
// with merge sort and insertion sort ...
#ifndef dwVECTOR_H
#define dwVECTOR_H
/* can re-set this to minimize copying and getting new memory using push_back */
#ifndef VEC_CHUNK_SIZE
#define VEC_CHUNK_SIZE 8
#endif
template < typename T >
class Vector
{
public:
Vector();
~Vector() { clear(); }
void push_back( T );
void reserve( int );
void shrink( int );
void clear();
T& operator [] (int i) { return ary[i]; }
const T& operator [] (int i) const { return ary[i]; }
int get_size() const { return size; }
int get_cap() const { return cap; }
bool get_isSorted() const { return isSorted; }
bool isSortedUp() const;
int find( T ) const; // returns index if T value present ... else -1
void erase( int ); // if int index valid, erases element there
void msort();
void isort();
private:
int cap; // capacity
int size;
bool isSorted;
T* ary;
void enlarge(); // used by push_back
void merge( int, int, int, Vector< T >& ); // used by msort ...
void my_msort( int, int, Vector< T >& );
};
template < typename T >
Vector<T>::Vector() : cap(0), size(0), isSorted(true), ary(0) {}
template < typename T >
void Vector<T>::push_back( T e )
{
if( size == cap ) enlarge();
/* now add in new Rec ... */
ary[size] = e;
++ size;
isSorted = false;
}
// new array to hold 2x's records ... copies old to new
template < typename T >
void Vector<T>::enlarge()
{
if( cap ) cap += cap; // double capacity ...
else cap = VEC_CHUNK_SIZE; // set initial capacity
T* tmp = new T[ cap ];
for( int i = size-1; i >= 0; --i ) tmp[i] = ary[i];
//for( int i = cap-1; i >= size; --i ) tmp[i] = 0;
delete [] ary;
ary = tmp; // update the base address of ary
}
template < typename T >
void Vector<T>::reserve( int newCap )
{
if( newCap > cap )
{
cap = newCap;
T* tmp = new T[ cap ];
for( int i = size-1; i >= 0; --i ) tmp[i] = ary[i];
//for( int i = cap-1; i >= size; --i ) tmp[i] = 0;
delete [] ary;
ary = tmp; // update the base address of ary
}
}
template < typename T >
void Vector<T>::shrink( int newSize )
{
if( newSize < size && newSize >= 0 ) size = newSize; // leave cap unchanged
if( size < 2 ) isSorted = true;
}
template < typename T >
void Vector<T>::clear()
{
if( ary != 0 )
{
delete [] ary;
cap = size = 0;
ary = 0;
isSorted = true;
}
}
template < typename T >
int Vector<T>::find( T value ) const // returns index if present ... else -1
{
for( int i = 0; i < size; ++i )
if( ary[i] == value ) return i;
// else if reach here ...
return -1;
}
template < typename T >
void Vector<T>::erase( int index ) // if index valid, erases element there
{
if( index < 0 || index >= size )
{
std::cout << "\nERROR! Index " << index
<< " out of range 0.." << size-1 << std::endl;
return;
}
for( int i = index; i < size-1; ++i )
ary[i] = ary[i+1]; // copy each element above, down one index, so erased
// now update size and return (by reference, since address passed in)
-- size;
}
template < typename T >
bool Vector<T>::isSortedUp() const
{
int size_ = size;
while( --size_ )
if( ary[size_] < ary[size_-1] ) return 0;
return 1;
}
/* * * * * * * * * * * * * * merge sort / isort * * * * * * * * * * * * * * * */
template < typename T >
void Vector<T>::merge( int bot, int mid, int top, Vector<T>& tmp )
{
int sz = top - bot + 1; // size of the range to be merged
int j = 0; // next open index in tmp
int h1 = bot; // next index to consider in the 1st half
int h2 = mid + 1; // next index to consider in the 2nd half
// while indexes h1 and h2 are not past their ends ...
while( h1 <= mid && h2 <= top )
{ // move the smaller element into the tmp vec...
if( ary[h1] < ary[h2] ) tmp[j++] = ary[h1++];
else tmp[j++] = ary[h2++];
}
// Note: only one of the two while loops below is executed ...
while( h1 <= mid ) tmp[j++] = ary[h1++]; // copy any remaining entries (1st half)
while( h2 <= top ) tmp[j++] = ary[h2++]; // copy any remaining entries (2nd half)
for( j = 0; j < sz; ++j ) ary[bot+j] = tmp[j]; // copy back sorted tmp vec...
}
template < typename T >
void Vector<T>::my_msort( int bot, int top, Vector& tmp )
{
if( bot == top ) return;
else
{
int mid = ( bot + top ) / 2;
my_msort( bot, mid, tmp ); // sort the first ...
my_msort( mid + 1, top, tmp ); // and the second half ...
merge( bot, mid, top, tmp ); // now merge these 2 sorted chunks
}
}
template < typename T >
void Vector<T>::msort()
{
if( isSorted ) return;
Vector<T> tmp;
tmp.reserve( size );
my_msort( 0, size-1, tmp );
isSorted = true;
}
template < typename T >
void Vector<T>::isort()
{
if( isSorted ) return;
// start with an array of just the first 2 elements (if exists)
for( int i = 1; i < size; ++i )
{
T cmp = ary[i]; // get copy of this new cmp element on each outer loop
int j = i-1; // get index of element just to the left of the above 'cmp'
// to start comparisons
while( j >= 0 && cmp < ary[j] )
{
ary[j+1] = ary[j]; // copy element 'up' ...
--j; // decrement j in preparation for next inner loop
}
ary[j+1] = cmp; // insert element at index j+1 (since j was decremented above)
}
isSorted = true;
}
#endif
-
And now the test program for the above file ...
// Vector_test1.cpp // // 2011-03-27 //
// enter data, find sum, average, msort, isort, find value, erase, show vector
// http://developers-heaven.net/forum/index.php/topic,46.0.html
#include <iostream>
#include "Vector.h"
template < typename T >
T takeIn( const char prompt[] )
{
for( ; ; ) // an example of a C/C++ forever loop ... until 'return'
{
std::cout << prompt << std::flush;
T tmp;
if( std::cin >> tmp )
{
std::cin.sync();
return tmp;
}
// else ...
std::cin.clear();
std::cin.sync();
std::cout << "Invalid input ...\n";
}
}
bool more() // defaults to 'true'/'yes' ... unless 'n' or 'N' entered
{
std::cout << "More (y/n) ? " << std::flush;
int reply = std::cin.get();
std::cin.sync();
if( reply == 'n' || reply == 'N' ) return false;
// else ...
return true;
}
template< typename T >
void show(const Vector< T >& v )
{
for( int i = 0; i < v.get_size(); ++i ) std::cout << v[i] << " ";
std::cout << std::endl;
}
template< typename T >
T sum(const Vector< T >& v )
{
T sum = 0;
for( int i = 0; i < v.get_size(); ++i ) sum += v[i];
return sum;
}
int main()
{
Vector< int > v;
do
{
int val = takeIn< int >( "Enter next integer to sum: " );
v.push_back( val );
}
while( more() );
int sum_v = sum( v );
std::cout << "\nFor " << v.get_size()
<< " numbers entered, sum_v was "
<< sum_v << " and average was "
<< (float)sum_v/v.get_size() << std::endl;
std::cout << "\nshow( v ) : "; show( v );
int last = v[ v.get_size()-1 ];
v.msort();
std::cout << "\nAfter v.msort() ... "
<< "v.isSortedUp() = " << v.isSortedUp()
<< " ... v.get_isSorted() = " << v.get_isSorted() << std::endl
<< "show( v ) : "; show( v );
int index = v.find( last );
if( index >= 0 )
{
v.erase( index );
std::cout << "\nAfter erasing " << last << " ...";
std::cout << "\nshow( v ) : "; show( v );
}
else std::cout << "\n" << last << " NOT found in Vectot.\n";
int val = takeIn< int >( "\n\nEnter a new integer before isort: " );
v.push_back( val );
v.isort();
std::cout << "After v.isort()... "
<< "v.isSortedUp()= " << v.isSortedUp()
<< " ... v.get_isSorted() = " << v.get_isSorted() << std::endl
<< "show( v ) : "; show( v );
v.shrink( 2 );
std::cout << "After v.shrink( 2 )... "
<< "v.get_cap()= " << v.get_cap()
<< " ... v.get_size() = " << v.get_size() << std::endl
<< "show( v ) : "; show( v );
v.clear();
std::cout << "\nAfter v.clear() ... "
<< "v.get_cap()= " << v.get_cap()
<< " ... v.get_size() = " << v.get_size()
<< "\n\nPress 'Enter' to continue/exit ... " << std::flush;
std::cin.get(); // keep 'Window' open until 'Enter' key is pressed ...
}
-
A little upgrade ... with insert and pack added ... and more standard function names like size() and capacity() ...
AND NOW Iterators ...
// Vector_test2.cpp // // 2013-06-15 //
// enter data, find sum, average, msort, isort, find value, erase, show vector
// http://developers-heaven.net/forum/index.php/topic,46.0.html
#include <iostream>
#include <string>
#include "Vector2.h"
template < typename T >
T takeIn( const char prompt[] )
{
for( ; ; ) // an example of a C/C++ forever loop ... until 'return'
{
std::cout << prompt << std::flush;
T tmp;
if( std::cin >> tmp )
{
std::cin.sync();
return tmp;
}
// else ...
std::cin.clear();
std::cin.sync();
std::cout << "Invalid input ...\n";
}
}
bool more() // defaults to 'true'/'yes' ... unless 'n' or 'N' entered
{
std::cout << "More (y/n) ? " << std::flush;
int reply = std::cin.get();
std::cin.sync();
if( reply == 'n' || reply == 'N' ) return false;
// else ...
return true;
}
template< typename T >
void show(const Vector< T >& v )
{
for( int i = 0; i < v.size(); ++i ) std::cout << v[i] << " ";
std::cout << std::endl;
}
template< typename T >
T sum(const Vector< T >& v )
{
T sum = 0;
for( int i = 0; i < v.size(); ++i ) sum += v[i];
return sum;
}
int main()
{
Vector< int > v;
do
{
int val = takeIn< int >( "Enter next integer to sum: " );
v.push_back( val );
}
while( more() );
int sum_v = sum( v );
std::cout << "\nFor " << v.size()
<< " numbers entered, sum_v was "
<< sum_v << " and average was "
<< (float)sum_v/v.size() << std::endl;
Vector< int >::iterator it;
std::cout << "showing v with for( it = v.begin(); it != v.end() ; ++it ) ...\n";
for( it = v.begin(); it != v.end() ; ++it )
std::cout << *it << " ";
std::cout << std::endl;
Vector< int >::reverse_iterator rit;
std::cout << "showing v with for( rit = v.rbegin(); rit != v.rend() ; ++rit ) ...\n";
for( rit = v.rbegin(); rit != v.rend() ; ++rit )
std::cout << *rit << " ";
std::cout << std::endl;
int last = v[ v.size()-1 ];
v.msort();
std::cout << "After v.msort() ... "
<< "v.isSortedUp() = " << v.isSortedUp()
<< " ... v.get_isSorted() = " << v.get_isSorted() << std::endl
<< "show( v ) : "; show( v );
int index = v.find( last );
if( index >= 0 )
{
v.erase( index );
std::cout << "After erasing " << last << " ...";
std::cout << "\nshow( v ) : "; show( v );
}
else std::cout << "\n" << last << " NOT found in Vectot.\n";
int val = takeIn< int >( "\n\npush_back a new integer and then call isort: " );
v.push_back( val );
v.isort();
std::cout << "After v.isort()... "
<< "v.isSortedUp()= " << v.isSortedUp()
<< " ... v.get_isSorted() = " << v.get_isSorted() << std::endl
<< "show( v ) : "; show( v );
v.resize( 20 );
std::cout << "After v.resize( 20 )... "
<< "v.capacity()= " << v.capacity()
<< " ... v.size() = " << v.size() << std::endl
<< "show( v ) : "; show( v );
v.resize( 2 );
std::cout << "After v.resize( 2 )... "
<< "v.capacity()= " << v.capacity()
<< " ... v.size() = " << v.size() << std::endl
<< "show( v ) : "; show( v );
Vector < int > v2 = v;
std::cout << "After Vector v2 = v ... "
<< "v2.capacity()= " << v2.capacity()
<< " ... v2.size() = " << v2.size() << std::endl
<< "show( v2 ) : "; show( v2 );
v.clear();
std::cout << "\nAfter v.clear() ... "
<< "v.capacity()= " << v.capacity()
<< " ... v.size() = " << v.size() << std::endl;
v2 = v;
std::cout << "After v2 = v ... "
<< "v2.capacity()= " << v2.capacity()
<< " ... v2.size() = " << v2.size() << std::endl;
using std::string;
Vector <string> v3;
string iAry[] = { "the", "fat", "cat", "was", "wearing", "a", "tiny", "hat" };
v3 = Vector <string> ( iAry, iAry + sizeof(iAry)/sizeof(string) );
std::cout << "\nAfter "
<< "v3 = Vector <string> ( iAry, iAry + sizeof(iAry)/sizeof(string) )...\n"
<< "v3.capacity()= " << v3.capacity()
<< " ... v3.size() = " << v3.size() << std::endl
<< "show( v3 ) : "; show( v3 );
v3.msort();
std::cout << "\nAfter calling v3.msort ... "
<< "v3.capacity()= " << v3.capacity()
<< " ... v3.size() = " << v3.size() << std::endl
<< "show( v3 ) : "; show( v3 );
std::cout << "\nPress 'Enter' to continue/exit ... " << std::flush;
std::cin.get(); // keep 'Window' open until 'Enter' key is pressed ...
}
// classVector2_demo.cpp // // this version 2012-05-24 //
// with merge sort and insertion sort ... and added ...
// resize, pack ... and ...
// size constructor,
// copy constuctor, array constructor and overloaded operator=
#include "Vector2.h" // includes <iostream>
#include <fstream>
using namespace std;
template < typename T >
ostream& operator << ( ostream& os, const Vector< T >& v )
{
int size = v.size();
for( int i = 0; i < size; ++ i ) os << ' ' << v[i];
os << " :: size = " << v.size() << " :: capacity = " << v.capacity();
return os;
}
bool reverseCmp( const int& a, const int& b )
{
return a > b;
}
int main()
{
int ary[] = { 9, 8, 6, 0, 1, 4, 7, 3, 2, 5 }; // get some test data ...
// select Vector constructor for an (int) array passed in
Vector < int > v( ary, ary+sizeof(ary)/sizeof(ary[0]) );
cout << "Showing vector v ... \n" << v << endl;
v.msort();
cout << "After msort ... \n" << v << endl;
v.insert( 1, 3, -1 ); // insert at index 1, 3 copies of -1
cout << "After v.insert( 1, 3, -1 ) ... \n" << v << endl;
v.erase( 10, 3 ); // erase, beegin at index 1, 3 elemements ...
cout << "After v.erase( 10, 3 ) ... \n" << v << endl;
v.unique();
cout << "After v.unique() ... \n" << v << endl;
v.erase( 0 ); // erase at index 0, 1 elemement ...
cout << "After v.erase( 0 ) ... \n" << v << endl;
msort( v, reverseCmp ); // erase at index 0, 1 elemement ...
cout << "After msort( v, reverseCmp ) ... \n" << v << endl;
cout << "\nPress 'Enter' to continue/exit ... " << flush;
cin.get();
}
// example output ...
/*
Showing vector v ...
9 8 6 0 1 4 7 3 2 5 :: size = 10 :: capacity = 10
After msort ...
0 1 2 3 4 5 6 7 8 9 :: size = 10 :: capacity = 10
After v.insert( 1, 3, -1 ) ...
0 -1 -1 -1 1 2 3 4 5 6 7 8 9 :: size = 13 :: capacity = 13
After v.erase( 10, 3 ) ...
0 -1 -1 -1 1 2 3 4 5 6 :: size = 10 :: capacity = 13
After v.unique() ...
-1 0 1 2 3 4 5 6 :: size = 8 :: capacity = 13
After v.erase( 0 ) ...
0 1 2 3 4 5 6 :: size = 7 :: capacity = 13
Press 'Enter' to continue/exit ...
*/
-
This file is used by the above test programs ...
UPDATE: Now with forward and reverse iterators
// Vector2.h // // this version 2013-06-15 //
// with merge sort and insertion sort ... and added ...
// resize, pack ... and ...
// size constructor,
// copy constuctor, array constructor and overloaded operator=
#ifndef dwVECTOR_H
#define dwVECTOR_H
#include <iostream>
/* can re-set this to minimize copying and getting new memory using push_back */
#ifndef VEC_CHUNK_SIZE
#define VEC_CHUNK_SIZE 8
#endif
template < typename T >
class Vector
{
public:
Vector();
Vector( int n );
Vector( const Vector< T >& ); // copy constructor ...
Vector( const T*, const T* ); // array constructor ...
Vector<T>& operator= ( const Vector< T >& v ); // overloaded operator=
~Vector() { clear(); }
void push_back( const T& );
void reserve( int );
void resize( int );
void shrink( int );
void pack();
void clear();
T& operator [] (int i) { return ary[i]; }
const T& operator [] (int i) const { return ary[i]; }
class iterator
{
public:
iterator( T* p = 0 ) : ptr(p) {}
iterator& operator ++ () { ++ptr; return *this; }
iterator& operator ++ ( int ) { ++ptr; return *this; }
iterator& operator -- () { --ptr; return *this; }
iterator& operator -- ( int ) { --ptr; return *this; }
bool operator != (const iterator & it2) const { return ptr != it2.ptr; }
bool operator == (const iterator & it2) const { return ptr == it2.ptr; }
const T& operator * () const { return *ptr; }
T& operator * () { return *ptr; }
private:
T* ptr; // cur
} ;
iterator begin() { iterator it( ary ); return it; }
iterator end() { iterator it( ary + len ); return it; }
class reverse_iterator
{
public:
reverse_iterator( T* p = 0 ) : ptr(p) {}
reverse_iterator& operator ++ () { --ptr; return *this; }
reverse_iterator& operator ++ ( int ) { --ptr; return *this; }
reverse_iterator& operator -- () { ++ptr; return *this; }
reverse_iterator& operator -- ( int ) { ++ptr; return *this; }
bool operator != (const reverse_iterator & it2) const { return ptr != it2.ptr; }
bool operator == (const reverse_iterator & it2) const { return ptr == it2.ptr; }
const T& operator * () const { return *ptr; }
T& operator * () { return *ptr; }
private:
T* ptr; // cur
} ;
reverse_iterator rbegin() { reverse_iterator it( ary + len-1 ); return it; }
reverse_iterator rend() { reverse_iterator it( ary-1 ); return it; }
int size() const { return len; }
int capacity() const { return cap; }
bool get_isSorted() const { return isSorted; }
void set_isSorted() { isSorted = true; }
bool isSortedUp() const;
int find( T ) const; // returns index if T value present ... else -1
void erase( int ); // if int index valid, erases element there
void erase( int, int ); // if int index valid, erases n elements there
void insert( int, int, const T& );
void msort();
void isort();
void unique();
bool isUnique() const ;
private:
int cap; // capacity
int len;
bool isSorted;
T* ary;
void enlarge(); // used by push_back
void merge( int, int, int, Vector< T >& ); // used by msort ...
void my_msort( int, int, Vector< T >& );
};
// definitions ...
template < typename T >
Vector< T >::Vector() : cap(0), len(0), isSorted(true), ary(0) {}
template < typename T >
Vector< T >::Vector( int n ) : cap(0), len(0), isSorted(true), ary(0)
{
if( n > 0 )
{
cap = len = n;
if( len > 1 ) isSorted = false;
ary = new T[size];
for( int i = 0; i < len; ++i ) ary[i] = T(0);
}
}
template < typename T >
Vector< T >::Vector( const Vector< T > & v ) // copy constructor ...
{
cap = v.cap;
len = v.len;
isSorted = v.isSorted;
ary = new T[cap];
for( int i = 0; i < len; ++i ) ary[i] = v.ary[i];
}
template < typename T >
Vector< T >::Vector( const T* a, const T* b ) // array constructor ... NOTE! b is one past last element
{
len = cap = b-a;
isSorted = false;
ary = new T[cap];
for( int i = 0; i < len; ++i ) ary[i] = a[i];
}
template < typename T >
Vector< T >& Vector< T >::operator= ( const Vector< T >& v ) // overloaded operator=
{
if( this != &v )
{
delete [] ary;
cap = v.cap;
len = v.len;
isSorted = v.isSorted;
ary = new T[cap];
for( int i = 0; i < len; ++i ) ary[i] = v.ary[i];
}
return *this;
}
template < typename T >
void Vector< T >::push_back( const T& e )
{
if( len == cap ) enlarge();
/* now add in new Rec ... */
ary[len] = e;
++ len;
isSorted = false;
}
// new array to hold 2x's records ... copies old to new
template < typename T >
void Vector< T >::enlarge()
{
if( cap ) cap += cap; // double capacity ...
else cap = VEC_CHUNK_SIZE; // set initial capacity
T* tmp = new T[ cap ];
for( int i = len-1; i >= 0; --i ) tmp[i] = ary[i];
//for( int i = cap-1; i >= len; --i ) tmp[i] = 0;
delete [] ary;
ary = tmp; // update the base address of ary
}
template < typename T >
void Vector< T >::reserve( int newCap )
{
if( newCap > cap )
{
cap = newCap;
T* tmp = new T[ cap ];
for( int i = len-1; i >= 0; --i ) tmp[i] = ary[i];
delete [] ary;
ary = tmp; // update the base address of ary
}
}
template < typename T >
void Vector< T >::resize( int newSize )
{
if( newSize > len )
{
reserve( newSize );
for( int i = cap-1; i >= len; --i ) ary[i] = T(0);
len = newSize;
isSorted = false;
}
else if( newSize < len )
{
shrink( newSize );
//pack(); // ? //
}
}
template < typename T >
void Vector< T >::shrink( int newSize )
{
if( newSize < len && newSize >= 0 ) len = newSize; // leave cap unchanged
if( len < 2 ) isSorted = true;
}
template < typename T >
void Vector< T >::pack()
{
if( len < cap )
{
cap = len;
T* tmp = new T[cap];
for( int i = len-1; i >= 0; --i ) tmp[i] = ary[i];
delete [] ary;
ary = tmp; // update address ...
}
}
template < typename T >
void Vector< T >::clear()
{
if( ary != 0 )
{
delete [] ary;
cap = len = 0;
ary = 0;
isSorted = true;
}
}
template < typename T >
int Vector< T >::find( T value ) const // returns index if present ... else -1
{
for( int i = 0; i < len; ++i )
if( ary[i] == value ) return i;
// else if reach here ...
return -1;
}
template < typename T >
void Vector< T >::erase( int index ) // if index valid, erases element there
{
if( ! len )
{
std::cout << "\nERROR! Vector empty." << std::endl;
return;
}
//else ...
if( index < 0 || index >= len )
{
std::cout << "\nERROR! Index " << index
<< " out of range 0.." << len-1 << std::endl;
return;
}
// else ...
for( int i = index; i < len-1; ++i )
ary[i] = ary[i+1]; // copy each element above, down one index, so erased
// now update len for 'this' vector object ...
-- len;
}
template < typename T >
void Vector< T >::erase( int index, int num ) // if index valid, erases n elements there
{
if( ! len )
{
std::cout << "\nERROR! Vector empty." << std::endl;
return;
}
//else ...
if( index < 0 || index >= len )
{
std::cout << "\nERROR! Index " << index
<< " out of range 0.." << len-1 << std::endl;
return;
}
//else ...
if( num > len - index )
{
num = len - index;
std::cout << "\nERROR! num to erase " << num
<< " out of range 0.." << len-index << std::endl;
return;
}
// else ...
for( int i = index; i < len-num; ++i )
ary[i] = ary[i+num]; // copy nth element above, down n places, so erased
// now update len for 'this' vector object ...
len -= num;
}
// default is push_front one '0' value element
template < typename T > // assumes pos >= 0, num > 0
void Vector< T >::insert( int pos = 0, int num = 1, const T& val = T(0) )
{
if( pos < 0 || num < 1 )
{
std::cout << "\nERROR! Index must be >= 0 and num must be > 1 \n";
return;
}
if( cap < len + num ) reserve( len + num ); // updates cap
if( pos > cap-num ) pos = len; // just add in ... at end ...
else if( pos < len ) // shift last 'len-pos' elements up num places ....
{
int top = len + num - 1;
for( int i = 0; i < len-pos; ++i ) { ary[top] = ary[top-num]; --top; }
}
for( int i = 0; i < num; ++ i ) ary[pos+i] = val; // insert val's
len += num; // update len
isSorted = false;
}
template < typename T >
bool Vector< T >::isSortedUp() const
{
int sizeTmp = len;
while( --sizeTmp )
if( ary[sizeTmp] < ary[sizeTmp-1] ) return false;
return true;
}
/* * * * * * * * * * * * * * merge sort / isort * * * * * * * * * * * * * * * */
template < typename T >
void Vector< T >::merge( int bot, int mid, int top, Vector< T >& tmp )
{
int sz = top - bot + 1; // len of the range to be merged
int j = 0; // next open index in tmp
int h1 = bot; // next index to consider in the 1st half
int h2 = mid + 1; // next index to consider in the 2nd half
// while indexes h1 and h2 are not past their ends ...
while( h1 <= mid && h2 <= top )
{ // move the smaller element into the tmp vec...
if( ary[h1] < ary[h2] ) tmp[j++] = ary[h1++];
else tmp[j++] = ary[h2++];
}
// Note: only one of the two while loops below is executed ...
while( h1 <= mid ) tmp[j++] = ary[h1++]; // copy any remaining entries (1st half)
while( h2 <= top ) tmp[j++] = ary[h2++]; // copy any remaining entries (2nd half)
for( j = 0; j < sz; ++j ) ary[bot+j] = tmp[j]; // copy back sorted tmp vec...
}
template < typename T >
void Vector< T >::my_msort( int bot, int top, Vector< T >& tmp )
{
if( bot == top ) return;
else
{
int mid = ( bot + top ) / 2;
my_msort( bot, mid, tmp ); // sort the first ...
my_msort( mid + 1, top, tmp ); // and the second half ...
merge( bot, mid, top, tmp ); // now merge these 2 sorted chunks
}
}
template < typename T >
void Vector< T >::msort()
{
if( isSorted ) return;
if( len > 1 )
{
Vector< T > tmp;
tmp.reserve( len );
my_msort( 0, len-1, tmp );
isSorted = true;
}
}
template < typename T >
void Vector< T >::isort()
{
if( isSorted ) return;
// start with an array of just the first 2 elements (if exists)
for( int i = 1; i < len; ++i )
{
T cmp = ary[i]; // get copy of this new cmp element on each outer loop
int j = i-1; // get index of element just to the left of the above 'cmp'
// to start comparisons
while( j >= 0 && cmp < ary[j] )
{
ary[j+1] = ary[j]; // copy element 'up' ...
--j; // decrement j in preparation for next inner loop
}
ary[j+1] = cmp; // insert element at index j+1 (since j was decremented above)
}
isSorted = true;
}
/* * * * * * * * * * * * * * merge sort / isort * * * * * * * * * * * * * * * */
template < typename T >
void Vector< T >::unique()
{
if( !isSorted ) msort();
int i = 0;
for( int j = 1; j < len ; ++j )
{
if( ary[i] != ary[j] )
{
++i;
if( i != j ) ary[i] = ary[j];
}
}
len = ++i;
}
template < typename T >
bool Vector< T >::isUnique() const
{
if( !isSorted ) msort();
for( int i = len-1; i > 0; --i )
if( ary[i] == ary[i-1] ) return false;
// else ...
return true;
}
template < typename T >
void merge( Vector< T >& v, int bot, int mid, int top, Vector< T >& tmp, bool (*cmp) (const T& a, const T& b ) )
{
int sz = top - bot + 1; // size of the range to be merged
int j = 0; // next open index in tmp
int h1 = bot; // next index to consider in the 1st half
int h2 = mid + 1; // next index to consider in the 2nd half
// while indexes h1 and h2 are not past their ends ...
while( h1 <= mid && h2 <= top )
{ // move the 'true' element into the tmp vec...
if( cmp(v[h1], v[h2]) ) tmp[j++] = v[h1++];
else tmp[j++] = v[h2++];
}
// Note: only one of the two while loops below is executed ...
while( h1 <= mid ) tmp[j++] = v[h1++]; // copy any remaining entries (1st half)
while( h2 <= top ) tmp[j++] = v[h2++]; // copy any remaining entries (2nd half)
for( j = 0; j < sz; ++j ) v[bot+j] = tmp[j]; // copy back sorted tmp vec...
}
template < typename T >
void my_msort( Vector< T >& v, int bot, int top, Vector < T >& tmp, bool (*cmp) (const T& a, const T& b ) )
{
if( bot == top ) return;
else
{
int mid = ( bot + top ) / 2;
my_msort( v, bot, mid, tmp, cmp ); // sort the first ...
my_msort( v, mid + 1, top, tmp, cmp ); // and the second half ...
merge( v, bot, mid, top, tmp, cmp ); // now merge these 2 sorted chunks
}
}
template < typename T >
void msort( Vector< T >& v, bool (*cmp) (const T& a, const T& b ) )
{
if( v.size() > 1 )
{
Vector< T > tmp;
int size = v.size();
tmp.reserve( size );
my_msort( v, 0, size-1, tmp, cmp );
v.set_isSorted();
}
}
#endif