Templated class not modified by parent member function?

Discussion in 'C++' started by JPonens, Mar 20, 2011.

  1. JPonens

    JPonens Guest

    Greetings & salutations everyone,
    I'm struggling to wrap my brain around this one, because everything compiles just fine (g++); the sortable_list Mylist is not modified by insertion_sort() and has an apparent count == 0, even after adding to the list. I think the problem is in how I create the classes, but I don't see anything wrong. Can you see anything obvious that might be causing this behavior?

    ===================The main test file:
    #include "SortingAlgorithms.h"

    using namespace std;

    int main() {
    Sortable_list<int> Mylist;
    Mylist.insert(0,12);
    Mylist.insert(1,36);
    Mylist.insert(2,1);

    Mylist.traverse(printone); // prints 12\n36\n1\n
    Mylist.insertion_sort();
    cout << "-------" << endl;
    Mylist.traverse(printone); // prints 12\n36\n1\n ... these should be inascending order!
    return 0;
    }

    ======== SortingAlgorithms.h =========
    const int max_list = 500000;

    template <class T>
    class List {
    public:
    // methods of the List ADT
    List();
    template <class U> friend class Sortable_list;
    int size() const;
    bool full() const;
    bool empty() const;
    void clear();
    void traverse(void (*visit)(T &));
    Error_code retrieve(int position, T &x) const;
    Error_code replace(int position, const T &x);
    Error_code remove(int position, T &x);
    Error_code insert(int position, const T &x);
    protected:
    // data members for a contiguous list implementation
    int count;
    T entry[max_list];
    };

    // I presume the problem lies here:
    template <class T>
    class Sortable_list : public List<T> {
    public: // Add prototypes for sorting methods here.
    // void stl_sort();
    // etc..

    void insertion_sort(); // offending algorithm
    protected:
    // Add prototypes for auxiliary functions here.
    int count;
    T entry[max_list];
    };

    // This is the function that is not modifying:
    ////////////////////////////////////////////////////////////////////////////////
    // Unchanged from my data structures book (Kruse/Ryba):
    template <class Record>
    void Sortable_list<Record>::insertion_sort() {
    /*
    Post: The entries of the Sortable_list have been rearranged so that
    the keys in all the entries are sorted into nondecreasing order.
    Uses: Methods for the class Record; the contiguous List implementation
    */
    int first_unsorted; // position of first unsorted entry
    int position; // searches sorted part of list
    Record current; // holds the entry temporarily removed from list
    cout << "OKAY GOING, " << count << "!" << endl;
    ///// For the test, this should say "OKAY GOING, 3!" I think, but says OKAY GOING, 0!
    for (first_unsorted = 1; first_unsorted < count; first_unsorted++)
    {
    if (entry[first_unsorted] < entry[first_unsorted - 1]) {
    position = first_unsorted;
    current = entry[first_unsorted]; // Pull unsorted entryout of the list.
    do { // Shift all entries until the proper positionis found.
    entry[position] = entry[position - 1];

    position--; // position is empty.
    } while (position > 0 && entry[position - 1] > current);
    cout << "I'm never reached!" <<endl; // debugging, this is never reached
    entry[position] = current;
    }

    }
    }

    template <class List_entry>
    List<List_entry>::List()
    /*
    Post: The List is initialized to be empty.
    */
    {
    count = 0;
    }

    // clear: clear the List.
    /*
    Post: The List is cleared.
    */
    template <class List_entry>
    void List<List_entry>::clear()
    {
    count = 0;
    }

    template <class List_entry>
    int List<List_entry>::size() const
    /*
    Post: The function returns the number of entries in the List.
    */
    {
    return count;
    }

    // empty: returns non-zero if the List is empty.
    /*
    Post: The function returns true or false
    according as the List is empty or not.
    */

    template <class List_entry>
    bool List<List_entry>::empty() const
    {
    return count <= 0;
    }

    // full: returns non-zero if the List is full.
    /*
    Post: The function returns true or false
    according as the List is full or not.
    */
    template <class List_entry>
    bool List<List_entry>::full() const
    {
    return count >= max_list;
    }

    template <class List_entry>
    void List<List_entry>::traverse(void (*visit)(List_entry &))
    /*
    Post: The action specified by function (*visit) has been performed on every
    entry of the List, beginning at position 0 and doing each in turn.
    */
    {
    for (int i = 0; i < count; i++)
    (*visit)(entry);
    }

    template <class List_entry>
    Error_code List<List_entry>::insert(int position, const List_entry &x) {
    /*
    Post: If the List is not full and 0 <= position <= n,
    where n is the number of entries in the List,
    the function succeeds:
    Any entry formerly at
    position and all later entries have their
    position numbers increased by 1 and
    x is inserted at position of the List.
    Else:
    The function fails with a diagnostic error code.
    */
    if (full())
    return overflow;

    if (position < 0 || position > count)
    return overflow;

    for (int i = count - 1; i >= position; i--)
    entry[i + 1] = entry;

    entry[position] = x;
    count++;
    return success;
    }

    template <class List_entry>
    Error_code List<List_entry>::retrieve(int position, List_entry &x) const {
    /* Post: If the List is not full and 0 <= position < n,
    where n is the number of entries in the List,
    the function succeeds:
    The entry in position is copied to x.
    Otherwise the function fails with an error code of range_error.
    */
    if (position < 0 || position >= count) return range_error;
    x = entry[position];
    return success;
    }

    template <class List_entry>
    Error_code List<List_entry>::replace(int position, const List_entry &x)
    /*
    Post: If 0 <= position < n,
    where n is the number of entries in the List,
    the function succeeds:
    The entry in position is replaced by x,
    all other entries remain unchanged.
    Otherwise the function fails with an error code of range_error.
    */
    {
    if (position < 0 || position >= count) return range_error;
    entry[position] = x;
    return success;
    }

    /*
    Post: If 0 <= position < n,
    where n is the number of entries in the List,
    the function succeeds:
    The entry in position is removed
    from the List, and the entries in all later positions
    have their position numbers decreased by 1.
    The parameter x records a copy of
    the entry formerly in position.
    Otherwise the function fails with a diagnostic error code.
    */
    template <class List_entry>
    Error_code List<List_entry>::remove(int position, List_entry &x)
    {
    if (count == 0) return underflow;
    if (position < 0 || position >= count) return range_error;

    x = entry[position];
    count--;
    while (position < count) {
    entry[position] = entry[position + 1];
    position++;
    }
    return success;
    }


    ============
    Thank you for any assistance!
     
    JPonens, Mar 20, 2011
    #1
    1. Advertising

  2. JPonens

    Paul Guest

    "JPonens" <> wrote in message
    news:...
    Greetings & salutations everyone,
    I'm struggling to wrap my brain around this one, because everything compiles
    just fine (g++); the sortable_list Mylist is not modified by
    insertion_sort() and has an apparent count == 0, even after adding to the
    list. I think the problem is in how I create the classes, but I don't see
    anything wrong. Can you see anything obvious that might be causing this
    behavior?

    ===================The main test file:
    #include "SortingAlgorithms.h"

    using namespace std;

    int main() {
    Sortable_list<int> Mylist;
    Mylist.insert(0,12);
    Mylist.insert(1,36);
    Mylist.insert(2,1);

    Mylist.traverse(printone); // prints 12\n36\n1\n
    Mylist.insertion_sort();
    cout << "-------" << endl;
    Mylist.traverse(printone); // prints 12\n36\n1\n ... these should be in
    ascending order!
    return 0;
    }

    ======== SortingAlgorithms.h =========
    const int max_list = 500000;

    template <class T>
    class List {
    public:
    // methods of the List ADT
    List();
    template <class U> friend class Sortable_list;
    int size() const;
    bool full() const;
    bool empty() const;
    void clear();
    void traverse(void (*visit)(T &));
    Error_code retrieve(int position, T &x) const;
    Error_code replace(int position, const T &x);
    Error_code remove(int position, T &x);
    Error_code insert(int position, const T &x);
    protected:
    // data members for a contiguous list implementation
    int count;
    T entry[max_list];
    };

    // I presume the problem lies here:
    template <class T>
    class Sortable_list : public List<T> {
    public: // Add prototypes for sorting methods here.
    // void stl_sort();
    // etc..

    void insertion_sort(); // offending algorithm
    protected:
    // Add prototypes for auxiliary functions here.
    int count;
    T entry[max_list];
    };

    // This is the function that is not modifying:
    ////////////////////////////////////////////////////////////////////////////////
    // Unchanged from my data structures book (Kruse/Ryba):
    template <class Record>
    void Sortable_list<Record>::insertion_sort() {
    /*
    Post: The entries of the Sortable_list have been rearranged so that
    the keys in all the entries are sorted into nondecreasing order.
    Uses: Methods for the class Record; the contiguous List implementation
    */
    int first_unsorted; // position of first unsorted entry
    int position; // searches sorted part of list
    Record current; // holds the entry temporarily removed from list
    cout << "OKAY GOING, " << count << "!" << endl;
    ///// For the test, this should say "OKAY GOING, 3!" I think, but says
    OKAY GOING, 0!
    for (first_unsorted = 1; first_unsorted < count; first_unsorted++)
    {
    if (entry[first_unsorted] < entry[first_unsorted - 1]) {
    position = first_unsorted;
    current = entry[first_unsorted]; // Pull unsorted entry
    out of the list.
    do { // Shift all entries until the proper position
    is found.
    entry[position] = entry[position - 1];

    position--; // position is empty.
    } while (position > 0 && entry[position - 1] > current);
    cout << "I'm never reached!" <<endl; // debugging, this is never
    reached
    entry[position] = current;
    }

    }
    }

    template <class List_entry>
    List<List_entry>::List()
    /*
    Post: The List is initialized to be empty.
    */
    {
    count = 0;
    }

    I haven't really analyzed your program but a shot in the dark, judging by
    your warnings in other post, might be to change the above constructor to:
    template <class List_entry>
    List<List_entry>::List(): count(0){}

    HTH.
    <snip>
     
    Paul, Mar 21, 2011
    #2
    1. Advertising

  3. On 3/20/2011 5:55 PM, JPonens wrote:
    > Greetings& salutations everyone,
    > I'm struggling to wrap my brain around this one, because everything
    > compiles just fine (g++); the sortable_list Mylist is not modified
    > by insertion_sort() and has an apparent count == 0, even after
    > adding to the list. I think the problem is in how I create the
    > classes, but I don't see anything wrong. Can you see anything
    > obvious that might be causing this behavior?


    Yes. See below.

    >
    > ===================The main test file:
    > #include "SortingAlgorithms.h"
    >
    > using namespace std;
    >
    > int main() {
    > Sortable_list<int> Mylist;
    > Mylist.insert(0,12);
    > Mylist.insert(1,36);
    > Mylist.insert(2,1);
    >
    > Mylist.traverse(printone); // prints 12\n36\n1\n
    > Mylist.insertion_sort();
    > cout<< "-------"<< endl;
    > Mylist.traverse(printone); // prints 12\n36\n1\n ... these should be in ascending order!
    > return 0;
    > }
    >
    > ======== SortingAlgorithms.h =========
    > const int max_list = 500000;
    >
    > template<class T>
    > class List {
    > public:
    > // methods of the List ADT
    > List();
    > template<class U> friend class Sortable_list;
    > int size() const;
    > bool full() const;
    > bool empty() const;
    > void clear();
    > void traverse(void (*visit)(T&));
    > Error_code retrieve(int position, T&x) const;
    > Error_code replace(int position, const T&x);
    > Error_code remove(int position, T&x);
    > Error_code insert(int position, const T&x);
    > protected:
    > // data members for a contiguous list implementation
    > int count;
    > T entry[max_list];
    > };
    >
    > // I presume the problem lies here:
    > template<class T>
    > class Sortable_list : public List<T> {
    > public: // Add prototypes for sorting methods here.
    > // void stl_sort();
    > // etc..
    >
    > void insertion_sort(); // offending algorithm
    > protected:
    > // Add prototypes for auxiliary functions here.
    > int count;
    > T entry[max_list];


    Your base class has 'int count' and your derived class has its own 'int
    count'. If you declare a member named "blah" in the derived class, it
    *hides* the member named "blah" in the base class. Same with 'entry'
    array. Why do you think you need to define two additional members in
    the derived class if your base class already has them?

    You need to read again about inheritance and object layout, about
    members and access to them.

    > };
    > [...]
    >
    > ============
    > Thank you for any assistance!


    V
    --
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Mar 21, 2011
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jahagirdar Vijayvithal S
    Replies:
    2
    Views:
    448
    Jahagirdar Vijayvithal S
    Aug 7, 2005
  2. Amadeus W. M.
    Replies:
    2
    Views:
    415
    Amadeus W. M.
    Jul 4, 2006
  3. Replies:
    1
    Views:
    320
  4. Rasmus Johansen
    Replies:
    3
    Views:
    413
    VirGin
    Oct 18, 2007
  5. chhenning
    Replies:
    5
    Views:
    383
    chhenning
    Feb 13, 2008
Loading...

Share This Page