Debugging binary search in a vector

[klearner]

I have some code where I am attempting to build a vector and keep it in order by name. When a new planet is added, I binary search by name and then slide everything to make room. If I add planets a, then c, then b it puts b at the beginning rather than in between a and c. after that, it seems to function well. I don't have access to a debugger, so it's been painful trying to figure it out. Any thoughts would be appreciated.

#include <iostream>
#include "input.h"
#include <vector>
#include <string>
#include <cmath>

using namespace std;

const double G = 6.67408e-11;

class Planet
{
private:
	double radius;
	double mass;

public:
	Planet();
	string name;
	double SArea();
	double Density();
	double g();
	void Input();
	void Display();
	bool SetName(string n);
	bool SetRadius(double r);
	bool SetMass(double m);

};

void AddPlanet(vector<Planet>& l);
void DelPlanet(vector<Planet>& l);
void AddToList(vector<Planet>& l, Planet newp);
void ListAll(vector<Planet>& l);
void Remove(vector<Planet>& list, int idx);
bool BinSearch(vector<Planet>& l, string n, int& index);
int menu();




int main()
{
	vector<Planet> PList;
	int choice=0;
	do
	{
		choice=menu();
		if (choice==1)
		{
			AddPlanet(PList);
		}
		else if(choice==2)
		{
			DelPlanet(PList);
		}
		else if(choice==3)
		{
			int i=0;
			if(BinSearch(PList,ReadString("Planet Name? "), i)==false)
			{
				cout << "Planet not found" << endl;
			}	
			else
			{
				PList[i].Display();
			}
		}
		else if(choice==4)
		{
			ListAll(PList);
		}
		else 
		{
			cout<<"Goodbye"<<endl;
		}
	} while(choice!=5);
	return 0;
}
 
int menu()
{
	int rv=0;
	do
	{
		cout<<"1. Add Planet"<<endl;
		cout<<"2. Delete Planet"<<endl;
		cout<<"3. Search Planet"<<endl;
		cout<<"4. List All"<<endl;
		cout<<"5. Quit"<<endl;
		rv=ReadInt("Choose one of the above options");
	} while(rv<1||rv>5);
	return rv;
}


Planet::Planet()
{
	name = "Dummy";
	radius = 0.0;
	mass = 0.0;
}

double Planet::SArea()
{
	return 4*M_PI*pow(radius, 2);
}
double Planet::Density()
{
	return 4/3*M_PI*pow(radius, 3);
}
double Planet::g()
{
	return G * mass / pow(radius, 2);
}

bool Planet::SetName(string n)
{
	bool rv = false;
	if (n.length()>0)
	{
		name=n;
		rv = true;
	}
	return rv;
}

bool Planet::SetRadius(double r)
{
	bool rv = false;
	if (r>0.0)
	{
		radius=r;
		rv = true;
	}
	return rv;
}

bool Planet::SetMass(double m)
{
	bool rv = false;
	if (m>0.0)
	{
		mass=m;
		rv = true;
	}
	return rv;
}

void Planet::Input()
{
	while(SetName(ReadString("Name?"))==false)
		cerr<<"Planet must have a name\n";
	while(SetRadius(ReadDouble("Radius?"))==false)
		cerr<<"Value must greater than zero\n";
	while(SetMass(ReadDouble("Mass?"))==false)
		cerr<<"Value must greater than zero\n";
}

void Planet::Display()
{
//	cout << "Place in list: " << i << endl;
	cout << "Planet: " << name << endl;
	cout << "Radius: " << radius << endl;
	cout << "Mass: " << mass << endl;
	cout << "Surface Area: " << SArea() << endl;
	cout << "Density: " << Density() << endl;
	cout << "Gravitational Acceleration: " << g() << endl;
}

void AddPlanet(vector<Planet>& l)
{
	Planet newp;
	newp.Input();
	AddToList(l, newp);
}

void DelPlanet(vector<Planet>& l)
{
	int killp;
	killp = ReadInt("What place in list do you want to delete? ");
	Remove(l, killp);
}

void ListAll(vector<Planet>& l)
{
	if(l.empty()==0)
	{
		for(int i=0; i <=l.size()-1; i++)
		{
			l[i].Display();
		}
	}
	else
	{
		cout << "The list is empty." << endl;
	}
}



void AddToList(vector<Planet>& l, Planet newp)
{
	l.push_back(newp);
	int idx=0;
	BinSearch(l,newp.name,idx);
	for(int i=l.size()-1; i>idx; i--)
	{
		l[i]=l[i-1];
	}
	l[idx]=newp;
}

void Remove(vector<Planet>& list, int idx)
{
	for(int i=idx; i < list.size()-1; i++)
	{
		list[i]=list[i+1];
	}
	list.pop_back();
}

bool BinSearch(vector<Planet>& l, string n, int& index)
{
	bool found=false;
	index=0;
	if (l.empty()==0)
	{
		int curIndex=0;
		int left=0;
		int right=l.size()-1;
		bool done=false;
		while(done==false)
		{
			curIndex=(left+right)/2;
			if(l[curIndex].name==n)
			{
				done=true;
				found=true;
			}
			else
			{ 
				if(l[curIndex].name>n)
				{
					right=curIndex-1;
				}

				else if(l[curIndex].name<n)
				{
					left=curIndex+1;
				}
			}
			if (left>right)
			{
				done=true;
			}
			index=curIndex;
		}
	}
	return found;
}

#include <string>

using namespace std;

double ReadDouble(string prompt);
int ReadInt(string prompt);
string ReadString(string prompt);

#include <iostream>
#include <string>
#include "input.h"
using namespace std;

int ReadInt(string prompt)
{
	int rv = 0;
	cout<< prompt << endl;
	bool done = false;
	while(done == false)
	{
		cin>> rv;
		if(cin.fail() != 0)
		{
			cerr<< "Cannot read data." << endl;
			cin.clear();
			cin.ignore(256,'\n');
		}
		else
		{
			done = true;
		}
	}
	return rv;
}

double ReadDouble(string prompt)
{
	double rv = 0.0;
	cout<< prompt << endl;
	bool done = false;
	while(done == false)
	{
		cin>> rv;
		if(cin.fail() != 0)
		{
			cerr<<"Cannot read data."<<endl;
			cin.clear();
			cin.ignore(256,'\n');
		}
		else
		{
			done = true;
		}
	}
	return rv;
}

string ReadString(string prompt)
{
	string rv = "";
	cout<< prompt << endl;
	bool done = false;
	while(done == false)
	{
		cin>> rv;
		if(cin.fail() != 0)
		{
			cerr<<"Cannot read data."<<endl;
			cin.clear();
			cin.ignore(256,'\n');
		}
		else
		{
			done = true;
		}
	}
	return rv;
}

[cire]

I don't have access to a debugger, so it's been painful trying to figure it out. Any thoughts would be appreciated.

Thoughts: Reduce the code to a minimal subset that reproduces the problem. This not only helps you locate the problem, it makes it easier for other people to help you and more likely for responses to occur at all.

BinSearch returns a value. Perhaps you should use it for something.

A binary search requires a sorted array. Do not insert your string before you find the place where it should be inserted. Also, consider using std::lower_bound or std::upper_bound instead of your overly complex home-grown version of a binary search.

You might also consider using a container that keeps itself sorted (such as std::set) so you don't have to manually keep things sorted.

[klearner]

Never mind, I solved it. In BinSearch I needed to add after line 250:

curIndex++;