inserting in a sorted list

hi
I am a student in computer science and I'm having some trouble with our latest assignment. (Part of) the assignment is to insert elements into a sorted list.
The elements are some kind of interval-type objects
Every time when I insert an object I want it to be inserted in the right position. if there is an overlapping with another object in the list I dont want to insert it.

I wrote a small testprogram to test this part of the code, first for regular integers, then for the objects I have to insert.
For intergers I had (almost) no problems but with my own objects I am getting strange results. I am staring at my code for almost half a day, rewriting it over and over again. but I just cant see what I am doing wrong.

here are the relevant parts of the code:

the things I have to insert in the list are from the ScheduleItem class.

declarations:

Code:

// part of scheduleitem.h

typedef unsigned long int ulint;

class ScheduleItem
{   public:
        ScheduleItem(ulint, ulint, std::string);
        ScheduleItem(std::istream&);
        ulint getbegin() const;
        ulint getend() const;
        std::string getdescription() const;
        void setbegin(ulint);
        void setend(ulint);
        void setdescription(std::string);
    private:
        ulint begin_;
        ulint end_;
        std::string descr_;
};

std::ostream& operator<<(std::ostream&, const ScheduleItem&);
bool operator<(const ScheduleItem&, const ScheduleItem&);
bool operator>(const ScheduleItem&, const ScheduleItem&);
bool operator==(const ScheduleItem&, const ScheduleItem&);

definitions:

Code:

// small part of scheduleitem.cc

bool operator<(const ScheduleItem& si1, const ScheduleItem& si2)
{   si1.getend() < si2.getbegin();
}

bool operator>(const ScheduleItem& si1, const ScheduleItem& si2)
{   si1.getbegin() > si2.getend();
}

bool operator==(const ScheduleItem& si1, const ScheduleItem& si2)
{   si1.getbegin() == si2.getbegin() && si1.getend() == si2.getend() && si1.getdescription() == si2.getdescription();
}

I am quite sure I defined operator< and operator> right.
a<b if a ends before b starts
a>b if a starts after b ends


here is the class in which I have to insert the scheduleitems.

declarations:

Code:

// most of schedule.h

class Schedule
{   public:
        friend std::ostream& operator<<(std::ostream&, const Schedule&);
        Schedule();
        Schedule(std::istream&);
        bool insert_item(const ScheduleItem&);
        bool remove_item(const ScheduleItem&);
        bool check_item(ScheduleItem&, const ScheduleItem&, ScheduleItem&);
        bool check_item(ScheduleItem&, const ScheduleItem&, ScheduleItem&, const std::list<Schedule>&);
    private:
        std::list<ScheduleItem> items_;
};

definitions:

Code:

// part of schedule.cc

bool Schedule::insert_item(const ScheduleItem& si)
{   for (std::list<ScheduleItem>::iterator i = items_.begin(); ; i++)
    {   if ((i == items_.end()) || (*i > si))
        {   items_.insert(i, si);
            return 1;
        }
        else if (!(*i < si))
            return 0;
    }
}

bool Schedule::remove_item(const ScheduleItem& si)
{   for (std::list<ScheduleItem>::iterator i = items_.begin(); ; i++)
    {   if (i == items_.end())
            return 0;
        else if (*i == si)
        {   items_.erase(i);
            return 1;
        }
    }
}

std::ostream& operator<<(std::ostream& os, const Schedule& s)
{   for (std::list<ScheduleItem>::const_iterator i = s.items_.begin(); i != s.items_.end(); i++)
    os << *i;
}

if I write a small testing-loop in which I insert scheduleitems into a schedule it keeps inserting them at the front!
also, the remove-part always removes the first item from the schedule in stead of the right one.

one other small thing: if I change the last line ( os << *i; ) with os << *i << std::endl; the program crashes at runtime. I also have no idea why it does that...

thanks in advance for your help, and I hope that someone can point me in the right direction.


ken

I don't see anything specifically wrong, although it seems a little strange that operator<, operator> and opeator== are all implemented differently. Do any schedule items ever overlap? Do they ever share a start time but have different end times or different descriptions?

The crash at runtime is odd, is there any other code that inserts or removes from the list?

Perhaps you could provide a test main() that reproduces the problem.

thanks for having a look.
here is the main() function I am using to test it.
its not very nicely written, but its good enough to test the inserting and deleting of scheduleitems.

