Recent Posts

Pages: 1 ... 7 8 [9] 10
81
Ask the Author / Breakfast ... it's time to feed at Jesus Feet ...
« Last post by David on August 08, 2017, 07:24:53 AM »


A first rough draft to get started ...

Who IS GOD?
Every building has a builder, but the builder of all things is God. (also see: Hebrews 3:4, Genesis 1)
Note that we ALL know that every building has to have a builder ... so for this given we will all be held accountable. (See also Psalm 19, Romans 1:18-32)

When my then youngest grand-daughter was still in High School ... she asked me: 'Popa, how do you know?' My (then start to a) reply to her was like this:

How do you know that one and one are two?

How do you know if your dad is your father?

Many things are obvious ... and are 'the givens' that we all (adults) really do 'know are true' ... just like one and an other one ... we merely label the new total quantity as two ... and then adding an other ... gives us 'three' ... and so we have what we call the natural numbers. These are 'a given' ... the names we call these quantities ... and the base we use ... these are arbitrary ... but may be picked to make some math easier ... like base two for use inside modern digital computers ... or base ten, to facilitate the decimal number system and the use of powers of 10 to express very large (or very fractional) amounts.

Other things we 'know' because we 'see' them ... or we hear from honest witnesses to the event.

Other things we know from the laws of creation (forensics) ... so if the top of building hits the ground right below it at very close to free fall (in air) speed ... we know that any story about 'pan-caking' is a fraud.

God knows what we know and what we do not yet know and will hold us to account for all that we do know ... like the obvious fact that 'every building had a builder' ... so the design and highly irreducibly complex and  interdependent structures and 'engines' in His creation point to a very powerful and extremely skilled engineer.

Now since God created all things in the beginning, He can faithfully tell us some of the steps of His creation that He wants us to know ... and He has revealed them to several of His choosen vessels ... and has also promised to preserve ... and thus caused this revelation from Him to be preserved, of His Word, and His character ... in the Holy Bible ... and guided the faithful translation into many languages ... even during the 2nd and 3rd centuries following the final revelation given to the apostle John.

Who IS JESUS? (John 1:1-18, see also Isaiah 9:6,7, Isaiah 12, Isaiah 53)
In the beginning was the Word, and the Word was with God, and the Word was God.
The same was in the beginning with God.
All things were made by him; and without him was not any thing made that was made.
In him was life; and the life was the light of men.
And the light shineth in darkness; and the darkness comprehended it not.
There was a man sent from God, whose name was John. The same came for a witness, to bear witness of the Light, that all men through him might believe. He was not that Light, but was sent to bear witness of that Light. That was the true Light, which lighteth every man that cometh into the world.
He was in the world, and the world was made by him, and the world knew him not.
He came unto his own, and his own received him not.
But as many as received him, to them gave he power to become the sons of God, even to them that believe on his name:
Which were born, not of blood, nor of the will of the flesh, nor of the will of man, but of God.
And the Word was made flesh, and dwelt among us, (and we beheld his glory, the glory as of the only begotten of the Father,) full of grace and truth.
John bare witness of him, and cried, saying, This was he of whom I spake, He that cometh after me is preferred before me: for he was before me.
And of his fulness have all we received, and grace for grace.
For the law was given by Moses, but grace and truth came by Jesus Christ.
No man hath seen God at any time; the only begotten Son, which is in the bosom of the Father, he hath declared him.

Why do we need a SAVIOUR? (Romans 3:23, 5:12)
For all have sinned, and come short of the glory of God;  ... Wherefore, as by one man sin entered into the world, and death by sin; and so death passed upon all men, for that all have sinned:

Who is the SAVIOUR?  (Is there more than one SAVIOUR?) (Isaiah 43:11, 44:8,  Hosea 13:4)
I, even I, am the LORD; and beside me there is no saviour. ... Fear ye not, neither be afraid: have not I told thee from that time, and have declared it? ... ye are even my witnesses. Is there a God beside me? yea, there is no God; I know not any. ... Yet I am the LORD thy God from the land of Egypt, and thou shalt know no god but me: for there is no saviour beside me. (See also: Isaiah 12, Matthew 1:21 ... call his name JESUS: {YESHUA – GOD my SAVIOUR} for he shall save his people from their sins.)

Why do we need to get to know HIM? (John 17:3, Matthew 11:28-30)
And this is life eternal, that they might know thee the only true God,
and Jesus Christ, whom thou hast sent. ... Come unto me, all ye that labour and are heavy laden, and I will give you rest. Take my yoke upon you, and learn of me; for I am meek and lowly in heart: and ye shall find rest unto your souls. For my yoke is easy, and my burden is light.

How do we (1) get to know HIM, (2) come to know that we know HIM? (John 8:31,32; 1 John 2:3)
Then said Jesus to those Jews which believed on him, If ye continue in my word,
then are ye my disciples indeed; And ye shall know the truth, and the truth shall make you free. ...
And hereby we do know that we know him, if we keep his commandments.

Does He still speak to us today? (John 10:27, 14:26)
My sheep hear my voice, ... they follow me:  ... the Comforter, which is the Holy Ghost (the Holy Spirit), whom the Father will send in my name, he shall teach you all things, and bring all things to your remembrance, whatsoever I have said unto you.
82
C/C++ & Visual C++ / Re: Binary Search Tree template class in C ++ with C bst and now Red-Black version
« Last post by David on April 15, 2017, 10:43:43 AM »
And now back to a demo of coding and using an iterator for a binary search tree ...

Firstly the .txt data file (Name it Persons.txt), then the test .cpp file ... and then the .h file ...

Enjoy :)

Code: [Select]
19570810 101440980 Bob Lamprey NY
19270624 103980155 Pinky Fellowes OR
19470314 106100903 Oliver Kringle ND
19480105 108690448 Louie Brown KS
19641028 111180924 Alan Davies UT
19710227 112200747 Bella Napster OK
19730716 112550407 Roger Stone OR
19750716 111111111 Mary Stone OR
19570504 113070570 James Mitchell TX
19401023 113220519 Jilly Aston WY
19670607 114680858 Matt Vincent MI

Now the . cpp file ...

Code: [Select]
// test_bsTreeIterator.h.cpp //  // 2017-04-16 //


#include "bsTreeIterator.h"

#include <fstream>
#include <iomanip>
#include <sstream>
#include <string>


const char* MENU =
    "Find .............. Enter :  F lastname \n"
    "Print (tree) ...... Enter :  P lastname \n"
    "eXit .............. Enter :  X";

const char* FNAME = "Persons.txt";
/*
19570810 101440980 Bob Lamprey NY
19270624 103980155 Pinky Fellowes OR
19470314 106100903 Oliver Kringle ND
19480105 108690448 Louie Brown KS
19641028 111180924 Alan Davies UT
19710227 112200747 Bella Napster OK
19730716 112550407 Roger Stone OR
19750716 111111111 Mary Stone OR
19570504 113070570 James Mitchell TX
19401023 113220519 Jilly Aston WY
19670607 114680858 Matt Vincent MI
*/


class Person
{
public:
    // ctor... (also default ctor with default values) //
    Person( int dob=0, int ssn=0, std::string fn="", std::string ln="", std::string st="" )
        : dob(dob), ssn(ssn), fname(fn), lname(ln), state(st) {}

