辅导CMPT 129程序、讲解C/C++编程、辅导c++程序 辅导Web开发|辅导Python编程
- 首页 >> Python编程 CMPT 129 Assignment #3
Assignment is worth a total of 100 marks (Groups of up to 3 students)
Description of the attributes and and methods for the provided class: Rectangle
Your are given a class named Rectangle that can be used to build rectangle objects that you can display
graphically. Your rectangle class is defined in the provided files Rectangle.h and Rectangle.cpp.
DO NOT CHANGE any code you are given in these two files. You will add code to each file but you should
not change any existing code.
The class rectangle should have the following attributes:
Width: An int that holds the width of a rectangle (in pixels). The width measured as number of pixels
along the horizontal edge of the Rectangle.
Height: An int that holds the height of a rectangle (in pixels). The height measured as a number of
pixels along the vertical edge of the Rectangle.
xLocation: An int that holds the x coordinate (in pixels) of the upper left hand corner of the
Rectangle. The left hand edge of the page is xLocation = 0
yLocation: An int that holds the y coordinate (in pixels) of the upper left hand corner of the
Rectangle. The upper edge of the page is yLocation = 0
rectanglesCreated: An int that counts how many Rectangles have been created in the application
rectanglesExisting: An int that counts how many Rectangles are presently in existence in the
application (does not include Rectangles that have been destroyed)
blockColour: An object of type Colour (the Colour class is provided for you). This object holds
the colour that the plotted Rectangle will have. A colour is described by four integers, each between
1 and 255 inclusive. The first three numbers indicate the amount of red, green, and blue in
the colour respectively. The fourth number indicates the intensity of the colour (255 is darkest / most
saturated).
The class Rectangle should have the following methods:
Rectangle();
The default constructor
1. sets private members width and height to 10
2. sets members xLocation and yLocation to 10
3. increments counters, rectanglesCreated and rectanglesExisting
4. sets blockColour to black (0, 0, 0, 255)
Rectangle( int xLocationValue, int yLocationValue, int widthValue, int heightValue,
Colour blockColourValue);
Constructor that
1. Initializes width, height, xLocation, yLocation and blockColour to the provided values of the
corresponding actual arguments in the constructor call.
2. Increments both counters, rectanglesCreated and rectanglesExisting.
3. Checks to assure the rectangle is on the page
Rectangle( int xLocationValue, int yLocationValue, Colour blockColourValue);
Constructor that:
1. Initializes width, height and blockColour to the provided values of the corresponding actual
arguments in the constructor call.
2. Sets width and height to 10
3. Increments both counters, rectanglesCreated and rectanglesExisting.
4. Checks to assure the rectangle is on the page
Rectangle(const Rectangle& toBeCopied)
Copy constructor that makes a copy of the Rectangle toBeCopied and increments both counters,
rectanglesCreated and rectanglesExisting.
~Rectangle()
Destructor that destroys an object and decrements the counter rectanglesExisting.
int GetHeight() const;
int GetWidth() const;
int GetXLocation() const;
int GetYLocation() const;
Colour GetBlockColour() const;
static int GetRectanglesCreated();
static int GetRectanglesExisting();
Accessor functions to access each of the private members (to get the values of the private variables
from outside the class). The accessor functions use the const keyword to assure they cannot change
any values of the attributes of the objects. Static member functions are used to access static
members (the counters) so their values can be accessed before you create any rectangles.
An overloaded print function which prints the values of each private member in the Rectangle Class.
The output of the print function should look like
Width 50
Height 30
xLocation 240
yLocation 580
rectanglesCreated 6
rectanglesExisting 6
blockColour red 0 green 0 blue 0 alpha 255
The output should be aligned as shown. Each of the attribute names is printed left justified in a field
20 characters wide, each number left justified in a field 9 characters wide. The colour is printed using
the extraction operator (<<) in the class Colour. The numbers are of course only for illustration and
will be replaced with the actual values of the attributes for the particular object of the class being
printed.
void SetRectangleColour(const Colour blockColorValue);
void SetWidth(const int widthValue);
void SetHeight(const int heightValue);
void SetXLocation(const int xLocationValue);
void SetYLocation(const int yLocationValue);
static void SetRectanglesCreated(int numberCreated);
static void SetRectanglesExisting(int numberExisting);
Mutator functions to set each of the private members (to set the values of each of the private
variables from outside the class). When an attribute value is changed the methods make sure the
change does not cause the upper left corner to be off the page or allow part of the rectangle to
extend off the right hand side of the page or the bottom of the page.
const Rectangle& operator = (const Rectangle& Rectangle2);
bool operator==(const Rectangle& Rectangle2) const;
friend ostream& operator << (ostream& os,
const Rectangle& myRectangle);
overloaded operators, =, = = and <<
1. The << operator should produce the same output as the print function
2. The assignment operator should copy all values of variables.
3. The comparison operator (= =) should make sure that the values of all variable members of the
classes are identical. If any one variable member is not the same in both objects being compared
the objects are not equal.
Part 1 Write additional methods for a class Rectangle: (20 points)
You will be provided with a basic Rectangle Class. Both the Rectangle.h and Rectangle.cpp files are
provided. You will be asked to add two methods to the Rectangle.h and Rectangle.cpp files. Do not
change any of the existing code in Rectangle.h or Rectangle.cpp just add the prototype and
implantations of the two methods. The methods have the following prototypes
bool DoesOverlay(const Rectangle& rectangle2);
bool DoesIntersect(const Rectangle& rectangle2);
Boolean member function DoesOverlay which operates on two rectangles and returns TRUE if the
rectangle RX used to call the member function (RX.DoesOverlay(RY)) is inside the rectangle RY
passed to the member function DoesOverlay through the argument of the function. As an example
the black rectangle in the image below overlays the grey rectangle and the black rectangle overlays
the blue rectangle.
Boolean member function DoesIntersect which operates on two rectangles and returns TRUE if the
rectangles intersect. Two Rectangles intersect if they have ANY pixels in common. As an example
the grey rectangle in the image below intersects the red rectangle and the grey rectangle also
intersects the black rectangle. A rectangle that overlays another rectangle must intersect with that
rectangle.
You will also be provided with a test code, RectangleTest.cpp, that you can use to test your two functions.
The test code will produce the plots below. The parameters of the rectangles illustrated are given in the
tables beside the figures. In the second table the green numbers give the dimensions of the plotted
rectangles after they have been corrected by the constructor or mutator functions to be completely on
the page.
The following corrections are made when a rectangle is partially or completely off the page. These
corrections are made in the order they appear in the list below.
If xLocation or yLocation is off the page both xLocation and yLocation are set to 0
If the rectangle is too wide to completely fit on the page then the width of the rectangle is
truncated so it goes to the right edge of the page and then stops.
If the rectangle is too high to completely fit on the page then the height of the rectangle is
truncated so the rectangle does not extend beyond the bottom of the page.
After these corrections are made the rectangle is printed and / or displayed to the plot. A rectangle is
printed using the Print() method or the overloaded << operator.
The sample test code will be a model for the test program you will need to write to test your class
DiskStack in the next part of this assignment.
colour xLocation yLocation width height
R1 Dark
Blue
225 520 120 100
R2 Black 240 580 50 30
R3 Red 150 300 375 250
R4 Grey 90 400 210 300
R5 Light
blue
195 640 230 110
Colour xLocation yLocation width
R10 Red 610 / 0 810 / 0 200 350
R11 Black 100 / 0 -5 / 0 150 250
R12 Dark Blue -5 / 0 100 / 0 100 125
R13 Purple 550 50 100 / 50 300
R14 Light blue 195 740 230 510 / 60
R15 Grey 400 600 210 / 200 300 / 200
Part 2 (50 Marks) Write a class DiskStack:
Write a C++ class DiskStack using the class Rectangle above. All locations of Rectangles on the page and
sizes of Rectangles are given as integer numbers of pixels. The locations of the corners of a page are
labeled on the diagram below.
Use global variables pageWidth and pageHeight to indicate the horizontal and vertical size of
the page to be plotted. The values in pixels are
o pageWidth =600
o pageHeight=800.
Class DiskStack builds a Stack as illustrated in the diagram above. Class DiskStack has private members
(attributes) listed and explained below. The first six private members are integers. The last two are
pointers to dynamic arrays.
The class DiskStack has the attributes:
StackHeight gives the height (y extent in pixels) of the entire Stack (see diagram above).
(xStackLocation, yStackLocation) defines the location of the bottom left hand corner of the
Rectangle at the bottom of the Stack
StacksExisting counts the number of Stacks presently in existence. This member should have the
same value for all Stacks presently in existence. This number should be incremented every time a
DiskStack is created, and decremented whenever a DiskStack is destroyed.
StacksCreated counts the number of DiskStacks that have been created by the program. This number
should be incremented every time a DiskStack is created.
(0,0)
A
StackHeight
(pageWidth, 0)
(pageWidth, pageHeight)
[0]
[1]
[2]
[3]
(0,pageHeight)
(xStackLocation, yStackLocation),
rectangleWidthArrayp is a pointer to a 1-D array of integers. After the array is dynamically created
in the constructor or mutator methods, the integer in location of 0 of the rectangleWidthArrayp
array will be the width, in pixels, of the bottom Rectangle in the DiskStack. The integer in
rectangleWidthArrayp[k] will be the width, in pixels, of the kth Rectangle in the stack. The width of
rectangle k must be smaller than the width of rectangle k-1
rectangleArrayp, is a pointer to a 1-D array of Rectangles. After the array is dynamically allocated in
the constructor or mutator methods it will be modified to contain each Rectangle in the Stack. The
first Rectangle in the rectangleArrayp will be the bottom Rectangle in the Stack. The last Rectangle
in rectangleArrayp will be the Rectangle at the top of the Stack. All Rectangles in the Stack have the
same height.
The kth rectangle will be stored in rectangleArrayp[k] and the length of the kth Rectangle will be
stored in rectangleWidthArrayp[k].
Your class DiskStack class must include methods
DiskStack();
The default constructor
1. Sets private member numInStack and stackHeight to 0
2. Sets private members xStackLocation and yStackLocation to 0
3. Sets private members rectangleWidthArrayp and rectangleArrayp to nullptr (or NULL)
4. increments static counters, stacksCreated and stacksExisting
DiskStack( int numInStackValue, int stackHeightValue,
int xStackLocationValue, int yStackLocationValue, int *rectangleWidthArraypValue)
Constructor that
1. Sets the pointer attributes rectangleWIdthArrayp and rectangleArrayp to null
2. Checks that the pointer to the array rectangleWidthArraypValue passed to the function is
not NULL. If it is NULL the widths in the array will be calculated in step 5.
3. Initializes numInStack, stackHeight, xStackLocation, and yStackLocation, to the provided
values of the corresponding actual arguments in the constructor call.
Then if necessary corrects them to create an internally consistent stack that is completely on
the page.
The limits on the values of the attributes are given below. The actions to be taken if the
values the attributes the method DiskStack receives are not within those limits, are also
listed below. The purpose of the limits below are to assure the stack is completely on the
page and that the rectangles in the stack are at least ten pixels high and 20 pixels wide. The
checks should be done in the order they are given in this list,
a. If the value of stackHeightValue is not in the range
0 < stackHeightValue < pageLength Then stackHeight = pageLength
If stackHeightValue <= 0 then it is set to 0
b. If the value of numInStackValue is in the range
numInStack > 25 Then numInStack = 25
numInStack < 0 Then numInStack = 0 and stackHeight=0
c. If the value of yStackLocationValue is not in the range
pageLength > yStackLocation >= stackHeight-1
Then set yStackLocation = MAX( stackHeight – 1, 0)
d. If the value of xStackLocationValue is not in the range
1 <= xStackLocationValue < pageWidth/2
Set xStackLocation = pageWidth/2
4. Allocates dynamic memory. If stackHeight > 0
a. Allocates enough space for numInStack rectangles and places the pointer to the new
memory in the attribute rectangleArrayp.
b. Allocates enough space for numInStack integers. Each of these integers will later
represent the width of one of the rectangles. The pointer to the new memory will be
placed in the attribute rectangleWidthArrayp.
5. If the pointer rectangleWidthArraypValue that was supplied for the method was null then
calculate the widths of each rectangle in the stack and place those widths in
rectangleWidthArrayp. The width of the bottommost Rectangle will be 598 (from 1 to 598).
The width of Rectangle k in the stack will be
((numInStack-k)*pageWidth)/numInStack )-2
6. If the pointer rectangleWidthArraypValue is not null then the constructor
a. copies (deep copy) the values of rectangle Length from the array
rectangleWidthArraypValue to the memory pointed to by the pointer attribute
rectangleWidthArrayp.
b. As each element of the array is copied the constructor checks each length to assure
the length is valid.
For the each Rectangle in the stack. If xLocation + rectangleWidthArrayp[k] >=
pageWidth (where xLocation is the calculated x Coordinate for the Rectangle to be
constructed) then reset rectangleWidthArray[k] = pageWidth – xLocation
c. Builds each rectangle starting with the rectangle at the bottom of the stack and
ending with the rectangle at the top of the stack. Put the bottommost rectangle in
the stack in location 0 of the RectangleArrayp array and the nth rectangle in the stack
(going up) in the nth location of the array.
A Copy constructor that makes a copy of the DiskStack with the identifier toBeCopied and
increments both counters, stacksCreated and stacksExisting. Remember you must make a deep
copy of the arrays not just copy the pointers.
A destructor that deletes dynamic memory and decrements stackCreated.
Accessor functions GetStacksExisting and GetStacksCreated ONLY
Mutator functions SetStacksExisting, SetStacksCreated, SetStackHeight, and SetStack ONLY
The mutator SetStack should have the following prototype
void SetStack(int numInStackValue, int StackHeightValue, int xStackLocationValue,
int yStackLocationValue, int *StackWidthArraypValue);
This method will take the provided inputs and set the attributes of the existing DiskStack checking
each for range and consistency. All tests are the same as those used in the second constructor and
should be applied in the same order. The function will then construct the array of Rectangles.
Overloaded operators = and << with prototypes
DiskStack& DiskStack::operator = (const DiskStack &secondDiskStack)
ostream& operator << (ostream& os, const DiskStack& myDiskStack)
The values printed in the sample consoleOut files in the sample output folder for assignment 3 will
give you a pattern to match (character for character) when you print a DiskStack using the <<
operator. Note that the << for Rectangle is used to print each rectangle in the stack.
A display function to plot the Rectangle Stack to the bitmap. This display function should use the
display function for the class Rectangle so that no direct assignment of bits in the bitmap is
necessary. You already know how to display a Rectangle, so display each Rectangle in the
RectangleArrayp array. The prototype of the display function should be
void DiskStackDisplay(BMP& myImageValue, string outFIleValue);
Part 3 (20 Marks) Integration of the supplied Peg class and Rectangle class
and your Rectangle Stack into the towers of Hanoi solution:
Refer to the posted video for a description of the problem and a recursive solution to the towers of
Hanoi problem. You may begin with the solution discussed in the video. You will also use the provided
Peg class, Rectangle class, and the DiskStack class you have already developed. You will need to modify
the towers of Hanoi solution to be consistent with the following prototype
void Towers( int numDisks, Peg& presentPeg, Peg& toPeg, Peg& tempPeg, int displayedStep, BMP
myImage, string imageFileName);
Your new tower function will not only print out the step by step solution to the towers of Hanoi
problem for numDisks disks (as the solution in the video and notes already does), it will also display a
plot of the disks on each peg for one selected step in the solution (see example to the left). To indicate
the particular step to be displayed the parameter displayedStep has been added to the prototype of
the function. displayStep is the number of times a disk has been moved before the displayed step is
reached.
.
In order to be able to plot the disks on each peg (the cross section of each disk on a Peg is a Rectangle
in a Diskstack) we must keep track of which disk is on which peg at all times during the solution of the
towers of Hanoi problem. The Peg class will help us do this. A Peg is a stack of integers. The integers
that are placed on a Peg’s stack represent the diameters of the disks that are presently on the peg.
The integer on the top of the stack is the diameter of the disk of the top of the stack of disks on the
peg. The integer on the bottom of the stack is the diameter of the disk on the bottom of the stack of
disks on the peg. You can remove a disk from a Peg by taking an integer off the top of that Peg’s stack.
To do this (remove the disk from the Peg) use the pop method of the class Peg. The value of the
expression presentPeg.pop() is the value of the integer you removed from the top of the stack of
integers on presentPeg.. You can place a disk on a Peg by placing an integer representing the diameter
of that disk on the stack for that Peg. To do this (add a dis to a Peg) use the push method of the class
Peg. To put the integer diameter1 onto the stack for toPekg you would call the push method as
follows: toPeg.push(diameter1); Therefore, to keep track of what disks are on each peg during the
solution of the towers of Hanoi problem you need to move a disk each time you print out the move in
your towers function. Remember that you need to put all the disks on the fromPeg before the towers
function is called.
The supplied Peg class also allows you to access the numbers in the stack using array index notation
(the index operator [] ). You can determine how many integers are on the Peg by calling the Peg
member function size(), toPeg.size() will have a integer value equal to the number of disks on the
toPeg. Once you know how many disks are on the peg you can access all the integers on the stack (to
move them into an array ready to use in the constructor of a DiskStack as the rectangleWidthArrayp.
To access the ith integer in the stack of the toPeg use the expression toPeg.myPeg[i]. For the integer
on the top of the stack i=size-1, for the integer on the bottom of the stack i=0.
Next you will have to write a DisplayStep function that will display the disks on each of the three pegs
at step displayedStep. There is an example of one such displayed step below. This function should be
called from your towers function,. Be sure that you can plot both the initial state before the first move
(move 0) and the final move (the final state all disks on the toPeg) Also be sure that asking for a move
after the end or before the beginning of the towers solution to be plotted results in an appropriate
error message. Note the labels indicating which peg is which are not part of the expected plotted
output. Each time a DiskStack for the selected step is plotted using the display function it should also
be printed to the console using the << operator. The prototype of this function will be
void displayStep(Peg& fromPeg, Peg& toPeg, Peg& extraPeg, BMP myImage, string imageFileName);
Your display function should produce a plot like the one above and output that matches the supplied
output file character for character.
All disks (Rectangles) plotted should have the same thickness (ydimension)
The thickness of the disks may differ from one plot to another (to accommodate stacks of a
larger number of disks)
The width (dimension in x direction) of the largest disk plotted should be less than the width
of the page
The width of successive disks in the stack should decrease uniformly
You should print error messages and not plot your Rectangle if any part of your Rectangles
will not be contained on the page.
The image of any peg should never fill more than 1/3 of the page
The order of the pegs should be as shown in the diagram above
REMEMBER: You have a member function of class Rectangle, to plot each rectangle, your displayStep
should use this function to plot each rectangle in the stack.
Main program (PARTIALLY SUPPLIED, add code, 10 points)
Your main program should: be in file Hanoi.cpp
Declare and initialize all required local variables including a BMP and three Pegs,
Peg 2
Peg 1
Peg 3
Ask the user for the number of disks in the original stack on the from Peg. The number of disks
should be 0< numDisks < 25.
If the supplied value is not in range re-prompt. There is no maximum number of re-prompts.
Ask to user for the number of the step to be plotted. The step shown should be in the range
0 < stepShown < 2numDisks
If the supplied value is not in range re-prompt. There is no maximum number of re-prompts.
Push the Widths of the rectangles in the original stack onto peg 1. For the ith peg the width of the
rectangle should be
(((numDisks-i)*pageWidth)/numDisks )-2
Prompt for and read the filename for the file that will be used to hold the bitmap plot. The file
should have the extension bmp,
Call the towers function to print the towers solution and plot the requested step
SUBMITTING YOUR RESULTS
Please note that your classes may be tested with additional main programs to assure that all methods
in your classes are working properly. You should submit the following files
Rectangle.cpp
DiskStack.cpp
DiskStack.h
Hanoi.cpp (this file should include your main program and your modified towers function and your
displayStep function)
You are not required to submit an algorithm or test plan.
Assignment is worth a total of 100 marks (Groups of up to 3 students)
Description of the attributes and and methods for the provided class: Rectangle
Your are given a class named Rectangle that can be used to build rectangle objects that you can display
graphically. Your rectangle class is defined in the provided files Rectangle.h and Rectangle.cpp.
DO NOT CHANGE any code you are given in these two files. You will add code to each file but you should
not change any existing code.
The class rectangle should have the following attributes:
Width: An int that holds the width of a rectangle (in pixels). The width measured as number of pixels
along the horizontal edge of the Rectangle.
Height: An int that holds the height of a rectangle (in pixels). The height measured as a number of
pixels along the vertical edge of the Rectangle.
xLocation: An int that holds the x coordinate (in pixels) of the upper left hand corner of the
Rectangle. The left hand edge of the page is xLocation = 0
yLocation: An int that holds the y coordinate (in pixels) of the upper left hand corner of the
Rectangle. The upper edge of the page is yLocation = 0
rectanglesCreated: An int that counts how many Rectangles have been created in the application
rectanglesExisting: An int that counts how many Rectangles are presently in existence in the
application (does not include Rectangles that have been destroyed)
blockColour: An object of type Colour (the Colour class is provided for you). This object holds
the colour that the plotted Rectangle will have. A colour is described by four integers, each between
1 and 255 inclusive. The first three numbers indicate the amount of red, green, and blue in
the colour respectively. The fourth number indicates the intensity of the colour (255 is darkest / most
saturated).
The class Rectangle should have the following methods:
Rectangle();
The default constructor
1. sets private members width and height to 10
2. sets members xLocation and yLocation to 10
3. increments counters, rectanglesCreated and rectanglesExisting
4. sets blockColour to black (0, 0, 0, 255)
Rectangle( int xLocationValue, int yLocationValue, int widthValue, int heightValue,
Colour blockColourValue);
Constructor that
1. Initializes width, height, xLocation, yLocation and blockColour to the provided values of the
corresponding actual arguments in the constructor call.
2. Increments both counters, rectanglesCreated and rectanglesExisting.
3. Checks to assure the rectangle is on the page
Rectangle( int xLocationValue, int yLocationValue, Colour blockColourValue);
Constructor that:
1. Initializes width, height and blockColour to the provided values of the corresponding actual
arguments in the constructor call.
2. Sets width and height to 10
3. Increments both counters, rectanglesCreated and rectanglesExisting.
4. Checks to assure the rectangle is on the page
Rectangle(const Rectangle& toBeCopied)
Copy constructor that makes a copy of the Rectangle toBeCopied and increments both counters,
rectanglesCreated and rectanglesExisting.
~Rectangle()
Destructor that destroys an object and decrements the counter rectanglesExisting.
int GetHeight() const;
int GetWidth() const;
int GetXLocation() const;
int GetYLocation() const;
Colour GetBlockColour() const;
static int GetRectanglesCreated();
static int GetRectanglesExisting();
Accessor functions to access each of the private members (to get the values of the private variables
from outside the class). The accessor functions use the const keyword to assure they cannot change
any values of the attributes of the objects. Static member functions are used to access static
members (the counters) so their values can be accessed before you create any rectangles.
An overloaded print function which prints the values of each private member in the Rectangle Class.
The output of the print function should look like
Width 50
Height 30
xLocation 240
yLocation 580
rectanglesCreated 6
rectanglesExisting 6
blockColour red 0 green 0 blue 0 alpha 255
The output should be aligned as shown. Each of the attribute names is printed left justified in a field
20 characters wide, each number left justified in a field 9 characters wide. The colour is printed using
the extraction operator (<<) in the class Colour. The numbers are of course only for illustration and
will be replaced with the actual values of the attributes for the particular object of the class being
printed.
void SetRectangleColour(const Colour blockColorValue);
void SetWidth(const int widthValue);
void SetHeight(const int heightValue);
void SetXLocation(const int xLocationValue);
void SetYLocation(const int yLocationValue);
static void SetRectanglesCreated(int numberCreated);
static void SetRectanglesExisting(int numberExisting);
Mutator functions to set each of the private members (to set the values of each of the private
variables from outside the class). When an attribute value is changed the methods make sure the
change does not cause the upper left corner to be off the page or allow part of the rectangle to
extend off the right hand side of the page or the bottom of the page.
const Rectangle& operator = (const Rectangle& Rectangle2);
bool operator==(const Rectangle& Rectangle2) const;
friend ostream& operator << (ostream& os,
const Rectangle& myRectangle);
overloaded operators, =, = = and <<
1. The << operator should produce the same output as the print function
2. The assignment operator should copy all values of variables.
3. The comparison operator (= =) should make sure that the values of all variable members of the
classes are identical. If any one variable member is not the same in both objects being compared
the objects are not equal.
Part 1 Write additional methods for a class Rectangle: (20 points)
You will be provided with a basic Rectangle Class. Both the Rectangle.h and Rectangle.cpp files are
provided. You will be asked to add two methods to the Rectangle.h and Rectangle.cpp files. Do not
change any of the existing code in Rectangle.h or Rectangle.cpp just add the prototype and
implantations of the two methods. The methods have the following prototypes
bool DoesOverlay(const Rectangle& rectangle2);
bool DoesIntersect(const Rectangle& rectangle2);
Boolean member function DoesOverlay which operates on two rectangles and returns TRUE if the
rectangle RX used to call the member function (RX.DoesOverlay(RY)) is inside the rectangle RY
passed to the member function DoesOverlay through the argument of the function. As an example
the black rectangle in the image below overlays the grey rectangle and the black rectangle overlays
the blue rectangle.
Boolean member function DoesIntersect which operates on two rectangles and returns TRUE if the
rectangles intersect. Two Rectangles intersect if they have ANY pixels in common. As an example
the grey rectangle in the image below intersects the red rectangle and the grey rectangle also
intersects the black rectangle. A rectangle that overlays another rectangle must intersect with that
rectangle.
You will also be provided with a test code, RectangleTest.cpp, that you can use to test your two functions.
The test code will produce the plots below. The parameters of the rectangles illustrated are given in the
tables beside the figures. In the second table the green numbers give the dimensions of the plotted
rectangles after they have been corrected by the constructor or mutator functions to be completely on
the page.
The following corrections are made when a rectangle is partially or completely off the page. These
corrections are made in the order they appear in the list below.
If xLocation or yLocation is off the page both xLocation and yLocation are set to 0
If the rectangle is too wide to completely fit on the page then the width of the rectangle is
truncated so it goes to the right edge of the page and then stops.
If the rectangle is too high to completely fit on the page then the height of the rectangle is
truncated so the rectangle does not extend beyond the bottom of the page.
After these corrections are made the rectangle is printed and / or displayed to the plot. A rectangle is
printed using the Print() method or the overloaded << operator.
The sample test code will be a model for the test program you will need to write to test your class
DiskStack in the next part of this assignment.
colour xLocation yLocation width height
R1 Dark
Blue
225 520 120 100
R2 Black 240 580 50 30
R3 Red 150 300 375 250
R4 Grey 90 400 210 300
R5 Light
blue
195 640 230 110
Colour xLocation yLocation width
R10 Red 610 / 0 810 / 0 200 350
R11 Black 100 / 0 -5 / 0 150 250
R12 Dark Blue -5 / 0 100 / 0 100 125
R13 Purple 550 50 100 / 50 300
R14 Light blue 195 740 230 510 / 60
R15 Grey 400 600 210 / 200 300 / 200
Part 2 (50 Marks) Write a class DiskStack:
Write a C++ class DiskStack using the class Rectangle above. All locations of Rectangles on the page and
sizes of Rectangles are given as integer numbers of pixels. The locations of the corners of a page are
labeled on the diagram below.
Use global variables pageWidth and pageHeight to indicate the horizontal and vertical size of
the page to be plotted. The values in pixels are
o pageWidth =600
o pageHeight=800.
Class DiskStack builds a Stack as illustrated in the diagram above. Class DiskStack has private members
(attributes) listed and explained below. The first six private members are integers. The last two are
pointers to dynamic arrays.
The class DiskStack has the attributes:
StackHeight gives the height (y extent in pixels) of the entire Stack (see diagram above).
(xStackLocation, yStackLocation) defines the location of the bottom left hand corner of the
Rectangle at the bottom of the Stack
StacksExisting counts the number of Stacks presently in existence. This member should have the
same value for all Stacks presently in existence. This number should be incremented every time a
DiskStack is created, and decremented whenever a DiskStack is destroyed.
StacksCreated counts the number of DiskStacks that have been created by the program. This number
should be incremented every time a DiskStack is created.
(0,0)
A
StackHeight
(pageWidth, 0)
(pageWidth, pageHeight)
[0]
[1]
[2]
[3]
(0,pageHeight)
(xStackLocation, yStackLocation),
rectangleWidthArrayp is a pointer to a 1-D array of integers. After the array is dynamically created
in the constructor or mutator methods, the integer in location of 0 of the rectangleWidthArrayp
array will be the width, in pixels, of the bottom Rectangle in the DiskStack. The integer in
rectangleWidthArrayp[k] will be the width, in pixels, of the kth Rectangle in the stack. The width of
rectangle k must be smaller than the width of rectangle k-1
rectangleArrayp, is a pointer to a 1-D array of Rectangles. After the array is dynamically allocated in
the constructor or mutator methods it will be modified to contain each Rectangle in the Stack. The
first Rectangle in the rectangleArrayp will be the bottom Rectangle in the Stack. The last Rectangle
in rectangleArrayp will be the Rectangle at the top of the Stack. All Rectangles in the Stack have the
same height.
The kth rectangle will be stored in rectangleArrayp[k] and the length of the kth Rectangle will be
stored in rectangleWidthArrayp[k].
Your class DiskStack class must include methods
DiskStack();
The default constructor
1. Sets private member numInStack and stackHeight to 0
2. Sets private members xStackLocation and yStackLocation to 0
3. Sets private members rectangleWidthArrayp and rectangleArrayp to nullptr (or NULL)
4. increments static counters, stacksCreated and stacksExisting
DiskStack( int numInStackValue, int stackHeightValue,
int xStackLocationValue, int yStackLocationValue, int *rectangleWidthArraypValue)
Constructor that
1. Sets the pointer attributes rectangleWIdthArrayp and rectangleArrayp to null
2. Checks that the pointer to the array rectangleWidthArraypValue passed to the function is
not NULL. If it is NULL the widths in the array will be calculated in step 5.
3. Initializes numInStack, stackHeight, xStackLocation, and yStackLocation, to the provided
values of the corresponding actual arguments in the constructor call.
Then if necessary corrects them to create an internally consistent stack that is completely on
the page.
The limits on the values of the attributes are given below. The actions to be taken if the
values the attributes the method DiskStack receives are not within those limits, are also
listed below. The purpose of the limits below are to assure the stack is completely on the
page and that the rectangles in the stack are at least ten pixels high and 20 pixels wide. The
checks should be done in the order they are given in this list,
a. If the value of stackHeightValue is not in the range
0 < stackHeightValue < pageLength Then stackHeight = pageLength
If stackHeightValue <= 0 then it is set to 0
b. If the value of numInStackValue is in the range
numInStack > 25 Then numInStack = 25
numInStack < 0 Then numInStack = 0 and stackHeight=0
c. If the value of yStackLocationValue is not in the range
pageLength > yStackLocation >= stackHeight-1
Then set yStackLocation = MAX( stackHeight – 1, 0)
d. If the value of xStackLocationValue is not in the range
1 <= xStackLocationValue < pageWidth/2
Set xStackLocation = pageWidth/2
4. Allocates dynamic memory. If stackHeight > 0
a. Allocates enough space for numInStack rectangles and places the pointer to the new
memory in the attribute rectangleArrayp.
b. Allocates enough space for numInStack integers. Each of these integers will later
represent the width of one of the rectangles. The pointer to the new memory will be
placed in the attribute rectangleWidthArrayp.
5. If the pointer rectangleWidthArraypValue that was supplied for the method was null then
calculate the widths of each rectangle in the stack and place those widths in
rectangleWidthArrayp. The width of the bottommost Rectangle will be 598 (from 1 to 598).
The width of Rectangle k in the stack will be
((numInStack-k)*pageWidth)/numInStack )-2
6. If the pointer rectangleWidthArraypValue is not null then the constructor
a. copies (deep copy) the values of rectangle Length from the array
rectangleWidthArraypValue to the memory pointed to by the pointer attribute
rectangleWidthArrayp.
b. As each element of the array is copied the constructor checks each length to assure
the length is valid.
For the each Rectangle in the stack. If xLocation + rectangleWidthArrayp[k] >=
pageWidth (where xLocation is the calculated x Coordinate for the Rectangle to be
constructed) then reset rectangleWidthArray[k] = pageWidth – xLocation
c. Builds each rectangle starting with the rectangle at the bottom of the stack and
ending with the rectangle at the top of the stack. Put the bottommost rectangle in
the stack in location 0 of the RectangleArrayp array and the nth rectangle in the stack
(going up) in the nth location of the array.
A Copy constructor that makes a copy of the DiskStack with the identifier toBeCopied and
increments both counters, stacksCreated and stacksExisting. Remember you must make a deep
copy of the arrays not just copy the pointers.
A destructor that deletes dynamic memory and decrements stackCreated.
Accessor functions GetStacksExisting and GetStacksCreated ONLY
Mutator functions SetStacksExisting, SetStacksCreated, SetStackHeight, and SetStack ONLY
The mutator SetStack should have the following prototype
void SetStack(int numInStackValue, int StackHeightValue, int xStackLocationValue,
int yStackLocationValue, int *StackWidthArraypValue);
This method will take the provided inputs and set the attributes of the existing DiskStack checking
each for range and consistency. All tests are the same as those used in the second constructor and
should be applied in the same order. The function will then construct the array of Rectangles.
Overloaded operators = and << with prototypes
DiskStack& DiskStack::operator = (const DiskStack &secondDiskStack)
ostream& operator << (ostream& os, const DiskStack& myDiskStack)
The values printed in the sample consoleOut files in the sample output folder for assignment 3 will
give you a pattern to match (character for character) when you print a DiskStack using the <<
operator. Note that the << for Rectangle is used to print each rectangle in the stack.
A display function to plot the Rectangle Stack to the bitmap. This display function should use the
display function for the class Rectangle so that no direct assignment of bits in the bitmap is
necessary. You already know how to display a Rectangle, so display each Rectangle in the
RectangleArrayp array. The prototype of the display function should be
void DiskStackDisplay(BMP& myImageValue, string outFIleValue);
Part 3 (20 Marks) Integration of the supplied Peg class and Rectangle class
and your Rectangle Stack into the towers of Hanoi solution:
Refer to the posted video for a description of the problem and a recursive solution to the towers of
Hanoi problem. You may begin with the solution discussed in the video. You will also use the provided
Peg class, Rectangle class, and the DiskStack class you have already developed. You will need to modify
the towers of Hanoi solution to be consistent with the following prototype
void Towers( int numDisks, Peg& presentPeg, Peg& toPeg, Peg& tempPeg, int displayedStep, BMP
myImage, string imageFileName);
Your new tower function will not only print out the step by step solution to the towers of Hanoi
problem for numDisks disks (as the solution in the video and notes already does), it will also display a
plot of the disks on each peg for one selected step in the solution (see example to the left). To indicate
the particular step to be displayed the parameter displayedStep has been added to the prototype of
the function. displayStep is the number of times a disk has been moved before the displayed step is
reached.
.
In order to be able to plot the disks on each peg (the cross section of each disk on a Peg is a Rectangle
in a Diskstack) we must keep track of which disk is on which peg at all times during the solution of the
towers of Hanoi problem. The Peg class will help us do this. A Peg is a stack of integers. The integers
that are placed on a Peg’s stack represent the diameters of the disks that are presently on the peg.
The integer on the top of the stack is the diameter of the disk of the top of the stack of disks on the
peg. The integer on the bottom of the stack is the diameter of the disk on the bottom of the stack of
disks on the peg. You can remove a disk from a Peg by taking an integer off the top of that Peg’s stack.
To do this (remove the disk from the Peg) use the pop method of the class Peg. The value of the
expression presentPeg.pop() is the value of the integer you removed from the top of the stack of
integers on presentPeg.. You can place a disk on a Peg by placing an integer representing the diameter
of that disk on the stack for that Peg. To do this (add a dis to a Peg) use the push method of the class
Peg. To put the integer diameter1 onto the stack for toPekg you would call the push method as
follows: toPeg.push(diameter1); Therefore, to keep track of what disks are on each peg during the
solution of the towers of Hanoi problem you need to move a disk each time you print out the move in
your towers function. Remember that you need to put all the disks on the fromPeg before the towers
function is called.
The supplied Peg class also allows you to access the numbers in the stack using array index notation
(the index operator [] ). You can determine how many integers are on the Peg by calling the Peg
member function size(), toPeg.size() will have a integer value equal to the number of disks on the
toPeg. Once you know how many disks are on the peg you can access all the integers on the stack (to
move them into an array ready to use in the constructor of a DiskStack as the rectangleWidthArrayp.
To access the ith integer in the stack of the toPeg use the expression toPeg.myPeg[i]. For the integer
on the top of the stack i=size-1, for the integer on the bottom of the stack i=0.
Next you will have to write a DisplayStep function that will display the disks on each of the three pegs
at step displayedStep. There is an example of one such displayed step below. This function should be
called from your towers function,. Be sure that you can plot both the initial state before the first move
(move 0) and the final move (the final state all disks on the toPeg) Also be sure that asking for a move
after the end or before the beginning of the towers solution to be plotted results in an appropriate
error message. Note the labels indicating which peg is which are not part of the expected plotted
output. Each time a DiskStack for the selected step is plotted using the display function it should also
be printed to the console using the << operator. The prototype of this function will be
void displayStep(Peg& fromPeg, Peg& toPeg, Peg& extraPeg, BMP myImage, string imageFileName);
Your display function should produce a plot like the one above and output that matches the supplied
output file character for character.
All disks (Rectangles) plotted should have the same thickness (ydimension)
The thickness of the disks may differ from one plot to another (to accommodate stacks of a
larger number of disks)
The width (dimension in x direction) of the largest disk plotted should be less than the width
of the page
The width of successive disks in the stack should decrease uniformly
You should print error messages and not plot your Rectangle if any part of your Rectangles
will not be contained on the page.
The image of any peg should never fill more than 1/3 of the page
The order of the pegs should be as shown in the diagram above
REMEMBER: You have a member function of class Rectangle, to plot each rectangle, your displayStep
should use this function to plot each rectangle in the stack.
Main program (PARTIALLY SUPPLIED, add code, 10 points)
Your main program should: be in file Hanoi.cpp
Declare and initialize all required local variables including a BMP and three Pegs,
Peg 2
Peg 1
Peg 3
Ask the user for the number of disks in the original stack on the from Peg. The number of disks
should be 0< numDisks < 25.
If the supplied value is not in range re-prompt. There is no maximum number of re-prompts.
Ask to user for the number of the step to be plotted. The step shown should be in the range
0 < stepShown < 2numDisks
If the supplied value is not in range re-prompt. There is no maximum number of re-prompts.
Push the Widths of the rectangles in the original stack onto peg 1. For the ith peg the width of the
rectangle should be
(((numDisks-i)*pageWidth)/numDisks )-2
Prompt for and read the filename for the file that will be used to hold the bitmap plot. The file
should have the extension bmp,
Call the towers function to print the towers solution and plot the requested step
SUBMITTING YOUR RESULTS
Please note that your classes may be tested with additional main programs to assure that all methods
in your classes are working properly. You should submit the following files
Rectangle.cpp
DiskStack.cpp
DiskStack.h
Hanoi.cpp (this file should include your main program and your modified towers function and your
displayStep function)
You are not required to submit an algorithm or test plan.