# ECE368 Project#3 solution

\$24.99

Original Work ?

## Description

5/5 - (1 vote)

Description This project is to be completed on your own. You will implement a program involving tree traversal(s)tocomputethepackingofrectangles,representedbyabinarytree. In this binary tree, each leaf node represents a rectangle. Each internal node of the binary tree represents a partitioning of two groups of rectangles by a horizontal cutline or a vertical cutline. LetxHy(xVy)denotea(sub)tree,whoserootnodeisahorizonalcutH (averticalcutV). Theleft and right subtrees of H (V) are x and y, respectively. Assume that xHy means x is on top of and y isbelowthehorizontalcut,andxVy meansx istotheleftandyistotherightoftheverticalcut. In the following ﬁgure, we show an example of a “packing” of three rectangles based on a given binary tree representation. Here, each subtree is enclosed by a smallest rectangular room. Assumethatthedimensions(width,height)ofthethreerectanglesx,y,andzare (3,3), (4,5),and (7,7). ThesmallestroomcontainingthesubtreeyVz isofdimensions (11,7).
H
Vx
yz (a) A binary tree (b) The corresponding packing y V z xH
The smallest room containing the subtree xH(yVz) is of dimensions (11,10). This room is partitionedintotwosmallerrooms: Thetoproomisofdimensions(11,3)anditcontainsrectangle x, whereas the bottom room is of dimensions (11,7) and it contains rectangles y and z. We place thelowerleftcornerofeachrectangletothelowerleftcornerofitsroom. Assumingthatthelowerleftcornerofthesmallestroomcontainingalltheblocksisatcoordinates (0,0),thecoordinatesoflowerleftcornersofthethreerectanglesx,y,andzarerespectively (0,7), (0,0) and (4,0). Note that even though there is space above y to accommodate x, x has to stayabovethehorizontalcutlineinthepacking,asshownintheﬁgure. Given a binary tree representation, the smallest rectangular room to enclose all rectangles and the coordinates of these rectangles in the corresponding packing can be computed in O(n) time complexityusingappropriatetree-traversalalgorithm(s).
1
Deliverables: Inthisproject,youaretodevelopyourownincludeﬁlepacking.handsourceﬁlepacking.c, whichcanbecompiledwiththefollowingcommand:
All declarations and deﬁnition of data structures and functions must reside in the include ﬁle orsourceﬁle. Theexecutable proj3 wouldbeinvokedasfollows:
proj3 input file output file
Your source code should contain the following three functions (you may also need other functions):
1. Loadbinarytreefromﬁle Theinputﬁlename(includingpath)isprovidedinthecommandline. Thebinarytreecontained intheﬁleshouldbereadin,parsed,andstoredinthetreedatastructuresdeﬁnedbyyou. Theinput ﬁle is divided into two sections. The ﬁrst section contains information that should help you to constructyourbinarytree: • Number of blocks (int),whichspeciﬁesthenumberofrectangles. • Number of nodes (int),whichspeciﬁesthenumberofnodesinthebinarytree. Thesecondsectionspeciﬁesthetopologyofthebinarytree. Everylinecontainssevenﬁelds: • thisnode (integer),whichspeciﬁesthenodenumberofcurrentnode. • parnode (integer), which speciﬁes the node number of the parent of current node. A node numberof“-1”indicatestheabsenceofaparentnode,i.e.,thecurrentnodeistherootnode ofthetree. • lcnode (integer),whichspeciﬁesthenodenumberoftheleftchildnode. Anodenumberof “-1”indicatestheabsenceofaleftchildnode. • rcnode (integer), which speciﬁes the node number of the right child node. A node number of“-1”indicatestheabsenceofarightchildnode. • cutline (char), which speciﬁes the orientation of the cutline. For a leaf node, the cutline orientation is speciﬁed with ‘-’. For an internal node, we use ‘H’ to denote a horizontal cutlineand‘V’todenoteaverticalcutline. • width (double), the width of the rectangle if the node is a leaf node. We use ‘-’ for an internalnode.
2
• height (double), the height of the rectangle if the node is a leaf node. We use ‘-’ for an internalnode.
Notethatthelistofnodesstartswithallthesink(leaf)nodes. 2. Performpacking Perform packing on the binary tree you have loaded in, using data type double for your computationofcoordinates. Attheendoftheanalysis,theprogramshouldreportthefollowing:
Preorder:
Inorder:
Postorder:
Width: Height:
X-coordinate: Y-coordinate:
Elapsed time:
Here, Preorder, Inorder, and Postorder should print the node numbers as the tree is traversedinpreorder,inorder,andpostorderfashion. Theelapsedtimereferstotheusertimeusedby the packing function (see project 1). Please do not include the time it takes to load and save. For Width and Height, you should report the width and height of the smallest room that encloses the packing speciﬁed by the binary tree. For X-coordinate and Y-coordinate, you should report thecoordinatesoftherectanglewiththelargestnodenumber. Notethatyoudonotreallypacktherectanglestightly,asshowninFigure(b). 3. Savepackingtoﬁle The output ﬁlename (including path) is provided in the command line. The ﬁrst line should specifythenumberofrectangles. • Number of blocks (int),whichspeciﬁesthenumberofrectangles. Subsequently, the ﬁle should contain a line for each rectangle, starting from the lowest indexed rectanlge: Everylinecontainsﬁveﬁelds: • thisnode (integer),whichspeciﬁesthenodenumberofcurrentnode. • width (double),thewidthoftherectangle. • height (double),theheightoftherectangle. 3
• xcoord (double),thex-coordinateoftherectangle. • ycoord (double),they-coordinateoftherectangle.
Considerthefollowinginputﬁle:
8 15 1 14 -1 -1 – 2 4 2 13 -1 -1 – 1 3 3 10 -1 -1 – 3 3 4 9 -1 -1 – 3 5 5 13 -1 -1 – 3 2 6 11 -1 -1 – 5 3 7 9 -1 -1 – 1 2 8 12 -1 -1 – 2 4 9 10 7 4 V – 10 11 3 9 H – 11 12 10 6 V – 12 15 11 8 V – 13 14 2 5 V – 14 15 13 1 H – 15 -1 14 12 H –
Thefollowingﬁgureshowsthecorrespondingbinarytreeandpacking. Thenumbersinparentheses besides each internal node denote the width and height of the smallest room enclosing the rectangles in the subtrees of this node. Therefore, the width and the height of the smallest room enclosingallrectanglesare11and15. Thecoordinatesofthelargestindexednodeare (9,0).
9(4,5)
10(4,8)
12(11,8)
11(9,8)
13(4,3)
14(4,7)
15(11,15)
Theoutputﬁleshouldhavethefollowingformat:
4
8 1 2.000000e+00 4.000000e+00 0.000000e+00 8.000000e+00 2 1.000000e+00 3.000000e+00 0.000000e+00 1.200000e+01 3 3.000000e+00 3.000000e+00 0.000000e+00 5.000000e+00 4 3.000000e+00 5.000000e+00 1.000000e+00 0.000000e+00 5 3.000000e+00 2.000000e+00 1.000000e+00 1.200000e+01 6 5.000000e+00 3.000000e+00 4.000000e+00 0.000000e+00 7 1.000000e+00 2.000000e+00 0.000000e+00 0.000000e+00 8 2.000000e+00 4.000000e+00 9.000000e+00 0.000000e+00
Thescreendumpshouldshowthefollowing:
Preorder: 15 14 13 2 5 1 12 11 10 3 9 7 4 6 8
Inorder: 2 13 5 14 1 15 3 10 7 9 4 11 6 12 8
Postorder: 2 5 13 1 14 3 7 4 9 10 6 11 8 12 15
Width: 1.100000e+01 Height: 1.500000e+01
X-coordinate: 9.000000e+00 Y-coordinate: 0.000000e+00
Elapsed Time: 0.000000e+00
Grading: The project requires the submission (through Blackboard) of the C-code (source and include ﬁles) and a report detailing the results. There should a table listing the run-times, and the outputs of the packing (width, height, and x- and y-coordinates of the largest indexed rectangles) obtained from running your code on some sample input ﬁles. In your report, also comment on the run-time and space complexity of your algorithm. Your report should not be longer than 1 page and should beinplaintextformatorpdf. Gettingstarted: We provide sample input ﬁles for you to evaluate the run-times of your packing program. We also provide the sample output and the screen output for the 8-rectangle example: r6.pck and r6.log, respectively. The input of this example is r6 flr.txt. Copy over the ﬁles from the Blackboardwebsite. CheckouttheBlackboardwebsiteforanyupdatestotheseinstructions. Start packing!