    // re. 'ordering rule' for 'Person' objects ...
    bool operator < ( const Person& other ) const
    {
        if( lname != other.lname )
            return lname < other.lname;
        // else are the same ... so ...
        return fname < other.fname;
    }
    // re. search on names ...
    bool operator == ( const Person& other ) const
    {
        return lname == other.lname;
    }
private:
    int dob;
    int ssn;
    std::string fname;
    std::string lname;
    std::string state;
   
    // def'n of overloaded operator << for Person objects ...
    friend std::ostream& operator << ( std::ostream& os, const Person& per )
    {
        return os << std::left << std::setw(25) << per.lname + ", " + per.fname
                  << std::right << ' ' << per.state
                  << ' ' << per.dob << ' ' << per.ssn;
    }
    // to facilitate file input //
    friend std::istream& operator >> ( std::istream& is, Person& per )
    {
        is >> per.dob >> per.ssn >> per.fname >> per.lname >> per.state;
        return is;
    }
} ;


// load into (an empty) BSTree object, all records from file with name: fname
// BUT only load up to MAX elements //
bool load( const char* fname, BSTree< Person >& bst )
{
    std::ifstream fin( fname );
    if( fin )
    {
        Person tmp;
        while( fin >> tmp )
            bst.insert( tmp );
        fin.close();
        return true;
    }

    std::cout << "\nThere was a problem opening file "
              << fname << '\n';
    return false;
}

Person extractSearchInfo( const std::string& ans )
{
    std::string dummy, lname;
    std::istringstream iss( ans );
    iss >> dummy >> lname;
    return Person( 0, 0, "", lname );
}

std::string showMenuGetChoice()
{
    std::cout << MENU << "\nEnter your choice of line :  ";
    std::string line;
    getline( std::cin, line );
    return line;
}




int main()
{
    using std::cout; using std::string;
   
    BSTree< Person > tree;
    if( load( FNAME, tree ) )
    {
        cout << "There were " << tree.size() << " people in file '"
             << FNAME << "'\n";
             
        BSTree< Person >::Iterator it;
        for( it = tree.begin(); it != tree.end(); ++ it )
        {
            cout << *it << '\n';
        }
       
        for( ; ; )
        {
            char ch = 0;
            string ans = showMenuGetChoice();
            if( ans.size() ) ch = ans[0];
            Person tmp;
            switch( ch )
            {
                case 'f' : case 'F' : /* take in search info and search and report */
                    tmp = extractSearchInfo( ans );
                    if( tree.isItem( tmp, true ) ) // 'true' to show num checks //
                        cout << "Found and data on file is: "
                             << *tree.find( tmp ) << '\n';
                    else cout << "Not found.\n";
                break;
                case 'p' : case 'P' : /* talke in top of tree info and report (from there) */
                    tmp = extractSearchInfo( ans );
                    if( tree.isItem( tmp ) )
                    {
                        cout << "Found and tree (printed in order) from there is:\n";
                        tree.print_r( tree.findNode(tmp), cout, '\n' );

                    }
                    else cout << "Not found.\n";
                break;
                case 'x' : case 'X' :
                    return 0;
                break;
                default  : cout << "'" << ch << "' is NOT a valid entry here ...\n";
            }
        }
    }
}


And finally, the .h file ...

Code: [Select]
// BSTreeIterator.h //  // revised 2017-04-16 //

// this revision was on 2017-04-15 ...
// and was to make (most all) recursive methods PRIVATE
// since these meyhods are NOT to Be called by the user. //


// Using the C++ library stack in the following (nested) class iterator  ...

#ifndef BSTREEITERATOR_H
#define BSTREEITERATOR_H

#include <iostream>
#include <stack>


////////////////////////////////////////////////////////////
//
// // USAGE example:
//
// // constuct begin ('it') and end ('end') iterators:
// BSTree< objTYPE >::Iterator it = bst.begin(), end = bst.end();
//
// // print tree via *it and ++ it  ... till reach end:
// for( ; it != end ;  ++ it ) std::cout << *it << '\n';
//
////////////////////////////////////////////////////////////


template< typename T >
class BSTree
{
    // forward declaration ...
    class TreeNode;
public:
    // default ctor...
    BSTree() : root(0), len(0) {}

    // dtor...
    ~BSTree() { clean(); }
   
    void clean()
    {
std::cout << "Please wait a bit while the tree memory is freed up ... ";
        clean_r( root );

        root = 0;
        len = 0;
    }
   
    // copy ctor ... calls the recursive private method given below...
    BSTree( const BSTree& bst )
    {
        root = 0;
        len = 0;
        BSTree_r( root, bst.root );
    }

    // overloaded asignment ... calls the same recursive private method ...
    BSTree& operator = ( const BSTree& bst )
    {
        if( this != &bst )
        {
            clean(); // Note: sets root to 0 and len to 0 //
            BSTree_r( root, bst.root );
        }
        return *this;
    }

    void insert( const T& data )
    {
        insert_r( root, data ); // calls the private resursive method below ... //
        ++ len;
    }

    // A NON recursive search method ... //
    bool isItem( const T& data, bool show_count_steps = false ) const
    {
        // Return true if data is one of the items in the binary
        // sort tree to which root points.   Return false if not.
        TreeNode* cur = root;  // For "running" down the tree ...
                                    // start at the root node
        int count = 0; // so can count 'steps' ... and report if needed. //
        for( ; ; )
        {
            if( cur == 0 ) // We've fallen off the tree without finding data.
            {
                if( show_count_steps)
                    std::cout << "Number of tests was: " << ++count << '\n';
                return false;
            }
            else if( data == cur->data ) // We've found the data.
            {
                if( show_count_steps)
                    std::cout << "Number of tests was: " << ++count << '\n';
                return true;
            }
            else if( data < cur->data )
            {
                ++ count;
                // If the data occurs, it must be in the left subtree,
                // So, advance the runner down one level to the left.
                cur = cur->left;
            }
            else
            {
                ++ count;
                // If the data occurs, it must be in the right subtree.
                // So, advance the runner down one level to the right.
                cur = cur->right;
            }
        }  // end 'loop for ever' ... until return is reached //
    }
   
    TreeNode* findNode( const T& data )
    {
        return findNode( root, data ); // calls private method //
    }
   
   
    class Iterator
    {
    private:
        TreeNode* curNode;
        std::stack< TreeNode* > stkNodes;
    public:
        Iterator() : curNode(0) {}
       
        void set_curNode( TreeNode* tn ) { curNode = tn; }
       
        Iterator( TreeNode* binTree )
        {
            TreeNode* root = binTree;

            while( root )
            {
                stkNodes.push( root );
                root = root->left;
            }

            if( stkNodes.size() > 0 )
            {
                curNode = stkNodes.top();
                stkNodes.pop();
            }
            else
                curNode = 0;
        }

        T& operator * ()             { return curNode->data; }
        const T& operator * () const { return curNode->data; }


        bool operator == (const Iterator& other) const
        {
            return curNode == other.curNode;
        }

        bool operator != (const Iterator& other) const
        {
            return curNode != other.curNode;
        }

        Iterator& operator ++ ()
        {
            if( curNode->right )
            {
                stkNodes.push( curNode->right );

                if( curNode->right->left )
                    stkNodes.push( curNode->right->left );
            }

            if( stkNodes.empty() )
            {
                curNode = 0;
                return *this;
            }

            curNode = stkNodes.top();
            stkNodes.pop();

            return *this;
        }

