Sequence Class

[pat270881]

hello,

I have to implement a sequence class, however the header file is
predefined

class sequence
{
public:
// TYPEDEFS and MEMBER CONSTANTS
typedef double value_type;
typedef std::size_t size_type;
static const size_type DEFAULT_CAPACITY = 30;
// CONSTRUCTORS and DESTRUCTOR
sequence(size_type initial_capacity = DEFAULT_CAPACITY);
sequence(const sequence& source);
~sequence( );
// MODIFICATION MEMBER FUNCTIONS
void resize(size_type new_capacity);
void start( );
void advance( ); //set the current_index to the next number in
the array
void insert(const value_type& entry); //insert before the
number with the current index
void attach(const value_type& entry); //insert after the number
with the current index
void remove_current( );
void operator =(const sequence& source);
// CONSTANT MEMBER FUNCTIONS
size_type size( ) const;
bool is_item( ) const;
value_type current( ) const;
private:
value_type* data; //das array mit den zahlen drinnen
size_type used; //wieviele zahlen in dem array stehen
size_type current_index;
size_type capacity;
};
 

Unfortunately, I guess something is wrong with the copy constructor, or
the insert, attach or resize function:

sequence::sequence(const sequence& source)
{
data = new value_type[source.capacity];
capacity = source.capacity;
used = source.used;
current_index = source.current_index;
copy(source.data, source.data + used, data);
}
 

Here the insert, attach and resize function:

 
void sequence::insert(const value_type& entry)
{
if(used == capacity)
resize(used);
 
if(!(is_item()))
current_index = 0;
 
for(int i = used; i current_index; i--)
{
data[i] = data[i-1];
}
data[current_index] = entry;
++used;
}
 
void sequence::attach(const value_type& entry)
{
if(used == capacity)
resize(used);
 
if(current_index >= used)
{
start();
advance();
advance();
}
if(used!=0)
{
for(int i = used; i current_index+1; i--)
{
data[i] = data[i-1];
}
data[current_index+1] = entry;
current_index++;
}
else
{
data[current_index] = entry;
}
++used;
}
 
void sequence::resize (size_type new_capacity)
{
value_type* larger_array;
 
if(new_capacity < used)
new_capacity = used;
 
larger_array = new value_type[new_capacity];
copy(data, data + used + current_index, larger_array);
delete[] data;
data = larger_array;
capacity = new_capacity;
}
 

Has anybody an idea what went wrong here? I am working on the problem
fixing for such a long time but I haven't found the error yet...:((

pat

[red floyd]

pat270881 wrote:

hello,

I have to implement a sequence class, however the header file is
predefined

[large amount of code redacted]

Has anybody an idea what went wrong here? I am working on the problem
fixing for such a long time but I haven't found the error yet...:((

Well, you didn't tell us what you were expecting, or what results you
got that were different from what you were expecting. Tell us that, and
maybe we can help.

Until then, you have an error on line 42 of your code.

[mlimber]

pat270881 wrote:

I have to implement a sequence class, however the header file is
predefined
[...]
Unfortunately, I guess something is wrong with the copy constructor, or
the insert, attach or resize function:
[...]

We're not here to do your homework for you (see
http://parashift.com/c++-faq-lite/ho....html#faq-5.2). If you
post a minimal but complete sample that demonstrates what problem
you're talking about (see
http://parashift.com/c++-faq-lite/ho...t.html#faq-5.8) and ask
specific questions about the language (not "what's wrong with this?"),
then we can try to help you.

Cheers! --M

[pat270881]

Sorry for that I tried to execute this test-program:

[/code]
int test5( )
{
sequence original; // A sequence that we'll copy.
double items[2*original.DEFAULT_CAPACITY];
size_t i;

// Set up the items array to conatin 1...2*DEFAULT_CAPACITY.
for (i = 1; i <= 2*original.DEFAULT_CAPACITY; i++)
items[i-1] = i;

// Test copying of an empty sequence. After the copying, we change
the original.
cout << "Copy constructor test: for an empty sequence." << endl;
sequence copy1(original);
original.attach(1); // Changes the original sequence, but not the
copy.
if (!correct(copy1, 0, 0, items)) return 0;

// Test copying of a sequence with current item at the tail.
cout << "Copy constructor test: for a sequence with cursor at
tail." << endl;
for (i=2; i <= 2*original.DEFAULT_CAPACITY; i++)
original.attach(i);
cout << "SIZE: " << original.size() << endl;
sequence copy2(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy2, 2*original.DEFAULT_CAPACITY,
2*original.DEFAULT_CAPACITY-1, items)
)
return 0;

