COMP 250 Building Management

2.1    Introduction

You are having co ee with one of your friends named Paul. Paul recently graduated and is now working for a Town Housing O ce. He seems to be enjoying his work : the buildings that they are managing are quite old now, so they need to be renovated. He tells you more about this and then asks what you are up to. So you tell him about that amazing class (COMP250) that you are following. You tell him about binary search trees.

Paul looks puzzled and interrupts you to ask : \That’s cute, but what’s the point of this ?". You answer : \you are using software and database in your everyday work life, I am learning how to write them". But Paul is looking as if he does not believe you, so you add \let me show you. I will show you how the database you use at the o ce works".

\Ok, so you talked a great deal about how old your buildings are, this is how I am going to organize the database. What else is important on your buildings ?". Paul gets overly enthusiastic, so you restrict the list of important features to just a few : \Paul, I am not going to include the guy who designed it or what techniques were used to build the building. I only want to give you an idea of how the software you are using everyday is working !".

2.2    Organization of the code you are provided with :

The database of all buildings is going to be represented by a tertiary tree. We have separated the data associated to one building and the tree structure.

The class OneBuilding represents the data associated to a speci c build-ing. A OneBuilding has several elds : rst its name (it can represent the address or the name for instance). A OneBuilding also has a year of con-struction (yearOfConstruction), a height (height), a year when it is likely to need to be repaired (yearForRepair) and the projected cost of those repairs (costForRepair).

A Building bears the tree structure. A Building has a eld data bear-ing the information. A Building has also three elds of type Building

    • older, same and younger. These are going to allow you to construct a tertiary tree representing all the buildings. As the names suggest, given a Building b, the Building b.older and all its children were built before Building b was built, the Building b.younger and all its children were built after Building b was built and the Building b.same and all its chil-dren were built the same year as Building b was built. We also ask that


3





the buildings of same year of construction are sorted by decreasing height. You are also provided with a tester. The tester is VERY partial. Even

if your code seems to work, it does not mean that your code is correct : it only means that your code is working ON AN EXAMPLE. You NEED to expand the tester.

You do not need to import any other code (and if you do, you will get 0).

All the material needed for this assignment was covered during class.

2.3    Building your database

First thing to do is to add buildings in your tree structure.

Question 1. First, code addBuilding. The argument is the OneBuilding that you want to add to the tree structure.

Given a Building b and a OneBuilding obToAdd, b.addBuilding(obToAdd) adds the OneBuilding obToAdd in the tree with root b accordingly to the rules explained before : if obToAdd is older (resp. younger) than b.data,

it has to be added (in the appropriate place) to the subtree b.older (resp. b.younger). if obToAdd is the same age as b.data, then it depends on the height : if obToAdd is strictly higher than b.data, it becomes the new root and you have to adapt the other elds accordingly.

To clarify, let us give some examples. At the nodes of the tree, you will see

(for instance) b1(1987; 50). This means Building b1 has data.yearOfConstruction 1987 and data.height 50. When the elds older, same or younger are not

null, we represent them with an arrow to the corresponding Building. Let us start with the following tree :

b1(1987; 50)