        // Note that since, here, we are returning ONLY a copy,
        // this version does NOT permit records to be updated. //
        Iterator operator ++ ( int )
        {
            // NOTE this cpy here, i..e the correct way to implement POST ++ //
            Iterator cpy = *this;

            if( curNode->right )
            {
                stkNodes.push( curNode->right );

                if( curNode->right->left )
                    stkNodes.push( curNode->right->left );
            }

            if( stkNodes.empty() )
            {
                curNode = 0;
                return *this;
            }

            curNode = stkNodes.top();
            stkNodes.pop();
           
            return cpy;
        }
       
    } ; // END class Iterator //
   
    Iterator begin() { return Iterator( root ); }
    Iterator end() { return Iterator( 0 ); }
   
    Iterator find( const T& data )
    {
        Iterator tmp;
        tmp.set_curNode( findNode( root, data ) ); // calls the private method def'd below ... //
        return tmp;
    }
   
   
    //TreeNode* get_root() { return root; }

    size_t size() const { return len; }

/*
    size_t countNodes_r( const TreeNode< T >* cur ) const // recursive //
    {
        if( cur == 0 ) return 0;  // The tree is empty.  It contains no nodes.
        // else

        size_t count = 1;  // Start by counting the root.
        count += countNodes_r( cur->left) ;  // Add the number of nodes in the left subtree.
        count += countNodes_r( cur->right ); // Add the number of nodes in the right subtree.
        return count;  // Return the total.
    }
    size_t countNodes() const { return countNodes_r( root ); }
*/
    int maxDepth_r( const TreeNode* cur ) const
    {
        if( cur == 0 ) return 0;
        // else
       
        /* get depth of each subtree */
        int ld = maxDepth_r( cur->left );
        int rd = maxDepth_r( cur->right );

        /* return greater of two values + 1 */
        return ( ld > rd ? ld +1 : rd +1 );
    }
    int maxDepth() const // calls above method //
    {
        return maxDepth_r( root );
    }
   
    // print in order  ... used in main here so left here in public section ... //
    void print_r( const TreeNode* root, std::ostream& os = std::cout, char end = ' ' ) const
    {
        // The items in the left subtree are printed first, followed
        // by the data in the root node, followed by the items in
        // the right subtree.
        if( root == 0 )  return;         // there's nothing to print //

        print_r( root->left, os, end );  // Print items in left subtree.
        os << root->data << end;         // Print the root data.
        print_r( root->right, os, end ); // Print items in right subtree.
    }

    // print in order //
    void print( std::ostream& os = std::cout, char end = ' ' ) const
    {
        print_r( root, os, end );
    }
    void preorderPrint( std::ostream& os = std::cout, char end = ' ' ) const
    {
        preorderPrint_r( root, os, end );
    }
    void postorderPrint( std::ostream& os = std::cout, char end = ' ' ) const
    {
        postorderPrint_r( root, os, end );
    }

private:
    struct TreeNode
    {
        T data;           // The data in this node.
        TreeNode* left;   // Pointer to the left subtree.
        TreeNode* right;  // Pointer to the right subtree.
       
        // ctor...
        TreeNode( T data ) : data(data), left(0), right(0) {}
/*
        friend std::ostream& operator << ( std::ostream& os, const TreeNode& tn )
        {
            return os << tn.data;
        }
*/
    } ;

    TreeNode* root;
    size_t len;
   
    void clean_r( TreeNode* root )
    {
        if( root == 0 ) return;

        clean_r( root->left  );
        clean_r( root->right );
        delete root;
    }
   
    // Note ...traversing the passed in const bst in pre-order

    // Note that this recusive method is also called by
    // the overloaded assignment nelow //
    void BSTree_r( TreeNode*& nroot, const TreeNode* bstroot  )
    {
        if( ! bstroot ) return; // there's nothing to insert //

        insert( bstroot->data );           // insert the root data
        BSTree_r( nroot, bstroot->left );  // ...items in left subtree
        BSTree_r( nroot, bstroot->right ); // ... items in right subtree
    }
   
    // recursive method //
    void insert_r( TreeNode*& root, const T& data )
    {
        // Note that root is passed by reference since its value
        // can change in the case where the tree is empty.
        if( ! root )
        {
            // The tree is empty. Set root to point to a new node containing
            // the new data. This becomes the only node in the tree.

            root = new TreeNode( data );

            // NOTE: The left and right subtrees of root
            // are automatically set to 0 by the constructor.
            // This is important! !!! //

            return;
        }
        if( data < root->data )
            insert_r( root->left, data );
        else
            insert_r( root->right, data );
    }

    // A NON-recursive find ...
    // BUT!!! do NOT CHANGE, via this pointer,
    // the 'key' field(s) in the Mode !!! //
    TreeNode* findNode( TreeNode* cur, const T& data )
{
while( cur )
{
            if( data == cur->data )
                return cur;
if( data < cur->data )
cur = cur->left;
else
cur = cur->right;
}
return 0; // NOT found ... //
     }
     
    void preorderPrint_r( const TreeNode* root, std::ostream& os, char end ) const
    {
        if( root == 0 ) return;

        os << root->data << end; // Print the root data.
        preorderPrint_r( root->left, os, end );  // Print items in left subtree.
        preorderPrint_r( root->right ); // Print items in right subtree.
    }
    void postorderPrint_r( const TreeNode* root, std::ostream& os, char end ) const
    {
        if( root == 0 ) return;

        postorderPrint_r( root->left );  // Print items in left subtree.
        postorderPrint_r( root->right ); // Print items in right subtree.
        os << root->data << end;  // Print the root data.
    }
   
} ;

 #endif
83
C/C++ & Visual C++ / Re: Six Fast Steps to a simple template class Vector ...
« Last post by David on March 11, 2017, 06:59:04 AM »
Here in step 6, we add iterators ... and separate out our Vector class into its own .h file with suitable guards ...


So, firstly, a little test program ...

Code: [Select]
// Vector_6_iterators.cpp //  // 2017-03-10 //


// Here, in step 6, we add iterators ...
// Also, we separate out our class Vector into its own .h file
// with suitable guards //


#include "Vector.h" // includes <iostream>



// a little external print function to aid testing input/output ... //
template< typename T >
void print( const Vector< T >& v )
{
    using std::cout;
    typename Vector< T >::const_iterator it;
    for( it = v.begin(); it != v.end(); ++ it )
        cout << *it << ' ';
       
    cout << "\nThe size = " << v.size()
         << ", the capacity = " << v.capacity() << '\n';
}



int main()
{
    using std::cout;
   
    Vector< int > v, w;
    v.reserve(10);
    print( v );
   
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    v.shrink();
    cout << "After v.reserve(10) and 3 push_backs and calling v.shrink() ...\n";
    print( v );
   
    Vector< int > x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.resize(10);
    w.push_back( 9 );
    cout << "After calling w.resize(10) and w.push_back(9) ...\n";
    print( w );
   
    w.resize(6);
    cout << "After calling w.resize(6)...\n";
    print( w );

    w.resize(3);
    cout << "After calling w.resize(3)...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
   
    w.swap(v);
    cout << "After calling w.swap(v) ... print( w ) is ...\n";
    print( w );
    cout << "And print( v ) is ...\n";
    print( v );
}

And now, the file Vector.h needed above ...

Code: [Select]
// Vector.h //  // 2017-03-10 //

#ifndef VECTOR_2017_03_10_H
#define VECTOR_2017_03_10_H


#include <iostream>


const unsigned INIT_CAP = 2;

