Description
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 figure, 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,asshowninthefigure. 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,youaretodevelopyourownincludefilepacking.handsourcefilepacking.c, whichcanbecompiledwiththefollowingcommand:
gcc -Werror -Wbad-function-cast -Wall -Wshadow -O3 packing.c -o proj3
All declarations and definition of data structures and functions must reside in the include file orsourcefile. Theexecutable proj3 wouldbeinvokedasfollows:
proj3 input file output file
Theexecutableloadsthebinarytreefrom input file,performspacking,andsavesthepackinginto output file.
Your source code should contain the following three functions (you may also need other functions):
1. Loadbinarytreefromfile Theinputfilename(includingpath)isprovidedinthecommandline. Thebinarytreecontained inthefileshouldbereadin,parsed,andstoredinthetreedatastructuresdefinedbyyou. Theinput file is divided into two sections. The first section contains information that should help you to constructyourbinarytree: • Number of blocks (int),whichspecifiesthenumberofrectangles. • Number of nodes (int),whichspecifiesthenumberofnodesinthebinarytree. Thesecondsectionspecifiesthetopologyofthebinarytree. Everylinecontainssevenfields: • thisnode (integer),whichspecifiesthenodenumberofcurrentnode. • parnode (integer), which specifies the node number of the parent of current node. A node numberof“-1”indicatestheabsenceofaparentnode,i.e.,thecurrentnodeistherootnode ofthetree. • lcnode (integer),whichspecifiesthenodenumberoftheleftchildnode. Anodenumberof “-1”indicatestheabsenceofaleftchildnode. • rcnode (integer), which specifies the node number of the right child node. A node number of“-1”indicatestheabsenceofarightchildnode. • cutline (char), which specifies the orientation of the cutline. For a leaf node, the cutline orientation is specified 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 specified by the binary tree. For X-coordinate and Y-coordinate, you should report thecoordinatesoftherectanglewiththelargestnodenumber. Notethatyoudonotreallypacktherectanglestightly,asshowninFigure(b). 3. Savepackingtofile The output filename (including path) is provided in the command line. The first line should specifythenumberofrectangles. • Number of blocks (int),whichspecifiesthenumberofrectangles. Subsequently, the file should contain a line for each rectangle, starting from the lowest indexed rectanlge: Everylinecontainsfivefields: • thisnode (integer),whichspecifiesthenodenumberofcurrentnode. • width (double),thewidthoftherectangle. • height (double),theheightoftherectangle. 3
• xcoord (double),thex-coordinateoftherectangle. • ycoord (double),they-coordinateoftherectangle.
Considerthefollowinginputfile:
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 –
Thefollowingfigureshowsthecorrespondingbinarytreeandpacking. 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)
Theoutputfileshouldhavethefollowingformat:
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 files) 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 files. 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 files 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 files from the Blackboardwebsite. CheckouttheBlackboardwebsiteforanyupdatestotheseinstructions. Start packing!