Code:

#include <iostream>
using namespace std;
#include "scheduleitem.h"
#include "schedule.h"

int main()
{   Schedule s;
    while(true)
    {   cout << "give begin, end and description:\n";
        ScheduleItem i(cin);
        if (i.getbegin() < 10)
            break;
        s.insert_item(i);
        cout << s;
    }
    while(true)
    {   cout << "give begin, end and description:\n";
        ScheduleItem i(cin);
        if (i.getbegin() < 10)
            break;
        s.remove_item(i);
        cout << s;
    }
    return 0;
}

as you can see I initialise the scheduleitem from a stream.
the code is:

Code:

// part of schduleitem.cc

ScheduleItem::ScheduleItem(std::istream& is)
{   is >> begin_;
    is >> end_;
    is.ignore();
    getline(is, descr_);
}

this is what the output looks so far
it asks for input,
then I give some inut. and then it all the elements from the list.
as you can see it doesnt care what the element I want to insert is, it just puts it in front of the list.

give begin, end and description:
100 200 test1
100 200 test1
give begin, end and description:
300 400 test2
300 400 test2
100 200 test1
give begin, end and description:
50 150 test3
50 150 test3
300 400 test2
100 200 test1
give begin, end and description:

etc....


thanks

1) Why are the following implemented as non-member functions?

Code:

bool operator<(const ScheduleItem&, const ScheduleItem&);
bool operator>(const ScheduleItem&, const ScheduleItem&);
bool operator==(const ScheduleItem&, const ScheduleItem&);

The parameters you list indicate that a ScheduleItem object is going to be calling the operator function, e.g.

if(myScheduleItem < anotherScheduleItem)
if(myScheduleItem > anotherScheduleItem)
if(myScheduleItem == anotherScheduleItem)

2)

I am quite sure I defined operator< and operator> right.

None of your operator functions even return a value. How did they compile? If I compile this program:

Code:

#include<iostream>
using namespace std;

bool test(int a, int b)
{
	a < b;
}

int main()
{
	cout<<test(1, 2)<<endl;

	return 0;

}

I get:

warning C4552: '<' : operator has no effect; expected operator with side-effect
error C4716: 'test' : must return a value

hi
thanks for your reply.

why should I implement operator> etc as member functions?
they dont need any of the private stuff of the class.

I could compile my program without any problems (using devcpp, which uses g++) so I never realised that a > b doesnt return anything.
how come you can use something like (a<b) in a test then?

if I rewrite the operators like this it works!

Code:

bool operator<(const ScheduleItem& si1, const ScheduleItem& si2)
{   if (si1.getend() < si2.getbegin())
        return 1;
    else
        return 0;
}

bool operator>(const ScheduleItem& si1, const ScheduleItem& si2)
{   if (si1.getbegin() > si2.getend())
        return 1;
    else
        return 0; 
}

thanks a lot.

If you also rewrite operator == , deleting from the list should work too.
Kurt

why should I implement operator> etc as member functions?
they dont need any of the private stuff of the class.

As far as I can tell, there's no reason for them to be global functions.

so I never realised that a > b doesnt return anything.
how come you can use something like (a<b) in a test then?

a<b does return something. In my example, a<b returns true. However, the example doesn't do anything with the return value: it's not assigned to anything nor is it returned from the function, so it's discarded. The only way you can return something from a function is in a return statement. If I used a<b in a conditional:

if(a<b)

then in my example a<b would return true, converting the conditional to:

if(true)

which would then cause the if statement to execute.

I could compile my program without any problems (using devcpp, which uses g++)

My C++ book says if the function doesn't return void, then it has to have a return statement or it won't compile.

you're right, I totally forgot about the return-statements in the definition of the operators.

thanks so much

>> As far as I can tell, there's no reason for them to be global functions.

Prefer global functions to member functions if either will do the job. Making the operators non-member, non-friend functions was the correct choice. I don't know how I didn't see the missing return statements, though.

BTW, I had to mention how nice it is to see a homework question where the code used excellent C++ style throughout. Use of standard containers, const correctness, correct use of non-member function for the operators, etc... Your instructor (or you) should be congratulated.

thanks for the nice comment on my coding.

there is one more thing bugging me about this code.

if I change the definition for operator<< in schedule.cc a bit ( by adding an extra std::endl; ) the program crashes at runtime (as mentioned in the first post)

