Introduction to Data Structures and Algorithms
Assignment 5: General Tree

  • Due 28 June , 7pm

What To Hand In

  • Position.java
  • OrganisationChart.java
  • CPNCalculator.java

Do not rename these files.

Remember to submit all of these files. When you have submitted them, check that you can read the files listed on the submission page, and complete the submission process.

In order to make sure your code can be recognised correctly by our automatic marking program, please notice the following strict rules when implementing your program:

  • You are NOT allowed to change any code provided in Template, including the headers, the names or parameters of any existing methods. You can add new methods, but do not change the names/parameters of any existing methods.
  • You are NOT allowed to delete any constructors in any classes. You are not allowed to change the headers of any existing constructors.
  • Do NOT rename any file provided in the Template.
  • Make sure the output of your program matches exactly the example given in the grey boxes below. Please note that the printed out message is compared with the model solutions. If you print out any debugging messages, your answer will not match with our model solutions. So please remember to comment out or delete any lines that print any extra information.

Part 1: OrganisationChart (Weight: 1/2)

Many organisations are structured in a hierarchy with a CEO at the top, and then all the other positions below in a management hierarchy.

You are to complete the OrganisationChart program which allows the user to display and edit a chart of an organisation structure that displays the structure as a tree of positions with the CEO at the root of the tree. The links in the tree represent the management structure.

The main data structure in the program is a general tree of Position objects, where the tree structure is stored directly in the fields of the Position objects.

Each Position has fields for
  • information about the role
  • an Employee (who has a name and an id) or null to show the Position is vacant.
  • a manager - the Position that this Position reports to (except for the root node, which has no manager)
  • a team - a set of other Positions that report to this Position (possibly an empty set)