b1:older    b1:younger

    • (

b6(1985; 60)    b2(1988; 60)




b2:younger
b6:same



(
b4(1985; 50)
b8(1995; 55)


b4:same


b5(1985; 45)

Now, if we have a One Building ob3 with yearOfConstruction 1987, height 55, the command b1.addBuilding (ob3) should return a Building where




4





the root b3 has data ob3 and the    elds should have been updated to :

b3(1987; 55)


b3:older    b3:same    b3:younger


v
(

b6(1985; 60)
b1(1987; 50)
b2(1988; 60)


b2:younger




b6:same





(
b4(1985; 50)

b8(1995; 55)


b4:same


b5(1985; 45)

If OneBuilding ob7 has yearOfConstruction 1986 and height 55, then the command b3.addBuilding(ob7) should return b3 and the tree structure should be updated to :

b3(1987; 55)




b3:older






b3:same  b3:younger


s



(







b6(1985; 60)

b1(1987; 50)
b2(1988; 60)




b2:younger






b6:same  b6:younger






(



(
b4(1985; 50)
b7(1986; 55)



b8(1995; 55)


b4:same


b5(1985; 45)

with b7.data = ob7.

Question 2. You can now code addBuildings. The argument is a Building.

Given a Building b and a Building bToAdd, the command b.addBuildings(bToAdd) rst adds the OneBuilding bToAdd.data to b, then goes on by adding the Building bToAdd.older, then bToAdd.Same and nally bToAdd.younger

and returns the root of the tree structure as in the case for addBuilding.

For instance, if we have the two following Buildings :



b3(1987; 55)

b6(1985; 60)

b3:older

b6:younger







b3:same  b3:younger


w


’
’
b4(1985; 50)
b1(1987; 50)
b2(1988; 60)
b7(1986; 55)




b7:younger






b4:same









’
b5(1985; 45)



b8(1995; 55)


5





The command b1.addBuildings(b6) will return b1 and update the tree structure to :

b3(1987; 55)




b3:older






b3:same  b3:younger


s



(







b6(1985; 60)

b1(1987; 50)
b2(1988; 60)




b2:younger






b6:same  b6:younger






(



(
b4(1985; 50)
b7(1986; 55)



b8(1995; 55)


b4:same


b5(1985; 45)

Question 3. Now you can code removeBuilding. Its argument is a OneBuilding. The command b.removeBuilding (ob) should return either b if no children

of b has data corresponding to ob, or the root of the tree corresponding to b where the OneBuilding ob has been removed otherwise.

You should not remove any of the children of the Building with data corresponding to ob. For the rest of the explanation, let us assume that b.data == ob (you can easily adapt what is going to be said to the case where the Building to remove is not the root). In this case, there are three cases to consider. First, if b.same != null, then the new root becomes b.same and the subtrees of b should be correctly attached to the new root. Second, if b.same == null and b.older != null, then the new root be-comes b.older and you need to add the OneBuildings in b.younger to this new root. Finally, if b.same == null and b.older == null, then the new root is b.younger (note that this also covers the case when b is a leaf).
hint : you just coded addBuildings

On an example, consider

b3(1987; 55)




b3:older






b3:same  b3:younger


s



(







b6(1985; 60)

b1(1987; 50)
b2(1988; 60)




b2:younger






b6:same  b6:younger






(



(
b4(1985; 50)
b7(1986; 55)



b8(1995; 55)


b4:same


b5(1985; 45)



6





The command b3.removeBuilding(b3.data) should return the new root b1 with elds updated to :

b1(1987; 50)


b1:older    b1:younger

    • (

b6(1985; 60)    b2(1988; 60)




b2:younger
b6:same  b6:younger



(
(
b4(1985; 50)
b7(1986; 55)
b8(1995; 55)


b4:same


b5(1985; 45)

The command b1.removeBuilding(b1.data) should now return the new root b6 with elds updated to :

b6(1985; 60)


b6:same    b6:younger

(

b4(1985; 50)    b7(1986; 55)


b4:same    b7:younger

     (
b5(1985; 45)    b2(1988; 60)


b2:younger

(
b8(1995; 55)

2.4    Showing Paul how powerful this is

Congratulations, you can now construct a database, you are now going to exploit this to nd out useful information. In all the remaining questions, you should not modify the tree structure anymore.

Paul : \Those numbers are ridiculous, that’s not how high a building is or how much it costs to repair a building !"

you : \I do not work on buildings, if you are unhappy about those num-bers, you can either change them or imagine they are in a di erent unit."

Paul : \Oh, OK. So what now ?"

you : \well, I can compute things. For instance, I can easily tell you when the oldest building was constructed."

Question 4. Code oldest. When called on a Building b, the integer b.oldest() should be the year when the oldest Building in the tree with root b was built. Do not modify the tree structure.

7





Let us give you an example. At the nodes of the tree, you will see for in-stance b1(1950; 10). This means Building b1 has data.yearOfConstruction 1950 and data.height 10.

b3(1987; 55)




b3:older






b3:same  b3:younger


s



(







b6(1985; 60)

b1(1987; 50)
b2(1988; 60)




b2:younger






b6:same  b6:younger






(



(
b4(1985; 50)
b7(1986; 55)



b8(1995; 55)


b4:same


b5(1985; 45)

b3.oldest() should return 1985 and b1.oldest() should return 1987.


Paul : \Can you tell me how high is the highest building then ?"

you : \Yes. But it is missing the point of having my database organized by year of construction though."

Question 5. Code highest. When called on a Building b, the integer b.highest() should be the height of the highest Building in the tree with root b. Do not modify the tree structure.

On the example given to you in question 4, b3.highest() should return 60 and b4.highest() should return 50.


Paul : \You said that I was missing a point on the organization of the database."

you : \Well, I decided to organize buildings by their years of construc-tion, so it is very e cient to answer questions based on this parameter. For instance, instead of how high the highest building is, I can tell you which one is the highest building constructed on a certain year."

Question 6. Code highestFromYear. When called on a Building b, the OneBuilding b.highestFromYear(year) should be the OneBuilding that was the highest built in year year and that is in the tree with root b (and null if there are none). Do not modify the tree structure.

On the example from question 4, b3.highestFromYear(1985) should re-

turn b6.data, and so should b6.highestFromYear(1985), but b4.highestFromYear(1985) should return b4.data.

8





Paul : \Can you answer questions based on multiple years ?"

you : \Yes, for instance, I can tell you how many buildings were built during the time from one year to another one."

Question 7. Code numberFromYears. When called on a Building b, the integer b.numberFromYears(yearMin, yearMax) should be the number of Buildings built from year yearMin to yearMax (including those two years) that is in the tree with root b. If yearMin > yearMax, this should return 0. Do not modify the tree structure.

On the example from question 4, b3.numberFromYears(1986, 1988) should return 4 (corresponding to buildings b7, b3, b1 and b2).


Paul : \That’s pretty cool ! Can this also help us plan the renovation of the buildings ?"

you : \yes"

Question 8. Code costPlanning. When called on a Building b, the array b.costPlanning(n) should have in its i-th cell, how much you should spend on year (2018 + i) to repair all the scheduled buildings in the tree with root b. The argument n will always be a positive integer. Do not modify the tree structure.

Let us modify the example given in question 4 to only display the year planned for repairs and the costs for such repairs.

b3(2024; 23)




b3:older






b3:same  b3:younger


s



(







b6(2024; 26)

b1(2025; 35)
b2(2023; 50)




b2:younger






b6:same  b6:younger






(



(
b4(2022; 5)
b7(2024; 11)



b8(2019; 46)


b4:same


b5(2021; 42)

On this example, b3.costPlanning(7) should return the array {0, 46, 0, 42, 5, 50, 60} :

in year 2018, there is no cost to plan for repairing the buildings, but in year

2024, buildings b3, b6 and b7 will need to be repaired, for a cost of 23

    • 26 + 11 = 60. Similarly, b2.costPlanning(7) should return the array {0, 46, 0, 0, 0, 50, 0}.




9