while this is not really a problem in this assignment, I would like to know what exactly causes the crash.

if somebody could enlighten me on this matter I would be very happy

Code:

//original (non-crashing) code

std::ostream& operator<<(std::ostream& os, const Schedule& s)
{   for (std::list<ScheduleItem>::const_iterator i = s.items_.begin(); i != s.items_.end(); i++)
    os << *i;
}

//crashing code

std::ostream& operator<<(std::ostream& os, const Schedule& s)
{   for (std::list<ScheduleItem>::const_iterator i = s.items_.begin(); i != s.items_.end(); i++)
    os << *i << std::endl;
}

the *i I want to put on the outputstream is a ScheduleItem, below is the code of the operator<< for a ScheduleItem.

Code:

std::ostream& operator<<(std::ostream& os, const ScheduleItem& si)
{   os << si.getbegin() << " ";
    os << si.getend() << " ";
    os << si.getdescription() << std::endl;
}

thanks a lot guys!

You need return os; in both of your operator<< functions.

What input are you giving it that causes the crash? If adding the return statements don't fix the issue, you should give the exact steps that lead to the crash.

right, again I forgot the returns.
now it works like it should.

thank you!

>> As far as I can tell, there's no reason for them to be global functions.

Prefer global functions to member functions if either will do the job.

Why?

I would reconsider the structure of your for-loops:

Code:

for (std::list<ScheduleItem>::iterator i = items_.begin(); ; i++)

A for loop without a loop conditional is just an infinite loop, so you might as well just do this:

Code:

for(;;)
{
    ...
}

or 

while(true)
{
    ...
}

Sticking some token statements in the for-loop header seems pointless to me. I also don't really understand this one:

Code:

bool Schedule::insert_item(const ScheduleItem& si)
{   for (std::list<ScheduleItem>::iterator i = items_.begin(); ; i++)
    {   if ((i == items_.end()) || (*i > si))
        {   items_.insert(i, si);
            return 1;
        }
        else if (!(*i < si))
            return 0;
    }
}

The conditional !(*i < si) is the same thing as *i >= si, so the elseif block will only execute if *i==si. The whole thing needs rewriting with a proper loop conditional, maybe something like this:

Code:

bool Schedule::insert_item(const ScheduleItem& si)
{   
	std::list<ScheduleItem>::iterator i = items_.begin();
	
	for(; i != items_.end(); i++)
	{
		if(*i > si)
		{
			items_.insert(i, si);
			break;
		}
	}

	return (i == items.end())? false:true;
}

Originally Posted by 7stud

The conditional !(*i < si) is the same thing as *i >= si, so the elseif block will only execute if *i==si.

a few posts ago I mentioned the scheduleitems are actually intervals.
eg [100 , 200] where 100 is the start, and 200 is the end.

here is the implementation of the operators again (now WITH the returnstatements)

Code:

bool operator<(const ScheduleItem& si1, const ScheduleItem& si2)
{   return (si1.getend() < si2.getbegin());
}

bool operator>(const ScheduleItem& si1, const ScheduleItem& si2)
{   return (si1.getbegin() > si2.getend());
}

scheduleitem1 is greater than scheduleitem2 if 1 starts after 2 ends.
scheduleitem1 is smaller than scheduleitem2 if 1 ends before 2 starts.

this means the elseif block will be executed when the item I want to insert overlaps with an item already in the list.

I will shortly explain what the project is all about, so you can see what the point of this all is
We are supposed to implement something that can hold your appointments. the begin and end are stored in unixtime format.
since you cant have two appointments at the same time, you should make sure that you dont store overlapping appointments in your scheduling system.

I'll think about rewriting the loops, but probably they will still change quite a bit since I am thinking of writing a little helper function that can check if there is a free place in the list to insert the item. and returns a pointer to this place.
since later I also need to check if its possible to insert an element, without really inserting it if I can, it would be nicer to have a helper-function do this than to repeat almost everything from the insert_item function.
still having problems with this helper function atm, but I'll first double-check if I have written down all the returns before I come and ask for some more help.

>> Prefer global functions to member functions if either will do the job.
>> Why?

It's better design. It keeps the class interface from becoming too bloated, and reduces dependencies on class internals.

See Item 44 in C++ Coding Standards (that is the book you would enjoy reading) for more information. It basically says the same thing- nonmember nonfriend functions minimize dependencies which improves encapsulation.