In c++ using a binary search tree Applications of BST Consider the plan-landing

Question

In c++ using a binary search tree

Applications of BST Consider the plan-landing problem we have discussed in the class where an airport has one runway and planes request landing. Constraints is that runway request will be granted only if there is a K time gap from either side of the landing request. For example, suppose K = 3 and a plane request landing time 56. If there are landing requested for 60 and 45 already granted, then the differences from either sides are 60-56 = 4 and 56-45 = 11. Satisfies the K = 3 constraint. Landing request will be granted. However, if landing times 58 and 45 have already been granted, then 58-56 = 2, which is less than 3. So, landing request will not be granted. In this problem, you will be implementing several functionalities of this plane landing system using BST ("Landing times BST"). Your plane landing system should first ask for the K value from the user, then implement the following functionalities. Your landing times BST should store the landing time (use as the key) and the plane flight number in the node. A) Request landing-input for this functionality is the landing time. You can consider the current time as zero. If the landing time request satisfies the K constraint, grant the landing time and insert the landing time to the landing times BST. B) Withdraw landing request-A plane can withdraw landing request. This may be due to delay and cancel flight. In this case, remove the landing request from the landing BST. C) List landing times and the flight number-display the landing times and flights in the landing times BST. Write a C or C++ program that Implements above functionality

Explanation / Answer

The C++ program is as follows-

class Aircraft
{
private:
double altitude, airSpeed;
public:
Aircraft()
{
altitude = 0;
airSpeed = 0;
}
virtual void takeoff();
void fly();
void land();
};

Aircraft.cpp

For now these methods simply display diagnostic messages:

void Aircraft::takeoff()
{
cout << "an aircraft is taking off ";
}

void Aircraft::fly()
{
cout << "an aircraft is flying ";
}

void Aircraft::land()
{
cout << "an aircraft is landing ";
}

Airplane.h

Airplane, Helicopter, and Blimp are derived from Aircraft. Here's the declaration of Airplane, Helicopter and Blimp are similar:

class Airplane :
public Aircraft
{
public:
void takeoff();
void fly();
void land();
};

Airplane.cpp

Airplane overrides the inherited takeoff, fly, and land methods with ones that display different diagnostic messages:

void Airplane::takeoff()
{
cout << "an airplane is taking off ";
}

void Airplane::fly()
{
cout << "an airplane is flying ";
}

void Airplane::land()
{

cout << "an airplane is landing ";
}

Helicopter and Blimp are similar.

Fleet.h

The Fleet class maintains an array of 100 Aircraft pointers. Note that the members array must contain pointers or references rather than the actual Aircraft objects. This is because the Liskov Substitution principle in C++ only applies to pointers:

A variable of type T* can hold values of type S* for S a subtype of T.

#define cap 100

class Fleet
{
private:
int size;
Aircraft* members[cap];
public:
Fleet() { size = 0;}
void add(Aircraft* a)
{
if (size < cap)
{
members[size++] = a;
}
}
void takeoff();
void fly();
void land();
};

Fleet.cpp

Fleet's takeoff, fly, and land methods are bulk operations. They simply ask each member to execute the corresponding takeoff, fly, or land method.

void Fleet::takeoff()
{
for(int i = 0; i < size; i++) {

members[i]->takeoff();
}
}

void Fleet::fly()
{
for(int i = 0; i < size; i++) {
members[i]->fly();
}
}
void Fleet::land()
{
for(int i = 0; i < size; i++) {
members[i]->land();
}
}

Output

Our main method creates a fleet consisting of an airplane, a helicopter, a blimp, and a generic aircraft. Every member is asked to takeoff, then every member is asked to land:

void main()
{
Fleet united;
united.add(new Aircraft());
united.add(new Airplane());
united.add(new Helicopter());
united.add(new Blimp());
united.takeoff();
cout << "+++++ ";
united.land();
}

The output of main shows that the individual objects decided which takeoff method to execute, while the compiler decided which land method to execute:

an aircraft is taking off
an airplane is taking off
a helicopter is taking off
a blimp is taking off
+++++
an aircraft is landing
an aircraft is landing
an aircraft is landing
an aircraft is landing

Aircraft.h (version 2)

To duplicate the behavior of a virtual method in the Control-Driven paradigm, the programmer must explicitly type each aircraft:

class Aircraft
{
public:
enum Type { AIRPLANE, HELICOPTER, BLIMP, UNKNOWN};
Aircraft(Type t)
{
altitude = 0.0;
airSpeed = 0.0;
type = t;
}
Aircraft()
{
altitude = 0.0;

airSpeed = 0.0;

type = UNKNOWN;
}
virtual void takeoff();
void fly();
void land();
Type getType() { return type; }
private:
double altitude, airSpeed;
Type type;
};

Airplane.h (version 2)

The default Airplane, Helicopter, and Blimp constructors must invoke the new Aircraft constructor:

class Airplane :
public Aircraft
{
public:
Airplane(): Aircraft(Aircraft::AIRPLANE) {}
void takeoff();
void fly();
void land();
};
Fleet.cpp (version 2)

Fleet's land method uses a switch statement to dispatch to the correct method:

void Fleet::land()
{
for(int i = 0; i < size; i++)
{
switch(members[i]->getType())
{
case Aircraft::AIRPLANE:
((Airplane*)members[i])->land(); break;
case Aircraft::HELICOPTER:
((Helicopter*)members[i])->land(); break;
case Aircraft::BLIMP:
((Blimp*)members[i])->land(); break;
default: members[i]->takeoff();
}
}
}

Output (version 2)

an aircraft is taking off
an airplane is taking off
a helicopter is taking off
a blimp is taking off
+++++
an aircraft is taking off
an airplane is landing
a helicopter is landing
a blimp is landing

Both methods work. Certainly the Data-Driven style is much shorter. But there are several other advantages.

Suppose CyberAir wants to add a new type of aircraft into their Aircraft hierarchy:

class Saucer :
public Aircraft
{
public:
Saucer(): Aircraft(Aircraft::Saucer) {}
void takeoff();
void fly();
void land();
};

The control-driven programmer must now add a line to Fleet.land():

case Aircraft::SAUCER:
((Saucer*)members[i])->land(); break;

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.