So, I'm having issues with a certain seg fault. I don't really understand what's causing it.
I can perform the following operations with curBall, which is class Ball* type.
Code:
curBall->val
curBall != NULL
It seems though, that when I attempt to perform the following operations that it segfaults.
Code:
curBall->high != NULL
curBall->high->high != NULL
These occur when curBall != NULL is true, so I don't see why these would cause seg faults (or, at least the first of the two).
Part of the problem is that this is a class-assigned TopCoder problem, so I'm not sure what kind of debugging tools I have at my disposal...
The class definition is included in the full code, which is at the end of this post.
I have what seems to be the trouble spot underlined. It's near the end of the whole file.
Code:
#include <map>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;
class Ball
{
public:
int val;
Ball* low;
Ball* high;
Ball() : val(0), low(NULL), high(NULL) { }
};
class OneDimensionalBalls
{
public:
long long countValidGuesses(vector <int> firstPicture, vector <int> secondPicture);
long long cvg(int v);
map <int, Ball*> FP;
map <int, Ball*> SP;
};
long long OneDimensionalBalls::countValidGuesses(vector <int> firstPicture, vector <int> secondPicture)
{
long long rv = 0; // Number of valid guesses.
map <int, int> v; // Map of the velocities to be considered, to prevent looking at same velocities twice. Index is the velocity, value is also the velocity.
map <int, int>::iterator it;
int velocity; // Current velocity being considered.
int i; // Loop control, iteration, etc.
Ball* curBall;
// Passing the picture data to class variables, so other functions can access and organize.
for(i=0; i < firstPicture.size(); i++)
{
curBall = new Ball;
curBall->val = firstPicture[i];
curBall->high = NULL;
curBall->low = NULL;
FP[curBall->val] = curBall;
}
for(i=0; i < secondPicture.size(); i++)
{
curBall = new Ball;
curBall->val = secondPicture[i];
curBall->high = NULL;
curBall->low = NULL;
SP[curBall->val] = curBall;
}
// Get the velocities to be examined
for(i=0; i < secondPicture.size(); i++)
{
// Find a velocity, get its absolute value, and add it to the list to be examined.
velocity = firstPicture[0] - secondPicture[i];
velocity = abs(velocity);
if(velocity != 0)
v[velocity] = velocity;
}
// Get the number of guesses for all velocities
for(it = v.begin(); it != v.end(); it++)
rv += cvg(it->second);
return rv;
}
long long OneDimensionalBalls::cvg(int v)
{
long long rv = 1; // Number of valid guesses for this velocity. Assumed to be 1 for math simplicity.
int i = 0; // Used to count how many consecutive balls in FP have two associated balls in SP.
map <int, Ball*>::iterator fit; // Used to locate specified balls in the first picture.
map <int, Ball*>::iterator sit; // Used to locate specified balls in the second picture.
Ball* curBall; // Ball currently being examined and/or tampered with.
// Iterate through the first picture to find potential pairs.
for(fit = FP.begin(); fit != FP.end(); fit++)
{
// Find the low in the second picture that corresponds to the velocity.
sit = SP.find(fit->second->val - v);
// If a match wasn't found, set the low to NULL.
if(sit == SP.end())
{
fit->second->low = NULL;
}
else
{
// Otherwise, connect the two.
fit->second->low = sit->second;
sit->second->high = fit->second;
}
// Find the high in the second picture that corresponds to the velocity.
sit = SP.find(fit->second->val + v);
// If a match wasn't found, set the high to NULL.
if(sit == SP.end())
{
fit->second->high = NULL;
}
else
{
// Otherwise, connect the two.
fit->second->high = sit->second;
sit->second->low = fit->second;
}
}
// Check to be sure all values in FP have at least one value in SP they match.
for(fit = FP.begin(); fit != FP.end(); fit++)
{
curBall = fit->second;
// If the current ball has nothing it's linked to, there is no valid guess.
if(curBall->low == NULL && curBall->high == NULL)
{
return 0;
}
// If the current ball has no lower ball, but has a higher ball.
if(curBall->low == NULL && curBall->high != NULL)
{
// Remove all connections to curBall->high. This ball can only be linked to curBall.
if(curBall->high->high != NULL)
{
curBall->high->high->low = NULL;
curBall->high->high = NULL;
}
curBall->high->low = NULL;
curBall->high = NULL;
}
// If the current ball has a lower ball, but no higher ball.
else if(curBall->low != NULL && curBall->high == NULL)
{
// Then traverse backwards one ball at a time with curBall through all linked balls, and destroy all links traversed.
while(curBall->low != NULL)
{
curBall = curBall->low;
curBall->high->low = NULL;
curBall->high = NULL;
}
}
}
// At this point, all balls in FP that are still linked should have a high and low assigned to them.
for(fit = FP.begin(); fit != FP.end(); fit++)
{
// Grab the current ball.
curBall = fit->second;
i = 1;
if(fit->second->high == NULL && fit->second->low == NULL)
{
continue;
}
if(curBall != NULL)
{
if(curBall->high != NULL)
{
while(curBall->high->high != NULL)
{
// Find the next "mountain peak". If there is one, move to it and count it.
i++;
curBall = curBall->high->high;
// Destroy connections on the previous "mountain peak" in the set.
curBall->low->low->low->high = NULL;
curBall->low->low->low = NULL;
curBall->low->low->high = NULL;
curBall->low->low = NULL;
}
}
}
// On the final "mountain peak" on this set. Destroy the connections so it's not counted twice.
curBall->low->high = NULL;
curBall->low = NULL;
curBall->high->low = NULL;
curBall->high = NULL;
// Multiply the current return value with this new value.
rv *= (i+1);
}
return rv;
}