CENG242 -pe7 -Solved

Programming Languages

1             Problem Definition
In this exam, you are going to construct some n-ary trees and handle some operations on them.

1.    The problem starts with the construction of the trees. For this, you are given some <parent-child> relationships in an unordered way, and you are expected to construct the corresponding tree(s) properly. For example:

addRelation(18, 35)
The parent-child sequence given on the left
addRelation(20, 17) addRelation(10, 30)
results in 3 independent trees:
 
addRelation(10, 44)
tree-1:
20
tree-2:
65
addRelation(80, 100)
/
     |        \
 
/              \
addRelation(35, 43)
17
     19        18
 
26             10
addRelation(20, 19)
|
/ \
 
/ | \
addRelation(65, 26)
16
             35        42
 
        12            30 44
addRelation(48, 60)
 
|
 
 
addRelation(10, 12) addRelation(65, 10) addRelation(48, 70)
 
43
 
 
addRelation(20, 18)
tree-3:
____48____
 
 
addRelation(17, 16)
 
/           / \             \
 
 
addRelation(48, 80)
                                   60        70        80        90
 
addRelation(18, 42)
|
 
addRelation(48, 90)
100
 
As you see, child may be introduced before its parent in the input. It is ensured that any independent tree have unique nodes (i.e. distinct nodes from those of the other trees). Also, there will be no repetition in the input (like giving the same parent-child relationship). Moreover, ordering between the children of a node is not important.

2.    Node.cpp: Node is the most fundamental class in this task. It represents a node holding a unique id and it is actually a tree at the same time whose starting node is itself and may have some children and a parent (if it is itself a child of another tree).

 
?

|
may have parent
Node:
[ int id ]

/ / .... \ \
 
 
? ? ... ? ?
may have children
This class has some some basic methods like constructor, destructor, copy cons., operator overload, etc. Each one is explained in the header file in a detailed way.

(a) DataNode.cpp: DataNode is a derivation of Node class. The difference from Node is that it also carries a char value other than id. Except than having a char data, it has the same properties with Node class. However, the implementation of some methods of DataNode may slightly differ from those of Node. These details are given in the header.

3.    NodeManager.cpp: NodeManager is the class carrying the independent tree pieces (i.e. independent Node objects). This class also has 3 important methods other than constructor/destructor:

•    First, it provides to add new <parent-child> relationships via addRelation(int parent.id, int child.id) method. An illustration of sequential calls of this method is given above, at article 1.

•    Second, it enables to convert the type of a Node object into DataNode object via setDataToNode(char data, int node.id) method in which you need to find the related method and replace it with a new node of DataNode.

•    Third, it has getNode(int node.id) method which simply returns the corresponding node.

4.    Action.cpp: Action is an abstract base class which inherits a single method named act(const Node& node) to its derivations. How the action becomes depends on the derivated class, yet we can say that it conducts some operations on the given node and returns the output tree.

(a)     CompleteAction.cpp: CompleteAction is a derivation of abstract Action class. Its constructor saves a Node object as its member. It derives the act(const Node& node) method as follows: The node object given in the parameter and the one kept as member are compared along their children one by one and produced a new tree (Node object). It is ensured that both input trees (namely Node object) has the same structure and nodes with corresponding ids. If there is object of Node type at the corresponding positions of trees, there is nothing special to do. The output tree will have the same Node object in that case. However, there may be DataNode objects at some places in the first tree instead of some bare Node objects whereas they are simply a Node object in the second tree, or vice versa. Then, in such a case the output tree will have the DataNode object at that position. Below, act() operation of

CompleteAction class is illustrated:
 
100
[100,’G’]
___/ | \___
                            /             |
\
             20             [50,’A’] 10
             [50,’A’]                20
[10,’H’]
             / \               / \                    \
               / \                       /\
\
        3          7        1        90             [2,’C’]
90 [1,’I’] 3 7
[2,’C’]
                   / \                   |               / | \_
        |                                      / \
             /        |          \
[5,’B’] 4                            8               30 40 [9,’F’]
        8                                 4
5                 9 [40,’K’] 30
/ \
/ \
 
6 [70,’D’]
6           70
 
/ \
/ \
 
 
[60,’E’] 80
60 [80,’J’]
 
 
(tree1)
(tree2)
 
 
 
 
 
 
 
Assume that a CompleteAction object was constructed previously by calling CompleteAction(tree1). After act() method of CompleteAction class is called with the tree2 as its argument, it is expected to return tree3 below:

[100,’G’]

__/
|             \__
[50,’A’]
20                     [10,’H’]
/ \
/\                                \
90 [1,’I’]
3 7                               [2,’C’] _______
|
       / \                        /           \                     \
8

/ \

6 [70,’D’]

/ \

[60,’E’] [80,’J’]
4 [5,’B’] [9,’F’] [40,’K’] 30
(tree3)

(The ordering of the siblings is not important)

(b)    CutAction.cpp: CutAction is a derivation of abstract Action class. Its constructor saves a char value as its member, say data. It derives the act(const Node& node) method as follows: It applies some cut operation on the nodes of the argument tree that satisfy a basic rule. If a node has at least 2 char value which is same with the data at the total of its children and grandchildren, then that node is cut such that in the output tree it is replaced with a new node of type DataNode which has data as its char value and has no child. Note that cut operation should start from the leaves and proceeded towards the root (i.e. from down to up). If you do it in the reverse manner, the result may change! Below, act() operation of CutAction class is illustrated:

                                                       100                                                                                                                   100

                                               ___/ | \___                                                                                                     __/ | \_

                                     20               50               10                                                                               20             50        10

                                     / \               / \                     \                                         ===>                         / \               / \           \

                                3          7        1        90                  2                                                                  3        7        1             90 [2,’*’]

                                            / \                   |               / | \__                                                                   / \                 |

                                [5,’*’] 4                     8               30 40 [9,’*’]                                                  [5,’*’] 4 [8,’*’]

                                                                   / \                      \

6 [70,’*’] [242,’*’]

/ \

[60,’*’] [80,’*’]

                                                       (tree1)                                                                                                               (tree2)

Assume that a CutAction object was constructed previously by calling

CutAction(’*’). After act() method of CutAction class is called with

the tree1 as its argument, it is expected to return the tree2.

(The ordering of the siblings is not important)

(c) CompositeAction.cpp: CompositeAction is a derivation of abstract Action class. This action is the composition of the other actions. It allows actions to be added using the

CompositeAction* addAction(const Action* action) method (notice that this method returns a reference to the object itself, i.e., return the ”this” pointer, for syntactic purposes). Note that CompositeAction is not responsible for deleting child actions when it is destructed. You may assume that there will be at least one child action added to a CompositeAction object.

5.    Exception.h: This is implemented by the author and directly supplied to you. There is nothing that you need to implement on it. It includes an InvalidRequest exception which you may need in your implementations when any data is queried from a Node yet not DataNode object.