Note that each node in this tree not only has links to its child nodes, but also has a link to its parent node (the position's manager), which makes it easier to "move around", but makes modification more tricky because both upward and downward links may have to be modified.

The user can modify the organisation chart by
  • Selecting a Position by clicking on it. The selected Position becomes highlighted.
  • Renaming a Position, by selecting the Position then typing the new role in the "Change Role" textfield.
  • Removing a Position, by dragging it to the "retirement" icon.
    Only Positions that are vacant (no employee) and have no team members (child nodes) can be removed.
  • Moving an existing Position to be under a different manager by dragging it to the new manager.
    All the Position's team members (ie, the whole subtree) will move with the Position.
    (note, you shouldn't be able to move a Position to be managed by a Position in the subtree under the Position.)
  • Creating a new Position, by dragging the New Position icon to its new manager.
  • Moving an existing Employee to a vacant Position in the chart by dragging the Employee (the oval within a Position) to their new Position.
    An Employee can only be moved to a vacant Position.
  • Retiring an Employee by dragging them to the retirement icon.
  • Adding a new Employee to the chart by selecting an vacant Position, then typing their initials in the "New Employee" textfield.
    If the selected Position already has an Employee, it is not changed.
  • Changing the horizontal location of a Position, by dragging the Position to empty space.

Much of the framework of the program has been written for you, including most of the user interface, the doMouse method, much of the Position class, the entire Employee class, and the code for repositioning a tree node. There is also a method to make a new tree to let you test your program. You should carefully read the Position and Employee classes, and the setupGUI and doMouse methods.

The user interface for an editor like this is not trivial. Here are two tables showing how the program should respond to mouse actions and to the textfields.

Mouse PressedMouse ReleasedActionConditions
on "new" icon on a target Position create a new Position and add it to target's team none
on a Position same Position select Position none
on empty space move Pos (to the empty space) none
on a Position but not its Employee another target Position add Position to target's team cannot move to within its own subtree
on retirement icon remove Position from tree Position must be vacant and have no team
on an Employee
Emp in a
Position
another target Position move Emp to the target target must be vacant
on retirement icon remove Emp making Position vacant

Textfield updatedActionConditions
Role Change the role of the selected Position A Position must be selected
Initials Create new Employee and fill the vacant selected Position A Position must be selected and must be vacant

What's missing is most of the methods for actually manipulating the tree - you need to complete them.

Here is an example hierarchy that the program could display. It is the test tree, with the VP3 position moved to be under SEP, and the employee BV has retired leaving the position VP2 vacant. The position AS has been selected.

OrganisationChart.png

Core

The Core involves completing the core functionality of drawing and editing the tree. You should do it in two steps. The relevant methods are listed; the documentation comments on the methods say what the methods should do.

Step 1:

Adding Positions and drawing the tree.
  • addToTeam (Position class)
  • drawTree (OrganisationChart class)
Now you should be able to load the test tree!

Step 2: adding, moving and removing positions and employees.

  • removeFromTeam (Position class)
  • findPosition (OrganisationChart class)
  • addNewPosition (OrganisationChart class)
  • movePosition (OrganisationChart class) version a
  • removePosition (OrganisationChart class)
  • moveEmployee (OrganisationChart class)
  • retireEmployee (OrganisationChart class)

Completion:

The Completion adds an important check on moving employees around: employees should not be moved into their own subtree!
  • inSubtree (OrganisationChart class)
  • movePosition (OrganisationChart class) (version b)

Also, ensure that if one position is drawn on top of another, findPosition will return the top position, not the bottom one.

Challenge:

The Challenge involves extending the program in several useful ways:

  • Extend the program to save the current hierarchy to a file and to load a hierarchy from a file.
    Hint: You will need to work out a file format that will enable you to reconstruct the tree. Knowing how many positions are in a manager's team before attempting to read them is helpful.

  • The current program makes sure that all positions are drawn at the right level on the window, but makes the user do the tricky part of the layout - specifying the horizontal layout of the members of each team.
    Fix the drawTree method so that it spaces out all the positions nicely and evenly.
    Hint: work out the correct offsets of all the positions, by doing a post-order depth-first traversal of the tree, passing back the total width of each subtree.

  • Animate the dragging so that the user can see what they are doing.

Part 2: CPN Calculator (Weight: 1/2)

The lectures demonstrated a program for a simple calculator that would read and evaluate expressions converted into a binary tree, where each operator (+, -, *, /) had exactly two operands.

For this program, you are to complete a more complex calculator that has a wider range of operators, and also allows some of the operators to have more than two operands (the values that the operator is applied to). It uses "Cambridge Polish Notation" which means that it puts the operator before the operands and puts round brackets around every operator and its operands. For example, 6+3+5 is written ( + 6 3 5 ).

Expressions can be nested; for example, the expression ( * ( + 4 8 3 7 2 ) 7 ( / 20 2 5 ) 18 ) is a multiplication operator applied to four operands; the first operand is the sum of 4, 8, 3, 7 and 2; the second operand is 7; the third operand is 20 divided by 2 then divided by 5, and the fourth operand is 18. The value of ( * ( + 4 8 3 7 2 ) 7 ( / 20 2 5 ) 18 ), should be 6048 (which is 24 * 7 * 2 * 18).

The operators that the calculator should know about are:
  • +, which adds up all its operands.
  • -, which subtracts from the first operand all the remaining operands.
  • *, which multiplies all its operands.
  • /, which divides the first operand by all the remaining operands.
  • ^, which has two arguments, and computes the first to the power of the second. eg, ( ^ 2 3 ) would compute 2 to the power of 3, which is 8.
  • sqrt, which computes the square root of its (one) operand
  • log and ln, which compute the log to base 10 and the natural log (base e) of the operand. If log has two operands, it computes the log of the first operand to base of the second operand.
  • sin, cos, and tan, which compute the standard trigonometric functions.
  • dist, which either has four operands (x1, y1, x2, y2) and computes the euclidean distance between the points (x1,y1) and (x2,y2), or it has six operands (x1, y1, z1, x2, y2, z2) and computes the euclidean distance between the points (x1,y1,z1) and (x2,y2,z2)
  • avg, which computes the average of all its arguments (any number of them, but at least one).

The calculator should also know about two constants:
  • PI, which has the value Math.PI (3.14159...)
  • E, which has the value Math.E (2.71828..., the base of natural logarithms)

Some of the calculator program is written for you:
  • The GUI set up,
  • The top level REPL structure (a Read Evaluate, Print Loop that reads an expression, evaluates it, and prints it out).
  • A method that reads an expression from the user and turns it into a general tree where the leaves have numbers (or constants), and the internal nodes have an operator and a list of child nodes that the operator is applied to.

You have to complete the evaluate method which evaluates an expression tree.

Core:

Make the calculator work on expressions with the operators +, -, *, and /, and the constants PI and E.

You should test your code on a range of epressions. You can also run some automated tests by using Set input in the menu to get input from the test-core.txt file. This will enter 7 expressions for you (though you will need to enter a first expression manually). The expected output is given at the end of the assignment.

Completion

Extend your evaluate method:
  • Handle the other operators above. You will find methods in the Math class to be useful.
  • Check for unknown operators - if an expression has an invalid operator, evaluate should report the error (eg, The operator $ is invalid) and return the special double value Double.NaN.
  • Check that an operator has a valid number of operands, report any errors, and return Double.NaN
    • The arithmetic operators and avg allow any number of operands above 0. eg ( + 5 ) is OK and means just 5;
    • dist allows four or six operands
    • log allows one or two operands
    • The other operators have a fixed number of arguments.

You can use the test.txt file. This will enter 19 expressions for you (though you will need to enter a first expression manually). The expected output is given at the end of the assignment.

Challenge

Extend readExpr:
  • Check for empty brackets (ie ( ) ). Report the error and return the null tree.
  • Check for an invalid expression that has brackets that don't match,

  • Add a printExpr method that will print the expression using normal infix for +, -, *, and /^, using brackets only when necessary, and using normal brackets notation for the other functions. For example
    • ( + 7 6 ( * 5 4 ) ( * 3 2 1 ) ( ^ 2 5 ) ) prints as 7+6+5*4+3*2*1+2^5
    • ( * 7 6 ( + 5 4 ) ( + 3 ( 2 5 ) 1 ) ) prints as 7*6*(5+4)*(3+2^5+1)
    • ( + 3 ( sin ( + 4 ( * 5 PI ) ) ) ( ln 6 ) ) prints as 3+sin(4+5*PI)+ln(6)



Sample output for CPNCalculator on the test-core.txt file:

Make sure the output of your program exactly matches the given text.

expr: 20
 -> 20.0

expr: ( + 7 6 ( * 5 4 ) ( * 3 2 1 ) )  
 -> 39.0

expr: ( * 7 6 ( + 5 4 ) ( + 3 2 1 ) )
 -> 2268.0

expr: ( - ( * 2 4 ) ( / 2 4 ) )
 -> 7.5

expr: ( - 24 2 3 4 )
 -> 15.0

expr: ( / 24 2 3 4 )
 -> 1.0

expr: ( * 2 PI 10 )
 -> 62.83185307179586

Sample output for CPNCalculator on the test.txt file:

Make sure the output of your program exactly matches the given text.

expr: ( + 50 ( log ( * 125 8 ) ) )
 -> 53.0

expr: ( ^ 2.718282 ( ln 20 ) )
 -> 20.00000378099725

expr: ( ^ ( ^ 2 5 ) 2 )
 -> 1024.0

expr: ( ^ 10 ( log 38 ) )
 -> 37.99999999999999

expr: ( + ( sin ( / 3.14159 3 2 ) ) ( cos ( / 3.14159 3 ) ) ( tan ( / 3.14159 4 ) ) )
 -> 1.9999990562184347

expr: ( dist 0 0 3 4 )
 -> 5.0

expr: ( dist 0 0 0 3 4 12 )
 -> 13.0

expr: ( avg 1 2 3 4 5 6 7 8 9 10  )
 -> 5.5

expr: ( +  3 ( sin ( / PI 6 ) )  ( log ( * 125 8 ) ) )
 -> 6.5

expr: ( ^ E ( ln 20 ) )
 -> 19.999999999999993

expr: ( + ( sin ( / PI 3 2 ) ) ( cos ( / PI 3 ) ) ( tan ( / PI 4 ) ) )
 -> 2.0

expr: ( log 64 4 )
 -> 3.0

expr: ( The remaining examples should all be errors )
The is not a valid operator.
 -> NaN

expr: ( + 1 2 3 4 
Missing closing bracket
 -> NaN

expr: ( log 64 2 2 ) 
Too many operands for log
 -> NaN

expr: ( dist 1 2 3 )
Wrong operands for dist
 -> NaN

expr: ( dist 1 2 3 4 5 )
Wrong operands for dist
 -> NaN

expr: ( dist 1 2 3 4 5 6 7 )
Wrong operands for dist
 -> NaN

expr: ( power 5 7 )
power is not a valid operator.
 -> NaN