J
JPonens
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!
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!