template< typename T >
class Vector
{
public:
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}

    // copy ctor ...
    Vector( const Vector< T >& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }

    // overloaded assignment ...
    Vector< T >& operator = ( const Vector< T >& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }

    // destructor ...
    ~Vector() { clear(); }

    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }

    void push_back( const T& val );

    void reserve( size_t );
    void resize( size_t );

    void swap( Vector& );
    void shrink();


    const T& operator [] ( size_t i ) const { return ary[i]; } // read only //

    // NOT const and returned by ref
    // so can set new values inside the vector //
    T& operator [] ( size_t i ) { return ary[i]; }

    size_t size() const { return len; }
    size_t capacity() const { return cap; }
   
    typedef T* iterator;
    iterator begin() { return ary; }
    iterator end() { return ary+len; }

    typedef const T* const_iterator;
    const_iterator begin() const { return ary; }
    const_iterator end() const { return ary+len; }

private:
    size_t len;
    size_t cap;
    T* ary;

    void enlarge();
} ;


// definitions //
template< typename T >
void Vector< T >::push_back( const T& val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

template< typename T >
void Vector< T >::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;

    T* tmp = new int[cap]; // get enlarged memory //

    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //

    delete [] ary; // delete OLD array memory //

    ary = tmp; // update ary pointer to point to new memory ///
}

template < typename T >
void Vector< T >::reserve( size_t newCap )
{
    if( newCap > cap )
    {
        cap = newCap;
        T* tmp = new T[ cap ];
        for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
        delete [] ary;
        ary = tmp; // update the base address of ary
    }
}

template < typename T >
void Vector< T >::resize( size_t newSize )
{
    if( newSize > len )
    {
        reserve( newSize );
        for( size_t i = len; i < cap; ++ i ) ary[i] = T();
        len = newSize;
    }
    else if( newSize < len )
        len = newSize;
}

template < typename T >
void Vector< T >::swap( Vector& vec )
{
    T* aryTmp  = vec.ary; // save start address
    size_t lenTmp = vec.len;
    size_t capTmp = vec.cap;

    vec.ary = ary;
    vec.len = len;
    vec.cap = cap;

    ary = aryTmp;
    len = lenTmp;
    cap = capTmp;
}

template < typename T >
void Vector< T >::shrink()
{
    if( len < cap )
    {
        T* tmp = new T[ len ]; // get 'right-sized' memory //
        for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i];
        delete [] ary; // now can delete old memory //
        ary = tmp; // update with the address of the new memory //
        cap = len;
    }
}

#endif

Also ... to get hints about how to add these methods

push
pop
back
empty

You can look here ...

class Vector ... and Stacks and Queues ...

http://developers-heaven.net/forum/index.php/topic,2622.0.html
84
C/C++ & Visual C++ / Re: Six Fast Steps to a simple template class Vector ...
« Last post by David on March 11, 2017, 06:43:54 AM »
Step 5 ... (again, please see comments in program ... and at the top ...)


Code: [Select]
// Vector_5_shrink_swap.cpp //  // 2017-03-10 //


// Here, in step 5, we add methods shrink and swap //


#include <iostream>


const unsigned INIT_CAP = 2;

template< typename T >
class Vector
{
public:
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}

    // copy ctor ...
    Vector( const Vector< T >& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }

    // overloaded assignment ...
    Vector< T >& operator = ( const Vector< T >& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }

    // destructor ...
    ~Vector() { clear(); }

    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }

    void push_back( const T& val );

    void reserve( size_t );
    void resize( size_t );
   
    void swap( Vector& vec );
    void shrink();

    const T& operator [] ( size_t i ) const { return ary[i]; } // read only //

    // NOT const and returned by ref
    // so can set new values inside the vector //
    T& operator [] ( size_t i ) { return ary[i]; }


    size_t size() const { return len; }
    size_t capacity() const { return cap; }

private:
    size_t len;
    size_t cap;
    T* ary;

    void enlarge();
} ;


// definitions //
template< typename T >
void Vector< T >::push_back( const T& val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

template< typename T >
void Vector< T >::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;

    T* tmp = new int[cap]; // get enlarged memory //

    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //

    delete [] ary; // delete OLD array memory //

    ary = tmp; // update ary pointer to point to new memory ///
}

template < typename T >
void Vector< T >::reserve( size_t newCap )
{
    if( newCap > cap )
    {
        cap = newCap;
        T* tmp = new T[ cap ];
        for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
        delete [] ary;
        ary = tmp; // update the base address of ary
    }
}

template < typename T >
void Vector< T >::resize( size_t newSize )
{
    if( newSize > len )
    {
        reserve( newSize );
        for( size_t i = len; i < cap; ++ i ) ary[i] = T();
        len = newSize;
    }
    else if( newSize < len )
        len = newSize;
}

template< typename T >
void Vector< T >::swap( Vector& vec )
{
    T* aryTmp  = vec.ary; // save start address
    size_t lenTmp = vec.len;
    size_t capTmp = vec.cap;

    vec.ary = ary;
    vec.len = len;
    vec.cap = cap;

    ary = aryTmp;
    len = lenTmp;
    cap = capTmp;
}

template< typename T >
void Vector< T >::shrink()
{
    if( len < cap )
    {
        T* tmp = new T[ len ]; // get 'right-sized' memory //
        for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i];
        delete [] ary; // now can delete old memory //
        ary = tmp; // update with the address of the new memory //
        cap = len;
    }
}


// a little external print function to aid testing input/output ... //
template< typename T >
void print( const Vector< T >& v )
{
    using std::cout;
   
    for( size_t i = 0; i < v.size(); ++ i )
        cout << v[i] << ' ';

    cout << "\nThe size = " << v.size()
         << ", the capacity = " << v.capacity() << '\n';
}




int main()
{
    using std::cout;
   
    Vector< int > v, w;
    v.reserve(10);
    print( v );
   
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    v.shrink();
    cout << "After v.reserve(10) and 3 push_backs and calling v.shrink() ...\n";
    print( v );
   
    Vector< int > x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.resize(10);
    w.push_back( 9 );
    cout << "After calling w.resize(10) and w.push_back(9) ...\n";
    print( w );
   
    w.resize(6);
    cout << "After calling w.resize(6)...\n";
    print( w );

    w.resize(3);
    cout << "After calling w.resize(3)...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
   
    w.swap(v);
    cout << "After calling w.swap(v) ... print( w ) is ...\n";
    print( w );
    cout << "And print( v ) is ...\n";
    print( v );
}
85
C/C++ & Visual C++ / Re: Six Fast Steps to a simple template class Vector ...
« Last post by David on March 09, 2017, 09:12:34 AM »
In step 4 ... (again please see comments at top of program)


Code: [Select]
// Vector_step4.cpp //  // 2017-03-10 //


// Here, in step 4, we add methods reserve and resize


#include <iostream>


const unsigned INIT_CAP = 2;

template< typename T >
class Vector
{
public:
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}

    // copy ctor ...
    Vector( const Vector< T >& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }

    // overloaded assignment ...
    Vector< T >& operator = ( const Vector< T >& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }

    // destructor ...
    ~Vector() { clear(); }

    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }

    void push_back( const T& val );

    void reserve( size_t );
    void resize( size_t );

    const T& operator [] ( size_t i ) const { return ary[i]; } // read only //

    // NOT const and returned by ref
    // so can set new values inside the vector //
    T& operator [] ( size_t i ) { return ary[i]; }


    size_t size() const { return len; }
    size_t capacity() const { return cap; }

private:
    size_t len;
    size_t cap;
    T* ary;

    void enlarge();
} ;


