Lab 04: a few pointers
Due Thursday, October 1st, by 4pm
This work continues with exercises similar to the work of Lab 04. We
have two new programs to complete, one called sequence.cc
that allows you to edit a sequence of integers, and another called
rotate.cc that processes a text file containing ASCII art and outputs
a new text file containing that art rotated 90 degrees. Both programs
rely on the use of a pointer to a struct. And that struct acts as a
“cover object” with links to an underlying data structure representing
it.
For the sequence program, the underlying data structure
is just an array of integers, where the first size items
constitute an integer sequence. But, as the program edits the sequence
(with user commands insert, append, and
remove) that array might need to get resized to have
storage for larger sequences. Your jon is to write some of the functions
that edit the sequence.
For the rotate program, the underlying data structure is
essentially a “two-dimensional array” of characters so as to represent
the grid of an ASCII art image. To do this we have a field named
image of an asciiArt struct. Its type is
char** image;
Each line of the image is represented as an array of characters, so
that means it is a pointer of type char*. Since we want
several lines, an image is an array of these char*
pointers. It is of type (char*)*, or simply
char**. The image field points to an array of
arrays.
For this second exercise, you’ll write the code that takes an
asciiArt pointer and invents a new asciiArt
struct on the heap that is a rotated version of the input image.
I briefly describe each exercise below. The details for the work can
also be found by reading the comments within the two source
.cc files.
These two programs can be built using the commands
make sequence and make rotate, which relies on
the provided Makefile (just like we used in lab).
Exercises
Exercise 1. sequence
I’ve written the code for the newSequence,
append, and release functions. The first
creates a new sequence data structure on the heap and
returns a pointer to it. The integer sequence it creates is empty
initially, but some space gets allocated to store elements that may get
added later. The second uses that extra space to stick a new value onto
the end of the sequence. And the last gives back the storage allocated
for that data structure to the memory heap.
You are to complete the code of these four functions.
Part 1: output
As the code currently runs, the program outputs a sequence by printing
its integers separated by spaces (and with an extra space at the end.
Modify this code so that it instead formats the output to use brackets
and commas like so:
[47, 37, 18]
[10]
[]
You’ll want to check the size field of S to
see how many items are in that sequence, and format the output in those
three ways accordingly.
Part 2: resize
The main function builds an empty sequence data structure
with capacity to hold two integers using the line:
sequence* seq = newSequence(2);
Under the covers, an array seq->elements gets built
with length 2 within the heap, and seq->size is set to
0. This means that the code can only add two integers to that empty
sequence.
But I’ve written append so that, should more than two
integers be added by the user, the function calls a procedure
resize to allocate a larger array of integers, so that that
extra value can then be placed on the end. I’d like you to write the
code for resize to make it do that properly.
Roughly expressed, here is what your code needs to do:
Describe a new integer array variable
newElements.
Request a new array with room for newCapacity
integers.
Copy the data from S->elements into
newElements.
Give back the smaller array using delete.
Make the S struct use that new storage.
Part 3: insert
Now finish the code for the other two editing functions. Inserting, like
append, may need to resize the array. But, regardless, it
should move the sequence data in the array one position to the right,
making room to add that new value v at position
i.
Part 4: remove This code need not
resize the array. It should move the sequence data right of position
i to the left one position. This has the effect of
“deleting” the i-th value from the sequence.
Exercise 2. rotate
The code in rotate.cc is meant to be a program that
reads a file of ASCII art. That might be something like:
.S_sSSs sSSs sSSs .S_sSSs sSSs sSSs
.SS~YS%%b d%%SP d%%SP .SS~YS%%b d%%SP d%%SP
S%S `S%b d%S' d%S' S%S `S%b d%S' d%S'
S%S S%S S%S S%S S%S S%S S%S S%|
S%S d*S S&S S&S S%S S&S S&S S&S
S&S .S*S S&S_Ss S&S_Ss S&S S&S S&S Y&Ss
S&S_sdSSS S&S~SP S&S~SP S&S S&S S&S `S&&S
S&S~YSY%b S&S S&S S&S S&S S&S `S*S
S*S `S%b S*b S*b S*S d*S S*b l*S
S*S S%S S*S. S*S. S*S .S*S S*S. .S*P
S*S S&S SSSbs SSSbs S*S_sdSSS SSSbs sSS*S
S*S SSS YSSP YSSP SSS~YSSY YSSP YSS'
SP
Y
And then, once working, rotates it like so (thanks PATORJK:
YSSSSSSSSSSS..
P****&&&%%%SS
SSSSSSSSSSS_
~_ ~s
Ys YS
Sd SS
`YS. `%s
SSSS%SSdSS%
S&%%bS**%%b
SSSb SSSb
SSSSSSSd
S**&&&&%%ds
YSSbSSSSSS%S
SS. ~_ '%S
Sb SS Ss
Ps Ps P
SSSSSSSd
S**&&&&%%ds
YSSbSSSSSS%S
SS. ~_ '%S
Sb SS Ss
Ps Ps P
SSSSSSSSSS..
S***&&&%%%SS
SSSSSSSSSSS_
~_ ~s
Ys YS
Sd SS
SS. `%s
YSSdSSSSSS%
S**&&&&%%b
SSSSSSSb
SSSSSSSd
S**&&&&%%ds
YSSbSSSSSS%S
SS. '%S
Sb Ss
Ps P
Ys `YSSd
SS S&&%%ds
SS. `&SS|S%S
'*SlS&s '%S
S***S Ss
PSS P
The files themselves have extra information in their first line,
giving their height and width information. A bunch of these
.txt files can be found in this repo. For example, you can
use the cat command and see
% cat sample.txt
7 10
@###@
#...#
%##@...#
#......#
%######@
Two of these are quite large, generated from famous works of art,
found at Ian
Parberry’s site.
I also have provided a folder full of sample output for the
rotate program. I generated each of these with my solution
to the exercise. For example, if I typed
% ./rotate sample.txt
I would get a new file named sample-90.txt in my same
folder that has the contents
10 7
%#%
#.#
#.#
#.@#@
#...#
#...#
#...#
@###@
The code relies on a cool Unix trick that I’ve hinted at in class.
The main function can take two parameters (instead of
void) named argc and argv. The
first of these argc gives the integer count of the number
of command-line arguments provided to rotate. Strangely,
the command word rotate is couinted as one of the
arguments, and so the command rotate sample.txt has a count
of 2. The second of these argv is an
“argument vector”, of type char**, so it is an array of an
array of characters.
The program, then, gets the filename string sample.txt
from the array argv[1].
As the code runs now, it performs no rotation. Instead it just
outputs the image contents of the ASCII art file that it reads. Delete
those lines, and uncomment the lines at the bottom. Then write and test
your code for rotationOf, the function that does all the
rotation work. Roughly expressed, that code needs to:
Allocate the asciiArt struct for the rotated image,
as pointer outputArt.
Set outputArt->image to be a new array of
rows.
Allocate each row outputArt->image[row] as an
array of characters.
Set each of the characters
outputArt->image[row][column] based on
inputArt.
If you want to see similar work, look at readImage which
builds an asciiArt struct from the contents of the input
file.