[-shadow-]

Hey guys,

Sorry I haven't been around for a while, I've been
very busy.

I'm having some issues with a program for my C++ class.
The assignment is to create a templated array class
( Which I have done ) and then to import the array from
a file of about 40,000 words and sort the words using
shell sort, then using a sub-linear search algorithm
( I'll probably use binary-search ) find a user-input
word in the file.

My issue is that it works fine with my smaller test file.
containing a sequence of about 20 3-character strings. But,
when I switch to the large file, it hangs up. After a massive
amount of debugging, I have found that it's hanging up on the
import for some reason and I have no idea why. I will paste
the template class in a spoiler, but it generally works the
same way as standard subscripted arrays with a constructor.

Array<T> ( size_t pSize, const T& value = T() );
Array<T> ();
Array<T> ( const_iterator first, const_iterator last );
Array<T> ( const Array &a );

Spoiler

/*
  Filename   : Array.h
  Author     : Gary M. Zoppetti
  Course     : CSCI 362-01
  Assignment : N/A
  Description: Array class, our implementation of a list ADT 
                 with random access and dynamic resizing
*/   

/************************************************************/
// Macro guard to prevent multiple inclusions

#ifndef ARRAY_H
#define ARRAY_H

/************************************************************/
// System includes

#include <cstdlib>
#include <iostream>
#include <algorithm>

/************************************************************/
// Local includes

/************************************************************/
// Using declarations

using std::ostream;

/************************************************************/

template <typename T>
class Array 
{
        private:

        size_t m_size;
        size_t m_capacity;
        T*     m_array;

        public:
  
        typedef T          value_type;
        // Iterators are just pointers to objects of type T
        typedef T*         iterator;
        typedef const T*   const_iterator;

        typedef T&         reference;
        typedef const T&   const_reference;
        typedef size_t     size_type;
        typedef ptrdiff_t  difference_type;

        // Initialize an empty Array
        Array ()
        {
                m_size = 0;
                m_capacity = 0;
                m_array = NULL;
        }

        // Initialize an Array of size "pSize", with each element
        //   set to "value"
        explicit Array (size_t pSize, const T& value = T ())
        {
                m_size = pSize;
                m_capacity = pSize;
                m_array = new T[pSize];
                std::fill( begin(), end(), value );
        }
        // Initialize an Array from the range [first, last)
        Array (const_iterator first, const_iterator last)
        {
                m_size = last - first;
                m_capacity = m_size;
                m_array = new T[ last - first ];
                std::copy( first, last, m_array );
        }

        // Initialize this object from "a"
        Array (const Array &a)
        {
                m_array = new T[ a.size() ];
                m_size = a.size();
                m_capacity = a.size();
                std::copy( a.begin(), a.end(), m_array );
        }

        // Release allocated memory
        ~Array ()  
        {
                delete [] m_array;
        }
        // Assign "a" to this object
        //   Watch for self-assignment
        Array&
        operator= (const Array& a)
        {
                m_array = new T[ a.size() ];
                m_size = a.size();
                m_capacity = a.size();
                std::copy( a.begin(), a.end(), m_array );
                return( *this );
        }

        size_t
        size () const
        {
                return( m_size );
        }

        size_t
        capacity () const
        {
                return( m_capacity );
        }

        T&
        operator[] (size_t index)
        {
                return( m_array[index] );
        }

        const T&
        operator[] (size_t index) const
        {
                return( m_array[index] );
        }

        void
        push_back (const T& item)
        {
                insert( end(), item );
        }

        void
        pop_back ()
        {
                --m_size;
        }

        // Reserve capacity for "space" elements -- "space" must be 
        //   > capacity -- this doesn't change the size 
        //   Invoking methods double capacity when extra space is needed
        void
        reserve (size_t space)
        {
                if( space > m_capacity )
                {
                        T * old = m_array;
                        m_array = new T[ space ];
                        std::copy( old, &old[m_size], m_array );
                        m_capacity = space;
                        delete [] old;
                }
        }

        void
        resize (size_t newSize, const T& defValue = T ())
        {
                if( newSize > m_capacity )
                {
                        if( m_capacity > 0 )
                        {
                                reserve( m_capacity * 2 );
                        } else {
                                reserve( 1 );
                        }
                }
                std::fill( end(), begin() + newSize, defValue );
                m_size = newSize;
        }

        // Insert "item" before "pos", and return iterator referencing "item"
        iterator       insert (iterator pos, const T& item)
        {
                if( m_capacity <= m_size )
                {
                        int i = pos - m_array;
                        if( m_capacity < 1 )
                        {
                                reserve( 1 );
                        } else {
                                reserve( m_capacity * 2 );
                        }
                        pos = &m_array[i];
                }

                T * newArray = new T[m_size + 1];
                std::copy( begin(), pos, newArray );
                std::copy( pos, end(), &newArray[pos - m_array + 1] );

                newArray[pos - m_array] = item;
                m_array = newArray;

                ++m_size;

                return( pos );
        }

        // Remove element at "pos", and return iterator referencing next element
        iterator       erase  (iterator pos)
        {
                if( m_size > 0 )
                {
                        T * newArray = m_array;
                        std::copy( pos + 1, end(), &newArray[pos - m_array] );
                        m_array = newArray;
                        --m_size;
                }
                return( pos );
        }

        iterator       begin ()
        {
                return( m_array );
        }
        const_iterator begin () const
        {
                return( m_array );
        }

        // Return pointer to element one past last
        iterator       end ()
        {
                return( &m_array[m_size] );
        }
        const_iterator end () const
        {
                return( &m_array[m_size] );
        }

};

/************************************************************************/
// Free functions associated with class

template <typename T>
ostream&
operator<< (ostream& output, const Array<T>& a)
{
        int i = 0;

        output << "[ ";

        if( a.size() > 0 )
        {
                output << a[0];
                for( i = 1; i < (int)a.size(); ++i )
                {
                        output << ", " << a[i];
                }
        }

        output << " ]";
        return( output );
}

#endif

/************************************************************************/

MAIN:

/******************************************************************************/
// MAIN
int
main( int argc, char * argv[] )
{
        /*******************************************************
        ****                    VARIABLES                   ****
        *******************************************************/
        Array<string> a( 5 );

        /*******************************************************
        ****                      BODY                   ****
        *******************************************************/
        cout << "Importing Words to array... ";
        importWords( a );
        cout << "done.\n";

        cout << "Sorting Array... ";
        //a = shell( a );
        cout << "done.\n";
        //cout << a;

}

bool
importWords( Array<string> &a )
{
        int i = 0;
        string tmp;

        ifstream fp( "./words.txt" );

        if( fp.is_open() )      // Open the file
        {
                /* Are there remaining Lines? */
                while( fp >> tmp && !fp.eof() )
                {
                        // Is it out of bounds?
                        if( i >= (signed)a.size() )
                        {
                                a.push_back( "0" );
                        }

                        /* Populate the array */
                        a[i++] = tmp;
                }
                fp.close();
                return( true );
        }
        return( false );
}

[ishkabible]

first off, lines 14-21 are just asking for trouble and it can be replaced with 1 line.

a.push_back(tmp);

second can you post an example file that creates the issue?

edit:

fp >> tmp && !fp.eof()

i just spotted the likely culprit. let's say fp is 1 line from the end of the file when this condition runs. it reads in temp and eof is still false so it enters the loop. on the next loop you read in temp but there is nothing to read in!!

This post has been edited by ishkabible: 31 October 2011 - 08:26 AM

[-shadow-]

wow I'm an idiot

Unfortunately it's still hanging up

This post has been edited by -shadow-: 31 October 2011 - 08:42 AM

[-shadow-]

fixed the import. My insert method was really inefficient.
I made it a lot better now, but my shell sort is taking a
while now. Yeah, it's 400,000 strings but the teacher told
us to use shell sort so I feel like it should be faster than
that.

Heres my shellsort code:

/******************************************************************************/
// Shell Sort Array
Array<string> shell( Array<string> a )
{
    /*******************************************************
    ****                    VARIABLES                   ****
    *******************************************************/
    int n = a.size(),           /* Size of Array     */
        i = 0,                  /* Loop Controller   */
        h = 0;                  /* Size of each pass */

    /*******************************************************
    ****                        BODY                    ****
    *******************************************************/
    // Before we waste any time, lets see if its already sorted
    if( isSorted( a ) )
    {
        return( a );
    }

    // Get h initial value
    h = 1;
    while( h * 3 + 1 < n )
    {
        h = h * 3 + 1;
    }

    while( h > 0 )
    {
        // Run through the array, decreasing h by 1 + a factor of 3
        for( i = h; i < n; ++i )
        {
            while( a[i] < a[i - h] )
            {
                std::swap( a[i], a[i - h] );
                i -= ( i - h > 0 ) ? 1 : 0;
            }
        }

        // Update h
        h = h / 3;
    }
    return( a );
}