// definitions //
template< typename T >
void Vector< T >::push_back( const T& val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

template< typename T >
void Vector< T >::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;

    T* tmp = new int[cap]; // get enlarged memory //

    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //

    delete [] ary; // delete OLD array memory //

    ary = tmp; // update ary pointer to point to new memory ///
}

template < typename T >
void Vector< T >::reserve( size_t newCap )
{
    if( newCap > cap )
    {
        cap = newCap;
        T* tmp = new T[ cap ];
        for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
        delete [] ary;
        ary = tmp; // update the base address of ary
    }
}

template < typename T >
void Vector< T >::resize( size_t newSize )
{
    if( newSize > len )
    {
        reserve( newSize );
        for( size_t i = len; i < cap; ++ i ) ary[i] = T();
        len = newSize;
    }
    else if( newSize < len )
        len = newSize;
}




// a little external print function to aid testing input/output ... //
template< typename T >
void print( const Vector< T >& v )
{
    using std::cout;
   
    for( size_t i = 0; i < v.size(); ++ i )
        cout << v[i] << ' ';
       
    cout << "\nThe size = " << v.size()
         << ", the capacity = " << v.capacity() << '\n';
}



int main()
{
    using std::cout;
   
    Vector< int > v, w;
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    print( v );
   
    Vector< int > x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.reserve(10);
    w.push_back( 9 );
    cout << "After calling w.reserve(10) and w.push_back(9) ...\n";
    print( w );
   
    w.resize(6);
    cout << "After calling w.resize(6)...\n";
    print( w );

    w.resize(3);
    cout << "After calling w.resize(3)...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
}

A test to check-out a specific case of resize method ...


Code: [Select]
// Vector_4_test_resize.cpp //  // 2017-03-10 //


// Here, in step 4, we add specific test of resize //


#include <iostream>


const unsigned INIT_CAP = 2;

template< typename T >
class Vector
{
public:
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}

    // copy ctor ...
    Vector( const Vector< T >& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }

    // overloaded assignment ...
    Vector< T >& operator = ( const Vector< T >& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }

    // destructor ...
    ~Vector() { clear(); }

    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }

    void push_back( const T& val );

    void reserve( size_t );
    void resize( size_t );

    const T& operator [] ( size_t i ) const { return ary[i]; } // read only //

    // NOT const and returned by ref
    // so can set new values inside the vector //
    T& operator [] ( size_t i ) { return ary[i]; }


    size_t size() const { return len; }
    size_t capacity() const { return cap; }

private:
    size_t len;
    size_t cap;
    T* ary;

    void enlarge();
} ;


// definitions //
template< typename T >
void Vector< T >::push_back( const T& val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

template< typename T >
void Vector< T >::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;

    T* tmp = new int[cap]; // get enlarged memory //

    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //

    delete [] ary; // delete OLD array memory //

    ary = tmp; // update ary pointer to point to new memory ///
}

template < typename T >
void Vector< T >::reserve( size_t newCap )
{
    if( newCap > cap )
    {
        cap = newCap;
        T* tmp = new T[ cap ];
        for( size_t i = 0; i < len; ++i ) tmp[i] = ary[i];
        delete [] ary;
        ary = tmp; // update the base address of ary
    }
}

template < typename T >
void Vector< T >::resize( size_t newSize )
{
    if( newSize > len )
    {
        reserve( newSize );
        for( size_t i = len; i < cap; ++ i ) ary[i] = T();
        len = newSize;
    }
    else if( newSize < len )
        len = newSize;
}




// a little external print function to aid testing input/output ... //
template< typename T >
void print( const Vector< T >& v )
{
    using std::cout;

    for( size_t i = 0; i < v.size(); ++ i )
        cout << v[i] << ' ';

    cout << "\nThe size = " << v.size()
         << ", the capacity = " << v.capacity() << '\n';
}




int main()
{
    using std::cout;
   
    Vector< int > v, w;
    v.resize(10);
    print( v );
   
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    print( v );
   
    Vector< int > x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.reserve(10);
    w.push_back( 9 );
    cout << "After calling w.reserve(10) and w.push_back(9) ...\n";
    print( w );
   
    w.resize(6);
    cout << "After calling w.resize(6)...\n";
    print( w );

    w.resize(3);
    cout << "After calling w.resize(3)...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
}
86
C/C++ & Visual C++ / Re: Six Fast Steps to a simple template class Vector ...
« Last post by David on March 09, 2017, 09:10:04 AM »
In step 3 ... (again, please see comments at top of program)


Code: [Select]
// Vector_step3.cpp //  // 2017-03-10  //


// Here, in step 3, we do simple and fairly straight-foward
// update to a template class //



#include <iostream>

using namespace std;

const unsigned INIT_CAP = 2;

template< typename T >
class Vector
{
    size_t len;
    size_t cap;
    T* ary;
public:
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}
   
    // copy ctor ...
    Vector( const Vector< T >& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }
   
    // overloaded assignment ...
    Vector< T >& operator = ( const Vector< T >& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }
   
    // destructor //
    ~Vector() { clear(); }
   
    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }
   
    void push_back( const T& val );
    void enlarge();
   
    const T& operator [] ( size_t i ) const { return ary[i]; } // read only //
   
    // NOT const and returned by ref
    // so can set new values inside the vector //
    T& operator [] ( size_t i ) { return ary[i]; }
   
    size_t size() const { return len; }
    size_t capacity() const { return cap; }
} ;


// definitions //
template< typename T >
void Vector< T >::push_back( const T& val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}
template< typename T >
void Vector< T >::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;
   
    T* tmp = new int[cap]; // get enlarged memory //
   
    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //
   
    delete [] ary; // delete OLD array memory //
   
    ary = tmp; // update ary pointer to point to new memory //
}


// a little external print function to aid testing input/output ... //
template< typename T >
void print( const Vector< T >& v )
{
    for( size_t i = 0; i < v.size(); ++ i )
        cout << v[i] << ' ';
       
    cout << "\nThe size = " << v.size()
         << ", the capacity = " << v.capacity() << '\n';
}



int main()
{
    Vector< int > v, w;
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    print( v );
   
    Vector< int > x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
}
87
C/C++ & Visual C++ / Re: Six Fast Steps to a simple template class Vector ...
« Last post by David on March 09, 2017, 09:07:43 AM »
In step 2 we ... (please see comments in program at top)


Code: [Select]
// Vector_step2.cpp //  // 2017-03-09 //


// Here, in step 2,
// we add "BIG THREE" needed when you use new memory
// 1) destructor ... (that calls a clear method)
// and 2) copy ctor
// and 3) overloaded assignment //


#include <iostream>

using namespace std;

const unsigned INIT_CAP = 2;

struct Vector
{
    size_t len;
    size_t cap;
    int* ary;
   
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}
   
    // copy ctor ...
    Vector( const Vector& v )
    {
        len = v.len;
        cap = v.cap;
        ary = new int[ cap ];
        for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
    }
   
    // overloaded assignment ...
    Vector& operator = ( const Vector& v )
    {
        if( this != &v ) // if NOT same addresses //
        {
            delete [] ary; // since NOT same memory can now do this //

            len = v.len;
            cap = v.cap;
            ary = new int[ cap ];
            for( size_t i = 0; i < len; ++ i ) ary[i] = v.ary[i];
        }
        return *this;
    }
   
    // destructor //
    ~Vector() { clear(); }
   
    void clear()
    {
        delete [] ary;
        cap = len = 0;
        ary = 0; // this fix clears up case of calling destructor after calling clear //
    }
   
    void push_back( int val );
    void enlarge();
   
    int operator [] ( size_t i ) const { return ary[i]; }
   
    // so can set new values in vector //
    int& operator [] ( size_t i ) { return ary[i]; }
} ;