// Test copying of a sequence with cursor near the middle.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);
for (i = 1; i < original.DEFAULT_CAPACITY; i++)
original.advance( );
// Cursor is now at location [DEFAULT_CAPACITY] (counting [0] as
the first spot).
sequence copy3(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy3, 2*original.DEFAULT_CAPACITY, original.DEFAULT_CAPACITY,
items)
)
return 0;

// Test copying of a sequence with cursor at the front.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);
original.start( );
// Cursor is now at the front.
sequence copy4(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy4, 2*original.DEFAULT_CAPACITY, 0, items)
)
return 0;

// Test copying of a sequence with no current item.
cout << "Copy constructor test: for a sequence with no current
item." << endl;
original.insert(2);
while (original.is_item( ))
original.advance( );
// There is now no current item.
sequence copy5(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy5, 2*original.DEFAULT_CAPACITY,
2*original.DEFAULT_CAPACITY, items)
)
return 0;
}
[/code]

After this line cout << "Copy constructor test: for a sequence with
cursor near middle." << endl; the programm breaks and a pop-window
appears where it is quoted that TestApplication.exe has detected a
problem and has to be finished.

I think the actual error occurs at the original.insert(2); line.
Does andybody know now what went wrong...? :(

pat

[mlimber]

pat270881 wrote:

Sorry for that I tried to execute this test-program:

[/code]
int test5( )
{
sequence original; // A sequence that we'll copy.
double items[2*original.DEFAULT_CAPACITY];
size_t i;

// Set up the items array to conatin 1...2*DEFAULT_CAPACITY.
for (i = 1; i <= 2*original.DEFAULT_CAPACITY; i++)
items[i-1] = i;

// Test copying of an empty sequence. After the copying, we change
the original.
cout << "Copy constructor test: for an empty sequence." << endl;
sequence copy1(original);
original.attach(1); // Changes the original sequence, but not the
copy.
if (!correct(copy1, 0, 0, items)) return 0;

// Test copying of a sequence with current item at the tail.
cout << "Copy constructor test: for a sequence with cursor at
tail." << endl;
for (i=2; i <= 2*original.DEFAULT_CAPACITY; i++)
original.attach(i);
cout << "SIZE: " << original.size() << endl;
sequence copy2(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy2, 2*original.DEFAULT_CAPACITY,
2*original.DEFAULT_CAPACITY-1, items)
)
return 0;

// Test copying of a sequence with cursor near the middle.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);
for (i = 1; i < original.DEFAULT_CAPACITY; i++)
original.advance( );
// Cursor is now at location [DEFAULT_CAPACITY] (counting [0] as
the first spot).
sequence copy3(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy3, 2*original.DEFAULT_CAPACITY, original.DEFAULT_CAPACITY,
items)
)
return 0;

// Test copying of a sequence with cursor at the front.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);
original.start( );
// Cursor is now at the front.
sequence copy4(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy4, 2*original.DEFAULT_CAPACITY, 0, items)
)
return 0;

// Test copying of a sequence with no current item.
cout << "Copy constructor test: for a sequence with no current
item." << endl;
original.insert(2);
while (original.is_item( ))
original.advance( );
// There is now no current item.
sequence copy5(original);
original.start( );
original.advance( );
original.remove_current( ); // Removes 2 from the original, but not
the copy.
if (!correct
(copy5, 2*original.DEFAULT_CAPACITY,
2*original.DEFAULT_CAPACITY, items)
)
return 0;
}
[/code]

After this line cout << "Copy constructor test: for a sequence with
cursor near middle." << endl; the programm breaks and a pop-window
appears where it is quoted that TestApplication.exe has detected a
problem and has to be finished.

