CIS 212讲解、ArrayList ADTs讲解、C/C++辅导、C/C++编程设计调试 讲解SPSS|辅导留学生Prolog
- 首页 >> Web CIS 212 Project 4
-1-
Use of String and ArrayList ADTs
Due at 11:59pm on Monday, 29 April 2019
In Project 1, we explored the use of pipelines of simple tools in Linux to produce a word
frequency list from a single input file using pipelines of the form
| sort | uniq -c
In the original version of this pipeline, from the textbook on page 37, themore tr invocations> was a single tr invocation that simply converted text
read from standard input into one word per line, where words were separated by white
space.
The solution to Part 1 of Project 1 required that you pipe the output of the previous tr
invocation into another tr invocation, this time converting upper-case letters to lowercase
letters.
The solution to Part 3 of Project 1 required that you start the pipeline with a tr
invocation that converted punctuation characters into spaces, piping it into the original
tr invocation to break up into one word per line.
If this summary is a bit too cryptic for you, please refer to the handout for Project 1, as
well as review Exercise 2-4 starting on page 36 of the textbook.
In this project you are going to write a C program that replaces thetr invocations> part of the pipeline, converting text from one or more input files
into one word per line on standard output.
1 Requirements
1.1 Synopsis
./wordperline [-lp] [FILE …]
wordperline prints each word in the specified files on a line of its own on standard
output; if no files are specified, it processes standard input.
Words, by default, are separated by white space.
wordperline supports the following options:
-l Convert upper-case characters to lower-case.
-p Punctuation characters also separate words.
You are required to use the String and ArrayList abstract data types described in
chapter 5 of the textbook.CIS 212 Project 4
-2-
2 Starting files
In Canvas, in Files/Projects, you will find a gzipped tar archive named
project4start.tgz; this file contains the following files:
input – a file that contains text; this is the same file used in Project 1.
input1, input2 – other files containing text; these are the same files used
in Projects 2 and 3.
tscript – a bash script file that performs a number of tests of your
wordperline using input, input1, input2, and test*.out; invoking
./tscript
will execute all of the tests using your executable wordperline.
test*.out – the correct output files for the tests in tscript.
arraylist.[ch] – header and source file for the ArrayList ADT
stringADT.[ch] – header and source file for the String ADT
iterator.[ch] – header and source file for the Iterator ADT, needed by
ArrayList
3 Hints
I suggest that you thoroughly review Chapter 5 of the textbook on Abstract Data Types. I
have included additional information on how to use ArrayList, String , and
Iterator in sections 6-8 below; you are not required to use the Iterator ADT.
4 Checking that your solution works correctly
tscript takes zero or more arguments; if one or more arguments are specified,
tscript will only perform those specific tests; if no arguments are specified, all of the
tests are performed.
The tests that tscript performs are:
a Tests that you detect non-existent file names, log an error on stderr, and
terminate the program
b Tests that it detects illegal flags and terminates the program.
c Tests that it works correctly with no flags and no file names.
d Tests that it works correctly with –l and no file names.
e Tests that it works correctly with –p and no file names.
f Tests that it works correctly with –l –p and no file names.
g Tests that it works correctly with –lp and no file names.
h Tests that it works correctly with no flags and a single file name.
i Tests that it works correctly with –l and a single file name.CIS 212 Project 4
-3-
j Tests that it works correctly with –p and a single file name.
k Tests that it works correctly with –lp and a single file name.
l Tests that the –l flag works for multiple files.
m Tests that the –p flag works for multiple files.
n Tests that -lp works for multiple files.
For each test, tscript prints out “Starting test”, where
is one of {a, b, c, d, e, f, g, h, i, j, k, l, m, n}; it
then prints a 1-line description of what it is testing; it then prints the actual command
line that it is executing; finally, it prints “Stopping test”.
If there is any output between the actual command line and the Stopping line for any
test but tests a and b, the test has failed.
5 Submission1
You will submit your solutions electronically by uploading a gzipped tar archive2 via
Canvas.
Your TGZ archive should be named-project4.tgz, where is
your “duckid”. It should contain your files wordperline.c and Makefile; it should
also contain a file named report.txt; this file should contain your name, duckid, the
names of any classmates who helped you and what assistance they provided, and the
current state of your solution. Do not include arraylist.[ch],
stringADT.[ch], or iterator.[ch] in your archive; I will use those provided to
you.
6 Use of the String ADT
This section provides a simple usage guide for the String ADT.
6.1 Creating and using an instance of a String
If you have a C string (i.e., an array of char) named str, you can create a String instance
with a declaration of the following form:
#include "stringADT.h"
const String *st = String_create(str);
1 A 75% penalty will be assessed if you do not follow these submission instructions.
2 See section 7 of Canvas/Files/Projects/P1Handout.pdf for instructions if you do not remember how to
create a gzipped tar archive. Obviously, the filenames used for this project will be different.CIS 212 Project 4
-4-
The return value from String_create() should be checked to see if it was
successful; if the return value is NULL, String_create() was unable to create the
ADT instance.
As you can see in the next subsection, there are a large number of methods that you can
invoke on your String instance. For example, if we wanted to convert all lower-case
letters to upper-case letters, we would invoke:
st->upper(st);
If you want to obtain the C string equivalent to the contents of your String instance,
you can do the following (shown using printf()):
printf(“My string is: %s\n”, st->convert(st));
If you want to clear the contents of your String instance, you invoke:
st->clear(st);
Finally, if you want to destroy your String instance, you invoke:
st->destroy(st);
6.2 Methods of the String ADT
In each of the following, it is assumed that you have invoked String_create() to
create a pointer to a String instance named st. Invocation of each method is shown
using this pointer prior to a description of what the method does. Where the description
uses an index, this views st as an array of characters with a starting index of 0, and
an ending index of length-1.
const String *nst = st->copy(st);
Creates a copy of the String st in nst.
const String *nst = st->slice(st, begin, end);
Creates a copy of a slice of st corresponding to [begin,end); begin and end are
integers indicating indices of st that define the slice. If end == 0, it indicates that the
slice is [begin, length of the string).
st->destroy(st);
Destroys the String st; returns all heap allocated storage associated with st to the
heap; no return value.
int status = st->append(st, suffix);
Appends the C string suffix to st; returns 1 if successful, 0 if unsuccessful.
int status = st->assign(st, chr, index);
Assigns the C character chr to st at index; returns 1 if successful, in which case the
previous value at index is overwritten, or 0 if the index is out of bounds.
int status = st->clear(st);
Clears st, such that it contains the empty C string, “”; returns 1 if successful, 0 if
unsuccessful.CIS 212 Project 4
-5-
int status = st->insert(st, substr, index);
Inserts the C string substr into st, starting at index; all current characters from
index to length are shifted up by the length of the substring; returns 0 if illegal
index, 1 otherwise.
st->lower(st);
Converts all upper-case characters in st to lower-case; no return value.
st->lStrip(st);
Remove leading white space from st; all remaining characters are shifted down so that
1st character of the remaining string is at index 0; no return value.
int status = st->remove(st, index);
Removes the character at index; all remaining characters are shifted down; returns 0 if
illegal index; otherwise, returns 1.
int status = st->replace(st, old, new);
Replaces all occurrences of the C string old by the C string new; returns 1 if successful,
0 if unsuccessful.
st->rStrip(st);
Removes trailing white space from st; no return value.
st->strip(st);
Removes leading and trailing white space from st; no return value.
st->upper(st);
Convert all lower-case characters in st to upper-case; no return value.
int value = st->compare(st, ost);
Compares the contents of st with the contents of another String instance, ost; returns
a value less than 0 if st < ost; returns 0 if st == ost; returns a value greater than 0 if
st > ost.
int value = st->endsWith(st, suffix, begin, end);
Checks to see if the [begin,end) slice of st ends with the C string suffix; if end ==
0, it means the length of the string; returns 1 if true, 0 if false.
int ind = st->index(st, substr, begin, end);
Returns the index of the first occurrence of the C string substr in the slice
[begin,end); if end == 0, it means the length of the string; returns the index if
substr is found in the slice, -1 if not.
int value = st->isAlpha(st);
Returns 1 if st has at least one character, and all characters are alphabetic characters;
otherwise, returns 0.
int value = st->isDigit(st);
Returns 1 if st has at least one character, and all characters are digits; otherwise,
returns 0.CIS 212 Project 4
-6-
int value = st->isLower(st);
Returns 1 if st has at least one character, and all alphabetic characters are lower-case;
otherwise, returns 0.
int value = st->isSpace(st);
Returns 1 if st has at least one character, and all characters are whitespace characters;
otherwise, returns 0.
int value = st->isUpper(st);
Returns 1 if st has at least one character, and all alphabetic characters are upper-cases;
otherwise, returns 0.
int size = st->len(st);
Returns the number of characters currently in st.
int ind = st->rindex(st, substr, begin, end);
Returns the index of the last occurrence of the C string substr in the slice
[begin,end); if end == 0, it means the length of the string; returns the index if
substr is found in the slice, -1 if not.
const ArrayList *al = st->split(st, sepstr);
Splits the contents of st into separate words, returning an ArrayList containing the
words; if the C string sepstr is "", it separates words by whitespace; if it contains a
single character, such as ",", it separates words using that character; if any problems
creating the ArrayList, NULL is returned. After you have finished using al, you
must invoke
al->destroy(al, free);
to return the heap storage associated with al.
int value = st->startsWith(st, prefix, begin, end);
Checks to see if the [begin,end) slice of st starts with the C string prefix; if
end == 0, it means the length of the string; returns 1 if true, 0 if false.
char *sp = st->convert(st);
Returns a pointer to the contents of st as a C string.
7 Use of the ArrayList ADT
This section provides a simple usage guide for the ArrayList ADT.
7.1 Creating and using an instance of an ArrayList
You can create an ArrayList instance with a declaration of the following form:
#include "arraylist.h"
const ArrayList *al = ArrayList_create(capacity);
where capacity is a long integer indicating the number of elements you want al to
hold initially; if capacity == 0L, a default capacity is used. The return value from CIS 212 Project 4
-7-
ArrayList_create() should be checked to see if it was successful; if the return
value is NULL, ArrayList_create() was unable to create the ADT instance.
In this project, you will receive a pointer to an ArrayList by calling the split()
method on a String instance.
As you can see in the next subsection, there are a large number of methods that you can
invoke on your ArrayList instance. For example, if we wanted to determine the
current number of elements, we would invoke:
long length = al->size(al);
Suppose that we have an ArrayList that contains C strings (such as would be
returned by the split() method for the String ADT). If we want to process each C
string in the ArrayList in order, we would do the following:
long i;
for (i = 0L; i < al->size(al); i++) {
char *sp;
(void) al->get(al, i, (void **)&sp);
/* do something with the string */
}
We place a (void) in front of the get() method invocation since we know there
cannot be an error return; the (void **) cast is needed to avoid warnings from the
compiler.
Finally, if you want to destroy your ArrayList instance, you invoke:
al->destroy(al, freeFxn);
If the elements that were added to the ArrayList were allocated from the heap (as
for the words added by the split() method in the String ADT), you would specify
the free() function defined in.
#include
al->destroy(al, free);
7.2 Methods of the ArrayList ADT
In each of the following, it is assumed that you have invoked ArrayList_create()
to create a pointer to an String instance named al. Invocation of each method is
shown using this pointer prior to a description of what the method does.
al->destroy(al, freeFxn);
Destroys al; for each occupied index, if freeFxn != NULL, that function is invoked
on the element at that position; the storage associated with al is then returned to the
heap; no return value.CIS 212 Project 4
-8-
al->clear(al, freeFxn);
Clears all elements from al; for each occupied index, if freeFxn != NULL, that
function is invoked on the element at that position; upon return, al will be empty; no
return value.
int status = al->add(al, element);
Appends element (which is of type void *) to al; if no more room in al, it is
dynamically resized; returns 1 if successful, 0 if unsuccessful.
int status = al->ensureCapacity(al, minCapacity);
Ensures that al can hold at least minCapacity (of type long) elements; returns 1 if
successful, 0 if unsuccessful.
int status = al->get(al, index, elementPtr);
Returns the element at the specified index (of type long) in *elementPtr (of type
void **); returns 1 if successful, 0 if illegal index.
int status = al->insert(al, index, element);
Inserts element (of type void *) at the specified index (of type long) in al; all
elements from index onwards are shifted one position to the right; if no more room in
the list, it is dynamically resized; if the current size of the list is N, legal values of index
are in the interval [0, N]; returns 1 if successful, 0 if unsuccessful.
int value = al->isEmpty(al);
Returns 1 if al is empty, 0 if not.
int status = al->remove(al, index, elementPtr);
Removes the element at index (of type long) from al, returning the value that
occupied that position in elementPtr (of type void **); all elements from
[index + 1, size – 1] are shifted one position to the left; returns 1 if
successful, 0 if illegal index value.
int status = al->set(al, index, element, previousPtr);
Replaces the element at index (of type long) with element (of type void *),
returning the element that was replaced in previousPtr (of type void **); returns
1 if successful, 0 if illegal index value.
length = al->size(al);
Returns the number of elements in al as a long integer.
int status al->trimToSize(al);
Trims the capacity of al to its current size; returns 1 if successful, 0 if failure.
const Iterator *it = al->itCreate(al);
Creates a generic iterator to al; returns pointer to the Iterator instance or NULL if
failure.CIS 212 Project 4
-9-
8 Use of the Iterator ADT
This section provides a simple usage guide for the Iterator ADT.
8.1 Creating and using an instance of an Iterator
All of the ADTs that we will use that are containers for other data (ArrayList in this
project) support a factory method (named itCreate()) for creating an iterator to
iterate over the contents of the container.
You can create an Iterator instance given an ArrayList instance al with a
declaration of the following form:
const Iterator *it = al->itCreate(al);
With such an iterator, you can then process each of the elements of an ArrayList
with code such as the following (the following assumes that the ArrayList has C
strings in it):
while (it->hasNext(it) {
char *sp;
(void) it->next(al, i, (void **)&sp);
/* do something with the string */
}
it->destroy(it);
We place a (void) in front of the next() method invocation since we know there
cannot be an error return; the (void **) cast is needed to avoid warnings from the
compiler.
Finally, you must destroy your Iterator instance when you are finished with it;
otherwise, you will leak memory from the heap.
8.2 Methods of the Iterator ADT
In each of the following, it is assumed that you have invoked a factory method to create
a pointer to an Iterator instance named it. Invocation of each method is shown
using this pointer prior to a description of what the method does.
it->hasNext(it);
Returns 1 if the iterator has a next element; returns 0 otherwise.
it->next(it, elementPtr);
Returns the next element in the iterator in elementPtr (of type void **); returns 1 if
successful; returns 0 otherwise.
it->destroy(it);
Destroys the iterator, returning all heap storage associated with the iterator.CIS 212 Project 4
-1-
Grading Rubric
Your submission will be marked on a 50 point scale. Substantial emphasis is placed
upon WORKING submissions, and you will note that a large fraction of the points are
reserved for this aspect. It is to your advantage to ensure that whatever you submit
compiles, links, and runs correctly. The information returned to you will indicate the
number of points awarded for the submission.
You must be sure that your code works correctly on the virtual machine under
VirtualBox, regardless of which platform you use for development and testing. Leave
enough time in your development to fully test on the virtual machine before
submission.
The marking scheme is as follows:
Points Description
5 Your report – honestly describes the state of your submission
Your wordperline passes test a on an unseen set of input files.
Your wordperline passes test b on an unseen set of input files.
Your wordperline passes test c on an unseen set of input files.
Your wordperline passes test d on an unseen set of input files.
Your wordperline passes test e on an unseen set of input files.
Your wordperline passes test f on an unseen set of input files.
Your wordperline passes test g on an unseen set of input files.
Your wordperline passes test h on an unseen set of input files.
Your wordperline passes test i on an unseen set of input files.
Your wordperline passes test j on an unseen set of input files.
Your wordperline passes test k on an unseen set of input files.
Your wordperline passes test l on an unseen set of input files.
Your wordperline passes test m on an unseen set of input files.
Your wordperline passes test n on an unseen set of input files.
wordperline.c successfully compiles
wordperline.c successfully compiles with no warnings
The link phase to create wordperline is successful
The link phase to create wordperline is successful with no warnings
There are no memory leaks in your program
The code could have worked with minor modification to the source.
Note that:
Your report needs to be honest. Stating that everything works and then finding
that it doesn’t is offensive. The 5 points associated with the report are probably
the easiest 5 points you will ever earn as long as you are honest.CIS 212 Project 4
-2-
The 8 points for “could have worked” is the maximum awarded in this category;
your mark in this category may be lower depending upon how close you were to
a working implementation.
-1-
Use of String and ArrayList ADTs
Due at 11:59pm on Monday, 29 April 2019
In Project 1, we explored the use of pipelines of simple tools in Linux to produce a word
frequency list from a single input file using pipelines of the form
In the original version of this pipeline, from the textbook on page 37, the
read from standard input into one word per line, where words were separated by white
space.
The solution to Part 1 of Project 1 required that you pipe the output of the previous tr
invocation into another tr invocation, this time converting upper-case letters to lowercase
letters.
The solution to Part 3 of Project 1 required that you start the pipeline with a tr
invocation that converted punctuation characters into spaces, piping it into the original
tr invocation to break up into one word per line.
If this summary is a bit too cryptic for you, please refer to the handout for Project 1, as
well as review Exercise 2-4 starting on page 36 of the textbook.
In this project you are going to write a C program that replaces the
into one word per line on standard output.
1 Requirements
1.1 Synopsis
./wordperline [-lp] [FILE …]
wordperline prints each word in the specified files on a line of its own on standard
output; if no files are specified, it processes standard input.
Words, by default, are separated by white space.
wordperline supports the following options:
-l Convert upper-case characters to lower-case.
-p Punctuation characters also separate words.
You are required to use the String and ArrayList abstract data types described in
chapter 5 of the textbook.CIS 212 Project 4
-2-
2 Starting files
In Canvas, in Files/Projects, you will find a gzipped tar archive named
project4start.tgz; this file contains the following files:
input – a file that contains text; this is the same file used in Project 1.
input1, input2 – other files containing text; these are the same files used
in Projects 2 and 3.
tscript – a bash script file that performs a number of tests of your
wordperline using input, input1, input2, and test*.out; invoking
./tscript
will execute all of the tests using your executable wordperline.
test*.out – the correct output files for the tests in tscript.
arraylist.[ch] – header and source file for the ArrayList ADT
stringADT.[ch] – header and source file for the String ADT
iterator.[ch] – header and source file for the Iterator ADT, needed by
ArrayList
3 Hints
I suggest that you thoroughly review Chapter 5 of the textbook on Abstract Data Types. I
have included additional information on how to use ArrayList, String , and
Iterator in sections 6-8 below; you are not required to use the Iterator ADT.
4 Checking that your solution works correctly
tscript takes zero or more arguments; if one or more arguments are specified,
tscript will only perform those specific tests; if no arguments are specified, all of the
tests are performed.
The tests that tscript performs are:
a Tests that you detect non-existent file names, log an error on stderr, and
terminate the program
b Tests that it detects illegal flags and terminates the program.
c Tests that it works correctly with no flags and no file names.
d Tests that it works correctly with –l and no file names.
e Tests that it works correctly with –p and no file names.
f Tests that it works correctly with –l –p and no file names.
g Tests that it works correctly with –lp and no file names.
h Tests that it works correctly with no flags and a single file name.
i Tests that it works correctly with –l and a single file name.CIS 212 Project 4
-3-
j Tests that it works correctly with –p and a single file name.
k Tests that it works correctly with –lp and a single file name.
l Tests that the –l flag works for multiple files.
m Tests that the –p flag works for multiple files.
n Tests that -lp works for multiple files.
For each test, tscript prints out “Starting test
then prints a 1-line description of what it is testing; it then prints the actual command
line that it is executing; finally, it prints “Stopping test
If there is any output between the actual command line and the Stopping line for any
test but tests a and b, the test has failed.
5 Submission1
You will submit your solutions electronically by uploading a gzipped tar archive2 via
Canvas.
Your TGZ archive should be named
your “duckid”. It should contain your files wordperline.c and Makefile; it should
also contain a file named report.txt; this file should contain your name, duckid, the
names of any classmates who helped you and what assistance they provided, and the
current state of your solution. Do not include arraylist.[ch],
stringADT.[ch], or iterator.[ch] in your archive; I will use those provided to
you.
6 Use of the String ADT
This section provides a simple usage guide for the String ADT.
6.1 Creating and using an instance of a String
If you have a C string (i.e., an array of char) named str, you can create a String instance
with a declaration of the following form:
#include "stringADT.h"
const String *st = String_create(str);
1 A 75% penalty will be assessed if you do not follow these submission instructions.
2 See section 7 of Canvas/Files/Projects/P1Handout.pdf for instructions if you do not remember how to
create a gzipped tar archive. Obviously, the filenames used for this project will be different.CIS 212 Project 4
-4-
The return value from String_create() should be checked to see if it was
successful; if the return value is NULL, String_create() was unable to create the
ADT instance.
As you can see in the next subsection, there are a large number of methods that you can
invoke on your String instance. For example, if we wanted to convert all lower-case
letters to upper-case letters, we would invoke:
st->upper(st);
If you want to obtain the C string equivalent to the contents of your String instance,
you can do the following (shown using printf()):
printf(“My string is: %s\n”, st->convert(st));
If you want to clear the contents of your String instance, you invoke:
st->clear(st);
Finally, if you want to destroy your String instance, you invoke:
st->destroy(st);
6.2 Methods of the String ADT
In each of the following, it is assumed that you have invoked String_create() to
create a pointer to a String instance named st. Invocation of each method is shown
using this pointer prior to a description of what the method does. Where the description
uses an index, this views st as an array of characters with a starting index of 0, and
an ending index of length-1.
const String *nst = st->copy(st);
Creates a copy of the String st in nst.
const String *nst = st->slice(st, begin, end);
Creates a copy of a slice of st corresponding to [begin,end); begin and end are
integers indicating indices of st that define the slice. If end == 0, it indicates that the
slice is [begin, length of the string).
st->destroy(st);
Destroys the String st; returns all heap allocated storage associated with st to the
heap; no return value.
int status = st->append(st, suffix);
Appends the C string suffix to st; returns 1 if successful, 0 if unsuccessful.
int status = st->assign(st, chr, index);
Assigns the C character chr to st at index; returns 1 if successful, in which case the
previous value at index is overwritten, or 0 if the index is out of bounds.
int status = st->clear(st);
Clears st, such that it contains the empty C string, “”; returns 1 if successful, 0 if
unsuccessful.CIS 212 Project 4
-5-
int status = st->insert(st, substr, index);
Inserts the C string substr into st, starting at index; all current characters from
index to length are shifted up by the length of the substring; returns 0 if illegal
index, 1 otherwise.
st->lower(st);
Converts all upper-case characters in st to lower-case; no return value.
st->lStrip(st);
Remove leading white space from st; all remaining characters are shifted down so that
1st character of the remaining string is at index 0; no return value.
int status = st->remove(st, index);
Removes the character at index; all remaining characters are shifted down; returns 0 if
illegal index; otherwise, returns 1.
int status = st->replace(st, old, new);
Replaces all occurrences of the C string old by the C string new; returns 1 if successful,
0 if unsuccessful.
st->rStrip(st);
Removes trailing white space from st; no return value.
st->strip(st);
Removes leading and trailing white space from st; no return value.
st->upper(st);
Convert all lower-case characters in st to upper-case; no return value.
int value = st->compare(st, ost);
Compares the contents of st with the contents of another String instance, ost; returns
a value less than 0 if st < ost; returns 0 if st == ost; returns a value greater than 0 if
st > ost.
int value = st->endsWith(st, suffix, begin, end);
Checks to see if the [begin,end) slice of st ends with the C string suffix; if end ==
0, it means the length of the string; returns 1 if true, 0 if false.
int ind = st->index(st, substr, begin, end);
Returns the index of the first occurrence of the C string substr in the slice
[begin,end); if end == 0, it means the length of the string; returns the index if
substr is found in the slice, -1 if not.
int value = st->isAlpha(st);
Returns 1 if st has at least one character, and all characters are alphabetic characters;
otherwise, returns 0.
int value = st->isDigit(st);
Returns 1 if st has at least one character, and all characters are digits; otherwise,
returns 0.CIS 212 Project 4
-6-
int value = st->isLower(st);
Returns 1 if st has at least one character, and all alphabetic characters are lower-case;
otherwise, returns 0.
int value = st->isSpace(st);
Returns 1 if st has at least one character, and all characters are whitespace characters;
otherwise, returns 0.
int value = st->isUpper(st);
Returns 1 if st has at least one character, and all alphabetic characters are upper-cases;
otherwise, returns 0.
int size = st->len(st);
Returns the number of characters currently in st.
int ind = st->rindex(st, substr, begin, end);
Returns the index of the last occurrence of the C string substr in the slice
[begin,end); if end == 0, it means the length of the string; returns the index if
substr is found in the slice, -1 if not.
const ArrayList *al = st->split(st, sepstr);
Splits the contents of st into separate words, returning an ArrayList containing the
words; if the C string sepstr is "", it separates words by whitespace; if it contains a
single character, such as ",", it separates words using that character; if any problems
creating the ArrayList, NULL is returned. After you have finished using al, you
must invoke
al->destroy(al, free);
to return the heap storage associated with al.
int value = st->startsWith(st, prefix, begin, end);
Checks to see if the [begin,end) slice of st starts with the C string prefix; if
end == 0, it means the length of the string; returns 1 if true, 0 if false.
char *sp = st->convert(st);
Returns a pointer to the contents of st as a C string.
7 Use of the ArrayList ADT
This section provides a simple usage guide for the ArrayList ADT.
7.1 Creating and using an instance of an ArrayList
You can create an ArrayList instance with a declaration of the following form:
#include "arraylist.h"
const ArrayList *al = ArrayList_create(capacity);
where capacity is a long integer indicating the number of elements you want al to
hold initially; if capacity == 0L, a default capacity is used. The return value from CIS 212 Project 4
-7-
ArrayList_create() should be checked to see if it was successful; if the return
value is NULL, ArrayList_create() was unable to create the ADT instance.
In this project, you will receive a pointer to an ArrayList by calling the split()
method on a String instance.
As you can see in the next subsection, there are a large number of methods that you can
invoke on your ArrayList instance. For example, if we wanted to determine the
current number of elements, we would invoke:
long length = al->size(al);
Suppose that we have an ArrayList that contains C strings (such as would be
returned by the split() method for the String ADT). If we want to process each C
string in the ArrayList in order, we would do the following:
long i;
for (i = 0L; i < al->size(al); i++) {
char *sp;
(void) al->get(al, i, (void **)&sp);
/* do something with the string */
}
We place a (void) in front of the get() method invocation since we know there
cannot be an error return; the (void **) cast is needed to avoid warnings from the
compiler.
Finally, if you want to destroy your ArrayList instance, you invoke:
al->destroy(al, freeFxn);
If the elements that were added to the ArrayList were allocated from the heap (as
for the words added by the split() method in the String ADT), you would specify
the free() function defined in
#include
al->destroy(al, free);
7.2 Methods of the ArrayList ADT
In each of the following, it is assumed that you have invoked ArrayList_create()
to create a pointer to an String instance named al. Invocation of each method is
shown using this pointer prior to a description of what the method does.
al->destroy(al, freeFxn);
Destroys al; for each occupied index, if freeFxn != NULL, that function is invoked
on the element at that position; the storage associated with al is then returned to the
heap; no return value.CIS 212 Project 4
-8-
al->clear(al, freeFxn);
Clears all elements from al; for each occupied index, if freeFxn != NULL, that
function is invoked on the element at that position; upon return, al will be empty; no
return value.
int status = al->add(al, element);
Appends element (which is of type void *) to al; if no more room in al, it is
dynamically resized; returns 1 if successful, 0 if unsuccessful.
int status = al->ensureCapacity(al, minCapacity);
Ensures that al can hold at least minCapacity (of type long) elements; returns 1 if
successful, 0 if unsuccessful.
int status = al->get(al, index, elementPtr);
Returns the element at the specified index (of type long) in *elementPtr (of type
void **); returns 1 if successful, 0 if illegal index.
int status = al->insert(al, index, element);
Inserts element (of type void *) at the specified index (of type long) in al; all
elements from index onwards are shifted one position to the right; if no more room in
the list, it is dynamically resized; if the current size of the list is N, legal values of index
are in the interval [0, N]; returns 1 if successful, 0 if unsuccessful.
int value = al->isEmpty(al);
Returns 1 if al is empty, 0 if not.
int status = al->remove(al, index, elementPtr);
Removes the element at index (of type long) from al, returning the value that
occupied that position in elementPtr (of type void **); all elements from
[index + 1, size – 1] are shifted one position to the left; returns 1 if
successful, 0 if illegal index value.
int status = al->set(al, index, element, previousPtr);
Replaces the element at index (of type long) with element (of type void *),
returning the element that was replaced in previousPtr (of type void **); returns
1 if successful, 0 if illegal index value.
length = al->size(al);
Returns the number of elements in al as a long integer.
int status al->trimToSize(al);
Trims the capacity of al to its current size; returns 1 if successful, 0 if failure.
const Iterator *it = al->itCreate(al);
Creates a generic iterator to al; returns pointer to the Iterator instance or NULL if
failure.CIS 212 Project 4
-9-
8 Use of the Iterator ADT
This section provides a simple usage guide for the Iterator ADT.
8.1 Creating and using an instance of an Iterator
All of the ADTs that we will use that are containers for other data (ArrayList in this
project) support a factory method (named itCreate()) for creating an iterator to
iterate over the contents of the container.
You can create an Iterator instance given an ArrayList instance al with a
declaration of the following form:
const Iterator *it = al->itCreate(al);
With such an iterator, you can then process each of the elements of an ArrayList
with code such as the following (the following assumes that the ArrayList has C
strings in it):
while (it->hasNext(it) {
char *sp;
(void) it->next(al, i, (void **)&sp);
/* do something with the string */
}
it->destroy(it);
We place a (void) in front of the next() method invocation since we know there
cannot be an error return; the (void **) cast is needed to avoid warnings from the
compiler.
Finally, you must destroy your Iterator instance when you are finished with it;
otherwise, you will leak memory from the heap.
8.2 Methods of the Iterator ADT
In each of the following, it is assumed that you have invoked a factory method to create
a pointer to an Iterator instance named it. Invocation of each method is shown
using this pointer prior to a description of what the method does.
it->hasNext(it);
Returns 1 if the iterator has a next element; returns 0 otherwise.
it->next(it, elementPtr);
Returns the next element in the iterator in elementPtr (of type void **); returns 1 if
successful; returns 0 otherwise.
it->destroy(it);
Destroys the iterator, returning all heap storage associated with the iterator.CIS 212 Project 4
-1-
Grading Rubric
Your submission will be marked on a 50 point scale. Substantial emphasis is placed
upon WORKING submissions, and you will note that a large fraction of the points are
reserved for this aspect. It is to your advantage to ensure that whatever you submit
compiles, links, and runs correctly. The information returned to you will indicate the
number of points awarded for the submission.
You must be sure that your code works correctly on the virtual machine under
VirtualBox, regardless of which platform you use for development and testing. Leave
enough time in your development to fully test on the virtual machine before
submission.
The marking scheme is as follows:
Points Description
5 Your report – honestly describes the state of your submission
Your wordperline passes test a on an unseen set of input files.
Your wordperline passes test b on an unseen set of input files.
Your wordperline passes test c on an unseen set of input files.
Your wordperline passes test d on an unseen set of input files.
Your wordperline passes test e on an unseen set of input files.
Your wordperline passes test f on an unseen set of input files.
Your wordperline passes test g on an unseen set of input files.
Your wordperline passes test h on an unseen set of input files.
Your wordperline passes test i on an unseen set of input files.
Your wordperline passes test j on an unseen set of input files.
Your wordperline passes test k on an unseen set of input files.
Your wordperline passes test l on an unseen set of input files.
Your wordperline passes test m on an unseen set of input files.
Your wordperline passes test n on an unseen set of input files.
wordperline.c successfully compiles
wordperline.c successfully compiles with no warnings
The link phase to create wordperline is successful
The link phase to create wordperline is successful with no warnings
There are no memory leaks in your program
The code could have worked with minor modification to the source.
Note that:
Your report needs to be honest. Stating that everything works and then finding
that it doesn’t is offensive. The 5 points associated with the report are probably
the easiest 5 points you will ever earn as long as you are honest.CIS 212 Project 4
-2-
The 8 points for “could have worked” is the maximum awarded in this category;
your mark in this category may be lower depending upon how close you were to
a working implementation.