// definitions //

void Vector::push_back( int val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

void Vector::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;
   
    int* tmp = new int[cap]; // get enlarged memory //
   
    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //
   
    delete [] ary; // delete OLD array memory //
   
    ary = tmp; // update ary pointer to point to new memory //
}




// a little test ... //
void print( const Vector& v )
{
    for( size_t i = 0; i < v.len; ++ i )
        cout << v[i] << ' ';
       
    cout << "\nThe len = " << v.len
         << ", the cap = " << v.cap << '\n';
}


int main()
{
    Vector v, w;
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    print( v );
   
    Vector x(v); // calling copy ctor //
    cout << "After calling Vector x(v) ...\n";
    print( x );
   
    w = x; // call overloaded assignemnt //
    cout << "After calling w = x ...\n";
    print( w );
   
    w.clear();
    cout << "After calling w.clear() ...\n";
    print( w );
   
   
}
88
C/C++ & Visual C++ / Six Fast Steps to a simple template class Vector ...
« Last post by David on March 09, 2017, 09:05:50 AM »
Here is one more attempt, to demystify for beginning C++ students,  the steps to coding a simple Vector class ...



The first step will be just a Vector of int ...using a struct ... so all members are public by default.

Code: [Select]
// Vector_step1.cpp //  // 2017-03-09 //


#include <iostream>

using namespace std;

const unsigned INIT_CAP = 2;

struct Vector
{
    size_t len;
    size_t cap;
    int* ary;
   
    // default ctor ...
    Vector() :len(0), cap(0), ary(0) {}
   
    void push_back( int val );
    void enlarge();
   
    int operator [] ( size_t i ) const { return ary[i]; }
   
    // so can set new values in the vector //
    int& operator [] ( size_t i ) { return ary[i]; }
} ;


// definitions //

void Vector::push_back( int val )
{
    if( len == cap ) enlarge();
    ary[len] = val;
    ++ len;
}

void Vector::enlarge()
{
    if( cap ) cap += cap; // it gets doubled if had a value
    else cap = INIT_CAP;
   
    int* tmp = new int[cap]; // get enlarged memory //
   
    for( size_t i = 0; i < len; ++ i ) tmp[i] = ary[i]; // copy over //
   
    delete [] ary; // delete OLD aray memory //
   
    ary = tmp; // update ary pointer to point to new memory //
}




// a little test ... //
void print( const Vector& v )
{
    for( size_t i = 0; i < v.len; ++ i )
        cout << v[i] << ' ';
       
    cout << "\nThe len = " << v.len
         << ", the cap = " << v.cap << '\n';
}


int main()
{
    Vector v;
    v.push_back( 6 );
    v.push_back( 7 );
    v.push_back( 8 );
   
    print( v );
}
89
C/C++ & Visual C++ / Re: Lists ... examples of steps to a SLL (Single-Link Linked List) and a DLL ...
« Last post by David on February 14, 2017, 04:39:13 AM »
An observation to NOTE about sorting a container that already is mostly sorted ... note the following very quick ways to sort it then ...


Code: [Select]
// DDLsorts.h //  // 2017-02-13 //

#ifndef DDLSORTS_H
#define DDLSORTS_H

#include <iostream>

template < typename T >
class List
{
    struct Node
    {
        T data;
        Node* prev;
        Node* next;

        Node( const T& data = T() ) : data(data), prev(0), next(0) {}
    } ;

    Node* head;
    Node* tail;
    size_t len;

public:
    // ctor...
    List() : head(0), tail(0), len(0) {}
   
    //dtor...
    ~List() { clear(); }
   
    void clear()
    {
        while( head )
        {
            Node* del = head;
            head = head->next;
            delete del;
        }
        tail = 0;
        len = 0;
    }

    // copy ctor...
    List ( const List& other )
    {
        head = tail = 0;
        len = 0;
        for( Node* cur = other.head; cur != 0; cur = cur->next )
            push_back( cur->data );
    }

    // for ... def'n of overloaded (assignment) operator =
    // see def'n below //
    List& operator = ( const List& other ) ;
    /*
    {
        if( this != &other )
        {
            clear();
            for( Node* cur = other.head; cur != 0; cur = cur->next )
                push_back( cur->data );
        }
        return *this;
    }
    */
   
    size_t size() const { return len; }

    void push_front( const T& data )
    {
        Node* nNode = new Node( data );

        if( len )
        {
            nNode->next = head; // N->A
            head->prev = nNode; // N<-A
            head = nNode;
        }
        else tail = head = nNode;
        ++len;
    }


    void push_back( const T& data )
    {
        Node* nNode = new Node( data );

        if( len )
        {
            tail->next = nNode; // B->N
            nNode->prev = tail; // B<-N
            tail = nNode;
        }
        else tail = head = nNode;
        ++len;
    }

    void insert_sorted( const T& data )
    {
        Node* nNode = new Node( data );

        // case 1 ... NOT inserted as the head node
        if( head  &&  head->data <= data )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur && cur->data <= data )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;
            nNode->prev = prev;

            if( cur ) // NOT at end
            {
                cur->prev = nNode;
                nNode->next = cur;
            }
            else // at end
            {
                tail = nNode;
            }
        }
        else // insert at head ...
        {
            if( len )
            {
                nNode->next = head;
                head->prev = nNode;
                head = nNode;
            }
            else tail = head = nNode;
        }

        ++ len;
    }

    // a re-link method ... might be faster? for LARGE data records ? //
    void insert_sorted( Node* nNode )
    {
        // case 1 ... NOT inserted as the head node
        if( head  &&  head->data <= nNode->data )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur && cur->data <= nNode->data )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;
            nNode->prev = prev;

            if( cur ) // NOT at end
            {
                cur->prev = nNode;
                nNode->next = cur;
            }
            else // at end
            {
                nNode->next = 0;
                tail = nNode;
            }
        }
        else // insert at head ...
        {
            nNode->prev = 0;
            if( len )
            {
                nNode->next = head;
                head->prev = nNode;
                head = nNode;
            }
            else { nNode->next= 0 ; tail = head = nNode; }
        }

        ++ len;
    }
   
    // Note! This method, (moving and re-linking Nodes),
    // is MUCH slower than that below, for small (int) data records tested //
    void relink_insert_sort()
    {
        if( len > 1 ) // then head and cur != 0 //
        {
            Node* cur = head;
            Node* next = cur->next;
            head = tail = 0;
            len = 0;
            for( ; ; next = cur->next )
            {
                insert_sorted( cur );
                cur = next;
                if( !cur ) break;
            }
        }
    }
   
    void insert_sort()
    {
        if( len > 1 )
        {
            Node* cur = head->next;

            for( ; cur != 0; cur = cur->next ) /* start with set of just the first 2 elements (if exists) */
            {
                T cmp = cur->data; /* get copy of this new cmp element on each outer loop ... */
                Node* prev = cur->prev; /* get Node of element just to the left of the above 'cmp' to start comparisons */
                while( prev != 0 && cmp < prev->data )
                {
                    prev->next->data = prev->data; /* copy element 'up' ... */
                    prev = prev->prev; /* decrement j in preparation for next inner loop ... */
                }
                /* insert element at prev->next (since prev was 'decremented' above) */
                if( prev ) prev->next->data = cmp;
                else head->data = cmp;
            }
        }
    }
   
    void select_sort()
    {
        Node* cur = head;
        while( cur )
        {
            Node* min = cur;
            Node* next = cur->next;
            while( next )
            {
                if( next->data < min->data ) min = next; // update if needed //
                next = next->next;
            }
           
            if( cur != min ) // swap min and cur //
            {
                T tmp = cur->data;
                cur->data = min->data;
                min->data = tmp;
            }
           
            cur = cur->next;
        }
    }
   
    void select_sort_simpler()
    {
        Node* cur = head;
        while( cur )
        {
            Node* min = cur;
            Node* next = cur->next;
            while( next )
            {
                if( next->data < min->data ) min = next; // update if needed //
                next = next->next;
            }

            T tmp = cur->data;
            cur->data = min->data;
            min->data = tmp;

            cur = cur->next;
        }
    }
   
    void bubble_sort()
    {
        if( len > 1 )
        {
            Node* end = 0;
            Node* cur = head->next; // start 1 element in //
            bool swap;
            bool pass = false;
            do
            {
                swap = false;
                while( cur != end )
                {
                    if( cur->data < cur->prev->data ) // swap //
                    {
                        T tmp = cur->data;
                        cur->data = cur->prev->data;
                        cur->prev->data = tmp;
                        swap = true;
                    }
                    cur = cur->next;
                }
               
                if( pass ) end = end->prev;
                else end = tail;
               
                pass = true;
               
                if( !end ) break;
               
                cur = head->next; // get ready ready for next outer (do) loop //
            }
            while( swap );
        }
    }
   
   
   
    void print( std::ostream& os = std::cout ) const
    {
        Node* cur = head;
        while( cur )
        {
            os << cur->data << ' ';
            cur = cur->next;
        }
    }

    void printReversed( std::ostream& os = std::cout ) const
    {
        Node* cur = tail;
        while( cur )
        {
            os << cur->data << ' ';
            cur = cur->prev;
        }
    }
   
    bool isSorted() const
    {
        if( len > 1 )
        {
            Node* cur = head;
            while( cur->next )
            {
                if( cur->next->data < cur->data ) return false;
                cur = cur->next;
            }
        }
        return true;
    }
   
} ;