I think the actual error occurs at the original.insert(2); line.
Does andybody know now what went wrong...? :(

Sorry. It still isn't minimal but complete. In particular where are the
other functions, such as sequence::start()?

Regardless of that, however, this is a clear case where you need to
learn to use your debugger to step through the code. In particular,
make sure that you are not attempting to write to a memory location
past the end of your allocated array.

Again, if you have a specific language question, we'd be happy to try
to answer it, but we're not here to do your homework for you.

Cheers! --M

[pat270881]

I already tried to debug it and the error was a bad_alloc error so that
I write out of the heap. But I simply do not know why this
happens...?:((

here the other functions of my sequenceimple file:

sequence::sequence(size_type initial_capacity)
{
data = new value_type[initial_capacity];
capacity = initial_capacity;
used = 0;
current_index = 0;
}
 
sequence::~sequence()
{
delete[] data;
}
 
void sequence::operator = (const sequence& source)
{
value_type* new_data;
 
if (this == &source)
return;
 
if(capacity != source.capacity)
{
new_data = new value_type[source.capacity];
delete[] data;
data = new_data;
capacity = source.capacity;
}
 
used = source.used;
current_index = source.current_index;
copy(source.data, source.data + used, data);
}
 
void sequence::start( )
{
current_index = 0;
}
 
void sequence::advance( )
{
if(is_item())
current_index++;
}
 
void sequence::remove_current( )
{
//cout << current_index << " " << used;
for(int i = current_index; i < used; i++)
{
data[i] = data[i+1];
}
used--;
 
}
 
sequence::value_type sequence::current() const
{
return data[current_index];
}
 
bool sequence::is_item( ) const
{
if(current_index < used)
{
return true;
}
else
{
return false;
}
}
 
sequence::size_type sequence::size() const
{
return used;
}
 

I know that you should not do my homework but I simply see not the
error I made...:(

[mlimber]

pat270881 wrote:

I already tried to debug it and the error was a bad_alloc error so that
I write out of the heap. But I simply do not know why this
happens...?:((

Ahh, here's the rub and finally a C++ language question! The bad_alloc
exception is thrown when the new operator can't allocate storage of the
requested size. In short, your memory allocation is failing. Is the
requested size too large perhaps?

Cheers! --M

[pat270881]

Ahh, here's the rub and finally a C++ language question! The bad_alloc
exception is thrown when the new operator can't allocate storage of the
requested size. In short, your memory allocation is failing. Is the
requested size too large perhaps?

Yes I know but I simply do not see where I write out of the heap, that
is my big problem...?:(

[mlimber]

pat270881 wrote:

Ahh, here's the rub and finally a C++ language question! The bad_alloc
exception is thrown when the new operator can't allocate storage of the
requested size. In short, your memory allocation is failing. Is the
requested size too large perhaps?

Yes I know but I simply do not see where I write out of the heap, that
is my big problem...?:(

You don't get a bad_alloc exception when you go outside the bounds of
your array (well, in theory, I suppose you could since writing there is
technically undefined behavior which could do anything -- but it's
quite unlikely that it would generate bad_alloc). You only get it when
storage cannot be *allocated*. Put a breakpoint on your "new"
statements, and see if that's where things go off into the weeds.

Cheers! --M

[pat270881]

I have already debug the program and the error occurs here:

// Test copying of a sequence with cursor near the middle.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);

but I simply don't know why...? :((

[red floyd]

pat270881 wrote:

>
I have already debug the program and the error occurs here:

// Test copying of a sequence with cursor near the middle.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);

but I simply don't know why...? :((

No, that's the symptom. Mlimber is telling you that if you see
bad_alloc, that means that new is failing. That's your potential
cause. Don't fixate on what you think is wrong. If you were certain,
you wouldn't have come here. If you ask someone's advice, then listen
to it.

If you're seeing bad_alloc somewhere, that means that new is failing
(not that you're overwriting heap, though that may happen as well). Put
a break point on your new statements, and check that you're passing sane
values as the sizes.

[Alan Johnson]

pat270881 wrote:

I have already debug the program and the error occurs here:

// Test copying of a sequence with cursor near the middle.
cout << "Copy constructor test: for a sequence with cursor near
middle." << endl;
original.insert(2);

but I simply don't know why...? :((

You are making it too hard to help you. Right now if I wanted to debug
your program, I'd have to collect together several pieces of it from
multiple posts, and then I'd still have to write some code of my own to
have anything that would compile and run.

Your best bet is to post a complete program that demonstrates your
problem. This means that I could copy and paste directly from your
post into my editor, compile, and see your problem (Hint: a complete
program has a main function, and you haven't posted one anywhere).

--
Alan Johnson

[Thomas J. Gritzan]

pat270881 schrieb:

void sequence::insert(const value_type& entry)
{
if(used == capacity)
resize(used);

if(!(is_item()))
current_index = 0;

for(int i = used; i current_index; i--)
{
data[i] = data[i-1];
}
data[current_index] = entry;
++used;
}

[...]

Has anybody an idea what went wrong here? I am working on the problem
fixing for such a long time but I haven't found the error yet...:((

resize(used);
should be
resize(used+1);

Otherwise you are accessing data[used] in the for-loop, which is one past
the last element.

Why don't you use std::vector?

--
Thomas
http://www.netmeister.org/news/learn2quote.html

[mlimber]

Thomas J. Gritzan wrote:

Why don't you use std::vector?

Because this is homework.

Cheers! --M

[pat270881]

Sorry, that I cost you so much nerves, that was the error - when a
handed over the used to the resize function I haven't increased the
used, now I use 2*used in insert and attach and now it works :))

Thank you very much for your help!!!