# Getting a count of intervals

The statement of the problem is there are 2 files, one has a set of intervals i.e. 0-10, 3-40, etc which may be repetitive. The second file has a set of numbers which are also repetitive. The exercise is to get a count of the intervals, a number in the 2nd file would fit into.

Intervals.txt

0 12
2 36
6 98
2 36


Numbers.txt

2
4
123
20


What I thought of as a possible solution was keep a count of intervals when you populate a map of intervals. So if you encounter an interval 3-40 5 times, you keep the count as 5 so you don't try to populate a map 5 times with the same interval. How it helps downstream is, if a number is in a specific interval you can count its existence in 5 intervals. Secondly there is a map of found numbers in your previous iterations, so that you don't loop through the intervals again.

I have been told, by some random guy, that my implementation is ok but not what he desires. No further explanations. I have tried raking my brain but haven't got any further. Any pointers or help would be much appreciated. Any further clarifications, please ask.

void generateCounts(const string& fname1, const string& fname2)
{
std::ifstream file(fname1.c_str());
string line;
map<int, pair<int, int> > extents;
map<int, pair<int, int> >::iterator it;
std::string left;
std::string right;

if(file.is_open())
{
while(file.good())
{
getline(file, line);
string::size_type pos = line.find(' ');
left = line.substr(0, pos);
right = line.substr((++pos));
int ll = atoi(left);
int up = atoi(right);
it = extents.find(ll);
if(it != extents.end())
{
if(it->second.first != up){
extents.insert(make_pair<const int, pair<int, int> >(ll, make_pair<int, int>(up, ++count)));
}
else{
it->second.second += 1 ;
}
}
else
{
extents.insert(make_pair<const int, pair<int, int> >(ll, make_pair<int, int>(up, ++count)));
}
count = 0;
}
}
fclose(inp_file);

std::ifstream file1(fname2.c_str());
map<int, int> found;
map<int, int>::iterator it1;
string str;
if(file1.is_open())
{
while(file1.good())
{
count = 0;
getline(file1, str);
if(str.empty()) continue;
int var = atoi(str.c_str());
it1 = found.find(var);
if (it1 == found.end())
{
for(it = extents.begin(); it != extents.end(); ++it)
{
if((var >= it->first ) && (var <= it->second.first))
{
count += it->second.second ;
}
}
found.insert(make_pair(var, count));
}
else
count = it1->second;

cout << count << "\n";
str.clear();
}
file1.close();
}


OK. Since this is homework I am going to limit my points to hints (I may add more in a week or so).

1. Why are you doing this?

if(file.is_open())

2. This is an anti-pattern (in every language not just C++):
Remember the eof (part of not being good) does not happen until you read past the end of line.

Lots of examples on SO (go look it up).

    while(file.good())
{
getline(file, line);

3. You are doing too much work here:

There is an easy way to read integers from a stream. Lots of examples on SO (go look it up).

    getline(file, line);
string::size_type pos = line.find(' ');
left = line.substr(0, pos);
right = line.substr((++pos));   // Also this is wrong if no space was found.
int ll = atoi(left);
int up = atoi(right);

4. Why do a 2-phase compare?

    if(it != extents.end())
{
if(it->second.first != up){
extents.insert(make_pair<const int, pair<int, int> >(ll, make_pair<int, int>(up, ++count)));
}
else{
it->second.second += 1 ;
}
}
else
{
extents.insert(make_pair<const int, pair<int, int> >(ll, make_pair<int, int>(up, ++count)));
}


If you make the key std::pair&lt;left, right&gt; then you only need to do one test. Not this complicated mess. It also makes more sense to keep the left and right together.

5. Don't do this: (see Implementation using fstream failed evaluation)

fclose(inp_file);


 if((var >= it->first ) && (var <= it->second.first))

• @DumbCoder: 3) Yes. There is still a much better way built into the language io libraries (hint: atoi() is old school C). 4) Yes exactly why the key should be std::pair<left, right> so the find() can find an exact mach without you doing extra work. ie the map is std::map<std::pair<left, right>, count> Commented Sep 10, 2012 at 16:24