// def'n of overloaded (assignment) operator =
template< typename T >
List< T >& List< T >::operator = ( const List& other )
{
    if( this != &other )
    {
        clear();
        for( Node* cur = other.head; cur != 0; cur = cur->next )
            push_back( cur->data );
    }
    return *this;
}
   

#endif

Now the test program for the above DLLsorts.h code ...

Code: [Select]
// test_DLLSorts.h.cpp //  // 2017-02-13 //
 

#include "DLLsorts.h"

// include <iostream> // included above //
#include <string>




int main()
{
    using std::string;
    using std::cout;
    using std::cin;
   
    List < string > myLst;

    cout << "Now testing push_front: ";
    myLst.push_front( "Sam" );
    myLst.push_front( "Anne" );
    myLst.push_front( "Joe" );
    myLst.push_front( "Zak" );
   
    List< string > myLstCpy( myLst ); // construct a (backup) copy //
   
    myLst.print();
   
    cout << "\nPrinting after relink_insert_sort: ";
    myLst.relink_insert_sort();
    myLst.print();
   
    cout << "\nPrinting reversed: ";
    myLst.printReversed();
   
    myLst.clear();
   
   
    cout << "\n\nNow testing push_back: ";

    myLst.push_back( "Sam" );
    myLst.push_back( "Anne" );
    myLst.push_back( "Joe" );
    myLst.push_back( "Zak" );

    myLst.print();

    cout << "\nPrinting after insert_sort: ";
    myLst.insert_sort();
    myLst.print();

    cout << "\nPrinting reversed: ";
    myLst.printReversed();

    myLst.clear();
   

    cout << "\n\nNow testing insert_sorted: ";
    myLst.insert_sorted( "Billy" );
    myLst.insert_sorted( "Sam" );
    myLst.insert_sorted( "Joe" );
    myLst.insert_sorted( "Anne" );
    myLst.insert_sorted( "Jill" );
    myLst.insert_sorted( "Zak" );
   

    myLst.print();

    cout << "\nPrinting reversed: ";
    myLst.printReversed();
   
   
    myLst = myLstCpy; // restore from copy //
    cout << "\n\nPrinting before select_sort: ";
    myLst.print();

    cout << "\nPrinting after select_sort: ";
    myLst.select_sort();
    myLst.print();
   
   
    myLst = myLstCpy; // restore from copy //
    cout << "\n\nPrinting before select_sort_simpler: ";
    myLst.print();

    cout << "\nPrinting after select_sort_simpler: ";
    myLst.select_sort_simpler();
    myLst.print();
   
   
   
    myLst = myLstCpy; // restore from copy //
    cout << "\n\nPrinting before bubble_sort: ";
    myLst.print();

    cout << "\nPrinting after bubble_sort: ";
    myLst.bubble_sort();
    myLst.print();
   
   
   
    cout << "\n\nPress 'Enter' to continue/exit ...";
    cin.get();
}

And the timed sorts version ...

Code: [Select]
// timed_DLLsorts.cpp //  // 2017-02-13 //
 

#include "DLLsorts.h"

// include <iostream> // included above //

#include <string>
#include <sstream> // re. stringstream
#include <cstdlib> // re, rand, srand
#include <ctime> // re, time clock


const int MAX_SIZE = 30000;


template< typename T >
T takeIn( const std::string& msg, const std::string& errMsg = "\nError! Try again.\n\n" )
{
    T val = T();
    while( true )
    {
        std::cout << msg << std::flush;
        if( std::cin >> val && std::cin.get() == '\n' )
            break;
        else
        {
            std::cout << errMsg;
            std::cin.clear(); // clear error flasgs
            std::cin.sync(); // 'flush' cin stream ...
        }
    }
    return val;
}

char takeInChr( const std::string& msg )
{
    std::cout << msg;
    std::string reply;
    getline( std::cin, reply );
    if( reply.size() )
return reply[0];
    // else ...
    return 0;
}

bool more( const std::string& text = "" )
{
    char reply = takeInChr( "More " + text + "(y/n) ? " );
    if( reply == 'n' || reply == 'N' )
return false;
    // else ...
    return true;
}


void fillUpList( List< int >& lst, int num )
{
    for( int i = 0; i < num; ++ i )
        lst.push_back( rand() );
}




