Implement in Java a class, skyline . You decide within the class what data struc
ID: 3914919 • Letter: I
Question
Implement in Java a class, skyline. You decide within the class what data structure you want to use to implement thje ADT skyline. You decide what data and member functions will be needed for your skyline class. Using your skyline class, implement two algorithms: an induction algorithm and a divide and conquer algorithm for constructing a skyline from an input list of buildings.
The full details of the problem are below:
The handout being referred to is here:
We have discussed the Skyline Problem in class. We discusses the "list" representation of a skyline, and the triple (L,H,R) representation for a single building. A single building is itself a simple skyline. Two algorithms were discussed in class for constructing a skyline from an input list of buildings Induction order N2 Divide and Conquer order N log N 1. Implement in Java, C++ or Python, etc. (preferably Java if you are not familiar with it) a class, skyline. You decide within the class what data structure you want to use to implement the ADT skyline. You decide what data and what member functions will be needed for your skyline class. I will give a suggestion in class called the "spike" notation. Using your skyline class, implement two algorithms: an Induction algorithm and a Divide-and-Conquer algorithm for constructing a skyline from an input list of buildings. Note you may program in another language if you like. Let me know what language you plan to use 2. Use the following three data sets: sky1.dat, sky2.dat and sky3.dat located for your convenience on our Unix Solaris System and on The data sets are also displayed on the reverse side of this sheet for your reference 3. Turn in a computer listing of all of your code. Your program must be modular, well structured, efficient, well documented, and make use of your skyline class. I reserve the right to ask for an electronic version of your program, but for now it is not required. 4. Output from your program should consist of the resulting skylines depicted in the skyline form (p.h.p.h.p,h,.. p.h) as shown in the handout. Output results for Induction and for Merge for each of the three datasets (six total). Obviously, the output for Induction and Merge for each dataset should be identical. Do not give final results in the spike notation 5. Also draw by hand or machine the skyline results (graphic picture) for each of the three datasets utput must be easy to read, labeled clearly, and of course, accurateExplanation / Answer
#include<iostream>
using namespace std;
struct Building
{
int left; // x coordinate of left side
int ht; // height
int right; // x coordinate of right side
};
class Strip
{
int left; // x coordinate of left side
int ht; // height
public:
Strip(int l=0, int h=0)
{
left = l;
ht = h;
}
friend class SkyLine;
};
// Skyline: To represent Output
class SkyLine
{
Strip *arr;
int capacity;
int n;
public:
~SkyLine() { delete[] arr; }
int count() { return n; }
// A function to merge another skyline
SkyLine* Merge(SkyLine *other);
// Constructor
SkyLine(int cap)
{
capacity = cap;
arr = new Strip[cap];
n = 0;
}
// Function to add a strip 'st' to array
void append(Strip *st)
{
// Check for redundant strip, a strip is
if (n>0 && arr[n-1].ht == st->ht)
return;
if (n>0 && arr[n-1].left == st->left)
{
arr[n-1].ht = max(arr[n-1].ht, st->ht);
return;
}
arr[n] = *st;
n++;
}
// A utility function to print all strips
void print()
{
for (int i=0; i<n; i++)
{
cout << " (" << arr[i].left << ", "
<< arr[i].ht << "), ";
}
}
};
// This function returns skyline for a given array of buildings
SkyLine *findSkyline(Building arr[], int l, int h)
{
if (l == h)
{
SkyLine *res = new SkyLine(2);
res->append(new Strip(arr[l].left, arr[l].ht));
res->append(new Strip(arr[l].right, 0));
return res;
}
int mid = (l + h)/2;
SkyLine *sl = findSkyline(arr, l, mid);
SkyLine *sr = findSkyline(arr, mid+1, h);
SkyLine *res = sl->Merge(sr);
// To avoid memory leak
delete sl;
delete sr;
// Return merged skyline
return res;
}
SkyLine *SkyLine::Merge(SkyLine *other)
{
// Create a resultant skyline with capacity as sum of two
// skylines
SkyLine *res = new SkyLine(this->n + other->n);
// To store current heights of two skylines
int h1 = 0, h2 = 0;
// Indexes of strips in two skylines
int i = 0, j = 0;
while (i < this->n && j < other->n)
{
// Compare x coordinates of left sides of two
// skylines and put the smaller one in result
if (this->arr[i].left < other->arr[j].left)
{
int x1 = this->arr[i].left;
h1 = this->arr[i].ht;
// Choose height as max of two heights
int maxh = max(h1, h2);
res->append(new Strip(x1, maxh));
i++;
}
else
{
int x2 = other->arr[j].left;
h2 = other->arr[j].ht;
int maxh = max(h1, h2);
res->append(new Strip(x2, maxh));
j++;
}
}
// If there are strips left in this skyline or other
// skyline
while (i < this->n)
{
res->append(&arr[i]);
i++;
}
while (j < other->n)
{
res->append(&other->arr[j]);
j++;
}
return res;
}
// drive program
int main()
{
Building arr[] = {{1, 11, 5}, {2, 6, 7}, {3, 13, 9},
{12, 7, 16}, {14, 3, 25}, {19, 18, 22},
{23, 13, 29}, {24, 4, 28}};
int n = sizeof(arr)/sizeof(arr[0]);
// Find skyline for given buildings and print the skyline
SkyLine *ptr = findSkyline(arr, 0, n-1);
cout << " Skyline for given buildings is ";
ptr->print();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.