Thread: dreaded skyline D&C algo

hey all...I'm working on this Skyline problem, and I'm stuck. I'm not really sure how to merge the two arrays together according to the requirements. If you are not familiar with the Skyline Problem here it is in a nutshell:

There is a city with no hills and has a set of rectangular buildings. Suppose you are viewing the city from water. Leftmost position of city is used as reference point ( horiz position 0 ). This, a building can be speified by (l, h, w), where l gives the left boundary, h the height of the buildingsm and w its width.

the program will take as input a set of n buildings, in no particular order. The program now has to extract the outline formed by the buildings. This skyline will be formed by a sequence of horizontal segments starting at position 0. It will be represented by a equence of pairs (h, w) where h is the height abd w the width.

Code:

So basically if the input from a file is:
(13, 3 4), (3,6,6,), (1,2,9), (14, 2,5), (18,4,2)
the corresponding output will be:
(0,1), (2,2), (6,6), (2,1),(0,3),(3,4),(2,1),(4,2)

Unfortunately one of the requirements is that I have to use arrays, which is very annoying. It would be much simpler using linked lists.... anyways, here is the code I have so far...and the following errors arise about my recursion:

Code:

main.cpp(81) : error C2668: 'divide' : ambiguous call to overloaded function

Code:

#include <iostream>
#include <cstdlib>
#include <cctype>
#include <string>
#include <fstream>
using namespace std;

struct Skyline
{
	int x;
	int y;
	Skyline *n;
};

int* divide( int *B, int *O, int n);

void skyMerge(int *, int, int*, int, int*, int);

int main()
{
		ifstream inFile;		//text file IO
		ofstream outFile;
		
		string inFileName;		
		string outFileName;
		
		int numberOfBuildings;	//first number from file
		//float descriptions;
		char tmp[1];			//holding the characters from file
		int i = 0;				//counter
		int j = 0;				//counter
		
		inFile.open("hey.txt");
        inFile>>numberOfBuildings;

		//allocating memory for the size of the input file
		int *B = new int[numberOfBuildings*3]; 
		int *O = new int[numberOfBuildings*3];
		
		for( i = 0; i < (numberOfBuildings*7); i++ ){
			inFile>>tmp[0];
			if( isdigit(tmp[0]) ) {
				B[j] = atoi(tmp);
				j++;
			}
		}		

		divide(B, O, numberOfBuildings);

	return 0;
}

int* divide(int *B, int *&O, int n)
{
	if ( n == 1 )
	{
		return O;
	}
	
	int n1 = (n/2);
	int n2 = (n - n1);

	int *skyLeft = new int[n1*3];
	int *skyRight = new int[n2*3];

	divide(B, skyLeft, n1);
	divide(B, skyRight, n2);

	skyMerge(skyLeft, n1, skyRight, n2, O, n);


}

void skyMerge(int *s1, int n1, int *s2, int n2, int *&O, int n)
{

}

any ideas? suggestions?

I fixed that one error....but I still think that I'm not doing it right.

Code:

int* divide(int *B, int *&O, int n, int maxWidth)
{
	if ( n == 1 )
	{
		return O = B;
	}
	
	int n1 = (n/2);
	int n2 = (n - n1);

	int *skyLeft = new int[n1*3];
	int *skyRight = new int[n2*3];

	divide(&B[n1], skyLeft, n1, maxWidth);
	divide(&B[n2], skyRight, n2, maxWidth);

	//skyMerge(skyLeft, n1, skyRight, n2, O, n);


}

Code:

int* divide(int *B, int *&O, int n, int maxWidth)

What are you trying to pass to the function? Arrays? Or do you want a single integer to be passed? If you need to be able to change the variable, but it is not an array, try a reference :

Code:

int* divide(int& B, int& O, int n, int maxWidth)
{


}

Also note that I don't know what you want to do with the return value, so you may want to change that as well.

If you are trying to pass an entire array, pass pointers (remove the '&' before the 'O'):

Code:

int* divide(int* B, int* O, int n, int maxWidth)
{
//...
}

thanks jawib...I emailed my prof and he let me do it with linked lists hurrah! I'll post the finished prog later tonite.

I do hate arrays in complicated algos....seriously this is a data struct class....so why did he make the array requirement?