int main()
{
    using std::cout; using std::cin;
    using std::string; using std::stringstream;
   
    srand( time(0) ); // seed the random generator //
   
    do
    {
        int num = 0;
        for( ; ; )
        {
            stringstream ss;
            ss << MAX_SIZE;
            num = takeIn< int >( "How many numbers to sort (10000.." + ss.str() + "): " );
            if( num >= 10000 && num <= MAX_SIZE ) break;
            //else ///
            cout << "\nTry again with a value in range 10000.." << MAX_SIZE << " ...\n\n";
        }
       
        List< int > lst;
        fillUpList( lst, num );
       
        List< int > lstCpy( lst ); // save a (backup) copy //
       
       
        double t1 = clock();
        lst.insert_sort();
        double t2 = clock();
        cout << "\nTime to insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.insert_sort();
        t2 = clock();
        cout << "Time to insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             


        lst = lstCpy;
        t1 = clock();
        lst.relink_insert_sort();
        t2 = clock();
        cout << "\n\nTime to relink_insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.relink_insert_sort();
        t2 = clock();
        cout << "Time to relink_insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
             
        lst = lstCpy; // restore from copy //
        t1 = clock();
        lst.select_sort();
        t2 = clock();
        cout << "\n\nTime to select_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.select_sort();
        t2 = clock();
        cout << "Time to select_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             

        lst = lstCpy; // restore from copy //
        t1 = clock();
        lst.select_sort_simpler();
        t2 = clock();
        cout << "\n\nTime to select_sort_simpler was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.select_sort_simpler();
        t2 = clock();
        cout << "Time to select_sort_simpler was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
             
        lst = lstCpy; // restore from copy //
        t1 = clock();
        lst.bubble_sort();
        t2 = clock();
        cout << "\n\nTime to bubble_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.bubble_sort();
        t2 = clock();
        cout << "Time to bubble sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );


        cout << "\n\n";
    }
    while( more() );


}
90
C/C++ & Visual C++ / Re: Lists ... examples of steps to a SLL (Single-Link Linked List) and a DLL ...
« Last post by David on February 12, 2017, 11:31:22 PM »
This next test program is similar to the above, but it is menu driven ...

(Note that it uses the same DLL .h file as was used/provided above.)


Code: [Select]
// 6sorts_timed_all_menu_version.cpp //  // revised: 2016-05-05 //
 

#include "DLLinsertSorted.h"

// include <iostream> // included above //

#include <string>
#include <sstream> // re. istringstream
#include <cstdlib> // re, rand, srand
#include <ctime>   // re, time clock
#include <climits> // re. RAND_MAX
#include <cctype>  // re. tolower
#include <cmath>   // re. log

#include <list>    // to compare c++ library 'list sort' times with 'list sort' times //


const int MAX_PRINT = 5;
const int MAX_NxN = 20000;
const int MAX = 2000000;

const std::string MENU =
    "1) Insert sort\n"
    "2) Insert sorted\n"
    "3) Select sort\n"
    "4) Bubble sort\n"
    "5) Merge sort\n"
    "6) C++ list sort\n"
    "0) Exit program\n"
    "Your choice 0..6 ";


// 2 utilities to ease coding here ...
template< typename T >
T takeIn( const std::string& msg, const std::string& errMsg = "\nError! Try again.\n\n" )
{
    T val = T();
    while( true )
    {
        std::cout << msg;
        if( std::cin >> val && std::cin.get() == '\n' )
            break;
        else
        {
            std::cout << errMsg;
            std::cin.clear(); // clear error flags
            std::cin.sync(); // 'flush' cin stream ...
        }
    }
    return val;
}
char takeInChr( const std::string& msg )
{
    std::cout << msg;
    std::string reply;
    getline( std::cin, reply );
    if( reply.size() )
return reply[0];
    // else ...
    return 0;
}



// get a List of random ints in range 0..MAX_RAND
void fillUpList( List< int >& lst, int num )
{
    std::cout << "RAND_MIN = " << 0 << ", RAND_MAX = " << RAND_MAX << '\n';
    for( int i = 0; i < num; ++ i )
        lst.push_back( rand() );
}

template < typename T >
std::ostream& operator << ( std::ostream& os, const List< T >& lst )
{
    typename List< T >::const_iterator it;
    for( it = lst.begin(); it != lst.end(); ++ it ) os << *it << ' ';
    return os;
}


char showMenuGetChoice()
{
    return takeInChr( MENU );
}


int main()
{
    using std::cout; using std::cin;
    using std::string; using std::istringstream;
   
    srand( time(0) ); // seed the random generator //
   
    for( ; ; )
    {
        int num = 0;

        List< int > lst, lstCpy;
        List< int >::const_iterator cit;
       
        std::list< int > cppLst; // to compare times //
       
        double dt, t1, k;
       
        char choice = showMenuGetChoice();
        if( choice == '0' )
            break;
           
        int max_size = MAX;
        if( '1' <= choice && choice <= '4' )
            max_size = MAX_NxN;
           
        if( '1' <= choice && choice <= '6' )
        {
            // form prompt ...
            std::ostringstream oss;
            oss << "How many numbers to sort (3.." << max_size << ") : ";

            for( ; ; )
            {
                cout << "To see numbers printed, choose a number <= " << MAX_PRINT << '\n';
                num = takeIn< int >( oss.str() );
                if( num >= 3 && num <= max_size )
                    break;
                // else ...
                cout << "\nTry again with a value in range 3.." << max_size << " ...\n\n";
            }

            fillUpList( lstCpy, num );
        }
       
        switch( choice )
        {
            case '1':
                lst = lstCpy; // get from a copy //
                t1 = clock();
                lst.insert_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to insert_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                // t = k*n*n;
                // k = t/n/n
                k = dt/num/num;

                lst = lstCpy;
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //

                t1 = clock();
                lst.insert_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to insert_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '2':
                lst.clear();
                t1 = clock();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.insert_sorted( *cit );
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to insert_sorted was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                k = dt/num/num;

                lst.clear();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.insert_sorted( *cit );
                for( cit = lstCpy.begin(); cit != lstCpy.end(); cit ++ ) // test POST ++ //
                    lst.insert_sorted( *cit );
                // Now size is doubled //

                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to insert_sorted was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '3':
                lst = lstCpy; // restore from copy //
                t1 = clock();
                lst.select_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to select_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                k = dt/num/num;

                lst = lstCpy; // restore from copy //
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                lst.select_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to select_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '4':
                lst = lstCpy; // restore from copy //
                t1 = clock();
                lst.bubble_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to bubble_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                k = dt/num/num;

                lst = lstCpy; // restore from copy //
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                lst.bubble_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to bubble_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '5':
                lst = lstCpy; // restore from copy //
                if( num <= MAX_PRINT ) cout << "\nUnsorted: " << lst << '\n';
                t1 = clock();
                lst.merge_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to merge_sort was " << dt<< " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                // t = k*n*log(n)
                // k = t/n/og(n)

                k = dt/num/log(num);

                lst = lstCpy; // restore from copy //
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                lst.merge_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to merge_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << k*2*num*log(2*num) << '\n';
            break;
               
            case '6':
                // compare with C++ library list ...
                cppLst.clear();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    cppLst.push_back( *cit );
                t1 = clock();
                cppLst.sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nC++ library list sort was " << dt << " seconds.";


                k = dt/num/log(num);

                cppLst.clear();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    cppLst.push_back( *cit );
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    cppLst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                cppLst.sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nC++ library list sort was " << dt << " seconds.";
                cout << " Expected: " << k*2*num*log(2*num) << '\n';
            break;
           
            default: cout << "choice '" << choice << "' is NOT implemented here ...\n";
           
        } // end switch //
       
        if( num <= MAX_PRINT )
        {
            if( '1' <= choice && choice <= '5' )
            {
                cout << "\nSorted  : " << lst << "\nReversed: ";
                lst.printReversed();
            }
            else if( choice == '6' )
            {
                cout << "\nSorted  : ";
                std::list< int >::const_iterator ccit;
                for( ccit = cppLst.begin(); ccit != cppLst.end(); ++ ccit  )
                    cout << *ccit << ' ';

                cout << "\nReversed: ";
                std::list< int >::const_reverse_iterator rit;
                for( rit = cppLst.rbegin(); rit != cppLst.rend(); ++ rit  )
                    cout << *rit << ' ';
            }
        }
       
        cout << '\n';
       
    } // end while //
}

Pages: 1 ... 7 8 [9] 10